《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實驗報告

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課設(shè)題目：多種排序方式的比較專 業(yè)：計算機科學(xué)與技術(shù)班 級：姓 名：張浩然完成日期：指導(dǎo)教師：目錄1、引言 1.1課設(shè)目的-3 1.2課設(shè)內(nèi)容-3 2、需求分析 2.1任務(wù)與分析-3 2.2功能模塊的劃分-3 3、總體設(shè)計- 4、詳細(xì)設(shè)計- 4.1冒泡排序-5 4.2快速排序-6 4.3直接插入排序-7 4.5折半插入排序-7 4.4堆排序-7 5、調(diào)試結(jié)果- 5.1冒泡排序測試-8 5.2快速排序測試-8 5.3直接插入排序測試-9 5.4折半插入排序測試-9 5.5堆排序測試-10 5.6

2、輸入錯誤-10 6、課程設(shè)計總結(jié)-111.1課程設(shè)計目的學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法。另一方面，通過團(tuán)隊合作、文檔編制、主頁設(shè)計等環(huán)節(jié)對學(xué)生進(jìn)行全方位的訓(xùn)練，最終達(dá)到培養(yǎng)數(shù)據(jù)抽象能力和軟件設(shè)計的能力。通過全部過程培養(yǎng)和鍛煉的鉆研能力、動手能力、分析問題和解決問題的實際能力。1.2課程設(shè)計內(nèi)容本程序把對數(shù)列的排序轉(zhuǎn)化為對數(shù)組元素的排序，用戶可以根據(jù)自己的實際問題選擇系統(tǒng)提供的幾種排序方法的任意一種進(jìn)行排序。包括冒泡排序，直接插入排序，折半插入排序，堆排序和快速排序。對于每一種排序算法可以輸出初始序列和每一趟的排序結(jié)果。2.1

3、任務(wù)與分析任務(wù)：利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。分析：本系統(tǒng)實現(xiàn)了幾種常用的排序方法，包括：折半插入排序、直接插入排序、冒泡排序、快速排序（遞歸）、堆排序。2.2功能模塊的劃分2.2.1 輸入模塊利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)，個數(shù)由用戶從鍵盤中自己輸入。2.2.2選擇模塊在菜單中選擇相應(yīng)的編號來選擇采用何種排序算法，算法包括：冒泡排序、直接插入排序、折半插入、快速排序（遞歸）、堆排序。2.2.3輸出模塊輸出排序前或排序后的數(shù)據(jù)元素到屏幕顯示，并且輸出每一趟的排序結(jié)果顯示在屏幕上。2.2.4各個排序模塊具體的設(shè)計思路在后序的詳細(xì)設(shè)計中將系統(tǒng)的介紹。3. 總體設(shè)計（框圖

4、結(jié)構(gòu)） 排序小軟件錯誤再次輸入堆排序折半插入排序快速排序冒泡排序直接插入排序退出 開始調(diào)用歡迎界面函數(shù)showmenu()Startface()選擇操作項錯誤再次輸入直接插入排序冒泡排序折半插入排序退出堆排序快速排序結(jié)束4. 詳細(xì)設(shè)計4.1冒泡排序 冒泡排序是對所有相鄰的記錄進(jìn)行比較，若這兩個元素剛好與排序結(jié)果逆序，則將這兩個元素的位置進(jìn)行交換。 過程描述如下圖所示：圖3.3 冒泡排序的比較結(jié)果（1）、將整個的待排序序列的記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。（2）、對無序區(qū)從前向后依次將相鄰記錄的數(shù)據(jù)進(jìn)行比較，若兩結(jié)果的大小剛好與排序結(jié)果相反，則將其交

5、換，從而始數(shù)據(jù)值大的記錄向右邊移動。計較完無序區(qū)的最后兩個記錄，一趟冒泡排序結(jié)束。無序區(qū)最后一個記錄進(jìn)入有序區(qū)。（3）、重復(fù)步驟（2），直到無序區(qū)中只剩下一個記錄。4.2快速排序 首先用兩個指針i、j分別指向首，以第一個元素為關(guān)鍵字，該關(guān)鍵字所屬的記錄另存儲在一個x變量中。從文件右端元素rj.key開始與控制字x.key相比較，當(dāng)rj.key大于等于x.key時，rj不移動，修改指針j，j-，直到rj.key<x.key，把記錄rj移動到文件左邊i所指向的位置;然后在文件左邊修改i指針,i+，讓ri.key與x.key相比較，當(dāng)ri.key小于等于x.key時，ri不移動，修改指針i，i

