数据结构-王红梅-第7章 查找技术

《数据结构-王红梅-第7章 查找技术》由会员分享，可在线阅读，更多相关《数据结构-王红梅-第7章 查找技术（90页珍藏版）》请在金锄头文库上搜索。

1、数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社第第 7 章章 查找技术查找技术本章的主要内容是本章的主要内容是:查找的基本概念查找的基本概念线性表的查找技术线性表的查找技术树表的查找技术树表的查找技术散列表的查找技术散列表的查找技术 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社查找的基本概念查找的基本概念查找的基本概念查找的基本概念p 关键码关键码：可以标识一个记录的某个数据项。：可以标识一个记录的某个数据项。 p 键值键值：关键码的值。：关键码的值。p 主关键码主关键码：可以唯一地标识一个记录的关键码。：可以唯一地标识一个记录的关键码。p 次

2、关键码次关键码：不能：不能唯一地标识一个记录的关键码。唯一地标识一个记录的关键码。7.1 概述概述50女女李爽李爽000525女女齐梅齐梅000447女女刘楠刘楠000325男男张亮张亮000238男男王刚王刚0001年龄年龄性别性别姓名姓名职工号职工号1972.92003.71979.92003.71990.4工作时间工作时间数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社查找的基本概念查找的基本概念查找的基本概念查找的基本概念p 查找查找 ：在具有相同类型的记录构成的：在具有相同类型的记录构成的集合集合中找出满中找出满足足给给定条件定条件的记录。的记录。 p 给定的查

3、找条件可能是多种多样的，为便于讨论，给定的查找条件可能是多种多样的，为便于讨论，把查找条件限制为把查找条件限制为“匹配匹配”，即查找关键码等于给定，即查找关键码等于给定值的记录。值的记录。 7.1 概述概述p 查找的结果查找的结果 ：若在查找集合中找到了与给定值相匹：若在查找集合中找到了与给定值相匹配的记录，则称配的记录，则称查找成功查找成功；否则，称；否则，称查找查找失败失败。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 静态查找静态查找 ：不涉及插入和删除操作的查找：不涉及插入和删除操作的查找 。p 动态查找动态查找 ：涉及插入和删除操作的查找。：涉及插入和删

4、除操作的查找。 7.1 概述概述查找的基本概念查找的基本概念查找的基本概念查找的基本概念静态查找适用于：查找集合一经生成，便只对其进行静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。当查找不成功时，要插入被

5、查找的记录。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社7.1 概述概述查找的基本概念查找的基本概念查找的基本概念查找的基本概念查找结构查找结构 ：面向查找操作的数据结构面向查找操作的数据结构 ，即查找基于的，即查找基于的数据结构。数据结构。查找结构查找结构 查找方法查找方法 集合中元素之间不存在明显的组织规律，不便查找。集合中元素之间不存在明显的组织规律，不便查找。集合集合 线性表线性表 树树 表表 散列表散列表 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社本章讨论的查找结构本章讨论的查找结构 ： 线线性性表表：适适用用于于静静态态查查找找

6、，主主要要采采用用顺顺序序查查找找技技术术和折半查找技术。和折半查找技术。 树树表表：适适用用于于动动态态查查找找，主主要要采采用用二二叉叉排排序序树树的的查查找技术。找技术。 散列表散列表：静态查找和动态查找均适用，主要采用散：静态查找和动态查找均适用，主要采用散列技术。列技术。 7.1 概述概述查找结构查找结构 ：面向查找操作的数据结构面向查找操作的数据结构 ，即查找基于的，即查找基于的数据结构。数据结构。查找的基本概念查找的基本概念查找的基本概念查找的基本概念数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社查找算法的性能查找算法的性能查找算法的性能查找算法的性能 查

7、找算法时间性能通过关键码的比较次数来度量。查找算法时间性能通过关键码的比较次数来度量。7.1 概述概述关键码的比较次数与哪些因素有关呢？关键码的比较次数与哪些因素有关呢？平均查找长度：平均查找长度：将查找算法进行的关键码的比较次数将查找算法进行的关键码的比较次数的数学期望值定义为的数学期望值定义为平均查找长度平均查找长度，即：，即： 其中：其中：n：问题规模，查找集合中的记录个数；问题规模，查找集合中的记录个数； pi：查找第查找第i个记录的概率；个记录的概率； ci：查找第查找第i个记录所需的关键码的比较次数。个记录所需的关键码的比较次数。ASL = = =niiicp1数据结构（数据结构（

8、C+版）第版）第2版版清华大学出版社清华大学出版社查找算法的性能查找算法的性能查找算法的性能查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。查找算法时间性能通过关键码的比较次数来度量。7.1 概述概述关键码的比较次数与哪些因素有关呢？关键码的比较次数与哪些因素有关呢？平均查找长度：平均查找长度：将查找算法进行的关键码的比较次数将查找算法进行的关键码的比较次数的数学期望值定义为的数学期望值定义为平均查找长度平均查找长度，即：，即： ASL = = =niiicp1ci取决于算法；取决于算法；pi与算法无关，取决于具体应用。如果与算法无关，取决于具体应用。如果pi是已知的，则平均查找长

9、度只是问题规模的函数。是已知的，则平均查找长度只是问题规模的函数。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序查找顺序查找顺序查找顺序查找 （线性查找）（线性查找）（线性查找）（线性查找）基本思想基本思想：从线性表的一端向另一端逐个将关键码与：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。等的关键码，则查找失败，给出失败信息。 10 15 24 6 12

