排序算法集成

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說(shuō)明書(shū)題目排序算法集成學(xué)號(hào)1376807439姓名趙杉杉指導(dǎo)教師王麗穎日期2015年6月28日內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書(shū)課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)設(shè)計(jì)題目排序算法集成指導(dǎo)教師王麗穎 時(shí)間 2015.6.22——2015.7.2一、 教學(xué)要求掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、 設(shè)計(jì)資料及參數(shù)每個(gè)學(xué)生在教師提供的課程設(shè)計(jì)題目中任意選擇一題，獨(dú)立完成，題目選定后不可更換。排序算法集成定義動(dòng)態(tài)數(shù)組類(lèi)（或類(lèi)模板）以表示待排序數(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ù)組類(lèi)（或類(lèi)模板），測(cè)試各排序算法的函數(shù)模板。三、 設(shè)計(jì)要求及成果分析課程設(shè)計(jì)題目的要求寫(xiě)出詳細(xì)設(shè)計(jì)說(shuō)明編寫(xiě)程序代碼，調(diào)試程序使其能正確運(yùn)行設(shè)計(jì)完成的軟件要便于操作和使用設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告四、 進(jìn)度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開(kāi)發(fā)與測(cè)試（5天）編寫(xiě)課程設(shè)計(jì)說(shuō)明書(shū)和驗(yàn)收（2天）五、 評(píng)分標(biāo)準(zhǔn)根據(jù)平時(shí)上機(jī)考勤、表現(xiàn)和進(jìn)度，教師將每天點(diǎn)名和檢查根據(jù)課程設(shè)計(jì)完成情況，必須有可運(yùn)行的軟件。根據(jù)課程設(shè)計(jì)報(bào)告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡(jiǎn)練的語(yǔ)言敘述自己的設(shè)計(jì)和回答教師的提問(wèn)六、 建議參考資料《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》嚴(yán)蔚敏、吳偉民主編清華大學(xué)出版社2004.11《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編（用C/C++描述）》，李建學(xué)等編著，清華大學(xué)出版社2007.2《數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述》，殷人昆主編，清華大學(xué)出版社2007.6TOC\o"1-5"\h\z\o"CurrentDocument"第1章需求分析 4\o"CurrentDocument"第2章總體設(shè)計(jì) 5第3章抽象數(shù)據(jù)類(lèi)型定義 63.1排序抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì) 6\o"CurrentDocument"第4章詳細(xì)設(shè)計(jì) 74.1工程視圖 74.2類(lèi)圖視圖 74.3函數(shù)的調(diào)用關(guān)系 84.4主程序流程圖 94.5主要算法的流程圖 10\o"CurrentDocument"第5章測(cè)試 16\o"CurrentDocument"第6章總結(jié) 20\o"CurrentDocument"附錄：程序代碼 21第1章需求分析排序算法集成:定義動(dòng)態(tài)數(shù)組類(lèi)（或類(lèi)模板）以表示待排序數(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ù)組類(lèi)（或類(lèi)模板），測(cè)試各排序算法的函數(shù)模板。第2章總體設(shè)計(jì)本系統(tǒng)是輸入待排序的數(shù)據(jù)，通過(guò)人為的選擇是利用哪種排序進(jìn)行運(yùn)算，運(yùn)算之后，將排好序的結(jié)果輸出，并且可以進(jìn)行多組數(shù)據(jù)的操作。系統(tǒng)功能圖2.1主要設(shè)計(jì)思想流程圖第3章抽象數(shù)據(jù)類(lèi)型定義定義格式如下：3.1排序抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)ClassSort{基本操作：voidintput()操作結(jié)果：初始化動(dòng)態(tài)申請(qǐng)的數(shù)。intget_len()操作結(jié)果：返回申請(qǐng)數(shù)組的大小。voiddisplay。操作結(jié)果：排序菜單的顯示。voidsel_sort()操作結(jié)果：執(zhí)行簡(jiǎn)單選擇排序。voidpar_sort(intl,intr)初始條件：動(dòng)態(tài)數(shù)組的第一個(gè)元素的下標(biāo)，和最后一個(gè)元素的下標(biāo)。操作結(jié)果：執(zhí)行快速排序。voidbub_sort()操作結(jié)果：執(zhí)行冒泡排序。voidinsert_sort()操作結(jié)果：執(zhí)行插入排序。voidxier_sort()操作結(jié)果：執(zhí)行希爾排序。voidheap_rebuild(intdata[],introot,intsize)操作結(jié)果：建立堆。voidheap_sort()操作結(jié)果：執(zhí)行堆排序}；第4章詳細(xì)設(shè)計(jì)4.1工程視圖--SR.1.......classes+吒Sort+_lGIobaIs4.1.1源代碼文件顯示4.2類(lèi)圖視圖bub_sort0display。get_Ien()heap_rebjiIdl(intdata[].introot,intsize；heap_sort0input()insert_sort()output()par_sort(intI,intr)sel_sort0xier_sort()》data--J..S.i.pba.i.s.lmain0圖4.2.1類(lèi)圖視圖顯示Main()菜單顯示Input(六種排序函數(shù)Output()clear圖4.3.1函數(shù)調(diào)用關(guān)系開(kāi)始/輸入數(shù)據(jù)菜單顯示/ZZ；/排序選擇堆排序希爾排序直接插入排序冒泡排序快速排序簡(jiǎn)單選擇排序圖4.4.1主程序流程圖圖4.4.1選擇排序流程圖圖4.4.2快速排序流程圖圖4.4.3冒泡排序流程圖i++圖4.4.4直接插入排序流程圖55942731677956839756834556677J79V97花-^_327二趟排疹結(jié)果E三趟排序姑果;27【初始關(guān)鍵字1:一趟排序結(jié)果:圖4.4.5希爾排序流程例圖圖4.4.6堆排序流程圖第5章測(cè)試C:\llsers\lenovo\Desktopk趙杉杉in\Debug曙杉杉.exe歡迎來(lái)到排序系統(tǒng)請(qǐng)輸入申請(qǐng)數(shù)組的大小:圖5.1開(kāi)始界面C:\Users\lenovo\Desktop\趙杉杉in\Debug睫杉杉.exerr歡迎來(lái)到排序系統(tǒng)大62GO

的加加:且來(lái)右親萎i

mt

請(qǐng)第第第

申入入入請(qǐng)請(qǐng)請(qǐng)iiif選要【t-序?.序...—\序?單速泡票排入E檬冒直輸123456^圖5.2輸入數(shù)據(jù)及菜單顯示C:\Users\lenovo\Deskto[A趙杉杉\bin'Debug睫杉杉.exm歡迎來(lái)到排序系統(tǒng)628

噩魏教魏

628

噩魏教魏

請(qǐng)第第第

申入入入請(qǐng)請(qǐng)方的.序■.序■E.洋sflS擇^!^大序要單速泡累排入E曜冒直輸1.2.3.4.5.6.請(qǐng)排序后的結(jié)果顯示：268是否進(jìn)行其他數(shù)據(jù)排序（X其他）:圖5.3簡(jiǎn)單選擇排序結(jié)果顯示C:\Users\lenovo\Desktopk也杉杉\bin\Debug\^<杉杉.exe歡迎來(lái)到排序系統(tǒng)..1111-■.11..1111-■.11_l_'\i236的5:5?:乩軋1234請(qǐng)第第第第申入入入入An用請(qǐng)請(qǐng)請(qǐng)請(qǐng)iiii方fl的序序擇flfl擇-ty!tA:序要單速泡累排入E檬冒直輸1.2.3.4.5.6.請(qǐng)排序后的結(jié)果顯示：261131是否進(jìn)行其他數(shù)據(jù)排序（”其他）：搜狗拆首輸入法半=圖5.4快速排序結(jié)果顯示

C:\Users\lenovo\Deskto[A起杉杉in\Debug\^<杉杉.exe歡迎來(lái)到排序系統(tǒng)TTTTT12345請(qǐng)第第第第第SAAAAA.4/一削d職所d刖函^請(qǐng)倩請(qǐng)請(qǐng)方序■序，【W(wǎng)』二?』二?Lt~引引選至成片A-序要單速泡素排入E晨冒直輸」2.3.4.5.6.請(qǐng)排序后的杪口果顯?。?3468是否進(jìn)行其他數(shù)據(jù)排序（”其他）:歡迎來(lái)到排序系統(tǒng)圖5.5冒泡排序結(jié)果顯示+,■■-..■■歡迎來(lái)到排序系統(tǒng)圖5.5冒泡排序結(jié)果顯示+,■■-..■■416375L.1■■ ,b^a^uanrj*女*5*中萎采中汁Y--TTTTTT123456請(qǐng)第第第第第第SAAAAAA-In——-劇-ij.用-Lj.用-Lj.劇-ij.用-Lj.切心請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)iiiiii方fl的序■序，【律-Z--Z-tu~flfl擇-ty!tA:序要單速泡累排入寸模冒直輸1.2.3.4.5.6.請(qǐng)排序后的結(jié)果顯示：134567是否進(jìn)行其他數(shù)據(jù)排序（”其他）: 圖5.6直接插入排序結(jié)果顯示

C:\Users\lenovo\Deskto[A起杉杉in\Debug\^<杉杉.exe歡迎來(lái)到排序系統(tǒng)0146TTTTT12345請(qǐng)第第第第第SAAAAA0146TTTTT12345請(qǐng)第第第第第SAAAAA.4/一削d職所d刖函^請(qǐng)倩請(qǐng)請(qǐng)方序■序，【W(wǎng)』二?』二?Lt~引引選至成片A-序要單速泡素排入E晨冒直輸」2.3.4.5.6.請(qǐng)排序后的結(jié)果顯示：01469

是否進(jìn)行其他數(shù)據(jù)排序（”其他）:歡迎來(lái)到排序系統(tǒng)圖5.7希爾排序結(jié)果顯示請(qǐng)第第第第

申入入入入

An

請(qǐng)請(qǐng)請(qǐng)

陶iiii6方序■序，【W(wǎng)』二?』二?Lt~引引選至成片A-序要單速泡素排入E晨冒直輸」2.3.4.5.6.請(qǐng)排序后的結(jié)果顯示：38IB21

是否進(jìn)行其他數(shù)據(jù)排序（“其他）：圖5.8堆排序結(jié)果顯示第6章總結(jié)經(jīng)過(guò)了兩個(gè)星期的課程設(shè)計(jì)，我體會(huì)頗多，學(xué)到很多東西。利用設(shè)計(jì)排序算法集成系統(tǒng)的機(jī)會(huì)，我加強(qiáng)了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，復(fù)習(xí)了自己以前的知識(shí)，提高了邏輯思考能力。在這次課程設(shè)計(jì)中，我還懂得了做程序的一些比較重要的步驟，比如總體設(shè)計(jì)、程序模塊設(shè)計(jì)、包括功能需求、用戶(hù)界面設(shè)計(jì)、程序代碼設(shè)計(jì)與分析、運(yùn)行結(jié)果等。在課程設(shè)計(jì)中我遇到了一些平時(shí)做作業(yè)所沒(méi)遇到的問(wèn)題。在做課程設(shè)計(jì)的過(guò)程中，加深了對(duì)書(shū)本知識(shí)的理解，同時(shí)也培養(yǎng)了自己的動(dòng)手能力。因?yàn)樯蠈W(xué)期做過(guò)兩次課程設(shè)計(jì)，對(duì)于課程設(shè)計(jì)有了一些經(jīng)驗(yàn)了吧，從總體上來(lái)說(shuō)還算比較順利，只是之前忙于準(zhǔn)備考試，之后做課程設(shè)計(jì)感覺(jué)時(shí)間有點(diǎn)緊，應(yīng)該是我在時(shí)間安排上有點(diǎn)問(wèn)題吧。這次課程設(shè)計(jì)，是將這一學(xué)期學(xué)到的論知識(shí)用于了實(shí)踐，在我在實(shí)踐中得到了很多經(jīng)驗(yàn)。在這次設(shè)計(jì)過(guò)程中，體現(xiàn)出自己?jiǎn)为?dú)設(shè)計(jì)模具的能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。在看到在自己付出了努力所做出來(lái)的成果時(shí)，我感到非常的欣慰。最后我還要感謝我的指導(dǎo)老師，感謝在我遇到問(wèn)題時(shí)幫我解決問(wèn)題的同學(xué)，沒(méi)有你們的幫助我是不可能做好的。我以后還要更加努力，不辜負(fù)老師與家人的期望。從這段時(shí)間，我獲得了知識(shí)，學(xué)到了研究的堅(jiān)持與韌性，這不僅僅是交出了一份作業(yè)，還對(duì)自己有了新的認(rèn)識(shí)，實(shí)在是難得的機(jī)遇與經(jīng)歷。附錄：程序代碼#include<iostream>#include<cstdlib>usingnamespacestd;classSort{public:voidinput(){歡迎來(lái)到排序系統(tǒng)”歡迎來(lái)到排序系統(tǒng)”；請(qǐng)輸入申請(qǐng)數(shù)組的大小：”;請(qǐng)輸入第"<<i+1<<"個(gè)數(shù)：”cout<<endl<<"cout<<endl<<"";cout<<endl<<"cin>>n;len=n;data=newint[n];for(i=0;i<n;i++){cout<<"cin>>data[i];}}intget_len(){returnlen;}voidoutput();voiddisplay();voidsel_sort(); 〃選擇voidpar_sort(intl,intr);//快排voidbub_sort();〃冒泡voidinsert_sort(); //插入排序voidxier_sort();//希爾排序voidheap_rebuild(intdata[],introot,intsize);//堆得建立voidheap_sort(); //堆排序private:int*data;intlen;};voidSort::sel_sort(){inti,j,k,b;for(i=0;i<len-1;i++){k=i;for(j=i+1;j<len;j++){if(data[j]<data[k])k=j;}if(k!=i){b=data[i];data[i]=data[k];data[k]=b;}}}voidSort::par_sort(intl,intr){if(l<r){inti=l,j=r,x=data[l];while(i<j){while(i<j&&data[j]>=x)//從右向左找第一個(gè)小于x的數(shù)j--;if(i<j)data[i++]=data[j];while(i<j&&data[i]<x)//從左向右找第一個(gè)大于等于x的數(shù)i++;if(i<j)data[j--]=data[i];}data[i]=x;par_sort(l,i-1);//遞歸調(diào)用par_sort(i+1,r);}}voidSort::bub_sort(){inti,j,k;for(i=0;i<len-1;i++){for(j=i;j<len-1;j++){if(data[j+1]<data[j]){k=data[j+1];data[j+1]=data[j];data[j]=k;}}}}voidSort::insert_sort(){inti,j,k;inttemp;for(i=1;i<len;i++){temp=data[i];for(j=0;j<i;j++)if(data[i]<data[j]){for(k=i;k>j;k--){data[k]=data[k-1];}data[j]=temp;}}}voidSort::xier_sort(){intj,temp,d;d=len/2;while(d>0){for(inti=d;i<len;i++)temp=data[i];j=i-d；while(j>=0&&data[j]>temp){data[j+d]=data[j];j-=d;}data[j+d]=temp;}d/=2;}}voidSort::heap_rebuild(intdata[],introot,intsize){intchild=2*root+1;if(child<=size-1){intrightChild=child+1;if(rightChild<=size-1)if(data[child]<data[rightChild])child=rightChild;if(data[root]<data[child]){inttemp=data[child];data[child]=data[root];data[root]=temp;heap_rebuild(data,child,size);}}}voidSort::heap_sort(){inti;for(i=len-1;i>=0;i--){heap_rebuild(data,i,len);}intlast=len-1;for(intj=1;j<=len;j++,last--){inttemp=data[0];

data[0]=data[last];data[last]=temp;heap_rebuild(data,0,last);voidSort::output(){inti;cout<<endl<<"for(i=0;i<len;i++){cout<<""<<dat