首页计算机计算机基础程序设计基础与数据结构 09 第八章 查找.pptx

09 第八章 查找.pptx

页数:15页文件大小:118.5 KB来源: 程序设计基础与数据结构ppt课件

本课件系统讲解查找运算:先给出查找与关键字的定义,区分只查询的静态查找与含插入删除的动态查找;静态查找部分讲解顺序查找、二分查找与分块查找的原理及适用场合;动态查找部分讲解二叉排序树的查找与插入、平衡二叉树的定义与 LL、RR、LR、RL 四种平衡化旋转调整,最后介绍散列函数与散列表查找。

第八章章节目录页,列出查找的基本概念、静态查找、动态查找与小结四节
查找基本概念页,给出查找与关键字的定义并区分静态查找与动态查找
静态查找导览页,列出顺序查找、二分查找与分块查找三种方法
查看本课件的文字版(共 15 页,供检索与复制)

第1页:第八章 查找

第八章 查找

  • 查找的基本概念
  • 8.1 静态查找
  • 8.2 动态查找
  • 8.3 小结

第2页:查找的基本概念

查找的基本概念

  • 查找是根据给定的某个值,在一个数据元素集合中找出关键字值等于给定值的元素的过程。
  • 关键字是数据元素中某个数据项的值,用以识别一个数据元素。
  • 静态查找:数据元素集合一旦形成之后只进行查询而不作修改,即查询某个特定元素是否存在,或检索其各种属性。
  • 动态查找:所涉及的数据集合经常要作修改,除静态查找的操作外还需进行插入和删除。

第3页:静态查找

8.1 静态查找:静态查找主要有三种方法:

  • 顺序查找
  • 二分查找
  • 分块查找

第4页:顺序查找

8.1.1 顺序查找:数据集合的存储结构为线性表。

  • 从线性表的一端开始,依次逐个地把数据元素的关键字和给定值进行比较。
  • 如果某个数据元素的关键字值与给定值相等,则查找成功。
  • 如果整个线性表中元素都不满足要求,则查找失败。

第5页:二分查找

8.1.2 二分查找:

  • 首先将给定关键字值与有序表中处于中间位置的元素关键字值进行比较。
  • 若比较结果相等则找到该元素;否则根据比较结果决定继续在该元素之前的区间查找,还是在该元素之后的区间查找。
  • 每经过一次比较,要么找到所要找的元素,要么将比较区间缩小一半;如此反复直到找到或确定找不到为止。

第6页:分块查找

8.1.3 分块查找:分块查找又称索引顺序查找,一般用于数据量比较大的查找处理。

  • 线性表被分成若干块,每一块中的元素存储可以无序也可以有序,但块与块之间必须按关键字值大小有序,即前一块中的最大关键字小于后一块中的最小关键字。
  • 为每一块设定一个索引项,各块的索引项组成一张索引表。
  • 查找时先查索引表确定可能的块,再在该块中查找数据元素;块内有序可采用二分查找,否则采用顺序查找。

第7页:分块查找索引表示例(续)

分块查找索引表示例:图中给出一张索引表与对应的数据块,索引项包含起始地址、最大关键字与数据块长度三类字段,数据块长度为 4,最大关键字一栏可见 14、90、54、5 等取值。

说明:原文该页数字严重粘连(如“3131520227454146495358667483901081451366409”),无法安全切分为索引表与数据块的行列,此处只说明索引项的构成,未还原为数据表格,建议对照原课件图片核对具体数值。另:原文该页页眉标为 8.2.3,按内容应属 8.1.3 分块查找的续页,编号疑有误。

第8页:动态查找

8.2 动态查找:动态查找主要有三种方法:

  • 二叉排序树查找
  • 平衡二叉树查找
  • 散列表查找

第9页:二叉排序树查找

8.2.1 二叉排序树查找

  • 定义:二叉排序树或者是一棵空树,或者是这样的一棵二叉树——树中每个结点的值都大于其左子树上所有结点的值,同时每个结点的值又都小于其右子树上所有结点的值。
  • 查找方法:若树不空,将给定值与根结点的值比较,相等则查找成功;若根结点值小于给定值,则在右子树上继续查找,否则在左子树上继续查找。
  • 查找不成功时还需将新结点插入到树中,且插入后必须仍保持二叉排序树的性质。

第10页:平衡二叉树查找

8.2.2 平衡二叉树查找:二叉排序树的形态决定了其查找效率,需通过调整得到形态均匀的二叉排序树,即平衡二叉树。

  • 平衡二叉树或者是一棵空树,或者满足:它的左子树和右子树都是平衡二叉树,且左、右子树的深度之差的绝对值不超过 1。
  • 一个结点左右子树的深度之差被定义为该结点的平衡因子。
  • 一棵平衡二叉树上所有结点的平衡因子只能是 -1、0、1;若出现平衡因子绝对值大于 1 的结点,则该二叉树不平衡。

第11页:平衡化调整与LL型旋转

二叉排序树的平衡化:为保证由任意初始序列构成的二叉排序树都是平衡二叉树,需在构造过程中进行动态调整,称为二叉排序树的平衡化。以下均假设 A 是离插入结点最近、且平衡因子绝对值大于 1 的子树根结点。

  • LL 型调整:由于在 A 的左子树的左子树上插入结点 X,导致 A 的平衡因子由 1 变为 2 而失去平衡,需要以 B 为中心进行一次顺时针旋转,即将 B 调整为新的子树根结点,A 调整为 B 的右孩子。

第12页:RR型与LR型调整

平衡化的四种调整(续)

  • RR 型调整:由于在 A 的右子树的右子树上插入结点 X,导致 A 的平衡因子由 -1 变为 -2 而失去平衡,需要以 B 为中心进行一次逆时针旋转,将 B 调整为新的子树根结点,A 调整为 B 的左孩子。
  • LR 型调整:由于在 A 的左子树的右子树上插入结点 X,使 A 的平衡因子由 1 变为 2 而失去平衡,需进行两次旋转:先逆时针旋转,将 X 调整为 A 的左孩子、B 调整为 X 的左孩子;再以 X 为中心进行一次 LL 型调整。

第13页:RL型调整

RL 型调整:由于在 A 的右子树的左子树上插入结点 X,使 A 的平衡因子由 -1 变为 -2 而失去平衡,需要进行两次旋转操作(先顺时针旋转,后逆时针旋转):

  • 第一步顺时针旋转,将 X 调整为 A 的右孩子,B 调整为 X 的右孩子;
  • 第二步再以 X 为中心进行一次 RR 型调整。

第14页:散列表查找

8.2.3 散列表查找

  • 若能在数据元素的存储位置和它的关键字之间建立确定的对应关系,即在关键字与存储地址之间建立函数映射 h,把关键字值为 key 的元素存储在 h(key) 处,那么查找时只要计算 h(key),若集合中存在该关键字的元素,则必定在 h(key) 的存储位置上,不需要比较即可直接完成查找。
  • 这样的映射关系称为散列函数(hash 函数),由散列函数确定的存储位置称为散列地址。
  • 散列技术既是一种存储技术又是一种查找技术;按散列函数构造的存储结构称为散列表,相应的查找方法称为散列表查找。

第15页:第八章小结

8.3 小结

  • 查找是一种非常重要的数据处理运算
  • 查找的两种类型:静态查找、动态查找
顶部目录