C++数据结构与算法（七大查找）

小灰灰 2021-11-29 07:36 320阅读 0赞

**目录**

1 顺序查找（Sequence Search）

2 二分查找（Binary Search）

3 插值查找（Interpolation Search）

4 斐波那契查找（Fibonacci Search）

5 二叉查找树（Binary Search Tree）

6 分块查找（Block Search）

7 哈希查找（Hash Search）

--------------------

### **1 顺序查找（Sequence Search）** ###

顺序查找适用于存储结构为顺序存储或链式存储的线性表。

基本思想：

顺序查找也称为线形查找，属于无序查找算法。从数据结构线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定K值进行比较，若相等则表示查找成功，若扫描结束仍旧没有找到关键字等于K的结点，则表示查找失败。

算法实现：

#include<iostream>
    using namespace std;
    
    int SequenceSearch(int a[], int value, int n)
    {
    	int i;
    	for (i = 0; i<n; i++)
    	if (a[i] == value)
    		return i;
    	return -1;
    }
    
    int main()
    {
    	int a[] = { 2, 3, 5, 8, 6, 7, 9, 0 };
    	int key, index;
    	int n = sizeof(a) / sizeof(a[0]);
    	cout << "请输入待查找的值：" << endl;
    	cin >> key;
    	index = SequenceSearch(a, key, n);
    	if (index >= 0)
    	{
    		cout << "找到了" << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    	system("pause");
    	return 0;
    }

### **2 二分查找（Binary Search）** ###

说明：元素必须有序方能使用，无序则要先进行排序。

基本思想：

二分查找也叫折半查找，属于有序查找算法。用给定K值先与中间节点的关键字进行比较，中间节点把线性表分层两个子表，若相等则查找成功；若不相等，再根据K与中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找或查找结束没有发现表中有这样的结点。

算法实现：

#include<iostream>
    using namespace std;
    
    //二分查找（折半查找），版本1
    int BinarySearch1(int a[], int value, int n)
    {
    	int low, high, mid;
    	low = 0;
    	high = n - 1;
    	while (low <= high)
    	{
    		mid = (low + high) / 2;
    		if (a[mid] == value)
    			return mid;
    		if (a[mid]>value)
    			high = mid - 1;
    		if (a[mid]<value)
    			low = mid + 1;
    	}
    	return -1;
    }
    
    //二分查找，递归版本
    int BinarySearch2(int a[], int value, int low, int high)
    {
    	int mid = low + (high - low) / 2;
    	if (a[mid] == value)
    		return mid;
    	if (a[mid]>value)
    		return BinarySearch2(a, value, low, mid - 1);
    	if (a[mid]<value)
    		return BinarySearch2(a, value, mid + 1, high);
    }
    
    int main()
    {
    	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	int key, len;
    	cout << "请键入KEY值：" << endl;
    	cin >> key;
    	len = sizeof(a) / sizeof(a[0]);
    	//int index = BinarySearch1(a, key, len);
    	int index = BinarySearch2(a, key, 0, len-1);
    	if (index >= 0) cout << "找到" << endl;
    	else cout << "没找到" << endl;
    	system("pause");
    	return 0;
    }

### **3 插值查找（Interpolation Search）** ###

插值查找是根据要查找的关键字Key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值的计算公式：Key-arr\[low\]/arr\[high\]-arr\[low\]。mid的计算公式为：(high-low)\*(key-arr\[low\])/(arr\[high\]-arr\[low\])，而对半查找（折半查找、二分查找）的mid=(high-low)/2.

这种mid的改变的好处是：对于表长较长，且关键字分布比较均匀，插值查找算法的平均性能要高于折半查找，但是如果关键字分布极不均匀，那么插值查找不如折半查找。

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    using namespace std;
    //插值查找法 arr数组，length 数组长度，key 查找的关键字
    //返回查找值的下标 ，没查找到 返回-1
    int Interpolation_Search(int *arr, int length, int key)
    {
    	int low = 0;//低位下标
    	int high = length - 1;//高位下标
    	int mid;//中间值下标
    	while (low <= high)
    	{
    		mid = (high - low)*(key - arr[low]) / (arr[high] - arr[low]);//插值
    		if (key < arr[mid])
    		{
    			high = mid - 1;
    		}
    		else if (key > arr[mid])
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	return -1;
    }
    int main()
    {
    	int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	int key;
    	cout << "请键入key值：" << endl;
    	cin >> key;
    	int index = Interpolation_Search(arr, 10, key);
    	if (index >= 0) cout << "找到了，index为" << index << endl;
    	else  cout << "没找到" << endl;
    	system("pause");
    	return 0;
    }

### **4 斐波那契查找（Fibonacci Search）** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

算法实现：

//斐波那契查找
    
    #include <iostream>
    using namespace std;
    #define MAXN 20
    
    /*
    *产生斐波那契数列
    * */
    void Fibonacci(int *f)
    {
    	int i;
    	f[0] = 1;
    	f[1] = 1;
    	for (i = 2; i < MAXN; ++i)
    		f[i] = f[i - 2] + f[i - 1];
    }
    
    /*
    * 查找
    * */
    int Fibonacci_Search(int *a, int key, int n)
    {
    	int i, low = 0, high = n - 1;
    	int mid = 0;
    	int k = 0;
    	int F[MAXN];
    	Fibonacci(F);
    	while (n > F[k] - 1) 			//计算出n在斐波那契中的数列
    		++k;
    	for (i = n; i < F[k] - 1; ++i) //把数组补全
    		a[i] = a[high];
    	while (low <= high)
    	{
    		mid = low + F[k - 1] - 1;  //根据斐波那契数列进行黄金分割
    		if (a[mid] > key)
    		{
    			high = mid - 1;
    			k = k - 1;
    		}
    		else if (a[mid] < key)
    		{
    			low = mid + 1;
    			k = k - 2;
    		}
    		else
    		{
    			if (mid <= high) //如果为真则找到相应的位置
    				return mid;
    			else
    				return -1;
    		}
    	}
    	return -1;
    }
    
    int main()
    {
    	int a[MAXN] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 };
    	int k, res = 0;
    	cout << "请输入要查找的数字:";
    	cin>>k;
    	res = Fibonacci_Search(a, k, 13);
    	if (res != -1)
    		cout << "在数组的第" << res + 1 << "个位置找到元素:" << k << endl;
    	else
    		cout << "未在数组中找到元素:" << k << endl;
    	system("pause");
    	return 0;
    }

### **5 二叉查找树（Binary Search Tree）** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

算法实现：

#include<iostream>
    #include <iomanip>//输出控制的头文件
    using namespace std;
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa=NULL, *p;
    	int i;
    	root = (BTNode *)malloc(sizeof(BTNode));
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data<p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data<p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    	}
    }
    
    BTNode *FindNode(BTNode *root, int key)
    {
    	BTNode *p;
    	if (!root)
    		return NULL;
    	else if (root->data == key)
    		return root;
    	else if (key<root->data)
    		return FindNode(root->left, key);
    	else
    		return FindNode(root->right, key);
    }
    
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root, *p;
    	int key;
    	cout<<"任意键入一个key值：";
    	cin>>key;
    	root = CreateBTtree(a, 8);
    	//前序遍历
    	cout << "前序遍历为:";
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	cout<<"中序遍历为:";
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	cout << "后序遍历为:";
    	Porder(root);
    	cout << endl;
    	p = FindNode(root, key);
    	//printf("地址为：%x\n", p);
    	cout << "地址为：" << p << endl;
    	system("pause");
    	return 0;
    }

