第一篇：數(shù)據(jù)結構課程設計正文
兩種常用查找算法的
比較與實現(xiàn)
摘 要：本次課程設計主要研究幾種常用查找算法的比較與實現(xiàn)，查找的算法有很多種：靜態(tài)查找表的順序表、有序表、索引順序表等查找結構；動態(tài)查找表的二叉排序樹、哈希查找等查找結構。本次的課程設計主要研究兩種常見的查找算法：順序查找和折半查找，分析比較它們的時間復雜度，并且在此基礎上用C語言對它們進行算法編程、調試和運行。
關鍵詞：C語言；順序查找；折半查找;時間復雜度。
１ 引 言
“數(shù)據(jù)結構”在計算機科學中是一門綜合性的專業(yè)基礎課，“數(shù)據(jù)結構”的研究不僅涉及到計算機硬件的研究范圍，而且和計算機軟件的研究有著密切的關系無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，一遍查找和存取數(shù)據(jù)元素更為方便。因此，可以認為“數(shù)據(jù)結構”是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。
課程設計是我們專業(yè)課程知識綜合應用的實踐訓練，是實踐性教學的一個重要環(huán)節(jié)。而數(shù)據(jù)結構的課程設計，更要求學生在數(shù)據(jù)結構的邏輯特性和物理表示、數(shù)據(jù)結構的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。
在日常生活中，人們幾乎每天都要進行“查找”工作。例如，在電話號碼薄中查閱“某單位”或“某人”的電話號碼；在字典中查閱“某個詞”的讀音和含義等等。而同樣地，在各種系統(tǒng)軟件和應用軟件中，也存在“查找”：如編譯程序中符號表、信息處理表中相關信息的查找。所以，“查找”就是在一個含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄）。
【1】在計算機中進行查找的方法也會隨數(shù)據(jù)結構不同而不同。在此，引入“查找表”的概念：同類數(shù)據(jù)元素構成的集合。所以，這次的課程設計就可以從靜態(tài)查找表的幾種典型的算法來實現(xiàn)對數(shù)據(jù)元素的查找的算法和操作的實現(xiàn)和比較。
1.1課程設計背景
《數(shù)據(jù)結構》課程設計作為獨立的教學環(huán)節(jié)，是計算機相關專業(yè)集中實踐環(huán)節(jié)系列之一，是學習完《數(shù)據(jù)結構》課程后進行的一次全面的綜合練習。所以需要我們了解并掌握數(shù)據(jù)結構與算法的設計方法，并且具備初步的獨立分析和設計能力，同時要掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼測試等基本方法和技能，提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力。所以這次課程設計的目的在于：加強學生對C語言的基本知識和技能；加深對數(shù)據(jù)結構基礎理論和基本知識的理解，提高解決實際問題的實踐能力；同時幫助調動學生的積極性和能動性，培養(yǎng)學生的自學、動手能力。
２
1.2課程設計目標
本次課程設計，我準備用不同的兩種常見的查找方法：針對順序查找表中查找方法，如順序查找、折半查找等。并且通過用這些算法實現(xiàn)對某個“特定的”數(shù)據(jù)元素（關鍵字）的查找，分析這些操作的性能：它們各自的時間復雜度、空間復雜度和其它的一些性能，同時記錄每種查找方法的優(yōu)缺點，比較得出它們的查找效率和查找范圍。
３ 設計概要
2.1 問題描述
對于不同的查找算法，它們各自的時間復雜度和空間復雜度不同，查找的思想和算法也明顯不同，所以要分析它們的特點和效率，我們要多方面比較：要比較時間復雜度，我們可以從它們的查找長度側面比較出來；而它們算法的實現(xiàn)就要熟悉它們的查找思想，熟練應用C語言編寫合適的程序。
2.2 設計思路
靜態(tài)查找表有順序表和鏈式表兩種表示方法，在這次的課程設計里，我用順序存儲表來表示這兩種查找算法的程序。我的設計思路及步驟如下：
（1）熟悉兩種算法的編程思想,畫出流程圖。
（2）先編寫兩種算法的子程序，再遍寫主程序調用它們。
（3）分步調試子程序和主程序，直到不再出現(xiàn)錯誤，然后運行程序，檢查是否和 自己當初的設想一樣，一直到結果能讓自己滿意。（4）比較得出兩種查找算法的優(yōu)缺。
2.3 相關的知識點
（1）C語言表示靜態(tài)查找表的順序存儲結構 typedef struct { ElemType *elem;
//數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空
int length;
//表的長度
} SSTable;
４（2）查找算法的衡量指標
查找可能產(chǎn)生“成功”與“不成功”兩種結果，但在實際應用的大多數(shù)情況下，查找成功的可能性比不成功的可能性大得多，特別是在記錄數(shù)中n很大時，查找不成功的概率可以忽略不計。當查找不成功的情況不能忽視時，查找算法的平均長度應該是查找成功時的平均查找長度與查找不成功時的平均查找長度之和，平均查找長度為： ASL= ?pi?cii?1n
其中，n為元素的個數(shù)； ci是查找第i 個記錄需進行的比較次數(shù)；pi是查找第i個記錄的概率，一般可認為查找每個記錄的概率是相等的，即p1=p2=?=pn=1/n?！?】
５ 算法分析及程序編寫
3.1.順序表的查找
（1）基本思想
從查找表的一端開始，逐個將記錄的關鍵字值和給定值進行比較，如果某個記錄的關鍵字值和給定值相等，則稱查找成功；否則，說明查找表中不存在關鍵字值為給定值的記錄，則稱查找失敗。（2）順序查找算法流程圖
算法流程圖如圖3-1所示：
圖3-1：順序查找算法流程圖
６（3）順序查找算法代碼如下
int Search_Seq(SSTable *table, ElemType key){
/*在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為零。*/
table->elem[0]=key;
//設置哨兵 int result=0;
// 找不到時，返回0 int i;for(i=table->length;i>=1;i--)
{
//從后往前找
if(table->elem[i]==key)
{
} result=i;
//找到關鍵字的時候，該元素的位置 break;
}
return result;
//找不到時返回 } <4>順序查找算法性能分析
對于順序查找，不論給定值key為何值，查找不成功時和給定值進行比較的關鍵字個數(shù)均為n+1.假設查找成功與不成功的可能性相同，對每個記錄的查找概率也相等，則Pi=1/（2n）,此時順序查找的平均查找長度為[3]：
ASL= ?(ni?1n?i?1)+(1/2)(n+1)
=(3/4)(n+1)
<5>結論
順序查找的優(yōu)點是算法簡單，且對表的結構沒有任何要求。它的缺點是查找效率低，因此，當表中元素個數(shù)比較多時，不宜采用順序查找。
７
3.2.折半查找
（1）使用折半查找必須具備兩個前提條件
a：要求查找表中的記錄按關鍵字有序(假設：從小到大有序)b：只能適用于順序存儲結構
（2）基本思想
先取查找表的中間位置的關鍵字值與給定關鍵字值作比較，若它們的值相等，則查找成功；如果給定值比該記錄的關鍵字值大，說明要查找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折半查找；若給定值比該記錄的關鍵字值小，說明要查找的記錄一定在查找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找，直到查找成功，或者查找失敗。
(3）查找流程圖
流程圖如圖3-2所示：
８
圖3-2：折半查找算法流程圖
(4）折半查找算法的代碼
int Search_Bin(SSTable *table, ElemType key){
/*在有序表ST中折半查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0.*/
int low=1;
int high=table->length;
//置區(qū)間初值
int result=0;// 找不到時，返回0 while(low <= high)
９
{
} return result;int mid=(low+high)/2;
//中間的數(shù)據(jù)元素 if(table->elem[mid]==key){ result=mid;break;}
//找到待查元素 else if(key
//繼續(xù)在前半?yún)^(qū)間進行查找 else { low=mid+1;}
//繼續(xù)在后半?yún)^(qū)間進行查找
}[5]
（5）折半查找算法性能分析
在折半查找的過程中，每經(jīng)過一次比較，查找范圍都要縮小一半，所以折半查找的最大查找長度為
MSL=[log2 n]+1 當n足夠大時，可近似的表示為log2(n)。（6）結論
折半查找要求查找表按關鍵字有序，而排序是一種很費時的運算；另外，折半查找要求表是順序存儲的，為保持表的有序性，在進行插入和刪除操作時，都必須移動大量記錄。因此，折半查找的高查找效率是以犧牲排序為代價的，它特別適合于一經(jīng)建立就很少移動、而又經(jīng)常需要查找的線性表。
可見在查找速度上，折半查找比順序查找速度要快的多，這是它的主要優(yōu)點[4]。
１０ 測試分析
1.輸入元素有誤
（1）：若輸入的元素個數(shù)不合理，元素個數(shù)少于n，這種輸入造成的的結果是系統(tǒng)一直等待元素的輸入，即得不到結果。如圖4-1所示：
圖4-1：輸入元素個數(shù)少時的運行情況
（2）若輸入元素個數(shù)大于n時，系統(tǒng)將從第一個元素起，自動選取前n個元素作為有效元素，進行程序的后續(xù)運行。這種情況下的結果如圖4-2所示：
圖4-2：輸入元素個數(shù)多時的運行情況
１１
2.查找失敗
這種情況是指在n個元素中沒有與關鍵字相同的元素存在，所以程序運行的結果是查找失敗。運行結果如圖4-3所示：
圖4-3：查找失敗時的運行情況
3.查找成功
若查找成功，即元素輸入無誤，且有關鍵字存在的情況，這個時候的運行結果如圖4-4所示[5]：
圖4-4：查找成功時的運行情況
１２ 總結和體會
5.1 課程設計總結
“書到用時方恨少”。在這次課程設計，我感觸最深的當屬查閱大量的設計資料了，為了讓自己的設計更加完善，查閱這方面的設計資料是十分必要的，看著那么大疊的書籍、資料擺在自己的面前，有些時候還要上網(wǎng)查閱相關知識點，并且還要整理出有用的知識點，這對于我來說，是在是個不小的挑戰(zhàn)。所以，以后一定要多看自己專業(yè)方面的書籍，增長自己的知識。而且，寫程序是一件十分需要耐心的活，一個不小心，后果就可能是幾個小時的思考和調試，幸好這次的課題我并不陌生，所以，并沒有自己想象中的艱難。但是，用的時間和精力卻絕對也不少。
5.2 心得與體會
這次課程設計，使我對《數(shù)據(jù)結構》這門課程有了更深入的了解?！稊?shù)據(jù)結構》是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。一個人的力量是有限的，要想把課程設計做的更好，就要學會參考一定的資料，吸取別人的經(jīng)驗，讓自己和別人的思想有機的結合起來，得出屬于你自己的靈感。
在本課程設計中，我明白了理論與實際應用相結合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設計技能以及合作能力。這次課程設計同樣提高了我的綜合運用所學知識的能力。程序的編寫需要有耐心，有些事情看起來很復雜，但問題需要一點一點去解決，分析問題，把問題一個一個劃分，劃分成小塊以后就逐個去解決。再總體解決大的問題。這樣做起來不僅有條理也使問題得到了輕松的解決。
通過這兩周的課程設計，我認識到數(shù)據(jù)結構是一門比較難的課程。需要多花時間上機練習。這次的程序訓練培養(yǎng)了我實際分析問題、編程和動手能力，使我掌握了程序設計的基本技能，提高了我適應實際，實踐編程的能力。
１３
參考文獻：
[1]嚴蔚敏，吳偉民.《數(shù)據(jù)結構:C語言版》 清華大學出版社，2012.5 [2]Mark Allen Weiss.數(shù)據(jù)結構與算法分析——C語言描述（英文版第二版）.北京：人民郵電出版社，2005 [3]李峰，謝中科.C語言程序設計.上海：復旦大學出版社，2011 [4]Baloukas, C., Risco-Martin, J.L., Atienza, D., et al.Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systems[J].Journal of Systems and Software, 2009, 82(4): 590-602.[5]李春葆，尹為民.數(shù)據(jù)結構教程上機指導（第三版）.北京：清華大學出版社,2008
１４
附錄：程序源代碼：
#include
using namespace std;typedef int ElemType;
//用C語言定義順序存儲結構
typedef struct {
ElemType *elem;
//數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空
int length;
//表的長度 } SSTable;
void Create(SSTable *table, int length);
// 構建順序表
void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);
void Traverse(SSTable *table, void(*visit)(ElemType elem));
void Create(SSTable **table, int length){
// 構建順序表
SSTable *t =(SSTable*)malloc(sizeof(SSTable));
１５ t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));t->length=length;*table=t;} void FillTable(SSTable *table){
// 無序表的輸入
ElemType *t=table->elem;for(int i=0;i
t++;
scanf(“%d”, t);
getchar();} } void Destroy(SSTable *table){
//銷毀表
free(table->elem);free(table);} void PrintTable(SSTable *table){
// 打印查找表中的元素
int i;ElemType *t=table->elem;
１６ for(i=0;i
} } //順序（哨兵）查找算法
int Search_Seq(SSTable *table, ElemType key){
/*在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為零。*/
table->elem[0]=key;
//設置哨兵 int result=0;
// 找不到時，返回0 int i;for(i=table->length;i>=1;i--)
{
//從后往前找
if(table->elem[i]==key)
} {
} result=i;
//找到關鍵字的時候，該元素的位置 break;
return result;
//找不到時返回 }
１７
void Sort(SSTable *table){
// 排序算法
int i, j;ElemType temp;
for(i=table->length;i>=1;i--)
// 從前往后找 {
for(j=1;j } int Search_Bin(SSTable *table, ElemType key){ /*在有序表ST中折半查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元 } { } if(table->elem[j]>table->elem[j+1]){ //從小到大排列 } temp=table->elem[j];table->elem[j]=table->elem[j+1];//元素后移 table->elem[j+1]=temp;素在表中的位置，否則為0.*/ int low=1; １８ } int high=table->length; //置區(qū)間初值 int result=0;// 找不到時，返回0 while(low <= high){ } return result;int mid=(low+high)/2; //中間的數(shù)據(jù)元素 if(table->elem[mid]==key){ result=mid;break;} //找到待查元素 else if(key //繼續(xù)在前半?yún)^(qū)間進行查找 else { low=mid+1;} //繼續(xù)在后半?yún)^(qū)間進行查找 // 主函數(shù) １９ int main(int argc, char* argv[]){ SSTable *table; int r; //元素的位置 int n;ElemType key;printf(“輸入 n:”);scanf(“%d”,&n); Create(&table, n);//建立表 cout<<“請輸入”< printf(“您輸入的 %d 個值是：n”,n); PrintTable(table);//打印無序表 cout< printf(“順序法查找運行結果如下：n ”);Search_Seq(table,key);//順序（哨兵）查找算法 r=Search_Seq(table,key); if(r>0) printf(“ 關鍵字 %d 在表中的位置是： %dn”,key, r); else printf(“查找失敗，表中無此數(shù)據(jù)。n”); ２０ Sort(table);//對無序表進行排序 printf(“數(shù)據(jù)排序后的順序如下：n ”);PrintTable(table);//打印有序表 printf(“n”); printf(“折半查找法運行結果如下：n ”); r=Search_Bin(table,key);//折半查找算法 if(r>0)printf(“ 關鍵字 %d 在表中的位置是： %dn”,key, r); else { printf(“查找失敗，表中無此數(shù)據(jù)。n”);} } return 0;２１ 數(shù) 據(jù) 結 構 課程設計報告 題 目： 一元多項式計算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學 號： 201201011367 姓 名： 左帥帥 指導老師： 郝慎學 時 間： 一、課程設計題目分析 本課程設計要求利用C語言或C++編寫，本程序實現(xiàn)了一元多項式的加法、減法、乘法、除法運算等功能。 二、設計思路 本程序采用C語言來完成課程設計。 1、首先，利用順序存儲結構來構造兩個存儲多項式A(x)和 B(x)的結構。 2、然后把輸入，加，減，乘，除運算分成五個主要的模塊：實現(xiàn)多項式輸入模塊、實現(xiàn)加法的模塊、實現(xiàn)減法的模塊、實現(xiàn)乘法的模塊、實現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調用來實現(xiàn)其功能，盡量減少程序運行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實現(xiàn)對多項式輸入輸出以及加、減、乘、除，調試程序并將不足的地方加以修改。 三、設計算法分析 1、相關函數(shù)說明： (1)定義數(shù)據(jù)結構類型為線性表的鏈式存儲結構類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項式，void Print(Polyn P) 銷毀多項式函數(shù)釋放內存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個結構體變量中coef表示每一項前的系數(shù)，expn表示每一項的指數(shù)，polyn為結點指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結構體中的數(shù)據(jù)對象名。 (2)當用戶輸入兩個一元多項式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數(shù)為m的一元多項式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結點以接收數(shù)據(jù) Insert(p,head);調用Insert函數(shù)插入結點 這就建立一元多項式的關鍵步驟 (3)由于多項式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項式按指數(shù)進行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進行處理，此處由于反復使用指針對各個結點進行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進行插入操作。(4)加、減、乘、除、的算法實現(xiàn)： 在該程序中，最關鍵的一步是實現(xiàn)四則運算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負的加法實現(xiàn)；對于乘除算法的大致流程都是：首先建立多項式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實現(xiàn)了多項式計算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結果，算法是將最后計算合并的鏈表逐個結點依次輸出，便得到整鏈表，也就是最后的計算式計算結果。由于考慮各個結點的指數(shù)情況不同，分別進行了判斷處理。 四、程序新點 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺運行時總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。 五、設計中遇到的問題及解決辦法 首先是，由于此次課程設計里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進行 4 代碼編寫。 其次是，在寫除法模塊時比較復雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設計時的一個經(jīng)驗吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結 通過本次應用C語言設計一元多項式基本計算程序，使我更加鞏固了C語言程序設計的知識，以前對指針這一點使用是比較模糊，現(xiàn)在通過此次課程設計對指針理解的比較深刻了。而且對于數(shù)據(jù)結構的相關算法和函數(shù)的調用方面知識的加深。本次的課程設計，一方面提高了自己獨立思考處理問題的能力；另一方面使自己再設計開發(fā)程序方面有了一定的小經(jīng)驗和想法，對自己以后學習其他語言程序設計奠定了一定的基礎。 八、指導老師評語及成績 附錄：（課程設計代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結點指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結點 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結點 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結點插入 } 7 } //建立一個頭指針為head、項數(shù)為m的一元多項式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結點以接收數(shù)據(jù) printf(“請輸入第%d項的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調用Insert函數(shù)插入結點 } return head;} //銷毀多項式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項數(shù)計數(shù)器 if(!q)//若多項式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項式已空，但b多項式非空 else return 1;//b多項式已空，但a多項式非空 } //求解并建立多項式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當相加系數(shù)為0時，釋放該結點 } return headc;} //求解并建立多項式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調用Insert函數(shù)以合并指數(shù)相同的項 } } return hf;} //求解并建立多項式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點,存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點，存儲余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請輸入A(x)的項數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項式B printf(“n”);printf(“**********************************************n”);printf(“* 多項式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項式A(x):“);Print(pa);*n”); printf(“多項式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結構課程設計 1.赫夫曼編碼器 設計一個利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。要求： 1)將權值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個字符和26個權值（統(tǒng)計一篇英文文章中26個字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實現(xiàn)屏幕輸出，然后實現(xiàn)文件輸出）； 5)界面優(yōu)化設計。 代碼如下： #include typedef struct HTNode //結構體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請輸入權值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對結點進行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第二篇：2012數(shù)據(jù)結構課程設計
第三篇：數(shù)據(jù)結構課程設計