1、目錄1 設(shè)計(jì)題目 2 2 需求分析 2 1.程序設(shè)計(jì)問題描述2 2.基本要求 2 3. 流程圖 23 詳細(xì)設(shè)計(jì) 3 1.數(shù)據(jù)結(jié)構(gòu)定義4 2.主要算法設(shè)計(jì) 5 3.函數(shù)調(diào)用關(guān)系圖84.程序主要流程 84 調(diào)試分析 135 用戶手冊 156 測試結(jié)果 197 源代碼（帶注釋 ）21八參考文獻(xiàn)26一設(shè)計(jì)題目 多關(guān)鍵字排序二需求分析 1.程序設(shè)計(jì)問題描述 多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如:在進(jìn)行高考分?jǐn)?shù)處理時(shí)，除了需對總分進(jìn)行排序外，不同的專業(yè)對單科分?jǐn)?shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序。 2.基本要求 (1)假設(shè)待排序的記錄數(shù)不超過1000

2、0，表中記錄的關(guān)鍵字?jǐn)?shù)不超過5，各個關(guān)鍵字的范圍均為0至100。按用戶給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。 (2)約定按LSD法進(jìn)行多關(guān)鍵字的排序。在對各個關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用"分配"和"收集"的方法。并綜合比較這兩種策略。 （3）測試數(shù)據(jù)由隨機(jī)數(shù)生成器產(chǎn)生。開始 3.流程圖 輸出菜單 輸入記錄數(shù)選擇排序方法輸入不是1或2，重新輸入選擇排序方法判斷2 1基數(shù)排序內(nèi)部排序顯示排序結(jié)果輸入結(jié)束或繼續(xù)執(zhí)行判斷輸入非零值0繼續(xù)執(zhí)行退出結(jié)束三詳細(xì)設(shè)計(jì) 本程序是對語文，數(shù)學(xué)，英語，體育，綜合這5門成績按照此

3、順序進(jìn)行優(yōu)先排序。各科分?jǐn)?shù)為0100。 由于本實(shí)驗(yàn)約定按LSD進(jìn)行多關(guān)鍵字的排序。在對個關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略：其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用“分配”和“收集”的方法。所以在一個程序里實(shí)現(xiàn)了這兩種排序方法。 第一種排序方法由于要使用穩(wěn)定的排序方法，故參考書上的幾種排序方法后，選用了冒泡排序和靜態(tài)鏈表存儲方式，每一趟排序后，找出最高分 。第二種排序方法利用“分配”與“收集”的基數(shù)排序算法，用靜態(tài)鏈表存儲分?jǐn)?shù)，在一趟排序中，將結(jié)點(diǎn)分配到相應(yīng)的鏈隊(duì)列中去，再按從高到低鏈接起來。 1.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（1）穩(wěn)定的內(nèi)部排序法結(jié)構(gòu)體定義typedef struct node /定義結(jié)構(gòu)體 int

