數(shù)據(jù)結構課程設計--排序算法演示系統(tǒng)

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

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

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

文檔簡介

1、　　計算機學院　　數(shù)據(jù)結構課程設計　　題目：數(shù)據(jù)結構排序算法演示系統(tǒng) 　　班級： 　　姓名：

2、 　　學號： 　　同組人姓名： 　　起迄日期: 　　　　　　　　　　　　　 　　課程設計地點: 　　　　　　　　　　　　　　 <

3、/p>　　指導教師： 　　目錄　　一、課程設計的目的1　　二、設計內容和要求1　　三、數(shù)據(jù)采取的結構1　　四、功能模塊詳細

4、設計1　　4.1 詳細設計思想2　　4.1.1 冒泡排序5　　4.1.2 快速排序7　　4.1.3 直接插入排序9　　4.1.4 希爾排序10　　4.1.5 直接選擇排序12

5、　　4.1.6 堆排序14　　4.1.7歸并排序17　　五、總結或心得體會19　　六、參考文獻20　　七、附錄20<

6、;p>　　一. 設計目的　　隨著計算機技術的發(fā)展，各種排序算法不斷的被提出。排序算法在計算機科學中有非常重要的意義，且應用很廣泛。在以后的發(fā)展中排序對我們的學習和生活的影響會逐漸增大，很有必要學習排序知識。此次課程設計一方面使自己掌握排序的知識，另一方面鍛煉一下團隊合作開發(fā)系統(tǒng)的能力。　　二. 設計內容和要求

7、　　功能要求：　　(1)界面友好，易與操作。可采用菜單或其它人機對話方式進行選擇。　　(2)實現(xiàn)各種內部排序。包括直接插入排序，冒泡排序，直接選擇排序，希爾排序，快速排序，堆排序，歸并排序。　　(3)待排序的元素的關鍵字為整數(shù)或（字符

8、）?？捎秒S機數(shù)據(jù)和用戶輸入數(shù)據(jù)作測試比較。比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)(關鍵字交換以3次計)。　　演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標值的列表，以便比較各種排序的優(yōu)劣。　　三. 本設計所采用的數(shù)據(jù)結構　　typedef struct<p&

9、gt;　　{　　int key;　　}RecType;　　功能模塊詳細設計　　4.1 詳細設計思想

10、　　主函數(shù)：　　#include<stdio.h>　　#include<stdlib.h>　　#include <math.h>　　#define L 8 /

11、/排序元素個數(shù)　　#define FALSE 0　　#define TRUE 1　　typedef struct　　{　　int key;</p&g

12、t;　　}RecType;　　RecType R[L];　　int num; 　　int sum;　　int sun;

13、 //定義排序趟數(shù)的全局變量 　　//系統(tǒng)主界面　　//主函數(shù)　　int main()　　{　　RecType

14、 S[100]; 　　int i,k;　　char ch1,ch2,q;　　printf("\n\t\t***********排序算法演示系統(tǒng)************\n\n\t\t請輸入%d個待排序的數(shù)據(jù)：\n",L);<

