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

的加加:且來右親萎i

mt

請第第第

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

噩魏教魏

628

噩魏教魏

請第第第

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

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

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

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

申入入入入

An

請請請

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

是否進行其他數(shù)據(jù)排序（“其他）：圖5.8堆排序結(jié)果顯示第6章總結(jié)經(jīng)過了兩個星期的課程設(shè)計，我體會頗多，學到很多東西。利用設(shè)計排序算法集成系統(tǒng)的機會，我加強了對數(shù)據(jù)結(jié)構(gòu)的理解，復習了自己以前的知識，提高了邏輯思考能力。在這次課程設(shè)計中，我還懂得了做程序的一些比較重要的步驟，比如總體設(shè)計、程序模塊設(shè)計、包括功能需求、用戶界面設(shè)計、程序代碼設(shè)計與分析、運行結(jié)果等。在課程設(shè)計中我遇到了一些平時做作業(yè)所沒遇到的問題。在做課程設(shè)計的過程中，加深了對書本知識的理解，同時也培養(yǎng)了自己的動手能力。因為上學期做過兩次課程設(shè)計，對于課程設(shè)計有了一些經(jīng)驗了吧，從總體上來說還算比較順利，只是之前忙于準備考試，之后做課程設(shè)計感覺時間有點緊，應該是我在時間安排上有點問題吧。這次課程設(shè)計，是將這一學期學到的論知識用于了實踐，在我在實踐中得到了很多經(jīng)驗。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。在看到在自己付出了努力所做出來的成果時，我感到非常的欣慰。最后我還要感謝我的指導老師，感謝在我遇到問題時幫我解決問題的同學，沒有你們的幫助我是不可能做好的。我以后還要更加努力，不辜負老師與家人的期望。從這段時間，我獲得了知識，學到了研究的堅持與韌性，這不僅僅是交出了一份作業(yè)，還對自己有了新的認識，實在是難得的機遇與經(jīng)歷。附錄：程序代碼#include<iostream>#include<cstdlib>usingnamespacestd;classSort{public:voidinput(){歡迎來到排序系統(tǒng)”歡迎來到排序系統(tǒng)”；請輸入申請數(shù)組的大?。骸?請輸入第"<<i+1<<"個數(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)//從右向左找第一個小于x的數(shù)j--;if(i<j)data[i++]=data[j];while(i<j&&data[i]<x)//從左向右找第一個大于等于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