devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】07查找

作者：羊村懒王 | 2024-04-19 21:00:11

赞

踩

【数据结构】07查找

查找

1. 基本概念

查找表：由相同数据类型的数据元素构成的集合。
关键字：数据元素中某个数据项，它可以标识一个数据元素，是唯一的。
查找（Searching）就是根据给定的某个值，在查找表中找到一个关键字等于给定
值的数据元素。
静态查找表：查找表中的数据元素不会发生变化
动态查找表：查找表中的数据元素会发生变化（插入、修改和删除）
查找长度：在查找运算中，需要对比关键字的次数
平均查找长度（ASL）：所查找过程中进行关键字比较次数的平均值，用于衡量查找算法的效率，包括成功和失败两种情况。

2. 顺序表查找

2.1 顺序查找

顺序查找（线性查找）：用于在静态的线性表（顺序表或链表）中进行查找
算法的思想是从线性表的某一端开始，把表中的元素和关键字逐个比较（线性表的遍历）

// 查找表arry中关键字key是否存在，返回数组下标
int Search_Seql(int *array,int len,int key)
{
	for(int i =0;i<len;i++)
	{
		if(array[i]==key)
		{
			return i;
		}
	}
	return -1; // 查找失败
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

2.2 顺序查找优化-哨兵

每次循环查找都需要对下标i是否越界进行判断，可以把数组的首个元素设置为哨兵(需要数组把下标为0的位置预留给哨兵)，从数组末尾开始遍历，可以省略每次比较下标是否越界。

int Search_Seql_2(int* array,int len,int key)
{
	// 设置哨兵
	array[0]=key; 
	int i =0;
	for(i = len-1;array[i]!=key;i--)
	; // 空语句
	return i; // 如果找到直接返回，如果没找到则会下标为0，此时返回0表示未找到
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

3. 有序表查找

3.1 折半查找（二分查找）

折半查找（二分查找）：只适用于有序（升序或降序，通常升序）的顺序表（不能是链表）
算法思想：在有序表中，取中间作为比较对象，如果查找目标大于中间记录的关键字，那么在右半区继续查找；如果查找目标小于中间记录的关键字，则在左半区进行查找。不断重复上述过程，直到找到查找成功，或者查找完毕无法找到为止。

  • 迭代方法实现：
// 迭代实现
int Binary_Search1(int* array, int len, int key)
{
	int low = 0, high = len - 1;
	int mid = (low + high) / 2;
	while (low <= high)
	{
		if (array[mid] == key) // 找到
		{
			return mid;
		}
		else if (key < array[mid]) //key小，在左半区
		{
			high = mid - 1;
		}
		else // key大，在右半区
		{
			low = mid + 1;
		}
		mid = (low + high) / 2;
	}
	return -1; // 查找失败
}



  • 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
  • 递归实现：
// 递归实现
int Binary_Search2(int* array, int key, int low, int high)
{
	if (low>high) // 查找失败
	{
		return -1;
	}
	int mid = (low + high) / 2;
	if(key== array[mid]) // 找到
	{
		return mid;
	}
	// key小
	else if (key < array[mid])
	{
		//向左递归
		return Binary_Search2(array, key, low, mid- 1);
	}
	//key 大
	else 
	{
		// 向右递归
		return Binary_Search2(array, key, mid + 1, high);
	}
}

  • 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

4. 分块查找（索引顺序查找）

分块查找（索引顺序查找），是顺序查找的一种改进方法。在此查找法中，除表本身外，还需要建立一个索引表。索引表中存放了每个分块的最大关键字，和分块的起始地址。
分块有序：

  • 块内无序，即每一块内的记录不要求有序
  • 块间有序，即第一块，第二块，第三块…之间要求有顺序。

查找过程：

  • 先查找索引表，确定待查找元素所属的分块（顺序或折半查找）
  • 在分块内使用顺序查找

5. Hash表（散列表）

散列（Hash）表，这种数据结构的特点是：数据元素关键字和它在表中的存储的地址直接相关。关键字与存储地址之间的对应关系的函数称为哈希函数。
哈希函数：Address = Hash(Key)

  1. Hash是一种以常数平均时间执行插入、删除和查找的技术，但是不支持元素排序和查找最小（大）值的操作
  2. Hash函数是一种映射关系，很灵活，任何关键字通过它的计算，返回的值都落在表长允许的范围之内即可
  3. 对于不同的关键字，可能得到相同的Hash地址，这种现象称为冲突；Hash地址相同的关键字称为同义词。
  4. 处理冲突的办法由四种：链地址法、开放定址法、再散列法和建立公共溢出区。
  5. Hash表的装填因子（表中记录数/表长）越大，关键字冲突的可能性越大，同义词越多，查找效率可能更低。
    在这里插入图片描述
    对于长度固定的散列表来说，当数据分布的越均匀，查找效率越高。

5.1 散列函数的设计

  • 除留余数法：Hash(key)=key%p
    如果散列表的表长为m，p为小于等于m的最大质数，在一般情况下，对质数取余会让冲突更少，数据元素在散列表中分布的更均匀。
  • 直接定址法：Hash(key)=a*key+b
    这种方法的计算最简单，不会产生冲突，适合关键字的分布比较连续的情况，如果关键字分布不连续，空位较多，会造成存储空间浪费。

散列函数的设计没有固定的方法，需要结合实际情况，考虑的因素有：

  1. 清楚关键字分布情况
  2. 散列表的大小合理，太大浪费空间，太小则产生太多的同义词
  3. 散列表中的数据分布要均匀，不要形成堆积
  4. 散列函数代码要精简

5.2 代码实现

5.2.1 初始化Hash表

Hash表由存储链表头结点的数组，数据元素单链表构成，并且每个数据元素对应有关键字’key’和数值’value’，因此需要构建三个结构体，并对他们初始化

// Hash表中数据元素结构体
struct Element
{
	int key; // 关键字
	int value; // 数据元素，可以是任意数据类型
};

// 数据元素单链表
struct Node
{
	Element elem; // 数据元素
	Node* next; // next指针
};

// Hash表
struct HashTable 
{
	Node* head;// 数据元素存储地址，动态分配数组
	int table_size;// 表的大小
	int count; // 数据元素个数
};

// 初始化Hash表
HashTable* InitHashTable(int table_size)
{
	HashTable* ht = new(HashTable);
	ht->table_size = table_size; // 表长
	ht->count = 0; // 数据元素个数

	// 分配和初始化数据元素单链表的头结点
	ht->head = new Node[ht->table_size]; // 产生大小为table_size的数组，用于存放头结点
	// 初始化单链表头结点
	for (int i = 0; i < ht->table_size; i++)
	{
		ht->head[i].next = nullptr;
		ht->head[i].elem.key = 0;
		ht->head[i].elem.value = 0;
	}

	return ht;
}

  • 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

5.2.2 插入数据元素操作

Hash表根据数据元素的key生成一个Hash地址，找到Hash地址对应的头结点后，插入到头结点对应的单链表中，这里使用的是头插法。实际开发中，可以对value按照一定顺序插入

// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{
	return key % hs->table_size; // 除留余法，对表长取余
}

// 查找关键字为key的数据元素，存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{
	int pos = Hash(hs, key); // 找到Hash地址
	Node* pp = hs->head[pos].next;// 从头结点下一个结点开始遍历这个单链表
	while (pp != nullptr && pp->elem.key != key)
	{
		pp = pp->next;
	}
	return pp;
}

// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{
	// 查找关键字是否存在，存在则插入失败
	Node* pp = Lookup(hh,ee->key);
	if (pp != nullptr)
	{
		return false;
	}
	// 不存在，创建新的结点
	Node* qq = new Node; 
	qq->elem = *ee;
	qq->next = nullptr;
	// 插入新数据元素
	int pos = Hash(hh, ee->key); // 获取Hash地址
	// 头插法
	Node head_node = hh->head[pos]; // 找到头结点
	qq->next = head_node.next;
	hh->head[pos].next = qq;

	// 表中元素个数
	hh->count++;
	return true;
}

  • 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

5.2.3 删除数据元素

从Hash表中删除数据元素也是根据它的key值，生成一个Hash地址，然后找到头结点，遍历整个头结点对应的单链表，找到key值对应结点的前一个结点，删除最后key值对应的结点。

// 删除Hash表中的一个数据，根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{
	//  根据key产生Hash地址
	int pos = Hash(hs, key);
	Node* node_ptr = &hs->head[pos]; // 找到头结点所在位置
	while (node_ptr->next != nullptr && node_ptr->next->elem.key != key) // 遍历单链表，找到key前的结点
	{
		node_ptr = node_ptr->next;
	}
	if (node_ptr->next == nullptr) // 查找失败
	{
		return false;
	}
	// 删除链表结点
	Node* delete_node = node_ptr->next;
	node_ptr->next = delete_node->next;
	delete delete_node;
	hs->count--;
	return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5.2.4 完整实现

#include <iostream>
using namespace std;

// Hash表中数据元素结构体
struct Element
{
	int key; // 关键字
	int value; // 数据元素，可以是任意数据类型
};

// 数据元素单链表
struct Node
{
	Element elem; // 数据元素
	Node* next; // next指针
};

// Hash表
struct HashTable 
{
	Node* head;// 数据元素存储地址，动态分配数组
	int table_size;// 表的大小
	int count; // 数据元素个数
};

