实验九,查找、排序算法

1、数据结构教程上机实验报告实验九 查找、排序 班 级：13级计本2班 姓 名： 杨宴强 学 号：201392130129实验九 查找、排序一、实验目的：掌握顺序查找和折半查找的思路掌握顺序查找和折半查找算法的程序实现3.掌握冒泡排序和选择排序的思路4.掌握冒泡排序和选择排序算法的程序实现。二、实验内容：顺序查找 折半查找3冒泡排序4.选择排序三、实验步骤及结果：161 顺序查找#includestdio.h#define MAXSIZE 30typedef structint key;/int为关键字key的数据类型char data;/其他数据SeqList;/顺序表元素类型int SeqSe

2、arch(SeqList R,int n,int k)/顺序查找int i=n;R0.key=k;/R0.key为查找不成功的监视哨while(Ri.key!=k)/由表尾向表头方向查找i-;return i;/查找成功返回找到的位置值否则返回0值void main()int i=0,j,x;SeqList RMAXSIZE;/建立存放顺序表元素的数组Rprintf(Intput data of list(-1 stop):n);/生成顺序表中的数据(-1结束)scanf(%d,&x);while(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Intput dat

3、a of list(-1 stop):n);/输出顺序表中的数据for(j=0;j0)printf(Position of %d in Seqlist!:n,x,i+1);/找到输出在顺序表中的位置elseprintf(NO found %d in Seqlist!:n,x);/输出未找到信息printf(nSearch data in Seqlist,Intput data(-1 stop):n);scanf(%d,&x);16.2 折半查找#include#define MAXSIZE 30typedef structint key;char data;SeqList;int BinSea

4、rch(SeqList R,int n,int k)int low=0,high=n-1,mid;while(lowk)high=mid-1;elselow=mid+1;return -1;void main()int i;SeqList RMAXSIZE;for(i=1;i=12;i+)Ri.key=i*2;printf(Search 20 in Seqlist:n);i=BinSearch(R,12,20);if(i!=-1)printf(Position of 20 in Seqlist is %dn,i);elseprintf(NO found 20 in Seqlist!:n);pr

5、intf(Search 21 in Seqlist:n);i=BinSearch(R,12,21);if(i!=-1)printf(Position of 21 in Seqlist is %dn,i);elseprintf(NO found 21 in Seqlist!n);17.4 冒泡排序#include stdio.h#define MAXSIZE 30typedef structint key; /关键字项char data; /其他数据项RecordType; /记录类型void BubbleSort(RecordType R,int n) /对R1Rn这n个记录进行冒泡排序int

6、 i,j,swap;for(i=1;in;i+) /进行n-1趟排序swap=0; /设置未发生交换标志for(j=1;jRj+1.key) /如果R1大于Rj+i.key则交换Rj和Rj+1R0=Rj;Rj=Rj+1;Rj+1=R0;swap=1; /有交换发生if(swap=0)break; /本趟比较中未出现交换则结束排序（已排好） void main()int i=1,j,x;RecordType RMAXSIZE; /定义记录类型数组Rprintf(Input data of list (-1 stop):n); /给每一记录输入关键字直至-1结束scanf(%d,&x);while

7、(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Output data in list:n); /输出表中各记录的关键字for(j=1;ji;j+)printf(%4d,Rj.key);BubbleSort(R,i-1); /进行冒泡排序printf(nOutput data in list after Sort:n); /输出冒泡排序后的结果for(j=1;ji;j+)printf(%4d,Rj.key);printf(n);17.7 选择排序#includestdio.h#define MAXSIZE 30typedef structint key;/关键字项

8、char data;/其它数据项RecordType;/记录类型void SelectSort(RecordType R,int n)/对R1-Rn这n个记录进行选择排序int i,j,k;for(i=1;in;i+)/进行n-1趟选择k=i;/假设关键字最小的记录为第i个记录for(j=i+1;j=n;j+)/从第i个记录开始的n-i+1个无序记录中选出关键字最小的记录if(Rj.keyRk.key)k=j;/保存最小关键字记录的存放位置if(i!=k)/将找到的关键字最小的记录与第i个记录交换R0=Rk;Rk=Ri;Ri=R0;void main()int i=1,j,x;RecordTy

9、pe RMAXSIZE;/定义记录类型数组Rprintf(Input data of list(-1 stop);n);/给每一个记录输入关键字直至-1结scanf(%d,&x);while(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Output data in list:n);/输出表中各记录的关键字for(j=1;ji;j+)printf(%4d,Rj.key);printf(nSort:n);SelectSort(R,i-1);/进行选择排序printf(nOutput data in list after Sore:n);/输出选择排序后的结果for(j=1;ji;j+)printf(%4d,Rj.key);printf(n);四、实验总结： 查找又称检索，它也是数据处理中经常使用的一种重要的运算，在线性表上的查找方法有顺序查找，二分查找和分块查找。顺序查找是一种最简单的查找方法。它的基本思