數(shù)據(jù)結(jié)構(gòu)課程設(shè)計多關(guān)鍵字實驗報告

1、淮 海 工 學(xué) 院 計算機工程學(xué)院課程設(shè)計報告設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 選題名稱： 多關(guān)鍵字排 姓 名： 學(xué) 號： 專業(yè)班級： 系 （院）： 計算機工程學(xué)院 設(shè)計時間： 2013.12.232013.1.5 設(shè)計地點： 軟件工程實驗室、教室 成績：指導(dǎo)教師評語： 簽名： 年 月 日1課程設(shè)計目的1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。 2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3.提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，鞏固、

2、深化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。2課程設(shè)計任務(wù)與要求：任務(wù)多關(guān)鍵字的排序是根據(jù)多個不同的要求來進行的，在某些方面，有其一定的實用范圍。例如:在對高考學(xué)生的成績進行分析和處理的時候，各個學(xué)校錄取學(xué)生除了需要考慮總分的情況，不同的專業(yè)對單科的分?jǐn)?shù)的要求也有所不同。因此在總分相同的情況下，還需要根據(jù)學(xué)校定的單科分?jǐn)?shù)的高低來考慮考生錄取的優(yōu)先次序?？傮w要求：1、在處理每個題目時，要求從分析題目的需求入手，按設(shè)計抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計實現(xiàn)抽象數(shù)據(jù)類型、編制上機程序和上機調(diào)試等若干步驟完成題目，最終寫出完整的分析報告。前期準(zhǔn)備工作完備與否直接

3、影響到后序上機調(diào)試工作的效率。在程序設(shè)計階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 2、.設(shè)計的題目要求達到一定工作量（300行以上代碼），并具有一定的深度和難度。3、程序設(shè)計語言推薦使用c/c+，程序書寫規(guī)范，源程序需加必要的注釋;4、每位同學(xué)需提交可獨立運行的程序；5 、每位同學(xué)需獨立提交設(shè)計報告書（每人一份），要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實，不少于10頁（代碼不算）；6、 課程設(shè)計實踐作為培養(yǎng)學(xué)生動手能力的一種手段，單獨考核。題目要求： (1) 假設(shè)待排序的記錄數(shù)不超過10000，表中記錄的關(guān)鍵字?jǐn)?shù)不超過5，各個關(guān)鍵字的范圍均為0至100。按用戶給定的進行排序的關(guān)鍵字的優(yōu)先關(guān)系，

4、輸出排序結(jié)果。 (2) 約定按lsd法進行多關(guān)鍵字的排序。在對各個關(guān)鍵字進行排序時采用兩種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用分配和收集的方法。并綜合比較這兩種策略。 3課程設(shè)計說明書一 需求分析在進行高考分?jǐn)?shù)的處理時，除了需對總分進行排序外，不同的專業(yè)對單科的分?jǐn)?shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序。針對這一問題，設(shè)計一個用c語言描述的高考成績排名系統(tǒng)。按學(xué)科關(guān)鍵字高考總分進行排序的情況下，各科程序排序。本程序規(guī)定如下：1. 創(chuàng)建高考成績表包含語文、數(shù)學(xué)、英語、綜合四門成績，以及考號姓名等考生信息存放到名為高考成績.txt文本中。2

5、. 對考生成績可以實現(xiàn)查找、顯示等功能。3. 可以輸入成績進行排序也可以從文件中讀取數(shù)據(jù)進行排序。4. 對學(xué)生的成績排序，在總分不同的時候按照各自的排序，在總分相同的情況下。5. 對單科成績進行排序時分別用穩(wěn)定的冒泡排序和“分配”和“收集”的方法進行排序。二 概要設(shè)計1.規(guī)定成績個數(shù)、成績記錄的最大記錄數(shù)、和存儲每個成績的數(shù)組隊列#define max_num_of_key 5#define radix 101#define max_space 10002.定義結(jié)構(gòu)體存儲考生成績信息struct slcellint keysmax_num_of_key;char name20;int numb

