C语言内部结构

1、信息工程学院设计性实验报告专业：计算机科学与技术 班级：15级计科二班 2016-2017-1课程名称数据结构与算法实验指导教师朱振伸本组成员学号姓名学号： 1501110241 姓名：刘翱寒实验地点XK2-413实验时间2016.12.22实验名称内部排序实验类型设计性1、 实验目的1.掌握排序的有关概念和特点。2.掌握常见的排序算法的思想及其适用条件。3.掌握常见的排序算法的程序实现。二、实验设备 Microsoft Visual C+6.0三、实验内容 输入一组关键字序列分别实现直接插入排序、折半插入排序和希尔排序算法。实现冒泡排序和快速排序算法。实现简单选择排序和堆排序算法.实现归并排

2、序算法。试用各种排序算法进行排序。四、实验步骤#include#include #include typedef struct datatype int node,data; dtype; dtype a1000; int n,sum1,sum2;/sum1记录比较次数，sum2移动次数 void readln()/用文件读入待排序数据 int i; FILE *f1; f1=fopen(a300.txt,r); fscanf(f1,%d,&n); for(i=1;i=n;i+) ai.node=i; fscanf(f1,%d,&ai.data); fclose(f1); void bubbl

3、esort()/冒泡排序 int i,j; dtype t; for(i=n-1;i;i-) for(j=i;jaj+1.data) t=aj;aj=aj+1;aj+1=t;sum2+; void qsort(int l,int r)/快速排序 int i,j,m; dtype t; i=l;j=r;m=al.data;sum2+; while(i=j) while(ai.datam)j-,sum1+; if(il)qsort(l,j); if(ir)qsort(i,r); void insertsort()/插入排序 int i,j,m; for(i=2;im) aj+1=a0; sum2+

4、; void shellsort(int d)/隔了d个数的插入排序 int i,j,m,k; for(i=1;i for(j=i+d;j0&ak.datam) ak+d=ak; k-=d;sum2+;sum1+; ak+d=a0;sum2+; void shells()/希尔排序 int i,m,d100; printf(Input the sum of your shellarray:n); scanf(%d,&m); printf(Input your shellarray:n); for(i=1;i=m;i+) scanf(%d,&di); while(getchar()!=10);

5、for(i=m;i;i-)shellsort(di); void selectsort()/选择排序 int i,j,k,m; dtype t; for(i=1;in;i+) m=ai.data;k=i;sum2+; for(j=i+1;j=n;j+) sum1+; if(aj.datam) m=aj.data;k=j; sum2+; t=ak;ak=ai;ai=t; sum2+; void create(int i)/创建堆 Int m; a0=ai;m=a0.data;sum2+; while(ai/2.datam) ai=ai/2; i/=2;/a0起了哨兵作用保证i值不为0 sum1+

6、;sum2+; ai=a0;sum2+; void treesort(int i)/排序的一步并维护堆 int j,m; a0=ai;m=a0.data;ai=a1;j=1;i-;sum2+ while(2*jm) if(a2*j+1.dataa2*j.data)aj=a2*j+1;j=2*j+1; elseaj=a2*j;j=2*j; Else if(a2*j+1.datam)aj=a2*j+1;j=2*j+1; else break; if(2*j=i) if(a2*j.datam)aj=a2*j;j=2*j;sum2+; aj=a0;sum2+;sum1+; void pilesort(

7、)/堆排序 int i; for(i=2;i1;i-) treesort(i); void msort(int l,int r)/归并排序 int i,m,mid; mid=(l+r+1)/2; if(mid-1l)msort(l,mid-1); if(midr)msort(mid,r); while(lmid) m=amid.data; a0=amid; while(al.datal;i-)ai=ai-1;/移动(跟插入排序一样) al=a0; l+;mid+;if(midr)break; sum1+;sum2+; main() int c,num,i; while(1) sum1=0;su

8、m2=0; readln(); printf(=main=); printf(Press 0 to down sort and else to up sort:n); scanf(%d,&c);while(getchar()!=10); printf(Choose the number to the sortsn); printf(0.nosortn); printf(1.bubblesortn);printf(2.quicksortn); printf(3.insertsortn);printf(4.shellsortn); printf(5.selectsortn);printf(6.pi

9、lesortn); printf(7.mergesortn);printf(else to exitn); scanf(%d,&num);while(getchar()!=10); switch(num) case 0:break; case 1:bubblesort();break; case 2:qsort(1,n);break; case 3:insertsort();break; case 4:shells();break; case 5:selectsort();break; case 6:pilesort();break; case 7:msort(1,n);break; defa

10、ult:exit(1); printf(=data=); if(c) for(i=1;i=n;i+)printf(%dt,ai.data); else for(i=n;i;i-) printf(%dt,ai.data); putchar(10); printf(Here is the times of the compare:n%dn,sum1); printf(Here is the times of the movement:n%dn,sum2); while(getchar()!=10); system(CLS); 运行如下：六、实验总结这次试验是我对排序运算有了深刻的理解， 在程序编译和链接时还报了一些错，最后我对排序运算有了更深刻的理解，对我们课堂上的知识进行回顾。 在程序编译和链接时还报了一些错，最后通过一步一步的测试，也很快解决了问题。通过这次程序我感觉我对C+调试有个很深的理解，对程序的调试有了很多心得，也对我的程序调试和编写有了进一步的提高。同时对C+编程进一步熟悉，对数据结