1、word格式整理版學習參考計算機學院數據結構課程設計題目：數據結構排序算法演示系統班級：姓名：學號：同組人姓名：起迄日期：課程設計地點：指導教師： 評閱意見:成績評定:日期:評閱人:完成日期：2014年12月目錄一、課程設計的目的1二、設計內容和要求 1三、數據采取的結構1四、功能模塊詳細設計14.1 詳細設計思想24.1.1 冒泡排序54.1.2 快速排序74.1.3 直接插入排序94.1.4 希爾排序104.1.5 直接選擇排序124.1.6 堆排序144.1.7 歸弁排序17五、總結或心得體會19六、參考文獻20七、附錄201 .設計目的隨著計算機技術的發展，各種排序算法不斷的被提出。排

2、序算法在計算機科 學中有非常重要的意義，且應用很廣泛。在以后的發展中排序對我們的學習和生 活的影響會逐漸增大，很有必要學習排序知識。此次課程設計一方面使自己掌握 排序的知識，另一方面鍛煉一下團隊合作開發系統的能力。2 .設計內容和要求功能要求：(1)界面友好，易與操作?？刹捎貌藛位蚱渌藱C對話方式進行選擇。 實現各種內部排序。包括直接插入排序，冒泡排序，直接選擇排序，希爾排序，快速排序，堆排序，歸并排序。待排序的元素的關鍵字為整數或(字符)。可用隨機數據和用戶輸入數據作測試比較。比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數(關鍵字交換以3次計)。(1)演示程序以人機對話的形式進行。每次

3、測試完畢顯示各種比較指標值的列表，以便比較各種排序的優劣。3 .本設計所采用的數據結構typedef structint key;RecType;4 .功能模塊詳細設計 排序算法演示系統4.1 詳細設計思想主函數：#include<stdio.h>#include<stdlib.h>#include <math.h>排序元素個數# define L 8/# define FALSE 0# define TRUE 1 typedef structint key;RecType;RecType RL;int num;int sum;int sun; /定義排序趟

4、數的全局變量/系統主界面/主函數int main()RecType S100;int i,k;char ch1,ch2,q;printf("ntt*排序算法演示系統*nntt請輸入d待排序白數據：n”,L);for(i=1;i<=L;i+)printf("tt 請輸入第 dth數據:",i);scanf("%d”,&Si.key);getchar();ch1='y'while(ch1='y')printf("ntt菜單n");printf("ntt*n")printf(

5、"ntt * 1 更新排序數據* 2 直接插入排序n");printf("ntt * 3 希爾排 序* 4 冒泡排序n");printf("ntt * 5 快 速 排 序* 6 直接選擇排序n");printf("ntt * 7 堆排 序 * 8 歸 并 排序n");printf("ntt*0出 *n")；printf("ntt*n");printf("ntt 請選擇:");scanf("%c",&ch2);getchar();

