數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—綜合排序

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 東華理工大學(xué)東華理工大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：課程設(shè)計(jì)題目： 綜合排序的設(shè)計(jì)綜合排序的設(shè)計(jì)學(xué)生姓名：何楊學(xué)生姓名：何楊班班 級：級：專專 業(yè)：信息與計(jì)算科學(xué)業(yè)：信息與計(jì)算科學(xué)指導(dǎo)教師：郭樹蕻指導(dǎo)教師：郭樹蕻 2014 年年 12 月月 13 日日精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 目錄目錄摘要.一、題目的內(nèi)容及要求-4二、需求分析-4三、概要設(shè)計(jì)-5四、四種排序源代碼詳細(xì)設(shè)計(jì)-5五、程序輸出的結(jié)果-10六、運(yùn)行結(jié)果及分析-12七、收獲及體會(huì)-13八、參考文獻(xiàn)-14精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)摘 要數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)

2、元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；此外討論一個(gè)數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。 排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)

3、有的算法有很多種，其中包含冒泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有其特點(diǎn)。對排序算法比較的分析可以遵循若干種不同的準(zhǔn)則，通常以排序過程所需要的算法步數(shù)作為度量，有時(shí)也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當(dāng)作一次鍵比較需要較長時(shí)間，例如，當(dāng)鍵是較長的字符串時(shí)，常以鍵比較次數(shù)作為排序算法計(jì)算時(shí)間復(fù)雜性的度量。當(dāng)排序時(shí)需要移動(dòng)記錄，且記錄都很大時(shí)，還應(yīng)該考慮記錄的移動(dòng)次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時(shí)間復(fù)雜

4、度精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)一、題目的內(nèi)容及要求一、題目的內(nèi)容及要求排序綜合排序綜合利用隨機(jī)函數(shù)產(chǎn)生 N 個(gè)隨機(jī)整數(shù)（20000 以上） ，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：(1)至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序） 。并把排序后的結(jié)果保存在不同的文件中。(2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對比） ，找出其中兩種較快的方法。(3)如果采用 4 種或 4 種以上的方法者，可適當(dāng)加分。二、需求分析二、需求分析2.1 問題描述問題描述 此次的任務(wù)要求是輸入 20000

5、 個(gè)以上的隨機(jī)整數(shù)，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。 約束：程序可由用戶自行設(shè)定排序數(shù)的個(gè)數(shù)，但排序數(shù)具體值需要由計(jì)算機(jī)生成，然后用三種以上的排序方法對隨機(jī)數(shù)組進(jìn)行排序，每一種排序方法執(zhí)行后需統(tǒng)計(jì)出數(shù)據(jù)移動(dòng)次數(shù)以判斷排序方法的對比隨機(jī)數(shù)組的執(zhí)行優(yōu)劣性。另：用戶自行算出每一種排序方法的時(shí)間復(fù)雜度與空間復(fù)雜度。 2.2 基本要求基本要求2.2.1 輸入的形式和輸入值的范圍；設(shè)定的隨機(jī)數(shù)據(jù)的范圍為 20000 以上，用戶自定義隨機(jī)數(shù)的個(gè)數(shù)n，隨機(jī)數(shù)的數(shù)據(jù)類型均為整形。2.2.2 輸出的形式；程序是以一個(gè)完整的有

6、序數(shù)組來進(jìn)行輸出。2.2.3 程序所達(dá)到的功能：將一個(gè)無序數(shù)組進(jìn)行排序隨機(jī)生成 20000 以上個(gè)隨機(jī)整數(shù)，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。分別采用以下方法實(shí)現(xiàn)上述問題求解（可精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)采用的方法有簡單排序、希爾排序、冒泡排序、快速排序這四種排序方法）。三、概要設(shè)計(jì)三、概要設(shè)計(jì)3.13.1 可排序表的抽象數(shù)據(jù)類型定義：可排序表的抽象數(shù)據(jù)類型定義：typedef int KeyType; /關(guān)鍵字為整型typedef int OtherType; /關(guān)鍵字為整型typedef structKeyType key; /關(guān)鍵字為 KeyType 型OtherType o