15、;p>　　for(i=1;i<=L;i++)　　{　　printf("\t\t請輸入第%dth數(shù)據(jù):",i);　　scanf("%d",&S[i].key);　　getcha

16、r();　　}　　ch1='y';　　while(ch1=='y')　　{ 　　p

17、rintf("\n\t\t 菜單 \n");　　printf("\n\t\t***********************************************\n");　　printf("\n\t\t * 1----

18、----更新排序數(shù)據(jù)* 2--------直接插入排序 \n");　　printf("\n\t\t * 3--------希爾排序* 4--------冒泡排序 \n");　　printf("\n\t\t * 5--------快速排序* 6--------直接選擇排序

19、 \n");　　printf("\n\t\t * 7--------堆排序 * 8--------歸并排序 \n");　　printf("\n\t\t **********0--------退出************ \n");<

20、p>　　printf("\n\t\t********************************************\n");　　printf("\n\t\t請選擇:");　　scanf("%c",&ch2);　　getchar()

21、;　　for(i=1;i<=L;i++)　　{　　R[i].key=S[i].key;　　}　　switch(ch2)<

22、;p>　　{　　case '1':　　printf("\n\t\t請輸入%d個待排序數(shù)據(jù)\n\t\t",L);　　for(i=1;i<=L;i++)

23、　　{　　scanf("%d",&S[i].key);　　getchar();　　printf("\t\t");　　}<

24、;p>　　printf("\n\t\t數(shù)據(jù)輸入完畢！");　　break;　　case '2':　　Insertsort();　　bre

25、ak;　　case '3':　　Shellsort();　　break;　　case '4':</p

26、>　　Bubblesort();　　break;　　case '5':　　printf("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");

27、　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);　　}　　getchar();&

28、lt;p>　　printf("\n");　　num=0;sun=0;sum=0;　　Quicksort(1,L);　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(k=1;k<=L;k++)&

29、lt;/p>　　{　　printf("%5d",R[k].key);　　}　　printf("\n\t\t比較次數(shù)是：%d\n\t\t",sum);

30、　　printf("\n\t\t交換次數(shù)是：%d\n\t\t",sun);　　break;　　case '6':　　Selectsort();

31、;　　break;　　case '7':　　Heap();　　break;　　case

32、 '8':　　Mergesort();　　break;　　case '0':　　ch1='n';</b&

33、gt;　　break;　　default:　　system("cls");//清屏　　printf("\n\t\t對不起，您輸入有誤，請重新輸入！\n");

34、　　break;　　}　　if(ch2!='0')　　{　　if(ch2=='2'|

35、|ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')　　{　　printf("\n\n\t\t排序完畢！");

36、　　printf("\n\t\t按回車鍵繼續(xù)！");　　q=getchar();　　if(q!='\n')　　{　　getchar();&

37、lt;b>　　ch1='n';　　}　　}　　}　　}

38、　　return 1;　　}　　圖一主界面　　4.1.1 冒泡排序　　核心思想

39、　　依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面，第一輪比較后，最大的數(shù)便被放到了最后；第二輪操作前n-1個數(shù)據(jù)（假設有n個數(shù)據(jù)），依然是依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面，倒數(shù)第二個數(shù)便是第二大的數(shù)；同理第i輪操作前n-i+1的數(shù)據(jù)（假設i取值是從1開始的），則n-i+i位置上的數(shù)據(jù)為第i大的數(shù)據(jù)。一共有n-1輪，第i輪比較中共比較n-i次比較。&l

40、t;b>　　核心代碼　　void Bubblesort()　　{　　int i,j,k,x=0,y=0,m=0;　　int exchange=TRUE;//標志位exchange初始化為TRUE 1</

41、p>　　printf("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);

42、　　}　　getchar();　　printf("\n");　　for(i=1;i<L&&exchange==TRUE;i++)//外層對總的循環(huán)次數(shù)執(zhí)行次數(shù)<b&g

43、t;　　{　　exchange=FALSE;　　for(j=1;j<=L+1-i;j++) //內層相鄰記錄的交換與比較　　{ m++;//比較次數(shù)++　　if(R[j].key<R[j-1].key)<p&g

44、t;　　{　　R[0].key=R[j].key;　　R[j].key=R[j-1].key;　　R[j-1].key=R[0].key;　　exchange=TRUE;　　y++;//移動次

45、數(shù)++　　}　　}　　m--;//比較次數(shù)　　if(exchange) //輸出語句　　{</b&

46、gt;　　printf("\t\t第%d趟冒泡排序的結果為：\n\t\t",i);　　for(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}<

47、;/p>　　getchar();　　printf("\n");　　}　　}　　printf("\n\t\t比較次數(shù)是：\t\t"

48、);　　printf("%d",m);　　printf("\n\t\t移動次數(shù)是：\t\t");　　printf("%d",y);　　printf("\n\t\t排序最終結果是：\n\t\t"

49、);　　for(i=1;i<=L;i++)　　{ printf("%5d",R[i].key);　　}　　}

