顺序查找算法、二分（折半）查找算法详解【数据结构实验报告】

一、顺序查找算法

1、算法核心
在顺序表ST中顺序查找其关键字等于key的元素，若找到，则函数值为该元素所在元素表中的位置。

2、实现过程（详解在每一步的注释里）

#include<iostream>
using namespace std;

typedef int KeyType;  //给int的别名KeyType
typedef int InfoType;  //给int的别名InfoType 
//数据元素类型定义 
typedef struct
{
	KeyType key;  //定义数据的关键字域
	InfoType otherinfo;  //定义数据的其他域 
} ElemType;  //数据元素类型名 
//顺序表定义
typedef struct
{	
	ElemType R[10];  //存储空间的基地址（用R[]数据可以正常输出） 
	int length;  //顺序表的长度
}SStable;  //表类型名

//表的初始化
void Init_SStable(SStable &ST)
{
	int i;
	ST.length= 10;  //表长设为10 
	//设置表的数据 
	for(i=0; i<ST.length; i++)
	{
		ST.R[i].key= (i+10);  //初始化为从0开始的数字 
		//正常输出，cout << ST.R[i].key << " ";  
	}
} 

//设置监视哨的顺序查找函数
int Search_Seq(SStable &ST, KeyType key) 
{
	int i=0;  //遍历的下标 
	ST.R[0].key= key;  //先定个初值 
	for(i=ST.length; ST.R[i].key!=key; --i) ; //从后往前查找，若找到等值，则跳出循环 
	return(i);  //并返回该遍历到的元素下标
}

int main()
{
	SStable st;  //创建一个空表
	Init_SStable(st);  //初始化顺序表 
	
	ElemType key;  //创建一个待查数据元素
	key.key= 18;  //待查找元素值 
	
	int res= Search_Seq(st, key.key);  //在st中查找18的位置 
	cout << "key在顺序表中的下标为：" << res << endl;
	
	//正常输出 
//	for(int i=0; i<st.length; i++)
//	{
//		cout << st.R[i].key << " ";  
//	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

3、测试效果（在key.key的值那里做修改）

二、折半查找算法（二分查找）

1、算法核心
在有序表ST中折半查找其关键字等于key的数据元素，若找到，则函数值为该元素所在元素表中的位置，否则为0。

2、实现过程（详解在每句注释中）

#include <iostream>
using namespace std;

typedef int KeyType;  //给int的别名KeyType
typedef int InfoType;  //给int的别名InfoType 
//数据元素类型定义 
typedef struct
{
	KeyType key;  //定义数据的关键字域
	InfoType otherinfo;  //定义数据的其他域 
} ElemType;  //数据元素类型名 
//顺序表定义
typedef struct
{	
	ElemType R[10];  //存储空间的基地址（用R[]数据可以正常输出） 
	int length;  //顺序表的长度
}SStable;  //表类型名

//顺序表的初始化
void Init_SStable(SStable &ST)
{
	int i;
	ST.length= 10;  //表长设为10 
	//设置表的数据 
	for(i=0; i<ST.length; i++)
	{
		ST.R[i].key= (i+10);  //初始化为从0开始的数字 
	}
} 

//二分查找函数算法核心 
int Search_Bin(SStable &ST, KeyType key)
{
	int low=1;  //设置查找区间的初值，从1到最后一个 
	int high= ST.length;
	int mid;  //查找的中间下标 
	
	while(low<=high)  //不断遍历
	{
		mid= (low+high)/2;
		if(key==ST.R[mid].key) return mid;  //找到待查找元素key 
		else if(key<ST.R[mid].key) high=mid-1;  //继续在前一部分进行查找（因为前提ST是有序的表） 
		else low=mid+1;  //继续在后一部分进行查找
	}
	return 0;  //表中不存在待查找元素 
}

int main()
{
	SStable st;  //创建一个空表
	Init_SStable(st);  //初始化顺序表 
	
	ElemType key;  //创建一个待查数据元素
	key.key= 14;  //待查找元素值 
	
	int res= Search_Bin(st, key.key);  //在st中查找5的位置 
	cout << "key在顺序表中的下标为：" << res << endl;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

3、测试效果（修改key.key）