6、er; int next; ;3.定義靜態(tài)鏈表struct sllistslcell rmax_space;int keynum;int recnum;adt sllist數(shù)據(jù)對象：d：d=a|a屬于sllist數(shù)據(jù)關(guān)系：r：數(shù)據(jù)元素同屬一個集合?；静僮鳎簆：sllist * creat()操作結(jié)果：用sllist存儲輸入的考生的信息，但是不存入文件中。void read(sllist *l) 操作結(jié)果：從文件中讀取考生的各科成績進行操作。void search(sllist *l) 操作結(jié)果：可以按考號或姓名查找考生的各科成績。void distribute(recordtypel *r,

7、int i,int *f,int *e)初始條件：存在以i為下標(biāo)的關(guān)鍵字。操作結(jié)果：以下標(biāo)為i的關(guān)鍵字為準(zhǔn)做一趟分配。void collect(recordtypel *r,int i,int *f,int *e)初始條件：存在以i為下標(biāo)的關(guān)鍵字。操作結(jié)果：以下標(biāo)為i的關(guān)鍵字為準(zhǔn)做一趟收集。void radixsortmaths(sllist *l)操作結(jié)果：對*l中的成績做鏈?zhǔn)交鶖?shù)排序，以數(shù)學(xué)成績?yōu)殛P(guān)鍵字排序。void radixsortchinese(sllist *l)操作結(jié)果：對*l中的成績做鏈?zhǔn)交鶖?shù)排序，以語文成績?yōu)殛P(guān)鍵字排序。void radixsortenglish(sllist

8、 *l)操作結(jié)果：對*l中的成績做鏈?zhǔn)交鶖?shù)排序，以英語成績?yōu)殛P(guān)鍵字排序。void radixsortzonghe(sllist *l)操作結(jié)果：對*l中的成績做鏈?zhǔn)交鶖?shù)排序，以理綜成績?yōu)殛P(guān)鍵字排序。void radixsort(sllist *l) 操作結(jié)果：按用戶選擇的關(guān)鍵字排序并輸出排序結(jié)果void radixsorttotal(sllist *l)操作結(jié)果：對總分排序void showrank(sllist *l)操作結(jié)果：按名次順序輸出考生名次 考號 姓名 總分 數(shù)學(xué) 英語 語文 理綜分?jǐn)?shù)adt sllist系統(tǒng)流程圖如下：多關(guān)鍵字排序系統(tǒng) 查詢 取得考生信息的方式 各種排序手動輸入從

9、文件讀取按姓名查詢按考號查詢總分相同按語文成績排序總分相同按英語成績排序總分相同按數(shù)學(xué)成績排序總分相同按綜合成績排序考號姓名各科成績?nèi)?詳細設(shè)計1.存儲文件的書寫void read(sllist *l)2.考生信息輸入sllist * creat() 3.查找函數(shù)void search(sllist *l)4.鏈?zhǔn)交鶖?shù)排序void distribute(slcell *r,int i,int *f,int *e)/*以下標(biāo)為i的關(guān)鍵字為準(zhǔn)做一趟分配*/int j,p;for(j=radix-1;j=0;-j)/將radix個隊列初始化為空隊列fj=0;for(p=r0.next;p;p=rp.

10、next)j=rp.keysi;if(!fj)/將下標(biāo)p所指的節(jié)點插入第j個隊列中fj=p;elserej.next=p;ej=p;void collect(slcell *r,int i,int *f,int *e)/*收集*/int j,t;for(j=radix-1;!fj;j-);/找第一個非空隊列r0.next=fj;t=ej;while(j=0)for(j-;j0&!fj;j-);/找下一個非空隊列if(fj&j=0)rt.next=fj;t=ej;/鏈接兩個非空隊列rt.next=0;/t指向最后一個非空隊列中的最后節(jié)點/*對*l中的成績做鏈?zhǔn)交鶖?shù)排序,鏈表的記錄按從小到大的順序

11、連接*/void radixsortchinese(sllist *l)/語文int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=3;i0;-i)distribute(l-r,i,f,e);collect(l-r,i,f,e);void radixsortmaths(sllist *l)/數(shù)學(xué)int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l

