【数据结构】07查找

🕗 发布于 2024-04-13 11:05 数据结构 算法哈希算法

查找

1. 基本概念
2. 顺序表查找
- 2.1 顺序查找
- 2.2 顺序查找优化-哨兵
3. 有序表查找
- 3.1 折半查找（二分查找）
4. 分块查找（索引顺序查找）
5. Hash表（散列表）

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; // 查找失败
}

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表示未找到
}

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; // 查找失败
}

递归实现：

// 递归实现
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);
}
}

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

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

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

查找过程：

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

5. Hash表（散列表）

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

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

对于长度固定的散列表来说，当数据分布的越均匀，查找效率越高。

5.1 散列函数的设计

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

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

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

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;
}

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;
}

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;
}

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;
}

原文地址：https://blog.csdn.net/wlisontj/article/details/137642459

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：cocos jsb调用IOS震动功能
下一篇：ios ipa包上传需要什么工具

使用淘宝商品关键词搜索API接口提升销售利润
综上所述，淘宝商品关键词搜索API接口为商家和开发者提供了一个强大的工具，通过合理使用这一接口，商家可以轻松获取丰富的商品信息，提高运营效率，优化用户体验，并最终实现销售利润的提升。：传统的搜索方式需
阅读更多2024-09-24
USB总线同步数据采集卡6路高速模拟量采集带DIO功能USB2884/2885/2886
数据采集卡概述：系统框图：规格参数：板卡外形图：尺寸图及元器件功能说明：
阅读更多2024-09-24
python爬虫/引用requests/基本使用
3.找到该文件一般在第一个的位置，点击查看信息。进入控制台使用该命令安装requests。这里用对网站进行post请求，然后打印。1.访问网站打开发F12这里使用百度演示。这里用对网站进行get请求，
阅读更多2024-09-24
基于双向 LSTM 和 CRF 的序列标注模型
本文介绍了如何使用 Keras 构建一个基于双向 LSTM 和 CRF 的序列标注模型。这种模型结合了双向 LSTM 的上下文建模能力和 CRF 的标签依赖关系考虑，能够在序列标注任务中取得较好的性能
阅读更多2024-09-24
数据结构 - 查找算法
存储记录时，有意的建立key与记录的存储位置之间的关系，以构建哈希表。
阅读更多2024-09-24
蓝牙技术|详谈蓝牙信道探测技术，可实现厘米级精准定位
苹果发布AirTag发布以来，大家都更加注重物品的防丢，苹果的 Find My 就可以查找 iPhone、Mac、AirPods、Apple Watch，如今的Find My已经不单单可以查找苹果的设
阅读更多2024-09-24
JUC并发编程_ReadWriteLock
通过合理地使用读写锁，可以显著提高程序的并发性能和资源的利用率。当没有线程持有写锁时，读锁可以被多个线程同时获取，这提高了并发读取的效率。（Write Lock）：写锁是独占的，当一个线程获得写锁后，
阅读更多2024-09-24
Spring Boot 中实现任务后台处理的几种常见方式
在现代应用程序中，后台处理对于处理发送电子邮件、处理文件、生成报告等任务至关重要。Spring Boot 提供了多种机制来高效地实现后台任务。本文探讨了在 Spring Boot 中处理后台处理的各
阅读更多2024-09-24
时序约束进阶三：Create_clock与Create_Generated_Clock详解
时序约束中，使用Create_clock约束来生成主时钟，主时钟可以说是设计的心脏。主时钟是来自FPGA芯片外部的时钟，通过时钟输入端口或高速收发器GT的输出引脚进入FPGA内部。对于赛灵思7系列的器
阅读更多2024-09-24
ubuntu查看全部的磁盘分区命令
使用以上命令中的任何一个都可以获取完整的磁盘分区信息。这将显示磁盘和分区的层次结构以及文件系统类型。这个命令也可以显示所有分区信息。这将列出所有磁盘及其分区。
阅读更多2024-09-24