数据结构【查找】

这篇具有很好参考价值的文章主要介绍了数据结构【查找】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第八章 查找

提前了解:
1、关键字: 若关键字能唯一标识一个数据元素,则关键字称为主关键字;若能标识若干个数据元素的关键字称为次关键字;
2、查找(检索):顾名思义,给定一个值,进行查找;若存在值则查找成功,反之查找失败;
3、查找方法评价指标:其中pᵢ为查找第i个记录的概率;cᵢ查找第i个记录需要进行比较的次数;
数据结构【查找】,数据结构,数据结构

一、静态查找
1、定义:在查找时只对数据元素进行查询或检索,查找表称为静态查找表;
2、顺序查找:给定值,挨个找,从大往小比;

  • 算法分析:
    • 查找成功时的平均查找长度ASL;
      数据结构【查找】,数据结构,数据结构
    • 查找不成功时ASL=3(n+1)/4;

3、折半查找(二分查找):效率高;查找表中的所有记录都是按照关键字有序或者降序排好的;查找时都是将待查记录所在的区间缩一半,直到找到或者找不到为止;查找成功时ASL=n+1/n·log₂(n+1)-1,但n>50时,ASL=log₂(n+1);

  • 查找思想:采用Mid、Low、Hight指针;和二分排序差不多;Mid=(Low+Hight)/2取下整(就是数学里的取中位数);
    数据结构【查找】,数据结构,数据结构

4、散列查找
二、动态查找
1、定义:在实施查找的同时,插入查找表中不存在的记录,或从查找表中删除已存在的某个记录,查找表称为动态查找表;
2、二叉排序树的查找:找最大值即为右子树最后的结点值,找最小值即左节点最后的结点值;或为空,或具有以下性质;

  • 左子树不为空即所有左子树上的结点都小于根结点的值;
  • 右子树不为空即所有右子树上的值大于根结点的值;
  • 左右子树也分为二叉排序树;

3、二叉排序树的插入:遇到比根大值往右走,遇到比根小值往左走;
数据结构【查找】,数据结构,数据结构

4、二叉排序树的删除:如果被删的结点只有一个子结点,可直接将子结点连到被删结点的父结点上;若被删结点有两结点,那就以右子树内最小的结点代替被删的结点树;
数据结构【查找】,数据结构,数据结构
数据结构【查找】,数据结构,数据结构

5、二叉排序树的性能分析:插入和删除运行时间为O(H),H为树的高度;
6、二叉排序树的查找如何求ASL:左是等概率的情况,右是最坏的情况;
数据结构【查找】,数据结构,数据结构

7、二叉排序树查找算法的平均查找长度ASL,主要取决于树的高度,即与二叉树的形态有关。如果二叉排序树是一个单支树,其平均查找长度与单链表相同,为O(n);如果二叉排序树的左右子树的高度差不超过1,这样的二叉排序树称为平衡二叉树。它的平均查找长度达到O(log₂n)。
8、平衡二叉树:左右子树深度之差不超过1,左右子树也都是平衡二叉树;递归定义;

  • 平衡因子:左子树的深度减去右子树的深度则称为该结点的平衡因子;一般只能是-1、0、1;一棵二叉树既是二叉排序树又是平衡二叉树则称为平衡二叉排序树;
  • 平衡旋转:保持有序性,又具有平衡性;
    数据结构【查找】,数据结构,数据结构
  • LL型平衡化旋转(右单旋转):若在结点A的左孩子B结点的左子树上插入新结点,则回导致不平衡,那么先保持左孩子B结点和孩子的左子树不动,将它孩子的右子树移到结点A的左边,最后进行右翻转,A结点变成B结点(连带它们的子树一起变);
  • LR型平衡化旋转(先左后右双旋转):若在A的左孩子(L)的右子树®上插入了新结点,A的平衡因子由1增至2,导致以A为根失去平衡,需要进行两次旋转操作。先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置,然后再把该C结点向右上旋转提升到A结点的位置;
  • RL平衡旋转(先右后左双旋转):若在A的右孩子®的左子树(L)上插入了新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作。先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置,然后再把该C结点向左上旋转提升到A结点的位置。RL型平衡化旋转;
  • RR平衡旋转(左单旋转):若在A的右孩子®的右子树®上插入了新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树。

三、散列表
1、哈希函数:简单理解就是你给一个数据,它给你个对应的地址;
2、哈希表:应用哈希函数,由记录的关键字确定记录在表中的地址,并将记录放入此地址,然后构成的表(里头是数据对应着地址位);
3、哈希查找:利用哈希函数进行查找的过程;
4、冲突:两不同数据地址一样;
5、同义词:两不同数据地址一样;
6、设计方法(由于哈希函数通常是一种压缩映象,所以冲突不可避免,只能尽量减少;当冲突发生时,应该有处理冲突的方法)

  • 散列表的空间范围,即确定散列函数的值域;
  • 构造合适的散列函数,使得对于所有可能的元素(记录的关键字),函数值均在散列表的地址空间范围内,且出现冲突的可能尽量小;
  • 处理冲突的方法;即当冲突出现时如何解决。
    7、如何构造:只要使任何关键字的哈希函数值都落在表长允许的范围之内即可;
    8、评价因素:
  • 散列函数的构造简单;
  • 能“均匀”地将散列表中的关键字映射到地址空间;所谓“均匀”(uniform)是指发生冲突的可能性尽可能最少。

