《數(shù)據(jù)結(jié)構(gòu)》 內(nèi) 排 序 算 法

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

2、，縮短時(shí)間的花費(fèi)。 四、需求分析本次試驗(yàn)主要分為以下四大功能模塊：1) 頭文件：定義全局變量，申明函數(shù)；2) 菜單：各排序算法的分類；3) 算法：對(duì)不同算法的描述定義；4) 主函數(shù)：定義局部變量，調(diào)用各函數(shù)。五、概要設(shè)計(jì)1、各個(gè)模塊功能的詳細(xì)描述void insetsort(int b,int n);/直接插入void sheelsort(int b,int n);/希爾排序void binarysotr(int b,int n);/折半插入排序void selectsort(int b,int n);/簡(jiǎ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)結(jié)構(gòu)功能圖六、函數(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/ 最大關(guān)鍵字個(gè)數(shù)#define Radix 10 /關(guān)鍵字的基數(shù)#define MaxSize 80/元素的個(gè)數(shù)typedef int KeyType;/關(guān)鍵字類型為int 型typedef structchar keyMaxKeyNum;int next;SListCell;/每個(gè)元素的關(guān)鍵字類型typedef structSListCell dataMaxSize;int keynum,len;/關(guān)鍵字的個(gè)數(shù)及靜態(tài)鏈表的長(zhǎng)度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 );/調(diào)整屏幕顯示大小 列、行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);/簡(jiǎ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);/對(duì)數(shù)組中a元素進(jìn)行歸并排序 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.文件的有關(guān)操作4.直接插入排序5.希爾排序6.折半插入7.簡(jiǎn)單選擇排序8.堆調(diào)整七、測(cè)試分析白盒：黑盒：a.顯示主菜單；b選擇“1.插入類”；C.選擇”a.直接插入排序”；結(jié)論：正常。a.顯示主菜單；b選擇“2.選擇類”；C.選擇“k.直接插入排序”；結(jié)論：正常。a.顯示主菜單；b選擇“3.交換”；C.選擇”！快速排序”；結(jié)論：正常。a.顯示主菜單；b選擇“4.歸并”；結(jié)論：正常。a.顯示主菜單；b選擇“5.基數(shù)”；結(jié)論：正常。八、使用說明 運(yùn)行程序，在菜單界面，根據(jù)菜單的提示選擇您想要實(shí)現(xiàn)的功能： 1：插入類排序； a：直接插入類排序； b：折半排序； c：希爾排序； 2：選擇類排

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

10、楚的了解每一個(gè)變量隨時(shí)變化的值，以便能徹底的了解程序。實(shí)在是不能理解，就可以動(dòng)手寫，將程序代碼的每一步執(zhí)行運(yùn)算后的結(jié)果寫在紙上，通過不斷的對(duì)比去加深對(duì)代碼的理解與運(yùn)用。與此同時(shí)，也要和別人交流，講出你的代碼，在別人不斷的疑問與你的解答中，你會(huì)收獲頗多，真正的讓你知道你的不足！進(jìn)而深層次的挖掘代碼。十、附錄（各功能函數(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(請(qǐng)先載入數(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 排序簡(jiǎn)介圖 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 * *簡(jiǎn)單* *快速* 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(輸入有誤！請(qǐng)重新輸入(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(輸入有誤！請(qǐng)重新輸入!或!);scanf(%c,&x);return x; char sele_mu() char x;pri

15、ntf(ttttttn);printf(tttttt選擇類排序類排序n);printf(tttttt n);printf(tttttt i.簡(jiǎn)單選擇排序 n);printf(tttttt n);printf(tttttt k.堆排序 n);printf(ttttttn);printf(輸入你想要的選擇類排序方法：);scanf(%s,&x);printf(n);if(x!=i & x!=k)printf(輸入有誤！請(qǐng)重新輸入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(輸入有誤！請(qǐng)重新輸入!或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)/簡(jiǎn)單選擇排序int i,j,k,t;for(i=0;in;i+)k=i;/i被認(rèn)為當(dāng)前趟最小的元素的下標(biāo)for(j=i+1;

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

19、,t;for(i=n/2-1;i=0;i-)/從n/2開始建立堆a(bǔ)djustheap(b,i,n);for(i=n-1;i0;i+)t=b0;b0=bi;bi=t;adjustheap(b,0,i);/從根結(jié)點(diǎn)開始調(diào)整 /*交換類排序*/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趟排序結(jié)果：,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)/對(duì)數(shù)組中a元素進(jìn)行歸并排序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+)/求元素關(guān)鍵字的個(gè)數(shù)if(maxkeynum=(int)(log10(max)+

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

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