12、-r,i,f,e);void radixsortenglish(sllist *l)/英語int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l-r,i,f,e);void radixsortzonghe(sllist *l)/綜合int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l-r,i,f,e);v

13、oid radixsorttotal(sllist *l)/對總分排序slcell *r;r=l-r;int f401,e401;int j,p,t;for(j=400;j=0;-j) fj=0;for(p=r0.next;p;p=rp.next)j=rp.keys0;if(!fj) fj=p;elserej.next=p;ej=p;for(j=400;!fj;j-);r0.next=fj;t=ej;while(j=0)for(j-;j0&!fj;j-);if(fj&j=0)rt.next=fj;t=ej;rt.next=0;void showrank(sllist *l)/按名次順序輸出考生

14、名次 學(xué)號 姓名 總分 語文 數(shù)學(xué) 英語 綜合分?jǐn)?shù)int rank=1,i;cout 名次 考號 名字 總分 語文 數(shù)學(xué) 英語 綜合r0.next;rankrecnum;rank+)cousetw(2)rank;coutsetw(10)ri.numbersetw(10);coutsetw(10)ri.keys0;cout setw(10)ri.keys1setw(10)ri.keys2;cout setw(10)ri.keys3setw(10)ri.keys4ri.next;四 設(shè)計與調(diào)試分析剛開始的時候我設(shè)計了文件的插入、刪除、修改、查詢等功能，后來我用了靜態(tài)鏈表存儲，同時在文

15、件讀取的時候我設(shè)置了每次讀取的最大值為10所以在插入、刪除之后就出現(xiàn)了亂碼的情況，所以我就放棄了插入、刪除的功能，只寫了查詢的功能。在寫查詢的時候我本來想用兩個子函數(shù)和一個查找主函數(shù)的，可是后來在主函數(shù)中用switch語句調(diào)用兩個子函數(shù)出錯。后來我把函數(shù)寫在switch語句中就對了。在選擇功能界面和排序界面時也出錯了，一開始我用的是switch語句套在switch語句中，總是出現(xiàn)錯誤，而且檢查不出來。后來我把套在里面的switch語句寫在另外一個函數(shù)里，然后再調(diào)用這樣就沒有錯誤了。寫文件的時候把值直接賦給指針了，所以導(dǎo)致我一直出錯，后來進過看書弄懂了。鏈?zhǔn)交鶖?shù)排序的程序是按照書上的寫的，所以沒

16、什么大問題。五 用戶手冊1 主界面：1手動輸入考生成績進行排序2顯示文件中已經(jīng)存儲的考生成績信息3各種查詢考生成績信息4各種排序5輸出排序后的考生成績信息6.退出2 選擇1，進入手動輸入考生成績信息界面：依次分別輸入考生考號、姓名、語文、數(shù)學(xué)、英語、綜合，輸入完成按回車鍵。若想繼續(xù)輸入按1，不再輸入按0。2 選擇2，進入顯示考生信息界面（從文件中讀取考生成績信息）3 選擇3，進入查詢界面：1按考號查找2按姓名查找4 選擇4，進入排序界面：1總分相同時按語文成績排序2總分相同時按英語成績排序3總分相同時按數(shù)學(xué)成績排序4總分相同時按綜合成績排序。5 選擇5，輸出排好順序的考生成績信息，按總分排序。

