数组-数学与信息技术学院课件

数据结构

李萍

数据结构李萍第九章查找主要学习内容:掌握顺序表和有序表的查找掌握索引顺序表的查找掌握二叉排序树的构造和查找掌握平衡二叉树的平衡方法掌握B-树查找、插入和删除掌握哈希表的构造和查找掌握各种查找方法在等概率的情况下查找成功和不成功的平均查找长度第九章查找主要学习内容:9.1静态查找表一、定义1.查找表：具有同一类型（属性）的数据元素组成的集合，可以进行的运算：查找、读表员、插入和删除。依据是否包含插、删运算可分为静态查找表和动态查找表。2.关键码:是数据元素某项的值,用它可以标识一个数据元素3.衡量一个查找方法好坏的主要标准：平均比较次数、附加空间、算法的复杂性。9.1静态查找表一、定义一、顺序表的查找1.基本思想2.存储结构3.算法实现4.性能分析9.1静态查找表一、顺序表的查找9.1静态查找表二、有序表的查找1.两点要求表只能顺序存储表中的元素必须有序排列2.基本思想先确定待查记录所在范围,然后取中间元素作为比较对象,若相等,则查找成功,否则如果小于中间元素则将查找区域缩小到左半部分,否则缩小到右半部分,直到找到或找不到该记录为止.3.算法实现9.1静态查找表二、有序表的查找9.1静态查找表9.1静态查找表二、有序表的查找4.性能分析具有n个结点的判定树的深度为查找成功的比较次数恰好就是该结点的层数,最多的比较次数为树的深度查找不成功的比较次数最多就是也就是树的深度查找具体有序表的平均比较次数9.1静态查找表二、有序表的查找三、分块查找(索引顺序表查找)1.基本思想分块查找要求将查找表分成若干子表,并对子表建立索引表,查找表的每一个子表由索引表中的索引项确定.索引项元素必须顺序存储元素必须有序排列2.基本思想先在索引表中确定要查找的分块,在分块内进行顺序查找.9.1静态查找表三、分块查找(索引顺序表查找)9.1静态查找表9.1静态查找表三、分块查找3.算法实现4.性能分析9.1静态查找表三、分块查找一、二叉排序树1.定义一棵非空的二叉排序树满足以下特征：左子树（如果存在）上的所有结点的值均小于根结点的值。右子树（如果存在）上的所有结点的值均大于根结点的值。根结点的左右子树也都是二叉排序树。9.2动态查找表607080505540LNPEMCY一、二叉排序树9.2动态查找表607080505540LNP一、二叉排序树2.算法1)查找BiTreesearch_bst(BiTreet,DataTypek){if(t==NULL) return(NULL);else{if(t->data==k)returnt;elseif(t->data<k){t=t->rchild;search_bst(t,k);}else{t=t->lchild;search_bst(t,k);}}}//找到指向某个结点,找不到是空9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树2.算法2)插入在查找成功的情况下,不用插入;否则插入新结点,仍满足二叉排序树.voidInsertbst(BiTree*t,DataTypek){BiTnode*f,*p;p=*t;while(p){if(p->data==k)return;f=p;p=((p->data>k)?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(k<f->key)f->lchild=p;Elsef->rchild=p;}9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树2.算法3)删除在查找成功的情况下,删除这个结点,仍满足二叉排序树.分三种情况:删除一个叶子:只需将被删除结点的父结点相应指针域置空.删除的结点只有棵子树:将子树结点替换父结点.删除的结点左右子树均有:PL接替*P成为*F的子树,PR成为PL最右下结点的右子树

PR接替*P成为*F的子树,PL成为PR最左下结点的左子树9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树3.性能分析平均查找长度:最坏情况:9.2动态查找表一、二叉排序树9.2动态查找表二、平衡二叉树1.定义对于一棵非空二叉排序树,它的左子树和右子树都是一棵平衡二叉树,且左子树和右子树的高度之差绝对值不超过1。平衡因子:该结点的左子树和右子树高度之差,它的值只能为-1、0、1。2。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）9.2动态查找表二、平衡二叉树9.2动态查找表三、B-树1.定义对于一棵非空二叉排序树,它的左子树和右子树都是一棵平衡二叉树,且左子树和右子树的高度之差绝对值不超过1。平衡因子:该结点的左子树和右子树高度之差,它的值只能为-1、0、1。2。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）9.2动态查找表三、B-树9.2动态查找表三、B-树1。定义一棵m阶的B—树，或者是空树，或者是满足下列性质的m叉树:(1)树中每个结点至多有m

棵子树；(2)根结点至少有两棵子树；所有叶子结点都出现在同一层次，可用来“查找失败”处理。(3)除根结点之外的非终端结点至少有

