数据结构与算法-静态查找表

在这里插入图片描述
🌞 “清醒 自律 知进退！”

查找

  • 🎈1.查找的相关概念
  • 🎈2.静态查找表
    • 🔭2.1静态查找表的类定义
    • 🔭2.2顺序查找
    • 🔭2.3二分查找
      • 🔎二分查找例题
    • 🔭2.4分块查找
    • 🔭2.5三种算法的比较分析

查找是在一些有序的或无序的数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程，即根据给定的某个值在查找表中确定一个关键字等于给定的记录或数据元素。查找是信息处理科学中十分重要的操作。

🎈1.查找的相关概念

  1. 查找表是同一类型数据元素（或记录）构成的集合，与4种数据关系中的集合结构对应。由于集合中数据元素之间存在着完全松散的关系。因此，查找表往往要借助其他数据结构来实现相关算法。
  2. 关键字是可以标识一个数据元素（或记录）的数据项，关键字的值被称之为键值。若关键字可以唯一地标识一条记录，则称此关键字为主关键字。
  3. 查找是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素的过程。若在查找表中存在与给定值匹配的记录，则查找成功，此时查找的结果可以是整个记录的信息或查找成功标记等。若在查找表中不存在与给定值匹配的记录，则查找不成功，此时查找结果可以是不成功标记，或将被查找记录插入查找表。
  4. 静态查找表是仅对表进行查找操作，而不进行插入和删除操作的查找表。静态查找在查找不成功时，只返回一个不成功标志，不改变查找表，因此表中数据元素的数量不会发生变化。
  5. 动态查找表是在查找的同时对表进行插入和删除操作的表。动态查找在查找不成功时，需要将被查找的记录插入查找表，因此表中数据元素的数量可能会发生变化。
    在这里插入图片描述

🎈2.静态查找表

🔭2.1静态查找表的类定义

#define _CRT_SECURE_NO_WARNINGS 1
#define Max 100
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef int IndexType;
typedef struct 
{
	KeyType key;//KeyType为关键字数据类型
	InfoType otherinfo;//其他域
}SElemType;
class StaticSearchtable
{
private:
	SElemType* elem;
	int length;
public:
	StaticSearchtable()//构造函数，0位留空
	{
		elem = new SElemType[Max + 1];
		length = 0;
	}
	~StaticSearchtable()//析构函数，释放存储空间
	{
		delete[]elem;
		length = 0;
	}
	void Create(int n)//创建n个元素的顺序表
	{
		for (int i = 0; i <= n; i++)
		{
			cin >> elem[i].key >> elem[i].otherinfo;
		}
		length = n;
	}
	int SqSearch(KeyType key);//顺表表查找值等于key的关键字
	int BinSearch(KeyType key);//二分查找值等于key的关键字
	int IndexSearch(IndexType index[Max], KeyType key, int b);//分块查找值等于key的关键字，b为块数
};

🔭2.2顺序查找

🔎顺序查找的主要思想：

  1. 设立哨兵位elem[0].key=key,其作用是防止扫描溢出。
  2. 从表的末端开始向左扫描线性表，依次将扫描到的关键字值和给定值key进行比较，若找到关键字，则查找成功，返回该关键字在顺序表中的下标；否则查找失败，返回0.
int StaticSearchtable::SqSearch(KeyType key)
{
	elem[0].key = key;//哨兵位
	int i = 0;
	for (i = length; elem[i].key != key; i--)//从末端开始向左扫描
	{
		;//空语句
	}
	return i;
}

🔎顺序查找分析：
在这里插入图片描述

🔭2.3二分查找

二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求线性表采用顺序存储结构且元素有序。类似于顺序查找方法，在存储元素时，数组元素第0位留空。

🔎二分查找的主要思想是每次将待查找记录所在的区间缩小一 半。具体步骤如下：设elem[low..high]是当前的查找区间，首先确定中间点位置mid = [(low+high)/2],然后将待查元素的关键字key值与elem[mid].key比较：（初始时，令low=1,high=length）

  1. mid = [(low+high)/2]
  2. 若key==elem[mid].key,则查找成功，返回mid,即该元素在顺序表中的下标。
  3. 若key<elem[mid].key,则high = mid-1
  4. 若key>elem[mid].key,则low = mid+1
  5. 重复上述操作，直至low>high时，查找失败，此时返回0