17、六 測試成果1. 手動輸入考生信息測試結(jié)果2. 從文件中讀取考生信息進行排序七 附錄（源程序清單）#include#include#include#include#include #define max_num_of_key 5 /關(guān)鍵字最多為5#define radix 101#define max_space 1000 /待排序的數(shù)最大為1000struct slcellint keysmax_num_of_key;/子關(guān)鍵字?jǐn)?shù)組 char name20;int number; int next;/*定義一個靜態(tài)鏈表*/struct sllistslcell rmax_space;int

18、keynum;int recnum; ;sllist * creat() /手動輸入考生的高考成績信息sllist *l;int i=1,flag=1;l=new sllist;l-keynum=5;l-recnum=0;while(flag) /判斷是否繼續(xù)輸入cout請輸入考生考號、姓名、語文、數(shù)學(xué)、英語、綜合l-ri.number; ; cinl-ri.keys1; cinl-ri.keys2; cinl-ri.keys3; cinl-ri.keys4; l-ri.keys0=(l-ri.keys1+l-ri.keys2+l-ri.keys3+l-ri.keys4

19、);/成績總和 (l-recnum)+;cout繼續(xù)輸入考生成績則輸入1，否則輸入0flag;i+;return l;void read(sllist *l)/讀入文件int num=10;/定義從文件中讀取數(shù)據(jù)的最大值，可更改l-keynum=5;l-recnum=0; cout 考號 姓名 語文 數(shù)學(xué) 英語 綜合endl;ifstream infile (高考成績.txt,ios:in); /判斷文件是否能夠打開if ( ! infile )cout 打開文件失敗endl; for (int i=1;il-ri.number;coutsetw(2)ri.number; infile l-r

20、;coutsetw(10);infile l-ri.keys1;coutsetw(10)ri.keys1;infile l-ri.keys2;coutsetw(10)ri.keys2; infile l-ri.keys3;coutsetw(10)ri.keys3;infile l-ri.keys4;coutsetw(10)ri.keys4ri.keys0=(l-ri.keys1+l-ri.keys2+l-ri.keys3+l-ri.keys4); (l-recnum)+; infile.close();/*查找函數(shù)*/void search(sllist *l)cha

21、r name20;int number; int i;int j;cout按考號查找輸入0，按姓名查找輸入1j;switch (j) case 0:coutnumber;for (i=1;iri.number=number) /判斷輸入的學(xué)號是否正確 cout 考號 名字 語文 數(shù)學(xué) 英語 綜合endl; cout setw(2)ri.numbersetw(10); cout setw(10)ri.keys1setw(10)ri.keys2; cout setw(10)ri.keys3setw(10)ri.keys4endl; break; case 1: coutname;fo

22、r (i=1;,name)=0) cout 考號 姓名 語文 數(shù)學(xué) 英語 綜合endl; cout setw(2)ri.numbersetw(10); cout setw(10)ri.keys1setw(10)ri.keys2; cout setw(10)ri.keys3setw(10)ri.keys4=0;-j)/將radix個隊列初始化為空隊列fj=0;for(p=r0.next;p;p=rp.next)j=rp.keysi;if(!fj)/將下標(biāo)p所指的節(jié)點插入第j個隊列中fj=p;elserej.next=p;ej=p;void collect(slcel

23、l *r,int i,int *f,int *e)/*收集*/int j,t;for(j=radix-1;!fj;j-);/找第一個非空隊列r0.next=fj;t=ej;while(j=0)for(j-;j0&!fj;j-);/找下一個非空隊列if(fj&j=0)rt.next=fj;t=ej;/鏈接兩個非空隊列rt.next=0;/t指向最后一個非空隊列中的最后節(jié)點/*對*l中的成績做鏈?zhǔn)交鶖?shù)排序,鏈表的記錄按從小到大的順序連接*/void radixsortchinese(sllist *l)/語文int f101,e101;int i;for(i=0;irecnum;i+) l-ri.

24、next=i+1;l-rl-recnum.next=0;for(i=3;i0;-i)distribute(l-r,i,f,e);collect(l-r,i,f,e);void radixsortmaths(sllist *l)/數(shù)學(xué)int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l-r,i,f,e);void radixsortenglish(sllist *l)/英語int f101,e101;int i;for(i=0;irecnum;i+)

