【数据结构】07查找

查找

  • 1. 基本概念
  • 2. 顺序表查找
    • 2.1 顺序查找
    • 2.2 顺序查找优化-哨兵
  • 3. 有序表查找
    • 3.1 折半查找（二分查找）
  • 4. 分块查找（索引顺序查找）
  • 5. Hash表（散列表）
    • 5.1 散列函数的设计
    • 5.2 代码实现
      • 5.2.1 初始化Hash表
      • 5.2.2 插入数据元素操作
      • 5.2.3 删除数据元素
    • 5.2.4 完整实现

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)

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/540212.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Python】面向对象（专版提升2）

【Python】面向对象（专版提升2）

面向对象 1. 概述1.1面向过程1.2 面向对象 2. 类和对象2.1 语法2.1.1 定义类2.1.2 实例化对象 2.2 实例成员2.2.1 实例变量2.2.2 实例方法2.2.3 跨类调用 3. 三大特征3.1 封装3.1.1 数据角度3.1.2 行为角度3.1.3 案例:信息管理系统3.1.3.1 需求3.1.3.2 分析3.1.3.3 设计 3.2 继…
阅读更多...
照片分辨率怎么调？一键修改图片dpi

照片分辨率怎么调？一键修改图片dpi

当我们需要通过电子邮件、社交媒体、即时消息或在线存储服务共享图片时&#xff0c;较高分辨率的图片文件可能会占用更多的存储空间和传输时间。通过修改图片分辨率&#xff0c;您可以减小文件大小&#xff0c;提高传输速度&#xff0c;并确保照片在网络共享和传输过程中的顺利…
阅读更多...
gpu服务器与cpu服务器的区别在哪？

gpu服务器与cpu服务器的区别在哪？

GPU服务器与CPU服务器的区别主要体现在处理能力、应用场景、能源消耗和成本等方面。 处理能力&#xff1a;CPU&#xff08;中央处理器&#xff09;是计算机的“大脑”&#xff0c;负责执行指令和处理数据&#xff0c;它的设计注重于逻辑运算和串行处理能力。而GPU&#xff08;…
阅读更多...
隐私计算实训营第九讲-隐语多方安全计算在安全核对的行业实践

隐私计算实训营第九讲-隐语多方安全计算在安全核对的行业实践

隐私计算实训营第九讲-隐语多方安全计算在安全核对的行业实践 文章目录 隐私计算实训营第九讲-隐语多方安全计算在安全核对的行业实践1.业务背景&#xff1a;安全核对产生的土壤1.1相关政策出台1.2 数据差异的来源 2.产品方案&#xff1a;从试点到规模化的路3.技术共建&#xf…
阅读更多...
c++ 指针总结

c++ 指针总结

概述 内存地址 在计算机内存中&#xff0c;每个存储单元都有一个唯一的地址(内存编号)。通俗理解&#xff0c;内存就是房间&#xff0c;地址就是门牌号 指针和指针变量 指针&#xff08;Pointer&#xff09;是一种特殊的变量类型&#xff0c;它用于存储内存地址。指针的实质…
阅读更多...
Java springmvc 参数名用is开头导致为null

Java springmvc 参数名用is开头导致为null

因为最近在整理一些源码和编写规范&#xff0c;这里写一下只是记录几年前自己遇到的问题&#xff0c;好久都忘了&#xff0c;还是写下来比较好。 问题记录&#xff1a;由于变量使用了boolean&#xff0c;并且变量名是is开头的&#xff0c;由于java机制boolean默认是false&#…
阅读更多...
阿里云大学生免费服务器申请流程，2024年最新

阿里云大学生免费服务器申请流程，2024年最新

阿里云学生服务器免费申请&#xff0c;之前是云翼计划学生服务器9元/月&#xff0c;现在是高校计划&#xff0c;学生服务器可以免费申请&#xff0c;先完成学生认证即可免费领取一台云服务器ECS&#xff0c;配置为2核2G、1M带宽、40G系统盘&#xff0c;在云服务器ECS实例过期之…
阅读更多...
python入门（一）配置环境和选择IDE

python入门（一）配置环境和选择IDE

Python&#xff0c;作为一种简洁易懂的编程语言&#xff0c;近年来在全球范围内受到了广泛的关注和追捧。它不仅语法简单明了&#xff0c;易于上手&#xff0c;而且拥有强大的第三方库和广泛的应用领域。从数据分析、机器学习到Web开发&#xff0c;Python都能发挥出色的性能&am…
阅读更多...
算法题 - 双指针

算法题 - 双指针

目录 125. 验证回文串392. 判断子序列167. 两数之和 Ⅱ - 输入有序数组11. 盛最多的水15. 三数之和 125. 验证回文串 LeetCode_link 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后&#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 …
阅读更多...
面相对象设计

面相对象设计

设计原则 创建性模式 结构性模式 行为模式
阅读更多...
C++11 设计模式3. 工厂方法模式

C++11 设计模式3. 工厂方法模式