m/2棵子树；9.2动态查找表三、B-树(1)树中每个结点至多有m棵子树；(2三、B-树1。定义183312233048101520212431454750529.2动态查找表三、B-树1833122330481015202三、B-树2。插入新记录将插入到相应的叶子结点中。18331223304810152021243145475052叶子结点只包含1个记录插入新记录

119.2动态查找表三、B-树1833122330481015202叶子结点只包含1个记录插入新记录

18331223304815202124314547505210119.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。叶子结点只包含1个记录插入新记录18331223318331223304810152021243145475052叶子结点只包含2个记录插入新记录，分裂－提升

559.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。1833122330481015202124311833122330481015202124314547505255叶子结点只包含2个记录插入新记录，分裂－提升

插入9.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。1833122330481015202124311833122330481015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

分裂5055529.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。18331223304810152021243118331223301015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

提升505548529.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。18331223301015202124314518331223304810152021243145475052情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。9.2动态查找表三、B-树3。删除1833122330481015202124311833122330481015243145475052情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。219.2动态查找表三、B-树3。删除18331223304810152431454718331223304810152021243145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。9.2动态查找表三、B-树3。删除183312233048101520212431183312213048101520233145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。9.2动态查找表三、B-树3。删除183312213048101520233145183312213048101520233145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除1833122130481015202331451833122021481015303145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除1833122021481015303145471833122021481015303145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除183312202148101530314547202148333145475052情况2：从包含1个记录的叶子结点中删除这个记录。10121830解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除202148333145475052情况2：从包48333045475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。25209.2动态查找表三、B-树3。删除48333045475052情况2：从包含1个记录的散列即是一种存储方式,又是一种查找方法.一、概念基本思想：根据问题中的关键字构造一个合适的函数，利用这个函数求得各记录的存储位置，然后存储；在查找时用相同的函数找其元素。即：Addr(ai)=H(Ki)Addr(ai)为ai的存储地址H为散列函数Ki为ai的关键字9.3哈希表散列即是一种存储方式,又是一种查找方法.9.3哈希表散列即是一种存储方式,又是一种查找方法.一、概念散列表（哈希表）：按散列存储方式构造的存储结构为散列表。散列函数：H（Ki)关键字与表的对应关系。散列地址：散列函数的值。散列：将结点按关键字的散列地址存储到散列表的过程。同义词：K1<>K2，但H（K1）=H（K2），映射到同一地址的关键码K1和K2为同义词。冲突：K1<>K2，但H（K1）=H（K2），同义词争夺同一地址。9.3哈希表散列即是一种存储方式,又是一种查找方法.9.3哈希表二、构造哈希表1。直接定址法取关键字的某个线性函数值为哈希地址。H(key)=a*key+b例：H(key)=学号-20091001002。数字分析法把字符型关键词量化，对其中的数字进行分析，谁最均匀就取谁。3。除留求余法H(key)=key%pp<=mm为哈希表的表长p为不超过m的最大素数例：23351848107943609.3哈希表二、构造哈希表9.3哈希表三、处理冲突的方法冲突发生时，为后来的关键字找到另一个空的哈希地址。1。开放定址法线性探测法Hi=(H(key)+di)modmH(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哈希表三、处理冲突的方法9.3哈希表三、处理冲突的方法冲突发生时，为后来的关键字找到另一个空的哈希地址。2.拉链法设哈希函数得到的哈希地址在区间[0，m-1]上，以每个哈希地址作为一个指针，指向一个链。每个链表中的结点都是同义词9.3哈希表三、处理冲突的方法9.3哈希表

设{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函数为：Hash(key)=keymod11，用拉链法处理冲突，则建表如右图所示。

012345678910221189347379229716508109.3哈希表设{47,7,29,11,16,92,02数据结构

李萍

数据结构李萍第九章查找主要学习内容:掌握顺序表和有序表的查找掌握索引顺序表的查找掌握二叉排序树的构造和查找掌握平衡二叉树的平衡方法掌握B-树查找、插入和删除掌握哈希表的构造和查找掌握各种查找方法在等概率的情况下查找成功和不成功的平均查找长度第九章查找主要学习内容:9.1静态查找表一、定义1.查找表：具有同一类型（属性）的数据元素组成的集合，可以进行的运算：查找、读表员、插入和删除。依据是否包含插、删运算可分为静态查找表和动态查找表。2.关键码:是数据元素某项的值,用它可以标识一个数据元素3.衡量一个查找方法好坏的主要标准：平均比较次数、附加空间、算法的复杂性。9.1静态查找表一、定义一、顺序表的查找1.基本思想2.存储结构3.算法实现4.性能分析9.1静态查找表一、顺序表的查找9.1静态查找表二、有序表的查找1.两点要求表只能顺序存储表中的元素必须有序排列2.基本思想先确定待查记录所在范围,然后取中间元素作为比较对象,若相等,则查找成功,否则如果小于中间元素则将查找区域缩小到左半部分,否则缩小到右半部分,直到找到或找不到该记录为止.3.算法实现9.1静态查找表二、有序表的查找9.1静态查找表9.1静态查找表二、有序表的查找4.性能分析具有n个结点的判定树的深度为查找成功的比较次数恰好就是该结点的层数,最多的比较次数为树的深度查找不成功的比较次数最多就是也就是树的深度查找具体有序表的平均比较次数9.1静态查找表二、有序表的查找三、分块查找(索引顺序表查找)1.基本思想分块查找要求将查找表分成若干子表,并对子表建立索引表,查找表的每一个子表由索引表中的索引项确定.索引项元素必须顺序存储元素必须有序排列2.基本思想先在索引表中确定要查找的分块,在分块内进行顺序查找.9.1静态查找表三、分块查找(索引顺序表查找)9.1静态查找表9.1静态查找表三、分块查找3.算法实现4.性能分析9.1静态查找表三、分块查找一、二叉排序树1.定义一棵非空的二叉排序树满足以下特征：左子树（如果存在）上的所有结点的值均小于根结点的值。右子树（如果存在）上的所有结点的值均大于根结点的值。根结点的左右子树也都是二叉排序树。9.2动态查找表607080505540LNPEMCY一、二叉排序树9.2动态查找表607080505540LNP一、二叉排序树2.算法1)查找BiTreesearch_bst(BiTreet,DataTypek){if(t==NULL) return(NULL);else{if(t->data==k)returnt;elseif(t->data<k){t=t->rchild;search_bst(t,k);}else{t=t->lchild;search_bst(t,k);}}}//找到指向某个结点,找不到是空9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树2.算法2)插入在查找成功的情况下,不用插入;否则插入新结点,仍满足二叉排序树.voidInsertbst(BiTree*t,DataTypek){BiTnode*f,*p;p=*t;while(p){if(p->data==k)return;f=p;p=((p->data>k)?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(k<f->key)f->lchild=p;Elsef->rchild=p;}9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树2.算法3)删除在查找成功的情况下,删除这个结点,仍满足二叉排序树.分三种情况:删除一个叶子:只需将被删除结点的父结点相应指针域置空.删除的结点只有棵子树:将子树结点替换父结点.删除的结点左右子树均有:PL接替*P成为*F的子树,PR成为PL最右下结点的右子树

PR接替*P成为*F的子树,PL成为PR最左下结点的左子树9.2动态查找表一、二叉排序树9.2动态查找表一、二叉排序树3.性能分析平均查找长度:最坏情况:9.2动态查找表一、二叉排序树9.2动态查找表二、平衡二叉树1.定义对于一棵非空二叉排序树,它的左子树和右子树都是一棵平衡二叉树,且左子树和右子树的高度之差绝对值不超过1。平衡因子:该结点的左子树和右子树高度之差,它的值只能为-1、0、1。2。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）9.2动态查找表二、平衡二叉树9.2动态查找表三、B-树1.定义对于一棵非空二叉排序树,它的左子树和右子树都是一棵平衡二叉树,且左子树和右子树的高度之差绝对值不超过1。平衡因子:该结点的左子树和右子树高度之差,它的值只能为-1、0、1。2。构造单向左旋、单向右旋、双向旋转（先左后右）、双向旋转（先右后左）9.2动态查找表三、B-树9.2动态查找表三、B-树1。定义一棵m阶的B—树，或者是空树，或者是满足下列性质的m叉树:(1)树中每个结点至多有m

棵子树；(2)根结点至少有两棵子树；所有叶子结点都出现在同一层次，可用来“查找失败”处理。(3)除根结点之外的非终端结点至少有

m/2棵子树；9.2动态查找表三、B-树(1)树中每个结点至多有m棵子树；(2三、B-树1。定义183312233048101520212431454750529.2动态查找表三、B-树1833122330481015202三、B-树2。插入新记录将插入到相应的叶子结点中。18331223304810152021243145475052叶子结点只包含1个记录插入新记录

119.2动态查找表三、B-树1833122330481015202叶子结点只包含1个记录插入新记录

18331223304815202124314547505210119.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。叶子结点只包含1个记录插入新记录18331223318331223304810152021243145475052叶子结点只包含2个记录插入新记录，分裂－提升

559.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。1833122330481015202124311833122330481015202124314547505255叶子结点只包含2个记录插入新记录，分裂－提升

插入9.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。1833122330481015202124311833122330481015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

分裂5055529.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。18331223304810152021243118331223301015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

提升505548529.2动态查找表三、B-树2。插入新记录将插入到相应的叶子结点中。18331223301015202124314518331223304810152021243145475052情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。9.2动态查找表三、B-树3。删除1833122330481015202124311833122330481015243145475052情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。219.2动态查找表三、B-树3。删除18331223304810152431454718331223304810152021243145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。9.2动态查找表三、B-树3。删除183312233048101520212431183312213048101520233145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。9.2动态查找表三、B-树3。删除183312213048101520233145183312213048101520233145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除1833122130481015202331451833122021481015303145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除1833122021481015303145471833122021481015303145475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除183312202148101530314547202148333145475052情况2：从包含1个记录的叶子结点中删除这个记录。10121830解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。9.2动态查找表三、B-树3。删除202148333145475052情况2：从包48333045475052情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。25209.2动态查找表三、B-树3。删除48333045475052情况2：从包含1个记录的散列即是一种存储方式,又是一种查找方法.