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

整理為word格式整理為word格式整理為word格式xx大學(xué)本科生課程設(shè)計(jì)論文題目：排序算法集成學(xué)生姓名：學(xué)號(hào)：專業(yè)：計(jì)算機(jī)班級(jí)：指導(dǎo)教師：2013年整理為word格式整理為word格式整理為word格式xx大學(xué)課程設(shè)計(jì)任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目排序算法集成指導(dǎo)教師時(shí)間2013.5.20-2013.5.30一、教學(xué)要求1.掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能3.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計(jì)資料及參數(shù)每個(gè)學(xué)生在教師提供的課程設(shè)計(jì)題目中任意選擇一題，獨(dú)立完成，題目選定后不可更換。排序算法集成定義動(dòng)態(tài)數(shù)組類（或類模板）以表示待排序數(shù)據(jù)，在此基礎(chǔ)上實(shí)現(xiàn)多種排序算法。要求設(shè)計(jì)函數(shù)模板來(lái)實(shí)現(xiàn)下列排序算法：直接插入排序冒泡排序簡(jiǎn)單選擇排序希爾排序快速排序堆排序并設(shè)計(jì)主函數(shù)測(cè)試動(dòng)態(tài)數(shù)組類（或類模板），測(cè)試各排序算法的函數(shù)模板。三、設(shè)計(jì)要求及成果1.分析課程設(shè)計(jì)題目的要求

2.寫出詳細(xì)設(shè)計(jì)說(shuō)明

3.編寫程序代碼，調(diào)試程序使其能正確運(yùn)行

4.設(shè)計(jì)完成的軟件要便于操作和使用

5.設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告四、進(jìn)度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測(cè)試（5天）編寫課程設(shè)計(jì)說(shuō)明書和驗(yàn)收（2天）五、評(píng)分標(biāo)準(zhǔn)1.根據(jù)平時(shí)上機(jī)考勤、表現(xiàn)和進(jìn)度，教師將每天點(diǎn)名和檢查2.根據(jù)課程設(shè)計(jì)完成情況，必須有可運(yùn)行的軟件。

3.根據(jù)課程設(shè)計(jì)報(bào)告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4.根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡(jiǎn)練的語(yǔ)言敘述自己的設(shè)計(jì)和回答教師的提問六、建議參考資料1．《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》嚴(yán)蔚敏、吳偉民主編清華大學(xué)出版社2004.112．《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編（用C/C++描述）》，李建學(xué)等編著，清華大學(xué)出版社2007.23.《數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述》，殷人昆主編，

