当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/20 3:27:28

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

查找

  • 🎈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;elselow = 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;elses = length / b + 1;while (low <= high){mid = (low + high) / 2;if (index[mid].key >= key)high = mid - 1;elselow = mid + 1;}//在索引表high+1快对应的线性表中顺序查找keyi = 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;//查找成功，返回该元素的下标elsereturn 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;elsecout << "未找到！" << 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;elselow = 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;elses = length / b + 1;while (low <= high){mid = (low + high) / 2;if (index[mid].key >= key)high = mid - 1;elselow = mid + 1;}//在索引表high+1快对应的线性表中顺序查找keyi = 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;//查找成功，返回该元素的下标elsereturn 0;//查找失败，返回0
}
int main()
{StaticSearchtable a;a.Create(8);a.SqSearch(6);a.BinSearch(7);return 0;
}

在这里插入图片描述

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

相关文章：

  • Fiddler抓包工具之高级工具栏中的重定向AutoResponder的用法
  • 【网络安全技术】实体认证技术Kerberos
  • Hdoop学习笔记（HDP）-Part.02 核心组件原理
  • 【linux】信号——信号保存+信号处理
  • go使用aes加密算法
  • 详细学习Pyqt5的20种输入控件（Input Widgets）
  • Docker下安装Redis
  • STM32 ADC转换器、串口输出
  • 城市安全守护者：分析无人机在交通领域的应用
  • LaTeX插入裁剪后的pdf图像
  • Echarts大屏可视化_05 折线图的定制开发
  • C语言——深入理解指针（4）
  • apk和小程序渗透测试
  • SQL server 2016安装
  • golang 实现单向链表（lru）、双向链表、双向循环链表
  • 【140天】尚学堂高淇Java300集视频精华笔记（86-87）
  • 【391天】每日项目总结系列128（2018.03.03）
  • 2017-09-12 前端日报
  • Android 控件背景颜色处理
  • Java IO学习笔记一
  • JAVA 学习IO流
  • Javascript Math对象和Date对象常用方法详解
  • Java到底能干嘛？
  • java中的hashCode
  • Lsb图片隐写
  • Netty源码解析1-Buffer
  • NSTimer学习笔记
  • Promise面试题2实现异步串行执行
  • vue从入门到进阶：计算属性computed与侦听器watch（三）
  • Work@Alibaba 阿里巴巴的企业应用构建之路
  • 从零搭建Koa2 Server
  • 给初学者：JavaScript 中数组操作注意点
  • 机器学习学习笔记一
  • 漂亮刷新控件-iOS
  • 如何打造100亿SDK累计覆盖量的大数据系统
  • 如何正确配置 Ubuntu 14.04 服务器？
  • 入门到放弃node系列之Hello Word篇
  • 世界上最简单的无等待算法(getAndIncrement)
  • 算法-图和图算法
  • 译米田引理
  • 积累各种好的链接
  • ​​​​​​​Installing ROS on the Raspberry Pi
  • ​queue --- 一个同步的队列类​
  • # 日期待t_最值得等的SUV奥迪Q9：空间比MPV还大，或搭4.0T，香
  • （27）4.8 习题课
  • （4）Elastix图像配准：3D图像
  • （二）基于wpr_simulation 的Ros机器人运动控制，gazebo仿真
  • （附源码）springboot建达集团公司平台 毕业设计 141538
  • （附源码）计算机毕业设计SSM教师教学质量评价系统
  • （十一）图像的罗伯特梯度锐化
  • （四）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB
  • (未解决)jmeter报错之“请在微信客户端打开链接”
  • (转）可以带来幸福的一本书
  • (转)用.Net的File控件上传文件的解决方案
  • (转载)CentOS查看系统信息|CentOS查看命令