數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-排序算法集成

1、XX大學(xué)本科生課程設(shè)計論文題目:學(xué)生姓名:學(xué)號:專業(yè):班級:指導(dǎo)教師:排序算法集成計算機(jī)2013年5月20日XX大學(xué)課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目排序算法集成指導(dǎo)教師時 間2013.5.20-2013.5.30一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)訃、程序編碼、測試等基本方法和技能3. 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力4. 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作 方法和作風(fēng)二、設(shè)計資料及參數(shù)每個學(xué)生在教師提供的課程設(shè)計題目中任意選

2、擇一題，獨(dú)立完成，題目選左后不可更換。 排序算法集成定義動態(tài)數(shù)組類（或類模板）以表示待排序數(shù)據(jù)，在此基礎(chǔ)上實現(xiàn)多種排序算法。 要求設(shè)計函數(shù)模板來實現(xiàn)下列排序算法：直接插入排序冒泡排序簡單選擇排序希爾排序快速排序 堆排序并設(shè)計主函數(shù)測試動態(tài)數(shù)組類（或類模板），測試各排序算法的函數(shù)模板。三、設(shè)計要求及成果1. 分析課程設(shè)計題目的要求2. 寫出詳細(xì)設(shè)計說明3. 編寫程序代碼，調(diào)試程序使英能正確運(yùn)行4. 設(shè)計完成的軟件要便于操作和使用5. 設(shè)計完成后提交課程設(shè)汁報告四、進(jìn)度安排資料査閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設(shè)計說明書和驗收（2天）五、評分標(biāo)準(zhǔn)1. 根據(jù)平時上機(jī)考

3、勤、表現(xiàn)和進(jìn)度，教師將每天點(diǎn)名和檢查2. 根據(jù)課程設(shè)計完成情況，必須有可運(yùn)行的軟件。3. 根據(jù)課程設(shè)計報告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據(jù)答辯的情況，應(yīng)能夠以淸晰的思路和準(zhǔn)確、簡練的語言敘述自己的設(shè)計和回答教師的提問六、建議參考資料1. 數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴(yán)蔚敏、吳偉民主編淸華大學(xué)出版社2004.112. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述），李建學(xué)等編著，淸華大學(xué)出版社2007.23. 數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語言描述，殷人昆主編，淸華大學(xué)出版社2007.6目 錄3引言4本課程設(shè)計主要解決兒種不同排序方法以及在各種不同排序的過程中某一趟的 具體排序

4、結(jié)果。通過觀察各種排序的具體排序過程，加深對不同排序方法的認(rèn)識， 加深對不同排序算法的掌握。一. 算法設(shè)計的思想數(shù)據(jù)結(jié)構(gòu)是與數(shù)據(jù)相關(guān)的一門重要學(xué)科，不論是想通過升學(xué)考試還是想把程 序編得有水平，都要對這門學(xué)科下一點(diǎn)功夫才行。而課程設(shè)計是讓我們更好的掌 握這門學(xué)科的重要方式。排序是訃算機(jī)程序中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄） 的任意序列重新排列成一個按關(guān)鍵字有序的序列。而內(nèi)部排序中包括各種不同 的排療:，本課程設(shè)計主要討論的是插入排療:、希爾排丿了;、冒泡排序、快速排序、 選擇排序、堆排序。完成這兒利排序最主要的就是弄好不同排序的算法，只有深刻的認(rèn)識了 這不同排序的算法，才能了

5、解不同排序的優(yōu)點(diǎn)與缺點(diǎn)。通過對不同排序算法的分 析，了解它們的優(yōu)劣特點(diǎn)。據(jù)對題的分析，首先要根據(jù)插入排序、希爾排序、冒泡排序、快速排序、 選擇排序、堆排序的不同算法，寫出實現(xiàn)各個排序算法的函數(shù)。然后通過在主函 數(shù)中對不同排序的子函數(shù)的調(diào)用來實現(xiàn)對某個序列的具體排序。內(nèi)部排序的方法 很多，但就其全面性而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各 自的優(yōu)缺點(diǎn)，適合不同的環(huán)境。通常，在排序的過程中需進(jìn)行兩種基本操作：（1） 比較兩個關(guān)鍵字的大??；（2）將記錄從一個位置移動至另一位置。前一個操作對大 多數(shù)排序方法來說都是必要的，而后一個操作可以通過改變記錄的存儲方式來予以 避免。二. 算法的

