c基數(shù)排序-課程設計報告

1、 目錄設計內(nèi)容及要求3題目內(nèi)容及要求概要設計3存儲結構設計說明主要算法流程圖設計過程及程序代碼6算法設計程序代碼設計結果與分析13課設總結15參考文獻16.設計內(nèi)容及要求題目：基數(shù)排序算法說明：基數(shù)排序：通過LSD（最低為優(yōu)先）法：按最低關鍵字位k1對待排序數(shù)據(jù)中的n個值進行排序按k1值把待排序文件中的n個記錄分配到具有不同k1值的若干個堆，然后按k1值從小到大的次序收集在一起，下次再按高一位關鍵子位k2的值進行分配和收集，如此不斷地按更高一位關鍵字位進行分配和收集，直到用kn分配和收集之后，整個數(shù)據(jù)按多關鍵字位有序。.概要設計存儲結構設計說明typedefstruct/定義數(shù)據(jù)在存儲類型in

2、tkey;data1;/類型標識符typedefstruct/定義數(shù)據(jù)在存儲類型intkeyd;/用數(shù)組存放數(shù)據(jù)個位數(shù)、十位數(shù)、百位數(shù)intnext;/指針域指向下一個數(shù)據(jù)形成鏈表結構data2;/類型標識符data1Rmax;data2R1max;/新類型數(shù)據(jù)data2R;intfrd,erdintp=0;intk,t;inti=d;i=0intj=0;jrdfj=-1；ej=-1；j+；p!=-1k=Rp.keyi;Y=Rpkeyil；fk=p；Rek.next=p;ek=p；p=Rp.next;j=0；fj=-1j+；p=fj；t=ej;j|7!ij第i越收黑|HRiFH扣&H皿5HTH

3、mHT,H四。IT必|圖3-3收集分配圖示(2)基數(shù)排序過程闡述：設有n個記錄，d個關鍵字，rd為基數(shù)，通過LSD(最低為優(yōu)先)法：初始化一系列的空隊列，先按最低關鍵字位k1對待排序數(shù)據(jù)中的n個值進行排序，按k1值把待排序文件中的n個記錄分配到具有不同k1值的相應隊列。然后按k1值從小到大的次序收集在一起，下次再按高一位關鍵子位k2的值進行分配和收集，如此不斷地按更高一位關鍵字位進行分配和收集，每一趟按一個關鍵值的位置記錄分配到rd個隊列中，同一鏈隊列中的記錄都是用鏈域指針鏈接起來的，所有的隊頭和隊尾指針分別放在兩個數(shù)組中，每一趟分配后通過修改指針將這個鏈隊列中的記錄收集起來；直到用kn分配和

4、收集之后，重復分配和收集d趟，便得到了最終排序好的有序序列。整個數(shù)據(jù)按多關鍵字位有序。3.2程序代碼#includestdio.h#definemax#definemax100#definerd#definerd10#define#definetypedefstruct/定義數(shù)據(jù)在存儲類型typedefstruct/定義數(shù)據(jù)在存儲類型intkey;intkey;data1;/類型標識符data1;/類型標識符typedefstruct/定義數(shù)據(jù)在存儲類型intkeyd;/用數(shù)組存放數(shù)據(jù)個位數(shù)、十位數(shù)、百位intnext;/指針域指向下一個數(shù)據(jù)形成鏈表結構typedefstruct/定義數(shù)據(jù)在存