10、35 40 98 550 1 2 3 4 5 6 7 8 9 i7.2 线性表的查找技术线性表的查找技术例：查找例：查找k35iii数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序查找顺序查找顺序查找顺序查找 （线性查找）（线性查找）（线性查找）（线性查找）7.2 线性表的查找技术线性表的查找技术int SeqSearch1( (int r , int n, int k) )/数组数组r1 rn存放查找集合存放查找集合 i = n; while ( (i 0 & ri != k) ) i-; return i;数据结构（数据结构（C+版）第版）第2版版清华大学出版社清

11、华大学出版社基本思想基本思想：设置：设置“哨兵哨兵”。哨兵就是待查值，将它放。哨兵就是待查值，将它放在查找方向的在查找方向的尽头尽头处，免去了在查找处，免去了在查找过程中每一次比过程中每一次比较后都要判断查找位置是否较后都要判断查找位置是否越界越界，从而提高查找速度。，从而提高查找速度。 7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找改进的顺序查找改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k35iii哨兵哨兵35查找方向查找方向数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学

12、出版社基本思想基本思想：设置：设置“哨兵哨兵”。哨兵就是待查值，将它放。哨兵就是待查值，将它放在查找方向的在查找方向的尽头尽头处，免去了在查找处，免去了在查找过程中每一次比过程中每一次比较后都要判断查找位置是否较后都要判断查找位置是否越界越界，从而提高查找速度。，从而提高查找速度。 7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找改进的顺序查找改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k25ii25查找方向查找方向iiiiiii数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出