7、ther_data;RecordType; /定義一個(gè) RecordType 型結(jié)構(gòu)體，存放關(guān)鍵字void quicksort(RecordType a,int left,int right)/快速排序void bubbleSort(RecordType a,int length)/冒泡排序void shellSort(RecordType a,int n)/希爾排序void BinSort (RecordType r, int length)/折半插入排序void main()/主函數(shù)運(yùn)行入口四、四種排序源代碼詳細(xì)設(shè)計(jì)：四、四種排序源代碼詳細(xì)設(shè)計(jì)：4.1 快速排序模塊：快速排序模塊：void

8、 quicksort(RecordType a,int left,int right)RecordType t;int i,j,temp; if(leftright) return; temp=aleft.key; i=left; j=right; while(i!=j) while(aj.key=temp & ij)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) j-; while(ai.key=temp & ij) i+; if(ij) t=ai; ai=aj; aj=t; aleft = ai; ai.key = temp; quicksort(a,left,i-1);/繼續(xù)處理左邊的，這是

9、一個(gè)遞歸的過程 quicksort(a,i+1,right);/繼續(xù)處理右邊的，這是一個(gè)遞歸的過程 /* 快速排序算法 */ 4.2 冒泡排序模塊：冒泡排序模塊：/此處是一次冒泡排序過程，在主函數(shù)中會(huì)通過循環(huán)調(diào)用此冒泡函數(shù)過程void bubbleSort(RecordType a,int length)int i,temp; for(i=1;iai+1.key) temp = ai.key; ai.key=ai+1.key; ai+1.key=temp; /* 冒泡排序算法 */ 4.3 希爾排序模塊：希爾排序模塊：void shellSort(RecordType a,int n)int

10、i, j, temp; int gap = 0;while (gap 0) for ( i = gap; i = 0 ) & ( aj+1.key temp )aj + gap+1.key = aj+1.key;j = j - gap;aj+gap+1.key = temp;gap = ( gap - 1 ) / 3; 4.4 希爾折半插入排序模塊：希爾折半插入排序模塊：/*折半插入排序法*/void BinSort (RecordType r, int length)/*對記錄數(shù)組 r 進(jìn)行折半插入排序，length 為數(shù)組的長度*/int i,j;RecordType x;int low,

11、high,mid;for ( i=2; i=length ; +i ) x= ri;low=1; high=i-1;while (low=high ) /* 確定插入位置*/ mid=(low+high) / 2;if ( x.key= low; -j ) rj+1= rj; /* 記錄依次向后移動(dòng) */ rlow=x; /* 插入記錄 */ 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)/*BinSort*/4.5 主函數(shù)模塊：主函數(shù)模塊：void main()int n,i,j,t; char b; bool q=false;RecordType a40000; while(1) printf