50、　　圖二直接插入排序　　4.1.2 快速排序　　核心思想　　首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，如果小于兩個，則直接退出程序。如果有超過兩個以上的數(shù)據(jù)，就選擇一個分割點將數(shù)據(jù)分成兩個部分，小于分割點的數(shù)據(jù)放在一組，其余的放在另一組，然后分別對兩組數(shù)據(jù)排序。通

51、常分割點的數(shù)據(jù)是隨機選取的。這樣無論你的數(shù)據(jù)是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多　　核心代碼　　//遞歸算法實現(xiàn)　　void Quicksort(int low,int high)</

52、p>　　{ 　　int i=low,j=high,k;　　R[0].key=R[low].key;　　while(i<j)　　{<p

53、>　　while(i<j&&R[0].key<=R[j].key) //右側掃描　　{j--;　　sum++;　　}<

54、;b>　　if(i<j)　　{ R[i].key=R[j].key;//交換　　i++;　　sun++;　　}</p&

55、gt;　　while(i<j&&R[i].key<R[0].key)//左側掃描 　　{i++;　　sum++;　　}<

56、p>　　if(i<j)　　{　　R[j].key=R[i].key;//交換　　j--;　　sun++;&l

57、t;/p>　　}　　}　　R[i].key=R[0].key;　　num++;　　//輸出語句包括排序的結果及次數(shù) </p&

58、gt;　　printf("\t\t第%d趟快速排序的結果為：\n\t\t",num);　　for(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}

59、　　getchar();　　printf("\n");　　if(low<i-1) Quicksort(low,i-1);//遞歸部分(左側)　　if(j+1<high) Quicksort(j+1,high);//遞歸部分(右側)<

60、;p>　　}　　圖三快速排序　　4.1.3 直接插入排序　　核心思想　　經(jīng)過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L

61、[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止　　核心代碼<

62、;/b>　　void Insertsort()　　{　　int i,j,k,m=0,x=0; //初始化比較次數(shù)變量m，移動次數(shù)變量x　　printf("\n\t\t原始數(shù)據(jù)為：（按回車鍵開始排序）\n\t\t&qu

63、ot;);　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);　　}　　getchar

64、();　　printf("\n");　　//主要運行部分　　for(i=2;i<=L;i++)　　{　　if(R[i].key&

65、lt;R[i-1].key)　　{　　R[0]=R[i];　　j=i-1;　　while(R[0].key<R[j].key)

66、{　　R[j+1]=R[j];　　j--;　　}　　R[j+1]=R[0];　　x++;<

67、/p>　　}　　m++;　　//輸出語句包括排序的結果及次數(shù) 　　printf("\t\t第%d趟直接插入排序的結果為：\n\t\t",m);　　f

68、or(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}　　getchar();　　printf("\n");

69、;　　}　　printf("\n");　　printf("\n\t\t比較次數(shù)是：\t\t");　　printf("%d",m);　　printf("\n\t\t移

70、動次數(shù)是：\t\t");　　printf("%d",x);　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(i=1;i<=L;i++)　　{ printf("%5d"

71、,R[i].key);　　}　　}　　圖四直接插入排序　　4.1.4 希爾排序　　核心思想&l

72、t;/b>　　先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。<b&g

