數(shù)據(jù)結構課程設計報告--排序

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：19 大?。?56.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩18頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結構　　課程設計報告　　題目　　排序　　需求分析<

2、/p>　　2.1、選題要求　?。?）設計一個菜單，格式如下：　　1.直接插入排序　　2.希爾排序　　3.冒泡排序

3、　　4快速排序　　5選擇排序　　6.堆排序　　7.退出程序

4、　?。?）選擇不同的菜單進行相應的排序，并給出排序的關鍵字序列。　　2.2、選題的意義及背景　　排序是計算機程序設計中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。　　排序的方法很多，但是就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不

5、同的環(huán)境下使用。如果按排序過程中依據(jù)的不同原則對內部排序方法進行分類，則大致可分為插入排序，交換排序，選擇排序，歸并排序和記數(shù)排序等五類。　　此實驗通過對直插排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序這幾種內部排序算法進行比較，能使我們更好的掌握這些排序的基本思想及排序算法。通過該題目的設計過程，可以加深理解各種數(shù)據(jù)結構的邏輯結構、存儲結構及相應上運算的實現(xiàn)，進一步理解和熟練掌握課本中

6、所學的各種數(shù)據(jù)結構，學會如何把學到的知識用于解決實際問題，培養(yǎng)我們的動手能力。　　2.3、課程設計目標　　本課程設計對以下內部排序算法進行比較：直插排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。　　待排序表的元素關鍵字為整數(shù)，用隨機不同的測試數(shù)據(jù)做測試比較。比較的指標為關鍵字的比較次數(shù)、關鍵字的移動次數(shù)和

7、所用時間。最后對這些內部排序算法進行性能分析。　　概要設計　　3.1、原始數(shù)據(jù)　　用戶輸入記錄的個數(shù)，數(shù)據(jù)由隨機數(shù)產生器生成。　　3.2、輸出數(shù)據(jù)</p

8、>　　產生的隨機數(shù)分別用直插排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。這些排序方法進行排序，輸出關鍵字的比較次數(shù)、移動次數(shù)和所用時間。　　3.3、數(shù)據(jù)處理　　3.3、存儲結構　　typedef st

9、ruct{　　int key;　　} RedType;　　詳細設計　　4.1、各排序算法的基本思想　　1）直接插入排序

10、;　　每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個數(shù),然后把第二個數(shù)按大小插入到有序表中; 第二趟把第三個數(shù)據(jù)與前兩個數(shù)從后向前掃描，把第三個數(shù)按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。　　2）希爾排序

11、　　先取一個正整數(shù)d1<n，把所有序號相隔d1的數(shù)組元素放一組，組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止；　　3）冒泡排序　　冒泡排序的基本概念是：依次比較相鄰的兩個數(shù)，將大數(shù)放在前面，小數(shù)放在后面。即首先比較第1個和第

12、2個數(shù)，將大數(shù)放前，小數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將大數(shù)放前，小數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將大數(shù)放前，小數(shù)放后，此時第一趟結束，在最后的數(shù)必是所有數(shù)中的最小數(shù)。重復以上過程，仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再大于第2個數(shù)），將大數(shù)放前，小數(shù)放后，一直比較到最小數(shù)前的一對相鄰數(shù)，將大數(shù)放前，小數(shù)放后，第二趟結束，在倒數(shù)第二個數(shù)中得到一個新的最小數(shù)。如此下去，直至最終完成排序。由

13、于在排序過程中總是大數(shù)往前放，小數(shù)往后放，相當于氣泡往上升，所以稱作冒泡排序。　　4）快速排序　　首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，如果小于兩個，則直接退出程序。如果有超過兩個以上的數(shù)據(jù)，就選擇一個分割點將數(shù)據(jù)分成兩個部分，小于分割點的數(shù)據(jù)放在一組，其余的放在另一組，然后分別對兩組數(shù)據(jù)排序；<

14、p>　　5）選擇排序　?。?）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素（2）若它不是這組元素中的第個元素，則將它與這一組元素中的第一個元素對調；（3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執(zhí)行第（1）（2）步，直到剩余元素只有一個為止。<b