12、(nn);printf( * 綜 合 排 序*nn); printf( *菜 單*nn); printf( * = * n); printf( * 1. 讀 取 待排序長度 * n); printf( * 2. 產(chǎn)生隨機(jī)數(shù)并輸出 * n); printf( * 3. 采用快速排序法排序 * n); printf( * 4. 采用冒泡排序法排序 * n); printf( * 5. 采用希爾排序法排序 * n); printf( * 6. 采用折半插入排序法排序 * n); printf( * 7. 輸 出 * n);printf( * 0. 退 出 系 統(tǒng) * n);printf( * - *

13、 n); printf( 請輸入你要進(jìn)行的操作); b = getch(); switch(b) case 1: printf(%cn,b);精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)printf(請輸入待排序記錄的長度：);scanf(%d,&n);break; case 2:printf(%cn,b);srand( (unsigned)time( NULL );printf(下面隨機(jī)生成%d 個(gè)數(shù)字存儲(chǔ)在數(shù)組中n,n);for(i=1;i=n;i+)ai.key = rand()%20000;printf(%dt,ai.key);if(i%100=0)printf(n);printf(n)

14、;break;case 3:printf(%cn,b);printf(n-快速排序結(jié)束-nn);quicksort(a,1,n);q=true;break;case 4:printf(%cn,b);for(i=0;in-1;i+)bubbleSort(a,n-i);printf(n-冒泡排序結(jié)束-nn);q=true;break; case 5:printf(%cn,b);printf(n-希爾排序結(jié)束-nn);shellSort(a,n);q=true;break; case 6:printf(%cn,b);BinSort(a,n);printf(n-折半插入排序結(jié)束-nn);q=true;

15、break; 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)case 7:printf(%cn,b);if(q)printf(n-排序后輸出-n);for(i=1;i=n;i+)printf(%dt,ai.key);if(i%100=0)printf(n); elseprintf(n * = * n); printf( * 您未對待排序數(shù)據(jù)排序 * n); printf( * 請重新選擇排序的序號 * n); printf( * - * n);break; case 0:printf(%cn,b);printf(n 感謝使用綜合排序程序n 按任意鍵退出.n);return;break; defau

16、lt:printf(輸入錯(cuò)誤請重新輸入nn); 五、程序輸出的結(jié)果：五、程序輸出的結(jié)果：5.1 輸入和輸出：輸入和輸出：(1)主函數(shù)運(yùn)行的輸出結(jié)果：精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)(2)選擇 1，讀取待排序長度（這里以 20000 為例）：(3)選擇 2，產(chǎn)生隨機(jī)數(shù)并輸出：(4)選擇 3，采用快速排序法排序：精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)（選擇 4、5、6 的其他排序法的輸出雷同，此處就不再重復(fù)）(5)選擇 7，輸出排序結(jié)果：六、運(yùn)行結(jié)果及分析六、運(yùn)行結(jié)果及分析6.1 各算法的比較方法各算法的比較方法1.穩(wěn)定性比較 折半插入排序、冒泡排序是穩(wěn)定的 希爾排序、快速排序是不穩(wěn)

17、定的2.時(shí)間復(fù)雜性比較 折半插入排序、冒泡排序的時(shí)間復(fù)雜性為 O(n2) 其它非線形排序的時(shí)間復(fù)雜性為 O(nlog2n)3.輔助空間的比較精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 線形排序的輔助空間為 O(n),其它排序的輔助空間為 O(1);4.其它比較插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時(shí)，這種排序能達(dá)到較快的速度。反而在這種情況下，快速排序反而慢了。當(dāng) n 較小時(shí)，對穩(wěn)定性不作要求時(shí)宜用選擇排序，對穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。當(dāng) n 較大時(shí)，關(guān)鍵字元素比較隨機(jī)，對穩(wěn)定性沒要求宜用快速排序。七、收獲及體會(huì)七、收獲及體會(huì)根據(jù)四種排序法的基礎(chǔ)理論實(shí)際性模仿和編寫算

18、法程序，很是困難，算法是程序的靈魂，數(shù)據(jù)結(jié)構(gòu)確是算法的基礎(chǔ)，但是不斷的實(shí)踐也是一種進(jìn)步的好途徑。這次課程設(shè)計(jì)主要是對基礎(chǔ)知識的靈活應(yīng)用，這就讓我進(jìn)一步提高了對數(shù)結(jié)構(gòu)知識的鞏固。這次設(shè)計(jì)的完成，困難是少不了的，還有很多其它的難題讓我都不知道所措，但是通過努力最終解決他們讓我體會(huì)到成就感，更重要的是我的能力在實(shí)踐中得到了提升和優(yōu)化，特別是對常用的排序算法的應(yīng)用，這對我以后從事軟件應(yīng)用程序開發(fā)是有很大的幫助的。這次課程設(shè)計(jì)的心得體會(huì)通過實(shí)習(xí)我的收獲如下 1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。3、通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程