數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較

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

已閱讀1頁，還剩10頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　題目：　　內(nèi)部排序算法的比較　　實(shí)驗(yàn)報告　　需求分析　　本程序?qū)σ韵铝N常用的內(nèi)部排序進(jìn)行實(shí)測比較：起泡排序、直接插

2、入　　排序、簡單選擇排序、快速排序、希爾排序、堆排序。　　2.待排序表的元素的關(guān)鍵字為整數(shù)，雍正徐、逆序和隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)做測試比較。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換記為3次移動）。　　3.程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“提示信息”下，用戶可由鍵盤輸

3、入產(chǎn)生隨機(jī)數(shù)的種子，計算機(jī)終端顯示各內(nèi)部排序的比較參數(shù)。　　4.最終對結(jié)果做出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小給予解釋。　　二、概要設(shè)計　　1.可排序表的抽象數(shù)據(jù)類型定義：　　ADT OrderableList</p&g

4、t;　　{　　數(shù)據(jù)對象：D = {ai |ai ∈IntegerSet,i = 1,2,……,n,n >= 0}　　數(shù)據(jù)關(guān)系：R1 = {<ai-1,ai>|ai-1,ai ∈D.i = 2,……,n}　　基本操作：&

5、lt;/b>　　SelectListType(c)　　操作結(jié)果：打印提示信息，請用戶選擇待排序表的類型，順序型、　　逆序型還是隨機(jī)數(shù)組。　　BubbleSort(&L)　　操作結(jié)果：進(jìn)行起泡排序，返回排序后的順序表&

6、lt;/p>　　InsertSort(&L)　　操作結(jié)果：進(jìn)行插入排序，返回排序后的順序表　　SelectSort(&L)　　操作結(jié)果：進(jìn)行選擇排序，返回排序后的順序表　　QuickSort(&L)

7、　　操作結(jié)果：進(jìn)行快速排序，返回排序后的順序表　　ShellSort(&L)　　操作結(jié)果：進(jìn)行希爾排序，返回排序后的順序表　　HeapSort(&L)　　操作結(jié)果：進(jìn)行堆排序，返回排序后的順序表

8、　　SelectSortMethod(&L,c1)　　操作結(jié)果：打印提示信息，請用戶選擇排序方法，起泡排序、插入　　排序、選擇排序、快速排序、希爾排序還是堆排序　　OutPut(L)　　操作結(jié)果：打印排序中關(guān)鍵字的比較次數(shù)和移

9、動次數(shù)　　}ADT OrderableList　　本程序包含兩個模塊：　　1）.主程序模塊　　int mian()　　{　<

10、p>　　初始化；　　用戶選擇待測表的類型；　　輸入選擇，用switch語句判斷；　　While（“命令” ！= “退出”）　　{

11、　接受命令；　　處理命令；　　}　　}　?。玻膳判虮韱卧K----實(shí)現(xiàn)可排序表的抽象數(shù)據(jù)類型

12、;　　各模塊之間的調(diào)用關(guān)系：　　主程序模塊　　可排序表單元模塊　　三、詳細(xì)設(shè)計　　1.根據(jù)題目要求何可排序表的基本操作特點(diǎn)，可排序表采用證書順序表存儲結(jié)構(gòu)，并

13、實(shí)現(xiàn)在頭文件SqList.H。　　//******************基本操作的函數(shù)原型******************\\　　#define MAXSIZE 20 //用作示例的順序表的最大長度　　typedef int KeyType; //定義

14、關(guān)鍵字為整數(shù)類型　　typedef int InfoType; //定義其他數(shù)據(jù)項(xiàng)也為整數(shù)類型　　int time_key_compare = 0; //定義全局變量，關(guān)鍵字比較次　　int time_key_move = 0; //數(shù)和移動次數(shù)均為0

15、　　typedef struct　　{　　KeyType key; //關(guān)鍵字項(xiàng)　　InfoType otherinfo; //其他數(shù)據(jù)項(xiàng)<p

16、>　　}RedType; //記錄類型　　typedef struct　　{　　RedType r[MAXSIZE + 1]; //r[0]閑置或用做哨兵　　in

17、t length; //順序表長度　　}SqList; //順序表類型　　//****************************基本操作*********************\\　　bool LT(KeyType

