一、实验目的
掌握折半查找算法的基本思想
掌握折半查找算法的实现方法
掌握折半查找的时间性能
掌握折半查找类的定义和使用
二、实验要求
熟悉C++语言编程
了解折半查找的原理
了解折半查找类的定义、应用
三、实验内容
1、问题描述
在一个有序序列中，折半查找一个关键字
返回查找是否成功，如果成功，输出关键字所在的位置和查找次数。
2、折半查找算法
1.n个从小到大存放在有序顺序表ST中，k为给定值
2.设low、high指向待查元素所在区间的下界、上界，即low=1，high=n
3.设mid指向待查区间的中点，即mid=（low+high）/2
4.让k与mid指向的记录比较
若k=ST[mid].key,查找成功，结束
若k<ST[mid].key,则high=mid-1 [上半区间]
若k>ST[mid].key,则low=mid+1 [下半区间]
5.重复3,4操作，直至low>high时，查找失败。
举例：
3、输入
第一行：测试次数
每个样本分两行：
第一行：第一个数字n表示样本数目，其后跟n个样本；
第二行：查找的关键字的值。
4、输入样本
2
5 2 3 4 5 7
4
6 1 2 3 4 6 8
7
5、输出
查找是否成功（1-表示成功，0表示不成功）
所在位置（0-表示不成功）
查找次数
6、输出样本
1 3 1
0 0 3
四、实验步骤
1、折半查找变量的定义
2、生成顺序有序表函数
3、折半查找函数
4、主程序
五、详细代码
#include<stdio.h>
/*折半查找实验*/
int BinSuccess; // 查找是否成功（1-成功，0-不成功）
int BinPos; // 查找位置（0表示不成功）
int BinCount; // 查找次数
int BinList[32]; // 有序表
int BinListLen; // 有序表长度
int BinSearchKey(int Key);
void CreateSequence(int *r, int n);
int main()
{
int r[32], i, j, Key, TestNum, SampleNum;
printf(" 输入测试次数");
scanf("%d", &TestNum);
for(i = 0; i < TestNum; i++)
{
printf("输入样本数目");
scanf("%d", &SampleNum);
printf("输入样本数据: ");
for(j = 1; j <= SampleNum; j++)
scanf("%d", &r[j]);
CreateSequence(r, SampleNum);
printf("输入1个查找数据");
scanf("%d", &Key);
BinSearchKey(Key);
printf("%d %d %d\n", BinSuccess, BinPos, BinCount);
}
return 0;
}
void CreateSequence(int *r, int n)
{
int i, j, temp;
BinListLen = n;
for(i = 1; i < n; i++)
//利用直接插入排序将顺序表元素排成升序序列
{
if(r[i+1] < r[i])
{
temp = r[i+1];
for(j = i; j >= 1; j -= 1)
if(temp<r[j])
r[j+1] = r[j];
else break;
r[j+1] = temp;
}
}
for(i = 1; i <= n; i++)
BinList[i] = r[i];// 数据放到有序顺序表中
}
int BinSearchKey(int Key)
{
int Low, Mid = 0, High;
Low = 1;//low指向待查元素所在区间的下界
High = BinListLen;//high指向待查元素所在区间的上界
BinSuccess = 0;
BinPos = 0;
BinCount = 0;
while(Low <= High)
{
BinCount++;// 执行循环查找的记数
Mid =(High + Low)/2;
if(Key == BinList[Mid])
{
BinSuccess = 1;// 查找成功
BinPos = Mid;
break;
}
if(Key > BinList[Mid])// 关键字大于折半查找所取的中间数
{
Low = Mid + 1;
}
if(Key < BinList[Mid])// 关键字小于折半查找所取的中间数
{
High = Mid - 1;
}
}
return BinCount;// 返回查找次数
}
文章出处登录后可见！
已经登录？立即刷新
