数据结构及应用算法教程（修订版） 数据结构_第8章_查找表.ppt

《数据结构及应用算法教程（修订版） 数据结构_第8章_查找表.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 数据结构_第8章_查找表.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章 查找表 8.1 静态查找表 8.1.1 顺序查找 8.1.2 折半查找 8.1.3 分块查找 8.2 动态查找树表 8.2.1 二叉查找树 8.2.2 键树 8.3 哈希表及其查找 8.3.1 什么是哈希表？ 8.3.2 构造哈希函数的几种方法 8.3.3 处理冲突的方法和建表示例 8.3.4 哈希表的查找及其性能分析 8.3.5 哈希表的的应用举例,何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特

2、定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,查找表可分为两类: 静态查找表(static search table)：仅作查询和检索操作的查找表。 动态查找表(dynamic search table)：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或从查找表中删除其“查询”结果为“在查找表中”的数据元素。 关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。,查找：根据

3、给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功” ， 查找结果给出“空记录”或“空指针”。 如何进行查找？查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系,换句话说,用另外一种结构来表示查找表。,8.1 静态查找表 静态查找表的基本操作： Create( /数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int len

4、gth; /表的长度 SSTable; 数据元素类型的定义为: typedef struct KeyType key; /关键字域 /其它属性域 ElemType;,8.1.1 顺序查找 以顺序表或线性链表表示的静态查找表 查找过程： (1)从第一个元素的关键字起，依次向后和给定值相比较直至相等或不存在。 (2)从最后一个元素的关键字起，依次向前和给定值相比较直至相等或不存在。,ST.elem,回顾顺序表的查找过程：,假设给定值 e=64, 要求 ST.elemk = e, 问: k = ?,7,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,int S

5、earch_Seq(SSTable ST, KeyType kval) / 在顺序表ST中顺序查找其关键字等于kval的数 /据元素。若找到，则函数值为该元素在表中的 /位置，否则为0。 ST.elem0.key = kval; / “哨兵” for (i=ST.length; ST.elemi.key!=kval; -i ) ; / 从后往前找 return i; / 找不到时，i为0 / Search_Seq,算法8.1：,顺序查找的时间性能: 即查找算法的平均查找长度(Average Search Length) 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值: AS

6、L=(n+1)/2 其中:n 为表长,8.1.2 折半查找 当以顺序有序表表示静态查找表时，查找过程可按“折半”进行。 折半查找(又称二分查找)：查找过程是，先确定待查记录所在范围，然后拿给定值与范围的中间位置记录的关键字比较，若相等，表示成功；否则缩小范围。重复操作，直至找到该记录，或者当查找区间缩小到 0也没有找到关键字等于给定值的记录为止。,ST.elem,ST.length,例如: key=64 的查找过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2,int Searc

7、h_Bin(SSTable ST, KeyType kval) low=1; high=ST.length; while (low=high) mid=(low+high)/2; if (kval=ST.elemmid.key) return mid; else if (kvalST.elemmid.key) high=mid-1; else low=mid+1; /while return 0 /Search_Bin,算法8.2：,6,3,9,1,4,2,5,7,8,10,11,分析折半查找的平均查找长度 先看一个具体的情况，假设：n=11 ASL=(1+2*2+3*4+4*4)/11=33

8、/11=3,1,2,2,3,3,3,3,4,4,4,4,可以用一棵二叉树来描述折半查找过程，称此树为判定树。 二叉树中结点的值表示有序表中记录的序号 左右子树结点数相等或最多相差一个(左少右多) 判定树上每个结点需要查找的次数刚好为该结点所在的层数 查找成功时查找次数不会超过判定树的深度 一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。 平均查找长度为：,8.1.3 分块查找 分块查找也称索引顺序查找，其性能介于顺序查找和折半查找之间，适合于关键字分块有序的查找表。 分块有序：查找表中的记录可按其关键字的大小分成若干块,且前一块中的最大关键字小于后一块中的最小

9、关键字,而各块内部的关键字不一定有序。 索引查找思想:为每一块建立一个索引项，包括两个域:一个是该块中最大的关键字的值；一个是该块的起始位置， 由于查找表分块有序，则索引表为有序表。 查找过程：分两步进行：首先要在索引表中查找以确定元素所在的块（采用简单顺序查找或折半查找）；然后在所确定的块中进行查找（顺序查找）。,例 8.3,ST.elem,索引表,块内最大关键字 块的起始序号,typedef struct KeyTypekey; int stadr; indexItem; typedef struct indexItem*elem; intlength; indexTable;,int S

10、earch_Idx ( SSTable ST, indexTable ID, KeyType kval ) /在顺序表ST中分块查找其关键字等于给定值kval的数据元素， /ID为索引表。若找到,则返回该数据元素在ST中的位置，否则 /返回0 -算法8.3 low = 0; high = ID.length-1; found = FALSE; if (kvalID.elemhigh.key) return 0; / 给定值kval大于查找表中所有关键字 while ( low ID.elemmid.key ) low = mid +1; else found = TRUE; low = mid

11、; /while,s = ID.elemlow.stadr; / 经索引表查找后，下一步的查找范围定位在第low块 if ( low ID.length-1 ) t = ID.elemlow +1.stadr-1; else t = ST.length; / s和t为在ST表进行查找的下界和上界，若不是最后一块，则 /上界为“下一块的起始位置之前” if ( ST.elemt.key= kval ) return t; else / 在ST.elems 至ST.elemt-1的区间内进行顺序查找 ST.elem0 = ST.elemt; / 暂存ST.elemt ST.elemt.key =

12、kval; / 设置监视哨 for ( k=s; ST.elemk.key !=kval; k+ ) ; ST.elemt = ST.elem0; / 恢复暂存值 if ( k != t ) return k; else return 0; / else / Search_Idx,分块查找性能分析： 设顺序表长度为n，被均匀的分成b块，即索引表的长度为b，则： ASLidx=ASL(b)+ASL(n/b)log2(b+1)-1+(n/b+1)/2 索引查找典型应用：查字典,8.2 动态查找表 在程序运行过程中动态生成的查找表。对动态查找表常进行的操作为插入和删除，表示动态查找的方法：查找树和哈

13、希表。 基本操作： InitDSTable（ struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,2二叉排序树的查找算法： 若二叉排序树为空，则查找不成功,否则， 1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。 查找树: 具有“通过和根结点关键字的比较可将继续查找的范围缩小到某一棵子树中”特性的二叉树或树。二叉排序树又称二叉查找树（binary search tree）,50,30,80,20,90,85,40

14、,35,88,32,例如:二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,查找的递归算法： BiTree SearchBST(BiTree T , KeyType key) /在根指针T所指二叉排序树中递归地查找某关键字等于key /的数据元素,若查找成功,则返回指向该数据元素的指针，否 /则返回空指针。 if(!T | key= =T-data.key) return T; /查找结束 else if(keydata.key) return ( SearchBST( T-lchild , key) ); /在左子树中继续

15、查找 else return ( SearchBST( T-rchild , key) ); /在有子树中继续查找 /SearchBST,查找算法8.4： bool Search_BST (BiTree T, KeyType kval, BiTree / 查找不成功 / SearchBST,假设 kval = 48,kval=24,return TRUE,return FALSE,3二叉排序树的插入算法 根据动态查找表的定义,“插入”操作在查找不成功时才进行； 若二叉排序树为空树,则新插入的结点为新的根结点；否则, 新插入的结点必是一个新的叶子结点，并且是查找路径上访问的最后一个结点的左孩子或

16、右孩子。 举例：从空树出发,插入下列关键字,构造一棵二叉排序树(40，88，55，96，18，09，20，13，19),插入算法8.5: bool Insert_BST(BiTree /else / Insert_BST,T=NULL,kval=50,30,40,80,20,36,90,40,38,4.二叉排序树的删除算法 和插入相反，删除在查找成功之后进行。对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个元素，只要在删除某个结点之后，仍然保持二叉排序树的特性即可。 可分三种情况讨论： 被删除的结点是叶子结点,直接删除； 被删除的结点只有左子树或者只有右子树,则将其孩子直接挂到其双亲

17、上； 被删除的结点既有左子树，也有右子树,找左孩子中最大的一个元素，代替被删除结点，最大元素最多只有一个左子树，按处理删除最大元素。,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,

18、40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,二叉查找树删除算法8.6 void Delete_BST (BiTree / if,else if (!p-rchild) / 右子树空则只需挂接它的左子树 q = p; p = p-lchild; /if else / 左子树空，只需挂接它的右子树 q = p; p = p-rchild; / 将指针p所指子树挂接到被删结点的双亲(指针f所指的)结点上 if (!f) T = p; / 被删结点为根结点 else if (q = f-lchild) f-lchild = p; else f-rchil

19、d = p; / 完成子树的挂接 delete q; / 释放被删结点空间 /else /if /Delete_BST,二叉排序树的查找分析 在二叉查找树上查找关键字等于给定值的过程，与给定值比较的关键字的个数和结点所在的层次相等，最多不会超过二叉查找树的深度。可以证明，二叉查找树的平均查找长度： P（n）2（n1）/n *logn+C 同样的n个关键字,若先后插入的顺序不同, 构造出的二叉排序树的形态不同。如关键字序列（1，2，3，4，5)，若输入序列为：1,2,3,4,5，则 ASL=3，而输入序列为：3,1,4,2,5,则ASL=2.2。,最好的二叉排序树形态是n个关键字的折半查找对应的

20、判定树O(log2n)。 最坏的二叉排序树形态是链表形态O(n)。 二叉排序树的平均查找长度和折半查找是同一数量级log2n,但不如折半查找好。 5.平衡二叉树（Balanced Binary Tree） (1)定义：或是空树，或是具有如下性质的二叉树，它的左右子树也都是平衡二叉树,且左子树和右子树的深度之差的绝对值不大于1。,(2)平衡二叉树的深度：log2n (n为结点个数) (3)结点的平衡因子（Balance Factor）:是左子树深度减去右子树深度，它只可能是：-1、0、1。,例如:,平衡树,小结： 查找表:静态查找表、动态查找表、关键字、查找 静态查找表 顺序查找：ASLs=(n

21、+1)/2、ASLus=n+1 折半查找：判定树、ASLs=(n+1)/n*log2(n+1)-1log2(n+1)-1 分块查找：索引表、ASLs=ASL(b)+ASL(n/b) 动态查找表：二叉查找树、查找、插入、删除算法 P(n)=2(n+1)/n*log2n+C 平衡二叉树：|hL-hR|1,(4)如何构造平衡二叉树（平衡旋转技术） 在平衡的二叉排序树中插入一个结点，当出现不平衡时，根据不平衡情况分四种调整方法 假设最低不平衡结点为A，根据新插入结点与A的位置关系来命名调整方法： LL型：新插入结点在A的左孩子(L)的左子树(L)中； LR型：新插入结点在A的左孩子(L)的右子树(R)

22、中； RL型：新插入结点在A的右孩子(R)的左子树(L)中； RR型：新插入结点在A的右孩子(R)的右子树(R)中。 AVL树：根据Adelson-Velskii和Landis提出的动态平衡方法构造的平衡二叉排序树。,LL型(图示),C,LL型,A,BL,BR,AR,h+2,h,LL型,A,B,BL,BR,AR,LR型(图示),C,LR型,C,B,A,BL,CL,AR,h+2,h,LR型,A,C,CR,AR,C,CR,B,BR,CL,RL型(图示),A,B,C,RL型,B,A,B,AL,CL,BR,h,h+2,RL型,B,C,CR,BR,C,CR,A,AR,CL,RR型(图示),A,B,C,R

23、R型,C,A,B,BL,BR,AR,h+2,h,RR型,A,B,BL,AR,BR,练习：依次输入下列数据构造一棵平衡二叉树：100，90，80，60，70，50，120，110，150，87。,100,90,80,LL型,90,80,100,60,70,LR型,90,70,100,60,80,50,LL型,90,70,100,60,80,50,120,110,90,70,100,60,80,50,120,110,RL型,90,70,110,60,80,50,100,120,150,RR型,70,60,50,110,90,80,100,120,150,练习：依次输入下列数据构造一棵平衡二叉树：1

24、00，90，80，60，70，50，120，110，150，87。,70,60,50,110,90,80,100,120,150,87,RL型,70,60,50,110,90,80,100,120,150,87,练习：依次输入下列数据构造一棵平衡二叉树：100，90，80，60，70，50，120，110，150，87。,补充习题: 1.对线性表进行二分查找时，要求线性表必须( )。 A)以顺序方式存储 B)以顺序方式存储且元素有序 C)以链式方式存储 D)以链式方式存储且元素有序 2.关于判定树，下列说法不正确的是( )。 A)判定树是对有序序列进行二分查找得到的树 B)n个结点的判定树的深

