数据结构【查找】

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

第八章 查找

提前了解:
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日
    浏览(69)
  • 折半查找实验 (数据结构)

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

    2024年02月08日
    浏览(87)
  • 【数据结构(七)】查找算法

    在 java 中,我们常用的查找有四种:     ① 顺序(线性)查找     ② 二分查找/折半查找     ③ 插值查找     ④ 斐波那契查找 问题:     数组arr[] = {1, 9, 11, -1, 34, 89},使用线性查找方式,找出11所在的位置。 代码实现: 运行结果: 问题:     请

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

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

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

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

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

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

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

    (꒪ꇴ꒪ ),Hello我是 祐言QAQ 我的博客主页:C/C++语言,Linux基础,ARM开发板,软件配置等领域博主🌍 快上🚘,一起学习,让我们成为一个强大的攻城狮! 送给自己和读者的一句鸡汤🤔: 集中起来的意志可以击穿顽石! 作者水平很有限,如果发现错误,可在评论区指正,感谢

    2024年02月11日
    浏览(49)
  • 数据结构-查找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日
    浏览(39)
  • 数据结构-查找2(详解)

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

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

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

    2024年01月16日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包