查找和排序算法的实现(实验七)

《查找和排序算法的实现(实验七)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.实验目的及要求（1）学生在实验中体会各种查找和内部排序算法的基木思想、适用场合，理解开发高效算法的可能性和寻找、构造髙效算法的方法。（2）掌握运用查找和排序解决一些实际应用问题。二.实验内容：（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASLo（2）编程实现一种内部排序算法（如插入排序、快速排序等）。三.实验主要流程、基木操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现一种杳找算法（如折半杳找、二叉排序树的查找、哈希查找等），并计算相应的ASLo>程序代码：折半查找：头

2、文件：#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#definemaxlength20typedefintElemType;typedefstruct}ElemTypekey;ElemTypeother;}card;//^条记录包含的数据项typedefstruct}cardr[maxlength];intlength;JSSTable;//-张表中包含的记录容量voidCreate(SSTable&L);intSearch(SSTableLJntelem);功能函数：#include

3、MLhH#includeHstdio.hHvoidCreate(SSTable&L){printf("新的线性表已经创建，请确定元素个数(不超过20)W);scanf(u%dM,&L.length);printf(-请按递增序列输入具体的相应个数的整数元索(空格隔开)“)；for(inti=0;ielem){prin

4、tf(”表中没有该元索(不在范围内)”)；return0;}intlow=0,high=L.length-1;intmid;while(lowv二high){mid=(low+high)/2;if(EQ(L.r[midJ.key,elem)){printf(n该元素在第％d位”,mid+l);return0;}elseif(LT(elem,L.r[mid].key)){high=mid-l;}else{low二mid+1;}}printf(”表中没有该元素(不在范围内)”);return0;}主函数：#include"st

5、dio.h"include11l.hnSSTableL;Create(L);printf(””);printf(”此时的线性表元素：“)；for(inta=O;a

6、}>运行结果：新的线性表已经创建，请确定元素个数（不超过20）10请按递増序列输入具体的相应个数的整数元素（空格隔开）-2136101114234499此时的线性表兀素:-2136101114234499请输入要查找的元素〈输入000表示结束程序〉11皈元素在第6位（2）编程实现一种内部排序算法（如插入排序、快速排序等）。程序代码部分：直接插入排序头文件：#definemaxlength20〃最人数据容量#defineOK1typedefintOther;typedefintKeyType;typedefstruct{KeyTypek

7、ey;Otherdata;}Red;typedefstruct{Redrfmaxlength+1];//加了个哨兵的位置intlength;//当询数据个数JSqList;StatusInit(SqList&L);StatusInsertsort(SqList&L);功能函数：#includenstdio.h"#include"l.h"StatusInit(SqList&L){prindT新的线性表以创建，请确定元素个数(不超过20)『)；scanf("%d",&L.length);printfC1请输入具体的相应个数的整数元素(空

8、格隔开)”)；for(inti=l/*将哨兵的位置[0]空出来*/;ivL.length+l;i++){scanf(n%d",&L.r[i].key);}returnOK;}StatusInsertsort(SqLi