排序算法集成-杉杉

1、數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計(jì)說明書題 目排序算法集成學(xué) 號1376807439姓 名趙杉杉指導(dǎo)教師王麗穎日 期2015年6月28日內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)設(shè)計(jì)題目排序算法集成指導(dǎo)教師王麗穎時(shí)間2015.6.222015.7.2一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能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è)計(jì)資料及參數(shù)每個(gè)學(xué)生在教師

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

3、和驗(yàn)收（2天）五、評分標(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)確、簡練的語言敘述自己的設(shè)計(jì)和回答教師的提問六、建議參考資料1數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴(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+語言描述，殷人昆 主編，清華大學(xué)出版社 2007.6目 錄第1章 需求分析4第2章 總體設(shè)計(jì)

4、5第3章 抽象數(shù)據(jù)類型定義63.1 排序抽象數(shù)據(jù)類型的設(shè)計(jì)6第4章 詳細(xì)設(shè)計(jì)74.1 工程視圖74.2 類圖視圖74.3 函數(shù)的調(diào)用關(guān)系84.4 主程序流程圖94.5 主要算法的流程圖10第5章 測試16第6章 總結(jié)20附錄：程序代碼21第1章 需求分析排序算法集成：定義動態(tài)數(shù)組類（或類模板）以表示待排序數(shù)據(jù)，在此基礎(chǔ)上實(shí)現(xiàn)多種排序算法。要求設(shè)計(jì)函數(shù)模板來實(shí)現(xiàn)下列排序算法：v 直接插入排序v 冒泡排序v 簡單選擇排序v 希爾排序v 快速排序v 堆排序 并設(shè)計(jì)主函數(shù)測試動態(tài)數(shù)組類（或類模板），測試各排序算法的函數(shù)模板。第2章 總體設(shè)計(jì)本系統(tǒng)是輸入待排序的數(shù)據(jù)，通過人為的選擇是利用哪種排序進(jìn)行運(yùn)算

5、，運(yùn)算之后，將排好序的結(jié)果輸出，并且可以進(jìn)行多組數(shù)據(jù)的操作。系統(tǒng)功能希爾排序堆排序直接插入排序冒泡排序快速排序簡單選擇排序顯示排序結(jié)果圖2.1 主要設(shè)計(jì)思想流程圖第3章 抽象數(shù)據(jù)類型定義定義格式如下：3.1 排序抽象數(shù)據(jù)類型的設(shè)計(jì)Class Sort基本操作：void intput()操作結(jié)果：初始化動態(tài)申請的數(shù)。int get_len()操作結(jié)果：返回申請數(shù)組的大小。void display()操作結(jié)果：排序菜單的顯示。void sel_sort()操作結(jié)果：執(zhí)行簡單選擇排序。void par_sort(int l,int r)初始條件：動態(tài)數(shù)組的第一個(gè)元素的下標(biāo)，和最后一個(gè)元素的下標(biāo)。操作

6、結(jié)果：執(zhí)行快速排序。void bub_sort()操作結(jié)果：執(zhí)行冒泡排序。void insert_sort()操作結(jié)果：執(zhí)行插入排序。void xier_sort()操作結(jié)果：執(zhí)行希爾排序。void heap_rebuild(int data,int root,int size)操作結(jié)果：建立堆。void heap_sort()操作結(jié)果：執(zhí)行堆排序 ；第4章 詳細(xì)設(shè)計(jì)4.1 工程視圖圖 4.1.1 源代碼文件顯示4.2 類圖視圖圖 4.2.1 類圖視圖顯示4.3 函數(shù)的調(diào)用關(guān)系Main()清屏clearOutput()Input()六種排序函數(shù)菜單顯示圖 4.3.1 函數(shù)調(diào)用關(guān)系4.4 主程序

7、流程圖開始輸入數(shù)據(jù)菜單顯示排序選擇簡單選擇排序堆排序快速排序冒泡排序直接插入排序希爾排序是否對其他數(shù)據(jù)排序 是結(jié)束圖 4.4.1 主程序流程圖4.5 主要算法的流程圖i =0,datai+i len- 1 是K=i , j = i+1jlen j+ 否 是dataj datak 否 是K = jK=i 否b = datai,datai = datak ,datak = b 是結(jié)束圖4.4.1選擇排序流程圖圖 4.4.2 快速排序流程圖i=0,datai+i len -1j=i,jlen-1 是 否 是dataj+1datajK=dataj+1,dataj+1,dataj=k.結(jié)束圖 4.4.3

8、 冒泡排序流程圖i=1,ilen i+ 否 是temp=data 是ji 否 j+ 是dataidataj 否 是K=i 是K=0 否 i- 是構(gòu)建堆 j = 1j=len 否temp=data0, data0=datalast, datalast=temp, heap_rebuild(data,0,last); 是 結(jié)束 圖4.4.6 堆排序流程圖第5章 測試圖 5.1 開始界面圖 5.2 輸入數(shù)據(jù)及菜單顯示圖 5.3 簡單選擇排序結(jié)果顯示圖5.4 快速排序結(jié)果顯示圖5.5 冒泡排序結(jié)果顯示圖5.6 直接插入排序結(jié)果顯示圖5.7 希爾排序結(jié)果顯示圖5.8 堆排序結(jié)果顯示第6章 總結(jié)經(jīng)過了兩個(gè)

9、星期的課程設(shè)計(jì)，我體會頗多，學(xué)到很多東西。利用設(shè)計(jì)排序算法集成系統(tǒng)的機(jī)會，我加強(qiáng)了對數(shù)據(jù)結(jié)構(gòu)的理解，復(fù)習(xí)了自己以前的知識，提高了邏輯思考能力。在這次課程設(shè)計(jì)中，我還懂得了做程序的一些比較重要的步驟，比如總體設(shè)計(jì)、程序模塊設(shè)計(jì)、包括功能需求、用戶界面設(shè)計(jì)、程序代碼設(shè)計(jì)與分析、運(yùn)行結(jié)果等。在課程設(shè)計(jì)中我遇到了一些平時(shí)做作業(yè)所沒遇到的問題。在做課程設(shè)計(jì)的過程中，加深了對書本知識的理解，同時(shí)也培養(yǎng)了自己的動手能力。因?yàn)樯蠈W(xué)期做過兩次課程設(shè)計(jì)，對于課程設(shè)計(jì)有了一些經(jīng)驗(yàn)了吧，從總體上來說還算比較順利，只是之前忙于準(zhǔn)備考試，之后做課程設(shè)計(jì)感覺時(shí)間有點(diǎn)緊，應(yīng)該是我在時(shí)間安排上有點(diǎn)問題吧。這次課程設(shè)計(jì)，是將這一