18、 a,KeyType b)//比較兩個KeyType類型變量的大小　　{　　time_key_compare ++; //比較次數(shù)+1　　if(a < b)<p

19、>　　return true; //<,返回true　　else 　　return false; //否則，返回false　　} //LT</b

20、>　　void copyKey(RedType &a,RedType &b)　　{ //將RedType類型變量b復(fù)制給a　　a = b;　　time_

21、key_move ++; //關(guān)鍵字移動次數(shù)+1　　}//copyKey　　void swap(RedType &a,RedType &b)　　{ //將RedType型變量a和b進(jìn)行交換操作</p&

22、gt;　　RedType c; //定義RedType型變量c　　c = a;　　a = b;　　b = c;</p&g

23、t;　　time_key_move += 3; //關(guān)鍵字移動次數(shù)+3　　}//swap　　/****************直接插入排序*********************\　　void InsertSo

24、rt(SqList &L)　　{ //對順序表L做直接插入排序　　for(int i = 2; i <= L.length; ++i)　　{　　if(LT(L

25、.r[i].key,L.r[i - 1].key))　　{ //“<”，需將L.r[i]插入有序子表　　copyKey(L.r[0] ,L.r[i]); //復(fù)制為哨兵　　copyKey(L.r[i] ,L.r[i - 1]);&l

26、t;/p>　　for(int j = i - 2;LT(L.r[0].key,L.r[j].key); --j)　　{　　copyKey(L.r[j + 1] ,L.r[j]); //記錄后移　　}</b&

27、gt;　　copyKey(L.r[j + 1] ,L.r[0]); //插入到正確的位置　　}　　}　　}//InsertSort　　//***

28、**********************希爾排序*************************\　　void shellInsert(SqList &L,int dk)　　{ //對順序表L做一希爾插入排序。　　//1.前后記錄位置的增量式是dk，而不是1；<p&

29、gt;　　//2.r[0]只是暫存單元，不是哨兵。當(dāng) j<= 0時，插入位置已找到　　for(int i = dk + 1;i <= L.length; ++i)　　{　　if(LT(L.r[i].key,L.r[i - dk].key))

30、　　{ //需將L.r[i]插入到有序增量子表　　copyKey(L.r[0] ,L.r[i]); //暫存在L.r[0]中　　for(int j = i - dk;j > 0 && LT(L.r[0].key,L.r[j].key); j-= dk)</

31、p>　　copyKey(L.r[j + dk] ,L.r[j]); //記錄后移　　copyKey(L.r[j + dk] ,L.r[0]); //插入　　}　　}

32、;　　}//ShellInsert　　void ShellSort(SqList &L,int dlta[],int t)　　{ //按增量序列dlta[0……t - 1]對順序表L作希爾排序　　for(int k = 0;k < t;

33、 ++k)　　shellInsert(L,dlta[k]); //一趟增量為dlta[k]的插入排序　　}//ShellSort　　//**************起泡排序****************************\　　void BublleSort(Sq

34、List &L)　　{　　int i = L.length;　　while(i > 1)　　{　　int lastExchangeIndex

35、 = 1;　　for(int j = 1;j 　　{　　if(LT(L.r[j + 1].key,L.r[j].key)) //小于成立進(jìn)行交換　　{

36、　　swap(L.r[j + 1],L.r[j]);　　lastExchangeIndex = j;　　}　　}　　i = lastExchangeIndex;</p&

37、gt;　　}　　}//BubbleSort　　/***************************簡單選擇排序********************/　　int SelectMinKey(SqList L,int i)<

38、;p>　　{ //在L.r[i..L.length]中選擇key最小的記錄　　for(int j = i ;j <= L.length; ++j)　　{　　if(LT(L.r[j].key,L.r[i].key))</p

39、>　　{　　i = j;　　}　　}　　return i;

40、 //返回最小記錄下標(biāo)　　}　　void SelectSort(SqList &L)　　{ //對順序表做簡單選擇排序for(int i = 1;i < L.leng

41、th; ++i)　　{ //選擇第i小的記錄，并交換到位　　int j = SelectMinKey(L,i);　　//令j為L.r[i..L.length]中選擇key最小的記錄　　if(i != j)</p&

42、gt;　　{　　swap(L.r[j],L.r[i]); //與第i記錄進(jìn)行交換　　}　　}　　}//Selecte

43、Sort　　/*********************快速排序*************/　　int Partition(SqList &L,int low,int high)　　{ //交換順序表L中字表r[low……h(huán)igh]的記錄，樞軸記錄到位，并

44、　//返回其所在位置，此時在他之前（后）的記錄均不大（?。┡c它。　　copyKey(L.r[0],L.r[low]);//用字表的第一個紀(jì)錄作樞軸記錄 　　KeyTypepivotkey=L.r[low

45、].key; //樞軸記錄關(guān)鍵字　　while(low < high)　　{ //從表的兩端交替向中間掃描　　while(low<high&& !LT(L.r[high].key,pivotkey)) --high;</p&

46、gt;　　copyKey(L.r[low],L.r[high]);　　//將比樞軸記錄小的記錄移到低端　　while(low<high && !LT(pivotkey,L.r[low].key))++low;　　copyKey(L.r[high],L.r[low])

47、;　　//將比樞軸記錄大的記錄移到高端　　}　　copyKey(L.r[low],L.r[0]); //樞軸記錄到位　　return low;

48、 //返回樞軸位置　　}//Partition　　void QSort(SqList &L,int low,int high)　　{ //對順序表L中的子序列L.r[low……h(huán)igh]做快速排序　　if(low < high)<

49、/p>　　{ //長度> 1　　int pivotloc = Partition(L,low,high); 　　//將L.r[low……h(huán)igh]一分為二　　QSort(L,low,p

50、ivotloc - 1); 　　//對低子表遞歸排序，pivotloc是樞軸位置　　QSort(L,pivotloc + 1,high); 　　//對高子表遞歸排序　　}

51、　}//QSort　　void QuickSort(SqList &L)　　{ //對順序表L做快速排序　　QSort(L,1,L.length);　　}//QuickS

52、ort　　/*************************堆排序*********************/　　void HeapAdjust(SqList &L,int s,int m)　　{ //已知L.r[s...m]中記錄的關(guān)鍵字除L.r[s].key之外均滿足定義，

53、　　//本函數(shù)調(diào)整H.r[s]的關(guān)鍵字，使H.r[s...m]成為一個大頂對　　RedType rc = L.r[s];　　for(int j = 2 * s;j <= m;j *= 2)　　{ //沿key較大的孩子結(jié)點(diǎn)向下帥選<

54、/p>　　if(j < m && LT(L.r[j].key,L.r[j+1].key)) ++j;　　//j 為key較大的記錄的下標(biāo)　　if(!LT(rc.key,L.r[j].key)) break;//rc應(yīng)插入在位置s上　　copyKey(L.r

55、[s],L.r[j]);　　s = j;　　}　　L.r[s] = rc; //插入　　}//HeapAdjust&