73、t;　　核心代碼　　void Shellsort()　　{　　int i,j,gap,x,k,y=0,m=0; //初始化比較次數(shù)變量m，移動次數(shù)變量y　　printf("\n\t\t原始數(shù)據(jù)為：（按

74、回車鍵開始排序）\n\t\t");　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);　　}&

75、lt;p>　　getchar();　　printf("\n");　　//函數(shù)主要部分　　gap=L/2;　　while(gap>0)<

76、p>　　{　　for(i=gap+1;i<=L;i++)　　{　　j=i-gap;　　while(j>0)<p

77、>　　{　　if(R[j].key>R[j+gap].key)　　{　　x=R[j].key;//交換語句　　R[j].key=R[j+gap].key;<

78、;p>　　R[j+gap].key=x;　　j=j-gap;　　y++;//移動次數(shù)++　　}　　else&l

79、t;b>　　{　　j=0;　　}　　}　　}　　ga

80、p=gap/2;　　m++;//比較次數(shù)++　　//輸出語句包括排序的結果及次數(shù) 　　printf("\t\t第%d趟希爾排序的結果為：\n\t\t",m);　　for(k=1;k<=L;k++)<

81、b>　　{　　printf("%5d",R[k].key);　　}　　getchar();　　printf("\n");<

82、;b>　　}　　printf("\n\t\t比較次數(shù)是：\t\t");　　printf("%d",m);　　printf("\n\t\t移動次數(shù)是：\t\t");　　printf(&qu

83、ot;%d",y);　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(i=1;i<=L;i++)　　{　　printf("%5d",R[i].key)

84、;　　}　　printf("\n");　　} 　　圖五希爾排序　　4.1.5 直接選擇排序&

85、lt;/p>　　核心思想　　第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R{1}~R[n-1]中選取最小值，與R[2]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換,總共通過n-1次,得

86、到一個按排序碼從小到大排列的有序序列.　　核心代碼　　void Selectsort()　　{　　int i,j,k,h,x=0,y=0;　　printf

87、("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);　　}&l

88、t;/b>　　getchar();　　printf("\n");　　for(i=1;i<L;i++)　　{　　h=i;&l

89、t;/p>　　for(j=i+1;j<=L;j++)　　{x++; //比較次數(shù)　　if(R[j].key<R[h].key)　　{　　h=j;

90、 //確定最小值　　}　　}　　if(h!=i)　　{&

91、lt;p>　　R[0].key=R[i].key;　　R[i].key=R[h].key;　　R[h].key=R[0].key;　　y++; //移動次數(shù)　　}

92、　　printf("\t\t第%d趟選擇排序的結果為：\n\t\t",i);　　for(k=1;k<=L;k++)　　printf("%5d",R[k].key);　　getchar();　　printf(

93、"\n");　　}　　//輸出語句包括排序的結果及次數(shù) 　　printf("\n\t\t比較次數(shù)：%d",x);　　printf("\n\t\t移動次數(shù)：%d",y);<

94、;/p>　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(i=1;i<=L;i++)　　printf("%5d",R[i].key);　　printf("\n");&l

95、t;p>　　}　　圖六選擇排序　　4.1.6 堆排序　　核心思想　　堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序

96、存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。將原始記錄序列建成一個堆，成為初始堆，并輸出堆頂元素；調整剩余的記錄序列，使之成為一個新堆，再輸出堆頂元素；如此反復進行，當堆中只有一個元素時，整個序列的排序結束，輸出的序列便是原始序列的非遞減有序序列。在堆排序的過程中，主要負責兩方面的工作：一是如何將原始記錄序列構造成一個堆，即建立初始堆；二是輸出堆頂元素后，如何將剩余記錄整理成一個新堆。

97、　　核心代碼　　void CreateHeap(int root,int index,int *x,int *y)　　{　　int j,temp,finish;　　j=2*r

98、oot; //j指向左孩子　　temp=R[root].key;　　finish=0;　　while(j<=index&&finish==0)

99、;　　{　　if(j<index)　　{　　if(R[j].key<R[j+1].key)　　{　　j+

100、+;　　}　　} //指向較大的孩子　　if(temp>=R[j].key)　　{

101、　　finish=1;　　}　　else　　{　　R[j/2].key=R[j].key;<

102、/p>　　(*y)++;　　j=j*2;　　}　　*x = *x+2;　　}</p&g

103、t;　　R[j/2].key=temp;　　(*y)++;　　}　　//堆排序　　void Heapsort()

104、　　{　　int i,j,temp,k,x=0,y=0;　　for(i=(L/2);i>=1;i--) //建立初始堆　　{　　CreateHeap(i,L,&

105、x,&y);　　}　　x=0;　　y=0;　　for(i=L-1,k=1;i>=1;i--,k++) //將堆中根節(jié)點和最后一個節(jié)點交換<

106、;/p>　　{　　temp=R[i+1].key;　　R[i+1].key=R[1].key;　　R[1].key=temp;　　CreateHeap(1,i,&x,&y);</p&g

107、t;　　printf("\t\t第%d趟堆排序的結果為：\n\t\t",k);　　for(j=1;j<=L;j++)　　{　　printf("%5d",R[j].key);<p&

108、gt;　　}　　getchar();　　printf("\n");　　}　　printf("\n\t\t比較次數(shù)是：%d\t\t",x);

109、;　　printf("\n\t\t移動次數(shù)是：%d\t\t",y);　　}　　void Heap()　　{　　int i;</b&

110、gt;　　printf("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");　　for(i=1;i<=L;i++)　　{　　printf("%5d",R[i].key);<

111、;/p>　　}　　getchar();　　printf("\n");　　Heapsort();　　printf("\n\t\t排序最終結果是：\n\t\t");<

112、;/p>　　for(i=1;i<=L;i++)　　{　　printf("%5d",R[i].key);　　}　　printf("\n

113、");　　}　　void Merge(int low,int mm,int high,int *x,int *y)//兩個有序序列的合并　　{　　int i=low,j=mm+1,p=0

114、;　　RecType *R1; //i對第一個開始到結尾，j從第二個開始到結尾　　R1=new RecType[high-low+1];　　if(!R1)　　{<

115、p>　　printf("內存不足！");　　}　　while(i<=mm&&j<=high)//兩序列從起始位置開始將小的元素放入到R1中　　{

116、;　　R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];　　(*x)++;　　(*y)++;　　}　　while(i

117、<=mm)//第二段結束，剩余放入R1中　　{　　R1[p++]=R[i++];　　(*y)++;　　}　　w

