《数 据 结 构 课 程 设 计课件》由会员分享，可在线阅读，更多相关《数 据 结 构 课 程 设 计课件（18页珍藏版）》请在金锄头文库上搜索。
1、一 课程设计的目的 1.课程设计是一种全面的综合训练，是课堂教学的延续。 2.对学生数据结构知识的全面综合训练，把书上学到的知识用 于解决实际问题，培养今后软件开发工作所需的动手实践能 力，包括问题解析，总体结构设计，用户界面的设计，程序 设计的基本技能和技巧，以及一整套软件工作规范的训练和 团体协作精神的培养。 二课程设计的要求 1.认真上机编程，不得从事与课程设计无关的活动 2.程序运行正确，请指导老师检查提问，通过后提交课程设计 报告。 3.报告提交要求：课程设计结束应完成课程设计实习报告。课 程设计报告必须以书面形式和电子版两种形式提交。书面报 告装课程设计资料袋保存。,三课程设计的具
2、体要求： 几种排序算法的演示，要求给出从初始开始时的每一趟的变化 情况，并对各种排序算法的排序性能做分析和比较。 （1）直接插入排序 （2）折半插入排序 （3）冒泡排序 （4）简单选择排序 （5）快速排序 （6）堆排序 （7）归并排序 四具体算法及解析 #include #define A 20 typedef int keytype; typedef char infotype10; typedef struct, keytype key; infotype data; rectype; void insertsort(rectype r,int n) int i,j,k; rectype
3、temp; for(i=1;i=0 ,直 接 插 入 排 序 / 复制为哨兵 / 记录后移 / 插入到正确位置 /最后输出排序结果,void bubblesort(rectype r,int n) int i,j,k; rectype temp; for(i=0;ii;j-) if(rj.keyrj-1.key) temp=rj; rj=rj-1; rj-1=temp; printf( i=%d ,i+1); for(k=0;kn;k+) printf(%4d,rk.key); printf(n); void quicksort(rectype r,int s,int t) int i=s,j
4、=t,k; rectype temp;,冒 泡 排 序 / 将一个数和前面的数作比较，若小于前面的数 则互换两个数的位置 / 输出最后的排序结果 快 速 排 序,if(si k+) if(k=i),/ s(i)为开头数字，t(j)为结尾数字 / 把s作为比较的关键字 / 从后面找比关键字小的数，若有 与其互换 / 从前面找比关键字大的数，若有 与其互换,printf( %d,rk.key); else printf(%4d,rk.key); printf(n); quicksort(r,s,i-1); quicksort(r,i+1,t); void dispheap(rectype r,in
5、t i,int n) if(i=n) printf(%d,ri.key); if(2*i=n | 2*i+1n) printf(); if(2*i=n) dispheap(r,2*i,n); printf(,); if(2*i+1=n) dispheap(r,2*i+1,n); printf(); ,堆 排 序,void sift(rectype r,int low,int high) int i=low,j=2*i; rectype temp=ri; while(j=high) if(jhigh ,/ 建立一个大顶堆，使得根结点最大,for(i=n/2;i=1;i-) sift(r,i,n)
6、; printf(the first heap:); dispheap(r,1,n); printf(n); for(i=n;i=2;i-) printf(change %d and %d,printf %dn,ri.key,r1.key,r1.key); temp=r1; r1=ri; ri=temp; sift(r,1,i-1); printf( after select exchange the heap is:); dispheap(r,1,i-1); printf(n); void merge(rectype r,int low,int mid,int high) rectype *
7、r1; int i=low,j=mid+1,k=0; r1=(rectype *)malloc(high-low+1)*sizeof(rectype); while(i=mid i+; k+; else r1k=rj; j+; k+; while(i=mid) r1k=ri; i+; k+; while(j=high) r1k=rj; j+; k+; for(k=0,i=low;i=high;k+,i+),/ 将两个数进行比较，如果前面一个数小于等于 后面一个数，则把后面一个数放在存储空间的 第一个位置上,ri=r1k; void mergepass(rectype r,int length,
8、int n) int i; for(i=0;i+2*length-1n;i=i+2*length) merge(r,i,i+length-1,i+2*length-1); if(i+length-1n) merge(r,i,i+length-1,n-1); void mergesort(rectype r,int n) int length,k,i=1; for(length=1;lengthn;length=2*length) mergepass(r,length,n); printf( the %dth merging ,i+); for(k=0;kn;k+) printf(%4d,rk.
9、key); printf(n); void binsort(rectype r,int n) int k,mid,i=2,low,high,j,m=1; for(i=2;i=n;i+),折 半 查 找,/ 两两一组比较，若比较组为奇数个 剩下一组单独为一组, if(ri.key=high+1;-j) rj+1.key=rj.key; rhigh+1.key=r0.key; printf( i=%d ,m); for(k=1;k=10;k+) printf(%4d,rk.key); printf(n); m+; ,/ 最后一个数小于它前面的一个数 ，那么 把这个数作为关键字，在第一个数字 标注l
10、ow，在这个数的前面一个数标注high,/ 将这组数均分为二，将关键字与中间数 比较，若小于则与前面一半比较，若大于 与后面一半比较,void selectsort(rectype r,int n) int m,i,k,j,t; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(rj.keyrk.key) k=j; if(i!=k) t=rk.key; rk.key=ri.key; ri.key=t; printf( i=%d ,i+1); for(m=0;mn;m+) printf(%4d,rm.key); printf(n); ,简 单 选 择 排 序,/
11、 k总是为比较时最小的数,/ 当i不等于k时，将k的值与前面的值对调,void main( ) int i,k,n=10,t; keytype a10; rectype rA; clrscr(); printf(input the 10 data); printf(n); for(i=0;in;i+) printf(input the data:); scanf(%d,printf(n); getch(); clrscr(); for(i=0;in;i+) ri.key=ai; printf(n); printf( the first keyword); for(k=0;kn;k+) prin
12、tf(%3d,rk.key); printf(n); bubblesort(r,n); printf(the last result); for(k=0;kn;k+) printf(%3d,rk.key); printf(n); getch(); clrscr(); for(i=0;in;i+) ri.key=ai; printf(n); printf( the first keyword); for(k=0;kn;k+) printf(%4d,rk.key); printf(n);,quicksort(r,0,n-1); printf(the last result); for(k=0;k=
13、1;i-) sift(r,i,n); heapsort(r,n); printf( the last result ); for(k=1;k=n;k+) printf(%3d,rk.key); printf(n); getch(); clrscr();,for(i=0;in;i+) ri.key=ai; printf(n); printf( the first keyword); for(k=0;kn;k+) printf(%4d,rk.key); printf(n); mergesort(r,n); printf(the last result); for(k=0;kn;k+) printf
14、(%4d,rk.key); printf(n); getch(); clrscr(); for(i=0;in;i+) ri+1.key=ai; printf(n); printf(the first keyword:); for(k=1;k=n;k+) printf(%3d,rk.key); printf(n); binsort(r,n); printf(the last word:);,for(k=1;k=n;k+) printf(%4d,rk.key); printf(n); getch(); clrscr(); for(i=0;in;i+) ri.key=ai; printf(n); printf( the first keyword); for(k=0;kn;k+) printf(%4d,rk.key); printf(n); selectsort(r,n); printf(the last result); for(k=0;kn;k+) printf(%4d,rk.key); printf(n); getch(); ,截图：,1.输入十个数:45 36 28 97 3 18 66 71 42 88,2.直接插入排序 3.冒泡排序,4.快速排序 6.归并排序,5.堆排序,7.折半插入排序,8.简单选择排序,