56、lt;/p>　　void HeapSort(SqList &L)　　{//對順序表L進(jìn)行堆排序　　for(int i=L.length/2;i>0;--i)　　//把L.r[1....H.length]建成大頂堆　　HeapAdj

57、ust(L,i,L.length);　　for( i = L.length;i >1; --i)　　{　　swap(L.r[1],L.r[i]); //將堆頂記錄和當(dāng)前未經(jīng)排序的子序列　　// L.r[1……i]中最后一個記錄進(jìn)

58、行交換　　HeapAdjust(L,1,i - 1);//將L.r[1....i-1]重新調(diào)整為大頂堆　　}　　}//HeapSort　　2.主函數(shù)和其他輔助函數(shù)的偽碼算法　　#include

59、<stdlib.h> //產(chǎn)生隨機(jī)數(shù)所需的庫函數(shù)　　/*****************************主函數(shù)************************/　　int main()　　{<p&g

60、t;　　int arry[MAXSIZE + 1]; //存放排序前數(shù)組　　int typeChoice; //根據(jù)提示鍵入的類型選擇序號　　int methodChoice; //根據(jù)提示鍵入的方法選擇序號　　int seed;

61、 //用于產(chǎn)生隨機(jī)數(shù)的種子　　PrintArrayMenu(); //打印選擇待排序表的類型菜單　　switch(typeChoice)　　{　　case 1:選擇的是順序表，初

62、始化鏈表并打印　　break;　　case 2:選擇的是逆序表，初始化鏈表并打印　　break;　　case 3:選擇的是隨機(jī)數(shù)表　　srand(seed

63、);　　//初始化隨機(jī)數(shù)，并利用rand（）產(chǎn)生隨機(jī)數(shù)并打印　　break;　　default:　　break;&l

64、t;b>　　}　　cout <<L.length; //打印待排序數(shù)組的長度　　PrintMenu(); //打印排序方法選擇菜單　　while(methodChoice!= 7)&

65、lt;/p>　　{　　getChoice(L,choice); 　　//根據(jù)選擇的方法堆表進(jìn)行排序操作并打印相關(guān)信息　　for( j = 1;j <= MAXSIZE; j ++)　　{

66、 //將鏈表恢復(fù)至未排序時狀態(tài)　　L.r[j].key = arry[j];　　}　　}　　return 0;&l

67、t;/p>　　}　　/****************根據(jù)選擇排序********************/　　void getChoice(SqList &L,int c)　　{

68、 //根據(jù)選擇進(jìn)行排序并輸出相關(guān)信息　　int Array[3] = {5,3,1}; //希爾排序所需增量數(shù)組　　switch(c)　　{　　cas

69、e 1:　　InsertSort(L); // 直接插入排序 　　outPut(L); //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)　　break;&l

70、t;p>　　case 2:　　ShellSort(L,Array,3); //希爾排序　　outPut(L); //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)　　break;<

71、;/b>　　case 3:　　BublleSort(L); //起泡排序　　outPut(L); //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)

72、;　　break;　　case 4:　　SelectSort(L); //簡單選擇排序　　outPut(L); //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)&

73、lt;/p>　　break;　　case 5:　　QuickSort(L); //快速排序　　outPut(L);

74、 //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)　　break;　　case 6:　　HeapSort(L); //堆排序　　ou

75、tPut(L); //輸出關(guān)鍵字比較次數(shù)和移動次數(shù)　　break;　　case 7:排序結(jié)束　　default:　　break;</b&g

76、t;　　}　　}　　函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu)　　InsertSort </

