数据结构与算法实验教程

第5章搜索树 5．1初级实验1 一、 实验目的 掌握二分查找的过程和算法实现。 二、 实验内容 (1) 实现二分检索算法； (2) 用户输入数据能够判断检索是否成功，如果成功，输出该元素所在位置的信息和比较次数； 如果不成功，若查找的元素不存在，输出比较的次数和插入的位置。 三、 参考代码 1． 本程序的文件结构 图51程序的文件结构图 本程序的文件结构如图51所示，说明如下。 (1) SeqList．h： 顺序表头文件，提供了顺序表类型定义和相关接口说明，同第2章的初级实验1。 (2) SeqList．c： 顺序表接口的具体实现文件，同第2章的初级实验1。 (3) BinSearch．c： 二分检索算法，包括递归和迭代两种方式以及主函数，使用了顺序表，因此需要包含SeqList．h。 2． 二分检索算法的实现 BinSearch．c： 1#include 2#include 3#include "SeqList.h" 4//函数功能:二分检索算法(迭代) 5//参数slist:顺序表 6//参数key:要查找的元素 7//参数pos:如果查找的key不存在，pos记录key应插入的位置 8//返回值:如果元素存在，返回其位置； 如果元素不存在，返回-1，pos记录key应插入的位置 9int binsearch(SeqList slist, int key, int *pos) 10{ 11int index=1; //比较次数 12int mid; 13int low=0; 14int high=slist->n-1; 15while (low 16{ 17mid=(low+high) / 2; 18if (slist->elem［mid］==key) 19{ 20*pos=mid; 21printf("找到,共进行%d次比较＼n", index); 22printf("要找的数据%d在位置%d上＼n", key, mid); 23return mid; 24} 25else if (slist->elem［mid］ > key) 26high=mid-1; 27else 28low=mid+1; 29index++; 30} 31*pos=low; 32printf("没有找到,共进行%d次比较＼n", index - 1); 33printf("可将此数插入到位置%d上＼n", *pos); 34return -1; 35} 36//函数功能:二分检索算法(递归) 37//参数slist:顺序表 38//参数key:要查找的元素 39//参数low:查找区间的低端位置 40//参数high:查找区间的高端位置 41//参数pos:如果查找的key不存在，pos记录key应插入的位置 42//返回值:如果元素存在，返回其位置； 如果元素不存在，返回-1，pos记录key应插入的位置