13、版社int SeqSearch2(int r , int n, int k) /数组数组r1 rn存放查找集合存放查找集合 r0 = k; i = n; while (ri != k) i-; return i;7.2 线性表的查找技术线性表的查找技术改进的顺序查找改进的顺序查找改进的顺序查找改进的顺序查找 ASL= = =niicp1 + +- -= =niiinp1) 1(i= (n+1)/2=O(n)数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社平均查找长度较大，特别是当待查找集合中元素较多平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。时，查找效

14、率较低。7.2 线性表的查找技术线性表的查找技术顺序查找的缺点：顺序查找的缺点：顺序查找的缺点：顺序查找的缺点：对表中记录的存储没有任何要求，顺序存储和链接对表中记录的存储没有任何要求，顺序存储和链接存储均可；存储均可；对表中记录的有序性也没有要求，无论记录是否按对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。关键码有序均可。顺序查找的优点：顺序查找的优点：顺序查找的优点：顺序查找的优点：算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社折半查找折半查找折半查找折半查找使用条

15、件使用条件：线性表中的记录必须按关键码线性表中的记录必须按关键码有序有序；必须采用必须采用顺序顺序存储存储。基本思想基本思想：在有序表中，取：在有序表中，取中间中间记录作为比较对象，记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若若给定值与中间记录的关键码相等，则查找成功；若给定值给定值小于小于中间记录的关键码，则在中间记录的中间记录的关键码，则在中间记录的左半左半区继续查找；若给定值区继续查找；若给定值大于大于中间记录的关键码，则在中间记录的关键码，则在中间记录的中间记录的右半右半区继续查找。不断重复上述过程，直区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录

16、，查找失败。到查找成功，或所查找的区域无记录，查找失败。7.2 线性表的查找技术线性表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社折半查找的基本思想折半查找的基本思想折半查找的基本思想折半查找的基本思想7.2 线性表的查找技术线性表的查找技术 r1 rmid- -1 rmid rmid+1 rn 如果如果krmid 查找左半区查找左半区 查找右半区查找右半区k（mid=(1+n)/2）数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：查找值为例：查找值为14的记录的过程：的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 1

17、1 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 311418147221822low=4mid=4 21high数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社int BinSearch1(int r , int n, int k) /数组数组r1 rn存放查找集合存放查找集合 low = 1; high = n; while (low = high) mid = (low + high) / 2; if (k rmid) low = mid

18、+ 1; else return mid; return 0;7.2 线性表的查找技术线性表的查找技术折半查找折半查找折半查找折半查找非递归算法非递归算法非递归算法非递归算法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社int BinSearch2(int r , int low, int high, int k) /数组数组r1 rn存放查找集合存放查找集合 if (low high) return 0; else mid = (low + high) / 2; if (k rmid) return BinSearch2(r, mid+1, high, k); els

19、e return mid; 7.2 线性表的查找技术线性表的查找技术折半查找折半查找折半查找折半查找递归算法递归算法递归算法递归算法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社折半查找判定树折半查找判定树 判定树判定树：折半查找的过程可以用二叉树来描述，树中折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该的每个结点对应有序表中的一个记录，结点的值为该记录在记录在表中的位置。通常称这个描述折半查找过程的表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称二叉树为折半查找判定树，简称判定树判定树。7.2 线性表的查找技术

20、线性表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 当当n=0时，折半查找判定树为空；时，折半查找判定树为空； 当当n0时，折半查找判定树的根结点是有序表中时，折半查找判定树的根结点是有序表中序号为序号为mid=( (n+1) )/2的记录，根结点的左子树是与有的记录，根结点的左子树是与有序表序表r1 rmid- -1相对应的折半查找判定树，根结点相对应的折半查找判定树，根结点的的右子树是与右子树是与rmid+1 rn相对应的折半查找判定相对应的折半查找判定树。树。 7.2 线性表的查找技术线性表的查找技术判定树的构造方法判定树的构造方法数据结构（数据结构（

21、C+版）第版）第2版版清华大学出版社清华大学出版社7.2 线性表的查找技术线性表的查找技术 11223344510111191089785667内部结点内部结点外部结点外部结点3691011784512判定树的构造方法判定树的构造方法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社具有具有n个结个结点的折半查找判定树的深度为点的折半查找判定树的深度为 查查找找成成功功：在在表表中中查查找找任任一一记记录录的的过过程程，即即是是折折半半查查找找判判定定树树中中从从根根结结点点到到该该记记录录结结点点的的路路径径，和和给给定定值值的比较次数等于该记录结点在树中的层数。的比较次

22、数等于该记录结点在树中的层数。查查找找不不成成功功：查查找找失失败败的的过过程程就就是是走走了了一一条条从从根根结结点点到到外外部部结结点点的的路路径径，和和给给定定值值进进行行的的关关键键码码的的比比较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。7.2 线性表的查找技术线性表的查找技术。 1log2+ +n折半查找性能分析折半查找性能分析 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树二叉排序树二叉排序树二叉排序树二叉排序树二叉排序树（也称（也称二叉查找树二叉查找树）：或者是一棵空的二）：或者是一棵空的二叉树，或者是具有下列性质的二叉树

23、：叉树，或者是具有下列性质的二叉树： 若若它它的的左左子子树树不不空空，则则左左子子树树上上所所有有结结点点的的值值均均小小于根结点的值；于根结点的值； 若若它它的的右右子子树树不不空空，则则右右子子树树上上所所有有结结点点的的值值均均大大于根结点的值；于根结点的值； 它的左右子树也都是二叉排序树。它的左右子树也都是二叉排序树。7.3 树表的查找技术树表的查找技术二叉排序树的定义采用的是递归方法。二叉排序树的定义采用的是递归方法。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树二叉排序树 非二叉排序树非二叉排序树二叉排序树二叉排序树二叉排序树二叉排序树7.3 树

24、表的查找技术树表的查找技术6390554258104567837063605582581045678370中序遍历二叉排序树可以得到一个按关键码有序的序列中序遍历二叉排序树可以得到一个按关键码有序的序列 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的存储结构二叉排序树的存储结构以二叉链表形式存储，类声明如下：以二叉链表形式存储，类声明如下：class BiSortTree public: BiSortTree( (int a , int n) ); BiSortTree( )( ); void InsertBST( (BiNode *root , BiNod

25、e *s) ); void DeleteBST( (BiNode *p, BiNode *f ) ); BiNode *SearchBST( (BiNode *root, int k) ); private: BiNode *root; ;7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的插入二叉排序树的插入分析：分析：若二叉排序树为空树，则新插入的结点为新若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。结点，其插入位

26、置由查找过程得到。7.3 树表的查找技术树表的查找技术void InsertBST(BiNode *root , BiNode *s);数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：插入值为例：插入值为98的结点的结点7.3 树表的查找技术树表的查找技术63559058 7098root sroot数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社void BiSortTree:InsertBST(BiNode *root, BiNode *s) if (root = NULL) root = s; else if (s-data data) I

27、nsertBST(root-lchild, s); else InsertBST(root-rchild, s);7.3 树表的查找技术树表的查找技术二叉排序树的插入算法二叉排序树的插入算法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的构造二叉排序树的构造从空的二叉排序树开始，依次插入一个个结点从空的二叉排序树开始，依次插入一个个结点 。例：关键码集合为例：关键码集合为63，90，70，55，58，二二叉排序树的构造过程为：叉排序树的构造过程为： 7.3 树表的查找技术树表的查找技术63559058 70数据结构（数据结构（C+版）第版）第2版版清华大学出版

28、社清华大学出版社BiSortTree:BiSortTree(int r , int n) for (i = 0; i n; i+) s = new BiNode; s-data = ri; s-lchild = s-rchild = NULL; InsertBST(root, s); 7.3 树表的查找技术树表的查找技术二叉排序树的构造算法二叉排序树的构造算法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列变成一个有序序列;每次插入的新结点都是二叉排序树上新的叶子每次插入的新结

29、点都是二叉排序树上新的叶子结点结点;找到插入位置后，不必移动其它结点，仅需修找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；改某个结点的指针；在左子树在左子树/右子树的查找过程与在整棵树上查右子树的查找过程与在整棵树上查找过程相同；找过程相同；新插入的结点没有破坏原有结点之间的关系。新插入的结点没有破坏原有结点之间的关系。小小 结：结：7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的删除二叉排序树的删除在二叉排序树上删除某个结点之后，仍然保持二叉排在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。序树的特性

30、。分三种情况讨论：分三种情况讨论：被删除的结点是叶子；被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树被删除的结点既有左子树，也有右子树。7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社情况情况1被删除的结点是叶子结点被删除的结点是叶子结点7.3 树表的查找技术树表的查找技术50302080908588403532503020809085403532操作：操作：将双亲结点中相应指针域的值改为空。将双亲结点中相应指针域的值改为空。数据结构（数据结构（C+版）

31、第版）第2版版清华大学出版社清华大学出版社情况情况2被删除的结点只有左子树或者只有右子树被删除的结点只有左子树或者只有右子树操作：操作：将双亲结点的相应指针域的值指向被删除将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。结点的左子树（或右子树）。7.3 树表的查找技术树表的查找技术50302080908588403532503020908588403532数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社情况情况3被删除的结点既有左子树也有右子树被删除的结点既有左子树也有右子树操作：操作：以其左子树中的最大值结点（或右子树以其左子树中的最大值结点（或右子树中的

32、最小值结点）替代之，然后再删除该结点。中的最小值结点）替代之，然后再删除该结点。7.3 树表的查找技术树表的查找技术50302080908588403532403020809085883532数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1. 若结点若结点p是叶子，则直接删除结点是叶子，则直接删除结点p；2. 若结点若结点p只有左子树，则只需重接只有左子树，则只需重接p的左子树；的左子树； 若结点若结点p只有右子树，则只需重接只有右子树，则只需重接p的右子树；的右子树； 3. 若结点若结点p的左右子树均不空，则的左右子树均不空，则 3.1 查找结点查找结点p的右子树上的

33、最左下结点的右子树上的最左下结点s及其双亲结点及其双亲结点par； 3.2 将结点将结点s数据域替换到被删结点数据域替换到被删结点p的数据域；的数据域； 3.3 若结点若结点p的右孩子无左子树，的右孩子无左子树， 则将则将s的右子树接到的右子树接到par的右子树上；的右子树上； 否则，将否则，将s的右子树接到结点的右子树接到结点par的左子树上；的左子树上； 3.4 删除结点删除结点s；7.3 树表的查找技术树表的查找技术二叉排序树的删除算法二叉排序树的删除算法伪代码伪代码数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的查找二叉排序树的查找在二叉排序树中查找给

34、定值在二叉排序树中查找给定值k的过程是：的过程是： 若若root是空树，则查找失败；是空树，则查找失败； 若若kroot-data，则查找成功；否则则查找成功；否则 若若kroot-data，则在则在root的左子树上查找；否则的左子树上查找；否则 在在root的右子树上查找。的右子树上查找。 上上述述过过程程一一直直持持续续到到k被被找找到到或或者者待待查查找找的的子子树树为为空，如果待查找的子树为空，则查找失败。空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率在于只需查找二个子树之一。二叉排序树的查找效率在于只需查找二个子树之一。7.3 树表的查找技术树表的查找技术数据结构（数据

35、结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：在二叉排序树中查找关键字值为例：在二叉排序树中查找关键字值为35，95的过程：的过程：7.3 树表的查找技术树表的查找技术50302080908588403532二叉排序树的查找二叉排序树的查找50302080908588403532数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社BiNode *BiSortTree:SearchBST( (BiNode *root, int k) ) if ( (root = NULL) ) return NULL； else if ( (root-data = k) ) re

36、turn root; else if (k(k -data) ) return SearchBST( (root-lchild, k) ); else return SearchBST( (root-rchild, k) );7.3 树表的查找技术树表的查找技术二叉排序树的查找二叉排序树的查找数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉排序树的查找性能分析二叉排序树的查找性能分析由序列由序列3, 1, 2, 5, 4得到二叉排序树：得到二叉排序树：由序列由序列1, 2, 3, 4, 5得到二叉排序树：得到二叉排序树：ASL =（1+2+3+4+5）/ 5= 3AS

37、L =（1+2+3+2+3）/ 5 = 2.2二叉排序树的查找性能取决于二叉排序树的形状，二叉排序树的查找性能取决于二叉排序树的形状，在在O( (log2n) )和和O( (n) )之间。之间。 7.3 树表的查找技术树表的查找技术1234531254数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社平衡二叉树：平衡二叉树：或者是一棵空的二叉排序树，或者是具或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：有下列性质的二叉排序树： 根结点的左子树和右子树的深度最多相差根结点的左子树和右子树的深度最多相差1; 根结点的左子树和右子树也都是平衡二叉树。根结点的左子树和右

38、子树也都是平衡二叉树。 平衡因子：平衡因子：结点的平衡因子是该结点的左子树的深度结点的平衡因子是该结点的左子树的深度与右子树的深度之差。与右子树的深度之差。 平衡二叉树平衡二叉树平衡二叉树平衡二叉树7.3 树表的查找技术树表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社548254821是平衡树是平衡树 非平衡树非平衡树7.3 散列表的查找技术散列表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡二叉树在平衡树中，结点的平衡因子可以是在平衡树中，结点的平衡因子可以是1，0，-1。结点的平衡因子结点的平衡因子HL-HR数据结构（数据结构（C+版）第版）第2版版清华大

39、学出版社清华大学出版社最小不平衡子树：最小不平衡子树：在平衡二叉树的构造过程中，在平衡二叉树的构造过程中，以距以距离离插入结点插入结点最近的、且平衡因子的绝对值大于最近的、且平衡因子的绝对值大于1的结的结点为点为根根的子树。的子树。 7.3 树表的查找技术树表的查找技术542814平衡二叉树平衡二叉树平衡二叉树平衡二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社构造平衡二叉树的基本思想构造平衡二叉树的基本思想：每插入一个结点，：每插入一个结点，（1）从插入结点开始向上计算各结点的平衡因子，如）从插入结点开始向上计算各结点的平衡因子，如果某结点平衡因子的绝对值超过果某

40、结点平衡因子的绝对值超过1，则说明插入操作破，则说明插入操作破坏了二叉排序树的平衡性，需要进行平衡调整；否则坏了二叉排序树的平衡性，需要进行平衡调整；否则继续执行插入操作。继续执行插入操作。（2）如果二叉排序树不平衡，则找出最小不平衡子树）如果二叉排序树不平衡，则找出最小不平衡子树的根结点，根据新插入结点与最小不平衡子树根结点的根结点，根据新插入结点与最小不平衡子树根结点之间的关系判断调整类型。之间的关系判断调整类型。（3）根据调整类型进行相应的调整，使之成为新的平）根据调整类型进行相应的调整，使之成为新的平衡子树。衡子树。7.3 树表的查找技术树表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡

41、二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：设序列例：设序列20，35，40，15，30，25 ，构造平衡树。，构造平衡树。2035407.3 树表的查找技术树表的查找技术352040153025数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：设序列例：设序列20，35，40，15，30，25 ，构造平衡树。，构造平衡树。7.3 树表的查找技术树表的查找技术352040153025202515354030354030202515数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社设结点设结点A为为最小不平衡子树最小

42、不平衡子树的根结点，对该子树进行的根结点，对该子树进行平衡调整归纳起来有以下四种情况：平衡调整归纳起来有以下四种情况： 1. LL型型 2. RR型型 3. LR型型 4. RL型型7.3 树表的查找技术树表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社插入前插入前 插入后，调整前插入后，调整前 调整后调整后7.3 树表的查找技术树表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡二叉树LLLL型型型型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX旋转：扁担原理；冲突：旋转优先旋转：扁

43、担原理；冲突：旋转优先数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社612例例: :LL型型 7.3 树表的查找技术树表的查找技术108791291012876数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社平衡二叉树平衡二叉树平衡二叉树平衡二叉树RRRR型型型型7.3 树表的查找技术树表的查找技术插入前插入前 插入后，调整前插入后，调整前 调整后调整后A-1BLhBRh0ALhBXA-2BLhBRh0ALhBBALhBLh0BRh+1AX0数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社插入后，调整前插入后，调整前 先顺时针

44、旋转先顺时针旋转 再逆时针旋转再逆时针旋转7.3 树表的查找技术树表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡二叉树LRLR型型型型A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社插入后，调整前插入后，调整前 先顺时针旋转先顺时针旋转 再逆时针旋转再逆时针旋转7.3 树表的查找技术树表的查找技术平衡二叉树平衡二叉树平衡二叉树平衡二叉树RLRL型型型型XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBR

45、hCBCRh-1AALhCLh-1X001数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社课堂练习：设有关键码序列课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树，构造平衡树5427.3 树表的查找技术树表的查找技术LL型型42586数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社864256842585642课堂练习：设有关键码序列课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树，构造平衡树7.3 树表的查找技术树表的查找技术RL型型旋转旋转1次次RL型型旋转旋转2次次数据结构（数据结构（C+版）第版）第2版

46、版清华大学出版社清华大学出版社856429RR型型8465297.3 树表的查找技术树表的查找技术课堂练习：设有关键码序列课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树，构造平衡树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社7.3 散列表的查找技术散列表的查找技术顺序查找、折半查找、二叉排序树查找等。顺序查找、折半查找、二叉排序树查找等。这些查找技术都是通过一系列的给定值与关键码的这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。关键码的比较次数。

47、查找操作要完成什么任务？查找操作要完成什么任务？待查值待查值k确定确定k在存储结构中的位置在存储结构中的位置我们学过哪些查找技术？这些查找技术的共性？我们学过哪些查找技术？这些查找技术的共性？在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系能否不用比较，通过关键码直接确定存储位置？能否不用比较，通过关键码直接确定存储位置？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社概概概概 述述述述散列的基本思想：散列的基本思想：散列的基本思想：散列的基本思想：在记录的存储地址和它的关键码之在记录的存储地址和它的关键码之在记录的存储地址和它的关

48、键码之在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一间建立一个确定的对应关系。这样，不经过比较，一间建立一个确定的对应关系。这样，不经过比较，一间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。次读取就能得到所查元素的查找方法。次读取就能得到所查元素的查找方法。次读取就能得到所查元素的查找方法。7.3 散列表的查找技术散列表的查找技术关关键键码码集集合合ki riH( (ki) )H数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列表：散列表：散列表：散列表：采用散列技术将记录存储在一块采用散列技术将记录存储在

49、一块采用散列技术将记录存储在一块采用散列技术将记录存储在一块连续连续连续连续的存储的存储的存储的存储空间中，空间中，空间中，空间中，这块连续的存储空间这块连续的存储空间这块连续的存储空间这块连续的存储空间称为散列表。称为散列表。称为散列表。称为散列表。概概概概 述述述述7.3 散列表的查找技术散列表的查找技术关关键键码码集集合合ki riH( (ki) )H散列表散列表数组数组数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列函数：散列函数：散列函数：散列函数：将关键码映射为散列表中适当存将关键码映射为散列表中适当存将关键码映射为散列表中适当存将关键码映射为散列表中适当

50、存储位置的储位置的储位置的储位置的函数。函数。函数。函数。概概概概 述述述述7.3 散列表的查找技术散列表的查找技术散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数数组数组数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列地址：散列地址：散列地址：散列地址：由散列函数由散列函数由散列函数由散列函数所得的存储地址所得的存储地址所得的存储地址所得的存储地址 。概概概概 述述述述7.3 散列表的查找技术散列表的查找技术散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数散列地址散列地址下标下标数组数组数据结构（数据结构（

51、C+版）第版）第2版版清华大学出版社清华大学出版社概概概概 述述述述7.3 散列表的查找技术散列表的查找技术散列技术仅仅是一种查找技术吗？散列技术仅仅是一种查找技术吗？散列既是一种查找技术，也是一种存储技术。散列既是一种查找技术，也是一种存储技术。散列只是通过记录的关键码定位该记录，没有完散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要整地表达记录之间的逻辑关系，所以，散列主要是是面向查找面向查找的存储结构。的存储结构。散列是一种散列是一种完整的存储结构完整的存储结构吗？吗？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列技术一般不

52、适用于允许多个记录有同样关键码散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找，换言之，的情况。散列方法也不适用于范围查找，换言之，在散列表中，我们不可能找到最大或最小关键码的在散列表中，我们不可能找到最大或最小关键码的记录，也不可能找到在某一范围内的记录。记录，也不可能找到在某一范围内的记录。概概概概 述述述述7.3 散列表的查找技术散列表的查找技术散列技术适合于哪种类型的查找？散列技术适合于哪种类型的查找？散列技术最适合回答的问题是：如果有的话，散列技术最适合回答的问题是：如果有的话，哪个记录的关键码等于待查值。哪个记录的关键码等于待查值。数据结构（数据结构（

53、C+版）第版）第2版版清华大学出版社清华大学出版社散列技术的关键问题：散列技术的关键问题：散列技术的关键问题：散列技术的关键问题： 散列函数的设计。如何设计一个简单、均匀、存储散列函数的设计。如何设计一个简单、均匀、存储散列函数的设计。如何设计一个简单、均匀、存储散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。利用率高的散列函数。利用率高的散列函数。利用率高的散列函数。 冲突的处理。如何采取合适的处理冲突方法来解决冲突的处理。如何采取合适的处理冲突方法来解决冲突的处理。如何采取合适的处理冲突方法来解决冲突的处理。如何采取合适的处理冲突方法来解决冲突。冲突。冲突。冲突。7.3 散

54、列表的查找技术散列表的查找技术概概概概 述述述述数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社冲突：冲突：冲突：冲突：对于两个不同关键码对于两个不同关键码对于两个不同关键码对于两个不同关键码k ki i k kj j，有有有有HH( ( ( (k ki i) ) ) )HH( ( ( (k kj j) ) ) )，即两个不同的记录即两个不同的记录即两个不同的记录即两个不同的记录需要存放在同一个存储位置需要存放在同一个存储位置需要存放在同一个存储位置需要存放在同一个存储位置, , , ,k ki i和和和和k kj j相对于相对于相对于相对于HH称做称做称做称做同义词同义

55、词同义词同义词。 7.3 散列表的查找技术散列表的查找技术概概概概 述述述述关关键键码码集集合合ki riH(ki)kjH(kj)数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列函数散列函数散列函数散列函数7.3 散列表的查找技术散列表的查找技术设计散列函数一般应遵循以下原则：设计散列函数一般应遵循以下原则：设计散列函数一般应遵循以下原则：设计散列函数一般应遵循以下原则： 计算计算计算计算简单简单简单简单。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否则会降低查找效率。则会降低查找

56、效率。则会降低查找效率。则会降低查找效率。 函数值即散列地址分布函数值即散列地址分布函数值即散列地址分布函数值即散列地址分布均匀均匀均匀均匀。函数值要尽量均匀。函数值要尽量均匀。函数值要尽量均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利散布在地址空间，这样才能保证存储空间的有效利散布在地址空间，这样才能保证存储空间的有效利散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。用并减少冲突。用并减少冲突。用并减少冲突。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列函数散列函数散列函数散列函数直接定址法直接定址法直接定址法直接定址法散列函数是关键

57、码的线性函数散列函数是关键码的线性函数，即：即：H(key) = a key + b （a，b为常数）为常数）例：关键码集合为例：关键码集合为10, 30, 50, 70, 80, 90，选取的散，选取的散列函数为列函数为H( (key) )=key/10，则散列表则散列表为：为： 0 1 2 3 4 5 6 7 8 9103050708090适用情况？适用情况？事先知道关键码，关键码集合不是很大且连续性较好。事先知道关键码，关键码集合不是很大且连续性较好。 7.3 散列表的查找技术散列表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列函数为：散列函数为：H

58、( (key) )=key mod p 7.3 散列表的查找技术散列表的查找技术散列函数散列函数散列函数散列函数除留余数法除留余数法除留余数法除留余数法1470147014散列地址散列地址56494235282114 关键码关键码如何选取合适的如何选取合适的 p，产生较少同义词？，产生较少同义词？例：例： p 2137数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社7.3 散列表的查找技术散列表的查找技术散列函数散列函数散列函数散列函数除留余数法除留余数法除留余数法除留余数法一般情况下，选一般情况下，选一般情况下，选一般情况下，选p p为小于或等于表长（最好接近表长为小于

59、或等于表长（最好接近表长为小于或等于表长（最好接近表长为小于或等于表长（最好接近表长）的最小素数或不包含小于的最小素数或不包含小于的最小素数或不包含小于的最小素数或不包含小于2020质因子的合数。质因子的合数。质因子的合数。质因子的合数。 除留余数法是一种最简单、也是最常用的构造散列除留余数法是一种最简单、也是最常用的构造散列除留余数法是一种最简单、也是最常用的构造散列除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。函数的方法，并且不要求事先知道关键码的分布。函数的方法，并且不要求事先知道关键码的分布。函数的方法，并且不要求事先知道关键码的分布。 适用情

60、况？适用情况？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社根据关键码在各个位上的分布情况，选取分布比较根据关键码在各个位上的分布情况，选取分布比较均匀均匀的若干位组的若干位组成散列地址。成散列地址。 例：关键码为例：关键码为8位十进制数，散列地址为位十进制数，散列地址为2位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 7.3 散列表的查找技术散列表的查找技术散列函数散列函数散列函数散列函数数字分析法数字分析法数字分

61、析法数字分析法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社适用情况适用情况:能预先估计出全部关键码的每一位上各种数字出现能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。的频度，不同的关键码集合需要重新分析。7.3 散列表的查找技术散列表的查找技术散列函数散列函数散列函数散列函数数字分析法数字分析法数字分析法数字分析法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社对关键码平方后，按散列表大小，取中间的若干位作对关键码平方后，按散列表大小，取中间的若干位作为散列地址（为散列地址（平方平方后后截取截取）。）。 7.3

62、 散列表的查找技术散列表的查找技术散列函数散列函数散列函数散列函数平方取中法平方取中法平方取中法平方取中法事先不知道关键码的分布且关键码的位数不是很大。事先不知道关键码的分布且关键码的位数不是很大。适用情况适用情况:例：散列地址为例：散列地址为2位，则关键码位，则关键码123的散列地址为：的散列地址为：(1234)21522756数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社将关键码从左到右分割成位数相等的几部分，将这几将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。部分叠加求和，取后几位作为散列地址。 7.3 散列表的查找技术散列表的

63、查找技术散列函数散列函数散列函数散列函数折叠法折叠法折叠法折叠法例：设关键码为例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。，散列地址为三位。 2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位叠加移位叠加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间界叠加间界叠加适用情况适用情况:关键码位数很多，事先关键码位数很多，事先不知道关键码的分布。不知道关键码的分布。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法开放定址法开放定址法开放定址法开放定址法

64、由关键码得到的散列地址一旦产生了冲突，就去寻找由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空下一个空的散列地址，并将记录存入。的散列地址，并将记录存入。 如何寻找下一个空的散列地址如何寻找下一个空的散列地址?7.3 散列表的查找技术散列表的查找技术（1）线性探测法）线性探测法（2）二次探测法）二次探测法（3）随机探测法）随机探测法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社线性探测法线性探测法当发生冲突时，从冲突位置的下一个位置起，依次当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地寻找空的散列地址。址。 对对于于键键值值key，设设H( (key)

65、 )=d，闭闭散散列列表表的的长长度度为为m，则发生冲突时，寻找下一个散列地址的公式为：则发生冲突时，寻找下一个散列地址的公式为： Hi=( (H( (key) )di) ) % m （di=1，2，m- -1） 7.3 散列表的查找技术散列表的查找技术用开放定址法处理冲突得到的散列表叫用开放定址法处理冲突得到的散列表叫闭散列表闭散列表。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例例：关关键键码码集集合合为为 47, 7, 29, 11, 16, 92, 22, 8, 3，散散列列表表表表长长为为11，散散列列函函数数为为H( (key) )=key mod 11

66、，用用线线性探测法处理冲突，则散列表为：性探测法处理冲突，则散列表为：47729111692292222883333堆积：堆积：在处理冲突的过程中出现的在处理冲突的过程中出现的非同义词非同义词之间对之间对同一个散列地址争夺的现象同一个散列地址争夺的现象。7.3 散列表的查找技术散列表的查找技术线性探测法线性探测法 0 1 2 3 4 5 6 7 8 9 10数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社在线性探测法构造的散列表中查找算法在线性探测法构造的散列表中查找算法伪代码伪代码 1. 计算散列地址计算散列地址j; 2. 若若htj等于等于k，则查找成功，返回记录在散

67、列表中的下标；，则查找成功，返回记录在散列表中的下标； 否则执行第否则执行第3步；步； 3. 若若htj为空或整个散列表探测一遍，则查找失败，转为空或整个散列表探测一遍，则查找失败，转4； 否则，否则，j指向下一单元，转指向下一单元，转2； 4. 若整个散列表探测一遍，则表满，抛出溢出异常；若整个散列表探测一遍，则表满，抛出溢出异常； 否则，将待查值插入；否则，将待查值插入；7.3 散列表的查找技术散列表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社int HashSearch1(int ht , int m, int k) j = H(k); /计算散列地址

68、计算散列地址 if (htj = k) return j; /没有发生冲突，比较一次查找成功没有发生冲突，比较一次查找成功 else if (htj = Empty) htj = k; return 0; /查找不成功，插入查找不成功，插入 i = (j + 1) % m; /设置探测的起始下标设置探测的起始下标 while (hti != Empty & i != j) if (hti = k) return i; /发生冲突，比较若干次查找成功发生冲突，比较若干次查找成功 else i = (i + 1) % m; /向后探测一个位置向后探测一个位置 if (i = j) throw 溢出

69、溢出; else hti = k; return 0; /查找不成功，插入查找不成功，插入7.3 散列表的查找技术散列表的查找技术在线性探测法构造的散列表中查找算法在线性探测法构造的散列表中查找算法C+描述描述数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二次探测法二次探测法当发生冲突时，寻找下一个散列地址的公式为：当发生冲突时，寻找下一个散列地址的公式为： Hi=( (H( (key) )di) )% m（di=12，12，22，22，q2，q2且且qm/2） 7.3 散列表的查找技术散列表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版

70、社4772911169229222288333例例：关关键键码码集集合合为为 47, 7, 29, 11, 16, 92, 22, 8, 3，散散列列表表表表长长为为11，散散列列函函数数为为H( (key) )=key mod 11，用二次探测法处理冲突，则散列表为：用二次探测法处理冲突，则散列表为：二次探测法二次探测法7.3 散列表的查找技术散列表的查找技术 0 1 2 3 4 5 6 7 8 9 10数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社随机探测法随机探测法当发生冲突时，下一个散列地址的位移量是一个随当发生冲突时，下一个散列地址的位移量是一个随机数列，即机

71、数列，即寻找下一个散列地址的公式寻找下一个散列地址的公式为：为： Hi=( (H( (key) )+di) )% m （di是一个随机数列，是一个随机数列，i=1，2，m- -1）7.3 散列表的查找技术散列表的查找技术计算机中产生随机数的方法通常采用线性同余法，计算机中产生随机数的方法通常采用线性同余法，其其中中，d称称为为随随机机种种子子。当当b、c和和m的的值值确确定定后后，给定一个随机种子，产生确定的随机数序列。给定一个随机种子，产生确定的随机数序列。0= =da= =+ += =- -1, 2,LLmod)(1nmcbaann数据结构（数据结构（C+版）第版）第2版版清华大学出版社清

72、华大学出版社p 基本思想基本思想：将所有散列地址相同的记录，即所有同：将所有散列地址相同的记录，即所有同义词记录存储在一个单链表中（称为同义词子表），义词记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子在散列表中存储的是所有同义词子表的头指针。表的头指针。 p 用拉链法处理冲突构造的散列表叫做用拉链法处理冲突构造的散列表叫做开散列表开散列表。p 开散列表不会出现堆积现象。开散列表不会出现堆积现象。 p 设设n个记录存储在长度为个记录存储在长度为m的散列表中，则同义词的散列表中，则同义词子表的平均长度为子表的平均长度为n / m。7.3 散列表的查找技术散列表的查找技术处

73、理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法拉链法（链地址法）拉链法（链地址法）拉链法（链地址法）拉链法（链地址法）数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：关键码集合例：关键码集合 47, 7, 29, 11, 16, 92, 22, 8, 3，散列，散列函数为函数为H( (key) )=key mod 11，用拉链法处理冲突，构造用拉链法处理冲突，构造的开散列表为：的开散列表为： 7.3 散列表的查找技术散列表的查找技术 0 1 2 3 4 5 6 7 8 910 11 22 47 3 92 16 7 29 8 数据结构（数据结构（C+版）第版）第

74、2版版清华大学出版社清华大学出版社在拉链法构造的散列表查找算法在拉链法构造的散列表查找算法伪代码伪代码1. 计算散列地址计算散列地址j； 2. 在第在第j个同义词子表中顺序查找；个同义词子表中顺序查找； 3. 若查找成功，则返回结点的地址；若查找成功，则返回结点的地址； 否则，将待查记录插在第否则，将待查记录插在第j个同义词子表的表头。个同义词子表的表头。7.3 散列表的查找技术散列表的查找技术数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Node *HashSearch2( (Node *ht , int m, int k) ) j = H( (k) ); p = h

75、tj; while ( (p != NULL & p-data != k) ) p = p-next; if ( (p-data = k) ) return p; else q = new Node; q-data = k; q-next = htj; htj = q; 7.3 散列表的查找技术散列表的查找技术在拉链法构造的散列表查找算法在拉链法构造的散列表查找算法C+描述描述数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社散列查找的性能分析散列查找的性能分析散列查找的性能分析散列查找的性能分析 p 由于冲突的存在，产生冲突后的查找仍然是给定由于冲突的存在，产生冲突后的查

76、找仍然是给定值与关键码进行比较的过程。值与关键码进行比较的过程。p 在查找过程中，关键码的比较次数取决于产生冲在查找过程中，关键码的比较次数取决于产生冲突的概率。突的概率。影响冲突产生的因素有：影响冲突产生的因素有： （1 1）散列函数是否均匀）散列函数是否均匀 （2 2）处理冲突的方法）处理冲突的方法 （3 3）散列表的装载因子）散列表的装载因子 7.3 散列表的查找技术散列表的查找技术表中填入的记录数表中填入的记录数散列表的长度散列表的长度=数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社几种处理冲突方法的平均查找长度几种处理冲突方法的平均查找长度7.3 散列表的查找

77、技术散列表的查找技术 散列表的平均查找长度是散列表的平均查找长度是装填因子装填因子的函数的函数，而不是查找集合，而不是查找集合中记录个数中记录个数n的函数。在很多情况下，散列表的空间都比查找集的函数。在很多情况下，散列表的空间都比查找集合大，此时虽然浪费了一定的空间，但换来的是查找效率。合大，此时虽然浪费了一定的空间，但换来的是查找效率。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社开散列表与闭散列表的比较开散列表与闭散列表的比较开散列表与闭散列表的比较开散列表与闭散列表的比较7.3 散列表的查找技术散列表的查找技术不产生不产生产生产生有有没有没有堆积现象堆积现象结构

78、开销结构开销插入插入/删除删除 查找效率查找效率开开散散列列表表闭闭散散列列表表效率高效率高效率低效率低效率高效率高效率低效率低估计容量估计容量不需要不需要需要需要数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社本章总结本章总结查找技术查找技术静态查找静态查找动态查找动态查找线性线性表的表的查找查找技术技术树表树表的的查找查找技术技术散列散列表的表的查找查找技术技术顺序查找顺序查找折半查找折半查找二叉排序树二叉排序树平衡二叉树平衡二叉树散列函数散列函数处理冲突处理冲突开放定址法开放定址法 线性探测法线性探测法 二次探测法二次探测法 随机探测法随机探测法拉链法拉链法直接定址法直接定址法除留余数法除留余数法数字分析法数字分析法平方取中法平方取中法折叠法折叠法