6、流程圖如圖2.1圖2.1主要設(shè)計思想流程圖三. 算法的設(shè)計與分析3.1建立數(shù)組在程序中建立一個數(shù)組data,用于存儲程序運(yùn)行中的數(shù)據(jù)。3.2算法思想（1）插入排序插入排序的主要算法思想是將一個記錄插入到已排好的有序表中, 從而得到一個新的、記錄數(shù)增1的有序表。（2）希爾排序希爾排序的基本思想是先將整個待排記錄列分割成若干子序列分 別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄 進(jìn)行一次直接插入排序。（3）冒泡排序函數(shù)冒泡排序首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比 較，若為逆序則將兩個記錄交換，然后比較笫二個記錄和第三個記錄的關(guān)鍵 字，依次類推。（4）選擇排序函數(shù)

7、選擇排序的基本思想是：每一趟在n-i+l（i=12.,n-l）個記錄中選取 關(guān)鍵字最小的記錄作為有序序列中第i個記錄。（5）堆排序先將一個序列進(jìn)行建堆,然后將大頂堆的笫一個元素和最后一個元 素對換（或?qū)⑿№敹训淖詈笠粋€元素和第一個元素對換），再對除最后一個元 素的序列進(jìn)行求大頂堆（或?qū)Τ谝粋€元素的序列進(jìn)行求小頂堆），依次類推。33主要函數(shù)（1）插入排序函數(shù)void insertion_sort（int,int）;/*插入排序*/（2）希爾排序函數(shù)void shell_sort（int,int）;/*希爾排序*/（3）冒泡排序函數(shù)void bubble_sort（int,int）;/* 冒泡排

8、序*/（4）選擇排序函數(shù)void select_sort（int,int）;/*選擇排序*/（5）將數(shù)據(jù)調(diào)整為堆的函數(shù)void adjust（intjnt）;/*將數(shù)據(jù)調(diào)整為堆樹*/3.4主要函數(shù)聲明 插入排序插入排序的主要算法思想是將一個記錄插入到已排好的有序表中， 從而得到一個新的、記錄數(shù)增1的有序表。void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=O;for(base=l;base0 & datacompare-ltemp)datacompare=datacompare-l;compare-;

9、datacompare=temp;printf(M%d 趟排序J);for(i=0;isize;i+)printf(%d ,datai);printfCXn);printf(n最終排序結(jié)果for(i=0;i0)for(i=incr+l;i0)if(datajdata j+incr )/*比較每部分的數(shù)據(jù)大小順序不對則交換*/ temp=dataj;dataj=data j+incr;dataj+incr=temp;j=j-incr;elsei=o；num+;printf(n 第日趟排序/num);for(k=l;ksize;k+)printf(%d datak);in cr=i ncr/2;p

10、rintf(n最終排序結(jié)果：“);for(i=l;isize;i+)printf(H%d datapj); printfCXn); 冒泡排序冒泡排序首先將第一個記錄的關(guān)鍵字和笫二個記錄的關(guān)鍵字進(jìn)行比 較，若為逆序則將兩個記錄交換，然后比較第二個記錄和笫三個記錄的關(guān) 鍵字，依次類推。void bubble_sort(int data?int size)/* H泡排序*/int i,j,flag,k,temp,num=O;for(i=0;isize-l;i+)flag=O;for(j=0;jdataj+l)flag;temp=dataj;data j=d ata j+1;dataj+l=temp;