15、>　　6) 堆排序　　堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素；堆的定義: N個元素的序列K1，K2，K3，...，Kn.稱為堆，當且僅當該序列滿足特性：Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])；&

16、lt;b>　　4.2、程序代碼　　4.2.1 函數(shù)聲明　　#include <stdio.h>　　#include <iostream.h>　　#include <stdlib.h>&l

17、t;p>　　#include <string.h>　　#include <time.h>　　#include <windows.h>　　#include <winbase.h>　　#include <iomani

18、p.h>　　#define MAXSIZE 80　　#define TRUE 1　　#define FALSE 0　　typedef int BOOL;　　typedef struct{<p&g

19、t;　　int key;　　} RedType;　　class LinkList　　{　　public:　　RedT

20、ype r[MAXSIZE+1];　　int Length;　　int CmpNum, ChgNum;　　LinkList();　　bool LT(int i, int j);　　void Display();

21、　　void Insert( int dk);　　void ShellSort();　　int Partition( int low, int high);　　void QSort( int low, int high);　　void QuickSo

22、rt();　　void HeapAdjust( int s, int m);　　void HeapSort();　　void BubbleSort();　　int SelectMinKey( int k);　　void SelSo

23、rt();　　void SelectSort();　　}; 　　LinkList::LinkList(){　　int i;　　for (i = 0; i

24、<= MAXSIZE; i++)　　r[i].key = rand()%80;　　Length=MAXSIZE+1;　　CmpNum=0;　　ChgNum=0;<

25、;p>　　}　　bool LinkList::LT(int i, int j){　　(CmpNum)++;　　if (i < j)　　return TRUE;

26、else　　return FALSE;　　}　　void LinkList::Display()　　{　　int j

27、;　　for(int i=0;i<=MAXSIZE;i++)　　{　　cout<<setw(6)<<r[i].key;　　if(++j%10==0)<p&

28、gt;　　cout<<endl;　　}　　cout<<endl;　　}　　4.2.2六種排序算法代碼　　//插入

29、排序　　void LinkList::Insert(int dk){　　int i, j;　　RedType Temp;　　for (i = dk; i < Length; i++)&

30、lt;p>　　{　　if (LT(r[i].key, r[i - dk].key))　　{　　memcpy(&Temp, &r[i], sizeof(RedType));

31、for (j = i - dk; j >= 0 && LT(Temp.key, r[j].key); j -= dk)　　{　　(ChgNum)++;　　memcpy(&r[j + dk], &r[j], sizeof(RedType))

32、;　　}　　memcpy(&r[j + dk], &Temp, sizeof(RedType));　　}　　}<

33、p>　　}　　//希爾排序　　void LinkList::ShellSort()　　{　　int t=Length+1;<

34、;p>　　do{　　t=t/3+1;　　Insert( t);　　}　　while(t>1);<b

35、>　　}　　//快速排序　　int LinkList::Partition(int low, int high){　　RedType Temp;　　int PivotKey;<p

36、>　　memcpy(&Temp, &r[low], sizeof(RedType));　　PivotKey = r[low].key;　　while (low < high){　　while (low < high &&r[high].key >= Pivo

37、tKey){　　high--;　　(CmpNum)++;　　}　　(ChgNum)++;　　memcpy(&r[low], &r[high

38、], sizeof(RedType));　　while (low < high && r[low].key <= PivotKey){　　low++;　　(CmpNum)++;　　}<

39、;/b>　　(ChgNum)++;　　memcpy(&r[high], &r[low], sizeof(RedType));　　}　　memcpy(&r[low], &Temp, sizeof(R

40、edType));　　return low;　　}　　void LinkList::QSort( int low, int high){　　int PivotLoc = 0;　　if (low

41、 < high){　　PivotLoc = Partition( low, high);　　QSort(low, PivotLoc - 1);　　QSort( PivotLoc + 1, high);　　}

42、　　}　　void LinkList::QuickSort(){　　QSort(0, Length - 1);　　}　　//堆排序<