int StaticSearchtable::BinSearch(KeyType key)
{
	int low = 1,high = length;
	int mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (key == elem[mid].key)
			return mid;
		else if (key < elem[mid].key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	return 0;
}

✅二分查找过程可用二叉树来描述，在构造二叉树的过程中，把当前查找区间的中点位置上的元素作为树根，左子表和右子表的元素分别作为根的左子树和右子树。由此递归得到二叉树，通常称描述查找的过程的二叉树为判定树。判定树的形态与表中个数n相关，与输入示例中的key值无关。

例如，要找到15个数据元素的有序表中的第8个元素仅需比较1次，找到第4和第12个元素需要比较2次，找到第2,6，10和14个元素需要比较3次；找到第1,3，5,7，9,11,13和15个元素需要比较4次。其查找过程如图所示，树中的每个圆圈结点表示表中一个元素，结点中的值表示该元素在表中的位置；圆圈结点表示查找成功，方框结点表示查找失败。若查找失败，则比较过程是一条从判定树的根到某结点的路径，所需关键字比较次数是该路径上圆圈结点的个数。
在这里插入图片描述

🔎二分查找分析：

  1. 判定树为满二叉树：（有序表元素个数为:n=2h-1）
    （1）.查找成功时平均查找长度：
    在这里插入图片描述
    （2）.查找不成功时平均查找长度：h

  2. 判定树为非满二叉树：

（1）.查找成功时平均查找长度：
在这里插入图片描述
（2）.查找不成功时平均查找长度：
在这里插入图片描述

🔎二分查找例题

例：给定18个元素的有序表 {2,5，8,10,15,40,42,55,66,70,72,75,80,88,90,100,108,200}，采用二分查找，试问：
（1）.查找长度为4和5的元素个数分别有多少个？
（2）.若要查找值为15的数据元素，要经过多少次比较？依次与哪些元素进行比较？
（3）.在查找概率相等的情况下，计算查找成功和查找不成功的平均查找长度。
在这里插入图片描述
解：第一问可以直接数第四行和第五行元素的个数：分别是8和3.
第二问数这条路径圆圈结点的个数为比较次数，圆圈内的值为比较的数：
在这里插入图片描述
因此，我们需要进行4次比较，依次与表中的元素66,10,40,15比较。
第三问，在查找概率相等的情况下，查找成功的平均查找长度为：
（11+22+43+84+35）/18=32/9。
查找不成功的平均查找长度为：（413+5*6）/19=82/19

🔭2.4分块查找

🔎 分块查找又称索引顺序查找，它是顺序表查找的一种改进方法，其性能介于顺序查找和二分查找之间。在索引查找方法中，除存储表本身以外，还需存储一个索引表。存储方法如下：

  1. 将线性表elem[1..n]均分为b块，前b-1块中元素个数为s=[n/b]，最后一块即b块的元素个数小于等于s.
  2. 每一块中的关键字不一定有序，但前一块中的最大关键字小于后一块中的最小关键字，即块内无序，块间有序。
  3. 抽取各块的最大关键字及起始位置构成一个索引表index[0..b-1],即index[i]（0<=i<=b-1）中存放第i块的最大关键字和该块在表中的初始位置。

📖索引表的数据类型定义：

typedef struct
{
	KeyType key;
	int link;
}IndexType;

📖分块查找的算法：

int StaticSearchtable::IndexSearch(IndexType index[Max], KeyType key, int b)
{//b为块数
	int low = 0, high = b - 1, mid, i, s;
	if (length % b == 0)
		s = length / b;
	else
		s = length / b + 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (index[mid].key >= key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	//在索引表high+1快对应的线性表中顺序查找key
	i = index[high + 1].link;
	while (i <= index[high + 1].link + s - 1 && elem[i].key != key)
	{
		i++;
	}
	if (i <= index[high + 1].link + s - 1)
		return i;//查找成功，返回该元素的下标
	else
		return 0;//查找失败，返回0
}

🔭2.5三种算法的比较分析

  1. 顺序查找的时间复杂度最差，二分查找的时间复杂度最好，分块查找的时间复杂度介于两种之间。
  2. 分块查找需要增加索引数据的空间，空间复杂度最大。
  3. 顺序查找对表没有特殊要求。
  4. 分块查找的数据块之间在物理上可以不连续，插入、删除数据只涉及对应的块，但增加了索引的维护。
  5. 二分查找要求表有序，若表的元素插入与删除很频繁，则维持有序的工作量极大。
  6. 在表不大的时候，一般使用顺序查找。

🌞运行示例：

#define _CRT_SECURE_NO_WARNINGS 1
#define Max 100
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;//KeyType为关键字数据类型
	InfoType otherinfo;//其他域
}SElemType;
typedef struct
{
	KeyType key;
	int link;
}IndexType;
class StaticSearchtable
{
private:
	SElemType* elem;
	int length;
public:
	StaticSearchtable()//构造函数，0位留空
	{
		elem = new SElemType[Max + 1];
		length = 0;
	}
	~StaticSearchtable()//析构函数，释放存储空间
	{
		delete[]elem;
		length = 0;
	}
	void Create(int n)//创建n个元素的顺序表
	{
		for (int i = 0; i <= n; i++)
		{
			cout << "输入第" << i+1 << "个元素的值和下标：";
			cin >> elem[i].key >> elem[i].otherinfo;
		}
		length = n;
	}
	int SqSearch(KeyType key);//顺表表查找值等于key的关键字
	int BinSearch(KeyType key);//二分查找值等于key的关键字
	int IndexSearch(IndexType index[Max], KeyType key, int b);//分块查找值等于key的关键字，b为块数
};
int StaticSearchtable::SqSearch(KeyType key)
{
	elem[0].key = key;//哨兵位
	int i = 0;
	for (i = length; elem[i].key != key; i--)//从末端开始向左扫描
	{
		;//空语句
	}
	if (i >= 0)
		cout << "该数所在顺序表中的下标为:" << i << endl;
	else
		cout << "未找到！" << endl;
	return 0;
}
int StaticSearchtable::BinSearch(KeyType key)
{
	int low = 1, high = length;
	int mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (key == elem[mid].key)
		{
			cout << "该数经二分查找下标为：" << mid << endl;
			break;
		}
		else if (key < elem[mid].key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	if(low>high)
		cout << "未找到！" << endl;
	return 0;
}
int StaticSearchtable::IndexSearch(IndexType index[Max], KeyType key, int b)
{//b为块数
	int low = 0, high = b - 1, mid, i, s;
	if (length % b == 0)
		s = length / b;
	else
		s = length / b + 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (index[mid].key >= key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	//在索引表high+1快对应的线性表中顺序查找key
	i = index[high + 1].link;
	while (i <= index[high + 1].link + s - 1 && elem[i].key != key)
	{
		i++;
	}
	if (i <= index[high + 1].link + s - 1)
		return i;//查找成功，返回该元素的下标
	else
		return 0;//查找失败，返回0
}
int main()
{
	StaticSearchtable a;
	a.Create(8);
	a.SqSearch(6);
	a.BinSearch(7);
	return 0;
}

在这里插入图片描述

好啦，关于静态查找表的知识到这里就先结束啦，后期会继续更新学习数据结构与算法的相关知识，欢迎大家持续关注、点赞和评论！❤️❤️❤️

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

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

相关文章

通过转速计算物体的转动弧度(梯形积分法简单应用)

通过转速计算物体的转动弧度(梯形积分法简单应用)

数值积分在累积流量上的应用请参看下面文章链接： https://rxxw-control.blog.csdn.net/article/details/134542089https://rxxw-control.blog.csdn.net/article/details/1345420891200PLC流量累计 https://rxxw-control.blog.csdn.net/article/details/126004031
阅读更多...
线程与多线程编程

线程与多线程编程

1. 线程 1.1 概念 线程又可以称为轻量级进程 &#xff0c;在进程的基础上做出了改进。 一个进程在刚刚启动时&#xff0c;做的第一件事就是申请内存和资源&#xff0c;进程需要把依赖的代码和数据&#xff0c;从磁盘加载到内存中这件事是比较耗费时间的&#xff0c;有的业务…
阅读更多...
简单测试大语言模型 Yi-34B 的中日英能力

简单测试大语言模型 Yi-34B 的中日英能力

简单测试大语言模型 Yi-34B 的中日英能力 0. 背景1. 中文测试2. 日文测试3. 英文测试 0. 背景 简单测试一下C-Eval 排行榜第一&#xff08;20231129时点&#xff09;的 Yi-34B 的中日英能力&#xff0c; 1. 中文测试 问题1&#xff0c;回答正确。 问题2&#xff0c;回答正确。…
阅读更多...
【教3妹学编程-算法题】拼车

【教3妹学编程-算法题】拼车

3妹&#xff1a;“太阳当空照&#xff0c;花儿对我笑&#xff0c;小鸟说早早早&#xff0c;你为什么背上炸药包” 2哥 :3妹&#xff0c;什么事呀这么开发。 3妹&#xff1a;2哥你看今天的天气多好啊&#xff0c;阳光明媚、万里无云、秋高气爽&#xff0c;适合秋游。 2哥&#x…
阅读更多...
SOCKET、TCP、HTTP之间的区别与联系

SOCKET、TCP、HTTP之间的区别与联系

SOCKET、TCP、HTTP之间的区别与联系 一、 Socket 1、什么是socket2、为什么需要socket3、建立socket连接 二、HTTP(基于TCP) 1、HTTP的概念2、HTTP连接的特点 连接请求&#xff1a;一次连接连接请求&#xff1a;短连接(socket是长连接) 三、TCP/IP协议簇 四、HTTP、Socket…
阅读更多...
Linux：查看端口占用的进程

Linux：查看端口占用的进程

命令 netstat -tunlp可以从图中看到&#xff0c;端口被那个进程占用&#xff0c;对应进程的pid是多少。
阅读更多...
哪个软件有消除笔？这三款消除笔轻松消除杂物

哪个软件有消除笔？这三款消除笔轻松消除杂物

想必大家都有遇到日常下载保存的图片中有多余元素想要去除的情况&#xff0c;奈何不会用PS&#xff0c;导致无法快速解决消除图片水印的问题&#xff0c;这时你需要消除笔来帮你一键消除&#xff0c;那么你想知道哪个软件有消除笔&#xff1f;今天来分享几款好用的消除笔软件&a…
阅读更多...
jquery 判断是手机端还是电脑端

jquery 判断是手机端还是电脑端

判断为手机端&#xff1a; var sUserAgent navigator.userAgent.toLowerCase(); var bIsIpad sUserAgent.match(/ipad/i) "ipad"; var bIsIphoneOs sUserAgent.match(/iphone os/i) "iphone os"; var bIsMidp sUserAgent.match(/midp/i) "mid…
阅读更多...
Sass 同时导出JavaScript 和 CSS变量

Sass 同时导出JavaScript 和 CSS变量

Sass 官网 安装插件 注意 sass-loader 版本没设太高&#xff0c;否则会报错 Syntax Error: TypeError: this.getOptions is not a function npm i sass sass-loader10 -D创建 Sass 文件 variables.module.scss。注意这里是 module.scss&#xff1a; 否则报错 Cant find st…
阅读更多...
产品学习之路（一）

产品学习之路（一）

在做好开发的同时&#xff0c;还需要熟悉产品业务逻辑&#xff0c;不能为了功能而做功能&#xff0c;要从产品经理的角度去看待每个需求和客户痛点所在&#xff0c;这样针对产品设计出来的东西自己也有发言权&#xff1b; 目前作为一名前端开发人员&#xff0c;也在自学产品知识…
阅读更多...
【中文编码】利用bert-base-chinese中的Tokenizer实现中文编码嵌入

【中文编码】利用bert-base-chinese中的Tokenizer实现中文编码嵌入

最近接触文本处理&#xff0c;查询了一些资料&#xff0c;记录一下中文文本编码的处理方法吧。   先下载模型和词表&#xff1a;bert-base-chinese镜像下载   如下图示&#xff0c;下载好的以下文件均存放在 bert-base-chinese 文件夹下    1. 词编码嵌入简介 按我通俗的…
阅读更多...
匿名结构体类型、结构体的自引用、结构体的内存对齐以及结构体传参

匿名结构体类型、结构体的自引用、结构体的内存对齐以及结构体传参

文章目录 &#x1f680;前言&#x1f680;结构体✈️结构体类型的声明✈️结构体变量的创建与初始化✈️结构体类型的特殊声明✈️结构体的自引用✈️结构体的内存对齐&#x1f681;修改默认对齐数 ✈️结构体传参 &#x1f680;前言 在C语言中有着各种数据类型&#xff0c;这…
阅读更多...
第九节HarmonyOS 常用基础组件3-TextInput

第九节HarmonyOS 常用基础组件3-TextInput

一、TextInput描述 TextInput组件用于输入单行文本&#xff0c;响应输入事件。TextInput的使用也非常广泛&#xff0c;例如应用登录账号密码、发送消息等。和Text组件一样&#xff0c;TextInput组件也支持文本样式设置&#xff0c;下面的示例代码实现了一个简单的输入框&#x…
阅读更多...
JavaScript WebAPI（三）（详解）

JavaScript WebAPI（三）（详解）

这次介绍一下webAPI中的一些知识&#xff1a; 回调函数 回调函数是指 如果将函数A做为参数传递给函数B时&#xff0c;我们称函数A为回调函数 例如&#xff1a; // 立即执行函数中传递的函数是一个回调函数 (function(){ console.log("我是回调函数") })(); // …
阅读更多...
＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之linux存储管理（1）》（17）

＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之linux存储管理（1）》（17）

《Linux操作系统原理分析之linux存储管理&#xff08;1&#xff09;》&#xff08;17&#xff09; 6 Linux 存储管理6.1 80x86 的分段机制6.1.1 80x86 的虚拟存储空间6.1.2 段描述符表6.1.3 逻辑地址向线形地址的转换 6 Linux 存储管理 6.1 80x86 的分段机制 Linux 最早在 in…
阅读更多...
Docker篇之利用docker搭建ftp服务器可实现多用户上传

Docker篇之利用docker搭建ftp服务器可实现多用户上传

一、前言 场景&#xff1a;公司需要搭建FTP服务器&#xff0c;供内网之前可以互相传递数据&#xff0c;安全稳定&#xff0c;需要满足开通多个账号&#xff0c;每个用户上传的文件有自己对应的文件目录。 这里建议&#xff1a;用户目录Disk尽量大一点&#xff0c;避免因为空间不…
阅读更多...
三十六、seata的部署和集成

三十六、seata的部署和集成

seata的部署和集成 一、部署Seata的tc-server 1.下载 首先我们要下载seata-server包&#xff0c;地址在http&#x1f615;/seata.io/zh-cn/blog/download.html 当然&#xff0c;资料也准备好了&#xff1a; 2.解压 在非中文目录解压缩这个zip包&#xff0c;其目录结构如下…
阅读更多...
走向未来能源之巅：可控核聚变的探索与挑战

走向未来能源之巅：可控核聚变的探索与挑战

走向未来能源之巅：可控核聚变的探索与挑战 引言 随着人类文明的进步和科技的发展，对能源的需求与日俱增。传统的化石燃料能源面临着枯竭和环境问题的双重压力，因此，寻找一种清洁、可持续、高效的能源成为了全球科学家的共同使命。在这个过程中，可控核聚变作为一种具有巨…
阅读更多...
synchronized和volatile的区别是什么？

synchronized和volatile的区别是什么？

synchronized和volatile是Java中的两个关键词&#xff0c;分别用于实现线程同步和线程间的可见性。 synchronized用于实现线程之间的互斥同步&#xff0c;即同一时刻只能有一个线程访问被synchronized修饰的代码块或方法&#xff0c;其他线程需要等待。synchronized确保了线程…
阅读更多...
大学里学编程，为什么这么难？

大学里学编程，为什么这么难？

在大学学习计算机专业&#xff0c;为何很多同学觉得编程学得不顺心呢&#xff1f;许多同学会有这种感觉&#xff0c;在上大学里的计算机专业课程时&#xff0c;听得头都大了&#xff0c;但是真正要写代码&#xff0c;却不知道从哪里开始&#xff0c;或是觉得&#xff0c;大学里…
阅读更多...
最新文章

Copyright @ 2022~2023