1、数据结构数据结构 李李 萍萍 第九章第九章 查找查找主要学习内容主要学习内容:掌握顺序表和有序表的查找掌握顺序表和有序表的查找掌握索引顺序表的查找掌握索引顺序表的查找掌握二叉排序树的构造和查找掌握二叉排序树的构造和查找掌握平衡二叉树的平衡方法掌握平衡二叉树的平衡方法掌握掌握B-B-树查找、插入和删除树查找、插入和删除掌握哈希表的构造和查找掌握哈希表的构造和查找掌握各种查找方法在等概率的情况下查找成功和不成功的平均查找长度掌握各种查找方法在等概率的情况下查找成功和不成功的平均查找长度9.1静态查找表静态查找表一、定义一、定义1.查找表：具有同一类型（属性）的数据元素组成的集查找表：具有同一类型（
2、属性）的数据元素组成的集合，可以进行的运算：查找、读表员、插入和删除。依合，可以进行的运算：查找、读表员、插入和删除。依据是否包含插、删运算可分为静态查找表和动态查找据是否包含插、删运算可分为静态查找表和动态查找表。表。2.关键码关键码:是数据元素某项的值是数据元素某项的值,用它可以标识一个数据用它可以标识一个数据元素元素3.衡量一个查找方法好坏的主要标准：平均比较次数、衡量一个查找方法好坏的主要标准：平均比较次数、附加空间、算法的复杂性。附加空间、算法的复杂性。一、顺序表的查找一、顺序表的查找1.基本思想基本思想2.存储结构存储结构3.算法实现算法实现4.性能分析性能分析9.1静态查找表静态
3、查找表二、有序表的查找二、有序表的查找1.两点要求两点要求 表只能顺序存储表只能顺序存储 表中的元素必须有序排列表中的元素必须有序排列2.基本思想基本思想先确定待查记录所在范围先确定待查记录所在范围,然后取中间元素作为比较对象然后取中间元素作为比较对象,若相等若相等,则查找成功则查找成功,否则如果小于中间元素则将查找区否则如果小于中间元素则将查找区域缩小到左半部分域缩小到左半部分,否则缩小到右半部分否则缩小到右半部分,直到找到或找直到找到或找不到该记录为止不到该记录为止.3.算法实现算法实现9.1静态查找表静态查找表9.1静态查找表静态查找表二、有序表的查找二、有序表的查找4.性能分析性能分析
4、 具有n个结点的判定树的深度为 查找成功的比较次数恰好就是该结点的层数,最多的比 较次数为树的深度 查找不成功的比较次数最多就是也就是树的深度 查找具体有序表的平均比较次数)1log2n（三、分块查找三、分块查找(索引顺序表查找索引顺序表查找)1.基本思想基本思想分块查找要求将查找表分成若干子表分块查找要求将查找表分成若干子表,并对子表建立索引并对子表建立索引表表,查找表的每一个子表由索引表中的索引项确定查找表的每一个子表由索引表中的索引项确定.索引项索引项 元素必须顺序存储元素必须顺序存储 元素必须有序排列元素必须有序排列2.基本思想基本思想先在索引表中确定要查找的分块先在索引表中确定要查找
5、的分块,在分块内进行顺序查找在分块内进行顺序查找.9.1静态查找表静态查找表9.1静态查找表静态查找表三、分块查找三、分块查找3.算法实现算法实现4.性能分析性能分析一、二叉排序树一、二叉排序树1.定义定义一棵非空的二叉排序树满足以下特征：一棵非空的二叉排序树满足以下特征：左子树（如果存在）上的所有结点的值均小于根结点的值。左子树（如果存在）上的所有结点的值均小于根结点的值。右子树（如果存在）上的所有结点的值均大于根结点的值。右子树（如果存在）上的所有结点的值均大于根结点的值。根结点的左右子树也都是二叉排序树。根结点的左右子树也都是二叉排序树。9.2动态查找表动态查找表607080505540
6、LNPEMCY一、二叉排序树一、二叉排序树2.算法算法1)查找BiTree search_bst(BiTree t,DataType k)if(t=NULL)return(NULL);elseif(t-data=k)return t;else if(t-datarchild;search_bst(t,k);elset=t-lchild;search_bst(t,k);/找到指向某个结点,找不到是空9.2动态查找表动态查找表一、二叉排序树一、二叉排序树2.算法算法2)插入插入在查找成功的情况下在查找成功的情况下,不用插入不用插入;否则插入新结点否则插入新结点,仍满足二叉排序树仍满足二叉排序树.v
7、oid Insertbst(BiTree*t,DataType k)BiTnode*f,*p;p=*t;while(p)if(p-data=k)return;f=p;p=(p-datak)?p=p-lchild:p=p-rchild)/循环完毕循环完毕p为空为空,f为插入的父为插入的父结点结点New(p);P-data=k;p-lchild=NULL;p-rchild=NULL;/初始化新结点初始化新结点If(t=NULL)*t=p;ElseIf(kkey)f-lchild=p;Else f-rchild=p;9.2动态查找表动态查找表一、二叉排序树一、二叉排序树2.算法算法3)删除删除在查找
8、成功的情况下在查找成功的情况下,删除这个结点删除这个结点,仍满足二叉排序树仍满足二叉排序树.分三种情况分三种情况:删除一个叶子删除一个叶子:只需将被删除结点的父结点相应指针域置空只需将被删除结点的父结点相应指针域置空.删除的结点只有棵子树删除的结点只有棵子树:将子树结点替换父结点将子树结点替换父结点.删除的结点左右子树均有删除的结点左右子树均有:PL接替接替*P成为成为*F的子树的子树,PR成为成为PL最右下结点的右子树最右下结点的右子树 PR接替接替*P成为成为*F的子树的子树,PL成为成为PR最左下结点的左子树最左下结点的左子树9.2动态查找表动态查找表一、二叉排序树一、二叉排序树3.性能
9、分析性能分析平均查找长度平均查找长度:最坏情况最坏情况:9.2动态查找表动态查找表二、平衡二叉树二、平衡二叉树1.定义定义对于一棵非空二叉排序树对于一棵非空二叉排序树,它的左子树和右子树都是一棵它的左子树和右子树都是一棵平衡二叉树平衡二叉树,且左子树和右子树的高度之差绝对值不超过且左子树和右子树的高度之差绝对值不超过1。平衡因子平衡因子:该结点的左子树和右子树高度之差该结点的左子树和右子树高度之差,它的值只它的值只能为能为-1、0、1。2。构造。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）转（先右后左）9.2动态查找表动态查
10、找表三、三、B-树树1.定义定义对于一棵非空二叉排序树对于一棵非空二叉排序树,它的左子树和右子树都是一棵它的左子树和右子树都是一棵平衡二叉树平衡二叉树,且左子树和右子树的高度之差绝对值不超过且左子树和右子树的高度之差绝对值不超过1。平衡因子平衡因子:该结点的左子树和右子树高度之差该结点的左子树和右子树高度之差,它的值只它的值只能为能为-1、0、1。2。构造。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）转（先右后左）9.2动态查找表动态查找表三、三、B-树树1。定义。定义一棵一棵 m 阶的阶的 B树，或者是空树，或者是满足下列
11、性质的树，或者是空树，或者是满足下列性质的 m 叉树叉树:(1)树中每个结点树中每个结点至多至多有有 m 棵子树棵子树；(2)根结点根结点至少至少有有两两棵子树棵子树；(4)所有叶子结点都出现在同一层次，可用来所有叶子结点都出现在同一层次，可用来“查找失败查找失败”处理。处理。(3)除根结点之外的非终端结点除根结点之外的非终端结点至少至少有有 m/2 棵子树棵子树；9.2动态查找表动态查找表三、三、B-树树1。定义。定义18 331223 3048101520 21243145 4750 529.2动态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶
12、子结点中。结点中。18 331223 3048101520 21243145 4750 52叶子结点只包含叶子结点只包含1个记录个记录插入新记录插入新记录 119.2动态查找表动态查找表叶子结点只包含叶子结点只包含1个记录个记录插入新记录插入新记录 18 331223 30481520 21243145 4750 5210 119.2动态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶子结点中。结点中。18 331223 3048101520 21243145 4750 52叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分
13、裂提升 559.2动态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶子结点中。结点中。18 331223 3048101520 21243145 4750 52 55叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 插入插入9.2动态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶子结点中。结点中。18 331223 3048101520 21243145 47叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 分裂分裂5055529.2动
14、态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶子结点中。结点中。18 331223 30101520 21243145 47叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 提升提升505548 529.2动态查找表动态查找表三、三、B-树树2。插入。插入新记录将插入到相应的新记录将插入到相应的叶子叶子结点中。结点中。18 331223 3048101520 21243145 4750 52情况情况1：从包含：从包含2个记录的叶子结点删除个记录的叶子结点删除1个记录。个记录。解决方法：直接删除这个记录。解决方法：
15、直接删除这个记录。9.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331223 30481015243145 4750 52情况情况1：从包含：从包含2个记录的叶子结点删除个记录的叶子结点删除1个记录。个记录。解决方法：直接删除这个记录。解决方法：直接删除这个记录。219.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331223 3048101520 21243145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲解决方法：向兄弟结点借一个记录，同时修改双亲结点的
16、记录。结点的记录。9.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331221 3048101520233145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。结点的记录。9.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331221 3048101520233145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻
17、结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。9.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331220 21481015303145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。9.2动态查找表动态查找表三、三、B-树树3。删除。删除18 331220 21481015303145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录
18、的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。9.2动态查找表动态查找表三、三、B-树树3。删除。删除20 2148333145 4750 52情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。10 1218 30解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。9.2动态查找表动态查找表三、三、B-树树3。删除。删除48333045 4750 52情况情况2：从包含：从包含1个记录的
19、叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能并影响双亲结点，这可能减少树的高度减少树的高度。25209.2动态查找表动态查找表三、三、B-树树3。删除。删除散列即是一种存储方式散列即是一种存储方式,又是一种查找方法又是一种查找方法.一、概念一、概念基本思想：根据问题中的关键字构造一个合适的函数，基本思想：根据问题中的关键字构造一个合适的函数，利用这个函数求得各记录的存储位置，然后存储；在查利用这个函数求得各记录的存储位置，然后存储；在查找时用相同的函数找其元素。即：找时用相
20、同的函数找其元素。即：Addr(ai)=H(Ki)Addr(ai)为为ai的存储地址的存储地址H为散列函数为散列函数Ki为为ai的关键字的关键字9.3哈希表哈希表散列即是一种存储方式散列即是一种存储方式,又是一种查找方法又是一种查找方法.一、概念一、概念散列表（哈希表）：按散列存储方式构造的存储结构为散散列表（哈希表）：按散列存储方式构造的存储结构为散列表。列表。散列函数：散列函数：H（K i)关键字与表的对应关系。关键字与表的对应关系。散列地址：散列函数的值。散列地址：散列函数的值。散列：将结点按关键字的散列地址存储到散列表的过程。散列：将结点按关键字的散列地址存储到散列表的过程。同义词：同
21、义词：K1 K2，但，但H（K1）=H（K2），映射到同一），映射到同一地址的关键码地址的关键码K1和和K2为同义词。为同义词。冲突：冲突：K1 K2，但，但H（K1）=H（K2），同义词争夺同），同义词争夺同一地址。一地址。9.3哈希表哈希表二、构造哈希表二、构造哈希表1。直接定址法。直接定址法取关键字的某个线性函数值为哈希地址。取关键字的某个线性函数值为哈希地址。H(key)=a*key+b例：例：H(key)=学号学号-20091001002。数字分析法。数字分析法 把字符型关键词量化，对其中的数字进行分析，谁最均把字符型关键词量化，对其中的数字进行分析，谁最均匀就取谁。匀就取谁。3。除
22、留求余法。除留求余法H(key)=key%p p=m m 为哈希表的表长为哈希表的表长p为不超过为不超过m的最大素数的最大素数例：例：23 35 18 48 107 9 43 609.3哈希表哈希表三、处理冲突的方法三、处理冲突的方法冲突发生时，为后来的关键字找到另一个空的哈希地址。冲突发生时，为后来的关键字找到另一个空的哈希地址。1。开放定址法。开放定址法线性探测法线性探测法H i=(H(key)+di)mod mH(key)为哈希函数为哈希函数M为哈希表长为哈希表长di为增量序列为增量序列1，2，3，m-1例：例：47 ，7，29，11，16，92，22，8，3表长为表长为11堆积堆积二次探测法二次探测法di的增量序列的增量序列12,-12,22 ,-22,，q2,-q2(q=m/2)9.3哈希表哈希表三、处理冲突的方法三、处理冲突的方法冲突发生时，为后来的关键字找到另一个空的哈希地址。冲突发生时，为后来的关键字找到另一个空的哈希地址。2.拉链法拉链法设哈希函数得到的哈希地址在区间设哈希函数得到的哈希地址在区间0，m-1上，以每个哈上，以每个哈希地址作为一个指针，指向一个链。希地址作为一个指针，指向一个链。每个链表中的结点都是同义词每个链表中的结点都是同义词9.3哈希表哈希表 221189347379229716508109.3哈希表哈希表