清華大學(xué)出版社2007.6整理為word格式整理為word格式整理為word格式目錄目錄 3引言 4一．算法的設(shè)計(jì)思想 4二．算法的流程圖 4三．算法的設(shè)計(jì)與分析 53.1 建立數(shù)組 53.2算法思想 53.3 主要函數(shù) 63.4 主要函數(shù)聲明 63.5主要變量說(shuō)明 10四．程序源代碼 11五．運(yùn)行結(jié)果與分析（測(cè)試） 18六．總結(jié)（收獲與體會(huì)） 20七．參考文獻(xiàn) 21整理為word格式整理為word格式整理為word格式引言一．算法設(shè)計(jì)的思想數(shù)據(jù)結(jié)構(gòu)是與數(shù)據(jù)相關(guān)的一門重要學(xué)科，不論是想通過升學(xué)考試還是想把程序編得有水平，都要對(duì)這門學(xué)科下一點(diǎn)功夫才行。而課程設(shè)計(jì)是讓我們更好的掌握這門學(xué)科的重要方式。排序是計(jì)算機(jī)程序中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。而內(nèi)部排序中包括各種不同的排序，本課程設(shè)計(jì)主要討論的是插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。完成這幾種排序最主要的就是弄好不同排序的算法，只有深刻的認(rèn)識(shí)了這不同排序的算法，才能了解不同排序的優(yōu)點(diǎn)與缺點(diǎn)。通過對(duì)不同排序算法的分析，了解它們的優(yōu)劣特點(diǎn)。插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序的不同算法，寫出實(shí)現(xiàn)各個(gè)排序算法的函數(shù)。然后通過在主函數(shù)中對(duì)不同排序的子函數(shù)的調(diào)用來(lái)實(shí)現(xiàn)對(duì)某個(gè)序列的具體排序。二．算法的流程圖整理為word格式整理為word格式整理為word格式如圖2.1建立數(shù)組建立數(shù)組設(shè)計(jì)main函數(shù)建立各排序函數(shù)結(jié)束開始圖2.1主要設(shè)計(jì)思想流程圖三．算法的設(shè)計(jì)與分析3.1建立數(shù)組在程序中建立一個(gè)數(shù)組data[]，用于存儲(chǔ)程序運(yùn)行中的數(shù)據(jù)。3.2算法思想（1）插入排序插入排序的主要算法思想是將一個(gè)記錄插入到已排好的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。（2）希爾排序希爾排序的基本思想是先將整個(gè)待排記錄列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄整理為word格式整理為word格式整理為word格式“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。（3）冒泡排序函數(shù)冒泡排序首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，依次類推。（4）選擇排序函數(shù)選擇排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。（5）堆排序先將一個(gè)序列進(jìn)行建堆，然后將大頂堆的第一個(gè)元素和最后一個(gè)元素對(duì)換（或?qū)⑿№敹训淖詈笠粋€(gè)元素和第一個(gè)元素對(duì)換），再對(duì)除最后一個(gè)元素的序列進(jìn)行求大頂堆（或?qū)Τ谝粋€(gè)元素的序列進(jìn)行求小頂堆），依次類推。3.3主要函數(shù)（1）插入排序函數(shù)voidinsertion_sort(int[],int);/*插入排序*/（2）希爾排序函數(shù)voidshell_sort(int[],int);/*希爾排序*/（3）冒泡排序函數(shù)voidbubble_sort(int[],int);/*冒泡排序*/（4）選擇排序函數(shù)voidselect_sort(int[],int);/*選擇排序*/（5）將數(shù)據(jù)調(diào)整為堆的函數(shù)voidadjust(int,int);/*將數(shù)據(jù)調(diào)整為堆樹*/3.4主要函數(shù)聲明整理為word格式整理為word格式整理為word格式①插入排序插入排序的主要算法思想是將一個(gè)記錄插入到已排好的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。voidinsertion_sort(intdata[],intsize)/*插入排序*/{intbase,compare,temp,i,j=0;for(base=1;base<size;base++)/*當(dāng)數(shù)據(jù)小于第一個(gè)時(shí)，則插于前方，否則與后面數(shù)據(jù)對(duì)比找出插入位置*/{temp=data[base];compare=base;j++;while(compare>0&&data[compare-1]>temp){data[compare]=data[compare-1];compare--;}data[compare]=temp;printf("第%d趟排序:",j);for(i=0;i<size;i++) printf("%d",data[i]);printf("\n");}printf("\n最終排序結(jié)果:");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}②希爾排序希爾排序的基本思想是先將整個(gè)待排記錄列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄整理為word格式整理為word格式整理為word格式“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。voidshell_sort(intdata[],intsize)/*希爾排序*/{inti,j,k,incr,temp,num=0;incr=size/2;printf("\n");while(incr>0){ for(i=incr+1;i<size;i++){j=i-incr;while(j>0)if(data[j]>data[j+incr])/*比較每部分的數(shù)據(jù)大小順序不對(duì)則交換*/{ temp=data[j];data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr;}elsej=0;}num++;printf("\n第%d趟排序:",num);for(k=1;k<size;k++)printf("%d",data[k]);incr=incr/2;}printf("\n最終排序結(jié)果：");整理為word格式整理為word格式整理為word格式for(i=1;i<size;i++)printf("%d",data[i]);printf("\n");}③冒泡排序冒泡排序首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，依次類推。voidbubble_sort(intdata[],intsize)/*冒泡排序*/{inti,j,flag,k,temp,num=0;for(i=0;i<size-1;i++){flag=0;for(j=0;j<size-1;j++)/*讓數(shù)據(jù)兩兩比較，將小的置于前*/ {if(data[j]>data[j+1]){flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; } num++; printf("\n第%d趟排序：",num); for(k=0;k<size;k++) printf("%d",data[k]); printf("\n"); }printf("\n最終排序結(jié)果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");整理為word格式整理為word格式整理為word格式if(flag!=1) break;}}④選擇排序選擇排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。voidselect_sort(intdata[],intsize)/*選擇排序*/{intbase,compare,min,temp,i,num=0;for(base=0;base<size-1;base++)/*將目前數(shù)據(jù)與后面數(shù)據(jù)中最小的對(duì)調(diào)*/{min=base;for(compare=base+1;compare<size;compare++) if(data[compare]<data[min]) min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp;num++; printf("第%d趟排序：",num); for(i=0;i<size;i++) printf("%d",data[i]); printf("\n");}printf("\n最終排序結(jié)果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}整理為word格式整理為word格式整理為word格式3.5主要變量說(shuō)明Intdata[]:整型數(shù)組，用于儲(chǔ)存序列Intsize:整型變量，用于記錄序列長(zhǎng)度Inttemp:整型變量，用于交換元素Intm,n,k,i,j,num:一般整型變量四．程序源代碼#include<stdio.h>voidinsertion_sort(int[],int);/*插入排序*/voidshell_sort(int[],int);/*希爾排序*/voidbubble_sort(int[],int);/*冒泡排序*/voidselect_sort(int[],int);/*選擇排序*/voidadjust(int,int);/*將數(shù)據(jù)調(diào)整為堆樹*/voidinsertion_sort(intdata[],intsize)/*插入排序*/{intbase,compare,temp,i,j=0;for(base=1;base<size;base++)/*當(dāng)數(shù)據(jù)小于第一個(gè)時(shí)，則插于前方，否則與后面數(shù)據(jù)對(duì)比找出插入位置*/{temp=data[base];compare=base;j++;while(compare>0&&data[compare-1]>temp){data[compare]=data[compare-1];compare--;}data[compare]=temp;printf("第%d趟排序:",j);for(i=0;i<size;i++)整理為word格式整理為word格式整理為word格式printf("%d",data[i]);printf("\n");}printf("\n最終排序結(jié)果:");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}voidshell_sort(intdata[],intsize)/*希爾排序*/{inti,j,k,incr,temp,num=0;incr=size/2;printf("\n");while(incr>0){ for(i=incr+1;i<size;i++) {j=i-incr;while(j>0)if(data[j]>data[j+incr])/*比較每部分的數(shù)據(jù)大小順序不對(duì)則交換*/ { temp=data[j];data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr; }elsej=0; }整理為word格式整理為word格式整理為word格式num++;printf("\n第%d趟排序:",num);for(k=1;k<size;k++)printf("%d",data[k]);incr=incr/2;}printf("\n最終排序結(jié)果：");for(i=1;i<size;i++)printf("%d",data[i]);printf("\n");}voidbubble_sort(intdata[],intsize)/*冒泡排序*/{inti,j,flag,k,temp,num=0;for(i=0;i<size-1;i++){flag=0;for(j=0;j<size-1;j++)/*讓數(shù)據(jù)兩兩比較，將小的置于前*/{if(data[j]>data[j+1]){flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp;}num++;printf("\n第%d趟排序：",num);for(k=0;k<size;k++)printf("%d",data[k]);printf("\n");}printf("\n最終排序結(jié)果：");整理為word格式整理為word格式整理為word格式for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");if(flag!=1) break;}}voidselect_sort(intdata[],intsize)/*選擇排序*/{intbase,compare,min,temp,i,num=0;for(base=0;base<size-1;base++)/*將目前數(shù)據(jù)與后面數(shù)據(jù)中最小的對(duì)調(diào)*/{min=base;for(compare=base+1;compare<size;compare++) if(data[compare]<data[min]) min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp;num++; printf("第%d趟排序：",num); for(i=0;i<size;i++) printf("%d",data[i]); printf("\n");}printf("\n最終排序結(jié)果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}整理為word格式整理為word格式整理為word格式voidadjust(inti,intn)/*將數(shù)據(jù)調(diào)整為堆樹*/{intdata[20],j,k,done=0;k=data[i];j=2*i;while((j<=n)&&(done==0)){if((j<n)&&(data[j]<data[j+1]))j++;if(k>=data[j])done=1;else{data[j/2]=data[j];j=2*j;}}data[j/2]=k;}voidmain(){intdata[20];intsize=0,m=0,i,j,num,k,temp,n=0;printf("\n請(qǐng)輸入初始關(guān)鍵字（輸入0結(jié)束）:\n");do{ scanf("%d",&data[size]); m++;}while(data[size++]!=0);printf("你輸入的初始關(guān)鍵字為：");整理為word格式整理為word格式整理為word格式for(j=0;j<m-1;j++)printf("%d",data[j]);printf("\n排序方法：\n");printf("\n1、插入排序\n");printf("\n2、希爾排序\n");printf("\n3、冒泡排序\n");printf("\n4、選擇排序\n");printf("\n5、堆排序\n");printf("\n請(qǐng)選擇排序方法：\n");scanf("%d",&num);switch(num){case1:printf("****************插入排序************\n");for(i=0;i<50;i++)printf("-");printf("\n");insertion_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case2: printf("****************希爾排序************\n"); for(m=0;m<50;m++)printf("-");shell_sort(data,--size); for(i=0;i<50;i++)printf("-");printf("\n");break;case3: printf("****************冒泡排序************\n"); for(i=0;i<50;i++)printf("-");printf("\n");bubble_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case4:整理為word格式整理為word格式整理為word格式 printf("****************選擇排序************\n"); for(i=0;i<50;i++)printf("-");printf("\n");select_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case5: size=size-1; printf("*****************堆排序*************\n"); for(i=0;i<50;i++)printf("-"); for(i=size/2;i>0;i--)adjust(i,size); printf("\n堆："); for(k=1;k<siz