数据结构课程设计——排序与查找..

1、北京信息科技大学课程设计报告课程名称数据结构课程设计排序与查找1 -指导教师赵庆聪设计起止日期 设计地点别信息管理学院业信息管理与信息系统姓名/学号鲁丹 20120121081. 课程实践目的:通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。2. 课程实践内容:b）随机产生20个0100之间的整数，允许有重复b）分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递 增递减均可），并统计在各种排序方法中关键字的 比较次数，最后输出各类排序方法的排序 结果及关键字的比较次数。提示：双向起泡排序是对标准起泡排序算法的改进，该方法第

2、一次自上而下进行“起泡”使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复 上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对 某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。c）用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。3. 实践步骤:#in clude<stdio.h>#in clude<stdlib.h>#in clude<time.h>#defi ne N 100#defi ne OK 1#

3、defi ne ERROR 0#define LIST INIT SIZE 100#defi ne LISTINCREMENT 10#defi ne INFEASIBLE -1#defi ne OVERFLOW -2typ edef int Status;typ edef int ElemT ype;typ edef structElemT ype *elem;int len gth;int listsize;List;Status In itList(List &L)L.elem=(ElemTy pe * ) malloc(LIST_INIT_SIZE * sizeof(ElemTy

4、 pe);L.le ngth = 0;L.listsize二LIST_INIT_SIZE;retur n OK;/ln itListvoid Create(List & L, i nt n)int i;sra nd(time(NULL);for(i=0;i vn ;i+)L.elemi=ra nd()%N;L.le ngth+;prin tf("%d "丄.elemi);prin tf("n");int In sertSort(List L)int i,j,t,m;m=0;for(i=1;i<L.le ngth;i+)t=L.elemi;j

5、=i-1;if(t>=L.elemj)13 m+;elsem+;while(j>=0)&&( t<L.elemj)L.elemj+1=L.elemj;L.elemj+1=t;return m;int SelectSort(List L)int i,j,k,mi n,t=O;for(i=0;i<L.le ngth;i+)mi n=i;for(j二i+1;jvL.le ngth;j+)if(L.elemjvL.elemmi n)mi n=j;t+；else t+;if(mi n!二i)k=L.elemi;L.elemi=L.elemmi n;L.elemmi

6、 n=k;return t;int QuickSort(List L,i nt s,i nt t)int i=s,j=t,co un t4=0;if(svt)L.elemO=L.elems;dowhile(j>i&&L.elemj>=L.elemO)coun t4+;if(i<j)L.elemi=L.elemj;i+;while(ivj&&L.elemi<=L.elem0)i+;coun t4+;if(ivj)L.elemj二L.elemi;j-；while(ivj);L.elemi=L.elem0;QuickSort(L,s,j-1);

7、QuickSort(L,j+1,t);return count4;int BubbleSort(List L)int flag,i,j;int t=0;flag=1;while(flag=1)flag=O;i=0;for(j=L.le ngth-i;j>i;j-)if(L.elemj-1>L.elemj)flag=1;int m;m=L.elemj;L.elemj=L.elemj-1;L.elemj-1=m;t+;else t+;return t;void dis play(List L)int i;for(i=0;ivL.le ngth;i+)prin tf("%d &

8、quot;丄.elemi);prin tf("n");void mai n()List L;int low,high,a,b,c,d;Ini tList(L);printf（"请将随机产生的0-100间的20个数输出:n"）;Create(L,20);printf（"n直接插入法排序输出的顺序表为:n"）;a=I nsertSort(L);dis play(L);printf（"此排序法关键字比较的次数为：dn",a）;printf（"n直接选择法排序输出的顺序表为:n"）;b=SelectSo

9、rt(L);dis play(L);19 -printf（"此排序法关键字比较的次数为:%dn",b);printf（"n快速排序输出的顺序表为:n");c=QuickSort(L,1,20);dis play(L);printf（"此排序法关键字比较的次数为:%dn",c);..2.13.14.printf（"n双向起泡法排序输出的顺序表为:n"）;d=BubbleSort(L);dis play(L);printf（"此排序法关键字比较的次数为:%dn&q

10、uot;,d）;#include "stdio.h"#include "stdlib.h"#include "string.h"#include "time.h"#include "limits.h"#define MAXITEM 1000typ edefint KeyT yp e,ElemT ype;int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0;int swa p1=0,swa p2=0,swa p3=0,swa p4=0,

11、swa p5=0,swa p6=0; typ edefstruct recKeyT ype key;ElemT ype data;sqlistMAXITEM;4.55.void gennum(sqlist r,sqlist t,intn)int i;srand(unsigned)time(NULL);for (i=1;iv=n;i+)voidvoidti.key

