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