排序算法集成-杉杉

1、數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計說明書題 目排序算法集成學(xué) 號1376807439姓 名趙杉杉指導(dǎo)教師王麗穎日 期2015年6月28日內(nèi)蒙古科技大學(xué)課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計設(shè)計題目排序算法集成指導(dǎo)教師王麗穎時間2015.6.222015.7.2一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能3. 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計資料及參數(shù)每個學(xué)生在教師

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

3、和驗收（2天）五、評分標(biāo)準(zhǔn)1. 根據(jù)平時上機考勤、表現(xiàn)和進度，教師將每天點名和檢查2. 根據(jù)課程設(shè)計完成情況，必須有可運行的軟件。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目 錄第1章 需求分析4第2

4、章 總體設(shè)計5第3章 抽象數(shù)據(jù)類型定義63.1 排序抽象數(shù)據(jù)類型的設(shè)計6第4章 詳細設(shè)計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ǔ)上實現(xiàn)多種排序算法。要求設(shè)計函數(shù)模板來實現(xiàn)下列排序算法：v 直接插入排序v 冒泡排序v 簡單選擇排序v 希爾排序v 快速排序v 堆排序 并設(shè)計主函數(shù)測試動態(tài)數(shù)組類（或類模板），測試各排序算法的函數(shù)模板。第2章 總體設(shè)計本系統(tǒng)是輸入待排序的數(shù)據(jù)，通過人為的選擇是利用哪種

5、排序進行運算，運算之后，將排好序的結(jié)果輸出，并且可以進行多組數(shù)據(jù)的操作。系統(tǒng)功能希爾排序堆排序直接插入排序冒泡排序快速排序簡單選擇排序顯示排序結(jié)果圖2.1 主要設(shè)計思想流程圖第3章 抽象數(shù)據(jù)類型定義定義格式如下：3.1 排序抽象數(shù)據(jù)類型的設(shè)計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ù)組的第一個元素的下標(biāo)，和最后一個元素

6、的下標(biāo)。操作結(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章 詳細設(shè)計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

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

8、dataj+1,dataj+1,dataj=k.結(jié)束圖 4.4.3 冒泡排序流程圖i=1,i<len i+ 否 是temp=data 是j<i 否 j+ 是datai<dataj 否 是K=i 是K<j K- 否 是datak = datak-1dataj = temp 結(jié)束 圖4.4.4 直接插入排序流程圖 圖 4.4.5 希爾排序流程例圖i=len-1i>=0 否 i- 是構(gòu)建堆 j = 1j<=len 否temp=data0, data0=datalast, datalast=temp, heap_rebuild(data,0,last); 是 結(jié)束

9、圖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)過了兩個星期的課程設(shè)計，我體會頗多，學(xué)到很多東西。利用設(shè)計排序算法集成系統(tǒng)的機會，我加強了對數(shù)據(jù)結(jié)構(gòu)的理解，復(fù)習(xí)了自己以前的知識，提高了邏輯思考能力。在這次課程設(shè)計中，我還懂得了做程序的一些比較重要的步驟，比如總體設(shè)計、程序模塊設(shè)計、包括功能需求、用戶界面設(shè)計、程序代碼設(shè)計與分析、運行結(jié)果等。在課程設(shè)計中我遇到了一些平時做作業(yè)所沒遇

10、到的問題。在做課程設(shè)計的過程中，加深了對書本知識的理解，同時也培養(yǎng)了自己的動手能力。因為上學(xué)期做過兩次課程設(shè)計，對于課程設(shè)計有了一些經(jīng)驗了吧，從總體上來說還算比較順利，只是之前忙于準(zhǔn)備考試，之后做課程設(shè)計感覺時間有點緊，應(yīng)該是我在時間安排上有點問題吧。這次課程設(shè)計，是將這一學(xué)期學(xué)到的論知識用于了實踐，在我在實踐中得到了很多經(jīng)驗。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。在看到在自己付出了努力所做出來的成果時，我感到非常的欣慰。最后我還要感謝我的指導(dǎo)老師，感謝在我遇到問題時

11、幫我解決問題的同學(xué)，沒有你們的幫助我是不可能做好的。我以后還要更加努力，不辜負(fù)老師與家人的期望。從這段時間，我獲得了知識，學(xué)到了研究的堅持與韌性，這不僅僅是交出了一份作業(yè)，還對自己有了新的認(rèn)識，實在是難得的機遇與經(jīng)歷。附錄：程序代碼#include<iostream>#include<cstdlib>using namespace std;class Sortpublic:void input()int i,n;cout<<endl<<" 歡迎來到排序系統(tǒng)"cout<<endl<<""

12、;cout<<endl<<" 請輸入申請數(shù)組的大?。?quot;cin>>n;len = n;data = new intn;for(i = 0;i<n;i+)cout<<" 請輸入第"<<i+1<<"個數(shù)："cin>>datai;int get_len()return len;void output();void display();void sel_sort();/選擇void par_sort(int l,int r); /快排void bub_so

13、rt(); /冒泡void insert_sort(); /插入排序void 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;i<len-1;i+)k = i;for(j = i+1;j<len;j+)if(dataj<datak)k=j;if(k != i)b = datai;datai = datak;dat

14、ak = b;void Sort:par_sort(int l,int r)if (l< r) int i = l, j = r, x = datal;while (i < j)while(i < j && dataj>= x) / 從右向左找第一個小于x的數(shù)j-;if(i < j)datai+ = dataj;while(i < j && datai< x) / 從左向右找第一個大于等于x的數(shù)i+;if(i < j)dataj- = datai;datai = x; par_sort(l, i - 1); / 遞

15、歸調(diào)用par_sort(i + 1, r); void Sort:bub_sort()int i,j,k;for(i=0;i<len-1;i+)for(j=i;j<len-1;j+)if(dataj+1<dataj)k = dataj+1;dataj+1 = dataj;dataj = k;void Sort:insert_sort()int i,j,k;int temp;for(i=1;i<len;i+)temp=datai;for(j=0;j<i;j+)if(datai<dataj)for(k=i;k>j;k-)datak=datak-1;data

16、j=temp;void Sort:xier_sort()int j, temp,d;d = len / 2;while(d > 0)for ( int i = d; i < len; i+)temp = datai;j = i - d;while (j >= 0 && dataj>temp)dataj+d = dataj;j -= d;dataj + d = temp;d /= 2;void Sort:heap_rebuild(int data,int root,int size) int child=2*root+1; if(child<=siz

17、e-1) int rightChild=child+1; if(rightChild<=size-1) if(datachild<datarightChild) child=rightChild; if(dataroot<datachild) int temp=datachild; datachild=dataroot; dataroot=temp; heap_rebuild(data,child,size); void Sort:heap_sort()int i; for(i=len-1;i>=0;i-) heap_rebuild(data,i,len); int l

18、ast=len-1; for(int j=1;j<=len;j+,last-) int temp=data0; data0=datalast; datalast=temp; heap_rebuild(data,0,last); void Sort:output()int i;cout<<endl<<" 排序后的結(jié)果顯示："for(i = 0;i < len; i+)cout<<" "<<datai;cout<<endl;void Sort:display()cout<<endl<<""cout<<endl<<" 1.簡單選擇排序"cout<<endl<<" 2.快速排序"cout<<endl<<" 3.冒泡排序"cout<<endl<<" 4.直接插入排序"cout<<endl<<" 5.希爾排序"cout<<endl<<" 6.堆排序&