12、=rand()%100;ri.key=ti.key;ini(sqlist r,sqlist t,int n)int i;for (i=1;iv=n;i+)ri.key=ti.key;BubbleSort(sqlist r,int n) /起泡法r1rnint i,j;struct rec w;for (i=1;iv=n-1;i+)for (j=n;j>=i+1;j-)if (rj.keyvrj-1.key)w=rj;rj=rj-1;rj-1=w; swa p1+;count1+;void lnsertSort(sqlist r,int i,j;int n) /直接插入排序r1rn56.f

13、or (i=2;iv=n;i+)57.58.count2+;59.r0=ri；60.j=i-1；61.while (r0.keyvrj.key)62.63.rj+1=rj;64.j-；65.count2+;66.swa p2+;67.68.rj+1=r0;69.swa p2+;3. 'voidSelectSort(sqlist r,int n) / 简单选择排序74. 75.int i,j,k;76.struct rec temp;77.for (i=1;iv=n-1;i+)78.79.k=i;80.for (j=i+1;jv=n;j+)81.if (rj.keyv

14、rk.key)k=j;count3+;82.if (i!=k)83.84.temp=ri;85.ri=rk;86.rk=te mp;87.swa p3+;88.89.90.:91.92. 'voidQuickSort(sqlist r,int s, int t) / 快速排序93. 94.int i=s,j=t;95.if (svt)96.r1rnrsrt,rO空出000024.125

15、.35.136.137.rO=rs;swa p4+;dowhile (j>i&&rj.key>=r0.key)j-；count4+;if (ivj)voidri=rj; i+;swa p4+;while (i<j&&ri.keyv=r0.key)i+;count4+;if (i<j)rj=ri;j-;swa p4+;while (i<j);ri=r0;swa p4+;QuickSort(r,s,j-1);QuickSort(r,j+1,t);ShellSort

16、(sqlist r,int i,j,ga p;struct rec x;gap=n/2;while (gap>0)int n) / 希尔排序 r1rnfor (i=gap+1;iv=n;i+)j=i-ga p;while (j>0)if (rj.key>rj+gap.key)x=rj; rj=rj+ga p;21 138.rj+ga p=x;139.j=j-ga P；140.count5+;141.swa p5+;142.143.else144.145.j=0;count5+;146.147.148.gap=ga p/2;52.void sift(s

17、qlist r,int l, int m)153.154.int i,j;155.struct rec x;156.i=l;157.j=2*i;158.x=ri;159.while (j<=m)160.161.if (jvm&&rj.keyvrj+1.key)j+;count6+;162.if (x.key<rj.key)163.164.ri=rj;165.i=j;166.j=2*i;167.count6+;168.swa p6+;169.170.else j=m+1;count6+;171.172.ri=x;173.174.void HeapSort(sqlist

18、 r,int n) / 堆排序 i;177.struct rec m;178.for (i=n/2;i>=1;i-)sift(r,i,n);23 179.for (i=n;i>=2;i-)180.181.m=ri;182.ri=r1；183.r1=m;184.swa p6+;185.sift(r,1,i-1);89.void main()190.191.192.int k,n,a;193.sqlist r,t;194.prin tf("*n").195.p rintf("*n");19

19、6.p rintf("*内部排序算法的性能分析*n"）;197.p rintf("*n");198.prin tf("*nn")199.200.p rintf("*n");201.printf("*是否执行程序*n");202.printf（"（是）按1 键,（ 否）按0键n");203.Printf（"按键为："）；204.scanf("%d"，&a);205.p rintf("*n");206.207.w

20、hile (a=1)208.printf（"*请输入要排序的数据的个数：");209.scanf("%d"，&n);210.211.gennum(r,t,n);212.printf("n");213.214.printf（"*随机产生的最初顺序是：n");215.for (k=1;k<=n;k+)216. printf("%3d" ,tk.key);217.if (k%20=0)218.printf("n");219.-16 -220.printf("

21、n");221.BubbleSort(r,n);222.printf("n*排序之后的顺序是:n");223.for (k=1;kv=n;k+)224. printf("%3d" ,rk.key);225.if (k%20=0)226.printf("n");227.228.p rintf("nn");229.printf("*分析结果*230.p rintf("*起泡排序*n");231.p rintf("比较的次数是：%d,移动的次数是232.233.ini(r,t,n);234.lnsertSort(r,n);235.p rintf("*直接插入*n");236.p rintf("比较的次数是：%d,移动的次数是237.238.ini(r,t,n);239.SelectSort(r, n);240.p rintf("*简单选择排序*n");241.p rintf("比较的次数是：%d,移动