简单工厂模式的遗留问题 //从上面的代码可以看到&#xff0c;简单工厂模式确实实现了new 出来具体对象&#xff0c; 和 业务逻辑的分离&#xff0c; //但是不符合 "开闭原则" //"开闭原则"说的是代码扩展性问题——对扩展开放&#xff0c;对修改关…
阅读更多...
算法设计与分析实验报告c++实现(TSP问题、哈夫曼编码问题、顾客安排问题、最小生成树问题、图着色问题)

算法设计与分析实验报告c++实现(TSP问题、哈夫曼编码问题、顾客安排问题、最小生成树问题、图着色问题)

一、实验目的 1&#xff0e;加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握&#xff1b; 2&#xff0e;提高学生利用课堂所学知识解决实际问题的能力&#xff1b; 3&#xff0e;提高学生综合应用所学知识解决实际问题的能力。 二、实验任务 用贪心算…
阅读更多...
C# 两种方法截取活动窗口屏幕，实现窗体截图

C# 两种方法截取活动窗口屏幕，实现窗体截图

方法1&#xff0c;截屏内容仅包括活动窗口界面&#xff0c;而方法2是从屏幕范围取图&#xff0c;截屏内容会包括屏幕上所有内容。例如有一些程序在桌面顶层显示半透明的悬浮窗&#xff0c;用方法2截屏就会包括这些内容&#xff0c;并不是单纯的活动窗口内容。 方法1&#xff0c…
阅读更多...
开源代码分享(19)-配电网孤岛优化划分方法

开源代码分享(19)-配电网孤岛优化划分方法

参考文献&#xff1a; DING Tao, LIN Yanling, LI Gengfeng, et al. A new model for resilient distribution systems by microgrids formation[J]. IEEE Transactions on Power Systems, 2017, 32(5): 4145-4147. 1.基本原理 通过分布式电源&#xff08;DGs&#xff09;形…
阅读更多...
蓝桥杯 前一晚总结 模板 新手版

蓝桥杯 前一晚总结 模板 新手版

《准备实足&#xff0c;冲冲冲 省一》https://www.yuque.com/lenyan-svokd/hi7hp2/hfka297matrtsxy2?singleDoc# 《准备实足&#xff0c;冲冲冲 省一》 #include<bits/stdc.h> // 包含标准库头文件using namespace std; using ll long long; // 定义 long long 数据类…
阅读更多...
218基于matlab的有限差分法求解泊松方程

218基于matlab的有限差分法求解泊松方程

基于matlab的有限差分法求解泊松方程&#xff0c;采用SOR超松弛迭代法。模型采用方形区域&#xff0c;划分网格数为100*100&#xff0c;网格数可以很方便的更改。程序已调通&#xff0c;可直接运行。 218有限差分法 泊松方程 SOR超松弛迭代法 - 小红书 (xiaohongshu.com)
阅读更多...
基于React封装Handsontable并兼容antd

基于React封装Handsontable并兼容antd

背景 其实Handsontable官方也提供了React的版本&#xff0c;但是官方的版本再编辑和渲染的时候并不能够很好的嵌入第三方的组件库。这就导致了&#xff0c;使用了Handsontable就没有办和普通的react项目一样轻松引用其他第三方组件。因此对其react的版本进行了二次的封装&#…
阅读更多...
定制个性化的 openEuler 系统镜像：打造独特的安装体验

定制个性化的 openEuler 系统镜像：打造独特的安装体验

前言 标准的操作系统镜像可能无法完全满足特定用户群体或特定应用场景的需求。通过定制化&#xff0c;可以根据具体需求预装特定软件、配置特定网络设置&#xff0c;甚至设置特定的用户权限&#xff0c;以确保系统能够满足用户的需求。定制化系统镜像可以优化安装流程&#xf…
阅读更多...
PandasAI的应用与实战解析（二）：PandasAI使用流程与功能介绍

PandasAI的应用与实战解析（二）：PandasAI使用流程与功能介绍

文章目录 1.使用PandasAI进行开发的流程2.配置文件解析3.支持的数据库类型4.支持的LLMs5.其他 PandasAI这个工具最突出的优点就是通过结合了Pandas和生成式LLMs&#xff0c;极大地为开发人员降低了工作量。 传统的开发调用流程&#xff08;数据分析相关&#xff09;&#xff1a…
阅读更多...
(UDP)其他信息: 通常每个套接字地址(协议/网络地址/端口)只允许使用一次。

(UDP)其他信息: 通常每个套接字地址(协议/网络地址/端口)只允许使用一次。

“System.Net.Sockets.SocketException”类型的异常在 mscorlib.dll 中发生&#xff0c;但未在用户代码中进行处理其他信息: 通常每个套接字地址(协议/网络地址/端口)只允许使用一次。这个异常表示端口已经被占用了&#xff0c;需要释放端口或者使用其他端口来建立连接。您可以…
阅读更多...
最新文章

Copyright @ 2022~2023