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

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

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

2、找等），并计算相应的ASL。Ø程序代码：折半查找：头文件：#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#definemaxlength20typedefintElemType;typedefstruct{ElemTypekey;ElemTypeother;}card;//每条记录包含的数据项typedefstruct{cardr[maxlength];intlength;}SSTable;//一张表中包含的记录容量voidCreate(SSTable&L);i

3、ntSearch(SSTableL,intelem);功能函数：#include"1.h"#include"stdio.h"voidCreate(SSTable&L){printf("新的线性表已经创建，请确定元素个数（不超过20）");scanf("%d",&L.length);printf("请按递增序列输入具体的相应个数的整数元素（空格隔开）");for(inti=0;i

4、elem){if(L.r[L.length-1].key

5、

6、L.r[0].key>elem){printf("表中没有该元素（不在范围内）");return0;}intlow=0,high=L.length-1;intmid;while(low<=high){mid=(low+high)/2;if(EQ(L.r[mid].key,elem)){printf("该元素在第%d位",mid+1);return0;}elseif(LT(elem,L.r[mid].key)){high=mid-1;

7、}else{low=mid+1;}}printf("表中没有该元素（不在范围内）");return0;}主函数：#include"stdio.h"#include"1.h"intmain(){SSTableL;Create(L);printf("");printf("此时的线性表元素：");for(inta=0;a

8、素(输入000表示结束程序)");scanf("%d",&elem);if(elem!=000){Search(L,elem);}}while(elem!=000);return0;}Ø运行结果：（2）编程实现一种内部排序算法（如插入排序、快速排序等）。程序代码部分：直接插入排序头文件：#definemaxlength20//最大数据容量#defineOK1typedefintStatus;typedefintOther;typedefintKeyType;typedefstruct{KeyTypekey

9、;Otherdata;}Red;typedefstruct{Redr[maxlength+1];//加了个哨兵的位置intlength;//当前数据个数}SqList;StatusInit(SqList&L);StatusInsertsort(SqList&L);功能函数：#include"stdio.h"#include"1.h"StatusInit(SqList&L){printf("新的线性表以创建，请确定元素个数（不超过20）");scanf("%d",&L.length);printf("请输入

10、具体的相应个数的整数元素（空格隔开）");for(inti=1/*将哨兵的位置【0】空出来*/;i