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

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程設(shè)計(jì)題目： 綜合排序的設(shè)計(jì)</p><p>　　2014年 12 月 13 日</p><p><b>　　目錄</b></p><p><b>　　摘要2</b></p><p&

2、gt;　　一、題目的內(nèi)容及要求-------------------------------------------------------------------------------4</p><p>　　二、需求分析--------------------------------------------------------------------------------------------4<

3、;/p><p>　　三、概要設(shè)計(jì)--------------------------------------------------------------------------------------------5</p><p>　　四、四種排序源代碼詳細(xì)設(shè)計(jì)-----------------------------------------------------------------

4、-----5</p><p>　　五、程序輸出的結(jié)果---------------------------------------------------------------------------------10</p><p>　　六、運(yùn)行結(jié)果及分析-------------------------------------------------------------------

5、--------------12</p><p>　　七、收獲及體會(huì)---------------------------------------------------------------------------------------13</p><p>　　八、參考文獻(xiàn)--------------------------------------------------------

6、-----------------------------------14</p><p><b>　　摘 要</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的。對(duì)數(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)

7、算才有意義。在許多類型的程序的設(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ì)反過來(lái)，我們根據(jù)特定算法來(lái)選擇數(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)有的算法有很多種，其中包含冒泡排序，直接插入排序，簡(jiǎn)單

8、選擇排序，希爾排序，快速排序，堆排序等，各有其特點(diǎn)。對(duì)排序算法比較的分析可以遵循若干種不同的準(zhǔn)則，通常以排序過程所需要的算法步數(shù)作為度量，有時(shí)也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當(dāng)作一次鍵比較需要較長(zhǎng)時(shí)間，例如，當(dāng)鍵是較長(zhǎng)的字符串時(shí)，常以鍵比較次數(shù)作為排序算法計(jì)算時(shí)間復(fù)雜性的度量。當(dāng)排序時(shí)需要移動(dòng)記錄，且記錄都很大時(shí)，還</p><p>　　關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時(shí)間復(fù)雜度</p&

9、gt;<p>　　一、題目的內(nèi)容及要求</p><p><b>　　排序綜合</b></p><p>　　利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。</p><p><b>　　要求：</b></p><p>　　(1)至少采用三種方法實(shí)現(xiàn)上述問題求