4、 key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;基本操作Score RandData(Score &L,int n)初始條件：L為創(chuàng)建的靜態(tài)鏈表，代表了一個學(xué)生成績的記錄，n為生成的隨機(jī)數(shù)個數(shù)。操作結(jié)果：隨機(jī)生成n個數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針。Score BubbleSort(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表操作結(jié)果：對鏈表進(jìn)行冒泡降序排序，返回指針L。void PrintScore(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表。操作結(jié)果：在屏幕上顯示鏈表。 （2）“分配”與“收集”的基數(shù)排序結(jié)

5、構(gòu)體定義typedef struct node /定義結(jié)構(gòu)體 int key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;基本操作Score RadixSort(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表，代表了一條學(xué)生成績的記錄。操作結(jié)果：對鏈表L的第n個關(guān)鍵字進(jìn)行基數(shù)排序。void PrintScore(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表。操作結(jié)果：在屏幕上顯示鏈表。2. 主要算法設(shè)計(jì)（1）穩(wěn)定的內(nèi)部排序Score BubbleSort(Score &L) /對鏈表進(jìn)行冒泡降序排序，返回指針LScore p

6、,q,s,t,N;int n;t=(Score)malloc(sizeof(node);N=(Score)malloc(sizeof(node);N->next=L->next; /把N指向鏈表LL->next=NULL; /L重新指向空s=L; /創(chuàng)建新的鏈表Lwhile(N->next->next)p=N->next;q=p->next;while(q)n=0;while(p->keyn=q->keyn&&n<5) /當(dāng)前關(guān)鍵字相等則比較下一關(guān)鍵字n+;if(p->keyn>q->keyn) /交

7、換數(shù)據(jù)域，指針域不變for(int i=0;i<5;i+) t->keyi=q->keyi;q->keyi=p->keyi;p->keyi=t->keyi;if(q->next=NULL) /當(dāng)q指向最后一個結(jié)點(diǎn)時(shí)，將q插入到鏈表L的 尾部s->next=q;s=s->next;p->next=NULL; /p指向最后一個結(jié)點(diǎn)p=p->next;q=q->next;s->next=N->next; /將第一個結(jié)點(diǎn)插到L的尾部delete(N); /銷毀指針Nreturn L;（2） “分配”和“收集”的基

8、數(shù)排序Score RadixSort(Score &L) /對鏈表L的第n個關(guān)鍵字進(jìn)行基數(shù)排序Score headradix,tailradix,p,t;int d,i,j,m;for(int n=4;n>=0;n-) for(d=1;d<=2;d+)for(i=0;i<radix;i+) /初始化各鏈隊(duì)首尾指針headi=taili=NULL;p=L->next;while(p)if(d=1) m=p->keyn%10; /第一趟取個位分配else m=p->keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立單鏈表head

9、m=p; tailm=p;elsetailm->next=p;tailm=p;p=p->next; /取下一個待排序元素L->next=NULL; for(j=radix-1;j>=0;j-) /對每一個鏈隊(duì)從大到小進(jìn)行收集if(headj)if(L->next=NULL)L->next=headj; /L指向鏈隊(duì)頭t=tailj; /t指向隊(duì)尾elset->next=headj; /t->next指向下一個鏈隊(duì)頭t=tailj; t->next=NULL; /最后一個結(jié)點(diǎn)指向空return L; /返回L3. 函數(shù)調(diào)用關(guān)系圖void ma

10、in() 調(diào)用RadixSort(L) PrintScore(L)BubbleSort(L)PrintScore(L)RandData(L,n)Menu()If（b=2）調(diào)用If（b=1）調(diào)用調(diào)用4. 程序主要流程 1.隨機(jī)產(chǎn)生數(shù)據(jù)：輸入想要排序的學(xué)生成績記錄數(shù)并隨機(jī)產(chǎn)生成績：typedef struct node /定義結(jié)構(gòu)體 int key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;Score RandData(Score &L,int n) /隨機(jī)生成n個數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針Score p,q;L=(Score)mallo

11、c(sizeof(Lnode); /創(chuàng)建帶頭結(jié)點(diǎn)的鏈表LL->next=NULL;q=L; srand(time(0); cout<<"輸入你所需的數(shù)據(jù)個數(shù)："cin>>n;cout<<setw(8)<<"語文"<<setw(8)<<"數(shù)學(xué)"<<setw(8)<<"英語"<<setw(8)<<"體育"<<setw(8)<<"綜合"

12、;<<endl;for(int i=1;i<=n;i+)p=(Score)malloc(sizeof(Lnode);for(int j=0;j<5;j+)p->keyj=rand()%101; /對每個關(guān)鍵字隨機(jī)產(chǎn)生0-100的數(shù)字q->next=p;q=p;p->next=NULL; /最后一個節(jié)點(diǎn)的指針指向空 q=L->next; while(q) for(int k=0;k<5;k+)cout<<setw(8)<<q->keyk;cout<<endl;q=q->next;return L

13、; /返回結(jié)構(gòu)體指針2. 菜單顯示實(shí)現(xiàn)： void Menu() /菜單int a,b,n; Score L;double time;cout<<"#"<<endl<<" 本程序可以按關(guān)鍵字的優(yōu)先關(guān)系排序?qū)Τ煽兣判颉?quot;<<endl<<" 隨機(jī)產(chǎn)生數(shù)據(jù) "<<endl<<"#"<<endl;RandData(L,n); /隨機(jī)產(chǎn)生數(shù)據(jù)cout<<endl<<endl<<"#&q

14、uot;<<endl <<" 請選擇： "<<endl<<" 1.對數(shù)據(jù)進(jìn)行冒泡法排序 "<<endl<<" 2.對數(shù)據(jù)進(jìn)行基數(shù)排序 "<<endl<<"#"<<endl;docin>>b; if(b=1)cout<<setw(8)<<"語文"<<setw(8)<<"數(shù)學(xué)"<<setw(8)<

15、<"英語"<<setw(8)<<"體育"<<setw(8)<<"綜合"<<endl; BubbleSort(L); /調(diào)用冒泡排序 PrintScore(L); /打印結(jié)果 else if(b=2) RadixSort(L); /調(diào)用基數(shù)排序 PrintScore(L);/ else cout<<"選擇的操作不存在！請重新輸入（1或者2）"<<endl;while(b!=1&&b!=2); 3. 屏幕上顯示鏈表

16、 void PrintScore(Score &L) /在屏幕上顯示鏈表Score p;p=L->next;while(p)for(int i=0;i<5;i+) /依次輸出5個數(shù)據(jù)cout<<setw(8)<<p->keyi;cout<<endl;p=p->next;cout<<endl;4. 內(nèi)部穩(wěn)定排序算法 Score BubbleSort(Score &L) /對鏈表進(jìn)行冒泡降序排序，返回指針LScore p,q,s,t,N;int n;t=(Score)malloc(sizeof(node);N=

17、(Score)malloc(sizeof(node);N->next=L->next; /把N指向鏈表LL->next=NULL; /L重新指向空s=L; /創(chuàng)建新的鏈表Lwhile(N->next->next)p=N->next;q=p->next;while(q)n=0;while(p->keyn=q->keyn&&n<5) /當(dāng)前關(guān)鍵字相等則比較下一關(guān)鍵字n+;if(p->keyn>q->keyn) /交換數(shù)據(jù)域，指針域不變for(int i=0;i<5;i+) t->keyi=q-

18、>keyi;q->keyi=p->keyi;p->keyi=t->keyi;if(q->next=NULL) /當(dāng)q指向最后一個結(jié)點(diǎn)時(shí)，將q插入到鏈表L的尾部s->next=q;s=s->next;p->next=NULL; /p指向最后一個結(jié)點(diǎn)p=p->next;q=q->next;s->next=N->next; /將第一個結(jié)點(diǎn)插到L的尾部delete(N); /銷毀指針Nreturn L;5. “分配”與“收集”的基數(shù)排序 Score RadixSort(Score &L) /對鏈表L的第n個關(guān)鍵字進(jìn)行

19、基數(shù)排序Score headradix,tailradix,p,t;int d,i,j,m;for(int n=4;n>=0;n-) for(d=1;d<=2;d+)for(i=0;i<radix;i+) /初始化各鏈隊(duì)首尾指針headi=taili=NULL;p=L->next;while(p)if(d=1) m=p->keyn%10; /第一趟取個位分配else m=p->keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立單鏈表headm=p; tailm=p;elsetailm->next=p;tailm=p;p=p-&

20、gt;next; /取下一個待排序元素L->next=NULL; for(j=radix-1;j>=0;j-) /對每一個鏈隊(duì)從大到小進(jìn)行收集if(headj)if(L->next=NULL)L->next=headj; /L指向鏈隊(duì)頭t=tailj; /t指向隊(duì)尾elset->next=headj; /t->next指向下一個鏈隊(duì)頭t=tailj; t->next=NULL; /最后一個結(jié)點(diǎn)指向空return L; /返回L6. 主函數(shù)： void main() int c;doMenu(); /調(diào)用菜單cout<<"結(jié)束？輸入

21、0，輸入其他繼續(xù)"<<endl;cin>>c;while(c!=0) ; /c等于0停止循環(huán)四調(diào)試分析： 1.代碼設(shè)計(jì)分析 看到題目“多關(guān)鍵字排序”后，首先對課本的第十章所有的算法復(fù)習(xí)了一遍并對所有的排序方法進(jìn)行了總結(jié)。內(nèi)部排序法可詳細(xì)的分為：插入排序（直接插入排序），快速排序，選擇排序（簡單選擇排序），歸并排序，冒泡排序，希爾排序，堆排序，基數(shù)排序。通過對算法的分析。可將這些排序方法分為穩(wěn)定排序和不穩(wěn)定排序。其中不穩(wěn)定排序包括快速排序和堆排序，其余都為穩(wěn)定排序方法。故基于對算法的時(shí)間空間復(fù)雜度和熟練程度，穩(wěn)定的內(nèi)部排序法，我選擇了冒泡排序法。由于待排序的記錄

22、序列可有3種存儲方式：順序存儲，鏈表存儲和地址存儲。考慮到算法的執(zhí)行效率和當(dāng)前能力，我選擇了第二種記錄序列的存儲方式。故確定了排序方法和記錄的存儲方式后，開始設(shè)計(jì)代碼。程序的重要設(shè)計(jì)模塊為：結(jié)構(gòu)體定義，算法設(shè)計(jì)，界面設(shè)計(jì)和主函數(shù)的定義。 2.調(diào)試過程中的問題 （1）在基數(shù)排序中，輸入2后一直無顯示，如下圖所示：經(jīng)調(diào)試檢查后發(fā)現(xiàn)是因?yàn)榕判蛲暌粭l記錄后，沒有將指針指向下一條記錄。所以在while（）循環(huán)結(jié)束處添加一條指向下一條記錄第指針p=p->next; 如下代碼所示：while(p)if(d=1) m=p->keyn%10; else m=p->keyn/10; if(hea

23、dm=NULL) headm=p; tailm=p;elsetailm->next=p;tailm=p;p=p->next; /添加此行代碼 （2）基數(shù)排序中始終只能排序一個關(guān)鍵字。不能實(shí)現(xiàn)在主關(guān)鍵字相等的情況下此次鍵字按照從高分到低分的排序。如下情況所示： 經(jīng)調(diào)試后，在每趟分配和收集前添加代碼for(int n=4;n>=0;n-)，即可進(jìn)行多關(guān)鍵字排序。成功運(yùn)行后如下：3. 經(jīng)驗(yàn)和體會 本次課程設(shè)計(jì)我做的是多關(guān)鍵字LSD排序，在上數(shù)據(jù)結(jié)構(gòu)課時(shí)，我只是對LSD排序有了一個初步的認(rèn)識，對“分配”和“收集”的方法也沒有深究。在做這次實(shí)驗(yàn)時(shí)，我又重新翻開書本進(jìn)行了一次深入的研究，

24、LSD(最低位優(yōu)先）法是從最次位關(guān)鍵字起進(jìn)行排序，然后再對高一位的關(guān)鍵字進(jìn)行排序，依次重復(fù)，直至對最高位關(guān)鍵字進(jìn)行排序后便成為一個有序序列。“分配”和“收集”方法是在一趟排序中，將結(jié)點(diǎn)分配到相應(yīng)的鏈隊(duì)列中去，然后再鏈接起來。編程過程中我還用到了靜態(tài)鏈表這個數(shù)據(jù)結(jié)構(gòu)。在實(shí)驗(yàn)中，我還總結(jié)了一下選擇排序與“分配”和“收集”法的優(yōu)缺點(diǎn)，在記錄較少的情況下，前者是一個不錯的選擇，但是當(dāng)記錄非常多的時(shí)候，后者便體現(xiàn)出優(yōu)勢。從它們所需的輔助儲存空間來看，前者很有優(yōu)勢，而后者需要2*RADIX個計(jì)數(shù)單元。總之，通過這次課程設(shè)計(jì)，不僅編程能力，找錯能力和耐心得到的提高，我對數(shù)據(jù)結(jié)構(gòu)這門課的理解也更深入了一個層次

25、。在本實(shí)驗(yàn)中主要側(cè)重的是排序的方法，考生信息很簡單，主要只有分?jǐn)?shù)。要使程序更完美，還可以向結(jié)構(gòu)體中增加其它信息，如姓名、考號、性別等，使信息更完整。五用戶手冊 按照提示輸入想要排序的記錄數(shù) 比如輸入24： 此為隨機(jī)產(chǎn)生的24條學(xué)生成績的記錄，選擇輸入1或2，進(jìn)行冒泡排序或基數(shù)排序，如先選擇1輸入一個非零數(shù)字，重新開始,如下圖：輸入24輸入2輸入0 結(jié)束六測試結(jié)果（1） 冒泡排序 輸入： 輸出：（2） 基數(shù)排序 輸入： 輸出：七源代碼（帶注釋） #include<iostream>#include<cstdlib>#include<iomanip>#inclu

26、de<ctime>#include<fstream>#define radix 11 /基數(shù)using namespace std;typedef struct node /定義結(jié)構(gòu)體 int key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;Score RandData(Score &L,int n) /隨機(jī)生成n個數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針Score p,q;L=(Score)malloc(sizeof(Lnode); /創(chuàng)建帶頭結(jié)點(diǎn)的鏈表LL->next=NULL;q=L; srand(time(0

27、); cout<<"輸入你所需的數(shù)據(jù)個數(shù)："cin>>n;cout<<setw(8)<<"語文"<<setw(8)<<"數(shù)學(xué)"<<setw(8)<<"英語"<<setw(8)<<"體育"<<setw(8)<<"綜合"<<endl;for(int i=1;i<=n;i+)p=(Score)malloc(sizeof(L

28、node);for(int j=0;j<5;j+)p->keyj=rand()%101; /對每個關(guān)鍵字隨機(jī)產(chǎn)生0-100的數(shù)字q->next=p;q=p;p->next=NULL; /最后一個節(jié)點(diǎn)的指針指向空 q=L->next; while(q) /將數(shù)據(jù)寫入文件new.txt，以及在屏幕輸出for(int k=0;k<5;k+)cout<<setw(8)<<q->keyk;cout<<endl;q=q->next;return L; /返回結(jié)構(gòu)體指針Score BubbleSort(Score &

29、L) /對鏈表進(jìn)行冒泡降序排序，返回指針LScore p,q,s,t,N;int n;t=(Score)malloc(sizeof(node);N=(Score)malloc(sizeof(node);N->next=L->next; /把N指向鏈表LL->next=NULL; /L重新指向空s=L; /創(chuàng)建新的鏈表Lwhile(N->next->next)p=N->next;q=p->next;while(q)n=0;while(p->keyn=q->keyn&&n<5) /當(dāng)前關(guān)鍵字相等則比較下一關(guān)鍵字n+;if(

30、p->keyn>q->keyn) /交換數(shù)據(jù)域，指針域不變for(int i=0;i<5;i+) t->keyi=q->keyi;q->keyi=p->keyi;p->keyi=t->keyi;if(q->next=NULL) /當(dāng)q指向最后一個結(jié)點(diǎn)時(shí)，將q插入到鏈表L的尾部s->next=q;s=s->next;p->next=NULL; /p指向最后一個結(jié)點(diǎn)p=p->next;q=q->next;s->next=N->next; /將第一個結(jié)點(diǎn)插到L的尾部delete(N); /銷毀

31、指針Nreturn L;Score RadixSort(Score &L) /對鏈表L的第n個關(guān)鍵字進(jìn)行基數(shù)排序Score headradix,tailradix,p,t;int d,i,j,m; for(int n=4;n>=0;n-) for(d=1;d<=2;d+)for(i=0;i<radix;i+) /初始化各鏈隊(duì)首尾指針headi=taili=NULL;p=L->next;while(p)if(d=1) m=p->keyn%10; /第一趟取個位分配else m=p->keyn/10; /第二趟分配if(headm=NULL) /采用尾插

32、法建立單鏈表headm=p; tailm=p;elsetailm->next=p;tailm=p;p=p->next; /取下一個待排序元素L->next=NULL; for(j=radix-1;j>=0;j-) /對每一個鏈隊(duì)從大到小進(jìn)行收集if(headj)if(L->next=NULL)L->next=headj; /L指向鏈隊(duì)頭t=tailj; /t指向隊(duì)尾elset->next=headj; /t->next指向下一個鏈隊(duì)頭t=tailj; t->next=NULL; /最后一個結(jié)點(diǎn)指向空return L; /返回Lvoid PrintScore(Score &L) /在屏幕上顯示鏈表Score p;p=L->next;while(p)for(int i=0;i<5;i+) /依次輸出5個數(shù)據(jù)cout<<setw(8)<<p->keyi