5、儲類型intkeyd;/用數(shù)組存放數(shù)據(jù)個位數(shù)、十位數(shù)、百位intnext;/指針域指向下一個數(shù)據(jù)形成鏈表結構data2;/類型標識符data2;/類型標識符intjishusort(data2R)intjishusort(data2R)/*基數(shù)排序函數(shù)intfrd,erd;/定義隊列指示變量，分別指向隊intfrd,erd;/定義隊列指示變量，分別指向隊列頭和隊列尾intp=0,k,t;定義指示變量P,和存放數(shù)據(jù)各位關鍵值(個位，十位，百位)的七臨時隊尾存放用于收集數(shù)據(jù)的tfor(inti=d;i=0;i-)/外層循環(huán)控制數(shù)的關鍵值(個位，十位，百位)for(intj=0;jrd;j+)/*內(nèi)

6、層循環(huán)一初始化隊列為空*/fj=-1;ej=-1;while(p!=-1)/*內(nèi)層循環(huán)二數(shù)據(jù)按關鍵值分配至相應隊列*/k=Rp.keyi;關鍵值賦予kif(fk=-1)/隊列為空隊列頭指向當前數(shù)據(jù)fk=p;elseRek.next=p;/隊列不為空鏈接當前數(shù)據(jù)到隊列ek=p;/修改隊列尾指向當前值p=Rp.next;/數(shù)據(jù)指示變量后移為分配下一數(shù)據(jù)做準備intj=0;/刷新隊列指示器，為數(shù)據(jù)收集做準備while(fj=-1)/*內(nèi)層循環(huán)三數(shù)據(jù)收集*/j+;/掃描到非空隊列作為收集數(shù)據(jù)的p=fj;/當前指示器指向隊列首t=ej;/臨時存放保護隊列尾便于下一隊列鏈接上while(jrd-1)/*內(nèi)

7、層循環(huán)四收據(jù)數(shù)據(jù)鏈接成鏈表*/j+;/掃描下一隊列if(fj!=-1)/隊列非空則鏈接至數(shù)據(jù)收集鏈表Rt.next=fj;/數(shù)據(jù)收集鏈表尾指針指向索掃描到隊列的隊列首t=ej;/更改鏈表尾指針Rt.next=-1;/收集數(shù)據(jù)完成，鏈表尾置空returnp;voidchoices(data1R,inti)/選擇開關(主界面)data2R1max;/新類型數(shù)據(jù)intgw,sw,bw;/定義關鍵值，個位數(shù)，十位數(shù)，百位數(shù)intP；定義p存放最終返回值，鏈表頭for(intm=0;mi;m+)gw=Rm.key%10;/個位數(shù)關鍵值由除10取整得sw=(Rm.key%100)/10;/十位數(shù)由除百求余

8、再除10取整得bw=Rm.key/100;/百位數(shù)關鍵值由除100取余得R1m.key2=gw;/以下分別將關鍵值賦予相應位置R1m.key1=sw;R1m.key0=bw;R1m.next=m+1;/各數(shù)據(jù)指針域初始化intm;R1m.next=-1;/數(shù)據(jù)鏈表尾置空p=jishusort(R1);/調(diào)用基數(shù)排序函數(shù)while(p!=-1)/循環(huán)控制逐一打印排序后數(shù)列printf(%d%d%d,R1p.key0,R1p.key1,R1p.key2);p=R1p.next;printf(n);intmain()/*主函數(shù)*/intmain()inti=0;/局部變量用作結束輸入data1Rma

9、x;printf(請輸入數(shù)據(jù)以-1結束：”)；scanf(%d,&Ri.key);while(Ri.key!=-1)/待排序數(shù)據(jù)輸入i+;printf(請輸入數(shù)據(jù)以-1結束：);scanf(%d,&Ri.key);choices(R,i);調(diào)用主界面函數(shù)進行開關(操作)選擇return0;設計結果與分析1D;C-FreeMicrosoftVisualStudioMyProjectJiDebugji.eKe：123：123：34：345：67：1：-1請鮑入數(shù)據(jù)以T請|人數(shù)括以T請|人數(shù)括以T遹鮑遨據(jù)以T請輸人數(shù)據(jù)優(yōu)T眄1034067123345PressanykegtocontinueC:U5

10、ersa與usDesktopDebug.l23.exeS人數(shù)據(jù)以T結里2人數(shù)據(jù)以T結及與4人數(shù)據(jù)以T結克中8卬人數(shù)據(jù)以T結克;234人數(shù)據(jù)以T結束入數(shù)據(jù)以T結黃一工001012034234789Pressanykeytocontinue按照提示輸入任意一組整數(shù)，以-1結束，如圖所示，程序成功運行，實現(xiàn)將一組數(shù)字進行基數(shù)排序。由于能力和時間的關系，程序部分沒有包含處理不同類型的數(shù)據(jù)，只進行處理整形的數(shù)字排序，今后如果時間條件允許的話一定再進行詳細的研究。通過這次課程設計，使我對語言程程序設計這門課程有了更深一步的了解。它是計算機程序設計的重要理論技術基礎，在我們計算機專業(yè)的學習中占據(jù)著十分重要的地位。同時也使我們知道，要學好這門課程，僅學習書本上的知識是不夠的，還要有較強的實踐能力。因為我們學習知識就是為了實踐。而只有多實踐，多編寫程序，才能更好的理解與掌握書本上的東西。我們要知道，真本領只有在實戰(zhàn)中才能提高，光說不練是假把戲，我們要通過自己不斷追求完善，不斷學習新的能力，在一次次編程中成長，才能在真正的意思上成為一個會寫程序的人。課程設計是檢驗能力的重要環(huán)節(jié)，這能我們知識掌握更加牢固，能讓我們知道不僅僅要寫好寫出代碼，更要懂得去分析代碼，去讓別人看懂自己的代碼，要將自己的代碼達到最優(yōu)化。在最開始接到課設題目時，由于沒有具體的內(nèi)容和要求，我就把它當做心里想的那樣簡單