《数据结构(C／C描述)》-第8章查找课件

1、第8章查找第8章查找8.1 基本概念 8.2 静态查找8.3 动态查找8.4 哈希查找 8.1 基本概念 一、 何谓查找表 ？ 查找表是由同一类型的数据元素（或记录）构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。8.1 基 本 概 念一、 何谓查找表 ？ 查找表是由同一类型的数据元二、 对查找表经常进行的操作1. 查询某个“特定的”数据元素是否在查找表中；2. 检索某个“特定的”数据元素的各种属性；3. 在查找表中插入一个数据元素；4. 从查找表中删去某个数据元素。二、 对查找表经常进行的操作1. 查询某个“特定的”数据元素仅作查询和检索操作的查找

2、表。1. 静态查找表有时在查询之后，还需要将不在查找表中的数据元素插入到查找表中；或者，从查找表中删除指定的数据元素。2. 动态查找表三、查找表的分类仅作查询和检索操作的查找表。1. 静态查找表有时在查询之是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。四、关键字 若此关键字可以识别惟一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称之谓“次关键字”。是数据元素（或记录）中某个数据项的值，用以标识（识别）一例如：学生管理系统中，可将姓名作为关键字，也可将学号作为关键字。学号 姓名 专业 年龄 01 王洪 计算机 17 02 孙文 计算机 18 0

3、3 谢军 计算机 18 04 李辉 计算机 20 05 沈福 计算机 25 06 余斌 计算机 19 07 巩力 数学 17 08 王辉 数学 18例如：学生管理系统中，可将姓名作为关学号 姓名 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）的过程。五、查找 若查找表中存在这样一个记录，则称查找成功，返回整个记录的信息，或返回该记录在查找表中的位置；否则称查找不成功，返回空记录或空指针。 根据给定的某个值，在查找表中确定一个其关键字等于给定值由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表的元素之间人为地 附加某种

4、确定的关系，即： 用另外一种结构来表示查找表。六、如何进行查找查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，因此不便8.2静 态 查 找 8.2静 态 查 找 数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;数据元素类型的定义为:typedef struct 以顺序表或线性链表表示静态查找表的查找。8.2.1 顺序查找顺序表 以顺序表或线性链表表示静态查找表的查找。8.2.se_listii查找成功！查找失败！key = 64642137881992056456807513 0 1

5、2 3 4 5 6 7 8 9 10 11 se_listi60key = 64i2137881992056456807513 0 1 2 3 4 5 6 7 8 9 10 11 se_listii查找成功！查找失败！key = 64642分析顺序查找的时间性能。 定义： 查找算法的平均查找长度ASL 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第 i 个记录的概率 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数分析顺序查找的时间性能。 定义： 查找算法的平均查找顺序表查找的平均查找长度为：对顺序表而言，Ci = n-i+

6、1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表而言，Ci = n-i+ 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。8.2.2 折半查找顺序表 若以有序表表示静态查找表，则查找过程可以折半进行。 上述顺序查找表的查找算法简单，bi_list 长度n例如， key = 64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。bi_list 长度n例如， key = 64 的查

7、找过程如int binarysearch(elemtype bi_list,keytype key,int n)/在有序表bi_list1bi_listn中查找关键字为key的记录int low,high,mid;low=1;high=n;while(low=high) mid=(low+high)/2;if(bi_listmid.key=key) break;/找到记录else if(bi_listmid.keykey)low=mid+1;/在右半继续查找 else high=mid-1;/在左半继续查找if(low50 时，可得近似结果 假设 n=2h-1 并且查找概率相等 一般情况下8.

8、2.3 分块查找（索引顺序查找）在建立顺序表的同时，建立一个索引。012345678910111213170821191431332225405261784621 040 578 10例如：索引顺序表 = 索引表 + 顺序表顺序表索引8.2.3 分块查找（索引顺序查找）在建立顺序表的同时，建索引顺序表的查找过程： 1. 由索引确定记录所在区间；2. 在顺序表的某个区间内进行查找。可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。索引顺序表的查找过程： 1. 由索引确定记录所在区间；2. 索引表最大关键字起始地址2212138920334244382448605874498653第1块第2

9、块第3块224886例：2248861713特点：块间有序 块内无序顺序表索引表最大关键字起始地址2212138920334244388.3 动 态 查 找8.3 动 态 查 找8.3.1 二叉排序树（二叉查找树）1定义2查找算法3插入算法4删除算法5查找性能的分析8.3.1 二叉排序树（二叉查找树）1定义2查找算法3（1）若它的左子树不空，则左子树上所有结点 的值均小于根结点的值；1定义： 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点 的值均大于根结点的值；（1）若它的左子树不空，则左子树上所有结点

10、1定义： 503080209010854035252388例如:是二叉排序树。66不503080209010854035252388例如:是二叉 通常，取二叉链表作为二叉排序树的存储结构。typedef struct bsnode /定义二叉排序树中的结点类型 keytype key;struct bsnode *lchild;struct bsnode *rchild;bsnodetype; 通常，取二叉链表作为二叉排序树的存储结构。2二叉排序树的查找算法1. 若给定值等于根结点的关键字, 则查找成功；2. 若给定值小于根结点的关键字，则继续在左子树上进行查找；3. 若给定值大于根结点的关键

11、字，则继续在右子树上进行查找。否则:若二叉排序树为空，则查找不成功；2二叉排序树的查找算法1. 若给定值等于根结点的关键字, 50308020908540358832例如:二叉排序树查找关键字= 50 ,505035 ,503040355090 ,50809095 ,50308020908540358832例如:二叉排序树查找从上述查找过程可见，在查找过程中，生成了一条查找路径: 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 查找成功 查找不成功从上述查找过程可见，在查找过程中，生成了一条查找路径: 算

12、法8.5 用非递归算法描述二叉排序树的查找 ：bsnodetype *bs_search(bsnodetype *bt,keytype key) bsnodetype *p=bt; /指针p指向根结点，搜索从根结点开始while (p!=NULL&p-key!=key) if(keykey) p=p-lchild; else p=p-rchild; return (p);算法8.5 用非递归算法描述二叉排序树的查找 ：3二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点。其插入位置由查找过程得到。3二叉排序树的插入算法若二叉排序树为空树，

13、则新插入的结点为二叉排序树的插入算法（算法8.6）如下：void bs_insert (bsnodetype *bt , bsnodetype *pn) if(*bt=NULL) *bt=pn; /如果根结点为空，就把待插结点作为根结点 else if(*bt)-keypn-key) bs_insert(&(*bt)- lchild,pn) ; /如果待插结点的值小于根结点，就插入到左子树中 else if(*bt)-keykey) bs_insert(&(*bt)- rchild,pn) ; /如果待插结点的值大于根结点，就插入到右子树中二叉排序树的插入算法（算法8.6）如下：（1）被删除的