43、/p>　　void LinkList::HeapAdjust(int s, int m){　　RedType Temp;　　int j = 0;　　s++;　　memcpy(&Temp, &

44、r[s - 1], sizeof(RedType));　　for (j = 2 * s; j <= m; j *= 2){　　if (j < m && LT(r[j - 1].key, r[j].key))　　++j;<

45、;p>　　if (!LT(Temp.key, r[j - 1].key))　　break;　　(ChgNum)++;　　memcpy(&r[s - 1], &r[j - 1], sizeof(RedType));

46、　　s = j;　　}　　memcpy(&r[s - 1], &Temp, sizeof(RedType));　　}　　void LinkLi

47、st::HeapSort(){　　int i = 0;　　RedType Temp;　　for (i = Length / 2-1; i >= 0; i--)　　HeapAdjust(i, Length);　　for (i

48、= Length; i > 1; i--){　　memcpy(&Temp, &r[0], sizeof(RedType));　　(ChgNum)++;　　memcpy(&r[0], &r[i - 1], sizeof(RedType));<p&g

49、t;　　memcpy(&r[i - 1], &Temp, sizeof(RedType));　　HeapAdjust( 0, i - 1);　　}　　}　　//冒

50、泡排序　　void LinkList::BubbleSort(){　　int i, j;　　RedType temp;　　for (i = 1; i <= MAXSIZE; i++){

51、　　for (j = 1; j <= MAXSIZE - i; j++){　　if (!LT(r[j].key, r[j + 1].key)){　　(ChgNum)++;　　memcpy(&temp, &r[j], sizeof(RedType));

52、　　memcpy(&r[j], &r[j + 1], sizeof(RedType));　　memcpy(&r[j + 1], &temp, sizeof(RedType));　　}　　}

53、　　}　　}　　//選擇排序　　int LinkList::SelectMinKey( int i)

54、;　　{　　int Min = i;　　for (int k=i; k < Length; k++)　　{　　if (!LT(r[Min].key, r[k].key))<p&g

55、t;　　Min = k;　　}　　return Min;　　}　　void LinkList::SelSort(){

56、　　int i, j;　　RedType temp;　　for (i = 0; i < Length; i++){　　j = SelectMinKey( i);　　if (i != j){

57、;　　(ChgNum)++;　　memcpy(&temp, &r[i], sizeof(RedType));　　memcpy(&r[i], &r[j], sizeof(RedType));　　memcpy(&r[j], &temp, sizeof(RedType))

58、;　　}　　}　　}　　4.2.3 排序算法的選擇　　void LinkList::SelectSort(){<

59、;/p>　　cout<<" 歡迎來到排序綜合系統(tǒng) "<<endl;　　cout<<"============================================ ="<<endl;<

60、p>　　cout<<" 菜單 "<<endl;　　cout<<"============================================= "<<endl;

61、　　cout<<"1. 直接插入排序 "<<endl;　　cout<<"2. 希爾排序 "<<endl;　　cout

62、<<"3. 冒泡排序 "<<endl;　　cout<<"4. 快速排序 "<<endl;　　cout<

63、<"5. 選擇排序 "<<endl;　　cout<<"6. 堆排序 "<<endl;　　cout<<

64、;"7. 退出程序 "<<endl;　　cout<<"請選擇需要進行的操作: "<<endl;　　}&