77、p>　　順序表 ShellSort 　　BublleSor

78、t 　　逆序表 getTypeChoice getMethodChoice　　SelectSort <

79、;p>　　隨機(jī)數(shù)表 QuickSort 　　HeapSort　　srand rand<

80、b>　　排序算法結(jié)果比較　　對各種表長和測試組數(shù)進(jìn)行了測試，程序運(yùn)行正常。分析實(shí)測得到的數(shù)值，六種排序算法的特點(diǎn)小結(jié)如下：　　五、附錄　　源程序文件名清單：　　SqLis

81、t.H //可排序表的實(shí)現(xiàn)　　main.C //主程序　　實(shí)驗(yàn)中遇到的問題及解決辦法　　1.程序采取循序漸進(jìn)的策略。首先設(shè)計和實(shí)現(xiàn)可排序表的建立操作，根據(jù)要求因包括隨機(jī)數(shù)序列、正序和逆序三種情況，為避免不必要的錯誤，程序采用了先定義了兩個數(shù)組，分

82、別為正序和逆序，程序運(yùn)行時分別將數(shù)組的值賦給鏈表的方式進(jìn)行順序表的建立，另外，起初對于隨機(jī)數(shù)的產(chǎn)生產(chǎn)生了疑惑，但隨后通過搜集資料成功的使用srand（seed）和rand（）函數(shù)得到解決。然后用插入排序驗(yàn)證了各種內(nèi)部輔助操作的正確性，進(jìn)而逐個加入其他排序算法，最后完成對測試結(jié)果的顯示。　　2.程序旨在進(jìn)行六種排序方法優(yōu)劣性的比較，在進(jìn)行對六種排序依次排序時，出現(xiàn)了進(jìn)行過依次排序后，排序表變?yōu)檎?/p>

83、表而之后的集中排序方法都是在進(jìn)行正序表的排序，而沒有達(dá)到想要的效果，最后在主函數(shù)中添加了一個數(shù)組，用于記錄原排序表的順序，并在每次排序之后利用該數(shù)組對排序表進(jìn)行再次建立，使得問題成功解決。　　3.開始編程之初，總會出現(xiàn)關(guān)鍵字比較和移動次數(shù)的計算錯誤，在程序中進(jìn)行逐步記錄既繁瑣又易出錯，之后經(jīng)過思考，建立了copyKey（）和swap（）函數(shù)，成功提高了程序效率并降低了計算錯誤率。</p&g

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載