10、解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。</p><p>　　(2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。</p><p>　　(3)如果采用4種或4種以上的方法者，可適當(dāng)加分。</p><p><b>　　二、需

11、求分析</b></p><p>　　2.1 問題描述 </p><p>　　此次的任務(wù)要求是輸入20000個(gè)以上的隨機(jī)整數(shù)，對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。 約束：程序可由用戶自行設(shè)定排序數(shù)的個(gè)數(shù)，但排序數(shù)具體值需要由計(jì)算機(jī)生成，然后用三種以上的排序方法對(duì)隨機(jī)數(shù)組進(jìn)行排序，每一種

12、排序方法執(zhí)行后需統(tǒng)計(jì)出數(shù)據(jù)移動(dòng)次數(shù)以判斷排序方法的對(duì)比隨機(jī)數(shù)組的執(zhí)行優(yōu)劣性。另：用戶自行算出每一種排序方法的時(shí)間復(fù)雜度與空間復(fù)雜度。 </p><p><b>　　2.2 基本要求</b></p><p>　　2.2.1輸入的形式和輸入值的范圍；</p><p>　　設(shè)定的隨機(jī)數(shù)據(jù)的范圍為20000以上，用戶自定義隨機(jī)數(shù)的個(gè)數(shù)n，隨機(jī)數(shù)的數(shù)據(jù)類

13、型均為整形。</p><p>　　2.2.2輸出的形式；</p><p>　　程序是以一個(gè)完整的有序數(shù)組來(lái)進(jìn)行輸出。</p><p>　　2.2.3程序所達(dá)到的功能：</p><p>　　將一個(gè)無(wú)序數(shù)組進(jìn)行排序隨機(jī)生成20000以上個(gè)隨機(jī)整數(shù)，對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。分別采用以下方法實(shí)現(xiàn)上述問題求解（可采用的方法有簡(jiǎn)單排序、希爾排序、冒

14、泡排序、快速排序這四種排序方法）。</p><p><b>　　三、概要設(shè)計(jì)</b></p><p>　　3.1可排序表的抽象數(shù)據(jù)類型定義：</p><p>　　typedef int KeyType; //關(guān)鍵字為整型</p><p>　　typedef int OtherType; //關(guān)鍵字為整型</p>

15、;<p>　　typedef struct</p><p><b>　　{</b></p><p>　　KeyType key; //關(guān)鍵字為KeyType型</p><p>　　OtherType other_data;</p><p>　　}RecordType; //定義一個(gè)RecordType型結(jié)構(gòu)

16、體，存放關(guān)鍵字</p><p>　　void quicksort(RecordType a[],int left,int right)//快速排序</p><p>　　void bubbleSort(RecordType a[],int length)//冒泡排序</p><p>　　void shellSort(RecordType a[],int n)//

17、希爾排序</p><p>　　void BinSort (RecordType r[], int length)//折半插入排序</p><p>　　void main()//主函數(shù)運(yùn)行入口</p><p>　　四、四種排序源代碼詳細(xì)設(shè)計(jì)：</p><p>　　4.1快速排序模塊：</p><p>　　void

18、 quicksort(RecordType a[],int left,int right)</p><p><b>　　{</b></p><p>　　RecordType t;</p><p>　　int i,j,temp;</p><p>　　if(left>right)</p><p>

19、;<b>　　return;</b></p><p>　　temp=a[left].key;</p><p><b>　　i=left;</b></p><p><b>　　j=right;</b></p><p>　　while(i!=j)</p><p&

20、gt;<b>　　{</b></p><p>　　while(a[j].key>=temp && i<j)</p><p><b>　　j--;</b></p><p>　　while(a[i].key<=temp && i<j)</p><p&g

21、t;<b>　　i++;</b></p><p><b>　　if(i<j)</b></p><p><b>　　{</b></p><p><b>　　t=a[i];</b></p><p>　　a[i]=a[j];</p><

22、p><b>　　a[j]=t;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　a[left] = a[i];</p><p>　　a[i].key = temp;</p><p>　　q

23、uicksort(a,left,i-1);//繼續(xù)處理左邊的，這是一個(gè)遞歸的過程</p><p>　　quicksort(a,i+1,right);//繼續(xù)處理右邊的，這是一個(gè)遞歸的過程</p><p>　　} /* 快速排序算法 */</p><p>　　4.2冒泡排序模塊：</p><p>　　//此處是一次冒泡排序過程，在主函數(shù)中會(huì)通過

24、循環(huán)調(diào)用此冒泡函數(shù)過程</p><p>　　void bubbleSort(RecordType a[],int length)</p><p><b>　　{</b></p><p>　　int i,temp;</p><p>　　for(i=1;i<length;i++)</p><p>

25、;<b>　　{</b></p><p>　　if(a[i].key>a[i+1].key)</p><p><b>　　{</b></p><p>　　temp = a[i].key;</p><p>　　a[i].key=a[i+1].key;</p><p>　　

26、a[i+1].key=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　}/* 冒泡排序算法 */ </p><p>　　4.3希爾排序模塊：</p><p>　　void shellSort(RecordType

27、 a[],int n)</p><p><b>　　{</b></p><p>　　int i, j, temp; </p><p>　　int gap = 0;</p><p>　　while (gap<=n)//根據(jù)待排序的個(gè)數(shù)生成合適的步長(zhǎng)，gap是步長(zhǎng)</p><p><b&g

28、t;　　{</b></p><p>　　gap = gap * 3 + 1;</p><p><b>　　} </b></p><p>　　while (gap > 0) </p><p><b>　　{</b></p><p>　　for ( i = ga

29、p; i < n; i++ )</p><p><b>　　{</b></p><p>　　j = i - gap;</p><p>　　temp = a[i+1].key; </p><p>　　while (( j >= 0 ) && ( a[j+1].key >

30、 temp ))</p><p><b>　　{</b></p><p>　　a[j + gap+1].key = a[j+1].key;</p><p>　　j = j - gap;</p><p><b>　　}</b></p><p>　　a[j+gap+1].key

31、= temp;</p><p><b>　　}</b></p><p>　　gap = ( gap - 1 ) / 3;</p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　4.4希爾折半插入排序模塊：&

32、lt;/p><p>　　/*折半插入排序法*/</p><p>　　void BinSort (RecordType r[], int length)</p><p>　　/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長(zhǎng)度*/</p><p><b>　　{</b></p><p>

33、<b>　　int i,j;</b></p><p>　　RecordType x;</p><p>　　int low,high,mid;</p><p>　　for ( i=2; i<=length ; ++i ) </p><p><b>　　{</b></p><

34、p><b>　　x= r[i];</b></p><p>　　low=1; high=i-1;</p><p>　　while (low<=high ) /* 確定插入位置*/ </p><p><b>　　{</b></p><p>　　mid=(l

35、ow+high) / 2;</p><p>　　if ( x.key< r[mid].key ) </p><p>　　high=mid-1;</p><p><b>　　else </b></p><p>　　low=mid+1;</p><p><b>　　}<

36、;/b></p><p>　　for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j]; /* 記錄依次向后移動(dòng) */ </p><p>　　r[low]=x; /* 插入記錄 */ </p><p>

37、;<b>　　}</b></p><p>　　}/*BinSort*/</p><p><b>　　4.5主函數(shù)模塊：</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　int n,i,j,t

38、; </p><p><b>　　char b; </b></p><p>　　bool q=false;</p><p>　　RecordType a[40000];</p><p><b>　　while(1) </b></p><p><b>　　{ <

39、;/b></p><p>　　printf("\n\n");</p><p>　　printf(" ************** 綜合排序*****************************\n\n"); </p><p>　　printf(" *************

40、********菜 單***************************\n\n"); </p><p>　　printf(" * ======================================================= * \n"); </p><p>　　printf(" *

41、 1. 讀 取 待排序長(zhǎng)度 * \n"); </p><p>　　printf(" * 2. 產(chǎn)生隨機(jī)數(shù)并輸出 * \n"); </p><p>　　printf(" *

42、 3. 采用快速排序法排序 * \n"); </p><p>　　printf(" * 4. 采用冒泡排序法排序 * \n"); </p><p>　　printf(" *

43、 5. 采用希爾排序法排序 * \n"); </p><p>　　printf(" * 6. 采用折半插入排序法排序 * \n"); </p><p>　　printf(" * 7.

44、 輸 出 * \n");</p><p>　　printf(" * 0. 退 出 系 統(tǒng) * \n");</p><p>　　printf(" * --------------

45、----------------------------------------- * \n");</p><p>　　printf(" 請(qǐng)輸入你要進(jìn)行的操作"); </p><p>　　b = getch(); </p><p>　　switch(b) </p><p><b>　　

46、{ </b></p><p>　　case '1': </p><p>　　printf("%c\n",b);</p><p>　　printf("請(qǐng)輸入待排序記錄的長(zhǎng)度：");</p><p>　　scanf("%d",&n);break; &

47、lt;/p><p><b>　　case '2':</b></p><p>　　printf("%c\n",b);</p><p>　　srand( (unsigned)time( NULL ));</p><p>　　printf("下面隨機(jī)生成%d個(gè)數(shù)字存儲(chǔ)在數(shù)組中\(zhòng)n&qu

48、ot;,n);</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　a[i].key = rand()%20000;</p><p>　　printf("%d\t",a[i].key);</p><p>　　

49、if(i%100==0)</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　break;</b></p><p><

50、b>　　case '3':</b></p><p>　　printf("%c\n",b);</p><p>　　printf("\n-----------------快速排序結(jié)束-------------------\n\n");</p><p>　　quicksort(a,1,n

51、);</p><p>　　q=true;break;</p><p><b>　　case '4':</b></p><p>　　printf("%c\n",b);</p><p>　　for(i=0;i<n-1;i++)</p><p><b>

52、;　　{</b></p><p>　　bubbleSort(a,n-i);</p><p><b>　　}</b></p><p>　　printf("\n-----------------冒泡排序結(jié)束-------------------\n\n");</p><p>　　q

53、=true;break; </p><p><b>　　case '5':</b></p><p>　　printf("%c\n",b);</p><p>　　printf("\n-----------------希爾排序結(jié)束-------------------\n\n");

54、</p><p>　　shellSort(a,n);</p><p>　　q=true;break; </p><p><b>　　case '6':</b></p><p>　　printf("%c\n",b);</p><p>　　BinSort(a,n)

55、;</p><p>　　printf("\n-----------------折半插入排序結(jié)束-------------------\n\n");</p><p>　　q=true;break; </p><p><b>　　case '7':</b></p><p>　　

56、printf("%c\n",b);</p><p><b>　　if(q)</b></p><p><b>　　{</b></p><p>　　printf("\n-----------------排序后輸出-------------------\n");</p&g

57、t;<p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　printf("%d\t",a[i].key);</p><p>　　if(i%100==0)</p><p>　　printf("\n");<

58、/p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("\n * =

59、====================================================== * \n"); </p><p>　　printf(" * 您未對(duì)待排序數(shù)據(jù)排序 * \n"); </p><p>　　printf(" *

60、 請(qǐng)重新選擇排序的序號(hào) * \n"); </p><p>　　printf(" * ------------------------------------------------------- * \n");</p><p><b>　　}</b>&

61、lt;/p><p><b>　　break; </b></p><p><b>　　case '0':</b></p><p>　　printf("%c\n",b);</p><p>　　printf("\n 感謝使用綜合排序程序\n

62、 按任意鍵退出......\n");</p><p>　　return;break; </p><p>　　default:printf("輸入錯(cuò)誤請(qǐng)重新輸入\n\n");</p><p><b>　　}</b></p><p><b>　　} </b></p

63、><p><b>　　}</b></p><p>　　五、程序輸出的結(jié)果：</p><p><b>　　5.1輸入和輸出：</b></p><p>　　(1)主函數(shù)運(yùn)行的輸出結(jié)果：</p><p>　　(2)選擇1，讀取待排序長(zhǎng)度（這里以20000為例）：</p>

64、<p>　　(3)選擇2，產(chǎn)生隨機(jī)數(shù)并輸出：</p><p>　　(4)選擇3，采用快速排序法排序：</p><p>　?。ㄟx擇4、5、6的其他排序法的輸出雷同，此處就不再重復(fù)）</p><p>　　(5)選擇7，輸出排序結(jié)果：</p><p><b>　　六、運(yùn)行結(jié)果及分析</b></p>&l

65、t;p>　　6.1各算法的比較方法</p><p><b>　　1.穩(wěn)定性比較</b></p><p>　　折半插入排序、冒泡排序是穩(wěn)定的</p><p>　　希爾排序、快速排序是不穩(wěn)定的</p><p><b>　　2.時(shí)間復(fù)雜性比較</b></p><p>　　折半

66、插入排序、冒泡排序的時(shí)間復(fù)雜性為O(n2)</p><p>　　其它非線形排序的時(shí)間復(fù)雜性為O(nlog2n)</p><p><b>　　3.輔助空間的比較</b></p><p>　　線形排序的輔助空間為O(n),其它排序的輔助空間為O(1);</p><p><b>　　4.其它比較</b>&

67、lt;/p><p>　　插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時(shí)，這種排序能達(dá)到較快的速度。</p><p>　　反而在這種情況下，快速排序反而慢了。</p><p>　　當(dāng)n較小時(shí)，對(duì)穩(wěn)定性不作要求時(shí)宜用選擇排序，對(duì)穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。</p><p>　　當(dāng)n較大時(shí)，關(guān)鍵字元素比較隨機(jī)，對(duì)穩(wěn)定性沒要求宜用快速排

68、序。</p><p><b>　　七、收獲及體會(huì)</b></p><p>　　根據(jù)四種排序法的基礎(chǔ)理論實(shí)際性模仿和編寫算法程序，很是困難，算法是程序的靈魂，數(shù)據(jù)結(jié)構(gòu)確是算法的基礎(chǔ)，但是不斷的實(shí)踐也是一種進(jìn)步的好途徑。這次課程設(shè)計(jì)主要是對(duì)基礎(chǔ)知識(shí)的靈活應(yīng)用，這就讓我進(jìn)一步提高了對(duì)數(shù)結(jié)構(gòu)知識(shí)的鞏固。這次設(shè)計(jì)的完成，困難是少不了的，還有很多其它的難題讓我都不知道所措，但是通

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

70、計(jì)方法。4、通過課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。根據(jù)我在實(shí)習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點(diǎn)： 1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有</p><p><b>　　八、參考文獻(xiàn)</b></p><p>　　[1] 啊哈磊，《啊哈！算法》