65、lt;/p>　　void LinkList::AllAbove(){　　int TempTime;　　int SpendTime;　　cout<<endl;　　LinkList();　　co

66、ut<<"插入排序:"<<endl;　　TempTime = (int)GetTickCount();　　Insert( 1);　　SpendTime = (int)GetTickCount() - TempTime;　　cou

67、t<<endl;　　cout<<"CompareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<Spend

68、Time<<"ms"<<endl;　　LinkList();//隨機數(shù)列復位　　cout<<endl;　　cout<<"希爾排序:"<<endl;　　TempTime =

69、(int)GetTickCount();　　ShellSort();　　SpendTime = (int)GetTickCount() - TempTime;　　cout<<endl;　　cout<<"CompareNumber=&quo

70、t;<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;　　LinkList();

71、//隨機數(shù)列復位　　cout<<endl;　　cout<<"快速排序:"<<endl;　　TempTime = (int)GetTickCount();　　QuickSort();<

72、;p>　　SpendTime = (int)GetTickCount() - TempTime;　　cout<<endl;　　cout<<"CompareNumber="<<CmpNum<<" "<<"ChageNumber="&

73、lt;<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;　　LinkList();//隨機數(shù)列復位　　cout<<endl;<p&g

74、t;　　cout<<"堆排序:"<<endl;　　TempTime = (int)GetTickCount();　　HeapSort();　　SpendTime = (int)GetTickCount() - TempTime;

75、　　cout<<endl;　　cout<<"CompareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<

76、SpendTime<<"ms"<<endl;　　LinkList();//隨機數(shù)列復位　　cout<<endl;　　cout<<"冒泡排序:"<<endl;　　Tem

77、pTime = (int)GetTickCount();　　BubbleSort();　　SpendTime = (int)GetTickCount() - TempTime;　　cout<<endl;　　cout<<"CompareNu

78、mber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;　　Li

79、nkList();//隨機數(shù)列復位　　cout<<endl;　　cout<<"選擇排序:"<<endl;　　TempTime = (int)GetTickCount();　　SelSort();</p&g

80、t;　　SpendTime = (int)GetTickCount() - TempTime;　　cout<<endl;　　cout<<"CompareNumber="<<CmpNum<<" "<<"ChageNumber=

81、"<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;　　}　　4.2.4主函數(shù)程序代碼<p&g

82、t;　　void main(){　　int select = 0;　　int SpendTime = 0;　　int TempTime;　　do{　　LinkList L;

83、　　L.SelectSort();　　cin>>select;　　switch (select)　　{　　case 1:

84、　　cout<<"插入排序前:"<<endl;　　L.Display();　　cout<<"插入排序后:"<<endl; 　　TempTime = (int)GetTickCount();<p&

85、gt;　　L.Insert(1);　　SpendTime = (int)GetTickCount() - TempTime;　　L.Display();　　cout<<endl;　　cout<<"比較次數(shù)="<<L.

86、CmpNum<<" "<<"關鍵字移動次數(shù)="<<L.ChgNum<<" "<<"所需時間="<<SpendTime<<"ms"<<endl;　　break;<

87、;/p>　　case 2:　　cout<<"希爾排序前:"<<endl;　　L.Display();　　cout<<"希爾排序后:"<<endl;</p&

88、gt;　　cout<<endl;　　TempTime = (int)GetTickCount();　　L.ShellSort();　　SpendTime = (int)GetTickCount() - TempTime;　　L.Displ

89、ay();　　cout<<endl;　　cout<<"比較次數(shù)="<<L.CmpNum<<" "<<"關鍵字移動次數(shù)="<<L.ChgNum<<" "<<"所需時間=&q

90、uot;<<SpendTime<<"ms"<<endl;　　break;　　case 3:　　cout<<"冒泡排序前:"<<endl;&

91、lt;/p>　　L.Display();　　cout<<"冒泡排序后:"<<endl;　　TempTime = (int)GetTickCount();　　L.BubbleSort();　　Spend

92、Time = (int)GetTickCount() - TempTime;　　L.Display();　　cout<<endl;　　cout<<"比較次數(shù)="<<L.CmpNum<<" "<<"關鍵字移

93、動次數(shù)="<<L.ChgNum<<" "<<"所需時間="<<SpendTime<<"ms"<<endl;　　break;　　case 4:

94、;　　cout<<"快速排序前:"<<endl;　　L.Display();　　cout<<"快速排序后:"<<endl;　　TempTime = (int)GetTickCount(

95、);　　L.QuickSort();　　SpendTime = (int)GetTickCount() - TempTime;　　L.Display();　　cout<<endl;　　cout<<"

96、;比較次數(shù)="<<L.CmpNum<<" "<<"關鍵字移動次數(shù)="<<L.ChgNum<<" "<<"所需時間="<<SpendTime<<"ms"<<endl;

97、;　　break;　　case 5:　　cout<<"選擇排序前:"<<endl;　　L.Display();　　cout<<"選擇排序后:&quo

98、t;<<endl;　　TempTime = (int)GetTickCount();　　L.SelSort();　　SpendTime = (int)GetTickCount() - TempTime;　　L.Display();<

99、;p>　　cout<<endl;　　cout<<"比較次數(shù)="<<L.CmpNum<<" "<<"關鍵字移動次數(shù)="<<L.ChgNum<<" "<<"所需時間="<<SpendTim

100、e<<"ms"<<endl;　　break;　　case 6:　　cout<<"堆排序前:"<<endl;

101、　L.Display();　　cout<<"堆排序后:"<<endl;　　TempTime = (int)GetTickCount();　　L.HeapSort();　　SpendTime = (int)GetTickCount

102、() - TempTime;　　L.Display();　　cout<<endl;　　cout<<"比較次數(shù)="<<L.CmpNum<<" "<<"關鍵字移動次數(shù)="<<L.ChgN

103、um<<" "<<"所需時間="<<SpendTime<<"ms"<<endl;　　break;　　default:

104、　cout<<"please input numbers again"<<endl;　　break;　　}　　}

105、　while(select!=7);　　}　　調試分析　　1．對正序、逆序和若干不同程度隨機打亂的可排序表，進行各種排序方法的比較測試，得到的測試數(shù)據(jù)具有較好的典型性和可比較性。通過設計和實現(xiàn)指定程序的隨機亂序算法，對隨機數(shù)序列的產生有了

106、具體的認識和實踐。　　2．將排序算法中的關鍵字比較和交換分別由兩個內部操作實現(xiàn)，較好的解決了排序算法的關鍵字比較次數(shù)和移動次數(shù)的統(tǒng)計問題。　　3．本實習作業(yè)采用循序漸進的策略，首先設計和實現(xiàn)可排序表的建立和隨機操作，然后用插入排序驗證各種內部輔助操作的正確性，進而逐個加入其他排序算法，最后完成對測試結果的顯示。調試能力有了提高。&

107、lt;p>　　用戶手冊 　?。?）本程序的運行環(huán)境為VC++。　　（2）進入演示程序后，即顯示文本方式的用戶界面。　?。?）演示程序以人機對話的形式進行。只要輸入記錄的個數(shù)，程序便產生80組隨機數(shù)，顯示通過直插排序、冒泡排序、快速排序、選擇排序、堆排序對隨機數(shù)進行排序時

108、，關鍵字的比較次數(shù)、移動次數(shù)的平均值和所用時間，從而直觀的比較各種內部排序算法的優(yōu)劣。　　7.測試結果：　　7.1、進入程序后即顯示文本方式的用戶界面：　　圖5.1 進入程序后的界面　　7.2、開始運行時的用戶界面：

109、;　　1）輸入1回車，即得直接插入排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)和時間。如圖5.2：　　圖5.2 輸入1后的運行結果　　2）輸入2回車，即得希爾排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)及時間，如圖5.3：　　圖5.3 輸入2后的運行結果<p&g

