《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實驗報告--多種排序方式的比較

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計報告　　目錄　　1、引言　　1.1課設(shè)目的------------------

2、---------------------------------------3　　1.2課設(shè)內(nèi)容---------------------------------------------------------3　　2、需求分析　　2.1任務(wù)與分析-------------

3、-----------------------------------------3　　2.2功能模塊的劃分-------------------------------------------------3　　3、總體設(shè)計------------------------------------------　　4

4、、詳細(xì)設(shè)計------------------------------------------　　4.1冒泡排序-----------------------------------------------------------5　　4.2快速排序-----------------------------------------------------

5、------6　　4.3直接插入排序-----------------------------------------------------7　　4.5折半插入排序-----------------------------------------------------7　　4.4堆排序------------

6、--------------------------------------------------7　　5、調(diào)試結(jié)果-------------------------------------------　　5.1冒泡排序測試----------------------------------------------------8

7、　　5.2快速排序測試----------------------------------------------------8　　5.3直接插入排序測試----------------------------------------------9　　5.4折半插入排序測試--------------------------------

8、--------------9　　5.5堆排序測試-------------------------------------------------------10　　5.6輸入錯誤----------------------------------------------------------10　　6、課程

9、設(shè)計總結(jié)--------------------------------------11　　1.1課程設(shè)計目的　　學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法。另一方面，通過團隊合作、文檔編制、主頁設(shè)計等環(huán)節(jié)對學(xué)生進行全方位的訓(xùn)練，最終達(dá)到培養(yǎng)數(shù)據(jù)抽象能力和軟件

10、設(shè)計的能力。通過全部過程培養(yǎng)和鍛煉的鉆研能力、動手能力、分析問題和解決問題的實際能力。　　1.2課程設(shè)計內(nèi)容　　本程序把對數(shù)列的排序轉(zhuǎn)化為對數(shù)組元素的排序，用戶可以根據(jù)自己的實際問題選擇系統(tǒng)提供的幾種排序方法的任意一種進行排序。包括冒泡排序，直接插入排序，折半插入排序，堆排序和快速排序。對于每一種排序算法可以輸出初始

11、序列和每一趟的排序結(jié)果。　　2.1任務(wù)與分析　　任務(wù)：　　利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，對這些數(shù)進行多種方法進行排序。　　分析：<

12、;p>　　本系統(tǒng)實現(xiàn)了幾種常用的排序方法，包括：折半插入排序、直接插入排序、冒泡排序、快速排序（遞歸）、堆排序。　　2.2功能模塊的劃分　　2..2.1 輸入模塊　　利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，個數(shù)由用戶從鍵盤中自己輸入。　　2.2.2選擇模塊&

13、lt;/b>　　在菜單中選擇相應(yīng)的編號來選擇采用何種排序算法，算法包括：冒泡排序、直接插入排序、折半插入、快速排序（遞歸）、堆排序。　　2.2.3輸出模塊　　輸出排序前或排序后的數(shù)據(jù)元素到屏幕顯示，并且輸出每一趟的排序結(jié)果顯示在屏幕上。<p

14、>　　2.2.4各個排序模塊　　具體的設(shè)計思路在后序的詳細(xì)設(shè)計中將系統(tǒng)的介紹。　　總體設(shè)計（框圖結(jié)構(gòu)）　　詳細(xì)設(shè)計　　4.1冒泡排序　　冒泡排序是對

15、所有相鄰的記錄進行比較，若這兩個元素剛好與排序結(jié)果逆序，則將這兩個元素的位置進行交換。過程描述如下圖所示：　　圖3.3 冒泡排序的比較結(jié)果　?。?）、將整個的待排序序列的記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。　　（2）、對無序區(qū)從前向后依次將相鄰記錄的數(shù)據(jù)進行比較，若兩結(jié)