6、-，直到ri.key<x.key, 把記錄ri移動到文件右邊j所指向的位置;然后在文件右邊修改j指針j-。重復(fù)上面的步驟. 初始關(guān)鍵字序列 72 6 57 88 60 42 83 73 48 85 i j j 進(jìn)行1次交換之后 48 6 57 88 60 42 83 73 85 i i j進(jìn)行2次交換之后 48 6 57 60 42 83 73 88 85 I j j進(jìn)行3次交換之后 48 6 57 42 60 83 73 48 85 I j j完成一趟排序 48 6 57 42 60 72 83 73 88 85圖4.2.1一趟快速排序過程初始狀態(tài) 72 6 57 88 60 42 8

7、3 73 48 85一次劃分之后 48 6 57 42 60 72 83 73 48 85分別進(jìn)行快速排序 42 6 48 57 60 6 42 結(jié)束 57 60 結(jié)束 73 83 88 85 結(jié)束 85 88 結(jié)束有序序列 6 42 48 57 60 72 73 83 85 88圖4.2.2快速排序的完整過程4.3直接插入排序設(shè)有一組關(guān)鍵字K1,K2,.,Kn,排序開始變認(rèn)為K1是一個有序的序列,讓K2插入到表長為1的有序序列,使之成為一個表長為2的有序序列, 讓K3插入到表長為2的有序序列,使之成為一個表長為3的有序序列,依次類推,最后讓Kn插入上述表長為n-1的有序序列,得到一個表長為n

8、的有序序列.4.4折半插入排序因為關(guān)鍵字K1,K2,.,Kn 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在關(guān)鍵字K1,K2,.,Kn中查找ki的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。如同直接插入排序，只是確定插入的位置時，選擇折半查找的方法。4.5堆排序 把n個記錄存于向量r之中，把它看成完全二叉樹，此時關(guān)鍵字序列不一定滿足堆的關(guān)系。堆排序大體分為兩步處理：初建堆，從堆的定義出發(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é)點為根的

9、子樹調(diào)整為堆。此時可能會反復(fù)調(diào)整某些結(jié)點，直到i=1為止，堆初步建成。堆排序，首先輸出堆頂元素（一般是最小值）,讓堆中最后一個元素上移到原堆頂位置，然后恢復(fù)堆。因為經(jīng)過第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟。5.系統(tǒng)測試系統(tǒng)主界面5.1冒泡排序5.2快速排序5.3直接插入排序5.4折半插入排序5.5堆排序5.6輸入錯誤6. 課設(shè)總結(jié)通過這次課程設(shè)計的學(xué)習(xí)讓我學(xué)會了許多，加深了對數(shù)據(jù)結(jié)構(gòu)排序算法的認(rèn)識。在這次課程設(shè)計中，完成了每種排序算法。排序算法選了五個，包括：冒泡排序、直接插入排序、折半插入排序、快速排序（遞歸）、堆排序。

10、同時也實現(xiàn)了隨機數(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è)定一次。程序還存在的問題是如果用戶輸入錯誤，不能及時的進(jìn)行提醒，在這方面還有提高的空間。同時在完成這個課程設(shè)計后，我也學(xué)到了很多知識，并能熟練的掌握他們了。首先學(xué)會了隨機數(shù)的產(chǎn)生。熟練的撐握了C語言的函數(shù)調(diào)用、嵌套操作。撐握了每種排序算法的基本思想，

11、并學(xué)會了編寫程序的一般步驟：思考問題，寫出解決方案，寫出偽代碼，完成代碼，調(diào)試程序。不像以前那樣開始就直接寫代碼。當(dāng)然，還包括如何寫出操作簡便，比較友好的界面。但我還是認(rèn)為自己還有很多不足，希望以后能彌補。附（源代碼）：#include<stdio.h>#include<time.h>#include<stdlib.h>#define MAX 100void produce_data(int a,int n)/產(chǎn)生數(shù)據(jù)int i; srand(unsigned)time(NULL);/產(chǎn)生隨機數(shù)for(i=0;i<n;i+)ai=rand()%100;

12、void produce1_data(int data,int num) /隨機產(chǎn)生一批數(shù) /專門用于堆排序，數(shù)據(jù)從data1開始存放int i;srand(unsigned)time(NULL);for(i=1;i<=num;i+)datai=rand()%100;void print_data(int a,int n)/打印數(shù)據(jù)int i;int count;for(i=0;i<n;i+)printf("%5d",ai);count+;if(count%10=0)printf("n");printf("n");void

13、 print1_data(int data,int num) /輸出數(shù)據(jù) /專門用于堆排序，數(shù)據(jù)從data1開始輸出int i;int count;for(i=1;i<=num;i+)printf("%5d",datai);count+;if(count%10=0)printf("n");void order_data(int *a,int n)/冒泡排序int i,j,temp;int flag=1;int k=0;/一定要賦初值，否則會產(chǎn)生隨機數(shù)for(i=0;i<n-1&&flag=1;i+)flag=0;/利用進(jìn)行標(biāo)記