11、num+;printf(n 第4 趟排序：,num);for(k=0;ksize;k+)printf(%d ,datak);printfCXn);printf(n最終排序結(jié)果：”);for(i=0;isize;i+)printf(%d ”,datai);printf(n);if(flag!=l)break; 選擇排序選擇排序的基本思想是：每一趟在n-i+l(i=l,2/./n-l)個記錄中選取關(guān) 鍵字最小的記錄作為有序序列中第i個記錄。void select_sort(int dataJnt size)/*選擇排序*/int base,compare,min,temp丄num=O;for(ba

12、se=0;basesize-l;base+)/*將U前數(shù)據(jù)與后面數(shù)據(jù)中最小的對調(diào)*/ min二base;for(compare=base+l;comparesize;compare+)訐(datacomparedatamin)min=compare;temp=datamin;datamin=database;database=temp;num+;printf(第d 趟排序:znum);for(i=0;isize;i+)printf(%d ,datai);printfCXn);printf(n最終排序結(jié)果：for(i=0;isize;i+)printf(%d ,datai);printfCXn)

13、;3.5主要變量說明Int data:整型數(shù)組，用于儲存序列Int size:整型變量，用于記錄序列長度Int temp:整型變量，用于交換元素Int m,n,k,i,j,num:般整型變量四. 程序源代碼#includevoid insertion_sort(intJnt);/*插入排序拿/void shelsortfintOJnt);/*希爾排序*/void bubble_sort(intzint);/* 冒泡排序*/void selectsortfintlJjnt);/*選擇排序*/void adjust(intjnt);/*將數(shù)據(jù)調(diào)整為堆樹*/void insertion_sort(i

14、nt data山int size)/*插入排序*/int bas已compar已temp,j=O;for(base=l;base0 & datacompare-ltemp)datacompare=datacompare-l;compare-;datacompare=temp;printf(第d 趟排序:,j);for(i=0;isize;i+)printf(nn最終排序結(jié)果門;for(i=0;i0)for(i=incr+l；i0)if(datajdataj+incr)/*比較每部分的數(shù)據(jù)大小順序不對則交換*/ temp=dataj;dataj=dataj+incr;dataj+i ncr二te

15、mp;j=j-incr;elsej=0；num+；printf(Hn 第( 趟排序fnum);for(k=l;ksize;k+)printf(%d ,datak);incr=incr/2;printf(un最終排序結(jié)果：“)；for(i=l;isize;i+)printf(%d 舄 datai);printf(“n);void bubble_sort(int data,int size)/*冒泡排序*/int i jflagktemp，num=O;for(i=0;isize-l;i+)flag=O;forG=0;jdataj+l) flag=l；temp=dataj;dataj=dataj+l

16、;dataj+l=temp;num+;printf(Hn 第(1 趟排序:num);for (k=0; ks ize; k+)printf( *%d 蔦 datak);printf(n);printf(n最終排序結(jié)果：”)；for(i=0;isize;i+)if(flag!=l)break;void select_sort(int data,int size)/*選擇排序*7int baseompareminempjum;for(base=0;basesize-l;base+)/*將目前數(shù)據(jù)與后面數(shù)拯中最小的對調(diào)*/min 二 base;for(compare=base+l;comparesi

17、ze;compare+)if(datacomparedatamin)min=compare;temp=datamin;datamin=database);database=temp;nu m+;printf(%d 趟排序：.num);for(i=0;isize;i+)printf(H%d u,datai);printf(n”)；printf(un最終排序結(jié)果：“)；for(i=0;isize;i+)printf(%d 舄 datai);printfO11)；void adjust(int i,int n)嚴(yán)將數(shù)據(jù)調(diào)整為堆樹*/int data20,j/k/done=0;k=datai;j=2*

18、i；while(j=n)&(done=0)if(jn)&(dataj=dataj)done=l;elsedataj/2=dataj;j=2*j；dataj/2=k;void main()int data20;int size=0,m=0 jj,num，ktGmp,n=O;printf(un請輸入初始關(guān)鍵字(輸入0結(jié)束):n)；doscanf(,%d,&datasize);m+;while(datasize+ !=0);printf(你輸入的初始關(guān)鍵字為：);for(j=0;jm-l;j+)printf(u%d u,dataj);printf(nlx插入排序寸);printf(n2希爾排序rf)