16、果的大小剛好與排序結(jié)果相反，則將其交換，從而始數(shù)據(jù)值大的記錄向右邊移動。計較完無序區(qū)的最后兩個記錄，一趟冒泡排序結(jié)束。無序區(qū)最后一個記錄進入有序區(qū)。　?。?）、重復(fù)步驟（2），直到無序區(qū)中只剩下一個記錄。　　4.2快速排序　　首先用兩個指針i、j分別指向首，以第一個元素為關(guān)鍵

17、字，該關(guān)鍵字所屬的記錄另存儲在一個x變量中。從文件右端元素r[j].key開始與控制字x.key相比較，當(dāng)r[j].key大于等于x.key時，r[j]不移動，修改指針j，j--，直到r[j].key<x.key，把記錄r[j]移動到文件左邊i所指向的位置;然后在文件左邊修改i指針,i++，讓r[i].key與x.key相比較，當(dāng)r[i].key小于等于x.key時，r[i]不移動，修改指針i，i--，直到r[i].key<

18、x.key, 把記錄r[i]移動到文件右邊j所指向的位置;然后在文件右邊修改j指針j--。重復(fù)上面的步驟.　　初始關(guān)鍵字序列 72 6 57 88 60 42 83 73 48 85　　i j j <

19、;/p>　　進行1次交換之后 48 6 57 88 60 42 83 73 85　　i i j　　進行2次交換之后 48 6 57 60 42 83 73

20、88 85　　I j j　　進行3次交換之后 48 6 57 42 60 83 73 48 85　　I j j　　完成一趟排序 48

21、6 57 42 60 72 83 73 88 85　　圖4.2.1一趟快速排序過程　　初始狀態(tài) {72 6 57 88 60 42 83 73 48 85}　　一次劃分之后 {48 6 57

22、 42 60} 72 {83 73 48 85}　　分別進行快速排序 {42 6} 48 {57 60}　　{6} 42 　　結(jié)束　　57 {60}

23、;　　結(jié)束　　{73} 83 {88 85}　　結(jié)束　　{85} 88　　結(jié)束

24、　　有序序列 {6 42 48 57 60 72 73 83 85 88}　　圖4.2.2快速排序的完整過程　　4.3直接插入排序　　設(shè)有一組關(guān)鍵字{K1,K2,…

25、….,Kn},排序開始變認(rèn)為K1是一個有序的序列,讓K2插入到表長為1的有序序列,使之成為一個表長為2的有序序列, 讓K3插入到表長為2的有序序列,使之成為一個表長為3的有序序列,依次類推,最后讓Kn插入上述表長為n-1的有序序列,得到一個表長為n的有序序列.　　4.4折半插入排序　　因為關(guān)鍵字{K1,K2,…….,

26、Kn} 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在關(guān)鍵字{K1,K2,…….,Kn}中查找k[i]的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。如同直接插入排序，只是確定插入的位置時，選擇折半查找的方法。　　4.5堆排序　　把n個記錄存于向量r之中，把它看成完全二叉樹，此時關(guān)鍵字序列不一定滿足堆的關(guān)系

27、。堆排序大體分為兩步處理：　　初建堆，從堆的定義出發(fā)，當(dāng)i=1、2、。。。。、[2/n]時應(yīng)滿足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n個結(jié)點的雙親編號),將以i結(jié)點為根的子樹調(diào)整為堆，然后令i=i-1，將以不結(jié)點為根的子樹調(diào)整為堆。此時可能會反復(fù)調(diào)整某些結(jié)點，直到i=1為止，堆初步建成。　　堆排序，首先輸出堆

28、頂元素（一般是最小值）,讓堆中最后一個元素上移到原堆頂位置，然后恢復(fù)堆。因為經(jīng)過第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟。　　5.系統(tǒng)測試　　系統(tǒng)主界面

29、　　5.1冒泡排序　　5.2快速排序　　5.3直接插入排序　　5.4折半插入排序　　5.5堆排序&l