14、,減少比較次數(shù)for(j=0;j<n-i-1;j+)if(aj>aj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;k+;printf("第%d趟的排序結(jié)果為:",k);print_data(a,n);/函數(shù)的調(diào)用void QuickSort(int *a,int left,int right,int n)/(a,0,n-1,n) /利用快速排序算法，完成對數(shù)組list 中的index 個數(shù)進(jìn)行排序。int i=left;int j=right;int temp=ai;int k;for(k=0;k<n;k+)while(i<

15、j)while(j>i)&&(aj>temp)j-;if(i<j)ai=aj;i+;while(j>i)&&(ai<temp)i+;if(i<j)aj=ai;j-;ai=temp;printf("%6d", ak);printf("n");if(left<i-1)QuickSort(a,left,i-1,n);/(left,i-1)遞歸if(i+1<right)QuickSort(a,i+1,right,n);/(i+1,right)遞歸/直接插入排序void InsertS

16、ort(int *a,int n) int i,j;int temp; for(i=1;i<n;i+)/控制循環(huán)的次數(shù) temp=ai; for(j=i-1;j>=0;j-) if(aj>temp) aj+1=aj; else break; aj+1=temp;print_data(a,n); void createHeap (int *heap, int root, int n)int j;int temp; /于數(shù)值交換時的暫存變量int finish; /判斷堆是否建立完成j=2*root; /子結(jié)點的indextemp=heaproot; /暫存heap 的root

17、值finish=0; /默認(rèn)堆建立尚未完成while (j<=n && finish=0)/最大的子結(jié)點if (j<n)if (heapj<heapj+1)j+;if (temp>=heapj)finish=1; /堆建立完成elseheapj/2=heapj; /父結(jié)點=目前結(jié)點j=2*j;heapj/2=temp; /父結(jié)點=root 值void HeapSort(int *heap,int n) /堆排序int i,j,temp;for(i=(n/2);i>=1;i-) /將二叉樹轉(zhuǎn)成heapcreateHeap(heap,i,n);for(

18、i=n-1;i>=1;i-) /開始進(jìn)行堆排序temp=heapi+1; /heap 的root 值和最后一個值交換heapi+1=heap1;heap1=temp;createHeap(heap, 1, i); /對其余數(shù)值重建堆*/printf("n 目前的排序為:"); /打印堆處理過程*/for(j=1;j<=n;j+)printf("%3d",heapj);/printf("n");void bisort(int *a,int n)int low,high,m,k;int temp;for(k=2;k<=n

19、;k+)temp=ak-1;low=0;high=k-2;do m=(low+high)/2;if (temp<=am)high=m-1;/插入前半?yún)^(qū)else low=m+1;/插入后半?yún)^(qū) while (low<=high);for (high=k-1;high>low;high-)ahigh=ahigh-1;/記錄右移 ahigh=temp;/插入數(shù)據(jù) print_data(a,n);void auther()printf("nnnnnnnnnttt 軟件名稱:數(shù)據(jù)排序軟件nn");printf("ttt 技術(shù)開發(fā):張浩然nn");p

20、rintf("ttt 請按任意鍵繼續(xù).");getch();system("cls");void showmenu() /顯示菜單printf("tt*歡迎使用數(shù)據(jù)排序小軟件*n");printf("tt1、冒泡排序n");printf("tt2、快速排序n");printf("tt3、直接插入排序n");printf("tt4、堆排序n");printf("tt5、折半插入排序n");printf("tt6、退出程序n&qu

21、ot;);main()int num,choice;int aMAX;system("color f9");/第一個為背景，第二個為前景(亮白色，淺藍(lán)色)auther();while(1)showmenu();printf("請輸入你的選擇:n");scanf("%d",&choice);switch(choice)case 1:printf("你選擇的是冒泡排序n");printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)n");scanf("%d",&num);printf(

22、"排序前的數(shù)據(jù)n");produce_data(a,num);print_data(a,num);printf("排序過程為:n");order_data(a,num);printf("最終的排序結(jié)果為:n");print_data(a,num);system("pause");system("cls");break;case 2:printf("你選擇的是快速排序n");printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)n");scanf("%d",

23、&num);produce_data(a,num);printf("排序前的數(shù)據(jù)為:n");print_data(a,num);printf("n 排序過程如下：n");QuickSort(a,0,num-1,num);/函數(shù)的調(diào)用printf("n 最終的排序結(jié)果為:n");print_data(a,num);printf("n");system("pause");system("cls");break; case 3:printf("你選擇的是直接插入排序n");printf("請輸入產(chǎn)生數(shù)據(jù)個數(shù)n");scanf("%d",&num);produce_data(a,num);printf("排序前的數(shù)據(jù)為:n");print_data(a,num);printf("排序過程為:n");InsertSort(a,num);printf("n 最終的排序結(jié)果為:n");print_data(a,num);system("pause");system("cls