25、度为 log2n +1 C)判定树的叶子结点都在同一层 D)判定树除去最后一层结点以后是满二叉树或空二叉树 3.从原理上讲，折半查找法要求查找表中各元素的键值必须是 ( )。 A)递增或递减 B)递增 C)递减 D)无序,1.B 2.C 3.A,补充习题: 4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ）。 A)该中间位置 B)该中间位置1 C)该中间位置1 D)该中间位置/2 5.在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做（）次关键码比较。 A)2 B)3 C)4 D

26、)5 6.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树。 A)正确 B)不正确,4.B 5.C 6.B,补充习题: 7.静态查找表与动态查找表的根本区别在于( ). A)它们的逻辑结构不一样 B)施加在其上的操作不一样 C)所包含的数据元素的类型不一样 D)存储实现不一样 8.按12,24,36,90,52,30的顺序构成的平衡二叉树,其根结点是( ). A)24 B)36 C)52 D)30 9.一棵完全二叉树一定是一棵( ). A)堆 B)哈夫曼树 C)二叉排序树 D)平衡二叉树,7.B 8.B 9.D,8.2.2 键树 键树、数字查找树（Digital search

27、 trees） 结点不是关键字，而是关键字中的一个字符,从根到叶子结点的路径（根、叶子本身除外）才是关键字 例8.5 统计正文中某些单词出现的次数 算法8.7 void setmatch(DLTree root,char line) 算法8.8 bool Search_DLTree(DLTree rt, int j, int int num; KeysType; typedef enumLEAF, BRANCH NodeKind; typedef struct char symbol; struct DLTNode*next; NodeKind kind; Union struct DLTNo

28、de *first; intidx; DLTNode,*DLTree;,8.3 哈希表及其查找 以上两节所讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系；查找的过程为给定值依次和关键字集合中各个关键字进行比较；查找的效率取决于和给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,对于频繁使用的查找表,希望其平均查找长度ASL=0 只有一个办法: 预先知道所查关键字在表中的位置。即要求：记录在表中位置和其关键字之间存在一种确定的关系( 要求关键字与数据元素存储

29、位置之间存在一一对应关系)。,实例：某班的成绩表如下表,为了能一次查找成功,在存储表的过程中，建立key与存储地址之间的一一对应关系，如欲查找学号为95051130的信息，不需比较便可直接访问存储数组V30。,8.3.1 什么是哈希表 哈希函数:在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key) 作为关键字为 key 的记录在表中的位置（称为哈希地址），通常称这个函数 H(key)为哈希函数。 哈希表:一组关键字通过哈希函数得到一段有限的连续地址,这段地址是所有关键字的一个映像,称为哈希表(又称为散列表或杂凑表）,构建哈希表又称散列技术。 冲突:不同的关键字通过同一哈希函数得

30、到相同的哈希地址，称为产生冲突。(同义词:具有相同散列地址的关键字) 即：key1key2，但 H(key1)=H(key2)。,哈希查找（散列查找）的基本思想： 以数据元素的关键字为自变量，通过一确定的函数关系,计算出对应的函数值f(key),把这个值解释为元素的存储地址，并按此存放；查找时由同一函数对给定的Key值计算地址，将Key与地址单元中的关键字进行比较，确定查找是否成功。因此散列法（哈希法）又称为关键字地址转换法。 按此思想构建的表称为散列（哈希）表。,关键字集合,存储地址集合,Hash,例8.6：有数据元素序列(14，23，39，9，25，11),若规定每个元素k的存储地址H（k

31、ey）key，请画出存储结构图。 （注：H（key）key 称为散列函数） 解：根据散列函数H(key)key,可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，则对应散列存储表（哈希表）如下：,例8.7：设有一组记录的关键字为： S=ZHAO,QIAN,SUN,LI,CHEN,DIAO,MA,BAI,OU,NAN,TANG,JIN,XIAO,WU,GAO,YI 存储这组记录的一维数组为： ElemType hashtable26; 且关键字为key的记录存放在数组的第i个分量hashtablei中 i=f(key)=(关键字首字母）- A 则相应的哈希表为右表。,有6个

32、元素的关键码分别为：（14，23，39，9，25，11）。 选取关键码与元素位置间的函数为H(k)=k mod 7,通过哈希函数对6个元素建立哈希表：,25,39,23,9,14,冲突现象举例：,6个元素用7个 地址应该足够!,H(14)=14%7=0,11,H(25)=25%7=4 H(11)=11%7=4,有冲突,1）构造好的哈希函数 （a）所选函数尽可能简单，以便提高转换速度； （b）所选函数对关键码计算出的地址,应在哈希地址集中大致均匀分布，以减少空间浪费。,2）制定一个好的解决冲突的方案 查找时, 如果从哈希函数计算出的地址中查不到关键码,则应当依据解决冲突的规则，有规律地查询其它相

33、关单元。,在哈希查找方法中,冲突是不可能避免的，只能尽可能减少。所以，哈希方法必须解决以下两个问题：,哈希表的装填系数:设为哈希表分配空间大小为m，在表中填入的记录数为n，定义 n/m 为哈希表的装填系数。实际应用:为0.650.85。 8.3.2 构造哈希函数的方法 要求一：n个数据最好仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。 要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以减少冲突。 常用哈希函数构造方法有:直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法。,1.直接定址法 Hash(key)= key 或者 Hash(key)=

34、 a*key+b（a，b为任意正整数）,一般很少用。 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为100,300,500,700,800,900, 选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：,2.除留余数法 Hash(key)=key mod p (p=m是一个整数,m为哈希表长) 特点：以关键码除以p的余数作为哈希地址。 关键：如何选取合适的p？ 技巧：若设计的哈希表长为m，则一般取pm (4i+3)且为质数（也可以是不包含小于20质因子的合数）。 例如：若m=8、13、32 则p为

35、：7、13、31。 为什么要对p加限制？ 例如：给定一组关键字为：12, 39, 18, 24, 33, 21,若取p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3 可见，因p中含质因子3，则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。,3.平方取中法: 关键字平方(先扩大差别)后取中间几位为哈希地址,因为一个数的平方值的中间几位和这个数的每位数字都有关系，不易冲突。 例：若哈希表长为100,则取关键字平方值的中间位，325在平方后取105625中间两位，即56作为它的散列地址。,4.折叠法 将关键字分割成位数相同的几部分（最后一部分可以不同），然后

36、几部分相加舍进位作为哈希地址。 适用场合：关键字的数字位数特别多且每一位的值都随机出现，可得到冲突较少的哈希地址。 移位叠加：将分割后的每一部分的最低位对齐，然后相加。 间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加。,例如:身份证号码:340104198 805061532,先进行分组：340 104 198 805 061 532,5.随机数法 设定哈希函数为: Hash(key) = Random(key) 其中，Random为伪随机函数。通常此方法用于对长度不等的关键字构造哈希函数。 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，

37、总的原则是使产生冲突的可能性降到尽可能小。,8.3.3 处理冲突的方法 假设哈希表的地址集为0 -(n-1)，冲突是指由关键字得到的哈希地址为 j(0jn-1)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个空的哈希地址。 在处理冲突的过程中可能得到一个地址序列Hi(i=1, 2,，)且Hi0,n-1。即在处理哈希地址的冲突时,若得到的另一个哈希地址H1仍然冲突,则在求下一个地址H2,若H2仍然冲突，再求得H3。依次类推，直至Hk不发生冲突为止,则Hk为记录在表中的地址。,1.开放定址法 开放定址处理冲突的做法：当冲突发生时，形成一个探查序列,沿此序列逐个地址探查，直到找到一个

38、空位置(开放地址-未填入数据的空闲地址),将发生冲突的记录放入到该地址中。 Hi=(H(key)+di) MOD m，i=1,2,k(k=m-1) 其中：H(key)为哈希函数；m为哈希表表长；di为增量序列,有三种取法: 线性探测再散列 di=1，2，m-1 二次探测再散列 di=12, -12, 22, -22, ,+k2(km/2) 随机探测再散列 di是一组伪随机数列 闭散列表:用开放定址法处理冲突得到的散列表,例8.9:设一组关键字(07,15,20,31,48,53,64,76,82,99)试构建哈希表。 取m11，p=11, Hash（key）= key mod 11,48,53

39、,冲突，后移,31,53,64,64,82,15,20,07,31,64,53,48,82,64,76,76,99,99,99,76,99,线性探测再散列,聚集或堆积：线性探测法出现非同义词之间对同一散列地址争夺的现象。,76,53,31,82,15,20,07,31,64,48,76,99,二次探测再散列构造哈希表 Hi=(Hash（key）+di) mod 11 (di= 12, -12, 22, -22, ,+k2 i=1,2,k),(07,15,20,31,48,53,64,76, 82,99),48,53,64,64,64,76,82,99,53,di 的完备性: 产生的Hi应各不相

40、同,且产生的m-1个Hi 应覆盖哈希表的所有地址,要求: 平方探测时表长m必须为4j+3的质数 随机探测时m与di没有公因子,2.链地址法（拉链法） 将所有关键字为同义词（即具有相同的哈希函数值）的记录存贮在同一线性链表中，而哈希表中下标为i的分量存储哈希函数值为i的链表的头指 针。 开散列表:用链地址法处 理冲突构造的散列表。,(07,15,20,31,48,53,64,76, 82,99),链地址法构造的哈希表,与开放地址法相比，链地址法的优点： 不会出现二次聚集，平均查找长度较短； 各链表上的记录空间动态申请，比较适合造表前无法确定表长的情况； 开放地址法有时为了避免冲突，需增大表的长度

41、，造成空间浪费，而链地址法只增加了结点的指针域，可节省空间； 链地址法增加或删除一个结点时操作易于实现。,小结： 平衡二叉树:定义、平衡旋转技术 哈希表:哈希函数、哈希表、冲突、装填（系数）因子 构造哈希函数:原则、直接定址法、除留余数法、平方取中法、折叠法、随机数法 处理冲突的方法:开放定址法、链地址法,8.3.4 哈希函数的查找及其性能分析 1.哈希查找 在散列表中查找元素的过程和构造的过程基本一致： 对给定关键字k，由散列函数H计算出该元素的地址j=H(k)，若表中下标为j的分量为空，则查找失败。否则，比较关键字，若相等，查找成功,否则根据构造表时所采用的处理方法找下一个地址，直至找到关

42、键字等于k的元素（成功）或者找到空位置（失 败）为止。,地址为空？,给定k值,计算H(k),按处理冲突 方法计算Hj,N,N,Y,失败,Y,成功,key=k？,/- 开放定址法的存储结构 -/ int hashsize=997,. /哈希表容量递增表，为一个合适的素数序列 typedef struct ElemType*elem; /记录存储基址 intcount; /记录数 intsizeindex; /哈希表容量 HashTable; const SUCCESS1； const UNSUCCESS0； const DUPLICATE-1； / 哈希表建表时先初始化，每一位均置为：NULLK

43、EY,Status SearchHash (HashTable H, KeyType kval, int / 查找不成功(H.elemp.key = NULLKEY)，p 返回的是插入位置 / SearchHash,Status InsertHash(HashTable / 重建哈希表 / InsertHash,/- 链地址法存储结构 -/ typedef struct ElemType data; LHNode *next; LHNode,*LHNodeptr; typedef struct LHNodeptr *elem; intcount;/记录数 intsizeindex; /哈希表容

44、量 LHashTable;,Status SearchHash(LHashTable H,KeyType kval, LHNodeptr /SearchHash,Status InsertHash(HashTable /重建哈希表 /InsertHash,2.性能分析 线性探测散列、二次探测散列、链地址法构建哈希表比较 关键字序列:（07,15,20,31,48,53,64,76,82,99） n=10 m=11 p=11 0.91,* 表示m=13 p=13 0.77,比较次数,对表长为m的哈希表,若所选哈希函数是“好”的,且表中n个记录的查找概率相等，则哈希表的平均查找长度取决于装填系数和

45、处理冲突的方法。 查找成功时平均查找长度： ASLsl（）(1+1/(1-)/2 - 线性探测再散列 ASLsr（）-1/*ln(1-) - 二次探测再散列 ASLsc（）1+/2 - 链地址法 查找不成功时平均查找长度 ASLul（）(1+1/(1-)2)/2 ASLur（）1/(1-) ASLuc（）+e-,8.3.5 哈希表的应用举例 C语言中编译程序使用的符号表，操作有 对给定的名字查是否已在表中； 填入新的名字； 对给定的名字访问其有关信息； 对给定名字更新和填写其信息； 删除一些无用的名字。 例8.10 构建存放C语言32关键字的查找表且希望ASL40 考虑 m4j3 取m43 ，

46、p41 hash（key）（key的第一个字符序号）100（key的最后一个字符序号） mod 41 实际ASL=2.5,对静态查找表,若能找到不发生冲突的哈希函数，即此时哈希表的ASL=0,称此类哈希函数为理想(perfect)的哈希函数。 适合用于查找频繁的静态查找表。,补充习题: 10.AVL树的任何子树都是AVL树( )。 A)正确 B)不正确 11.在散列表中，所谓同义词就是具有相同散列地址的两个数据元素（ ）。 A）正确 B）不正确 12.对包含N个元素的散列表进行查找，平均查找长度（ ）。 A）为 O(log2N) B）为O(N) C）不直接依赖于N D）上述三者都不是,10.A

47、 11.A 12.D,补充习题: 13.哈希表的查找效率完全取决于所选取的哈希函数和处理冲突的方法（ ）。 A)正确 B)不正确 14.与其它查找方法相比,散列查找法的特点是( ). A)通过关键字的比较进行查找 B)通过关键字计算元素的存储地址进行查找 C)通过关键字计算元素的存储地址并进行一定的比较查找 D)以上都不是,13.B 14.C,补充习题: 15.假设有10个关键字，它们具有相同的散列地址，用线性探测法把这10个关键码存入散列中至少需要做（ ）次探测。 A)110 B)100 C）55 D）45 16.采用开放地址法解决冲突的散列查找中，发生聚集的原因主要是( ). A)数据元素过多 B)装填因子过大 C)散列函数选择不好 D)解决冲突的方法不好,15.C 16.C,本章总结： 1.顺序表和有序表的查找方法及平均查找长度的计算; 2.静态判定树的构造方法和查找算法，理解判定树与折半查找的关系； 3.二叉排序树（查找树）的构造和查找算法； 4.熟练掌握哈希表的构造方法(构建哈希表及处理冲突的方法),深刻理解哈希表与其它结构的表的实质性差别； 5.掌握按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。,