安徽理工大学：《数据结构》课程教学资源（PPT课件讲稿，C语言版，2018）第9章 查找

第九章查找 学习要点 熟练掌握顺序查找、二分查找和分块查找的方法 并能够灵活使用 理解二叉排序树的定义，熟练掌握二叉排序树的 相关运算和查找过程 掌握哈希表的建立方法和查找过程。 熟练掌握各种查找方法在等概率下的平均查找长 度的计算方法

n 熟练掌握顺序查找、二分查找和分块查找的方法 并能够灵活使用。 n 理解二叉排序树的定义，熟练掌握二叉排序树的 相关运算和查找过程。 n 掌握哈希表的建立方法和查找过程。 n 熟练掌握各种查找方法在等概率下的平均查找长 度的计算方法。 学习要点 第九章 查找

?基本概念 查找表：是由同一类型的数据元素（或记录）构 成的集合，由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵便的数据 结构 有关操作 ◆ 查询某个“特定的”数据元素是否在查找表 中 检索某个“特定的”数据元素的各种属性； 在查找表中插入一个数据元素； 从杏找夫中训士其个数捏云麦

l 查找表 ：是由同一类型的数据元素(或记录)构 成的集合,由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵便的数据 结构。 l 有关操作 u 查询某个“特定的”数据元素是否在查找表 中 u 检索某个“特定的”数据元素的各种属性； u 在查找表中插入一个数据元素； u 从查找表中删去某个数据元素。 v 基本概念

基本概念 查找表的分类 静态查找表：仅作查询和检索操作的查找表。 动态查找表：在查找过程中同时插入查找表中 不存在的数据元素，或者从查找表中删除已存 在的某个数据元素，此类表为动态查找表。 关键字 是数据元素（或记录）中某个数据项的值，用以标 识（识别一个数据元素（或记录）。若此关键字可以 识别唯一的一个记录，则称之谓“主关键字”。若 此关键字能识别若干记录，则称之谓“次关键字

l 查找表的分类 u 静态查找表：仅作查询和检索操作的查找表。 u 动态查找表：在查找过程中同时插入查找表中 不存在的数据元素，或者从查找表中删除已存 在的某个数据元素，此类表为动态查找表。 l 关键字 是数据元素(或记录)中某个数据项的值，用以标 识(识别)一个数据元素(或记录)。若此关键字可以 识别唯一的一个记录，则称之谓“主关键字” 。若 此关键字能识别若干记录，则称之谓“次关键字” 。 v 基本概念

冬基本概念 查找 根据给定的某个值，在查找表中确定一个其关 键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成 功”，查找结果：给出整个记录的信息，或指示 该记录在查找表中的位置；否则称“查找不成 功”，查找结果：给出“空记录”或“空指针

l 查找 根据给定的某个值，在查找表中确定一个其关 键字等于给定值的数据元素或(记录)。 若查找表中存在这样一个记录，则称“查找成 功” ，查找结果：给出整个记录的信息，或指示 该记录在查找表中的位置；否则称“查找不成 功” ，查找结果：给出“空记录”或“空指针” 。 v 基本概念

冬查找的基本概念 查找操作的性能分析 冬查找速度（时间复杂度） 冬占用存储空间多少（空间复杂度） 平均查找长度ASL(Average Search Length): 为确定记录在表中的位置，需和给定值进行比较 的关键字的个数的期望值叫查找算法的~ 对于一个含有个元素的表，查找成功时的平均 查找长度可表示为ASL= i=l

v 查找的基本概念 对于一个含有n个元素的表，查找成功时的平均 查找长度可表示为ASL=  n i i i p c 1 查找操作的性能分析 v查找速度(时间复杂度) v占用存储空间多少(空间复杂度) v平均查找长度ASL(Average Search Length)： 为确定记录在表中的位置，需和给定值进行比较 的关键字的个数的期望值叫查找算法的~

9.1静态查找表 9.1.1顺序表的查找 应用范围：以顺序表或线性链表表示的静态查找 表，表内元素之间无序 顺序查找的基本思想是：从表中最后一个记录 开始，逐个进行记录的关键字和给定值的比较，若 某个记录的关键字和给定值比较相等，则查找成功； 若直至第一个记录，其关键字和给定值比较都不等， 则查找不成功

9.1 静态查找表 9.1.1 顺序表的查找 应用范围：以顺序表或线性链表表示的静态查找 表，表内元素之间无序。 顺序查找的基本思想是：从表中最后一个记录 开始，逐个进行记录的关键字和给定值的比较，若 某个记录的关键字和给定值比较相等，则查找成功； 若直至第一个记录，其关键字和给定值比较都不等， 则查找不成功

9.1.1顺序表的查找 找64 0 23 4 5 6 8 9 1011 64 5 13 19 21 37 56 64 75 80 88 92 监视哨 比较次数=5 比较次数： 查找第n个元素：1 查找第n-1个元素：2 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1

9.1.1 顺序表的查找 i 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数=5 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1

顺序表的查找 顺序存储结构的表示： typedef int KeyType; typedef struct{ KeyType key;- 关键字域 ElemType; 记录类型 typedef struct{ ElemType *elem ElemType elem[maxsize+1]; R[O用作监视哨单元 int length }SSTable; 顺序表长度

顺序存储结构的表示： typedef int KeyType; typedef struct{ KeyType key; … }ElemType; 顺序表的查找 typedef struct{ ElemType *elem ; int length ; } SSTable;

顺序查找算法 若则查找成功，返回该记录的下标； 若则查找不成功，返回0。 int Search_Seq(SSTable ST,KeyType key){ ST.elem[0].key=key; 设置监视哨 for (i=ST.length;ST.elem[i].key!=key;--i); return i; 设置查找的起始位置 从后往 前查找

若则查找成功，返回该记录的下标； 若则查找不成功，返回0。 int Search_Seq(SSTable ST, KeyType key){ ST.elem[0].key=key; for (i=ST.length;ST.elem[i].key!=key;--i); return i; } 顺序查找算法

举例说明 例1：在下表中查找key=8的结点。 key ST.elem 8 100 10 0 77 1 3 0 1 2 n-3 n-2 n-1 查找不成功，i=0 例2：在下表中查找key=8的结点。 key ST.elem 8 100 10 0 8 3 0 2 n-3 n-2 n-1 查找成功，i=n-2

8 0 1 2 n-3 n-2 n-1 n ST.elem key 例1：在下表中查找 key = 8 的结点。 100 10 ……………… 0 7 1 3 i i i i i i i 查找不成功，i = 0 8 0 1 2 n-3 n-2 n-1 n ST.elem key 例2：在下表中查找 key = 8 的结点。 100 10 ……………… 0 8 1 3 i i i 查找成功，i = n-2 举例说明