6、for(i=1;i<=L;i+)Ri.key=Si.key;switch(ch2)case '1':printf("ntt請輸入d個待排序數據ntt",L);for(i=1;i<=L;i+)scanf("%d”,&Si.key);getchar();printf("tt");printf("ntt數據輸入完畢！")；break;case '2':Insertsort();break;case '3':Shellsort();break;case '4

7、':Bubblesort();break;case '5':ntt");printf("ntt原始數據為(按回車鍵開始排序)：for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");num=0;sun=0;sum=0;Quicksort(1,L);printf("ntt排序最終結果是：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);printf("nt

8、t比較次數是:%dntt",sum);printf("ntt交換次數是：dntt",sun);break;case '6':Selectsort();break;case '7':Heap();break;case '8':Mergesort();break;case '0':ch1='n'break;default:system("cls");/ 清屏printf("ntt 對不起，您輸入有誤，請重新輸入！n");break;if(ch2!=&

9、#39;0')if(ch2='2'|ch2='3'|ch2='4'|ch2='5'|ch2='6'|ch2=7|ch2='8')printf("nntt 排序完畢！");printf("ntt接回車鍵繼續！");q=getchar();if(q!='n')getchar();ch1='n'return 1;n D:Debugyan. exerZ3- .dnrr12345678居居居 居巖居 居居IJ I， r J - J

10、 1 J J I. " i* ， 1數數數數數數hhhhhhhh12345678第第第第第第第第*人入入入入人入請請請請請請請青*1更新排序數據*2直接插入排序* 3希爾排序蕤4冒泡排序* 決速 排序* 6直接選擇排序* 7堆排序*8歸并排序* >艮出 M M：圖一主界面4.1.1 冒泡排序核心思想依次比較相鄰的兩個數，將小數放在前面，大數放在后面，第一輪比較后，最大的數便被放到了最后；第二輪操作前 n-1個數據(假設有n個數據)，依然 是依次比較相鄰的兩個數，將小數放在前面，大數放在后面，倒數第二個數便是 第二大的數；同理第i輪操作前n-i+1的數據(假設i取值是從1開始的)

11、，則 n-i+i位置上的數據為第i大的數據。一共有n-1輪，第i輪比較中共比較n-i 次比較。核心代碼void Bubblesort()int i,j,k,x=0,y=0,m=0;int exchange=TRUE;/ 標志位 exchange 初始化為 TRUE 1printf("ntt原始數據為(按回車鍵開始排序)：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L&&exchange=TRUE;i+)

12、/外層對總的循環次數執行次數exchange=FALSE;for(j=1;j<=L+1-i;j+) /內層相鄰記錄的交換與比較 m+; 比較次數+if(Rj.key<R1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移動次數+m-;/比較次數if(exchange)/輸出語句printf("tt 第刪冒泡排序白結果為：ntt",i);for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf(&q

13、uot;n");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf("%d",y);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);"D:Debugyan.exe1rfl第3趟直接插入排序的結果為:第4趟直接插入排序的結果為:第5趟直接插入排序的結果為:第6趟直接插入排序的結果為:第7趟直接插入

14、排序的結果為:*一AT# 晝羸2 數箜( 次智取1圖二直接插入排序4.1.2 快速排序核心思想首先檢查數據列表中的數據數，如果小于兩個，則直接退出程序。如果有超過兩個以上的數據，就選擇一個分割點將數據分成兩個部分， 小于分割點的數據放在一組，其余的放在另一組，然后分別對兩組數據排序0通常分割點的數據是隨機選取的。這樣無論你的數據是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多核心代碼/遞歸算法實現void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;while(i<j)wh

15、ile(i<j&&R0.key<=Rj.key) / 右側掃描j-;sum+;if(i<j) Ri.key=Rj.key;/ 交換i+；sun+;while(i<j&&Ri.key<R0.key)/左側掃描i+；sum+;if(i<j)Rj.key=Ri.key;/ 交換j-;sun+;Ri.key=R0.key;num+;/輸出語句包括排序的結果及次數printf("tt第刪快速排序白結果為：ntt",num);for(k=1;k<=L;k+) printf("%5d",Rk.k

16、ey);getchar();printf("n");if(low<i-1) Quicksort(low,i-1);/遞歸部分(左側)if(j+1<high) Quicksort(j+1,high);/遞歸部分(右側)圖三快速排序4.1.3 直接插入排序核心思想經過i-1遍處理后，L1.i-1己排好序。第i遍處理僅將Li插入L1.i-1的適當位置，使得L1.i又是排好序的序列。要達 到這個目的，我們可以用順序比較的方法。首先比較Li和Li-1,如果Li-1 < Li,則L1.i已排好序，第i遍處理就結束了； 否則交換Li與Li-1的位置，繼續比較Li-1和L

17、i-2，直到找 到某一個位置j(1 <j <i-1),使得Lj <Lj+1時為止 核心代碼void Insertsort()int i,j,k,m=0,x=0; 初始化比較次數變量m,移動次數變量xprintf("ntt原始數據為：(接回車鍵開始排序)ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/主要運行部分for(i=2;i<=L;i+)if(Ri.key<Ri-1.key)R0=Ri；j=i-1;while(R

18、0.key<Rj.key)Rj+1=Rj；j-;Rj+1=R0;x+;m+;/輸出語句包括排序的結果及次數printf("tt第趟直接插入排序的結果為：ntt",m);for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");printf("n");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf(&q

19、uot;%d",x);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);"D:Debugyan.exe第3趟直接插入排序的結果為: 第4趟直接插入排序的結果為: 第5趟直接插入排序的結果為； 第8趟直接插入排序的結果為*第7趟直接插入排序的結果為:3 是#=羸2 次咨魯 靛動序 比藉圖四直接插入排序4.1.4 希爾排序核心思想先取一個小于n的整數di作為第一個增量，把文件的全部記錄分成di個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接

20、插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量 dt=1(dt<dt- l< - <d2< di),即所有記錄放在同一組中進行直 接插入排序為止。核心代碼void Shellsort()int i,j,gap,x,k,y=0,m=0; /初始化比較次數變量m移動次數變量yntt");printf("ntt原始數據為：(接回車鍵開始排序)for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/函數主要部分gap

21、=Lwhile(gap>0)for(i=gap+1;i<=L;i+)j=i-gap；while(j>0)if(Rj.key>Rj+gap.key)x=Rj.key;/交換語句Rj.key=Rj+gap.key;Rj+gap.key=x； j=j-gap；y+;/移動次數+elsej=0;gap=gapm+;/比較次數+ntt",m);/輸出語句包括排序的結果及次數printf("tt第趟希爾排序的結果為:for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n

22、");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf("%d",y);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");圖五希爾排序4.1.5 直接選擇排序核心思想第一次從R0Rn-1中選取最小值，與 R0交換，第二次從R1Rn-1中選取最小值，與R2交換，.，

23、第i次從Ri-1Rn-1中選取最小值，與 Ri-1交換，.，第n-1次從Rn-2Rn-1中選取最小值，與Rn-2交換，總共通過n-1次，得到一個按排序碼從小到大排列 的有序序列.核心代碼void Selectsort()int i,j,k,h,x=0,y=0;printf("ntt 原始數據為(按回車鍵開始排序)：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L;i+)h=i;for(j=i+1;j<=L;j+)x

24、+;/比較次數if(Rj.key<Rh.key)h=j;/確定最小值if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/移動次數printf("tt第刪選擇排序白結果為：ntt",i);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/輸出語句包括排序的結果及次數printf("ntt比較次數：%d",x);printf("ntt移動次數：%d",y);pri

25、ntf("ntt排序最終 2果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");圖六選擇排序4.1.6 堆排序 核心思想堆排序是一樹形選擇排序，在排序過程中，將 R1.N看成是一顆完全二叉 樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選 擇最小的元素。將原始記錄序列建成一個堆，成為初始堆，并輸出堆頂元素；調 整剩余的記錄序列，使之成為一個新堆，再輸出堆頂元素；如此反復進行，當堆 中只有一個元素時，整個序列的排序結束，輸出的序列便是原始序列的非

26、遞減有 序序列。在堆排序的過程中，主要負責兩方面的工作：一是如何將原始記錄序列 構造成一個堆，即建立初始堆；二是輸出堆頂元素后，如何將剩余記錄整理成一 個新堆。核心代碼void CreateHeap(int root,int index,int *x,int *y)int j,temp,finish;j=2*root;/j指向左孩子temp=Rroot.key;finish=0;while(j<=index&&finish=0)if(j<index)if(Rj.key<Rj+1.key)j+；/指向較大的孩子if(temp>=Rj.key)finish=

27、1;elseRj/2.key=Rj.key;(*y)+;j=j*2;*x = *x+2;Rj/2.key=temp;(*y)+;/堆排序void Heapsort()int i,j,temp,k,x=0,y=0;for(i=(L/2);i>=1;i-) /建立初始堆CreateHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;i>=1;i-,k+) /將堆中根節點和最后一個節點交換temp=Ri+1.key;Ri+1.key=R1.key;R1.key=temp;CreateHeap(1,i,&x,&y);printf(&q

28、uot;tt第趟堆排序的結果為：ntt",k);for(j=1;j<=L;j+)printf("%5d",Rj.key);getchar();printf("n");printf("ntt比較次數是：dtt",x);printf("ntt移動次數是：dtt",y);void Heap()int i;printf("ntt 原始數據為(按回車鍵開始排序)：ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);getchar

29、();printf("n");Heapsort();printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");void Merge(int low,int mm,int high,int *x,int *y)/兩個有序序列的合并int i=low,j=mm+1,p=0;RecType *R1; /i對第一個開始到結尾，j從第二個開始到結尾R1=new RecTypehigh-low+1;if(!R1)printf(&qu

30、ot;內存不足！");while(i<=mm&&j<=high)兩序列從起始位置開始將小的元素放入到R1中R1p+=(Ri.key<=Rj.key)?Ri+:Rj+;(*x)+;(*y)+;)while(i<=mm)/第二段結束，剩余放入R1中(R1p+=Ri+;(*y)+;)while(j<=high)/第二段剩余，剩余放入R1中(R1p+=Rj+;(*y)+;)for(p=0,i=low;i<=high;p+,i+)/剩余元素放入 R1 中，賦予 R(Ri=R1p;(*y)+;)D:ID e b ugya n .exe"

31、;第3趟堆排序的結果為, 4512431S536?76第4趟堆排序的結果為：43125145S36776第弓趟堆排序的結果為： 121543 4s536?76第6趟堆排序的結果為. 511243第7趟堆排序的結果為.n64S4318151:12 曰蠢5 次咨取1續 畢鍵 完車 序回：圖七堆排序4.1.7歸并排序核心思想將有n個記錄的原始序列看作n個有序子序列，每個子序列的長度為1,然后從第一個子序列開始，把相鄰的子序列兩兩合并，得到 n/2個長度為2或1的子序列(當子序列個數為奇數時，最后一組合并得到的序列長度為1),把這一過程稱為一次歸并排序，對第一次歸并排序后的n/2個子序列采用上述方法繼

32、續順序成對歸并，如此重復，當最后得到的長度為n的一個子序列時，該子序列便是原始序列歸并排序后的有序序列。核心代碼void MergePass(int length,int *x,int *y)/一次二路歸并排序 int i;for(i=1;i+2*length-1<=L;i=i+2*length) Merge(i,i+length-1,i+2*length-1,x,y); 函數調用if(i+length-1<L) Merge(i,i+length-1,L,x,y); 函數調用/歸并排序void Mergesort() / 二路歸并排序 int length,k,m=0,i,x=0,

33、y=0;printf("ntt 原始數據為(按回車鍵開始排序)：ntt");for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");for(length=1;length<L;length*=2) MergePass(length,&x,&y);m+; /輸出語句包括排序的結果及次數printf("tt第趟歸并排序的結果為：ntt",m);for(k=1;k<=L;k+) printf("%5d",

34、Rk.key);getchar();printf("n");printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);printf("n");printf("tt比較次數：dn",x);printf("tt移動次數：dn",y);fD:De bugyan.exe"請選擇唱原始數據為（按回車鍵開始排序）：124567143第1趟歸并排序的結果為:12451674376第2趟歸并排序的結果為:11

35、2456743第三趟歸并排序的結果為:124345536776排序最終結果是:1 E 1243S367續悵畢鍵 完車 序回=圖八歸并排序五.總結或心得回顧這個設計過程，我學到了許多書本上沒有學到的知識。通過這次小組制作的程序，豐富了自己的實踐技能，擴展了本專業的知識面，使我受益非淺，同時 也體驗到了搞軟件開發的困難度。在這次設計的同時我又從中學到了許多東西。但由于我對這樣的排序系統還只是一個開始， 了解的不多，這其中或許還有很多 的不足，在這里也懇請各位老師能夠對我們的作品指明不足并加以改正?？傊?， 在這一次的課程設計過程中，我們查閱了大量的資料，對數據結構有了一點初步 的認識，對于網絡工程這

36、些輔助性的教材也鞏固了不少， 為我們這次的課設提供 了很大的幫助，鍛煉了我們的能力，讓我更加熟練了這門程序設計語言：C/C+語言，系統地學習了數據結構方面的知識，并更進一步提高了我們在程序設計、 調試方面的技巧。更重要的是，它還讓我們認識到了自己的不足，在編程方面， 我僅僅是剛剛入門而已，以后的道路任重道遠，需要我不斷的豐富自己、充實自 己，這樣才能在程序設計方面有所收獲。在最后也感謝我們的小組成員，我在他的幫忙下順利的做好自己負責的部分.六.參考文獻嚴蔚敏,吳偉明，數據結構（C語言版），清華大學出版社，2007年:P263-P288七.附錄#include<stdio.h>#in

37、clude<stdlib.h>#include <math.h>#define L 8/排序元素個數#define FALSE 0#define TRUE 1typedef structint key;RecType;RecType RL;int num;int sum;int sun; /定義排序趟數的全局變量/系統主界面void Bubblesort()int i,j,k,x=0,y=0,m=0;int exchange=TRUE;/ 標志位 exchange 初始化為 TRUE 1printf("ntt原始數據為(按回車鍵開始排序)：ntt")

38、;for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L&&exchange=TRUE;i+)/外層對總的循環次數執行次數exchange=FALSE;for(j=1;j<=L+1-i;j+) / m+;/比較次數+if(Rj.key<R1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移動次數+m-;/比較次數if(exchange)/內層

39、相鄰記錄的交換與比較輸出語句printf("tt第刪冒泡排序白結果為：ntt",i);for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf("%d",y);printf("ntt排序最終結果是：ntt");for(i=1;i<=L

40、;i+) printf("%5d",Ri.key);/遞歸算法實現void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;while(i<j)while(i<j&&R0.key<=Rj.key) / 右側掃描j-;sum+;if(i<j) Ri.key=Rj.key;/ 交換i+；sun+;while(i<j&&Ri.key<R0.key)/i+；sum+;if(i<j)Rj.key=Ri.key;/ 交換j-;sun+;R

41、i.key=R0.key;num+;/輸出語句包括排序的結果及次數左側掃描ntt",num);printf("tt第刪快速排序的結果為for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");if(low<i-1) Quicksort(low,i-1);/遞歸部分(左側)if(j+1<high) Quicksort(j+1,high);/遞歸部分(右側)void Insertsort()int i,j,k,m=0,x=0; /初始化比較次數變量m,移動次數

42、變量xprintf("ntt 原始數據為：(接回車鍵開始排序)ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/主要運行部分for(i=2;i<=L;i+)if(Ri.key<Ri-1.key)R0=Ri；j=i-1;while(R0.key<Rj.key)Rj+1=Rj；j-;Rj+1=R0;x+;m+;ntt",m);/輸出語句包括排序的結果及次數printf("tt第趟直接插入排序的結果為:for(k=1

43、;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");printf("n");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf("%d",x);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);vo

44、id Shellsort()int i,j,gap,x,k,y=0,m=0; /初始化比較次數變量m移動次數變量yprintf("ntt原始數據為：(接回車鍵開始排序)ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/函數主要部分gap2;while(gap>0)(for(i=gap+1;i<=L;i+)(j=i-gap;while(j>0)(if(Rj.key>Rj+gap.key)(x=Rj.key;/交換語句Rj.ke

45、y=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/移動次數+ else(j=0;gap=gapm+;/比較次數+/輸出語句包括排序的結果及次數ntt",m);printf("tt第趟希爾排序的結果為:for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");printf("ntt比較次數是：tt");printf("%d",m);printf("ntt移動次數是：tt");printf

46、("%d",y);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");void Selectsort()ntt");int i,j,k,h,x=0,y=0;printf("ntt原始數據為(按回車鍵開始排序)：for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<

47、;L;i+)h=i;for(j=i+1;j<=L;j+)x+;/比較次數if(Rj.key<Rh.key)h=j;/確定最小值if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/移動次數printf("tt第d趟選擇排序白結果為：ntt",i);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/輸出語句包括排序的結果及次數printf("ntt比較次數：d",x);printf("ntt移動次數：%d",y);printf("ntt排序最終結果是：ntt");for(i=1;i<=L;i+)p