《數(shù)據(jù)結構》 內(nèi) 排 序 算 法

1、 數(shù)據(jù)結構課程設計報告設計題目 內(nèi) 排 序 算 法 學院名稱 專 業(yè) 班 級 姓 名 學 號 目錄 一、 實驗題目 1 內(nèi)排序算法1 二、問題描述1 三、設計目標1 四、需求分析1五、概要設計1六、函數(shù)2 流程圖3七、測試分析4八、使用說明7九、課程設計總結8 十、附錄（各功能函數(shù)源代碼）91、 實驗題目 內(nèi)排序算法二、問題描述要求從外部文件讀入或直接輸入數(shù)據(jù)，編寫一程序，通過插入、選擇、交換、歸并、基數(shù)等方法進行數(shù)據(jù)的排序。三、設計目標設計一個程序，利用內(nèi)排序各算法，如直接插入、希爾、冒泡、直接接擇、基數(shù)、歸并、堆排序等算法進行數(shù)據(jù)排序，輸出每趟排序結果，讓排序算法更加明了，大大提高排序效率

2、，縮短時間的花費。 四、需求分析本次試驗主要分為以下四大功能模塊：1) 頭文件：定義全局變量，申明函數(shù)；2) 菜單：各排序算法的分類；3) 算法：對不同算法的描述定義；4) 主函數(shù)：定義局部變量，調用各函數(shù)。五、概要設計1、各個模塊功能的詳細描述void insetsort(int b,int n);/直接插入void sheelsort(int b,int n);/希爾排序void binarysotr(int b,int n);/折半插入排序void selectsort(int b,int n);/簡單選擇排序void heapsort(int b,int n);/堆排序（完全二叉樹）v

3、oid bubblesort(int b,int n);/冒泡排序void quicksort(int b,int low,int high);/快速排序void Merge(int a,int low,int mid,int high,int b);/歸并排序 void jishu(int b,int n);/基數(shù)排序2、 系統(tǒng)結構功能圖六、函數(shù) 1、頭文件13、 a、h.h#include#include#include#include#include#define N 10000int g_flag;b、“head.h”#include#include#include#include#i

4、nclude#define MaxKeyNum 12/ 最大關鍵字個數(shù)#define Radix 10 /關鍵字的基數(shù)#define MaxSize 80/元素的個數(shù)typedef int KeyType;/關鍵字類型為int 型typedef structchar keyMaxKeyNum;int next;SListCell;/每個元素的關鍵字類型typedef structSListCell dataMaxSize;int keynum,len;/關鍵字的個數(shù)及靜態(tài)鏈表的長度SList;/靜態(tài)鏈表類型typedef int addrRadix;/定義靜態(tài)指針數(shù)組類型typedef str

5、uctKeyType key;DataType;/元素類型*/SList L;DataType aMaxKeyNum;2、主函數(shù)#includeh.h#includefp.c#includemudex.c#includeRad#includesort1.cvoid main()int g_flag;int bN,n;char ch;ixsort.cg_flag=0;15n=reaData(b);system(mode con: cols=170 );/調整屏幕顯示大小 列、行while(1)switch(nume()ch=getchar();case 1:switch(insetr_mu()c

