數(shù)據(jù)結(jié)構(gòu)多關(guān)鍵字排序課設(shè)報(bào)告.doc

目錄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 用戶手冊(cè) 156 測(cè)試結(jié)果 197 源代碼（帶注釋 ）21八參考文獻(xiàn)26一設(shè)計(jì)題目 多關(guān)鍵字排序二需求分析 1.程序設(shè)計(jì)問題描述 多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如:在進(jìn)行高考分?jǐn)?shù)處理時(shí)，除了需對(duì)總分進(jìn)行排序外，不同的專業(yè)對(duì)單科分?jǐn)?shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序。 2.基本要求 (1)假設(shè)待排序的記錄數(shù)不超過10000，表中記錄的關(guān)鍵字?jǐn)?shù)不超過5，各個(gè)關(guān)鍵字的范圍均為0至100。按用戶給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。 (2)約定按LSD法進(jìn)行多關(guān)鍵字的排序。在對(duì)各個(gè)關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用分配和收集的方法。并綜合比較這兩種策略。 （3）測(cè)試數(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ì) 本程序是對(duì)語文，數(shù)學(xué)，英語，體育，綜合這5門成績(jī)按照此順序進(jìn)行優(yōu)先排序。各科分?jǐn)?shù)為0100。 由于本實(shí)驗(yàn)約定按LSD進(jìn)行多關(guān)鍵字的排序。在對(duì)個(gè)關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略：其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用“分配”和“收集”的方法。所以在一個(gè)程序里實(shí)現(xiàn)了這兩種排序方法。 第一種排序方法由于要使用穩(wěn)定的排序方法，故參考書上的幾種排序方法后，選用了冒泡排序和靜態(tài)鏈表存儲(chǔ)方式，每一趟排序后，找出最高分 。第二種排序方法利用“分配”與“收集”的基數(shù)排序算法，用靜態(tài)鏈表存儲(chǔ)分?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 key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;基本操作Score RandData(Score &L,int n)初始條件：L為創(chuàng)建的靜態(tài)鏈表，代表了一個(gè)學(xué)生成績(jī)的記錄，n為生成的隨機(jī)數(shù)個(gè)數(shù)。操作結(jié)果：隨機(jī)生成n個(gè)數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針。Score BubbleSort(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表操作結(jié)果：對(duì)鏈表進(jìn)行冒泡降序排序，返回指針L。void PrintScore(Score &L) 初始條件：L為創(chuàng)建的靜態(tài)鏈表。操作結(jié)果：在屏幕上顯示鏈表。 （2）“分配”與“收集”的基數(shù)排序結(jié)構(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é)生成績(jī)的記錄。操作結(jié)果：對(duì)鏈表L的第n個(gè)關(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) /對(duì)鏈表進(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&nkeynq-keyn) /交換數(shù)據(jù)域，指針域不變for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;if(q-next=NULL) /當(dāng)q指向最后一個(gè)結(jié)點(diǎn)時(shí)，將q插入到鏈表L的 尾部s-next=q;s=s-next;p-next=NULL; /p指向最后一個(gè)結(jié)點(diǎn)p=p-next;q=q-next;s-next=N-next; /將第一個(gè)結(jié)點(diǎn)插到L的尾部delete(N); /銷毀指針Nreturn L;（2） “分配”和“收集”的基數(shù)排序Score RadixSort(Score &L) /對(duì)鏈表L的第n個(gè)關(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;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取個(gè)位分配else m=p-keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立單鏈表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一個(gè)待排序元素L-next=NULL; for(j=radix-1;j=0;j-) /對(duì)每一個(gè)鏈隊(duì)從大到小進(jìn)行收集if(headj)if(L-next=NULL)L-next=headj; /L指向鏈隊(duì)頭t=tailj; /t指向隊(duì)尾elset-next=headj; /t-next指向下一個(gè)鏈隊(duì)頭t=tailj; t-next=NULL; /最后一個(gè)結(jié)點(diǎn)指向空return L; /返回L3. 函數(shù)調(diào)用關(guān)系圖void main() 調(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é)生成績(jī)記錄數(shù)并隨機(jī)產(chǎn)生成績(jī)：typedef struct node /定義結(jié)構(gòu)體 int key5; /數(shù)據(jù)域struct node *next; /指針域*Score,Lnode;Score RandData(Score &L,int n) /隨機(jī)生成n個(gè)數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針Score p,q;L=(Score)malloc(sizeof(Lnode); /創(chuàng)建帶頭結(jié)點(diǎn)的鏈表LL-next=NULL;q=L; srand(time(0); coutn;coutsetw(8)語文setw(8)數(shù)學(xué)setw(8)英語setw(8)體育setw(8)綜合endl;for(int i=1;i=n;i+)p=(Score)malloc(sizeof(Lnode);for(int j=0;jkeyj=rand()%101; /對(duì)每個(gè)關(guān)鍵字隨機(jī)產(chǎn)生0-100的數(shù)字q-next=p;q=p;p-next=NULL; /最后一個(gè)節(jié)點(diǎn)的指針指向空 q=L-next; while(q) for(int k=0;k5;k+)coutsetw(8)keyk;coutnext;return L; /返回結(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ū)Τ煽?jī)排序。endl 隨機(jī)產(chǎn)生數(shù)據(jù) endl#endl;RandData(L,n); /隨機(jī)產(chǎn)生數(shù)據(jù)coutendlendl#endl 請(qǐng)選擇： endl 1.對(duì)數(shù)據(jù)進(jìn)行冒泡法排序 endl 2.對(duì)數(shù)據(jù)進(jìn)行基數(shù)排序 endl#b; if(b=1)coutsetw(8)語文setw(8)數(shù)學(xué)setw(8)英語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選擇的操作不存在！請(qǐng)重新輸入（1或者2）next;while(p)for(int i=0;i5;i+) /依次輸出5個(gè)數(shù)據(jù)coutsetw(8)keyi;coutnext;coutnext=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&nkeynq-keyn) /交換數(shù)據(jù)域，指針域不變for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;if(q-next=NULL) /當(dāng)q指向最后一個(gè)結(jié)點(diǎn)時(shí)，將q插入到鏈表L的尾部s-next=q;s=s-next;p-next=NULL; /p指向最后一個(gè)結(jié)點(diǎn)p=p-next;q=q-next;s-next=N-next; /將第一個(gè)結(jié)點(diǎn)插到L的尾部delete(N); /銷毀指針Nreturn L;5. “分配”與“收集”的基數(shù)排序 Score RadixSort(Score &L) /對(duì)鏈表L的第n個(gè)關(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;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取個(gè)位分配else m=p-keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立單鏈表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一個(gè)待排序元素L-next=NULL; for(j=radix-1;j=0;j-) /對(duì)每一個(gè)鏈隊(duì)從大到小進(jìn)行收集if(headj)if(L-next=NULL)L-next=headj; /L指向鏈隊(duì)頭t=tailj; /t指向隊(duì)尾elset-next=headj; /t-next指向下一個(gè)鏈隊(duì)頭t=tailj; t-next=NULL; /最后一個(gè)結(jié)點(diǎn)指向空return L; /返回L6. 主函數(shù)： void main() int c;doMenu(); /調(diào)用菜單cout結(jié)束？輸入0，輸入其他繼續(xù)c;while(c!=0) ; /c等于0停止循環(huán)四調(diào)試分析： 1.代碼設(shè)計(jì)分析 看到題目“多關(guān)鍵字排序”后，首先對(duì)課本的第十章所有的算法復(fù)習(xí)了一遍并對(duì)所有的排序方法進(jìn)行了總結(jié)。內(nèi)部排序法可詳細(xì)的分為：插入排序（直接插入排序），快速排序，選擇排序（簡(jiǎn)單選擇排序），歸并排序，冒泡排序，希爾排序，堆排序，基數(shù)排序。通過對(duì)算法的分析?？蓪⑦@些排序方法分為穩(wěn)定排序和不穩(wěn)定排序。其中不穩(wěn)定排序包括快速排序和堆排序，其余都為穩(wěn)定排序方法。故基于對(duì)算法的時(shí)間空間復(fù)雜度和熟練程度，穩(wěn)定的內(nèi)部排序法，我選擇了冒泡排序法。由于待排序的記錄序列可有3種存儲(chǔ)方式：順序存儲(chǔ)，鏈表存儲(chǔ)和地址存儲(chǔ)。考慮到算法的執(zhí)行效率和當(dāng)前能力，我選擇了第二種記錄序列的存儲(chǔ)方式。故確定了排序方法和記錄的存儲(chǔ)方式后，開始設(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(headm=NULL) headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /添加此行代碼 （2）基數(shù)排序中始終只能排序一個(gè)關(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)和體會(huì) 本次課程設(shè)計(jì)我做的是多關(guān)鍵字LSD排序，在上數(shù)據(jù)結(jié)構(gòu)課時(shí)，我只是對(duì)LSD排序有了一個(gè)初步的認(rèn)識(shí)，對(duì)“分配”和“收集”的方法也沒有深究。在做這次實(shí)驗(yàn)時(shí)，我又重新翻開書本進(jìn)行了一次深入的研究，LSD(最低位優(yōu)先）法是從最次位關(guān)鍵字起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字進(jìn)行排序，依次重復(fù)，直至對(duì)最高位關(guān)鍵字進(jìn)行排序后便成為一個(gè)有序序列?！胺峙洹焙汀笆占狈椒ㄊ窃谝惶伺判蛑?，將結(jié)點(diǎn)分配到相應(yīng)的鏈隊(duì)列中去，然后再鏈接起來。編程過程中我還用到了靜態(tài)鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)。在實(shí)驗(yàn)中，我還總結(jié)了一下選擇排序與“分配”和“收集”法的優(yōu)缺點(diǎn)，在記錄較少的情況下，前者是一個(gè)不錯(cuò)的選擇，但是當(dāng)記錄非常多的時(shí)候，后者便體現(xiàn)出優(yōu)勢(shì)。從它們所需的輔助儲(chǔ)存空間來看，前者很有優(yōu)勢(shì)，而后者需要2*RADIX個(gè)計(jì)數(shù)單元?？傊ㄟ^這次課程設(shè)計(jì)，不僅編程能力，找錯(cuò)能力和耐心得到的提高，我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課的理解也更深入了一個(gè)層次。在本實(shí)驗(yàn)中主要側(cè)重的是排序的方法，考生信息很簡(jiǎn)單，主要只有分?jǐn)?shù)。要使程序更完美，還可以向結(jié)構(gòu)體中增加其它信息，如姓名、考號(hào)、性別等，使信息更完整。五用戶手冊(cè) 按照提示輸入想要排序的記錄數(shù) 比如輸入24： 此為隨機(jī)產(chǎn)生的24條學(xué)生成績(jī)的記錄，選擇輸入1或2，進(jìn)行冒泡排序或基數(shù)排序，如先選擇1輸入一個(gè)非零數(shù)字，重新開始,如下圖：輸入24輸入2輸入0 結(jié)束六測(cè)試結(jié)果（1） 冒泡排序 輸入： 輸出：（2） 基數(shù)排序 輸入： 輸出：七源代碼（帶注釋） #include#include#include#include#include#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個(gè)數(shù)據(jù)并保存到鏈表L中，返回鏈表頭指針Score p,q;L=(Score)malloc(sizeof(Lnode); /創(chuàng)建帶頭結(jié)點(diǎn)的鏈表LL-next=NULL;q=L; srand(time(0); coutn;coutsetw(8)語文setw(8)數(shù)學(xué)setw(8)英語setw(8)體育setw(8)綜合endl;for(int i=1;i=n;i+)p=(Score)malloc(sizeof(Lnode);for(int j=0;jkeyj=rand()%101; /對(duì)每個(gè)關(guān)鍵字隨機(jī)產(chǎn)生0-100的數(shù)字q-next=p;q=p;p-next=NULL; /最后一個(gè)節(jié)點(diǎn)的指針指向空 q=L-next; while(q) /將數(shù)據(jù)寫入文件new.txt，以及在屏幕輸出for(int k=0;k5;k+)coutsetw(8)keyk;coutnext;return L; /返回結(jié)構(gòu)體指針Score BubbleSort(Score &L) /對(duì)鏈表進(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&nkeynq-keyn) /交換數(shù)據(jù)域，指針域不變for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;if(q-next=NULL) /當(dāng)q指向最后一個(gè)結(jié)點(diǎn)時(shí)，將q插入到鏈表L的尾部s-next=q;s=s-next;p-next=NULL; /p指向最后一個(gè)結(jié)點(diǎn)p=p-next;q=q-next;s-next=N-next; /將第一個(gè)結(jié)點(diǎn)插到L的尾部delete(N); /銷毀指針Nreturn L;Score RadixSort(Score &L) /對(duì)鏈表L的第n個(gè)關(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;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取個(gè)位分配else m=p-keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立單鏈表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一個(gè)待排序元素L-next=NULL; for(j=r