30、t;/p>　　5.6輸入錯誤　　課設(shè)總結(jié)　　通過這次課程設(shè)計的學(xué)習(xí)讓我學(xué)會了許多，加深了對數(shù)據(jù)結(jié)構(gòu)排序算法的認(rèn)識。在這次課程設(shè)計中，完成了每種排序算法。排序算法選了五個，包括：冒泡排序、直接插入排序、折半插入排序、快速排序（遞歸）、堆排序。同時也實現(xiàn)了

31、隨機數(shù)的生成。以及生成任意范圍內(nèi)的隨機數(shù)。雖然在算法完成的過程中從網(wǎng)上參考了一些資料和實驗內(nèi)容，但對這次課程設(shè)計的成果還是比較滿意的。　　這次的課程設(shè)計還有很多不足之處，如鏈表存儲結(jié)構(gòu)中的堆排序算法，當(dāng)排序個數(shù)過多時，就會等待很長時間?？赡軙r調(diào)用的函數(shù)過多的原因造成的，但排序是正確的。用指針代替函數(shù)的調(diào)用。還有就是隨機數(shù)不能隨時更改，只能設(shè)定一次。程序還存在的問題是如果用戶輸入錯誤，不能及時的進

32、行提醒，在這方面還有提高的空間。　　同時在完成這個課程設(shè)計后，我也學(xué)到了很多知識，并能熟練的掌握他們了。首先學(xué)會了隨機數(shù)的產(chǎn)生。熟練的撐握了C語言的函數(shù)調(diào)用、嵌套操作。撐握了每種排序算法的基本思想，并學(xué)會了編寫程序的一般步驟：思考問題，寫出解決方案，寫出偽代碼，完成代碼，調(diào)試程序。不像以前那樣開始就直接寫代碼。當(dāng)然，還包括如何寫出操作簡便，比較友好的界面。

33、;　　但我還是認(rèn)為自己還有很多不足，希望以后能彌補。　　附（源代碼）：#include<stdio.h>　　#include<time.h>　　#include<stdlib.h>　　#define MAX 100

34、　　void produce_data(int a[],int n){　　//產(chǎn)生數(shù)據(jù)　　int i;　　srand((unsigned)time(NULL));//產(chǎn)生隨機數(shù)

35、　　for(i=0;i<n;i++){　　a[i]=rand()%100;　　}　　}　　void produce1_data(int data[],int num) //隨機產(chǎn)生一批數(shù)&

36、lt;/p>　　{ //專門用于堆排序，數(shù)據(jù)從data[1]開始存放　　int i;　　srand((unsigned)time(NULL));　　for(i=1;i<=num;i++)　　data[

37、i]=rand()%100;　　}　　void print_data(int a[],int n){　　//打印數(shù)據(jù)　　int i;&

38、lt;p>　　int count;　　for(i=0;i<n;i++){　　printf("%5d",a[i]);　　count++;　　if(count%10==0)<p

39、>　　printf("\n");　　}　　printf("\n");　　}　　void print1_data(int data[],int num)

40、 //輸出數(shù)據(jù)　　{ //專門用于堆排序，數(shù)據(jù)從data[1]開始輸出　　int i;　　int count;　　for(i=1;i<=num;i++)　　{</

41、b>　　printf("%5d",data[i]);　　count++;　　if(count%10==0)　　printf("\n");<b

42、>　　}　　}　　void order_data(int *a,int n){　　//冒泡排序　　int i,j,temp;

43、int flag=1;　　int k=0;//一定要賦初值，否則會產(chǎn)生隨機數(shù)　　for(i=0;i<n-1&&flag==1;i++){　　flag=0;//利用進行標(biāo)記,減少比較次數(shù)　　for(j=0;j<n-i-1;j++){</p&

44、gt;　　if(a[j]>a[j+1]){　　flag=1;　　temp=a[j];　　a[j]=a[j+1];　　a[j+1]=temp;　　}

45、　　}　　k++;　　printf("第%d趟的排序結(jié)果為:",k);　　print_data(a,n);//函數(shù)的調(diào)用<p&

46、gt;　　}　　}　　void QuickSort(int *a,int left,int right,int n)//(a,0,n-1,n)　　{ 　　//

