《数据结构》 内 排 序 算 法

1、 数据结构课程设计报告设计题目 内 排 序 算 法 学院名称 专 业 班 级 姓 名 学 号 目录 一、 实验题目 1 内排序算法1 二、问题描述1 三、设计目标1 四、需求分析1五、概要设计1六、函数2 流程图3七、测试分析4八、使用说明7九、课程设计总结8 十、附录（各功能函数源代码）91、 实验题目 内排序算法二、问题描述要求从外部文件读入或直接输入数据，编写一程序，通过插入、选择、交换、归并、基数等方法进行数据的排序。三、设计目标设计一个程序，利用内排序各算法，如直接插入、希尔、冒泡、直接接择、基数、归并、堆排序等算法进行数据排序，输出每趟排序结果，让排序算法更加明了，大大提高排序效率

2、，缩短时间的花费。 四、需求分析本次试验主要分为以下四大功能模块：1) 头文件：定义全局变量，申明函数；2) 菜单：各排序算法的分类；3) 算法：对不同算法的描述定义；4) 主函数：定义局部变量，调用各函数。五、概要设计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);/基数排序2、 系统结构功能图六、函数 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/ 最大关键字个数#define Radix 10 /关键字的基数#define MaxSize 80/元素的个数typedef int KeyType;/关键字类型为int 型typedef structchar keyMaxKeyNum;int next;SListCell;/每个元素的关键字类型typedef structSListCell dataMaxSize;int keynum,len;/关键字的个数及静态链表的长度SList;/静态链表类型typedef int addrRadix;/定义静态指针数组类型typedef str

5、uctKeyType key;DataType;/元素类型*/SList L;DataType aMaxKeyNum;2、主函数#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);/对数组中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、入数据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.基数”；结论：正常。八、使用说明 运行程序，在菜单界面，根据菜单的提示选择您想要实现的功能： 1：插入类排序； a：直接插入类排序； b：折半排序； c：希尔排序； 2：选择类排

9、序；i：简单选择排序；k：堆排序；3：交换类排序；！：快速排序；y：冒泡排序；4：归并类排序；5：基数排序。九、课程设计总结 通过不断做课程设计，逐次有了一定的进步。在这次课程设计中，又有了新的认识、理解，对于写程序，首先自己得先明确程序的目的，然后写一个大的框架，逐步向其添加实现自己想实现的功能的代码，对于每一行程序代码，要明白它是要实现哪一步，有什么功能，尽量的精简代码，让程序的效率提高。当自己没有思路时，也可以去“继承”别人的代码，对于现成的代码，理解上就得严格把关，多次去想代码的运行，思路跟随代码，仔细的将代码大体化，进而细化，在这个过程中，调试是一个很好的方法，每一步的调试，都可以清

10、楚的了解每一个变量随时变化的值，以便能彻底的了解程序。实在是不能理解，就可以动手写，将程序代码的每一步执行运算后的结果写在纸上，通过不断的对比去加深对代码的理解与运用。与此同时，也要和别人交流，讲出你的代码，在别人不断的疑问与你的解答中，你会收获颇多，真正的让你知道你的不足！进而深层次的挖掘代码。十、附录（各功能函数源代码）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(请先载入数据文件。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);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基数* 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)/对数组中a元素进行归并排序MSort(a,0,n-1,a);#include#includehead.h /* 基数排序*/oid InitList(SList *L,DataType a,int n)/利用数组a的元素初始化静态链表Lchar str10,str210;int i,j,max=a0.key;for(i=1;in;i+)/求元素关键字的个数if(maxkeynum=(int)(log10(max)+

23、1;/求每个元素关键字的个数L-len=n;/静态链表的长度for(i=1;in;i+)/将整型转化为字符串，不够位数的补足位数itoa(ai-1.key,str,10);/将元素转化为字符串for(j=strlen(str);jkeynum;j+)/将不足位数上补0strcpy(str2,0);strcat(str2,str);strcpy(str,str2);/将每个元素上的每一位作为关键字存入成员key中for(j=0;jkeynum;j+)L-datai.keyj=strL-keynum-1-j;/xiancunfang个位上的数/构建静态链表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) /将数组data中的元素根据关键字建立Radix个子表，同一子表中keyi的相同int j,k,m=0;for(j=0;j=n-1)break; void Collect(SListCell data,addr f,addr r)/根据将各个子表链接成一个静态链表int j,k;for(j=0;!fj;j+)NULL;data0.next