118、hile(j<=high)//第二段剩余，剩余放入R1中　　{　　R1[p++]=R[j++];　　(*y)++;　　}<

119、p>　　for(p=0,i=low;i<=high;p++,i++)//剩余元素放入R1中,賦予R　　{　　R[i]=R1[p];　　(*y)++;　　}</b

120、>　　}　　圖七堆排序　　4.1.7 歸并排序　　核心思想　　將有n個記錄的原始序列看作n個有序子序列，每

121、個子序列的長度為1，然后從第一個子序列開始，把相鄰的子序列兩兩合并，得到[n/2]個長度為2或1的子序列（當子序列個數(shù)為奇數(shù)時，最后一組合并得到的序列長度為1），把這一過程稱為一次歸并排序，對第一次歸并排序后的[n/2]個子序列采用上述方法繼續(xù)順序成對歸并，如此重復，當最后得到的長度為n的一個子序列時，該子序列便是原始序列歸并排序后的有序序列。　　核心代碼&

122、lt;/p>　　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

123、+length-1,i+2*length-1,x,y); //函數(shù)調用　　}　　if(i+length-1<L)　　{ Merge(i,i+length-1,L,x,y); //函數(shù)調用　　}</b&

124、gt;　　}　　//歸并排序　　void Mergesort() //二路歸并排序　　{ int length,k,m=0,i,x=0,y=0;　　pri

125、ntf("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");　　for(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}　　getcha

126、r();　　printf("\n");　　for(length=1;length<L;length*=2)　　{ MergePass(length,&x,&y);　　m++; //輸出語句包括排序的結果及次數(shù)

127、　　printf("\t\t第%d趟歸并排序的結果為：\n\t\t",m);　　for(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}<

128、p>　　getchar();　　printf("\n");　　}　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(i=1;i<=L;i++)</p&

129、gt;　　{ printf("%5d",R[i].key);　　}　　printf("\n");　　printf("\t\t比較次數(shù)：%d\n",x);

130、;　　printf("\t\t移動次數(shù)：%d\n",y);　　}　　圖八歸并排序　　總結或心得　　回顧這個設計過程,我學到了許多書本上沒

131、有學到的知識。通過這次小組制作的程序,豐富了自己的實踐技能,擴展了本專業(yè)的知識面,使我受益非淺,同時也體驗到了搞軟件開發(fā)的困難度。在這次設計的同時我又從中學到了許多東西。但由于我對這樣的排序系統(tǒng)還只是一個開始，了解的不多，這其中或許還有很多的不足,在這里也懇請各位老師能夠對我們的作品指明不足并加以改正。總之，在這一次的課程設計過程中，我們查閱了大量的資料，對數(shù)據(jù)結構有了一點初步的認識，對于網(wǎng)絡工程這些輔助性的教材也鞏固了不少，為我們這次