// 初始化Hash表
HashTable* InitHashTable(int table_size)
{
	HashTable* ht = new(HashTable);
	ht->table_size = table_size; // 表长
	ht->count = 0; // 数据元素个数

	// 分配和初始化数据元素单链表的头结点
	ht->head = new Node[ht->table_size]; // 产生大小为table_size的数组，用于存放头结点
	// 初始化单链表头结点
	for (int i = 0; i < ht->table_size; i++)
	{
		ht->head[i].next = nullptr;
		ht->head[i].elem.key = 0;
		ht->head[i].elem.value = 0;
	}

	return ht;
}

// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{
	return key % hs->table_size; // 除留余法，对表长取余
}

// 查找关键字为key的数据元素，存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{
	int pos = Hash(hs, key); // 找到Hash地址
	Node* pp = hs->head[pos].next;// 从头结点下一个结点开始遍历这个单链表
	while (pp != nullptr && pp->elem.key != key)
	{
		pp = pp->next;
	}
	return pp;
}

// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{
	// 查找关键字是否存在，存在则插入失败
	Node* pp = Lookup(hh,ee->key);
	if (pp != nullptr)
	{
		return false;
	}
	// 不存在，创建新的结点
	Node* qq = new Node; 
	qq->elem = *ee;
	qq->next = nullptr;
	// 插入新数据元素
	int pos = Hash(hh, ee->key); // 获取Hash地址
	// 头插法
	Node head_node = hh->head[pos]; // 找到头结点
	qq->next = head_node.next;
	hh->head[pos].next = qq;

	// 表中元素个数
	hh->count++;
	return true;
}

// 打印Hash表
void PrintHash(HashTable* hs)
{
	for (int i = 0; i < hs->table_size; i++)
	{
		Node* pp = hs->head[i].next;// 招待第一个结点
		while (pp)
		{
			cout << "[" << pp->elem.key << "-" << pp->elem.value << "] ";
			pp = pp->next;
		}
		cout << "^\n";
	}
}

// 删除Hash表中的一个数据，根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{
	//  根据key产生Hash地址
	int pos = Hash(hs, key);
	Node* node_ptr = &hs->head[pos]; // 找到头结点所在位置
	while (node_ptr->next != nullptr && node_ptr->next->elem.key != key) // 遍历单链表，找到key前的结点
	{
		node_ptr = node_ptr->next;
	}
	if (node_ptr->next == nullptr) // 查找失败
	{
		return false;
	}
	// 删除链表结点
	Node* delete_node = node_ptr->next;
	node_ptr->next = delete_node->next;
	delete delete_node;
	hs->count--;
	return 0;
}

// 销毁Hash表
void DestoryHash(HashTable* hs)
{
	if (hs == nullptr)
	{
		return;
	}
	// 遍历Hash表，释放全部单链表
	for (int i = 0; i < hs->table_size; i++)
	{
		// 访问每个头结点的下一个结点
		Node* tmp_Ptr = hs->head[i].next;
		while (tmp_Ptr)
		{
			Node* next_Ptr = tmp_Ptr->next;
			delete tmp_Ptr;
			// 访问下一个结点
			tmp_Ptr = next_Ptr;
		}
	}
	hs->count = 0;
	hs->table_size = 0;
	// 释放头结点数组
	delete [] hs->head;
	// 删除Hash表
	delete hs;
}
int main(void)
{
	HashTable* hs = InitHashTable(10);
	// 数据元素
	Element ee;

	// 插入数据元素
	ee.key = 10; ee.value = 110; Insert(hs, &ee);
	ee.key = 11; ee.value = 111; Insert(hs, &ee);
	ee.key = 12; ee.value = 112; Insert(hs, &ee);
	ee.key = 13; ee.value = 113; Insert(hs, &ee);
	ee.key = 14; ee.value = 114; Insert(hs, &ee);
	ee.key = 15; ee.value = 115; Insert(hs, &ee);
	ee.key = 16; ee.value = 116; Insert(hs, &ee);
	ee.key = 17; ee.value = 117; Insert(hs, &ee);
	ee.key = 18; ee.value = 118; Insert(hs, &ee);
	ee.key = 19; ee.value = 119; Insert(hs, &ee);
	
	ee.key = 20; ee.value = 120; Insert(hs, &ee);
	ee.key = 21; ee.value = 121; Insert(hs, &ee);

	PrintHash(hs);
	if (Lookup(hs, 21) == nullptr)
	{
		cout << "查找key=21失败" << endl;
	}
	else
	{
		cout << "key=21,value=" << Lookup(hs, 21)->elem.value << endl;
	}

	Delete(hs, 21);

	PrintHash(hs);
	if (Lookup(hs, 21) == nullptr)
	{
		cout << "查找key=21失败" << endl;
	}
	else
	{
		cout << "key=21,value=" << Lookup(hs, 21)->elem.value << endl;
	}
	DestoryHash(hs);
	return 0;
}

  • 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
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/453633
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号