6、ase a:insetsort( b, n);printData(b,n);system(pause);break;case b: sheelsort( b, n);/希爾排序/123break;case c:binarysotr(b, n);/折半插入排序break;break;case 2:switch(sele_mu()case i: selectsort( b, n);/簡單選擇排序/ 123 printData(b,n);system(pause);break;case k: heapsort(b, n);/堆排序（完全二叉樹）/123break;break;case 3:switc

7、h(change_mu()case !: bubblesort( b, n);/冒泡排序 printData(b,n);system(pause);break;case y: quicksort( b, 0, n-1);/快速排序break;break;case 4: MergeSort( b,n);/對數(shù)組中a元素進行歸并排序 printData(b,n);system(pause);break;case 5: jishu(b,n); printData(b,n);system(pause);break;default:printf(error);break; 2、 流程圖1.求最大值3、載

8、入數(shù)據(jù)2.文件的有關操作4.直接插入排序5.希爾排序6.折半插入7.簡單選擇排序8.堆調整七、測試分析白盒：黑盒：a.顯示主菜單；b選擇“1.插入類”；C.選擇”a.直接插入排序”；結論：正常。a.顯示主菜單；b選擇“2.選擇類”；C.選擇“k.直接插入排序”；結論：正常。a.顯示主菜單；b選擇“3.交換”；C.選擇”！快速排序”；結論：正常。a.顯示主菜單；b選擇“4.歸并”；結論：正常。a.顯示主菜單；b選擇“5.基數(shù)”；結論：正常。八、使用說明 運行程序，在菜單界面，根據(jù)菜單的提示選擇您想要實現(xiàn)的功能： 1：插入類排序； a：直接插入類排序； b：折半排序； c：希爾排序； 2：選擇類排

9、序；i：簡單選擇排序；k：堆排序；3：交換類排序；?。嚎焖倥判颍粂：冒泡排序；4：歸并類排序；5：基數(shù)排序。九、課程設計總結 通過不斷做課程設計，逐次有了一定的進步。在這次課程設計中，又有了新的認識、理解，對于寫程序，首先自己得先明確程序的目的，然后寫一個大的框架，逐步向其添加實現(xiàn)自己想實現(xiàn)的功能的代碼，對于每一行程序代碼，要明白它是要實現(xiàn)哪一步，有什么功能，盡量的精簡代碼，讓程序的效率提高。當自己沒有思路時，也可以去“繼承”別人的代碼，對于現(xiàn)成的代碼，理解上就得嚴格把關，多次去想代碼的運行，思路跟隨代碼，仔細的將代碼大體化，進而細化，在這個過程中，調試是一個很好的方法，每一步的調試，都可以清

10、楚的了解每一個變量隨時變化的值，以便能徹底的了解程序。實在是不能理解，就可以動手寫，將程序代碼的每一步執(zhí)行運算后的結果寫在紙上，通過不斷的對比去加深對代碼的理解與運用。與此同時，也要和別人交流，講出你的代碼，在別人不斷的疑問與你的解答中，你會收獲頗多，真正的讓你知道你的不足！進而深層次的挖掘代碼。十、附錄（各功能函數(shù)源代碼）1、文件的操作#includeint g_flag;int reaData(int d)FILE * fp;int i = 0;int ch;fp = fopen(data.txt, r);if (NULL = fp)return -1;while (!feof(fp)fs

11、canf(fp, %d, &ch); di=ch;i+;g_flag = 1;fclose(fp);return i;int printData(int d,int n)int i = 0;if (g_flag1)printf(請先載入數(shù)據(jù)文件。n);return 0;for (; in; i+)printf(%dt, di);if(i+1)%10=0)printf(n);return 0;1、 菜單#includeint nume()int x;printf(nn);system(cls);printf(ttttttn);printf(tttttt 排序簡介圖 n);printf(ttttt

12、t 注：由上而下! n);printf(ttttttn);printf(tttttt n);printf(tttttt * 內(nèi)排序算法 * n);printf(tttttt * n);printf(tttttt *1插入類* * *3交換* n);printf(tttttt * *2選擇類* *n);printf(tttttt * n);printf(tttttt *堆* n); printf(tttttt * *n); printf(tttttt * *簡單* *快速* n); printf(tttttt *希爾* * *n); printf(tttttt * n); printf(tttt

13、tt * n);printf(tttttt * *冒泡* n);printf(tttttt *直接* * n);printf(tttttt * *4歸并* n); printf(tttttt* * n);printf(tttttt *折半* *5基數(shù)* n);printf(tttttt* n); printf(ttttttn);printf(nnnn);printf(輸入你想要的排序方法：);scanf(%d,&x);if(x6)printf(輸入有誤！請重新輸入(15);scanf(%d,&x);return x;char insetr_mu()char x;printf(ttttttn);

14、printf(tttttt插入類排序n);printf(tttttt n);printf(tttttt a.直接插入排序 n);printf(tttttt n);printf(tttttt b.折半排序 n);printf(tttttt n);printf(tttttt c.希爾排序 n);printf(ttttttn);printf(輸入你想要的插入類排序方法：);scanf(%s,&x);printf(n);if(x!=a & x!=b & x!=c)printf(輸入有誤！請重新輸入!或!);scanf(%c,&x);return x; char sele_mu() char x;pri

15、ntf(ttttttn);printf(tttttt選擇類排序類排序n);printf(tttttt n);printf(tttttt i.簡單選擇排序 n);printf(tttttt n);printf(tttttt k.堆排序 n);printf(ttttttn);printf(輸入你想要的選擇類排序方法：);scanf(%s,&x);printf(n);if(x!=i & x!=k)printf(輸入有誤！請重新輸入i或k);scanf(%s,&x);return x;char change_mu()char x;printf(ttttttn);printf(tttttt交換排序類排序

16、 n);printf(tttttt n);printf(tttttt !.快速排序 n);printf(tttttt n);printf(tttttt y.冒泡排序 n);printf(ttttttn);printf(輸入你想要的交換類排序方法：);scanf(%s,&x);printf(n);if(x!=! & x!=y)printf(輸入有誤！請重新輸入!或y);scanf(%s,&x);return x;3、排序#include /*插入類排序*/void insetsort(int b,int n)/直接插入排序int i,j,t;for(i=1;i0&t=1;delta/=2)for

17、(i=delta;i=0&bjt)bj+delta=bj;j-=delta;bj+delta=t;void binarysotr(int b,int n)/折半插入排序int low,high,mid,i,j,t;for(i=1;in;i+)low=0;high=i-1;t=bi;while(low=high)mid=(low+high)/2;if(tlow;j-)bj=bj-1;blow=t; /*選擇類排序*/void selectsort(int b,int n)/簡單選擇排序int i,j,k,t;for(i=0;in;i+)k=i;/i被認為當前趟最小的元素的下標for(j=i+1;

18、jbj)k=j;/找出當前趟最小元素下標記為kif(k!=i)t=bi;/當認為的和實際找到的最小元素的下標不等時，則交換bi=bk;bk=t;void adjustheap(int b,int s,int n)/從編號s開始調整int i,j,t,flag;i=s;j=2*i+1;t=bi;flag=0;while(jn & !flag)if(jn-1 & bjbj)/如果根結點元素值大于孩子結點flag=1;else/逐層調整元素的位置bi=bj;i=j;j=2*i+1;bi=t;/將根結點存放到相應的位置void heapsort(int b,int n)/堆排序（完全二叉樹）int i

19、,t;for(i=n/2-1;i=0;i-)/從n/2開始建立堆adjustheap(b,i,n);for(i=n-1;i0;i+)t=b0;b0=bi;bi=t;adjustheap(b,0,i);/從根結點開始調整 /*交換類排序*/void bubblesort(int b,int n)/冒泡排序int i,j,t;for(i=0;in;i+)for(j=0;jbj+1)t=bj;bj=bj+1;bj+1=t;printf(第%d趟排序結果：,i+1);for(j=0;jn;j+)if(j+1)%50=0)printf(%4dt,bj);printf(n);printf(%4dt,bj)