14、结点是叶子；（2）被删除的结点只有左子树或者只有右子树（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法可分 3 种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。（1）被删除的结点是叶子；4二叉排序树的删除算法可分 3 （1）被删除的结点是叶子结点其双亲结点中相应指针域的值改为“空”（2）被删除的结点只有左子树或者 只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。（3）被删除的结点既有左子树，也有右子树以其前驱替代之，然后再删除该前驱结点（1）被删除的结点是叶子结点其双亲结点中相应

15、指针域的值改为“void bs_delete ( bsnodetype *bt, keytype key)bsnodetype *p,*q,*r,*s;p=NULL;q=*bt;while(q&(q-key!=key)p=q;if(keykey)q=q-lchild;elseq=q-rchild; /在二叉树中查找关键字等于key的结点删除算法描述如下： void bs_delete ( bsnodetype *if(q=NULL) return;/如果二叉树中没有该结点，则不进行删除，直接返回if(q-lchild=NULL) s=q-rchild;else s=q-lchild;r=s;w

16、hile(r-rchild)r=r-rchild;r-rchild=q-rchild;/若被删结点有左子树，则在其左子树中找到中序遍历下的最后一个结点r if(q=NULL) return; if(p=NULL)*bt=s; /如果要删除的结点是根结点，就令s为根结点else if(q=p-lchild)p-lchild=s;elsep-rchild=s;free(q); if(p=NULL) 若被删结点没有左子树，则用其右孩子代替它（注意，右孩子可以为空）若被删结点有左子树，则在其左子树中找到中序遍历的最后一个结点r，把被删结点的右子树作为结点r的右子树，并用被删结点的左孩子代替被删结点。若

17、被删结点没有左子树，则用其右孩子代替它（注意，右孩子可以为注意：如果被删结点是根结点，同样适用上述方法，只不过要对根结点做调整，因为原根结点要被删除，所以把取代根结点的结点作为新的根结点。注意：如果被删结点是根结点，同样适用上述方法，只不过要对根结5二叉排序树的查找性能分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。5二叉排序树的查找性能分析 对于由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字序列 1，2，3，4，5构造而得的二叉排序树，

18、例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5= 2.2含n个结点的平均查找长度为：由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字8.3.2 平衡二叉树什么是平衡二叉树(Balanced Binary Tree) ?平衡二叉树是空树,或者是具有以下性质的二叉树:它的左子树和右子树也都是平衡二叉树并且左子树和右子树的深度之差的绝对值不超过1结点的平衡因子BF(Balance Factor)是左子树的深度减去右子树的深度,它只可能是-1,0,1平衡二叉树(也称AVL树)的深度为O(log N)(其中N为结点个数)它的平均

19、查找长度也是O(log N)8.3.2 平衡二叉树什么是平衡二叉树(Balanced 平衡二叉树及平衡因子举例-1100-110平衡的二叉树1100平衡二叉树及平衡因子举例-1100-110平衡的二叉树110不平衡的二叉树-1000-210 2-101 00不平衡二叉树及平衡因子举例不平衡的二叉树-1000-210 2-101 00不平衡二叉二叉排序树转成平衡树示例设关键字序列为(13,24,37,90,53) 013-113 024 037 013-213-124 024 037 053 013 013 037 090 053-124 190-237-224(a)(b)(c)(d)(e)(f

20、)(g)(h)2413375390二叉排序树转成平衡树示例设关键字序列为(13,24,37二叉排序树转成平衡树失去平衡后进行调整的4种情况(1)单向右旋平衡处理当在左子树上插入左结点,使平衡因子由1增至2时(2)单向左旋平衡处理(上例从图(d)到图(e)当在右子树上插入右结点,使平衡因子由-1增至-2时(3)双向旋转(先左后右)平衡处理当在左子树上插入右结点,使平衡因子由1增至2时(4)双向旋转(先右后左)平衡处理当在右子树上插入左结点,使平衡因子由-1增至-2时(例如上例从图(f)右旋到图(g)再左旋到图(h)二叉排序树转成平衡树失去平衡后进行调整的4种情况(1)单向 B-树是一种多路平衡查

21、找树。它适合在磁盘等直接存取设备上组织动态的查找表。 一棵m阶的B_树，或为空树，或为满足下列特性的m叉树：（1）所有的非终端结点的结构如下：8.3.3 B_ 树和B树nP0K1P1K2P2KiPiKnPn一、 B_ 树 B-树是一种多路平衡查找树。它适合在磁盘等直接存取设其中： K1，K2，Kn为n个按从小到大顺序排列的关键字； P0，P1，P2，Pn为（n+1）个指针，用于指向该结点的（n+l）棵子树，P0所指向的子树中的所有关键字的值均小于K1；Pn所指向的子树中的所有关键字的值均大于Kn；Pi（1in-1）所指向的子树中的所有关键字的值均大于Ki且小于Ki+1； n（nm-1）为结点中

22、关键字的个数，所以子树个数为（n+1）。数据结构(CC描述)-第8章查找课件（2）树中每个结点至多有m棵子树。（3）若根结点不为叶子结点，则它至少有两棵子树。（4）除根之外的所有非终端结点至少有棵子树。 （5）所有叶子结点在同一个层次上，且不含有任何信息（可以看作外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。（2）树中每个结点至多有m棵子树。15013027090125235401553758085195abcdefghB_树示例150130270901252354015537580851 B+树是B-树的一种变形树。一棵m阶的B+树满足下列条件：（1）每个结点至多

23、有m棵子树。（2）根结点或者没有子树或者至少有两棵子树。（3）除了根结点以外，每个分支结点至少有 棵子树。（4）树叶都在最底层，包含了所有的关键字以及指向相应记录的指针，而且按关键字的大小顺序链接。二、B树二、B树（5）有n棵子树的分支结点中含有n个关键字，而且每个关键字都不小于对应子树中最大的关键字。B+树与B-树的差异在于：（1）B+树中，有n棵子树的结点中含有n个关键字；而B-树中有n+1棵子树的结点中含有n个关键字。（2）B+树中所有的叶子结点包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小从小到大顺序链接（3）所有的非终端结点可以看成是索引部分，结

24、点中仅含有其子树中最大（或最小）的关键字。（5）有n棵子树的分支结点中含有n个关键字，而且每个关键字都a30 38 4065 75 8025 304055 6570 75bdcefg80hroot38i40 65sqtB+树示例a30 38 4065 75 8025 30405 一、什么是哈希表？二、哈希函数的构造方法三、处理冲突的方法 四、哈希表的查找8.4 哈 希 表 一、什么是哈希表？二、哈希函数的构造方法三、处理冲突的方法 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，一、什么是哈希表？ 查找的过程为给定值依次和关键字集合中各个关键

25、字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。 以上两节讨论的表示查找表的各种结构的共同特点 用这类方法表示的查找表，其平均查找长度ASL都不为零。 不同的表示方法，其差别仅在于关键字和给定值进行比较的顺序不同。 用这类方法表示的查找表，其平均查找长度ASL 只有一个办法：预先知道所查关键字在表中的位置。 对于频繁使用的查找表，希望 ASL = 0。 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 只有一个办法：预先知道所查关键字在表中的位置但是，对于动态查找表而言， 因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key) 作为关键字

26、为 key 的记录在表中的位置，通常称这个函数 H (key) 为哈希函数。(1) 表长不确定；(2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。但是，对于动态查找表而言， 因此在一般情况下，哈希表的定义: 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。哈希表的定义: 根据设定的哈希函数 H(key二、构造哈希函数的方法 对数字的关键字可有下列构造方法:1. 直接定址法3. 平方取中法5. 除留余数法4.

27、 折叠法6. 随机数法2. 数字分析法二、构造哈希函数的方法 对数字的关键字可有下列构造方法:哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b1. 直接定址法此法仅适合于：地址集合的大小 = = 关键字集合的大小哈希函数为关键字的线性函数1. 直接定址法此法仅适合于：5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中： pm (表长) 并且 p 应为不大于 m 的素数 5. 除留余数法 设定哈希函数为: 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 实际造表