47、利用快速排序算法，完成對數(shù)組list 中的index 個數(shù)進行排序。　　int i=left;　　int j=right;　　int temp=a[i];　　int k;　　for(k=0;k

48、<n;k++)　　{　　while(i<j)　　{　　while((j>i)&&(a[j]>temp))<b

49、>　　j--;　　if(i<j)　　{　　a[i]=a[j];　　i++;<b

50、>　　}　　while((j>i)&&(a[i]<temp))　　i++;　　if(i<j)　　{

51、　　a[j]=a[i];　　j--;　　}　　}　　a[i]=temp;

52、　printf("%6d", a[k]);　　}　　printf("\n");　　if(left<i-1)　　QuickSort(a,left,i-1,n);//(left,i-1)遞歸&

53、lt;/p>　　if(i+1<right)　　QuickSort(a,i+1,right,n);//(i+1,right)遞歸　　}　　//直接插入排序　　voi

54、d InsertSort(int *a,int n) 　　{ 　　int i,j;　　int temp;　　for(i=1;i<n;i++)//控制循環(huán)的次數(shù)

55、　　{ 　　temp=a[i]; 　　for(j=i-1;j>=0;j--)　　{ 　　if(a[j]>temp)

56、;　　{ 　　a[j+1]=a[j]; 　　}　　else 　　{ <p&

57、gt;　　break; 　　} 　　} 　　a[j+1]=temp;　　print_data(a,n);<

58、;b>　　} 　　} 　　void createHeap (int *heap, int root, int n)　　{　　int j;</b

59、>　　int temp; //于數(shù)值交換時的暫存變量　　int finish; //判斷堆是否建立完成　　j=2*root; //子結(jié)點的index　　temp=heap[root]; //暫存heap 的root 值　　f

60、inish=0; //默認(rèn)堆建立尚未完成　　while (j<=n && finish==0)　　{　　//最大的子結(jié)點　　if (j<n)</

61、b>　　if (heap[j]<heap[j+1])　　j++;　　if (temp>=heap[j])　　finish=1; //堆建立完成　　else&

62、lt;/b>　　{　　heap[j/2]=heap[j]; //父結(jié)點=目前結(jié)點　　j=2*j;　　}<

63、b>　　}　　heap[j/2]=temp; //父結(jié)點=root 值　　}　　void HeapSort(int *heap,int n)　　{ //堆排序</p

64、>　　int i,j,temp;　　for(i=(n/2);i>=1;i--) //將二叉樹轉(zhuǎn)成heap　　createHeap(heap,i,n);　　for(i=n-1;i>=1;i--) //開始進行堆排序

65、　{　　temp=heap[i+1]; //heap 的root 值和最后一個值交換　　heap[i+1]=heap[1];　　heap[1]=temp;　　createHeap(heap, 1, i); //對其余數(shù)值重建堆*/

66、　　printf("\n 目前的排序為:"); //打印堆處理過程*/　　for(j=1;j<=n;j++)　　printf("%3d",heap[j]);　　//printf("\n");<p&g

67、t;　　}　　}　　void bisort(int *a,int n)　　{　　int low,high,m,k;&

68、lt;b>　　int temp;　　for(k=2;k<=n;k++)　　{　　temp=a[k-1];　　low=0;high=k-2;

69、do {　　m=(low+high)/2;　　if (temp<=a[m])　　high=m-1;//插入前半?yún)^(qū)　　else 　　low=m+1;//插入后半?yún)^(qū)<

70、;/p>　　} while (low<=high);　　for (high=k-1;high>low;high--)　　a[high]=a[high-1];//記錄右移　　a[high]=temp;//插入數(shù)據(jù)　　print_dat

71、a(a,n);　　}　　}　　void auther()　　{　　printf("\n\n\n\n\n\n

72、\n\n\n\t\t\t 軟件名稱:數(shù)據(jù)排序軟件\n\n");　　printf("\t\t\t 技術(shù)開發(fā):張浩然\n\n");　　printf("\t\t\t 請按任意鍵繼續(xù)......");　　getch();</

73、b>　　system("cls");　　}　　void showmenu()　　{ //顯示菜單　　printf("\

74、t\t**********歡迎使用數(shù)據(jù)排序小軟件**********\n");　　printf("\t\t1、冒泡排序\n");　　printf("\t\t2、快速排序\n");　　printf("\t\t3、直接插入排序\n");</p

75、>　　printf("\t\t4、堆排序\n");　　printf("\t\t5、折半插入排序\n");　　printf("\t\t6、退出程序\n");　　}&l

76、t;p>　　main(){　　int num,choice;　　int a[MAX];　　system("color f9");//第一個為背景，第二個為前景(亮白色，淺藍(lán)色)　　authe

77、r();　　while(1){　　showmenu();　　printf("請輸入你的選擇:\n");　　scanf("%d",&choice);

78、　　switch(choice){　　case 1:printf("你選擇的是冒泡排序\n");　　printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)\n");　　scanf("%d",&num);

79、;　　printf("排序前的數(shù)據(jù)\n");　　produce_data(a,num);　　print_data(a,num);　　printf("排序過程為:\n");　　order_data(a,num);

80、　　printf("最終的排序結(jié)果為:\n");　　print_data(a,num);　　system("pause");　　system("cls");　　break;&

81、lt;/b>　　case 2:printf("你選擇的是快速排序\n");　　printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)\n");　　scanf("%d",&num);　　produce_data(a,nu

82、m);　　printf("排序前的數(shù)據(jù)為:\n");　　print_data(a,num);　　printf("\n 排序過程如下：\n");　　QuickSort(a,0,num-1,num);//函數(shù)的調(diào)用

83、　　printf("\n 最終的排序結(jié)果為:\n");　　print_data(a,num);　　printf("\n");　　system("pause");　　system("c

84、ls");　　break; 　　case 3:printf("你選擇的是直接插入排序\n");　　printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)\n");　　scanf("%d&quo

85、t;,&num);　　produce_data(a,num);　　printf("排序前的數(shù)據(jù)為:\n");　　print_data(a,num);　　printf("排序過程為:\n");<p

86、>　　InsertSort(a,num);　　printf("\n 最終的排序結(jié)果為:\n");　　print_data(a,num);　　system("pause");　　system("cls");&

87、lt;/p>　　break;　　case 4:printf("你選擇的是堆排序\n");　　printf("請輸入需要排序的元素個數(shù)：");　　scanf("%d",&num);&

88、lt;/p>　　produce1_data(a,num);　　printf("排序前的數(shù)據(jù)為:\n");　　print1_data(a,num);　　printf("\n 排序過程如下：\n");　　He

89、apSort(a,num);　　printf("\n 最終的排序結(jié)果為:\n");　　print1_data(a,num);　　printf("\n");　　system("pause");

90、　　system("cls");　　break;　　case 5:printf("你選擇的是折半插入排序\n");　　printf("請輸入需要排序的元素個數(shù):\n");&

91、lt;p>　　scanf("%d",&num);　　produce_data(a,num);　　printf("排序前的數(shù)據(jù)為:\n");　　print_data(a,num);　　printf("排序過程如

92、下:\n");　　bisort(a,num);　　printf("最終的排序結(jié)果為:\n");　　print_data(a,num);　　system("pause");　　sys

93、tem("cls");　　break;　　case 6:　　return 0;　　default:&

94、lt;/p>　　printf("你的選擇有誤，請重新輸入！\n");　　system("pause");　　system("cls");　　}&l

眾賞文庫> 全部分類> 畢業(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)方式做保護處理，對用戶上傳分享的文檔內(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è)計實驗報告--多種排序方式的比較

文檔簡介

溫馨提示

最新文檔

評論

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實驗報告--多種排序方式的比較

文檔簡介

溫馨提示

最新文檔

評論

免費下載