110、t;　　3）輸入3回車，即得快速排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)及時間，如圖5.4：　　圖5.4 輸入3后的運行結果　　4）輸入4回車，即得堆排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)及時間，如圖5.5：　　圖5.5 輸入4后的運行結果　　5）輸入5回車，即

111、得冒泡排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)及時間，如圖5.6：　　圖5.6 輸入5后的運行結果　　6）輸入6回車，即得選擇排序的排序結果及其關鍵字比較次數(shù)和移動次數(shù)及時間，如圖5.7：　　圖5.7 輸入6后的運行結果　　7）輸入7回車，即退出該程序。</p

112、>　　說明：從結果可以看出來，六種算法所用的時間均為零，這是因為排序的隨機數(shù)太少，如果數(shù)再多點，會有時間。　　8.附錄：　　在這次的數(shù)據(jù)結構課程設計中,排序綜合,通過該題目的設計過程,加深了對排序算法的理解,對排序算法上基本運算的實現(xiàn)有所掌握,對課本中所學的各種數(shù)據(jù)結構進一步理解和掌握,學

113、會了如何把學到的知識用于解決實際問題,鍛煉了自己動手的能力。　　參考書籍：　　[1]數(shù)據(jù)結構——習題與解析，李春葆，清華大學出版社　　[2]數(shù)據(jù)結構，嚴蔚敏，吳偉民。北京：清華大學出版社　　[3] c/c++與數(shù)據(jù)結構，棧。王力柱，2

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計報告--排序

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計報告--排序

文檔簡介

溫馨提示

最新文檔

評論

免費下載