132、的課設提供了很大的幫助，鍛煉了我們的能力,讓我更加熟練了這門程序設計語言：C/C++語言，系統(tǒng)地學習了數(shù)據(jù)結構方面的知識，并更進一步提高了我們在程序設計、調試方面的技巧。更重要的是，它還讓我們認識到了自己的不足，在編程方面，我僅僅是剛剛入門而已，以后的道路任重道遠，需要我不斷的豐富自己、充實自己，這樣才能在程序設計方面有所收獲。在最后也感謝我們的小組成員,我在他的幫忙下順利的做好自己負責的部分.

133、　　六．參考文獻　　嚴蔚敏,吳偉明,《數(shù)據(jù)結構(C語言版)》,清華大學出版社,2007年:P263-P288。　　七．附錄　　#include<stdio.h>　　#include&l

134、t;stdlib.h>　　#include <math.h>　　#define L 8 //排序元素個數(shù)　　#define FALSE 0　　#define TRUE 1　　typedef s

135、truct　　{　　int key;　　}RecType;　　RecType R[L];　　int

136、 num; 　　int sum;　　int sun; //定義排序趟數(shù)的全局變量 　　//系統(tǒng)主界面　　void Bubblesort()</p&

137、gt;　　{　　int i,j,k,x=0,y=0,m=0;　　int exchange=TRUE;//標志位exchange初始化為TRUE 1　　printf("\n\t\t原始數(shù)據(jù)為（按回車鍵開始排序）：\n\t\t");<

138、;/p>　　for(k=1;k<=L;k++)　　{　　printf("%5d",R[k].key);　　}　　getchar();</

139、p>　　printf("\n");　　for(i=1;i<L&&exchange==TRUE;i++)//外層對總的循環(huán)次數(shù)執(zhí)行次數(shù)　　{　　exchange=FALSE;<p

140、>　　for(j=1;j<=L+1-i;j++) //內層相鄰記錄的交換與比較　　{ m++;//比較次數(shù)++　　if(R[j].key<R[j-1].key)　　{　　R[0].key=R[j].key;</

141、p>　　R[j].key=R[j-1].key;　　R[j-1].key=R[0].key;　　exchange=TRUE;　　y++;//移動次數(shù)++　　}<

142、;b>　　}　　m--;//比較次數(shù)　　if(exchange) //輸出語句　　{　　printf("\t\t第%d趟冒泡排序的結果為：\n\t\t",i

143、);　　for(k=1;k<=L;k++)　　{ printf("%5d",R[k].key);　　}　　getchar();　　printf("\n&q

144、uot;);　　}　　}　　printf("\n\t\t比較次數(shù)是：\t\t");　　printf("%d",m);

145、;　　printf("\n\t\t移動次數(shù)是：\t\t");　　printf("%d",y);　　printf("\n\t\t排序最終結果是：\n\t\t");　　for(i=1;i<=L;i++)　　{

146、 printf("%5d",R[i].key);　　}　　}　　//遞歸算法實現(xiàn)　　void Quicksort(int low,int

147、high)　　{ 　　int i=low,j=high,k;　　R[0].key=R[low].key;　　while(i<j)　　{</p&

148、gt;　　while(i<j&&R[0].key<=R[j].key) //右側掃描　　{j--;　　sum++;　　}&l

149、t;p>　　if(i<j)　　{ R[i].key=R[j].key;//交換　　i++;　　sun++;　　}</b&

150、gt;　　while(i<j&&R[i].key<R[0].key)//左側掃描 　　{i++;　　sum++;　　}</p

151、>　　if(i<j)　　{　　R[j].key=R[i].key;//交換　　j--;　　sun++;&l

152、t;/b>　　}　　}　　R[i].key=R[0].key;　　num++;　　//輸出語句包括排序的結果及

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

溫馨提示

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

數(shù)據(jù)結構課程設計--排序算法演示系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計--排序算法演示系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

免費下載