19、;printf(un3x冒泡排序rf);printf(n4v選擇排序nj;printf(n5x 堆排序n“);printf(Hn請選擇排序方法：nu)； scanf(%cT,&num);switch( num) case 1:prin tf(* * 車扌甫入曲 for(i=0;iv50;i 卄)printf(,-,)；printf(,n);insertio n_ sort(data,-size);for(i=0;i50;i+)printf(叮);printf(”n);break;case 2: printf (h * 扌 * 寧車 * 希爾曲F序* * 孚 * *n) for( m=0; m5

20、0; m+) pri ntf ();shell_sort(data/size);for(i=0;i50;i+)printf(,-,);printf(,n,1)；break;case 3:prin冒泡排序for(i=0;i50;i+)printf(,-,);printf(,n,1)； bubble_sort(data,size);for(i=0;iv50;i+)printf();printf(n”);break;case 4: prin tf(r * *選擇序nmrT);for(i=0;i50;i+)printf(,-,)；printf(,n,)；select_sort(dataz-size);

21、for(i=0;iv50;i+)printfC);printf(n”); break;case 5:printf(size=size-l;堆排序for(i=0;i0;i)adjust(i,size);printf(Nn 堆);for(k=l;k0;i-)temp=datai+l；datai+l=datal);datal=temp;/*將樹根和最后的節(jié)點(diǎn)交換*/adjust(lj);/*再重新調(diào)整為堆樹拿/printf(Hn 第d 趟排序:for(k=l;ksize;k+)prlntf(%d 蔦 datak);printf(n最終排序結(jié)果：”); for(k=l;ksize;k+) printf

22、(”d u,datak);printf(“n);for(i=0;iv50;i+)printfV);printf(”n); break;五. 運(yùn)行結(jié)果與分析（測試）（1）程序開始如圖4.1請輸入初妬關(guān)鍵字（輸入0結(jié)朿丿：圖4.1程序開始界面（2）輸入關(guān)鍵字以后如圖42請輸入初始關(guān)犍字（輸入0結(jié)東）:8877665544332211圖4.2輸入關(guān)鍵字以后界而（3）在輸入關(guān)鍵字后的排序方法選擇如圖43你輸入的初始關(guān)鍵字為=8877665544332211菲序方法；L、插入排序氛希爾排序3、冒泡排序4、選擇排序5、堆操序請選擇推序方法:圖43在輸入關(guān)鍵字后的排序方法選擇界面（4）輸入1,輸出插入排序結(jié)

23、果如圖44* 入申 E 序 iwwwwwcwwwc+w1144448877882288778877447777447?666644334411 亠affffffga序 二-二-二-二-二-二-二 趣a:s:s:ffi:s:s: 二L f 二上二/ 二上4B i 2 3 4 5 G 7?4433最終排序結(jié)果記丄223344 556677 88圖4.4插入排序輸岀結(jié)果界而（5）輸入2,輸出希爾排序結(jié)果如圖4.5XXXXXXWXXXM)(lf 布邪申R 序資淡識XX)C)G)CXX)(M?1 2 3終 aa= hrkrr.11111144776655445566?4455667734455661177圖45希爾排序輸岀結(jié)果界而（6）輸入3,輸出冒泡排序結(jié)果如圖46* 冒 泡申 E 序 *第趟排序;7788665544332211第2趟排序;7766885544332211第3趟排序:7766558844332211第4趟排序7766554488332211第5趟排序7766554433882211第6趟排區(qū)7766554433228811第刪E序7766554433221188最終排序結(jié)杲=77665544332211圖46冒泡排序輸出結(jié)果（7）輸入4,輸出選擇排序結(jié)果如圖4.7X “再“選擇書E序其*養(yǎng)知條“*其6677774466117