### **6 分块查找（Block Search）** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

算法实现：

//分块查找算法
    #include <iostream>
    using namespace std;
    
    
    struct index  //定义一个结构体用来分块
    {
    	int key;
    	int start;
    	int end;
    }index[4];
    
    
    int search(int key, int a[]);
    int main()
    {
    	int i, j = -1, k, key;
    	int a[] = { 42, 63, 82, 89, 111, 146, 219, 254, 325, 336, 348, 795, 867, 951, 998 };
    	cout << "已知有一数组" << endl;
    	for (i = 0; i<15; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	for (i = 0; i<3; i++)  //3个块
    	{
    		index[i].start = j + 1;//确定每个块的起始值
    		j = j + 1;
    		index[i].end = j + 4;//确定每个块的结束值
    		j = j + 4;
    		index[i].key = a[j];//确定每个块范围中的元素最大值
    	}
    	cout << "请输入你要查找的数：" << endl;
    	cin >> key;
    	k = search(key, a);
    	if (k >= 0)
    		cout << "查找成功！你要找的数字在数组中的位置是：" << k + 1 << endl;
    	else
    		cout << "查找失败！你要找的数字不在数组中。" << endl;
    	system("pause");
    	return 0;
    }
    
    
    int search(int key, int a[])
    {
    	int i, j;
    	i = 0;
    	while (i<3 && key>index[i].key)//确定在哪个块中
    		i++;
    	if (i >= 3)//大于分得的块数 返回0
    		return -1;
    	j = index[i].start;//j等于块范围的起始值
    	while (j <= index[i].end&&a[j] != key)//在确定的块内进行查找
    		j++;
    	if (j>index[i].end)//如果大于块范围的结束值 则说明没有要查找的数 j置-1
    		j = -1;
    	return j;
    }

### **7 哈希查找（Hash Search）** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6][]

算法实现：

#include<iostream>
    using namespace std;
    
    #define OK 1
    
    
    #define HASHSIZE 7 /* 定义散列表长为数组的长度 */
    #define NULLKEY -32768 
    
    typedef int Status;
    typedef struct
    {
    	int *elem; /* 数据元素存储地址，动态分配数组 */
    	int count; /*  当前数据元素个数 */
    }HashTable;
    
    int m = 0; /* 散列表表长，全局变量 */
    
    /*初始化*/
    Status Init(HashTable *hashTable)
    {
    	int i;
    
    	m = HASHSIZE;
    	hashTable->elem = (int *)malloc(m*sizeof(int)); //申请内存
    	hashTable->count = m;
    	for (i = 0; i<m; i++)
    	{
    		hashTable->elem[i] = NULLKEY;
    	}
    	return OK;
    }
    
    /*哈希函数(除留余数法)*/
    int Hash(int data)
    {
    	return data%m;
    }
    
    /*插入*/
    void Insert(HashTable *hashTable, int data)
    {
    	int hashAddress = Hash(data); //求哈希地址
    
    	//发生冲突
    	while (hashTable->elem[hashAddress] != NULLKEY)
    	{
    		//利用开放定址的线性探测法解决冲突
    		hashAddress = (++hashAddress) % m;
    	}
    
    	//插入值
    	hashTable->elem[hashAddress] = data;
    }
    
    /*查找*/
    int Search(HashTable *hashTable, int data)
    {
    	int hashAddress = Hash(data); //求哈希地址
    
    	//发生冲突
    	while (hashTable->elem[hashAddress] != data)
    	{
    		//利用开放定址的线性探测法解决冲突
    		hashAddress = (++hashAddress) % m;
    
    		if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data)) return -1;
    	}
    
    	//查找成功
    	return hashAddress;
    }
    
    /*打印结果*/
    void Display(HashTable *hashTable)
    {
    	int i;
    	cout << endl;
    	cout << "**********展示结果**********" << endl;
    
    	for (i = 0; i<hashTable->count; i++)
    	{
    		cout << hashTable->elem[i] << ",";
    	}
    
    	cout << endl;
    	cout << "**********展示完毕**********" << endl;
    }
    
    int main()
    {
    	int i, j, result, key;
    	HashTable hashTable;
    	int arr[HASHSIZE] = { 13, 29, 27, 28, 26, 30, 38 };
    
    	cout << "***************哈希查找(C++版)***************" << endl;
    
    	//初始化哈希表
    	Init(&hashTable);
    
    	//插入数据
    	for (i = 0; i<HASHSIZE; i++)
    	{
    		Insert(&hashTable, arr[i]);
    	}
    	Display(&hashTable);
    
    	//查找数据
    	cout << "请键入key值：" << endl;
    	cin >> key;
    	result = Search(&hashTable, key);
    	if (result == -1) cout << "对不起，没有找到！" << endl;
    	else cout << key << "在哈希表中的位置是:" << result << endl;
    	getchar();
    	system("pause");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211129/611c40620c654a4db3a4f2fe65e93456.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211129/4a5586afb305478ab695f684379da54c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211129/9a5ee067011743379effd71b3d35150b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211129/b08661d57c8846aab89ec49e72d47b33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4]: /images/20211129/1d9821ce5a9c44d3a7561d673a78c952.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5]: /images/20211129/0e2f2412f71e4756a6fdf4e82080394b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6]: /images/20211129/2c3edf95ff2249978e4a851f0d3c5c61.png