25、 l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l-r,i,f,e);void radixsortzonghe(sllist *l)/綜合int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);collect(l-r,i,f,e);void radixsorttotal(sllist *l)/對總分排序slcell *r;r=l-r;int f401,e401;int j,p,t;for(j=400

26、;j=0;-j) fj=0;for(p=r0.next;p;p=rp.next)j=rp.keys0;if(!fj) fj=p;elserej.next=p;ej=p;for(j=400;!fj;j-);r0.next=fj;t=ej;while(j=0)for(j-;j0&!fj;j-);if(fj&j=0)rt.next=fj;t=ej;rt.next=0;void showrank(sllist *l)/按名次順序輸出考生名次 學(xué)號 姓名 總分 語文 數(shù)學(xué) 英語 綜合分?jǐn)?shù)int rank=1,i;cout 名次 考號 名字 總分 語文 數(shù)學(xué) 英語 綜合r0.next;rankrecnum

27、;rank+)cout setw(2)rank;cout setw(10)ri.numbersetw(10);cout setw(10)ri.keys0;cout setw(10)ri.keys1setw(10)ri.keys2;cout setw(10)ri.keys3setw(10)ri.keys4ri.next;void radixsort(sllist *l) int x,k=1;while(k!=0) cout*endl; cout* 你可以選擇以下幾種操作： *endl; cout* 1.總分相同時按語文成績排序 *endl; cout* 2.總分相同時按英語成績排序

28、 *endl; cout* 3.總分相同時按數(shù)學(xué)成績排序 *endl; cout* 4.總分相同時按綜合成績排序 *endl; cout* 5.退出 *endl; cout*endl; coutx; switch(x) case 1: radixsortchinese(l); radixsorttotal(l); cout考生成績已按您的選擇排序成功endl; showrank(l); break; case 2: radixsortmaths(l); radixsorttotal(l); cout考生成績已按您的選擇排序成功endl; showrank(l); break; case 3:

29、radixsortenglish(l); radixsorttotal(l); cout考生成績已按您的選擇排序成功endl; showrank(l); break; case 4: radixsortzonghe(l); radixsorttotal(l); cout考生成績已按您的選擇排序成功endl; showrank(l); break; case 5: return ; break; system(pause); system(cls); int main()int x,flag=1;sllist * l=new sllist;while(flag!=0) cout*歡迎使用多關(guān)鍵字

30、排序系統(tǒng)*n; cout*-手動輸入考生成績信息進行排序請選-1*n; cout*-顯示考生成績信息請選擇-2*n; cout*-各種查詢考生成績信息請選擇-3*n; cout*-各種排序請選擇-4*n; cout*-輸出排序后的考生高考信息請選擇-5*n; cout*-退出請選擇-6*n; cout*n;coutx;switch(x)case 1: l=creat(); break; case 2: read(l); break; case 3: search(l); break; case 4:radixsort(l); break; case 5: showrank(l); break; case 6: return 0 ; break; system(pause); system(cls);cout按任意鍵繼續(xù)操作endl; system(cls);return 0;4.課程設(shè)計心得本次課程設(shè)計我做的是多關(guān)鍵字lsd排序，在上數(shù)據(jù)結(jié)構(gòu)課時，我對鏈?zhǔn)交鶖?shù)排序的過程和功能實現(xiàn)有了一定的認識，但是對“分配”和“收集”的方法算法程序沒怎么弄懂。在做這次實驗時，我又重新把書上的算法看了一下，知道lsd(最低位優(yōu)先）法是從最次位關(guān)鍵字起進行排序，然后再對高一位的關(guān)鍵字進行排序，依次重復(fù)，直至對最高位關(guān)鍵字進行排序后便成為一個有序序列。“分配”和“收集”方法是在一趟排序中，將結(jié)點分配