数据结构试验5查找排序算法

1、实验五、查找排序算法的实现一、实验目的1 .掌握顺序、二分法查找方法及适用场合，并能在解决实际问题时灵活应用。2 .掌握各种排序(直接插入，希尔，冒泡，快速排序，简单选择，堆排序等)方法及适用场合，并能在解决实际问题时灵活应用。二、实验内容随机输入(或随机产生)30个数(1)采用冒泡排序完成对这30个数的排序(2)采用顺序、折半查找在(1)中排好序的数据中完成查找任务(3)分别采用插入、快速和希尔完成对这30个数的排序任务，并输出每一趟排序后的结果三、实验代码：#include<stdio.h>#include<time.h>#include<stdlib.h&g

2、t;#defineMaxSize100typedefstructintkey;RecordType;/直接插入排序voidInsertSort(RecordTyper,intlength)for(inti=2;i<=length;i+)r0=ri;intj=i-1;while(r0.key<rj.key)rj+1=rj;j=j-1;rj+1=r0;/冒泡排序voidBubbleSort(RecordTyper,intlength)(intt;for(inti=1;i<=length;i+)(for(intj=1;j<=length-i;j+)(if(rj.key>

3、rj+1.key)(t=rj+1.key;rj+1.key=rj.key;rj.key=t;)快速排序intQKPass(RecordTyper,intleft,intright)(intlow=left;inthigh=right;r0=rleft;while(low<high)(while(low<high&&rhigh.key>r0.key)(high-;)if(low<high)(rlow=rhigh;low+;)while(low<high&&rlow.key<r0.key)(low+;)if(low<high

4、)(rhigh=rlow;high-;)rlow=r0;returnlow;)voidQKSort(RecordTyper,intlow,inthigh)(if(low<high)(intpos=QKPass(r,low,high);QKSort(r,low,pos-1);QKSort(r,pos+1,high);)/希尔排序voidShellInsert(RecordTyper,intlength,intdelta)(inti,j;for(i=1+delta;i<=length;i+)(if(ri.key<ri-delta.key)(r0=ri;for(j=i-delta;

5、j>0&&rj.key>r0.key;j-=delta)(rj+delta=rj;)rj+delta=r0;)voidShellSort(RecordTyper,intlength,intdelta,intn)(for(inti=0;i<n;i+)(ShellInsert(r,length,deltai);)voidShowResult(RecordType*r,intlength)for(inti=1;i<=length;i+)(printf("%-5d",ri);if(i%10=0)(printf("n");v

6、oidRandNum(RecordTyperMaxSize)(srand(unsigned)time(NULL);for(inti=1;i<=30;i+)(ri.key=rand()%100+1;printf("%-5d",ri);if(i%10=0)(printf("n");intSeqSearch(RecordType*r,intlength,intn)(inti;for(i=0;i<length;i+)if(ri.key=n)returni;return(-1);intBinSearch(RecordType*r,intlength,i

7、ntn)(intlow,mid,high;low=0;high=length-1;while(low<=high)(mid=(low+high)/2;if(rmid.key=n)return(mid);elseif(rmid.key>n)high=mid-1;elselow=mid+1;return(-1);voidSelect()printf("排序算法n");printf("*1:冒泡排序*n");printf("*2:插入排序*n");printf("*3:快速排序*n");printf(&quo

8、t;*4:希尔排序*n");printf("n");intmain(void)intn,m;intj;RecordTyper31;intdelta=15,7,3,1;Select();doprintf("请选择排序算法：");scanf("%d",&m);switch(m)case 1:printf("你选择了冒泡排序!n");printf("n");printf("产生的随机待排序列为：n");RandNum(r);BubbleSort(r,30);pri

9、ntf("排序结果为：n");ShowResult(r,30);printf("请输入要查找的数：");scanf("%d",&j);printf("顺序查找结果：该数是第%dn",SeqSearch(r,30,j);printf("折半查找结果：该数是第d位坨",8访$62切(r,30力)；break;case 2:printf("你选择了直接插入排序！n");printf("n");printf("产生的随机待排序列为：n"

10、);RandNum(r);InsertSort(r,30);printf("排序结果为：n");ShowResult(r,30);break;case 3:printf("你选择了快速排序!n");printf("n");printf("产生的随机待排序列为：n");RandNum(r);QKSort(r,1,30);printf("排序结果为：n");ShowResult(r,30);break;case 4:printf("你选择了希尔排序!n");printf(&quo

11、t;n");printf("产生的随机待排序列为：n");RandNum(r);ShellSort(r,30,delta,4);printf("排序结果为：n");ShowResult(r,30);break;default:printf("输入有误！");returnfalse;break;while(true);return0;|=|回'*C：UsersAdministratorD5ktopD©bug123.X*83822,22449311存序序序序一盔人奈一，序邦悬一一京泡is2:3:4.一序官«*«*排了«««M-X二X-谑选6914产生的随机待排序列为1939745514t113244排序结聿为1155第第19口一1:&一G年该：的:法GC我果早算查结修择9蒙一成琲5人查育择诜;9土曲折上月5-1，I|=|