10、學(xué)期學(xué)到的論知識用于了實(shí)踐，在我在實(shí)踐中得到了很多經(jīng)驗(yàn)。在這次設(shè)計(jì)過程中，體現(xiàn)出自己單獨(dú)設(shè)計(jì)模具的能力以及綜合運(yùn)用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。在看到在自己付出了努力所做出來的成果時(shí)，我感到非常的欣慰。最后我還要感謝我的指導(dǎo)老師，感謝在我遇到問題時(shí)幫我解決問題的同學(xué)，沒有你們的幫助我是不可能做好的。我以后還要更加努力，不辜負(fù)老師與家人的期望。從這段時(shí)間，我獲得了知識，學(xué)到了研究的堅(jiān)持與韌性，這不僅僅是交出了一份作業(yè)，還對自己有了新的認(rèn)識，實(shí)在是難得的機(jī)遇與經(jīng)歷。附錄：程序代碼#include#includeusing

11、 namespace std;class Sortpublic:void input()int i,n;coutendl 歡迎來到排序系統(tǒng);coutendl;coutendln;len = n;data = new intn;for(i = 0;in;i+)cout 請輸入第i+1datai;int get_len()return len;void output();void display();void sel_sort();/選擇void par_sort(int l,int r); /快排void bub_sort(); /冒泡void insert_sort(); /插入排序void

12、xier_sort();/希爾排序void heap_rebuild(int data,int root,int size); /堆得建立void heap_sort(); /堆排序private:int * data;int len;void Sort:sel_sort()int i,j,k,b;for(i=0;ilen-1;i+)k = i;for(j = i+1;jlen;j+)if(datajdatak)k=j;if(k != i)b = datai;datai = datak;datak = b;void Sort:par_sort(int l,int r)if (l r) int

13、i = l, j = r, x = datal;while (i j)while(i = x) / 從右向左找第一個(gè)小于x的數(shù)j-;if(i j)datai+ = dataj;while(i j & datai x) / 從左向右找第一個(gè)大于等于x的數(shù)i+;if(i j)dataj- = datai;datai = x; par_sort(l, i - 1); / 遞歸調(diào)用par_sort(i + 1, r); void Sort:bub_sort()int i,j,k;for(i=0;ilen-1;i+)for(j=i;jlen-1;j+)if(dataj+1dataj)k = dataj+

14、1;dataj+1 = dataj;dataj = k;void Sort:insert_sort()int i,j,k;int temp;for(i=1;ilen;i+)temp=datai;for(j=0;ji;j+)if(dataij;k-)datak=datak-1;dataj=temp;void Sort:xier_sort()int j, temp,d;d = len / 2;while(d 0)for ( int i = d; i = 0 & datajtemp)dataj+d = dataj;j -= d;dataj + d = temp;d /= 2;void Sort:he

15、ap_rebuild(int data,int root,int size) int child=2*root+1; if(child=size-1) int rightChild=child+1; if(rightChild=size-1) if(datachilddatarightChild) child=rightChild; if(dataroot=0;i-) heap_rebuild(data,i,len); int last=len-1; for(int j=1;j=len;j+,last-) int temp=data0; data0=datalast; datalast=tem

16、p; heap_rebuild(data,0,last); void Sort:output()int i;coutendl 排序后的結(jié)果顯示：;for(i = 0;i len; i+)cout datai;coutendl;void Sort:display()coutendl;coutendl 1.簡單選擇排序;coutendl 2.快速排序;coutendl 3.冒泡排序;coutendl 4.直接插入排序;coutendl 5.希爾排序;coutendl 6.堆排序;int main()int s,c;Sort p1;char i=y;p1.input();p1.display();while(i = y | i = Y)if(c=1) p1.input();p1.display();coutendls;switch(s)case 1:p1.sel_sort();p1.output();break;case 2:p1.par_sort(