20、;printf(n);void quicksort(int b,int low,int high)/快速排序int i,j,pivot;i=low;j=high;pivot=blow;while(ij)while(ij & pivot=bj)j-;if(ij)bi=bj;i+;while(ij & bipivot)i+;if(ij)bj=bi;j-;bi=pivot;if(lowi)quicksort(b,low,i-1);if(ihigh)quicksort(b,j+1,high); /* 歸并排序 */void Merge(int a,int low,int mid,int high,in

21、t b)int i,j,k;i=low;j=mid+1;k=low;while(i=mid & j=high)if(ai=aj)bk=ai;i+;else bk=aj;j+;k+;while(i=mid)bk+=ai+;while(j=high)bk+=aj+;void MSort(int a,int low,int high,int c) clow.high中int bN,mid;if(low=high)clow=alow;else mid=(low+high)/2;MSort(a,low,mid,b);/遞歸的將alow.high歸并為有序的blow.highMSort(a,mid+1,h

22、igh,b);Merge(b,low,mid,high,c);/將alow.mid和cmid.high歸并到clow.highvoid MergeSort(int a,int n)/對數(shù)組中a元素進行歸并排序MSort(a,0,n-1,a);#include#includehead.h /* 基數(shù)排序*/oid InitList(SList *L,DataType a,int n)/利用數(shù)組a的元素初始化靜態(tài)鏈表Lchar str10,str210;int i,j,max=a0.key;for(i=1;in;i+)/求元素關鍵字的個數(shù)if(maxkeynum=(int)(log10(max)+

23、1;/求每個元素關鍵字的個數(shù)L-len=n;/靜態(tài)鏈表的長度for(i=1;in;i+)/將整型轉化為字符串，不夠位數(shù)的補足位數(shù)itoa(ai-1.key,str,10);/將元素轉化為字符串for(j=strlen(str);jkeynum;j+)/將不足位數(shù)上補0strcpy(str2,0);strcat(str2,str);strcpy(str,str2);/將每個元素上的每一位作為關鍵字存入成員key中for(j=0;jkeynum;j+)L-datai.keyj=strL-keynum-1-j;/xiancunfang個位上的數(shù)/構建靜態(tài)鏈表for(i=0;ilen;i+)L-dat

24、ai.next=i+1;L-dataL-len.next=0;/最后一個元素的指針域為0int Translate(char ch)/將字符轉換為整型return ch-0;void Distribute(SListCell data,int i,addr f,addr r,int n) /將數(shù)組data中的元素根據(jù)關鍵字建立Radix個子表，同一子表中keyi的相同int j,k,m=0;for(j=0;j=n-1)break; void Collect(SListCell data,addr f,addr r)/根據(jù)將各個子表鏈接成一個靜態(tài)鏈表int j,k;for(j=0;!fj;j+)NULL;data0.next