9、方法:直接定址法、数字分析法、除留余数法、冲突处理法;
10、冲突处理方法:开放定址法;

  • 线性探测法
    • 优点:只要表不满总会找到个地址;
    • 缺点:容易聚集(也就是每个冲突的地址都会比较靠近,那么会产生更多的冲突机会);
      数据结构【查找】,数据结构,数据结构
  • 二次探测法(循环的表)
    • 优点:探测序列跳跃式地散列到整个表中,不易产生冲突的“聚集”现象;
    • 缺点:不能保证探测到散列表的所有地址;
      数据结构【查找】,数据结构,数据结构
  • 再散列法
    • 优点:不易产生冲突的“聚集”现象;
    • 缺点:计算时间增加;
  • 链地址法(简单来说就是余数相同的放一块)
    • 优点:不易产生聚集,删除也很简单;
      数据结构【查找】,数据结构,数据结构

11、散列查找性能分析:尽管散列表在关键字与记录的存储地址之间建立了直接映象,但由于“冲突”,查找过程仍是一个给定值与关键字进行比较的过程,评价哈希查找效率仍要用ASL;

  • 哈希查找时关键字与给定值比较的次数取决于:
    • 哈希函数;
    • 处理冲突的方法;
    • 哈希表的填满因子a;
    • a=表中填入的记录数/哈希表长度;

12、散列表的ASL总结公式:
数据结构【查找】,数据结构,数据结构

13、例题:
数据结构【查找】,数据结构,数据结构
数据结构【查找】,数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-618183.html

到了这里,关于数据结构【查找】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • 折半查找实验 (数据结构)

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中,折半查找一个

    2024年02月08日
    浏览(85)
  • 【数据结构】查找(一)

    因为时间关系(现阶段来不及),先不学红黑树和B树,所以这是查找(一)。 先写一下二分查找,数据结构数上叫的“折半查找”。 下面依旧是对王道书上选择题的一个简单纠错(摸鱼),希望6.10能写完查找部分,6.11写完排序部分 1.(B) 对于顺序查找,每个元素查找成功

    2024年02月09日
    浏览(12)
  • 数据结构【查找】

    提前了解: 1、: 若能唯一标识一个数据元素,则称为主;若能标识若干个数据元素的称为次; 2、查找(检索):顾名思义,给定一个值,进行查找;若存在值则查找成功,反之查找失败; 3、查找方法评价指标:其中pᵢ为查找第i个

    2024年02月15日
    浏览(27)
  • 数据结构-查找1

    1.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为(   )。 A.(n-1)/2       B. n/2        C.(n+1)/2        D.n  答案:C 解释:总查找次数N=1+2+3+…+n=n(n+1)/2,则平均查找长度为N/n=(n+1)/2。 2.适用于折半查找的表的存储方式及元素排列要求为(

    2024年02月03日
    浏览(37)
  • 数据结构-查找2(详解)

    1 .在一棵由包含 4、5、6 等等一系列整数结点构成的二叉搜索树中,如果结点 4 和 6 在树的同一层,那么可以断定结点 5 一定是结点 4 和 6 的父亲结点。  错    解析:         反例  2.二叉搜索树的查找和折半查找的时间复杂度相同。 错   解析:不一定相同。二叉排序树

    2024年02月02日
    浏览(36)
  • 数据结构——查找

    目录 1.查找的基本概念 1.1基本概念 ​编辑1.2对查找表的常见操作 以此分为静态查找表和动态查找表:​编辑1.3查找算法的评价指标 2.顺序查找 2.1算法思想 2.2算法实现 2.2.1顺序表查找的实现 2.2.2顺序表查找的实现(哨兵) 2.3顺序查找效率及算法优化 3.折半查找⭐ 3.1算法思想

    2024年02月06日
    浏览(17)
  • 数据结构之查找详解

    1.1 定义 查找表是由同一类型的数据元素构成的集合。 例如电话号码簿和字典都可以看作是一张查找表。 1.2 查找表的几种操作: 1)在查找表中查找某个具体的数据元素; 2)在查找表中插入数据元素; 3)从查找表中删除数据元素; 1.3 静态查找表和动态查找表 在查找表中

    2024年01月16日
    浏览(32)
  • 数据结构_查找

    目录 1. 查找的基本概念 2. 顺序查找和折半查找 2.1 顺序查找 2.1.1 一般线性表的顺序查找 2.1.2 有序表的顺序查找 2.2 折半查找 2.3 分块查找 2.4 相关练习 3. 树型查找         3.1 二叉排序树 3.1.1 二叉排序树的定义 3.1.2 二叉排序树的查找 3.1.3 二叉排序树的插入 3.1.4 二叉排序

    2024年02月04日
    浏览(25)
  • 数据结构习题9---查找

    一、填空题 1 .   在数据的存放无规律而言的线性表中进行检索的最佳方法是    顺序查找(线性查找)    。 2 . 线性有序表( a 1 , a 2 , a 3 ,…, a 256 ) 是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索   

    2024年02月09日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包