数据结构第九章查找PPT课件

《数据结构第九章查找PPT课件》由会员分享，可在线阅读，更多相关《数据结构第九章查找PPT课件（86页珍藏版）》请在金锄头文库上搜索。

1、华中科技大学计算机学院华中科技大学计算机学院华中科技大学华中科技大学计算机学院计算机学院数据结构数据结构1第九章第九章 查找查找 查找表查找表: : 由同一类型的数据元素（记录）组成的集合。 记作：ST=a1,a2,.,an学 号姓 名性别数学外语200041刘大海 男 80 75200042王 伟 男 90 83 200046吴晓英 女 82 88200048 王 伟 女 80 90. . . . . 序号1234 n 关键字关键字: : 可以标识一个记录的数据项 主关键字主关键字: : 可以唯一地标识一个记录的数据项 次关键字次关键字: : 可以识别若干记录的数据项学生成绩表 数据项1(主

2、关键字)数据项2数据项52华中科技大学计算机学院华中科技大学计算机学院查找表的操作: 生成查找表 查找元素(记录)x在是否在表ST中 查找元素(记录)x的属性 插入新元素(记录)x 删除元素(记录)x .3华中科技大学计算机学院华中科技大学计算机学院查找查找-根据给定的某个关键字值，在查找表中确定一个其关键字等于给定值的记录或数据元素。 设k为给定的一个关键字值，R1.n为n个记录的表,若存在Ri.key=k,1in,称查找成功查找成功；否则称查找失败查找失败。静态查找静态查找: : 查询某个特定的元素，检查某个特定的数据元素的属性,不插入新元素或删除元素(记录) 。动态查找动态查找: : 在

3、查找过程中，同时插入查找表中不存在的数据元素(记录)。4华中科技大学计算机学院华中科技大学计算机学院查找表的类型及其查找方法 (1) 静态查找静态查找表表 顺序表，用顺序查找法 线性链表，用顺序查找法 有序的顺序表，用：折半查找法； *斐班那契查找法；插值查找法； 索引顺序表/分块表，用分块查找法。 (2) 动态查找动态查找表表 二叉排序树,平衡二叉树(AVL树） * B树, B+树, 键树 (3) 哈希哈希( (Hash)Hash)表表5华中科技大学计算机学院华中科技大学计算机学院平均查找长度平均查找长度-查找一个记录时比较关键字次数的平均值。 n ASL= PiCi i=1 Pi - 查找

4、ri的概率 Ci - 查找ri所需比较关键字的次数6华中科技大学计算机学院华中科技大学计算机学院2041刘大海.2042王 伟.2046吴晓英. . . . . . .0123maxsizeelem key name .监视哨监视哨9.19.1 静态查找表静态查找表9.1.1 9.1.1 顺序表与顺序查找法顺序表与顺序查找法 1.顺序表的描述 length7例1 元素类型为记录(结构) #define maxsize 100 /表长100 typedef struct node keytype key ； /关键字类型 char name6； /姓名 . /其它 ElemType； typed

5、ef struct ElemType elemmaxsize+1；/maxsize+1个记录, /elem0为监视哨 int length; SSTable; SSTable ST1,ST2;8华中科技大学计算机学院华中科技大学计算机学院 121030202515/60 1 2 3 4 5 6 maxsize length监视哨例2 元素类型为整型 #define maxsize 100 /表长100 typedef int ElemType； typedef struct ElemType elemmaxsize+1；/maxsize+1个记录, /elem0为监视哨 int length;

6、 SSTable; SSTable ST1,ST2;9华中科技大学计算机学院华中科技大学计算机学院2. 顺序查找法(sequential search)算法设计 算法算法1 1：假定不使用监视哨假定不使用监视哨elem0elem0 基本思想： 将关键字k依次与记录的关键字: elem n.key, elemn-1.key，., elem1.key 比较。 如果找到一个记录elemi,有: elemi.keyk (1in)， 则查找成功，停止比较,返回记录的下标i； 否则,查找失败,返回0。10华中科技大学计算机学院华中科技大学计算机学院输入：查找表ST，查找条件（关键字）k输出：成功时：记录序

7、号，失败时：0int sequsearch(SSTable ST,keytype k) int i=ST.length； /从第n个记录开始查找 while (i=1 & k!=ST.elemi.key) i-； /继续扫描 if (i) printf(”successn”)； /查找成功 else printf(”failn”)； /查找失败 return i； /返回记录的下标i 11华中科技大学计算机学院华中科技大学计算机学院算法算法2 2：假定使用监视哨假定使用监视哨elem0elem0 基本思想： 先将关键字k存入elem0.key,再将k依次与elemn.key,.,elem1.k

8、ey,elem0.key 进行比较。 如果找到一个记录,有： k=elem i.key, (0in)，则停止比较。 如果 i0,则查找成功；否则,查找失败。12华中科技大学计算机学院华中科技大学计算机学院输入：查找表ST，查找条件（关键字）k输出：成功时：记录序号，失败时：0int sequsearch(SSTable ST,keytype k) int i=ST.length； /从第n个记录开始查找 ST.elem0.key=k； /k填入ST.elem0.key while( k!=ST.elemi.key ) i- ； /继续扫描 return i； /返回记录的下标i 13华中科技大

9、学计算机学院华中科技大学计算机学院3 查找算法性能分析： 对n个记录的表,所需比较关键字的次数 只考虑查找成功: 最少为1,最多为n 假定每个记录的查找概率相等， 即 P1 = P2 = . = Pn =1/n ASL= = = =(n+1)/2 14华中科技大学计算机学院华中科技大学计算机学院 考虑查找失败: 使用监视哨使用监视哨elem0,elem0,为 n+1n+1 不使用监视哨不使用监视哨elem0,elem0,为 n n 假定查找成功和失败的机会相同，对每个记录的查找概率相等， Pi=1/(2*n), 则 1 n n+1 n+1 n+1 ASL=- Ci + - =- + - =3(

10、n+1)/43(n+1)/4 2n i=1 2 4 2 159.1.2 9.1.2 有序的顺序表的查找与折半查找法有序的顺序表的查找与折半查找法1.有序表 elem1.keyelem2.key.elemn.key2.折半查找(binary search,对半查找，二分查找) 假定 k=10 5101218202530401 2 3 4 5 6 7 81 2 3 4 5 6 7 8 low mid hig low mid hig low=1,hig=8low=1,hig=8mid=(low+hig)/2=4mid=(low+hig)/2=4 5101218202530401 2 3 4 5 6

11、7 81 2 3 4 5 6 7 8 low mid higlow mid hig low=1,hig=3low=1,hig=3mid=(low+hig)/2=2mid=(low+hig)/2=216华中科技大学计算机学院华中科技大学计算机学院 假定假定k=40k=40 5101218202530401 2 3 4 5 6 7 81 2 3 4 5 6 7 8 low mid hig low mid hig low=1,hig=8low=1,hig=8mid=(low+hig)/2=4mid=(low+hig)/2=4 5101218202530401 2 3 4 5 6 7 81 2 3 4

12、 5 6 7 8 low mid hig low mid hig low=5,hig=8low=5,hig=8mid=(low+hig)/2=6mid=(low+hig)/2=617华中科技大学计算机学院华中科技大学计算机学院 5101218202530401 2 3 4 5 6 7 81 2 3 4 5 6 7 8 low mid higlow mid hig low=7,hig=8low=7,hig=8mid=(low+hig)/2=7mid=(low+hig)/2=7 假定假定 k=40k=40（续）（续） 5101218202530401 2 3 4 5 6 7 81 2 3 4 5

13、6 7 8 low mid higlow mid hig low=8,hig=8low=8,hig=8mid=(low+hig)/2=8mid=(low+hig)/2=8 18华中科技大学计算机学院华中科技大学计算机学院 5101218202530401 2 3 4 5 6 7 81 2 3 4 5 6 7 8 low mid higlow mid hig low=1,hig=8low=1,hig=8mid=(low+hig)/2=4mid=(low+hig)/2=4 5101218202530401 2 3 4 5 6 7 8 low mid hig low mid hig low=5,hi

14、g=8low=5,hig=8mid=(low+hig)/2=6mid=(low+hig)/2=6假定假定 k=22k=22 5101218202530401 2 3 4 5 6 7 81 2 3 4 5 6 7 8 low mid higlow mid hig low=5,hig=5low=5,hig=5mid=(low+hig)/2=5mid=(low+hig)/2=5 19华中科技大学计算机学院华中科技大学计算机学院 假定假定 k=22k=22（续）（续） 5101218202530401 2 3 4 5 6 7 8 mid hig lowmid hig low mid=5 mid=5 l

15、ow=6,hig=5low=6,hig=5 5101218202530401 2 3 4 5 6 7 8 mid hig lowmid hig low mid=5 mid=5 low=6,hig=5low=6,hig=5 higlow,higlow,查找失败查找失败203 3 折半查找算法折半查找算法1 1 int binsrch(SSTable ST,keytype k) int low,mid,hig； low=1； hig=ST.length； while (low=hig) mid=(low+hig)/2； /计算中间记录的地址 if (kST.elemmid.key) hig=mid

16、-1； /查左子表 else if (k=ST.elemmid.key) break； /查找成功,退出循环 else low=mid+1； /查右子表 21华中科技大学计算机学院华中科技大学计算机学院if (ST.elemmid.key=k) printf(successn”)； /查找成功 return mid； else printf(failn”)； /查找失败 return 0； 22 折半查找算法2 int binsrch(SSTable ST,keytype k)int low,mid,hig； low=1； hig=ST.length； while (low=high) mid

17、=(low+high)/2； if (kdata=x； /生成并插入结点x t-lchild=t-rchild=NULL； /为叶子结点 else if(x.keydata.key) t-lchild=intree(t-lchild,x)；/插入左子树 else t-rchild=intree(t-rchild,x)；/插入右子树 return t; 34(5)二叉排序树的查找算法查找算法 ( (返回值返回值 失败：失败：NULL NULL 成功：非成功：非NULLNULL，结点指针），结点指针）a) 递归算法递归算法 struct node *search_tr(struct node *t

18、, keytype k) if (t=NULL) return NULL； /查找失败 else if (k=t-data.key) return t； /查找成功 else if (kdata.key) return search_tr(t-lchild,k)；/查左子树 else return search_tr(t-rchild,k)；/查右子树 35华中科技大学计算机学院华中科技大学计算机学院b) 非递归算法非递归算法struct node *search_tree(struct node *t,keytype k) while (t!=NULL) if (k=t-data.key)

19、return t； /查找成功 else if (kdata.key) t=t-lchild； /查左子树 else t=t-rchild； /查右子树 return t； /查找失败 36(6)二叉排序树的删除n在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。n为保证在删除节点后二叉排序树的性质不会丢失:n n删删删删除除除除叶叶叶叶结结结结点点点点，只需将其双亲结点指向它的指针置空，再释放它即可。n n被被被被删删删删结结结结点点点点缺缺缺缺左左左左子子子子树树树树（或或或或右右右右子子子子树树树树），可以用被删节点的右子树（或

20、左子树）顶替它的位置，再释放它。37n n被被删删结结点点左左、右右子子树树都都存存在在，可以在它的右子树中寻找中序下的第一个结点(关键值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。5378651787092345删除45缺右子树, 用左子树顶替53786517870923388853788817940923删除78缺左子树, 用右子树顶替53948817092353788117940945删除78在右子树上找中序下第一个结点填补236553818817940945236539(7)查找性能分析 最好情况最好情况(为满二叉树） n+1 ASL=-log2(n+1)-1 = O

21、(log2 n) n 最坏情况最坏情况(为单枝树): ASL=(1+2+.+n)/n=(n+1)/2 平均值平均值: : ASLO(log2 n)5828493045581519101811488697964756560满二叉树满二叉树单枝树单枝树ASL=(15+1)/15*log2(15+1)-13.3 ASL=(1+2+3+4)/4=2.5402.2.平衡二叉树平衡二叉树( (高度平衡二叉树）高度平衡二叉树） AVL树：由G.M.Adelson-Velskii和E.M.Landis提出。 结点的平衡因子：结点的左右子树的深度之差。 平衡二叉树：任意结点的平衡因子的绝对值 小于等于1的二叉树

22、。T1 T2 T3 T4 T5 0102-1000-112100-2（1）AVL树的定义41（2）AVL树的存储结构： typedef int DataType; /结点数据类型typedef struct node /AVL树结点定义 DataType data; /结点数据域 int balance; /结点平衡因子域 struct node *leftChild, *rightChild; /结点左、右子树指针域 AVLNode;typedef AVLNode * AVLTree; /AVL树42n如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化

23、。n平衡化旋转有两类：u 单旋转 (左旋和右旋)u 双旋转 (左平衡和右平衡)n每插入一个新结点时, AVL 树中相关结点的平衡状态会发生改变。因此,在插入一 个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。（3）平衡化旋转43n如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。n如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一 个的镜像，其方向与不平衡的形状相关。n如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。44右单旋转

24、右单旋转右单旋转右单旋转左单旋转左单旋转左单旋转左单旋转 左右双旋转左右双旋转左右双旋转左右双旋转右左双旋转右左双旋转右左双旋转右左双旋转45n在子树E中插入新结点，该子树高度增1导致结点A的平衡因子变成-2，出现不平衡。n沿插入路径检查三个结点A、C和E。它们处于方向为“”的直线上，需做左单旋转。n以结点C为旋转轴，让结点A逆时针旋转。（a）左单旋转 (RotateLeft )hhhACEBDhhh+1BACEDhhh+1CEABD-1-1-2-20 0-1-10 00 046n在子树D中插入新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。n沿插入路径检查三个结点A、B和D。

25、它们处于方向为“/”的直线上，需做右单旋转。n以结点B为旋转轴，让结点A顺时针旋转。（b）右单旋转 (RotateRight )hhhACEBDhh+1BACEDhhh+1CEABDh0 00 00 0+ + + +1 1+ + + +1 1+ + + +2 247n在子树F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为+2，发生了不平衡。（c）先左后右双旋转 (RotationLeftRight)插入插入0 00 0+ + + +1 1+ + + +2 2-1-1+ + + +1 1hhACEDh-1hhAhBCEDB左单左单左单左单旋转旋转旋转旋转FGFGh-1h-148插入插入

26、0 00 0+ + + +1 1+ + + +2 2-1-1+ + + +1 1hhACEDh-1hhAhBCEDB左单左单左单左单旋转旋转旋转旋转FGFGn从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“”的折线上，因此需要进行先左后右的双旋转。n以结点E为旋转轴，将结点B逆时针旋转。h-1h-1490 00 0+ + + +2 20 0 0 00 0-1-1hhACED+ + + +2 2hhhAhBCEDB右单右单右单右单旋转旋转旋转旋转FGFGh-1h-1n再以结点E为旋转轴，将结点A顺时针旋转。50n右左双旋转是左右双旋转的镜像n在子树F或G中插入新结点，该子树高度增1

27、，A的平衡因子变为+2，发生了不平衡。（d）先右后左双旋转 (RotationRightLeft)插入插入插入插入右右右右单单单单旋旋旋旋转转转转-1-10 00 00 0+1+10 0hhACEDBFG-2-20 00 00 0hhACEhBFGDh-1h-1h-151n从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“”的折线上，因此需要进行先右后左的双旋转。n以结点D为旋转轴，将结点C顺时针旋转。插入插入插入插入右右右右单单单单旋旋旋旋转转转转-1-10 00 00 0+1+10 0hhACEDBFG-2-20 00 00 0hhACEhBFGDh-1h-1h-152n再以结

28、点D为旋转轴，将结点A逆时针旋转。0 00 0-2-20 0 0 0+ + + +1 10 0hhACE-2-2hhhAhBCEDB左单左单左单左单旋转旋转旋转旋转FGFGDh-1h-153n在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| 1，则出现了不平衡，需要做平衡化处理。n算法从一棵空树开始，通过输入一系列对象关键码，逐步建立AVL树。在插入新结点时使用平衡旋转方法进行平衡化处理。（3）AVL树的插入541616例，例，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。0 0

29、3163+ + + +1 10 07 70 0-1-1+ + + +2 2左右双旋左右双旋左右双旋左右双旋7 73160 00 00 07 73110 0+ + + +1 1-1-17 7316161190 0+ + + +1 1+ + + +2 2右单旋右单旋右单旋右单旋37 71690 00 00 0-1-137 71126916110 0-1-1-1-1-2-2-2-25518180 03163+ + + +1 10 0160 0-2-2右左双旋右左双旋右左双旋右左双旋7390 00 00 0182611+ + + +1 1732616119+ + + +1 1左单旋左单旋左单旋左单旋9

30、716140 00 0-1-171126269-1-1-1-111561518-2-231816+ + + +2 2左右双旋左右双旋左右双旋左右双旋730 00 00 0117149+ + + +1 116150 0-1-111262614-1-1+ + + +2 29从空树开始的建树过程从空树开始的建树过程57华中科技大学计算机学院华中科技大学计算机学院 平衡二叉树、二叉排序树、平衡二叉排序树的区别：平衡二叉树、二叉排序树、平衡二叉排序树的区别：4850351020414560平衡二叉排序树6870651020414580平衡二叉树68807510414585二叉排序树-2-1-101-1-

31、11-11000000000000058华中科技大学计算机学院华中科技大学计算机学院静态和动态查找表查找方法 静态查找表和动态查找表通过比较关键字进行查找：（1）顺序表，对数据元素的存储一般有两种形式： (a) 是按到来次序连续存放，查找时顺序比较查找； (b) 按关键字的相对关系整理后以递增或递减形式连续存放，则查找时使用顺序法或二分法比较查找。（2）二叉排序树，从根开始进行比较查找。不足：查找时无法根据关键字的值估计数据元素可能在的位置。59华中科技大学计算机学院华中科技大学计算机学院9.3 哈希(Hash)表和哈希法 存储数据元素时，利用一个Hash函数根据数据元素的关键字计算出该数据元

32、素的存储位置，查找时，也是根据给定的数据元素的关键字计算出该数据元素可能存储位置，这样一来，存储和查找的效率相当高， 哈希表也称为散列表，其数据元素的存储一般是不连续的。 通过Hash函数计算出的地址称为哈希地址或散列地址。609.3.1 9.3.1 哈希哈希表相关术语表相关术语 HashHash函数函数实现的是将一组关键字映象到一个有限的地址区间上，理想的情况是不同的关键字得到不同的地址。设K1和K2为关键字, 若K1K2,H(K1)=H(K2),则称 K1,K2为同义词同义词, ,K2与K1发生了冲突冲突例 设 H(k)=k%17 k1=5 k2=22 H(5)=5%17=5 H(22)=

33、22%17=5 H(5)=H(22)=5 5和22是同义词,5和22发生冲突619.3.1 9.3.1 哈希哈希表相关术语表相关术语采用哈希表进行存储和查找需要着重考虑两个问题：（a）选择一个好的哈希（散列）函数；（b）选择一种解决冲突（碰撞）的方法。62华中科技大学计算机学院华中科技大学计算机学院例1 人口统计表 1 10.5 2 12.6 3 11.0 4 20.8 . .150 . 序号(地址) 年 龄 人 数(万) 1 2 3 4 150H(key)=key = H(key)=key = 地址地址H(H(年龄）年龄）= = 年龄年龄 key9.3.2 构造哈希函数的方法构造哈希函数的方

34、法 1.直接定址法直接定址法 取关键字或关键字的某个线性函数值为哈希地址 H(key)=key H(key)=a.key+b63华中科技大学计算机学院华中科技大学计算机学院例2 学生成绩表200041刘大海 男 80 75200042王 伟 男 90 83 200043吴晓英 女 82 88200044 王 伟 女 80 90. . . . . . . . .1234 nkey 序号 (地址)学 号 姓 名 性别 数学 外语H(key) = key - 200040 = H(key) = key - 200040 = 地址地址H(H(学号学号)= )= 学号学号- 200040- 200040

35、 64华中科技大学计算机学院华中科技大学计算机学院例3 标识符表 ABC ABC CAD CAD DAT DAT FOX FOX YAB YAB ZOO ZOO1234 562526序号 标识符(key)H(key)=keykey的第一个字母在的第一个字母在 字母表中的序号字母表中的序号key =ABC CAD DAT FOX YAB ZOO H(key)=1 3 4 6 25 26 65华中科技大学计算机学院华中科技大学计算机学院2.除留余数法除留余数法 设哈希表HT0.m-1的表长为m，哈希地址为key除以p所的的余数： H(key)=key MOD pH(key)=key MOD p /

36、PASCAL语言 H(key)=key % pH(key)=key % p /C语言 其中：MOD,%为“取模”或“求余” p=m p=m ，p p为接近为接近m m的质数的质数( (素数素数) ), 如： 3,5,7,11,13,17,19,23,29,31,37. 或不包含小于或不包含小于2020的质因子的合数的质因子的合数，如： 713(=23*31)66华中科技大学计算机学院华中科技大学计算机学院例1 设 m=130, 取p=127, H(key)=key % 127H(key)=key % 127 0 1 2 . 129例2 设 m=256 取 p=251 H(key)=key %

37、251H(key)=key % 2510 1 2 . 25567例 设哈希表的地址范围为020,哈希函数为 H(K)=K % 19 输入关键字序列：39,22,21,37,36,38,19,解决冲突的方法为线性探测再散列线性探测再散列( (哈希哈希) ),构造哈希表HT0.20。 关键字K H(K)=K%19 39 39%19=1 22 22%19=3 21 21%19=2 37 37%19=18 36 36%19=17 38 38%19=0 19 19%19=01919与与3838冲突冲突, ,再与再与39,21,39,21,2222冲突冲突, ,存入HT4 0 1 2 3 4 5 1718

38、1920HT0.20HT0.203922213738361968 38 39 21 22 19 55 36 37 17 56再输入17,56,55 17%19=171717与与3636冲突冲突, ,再与再与3737冲突冲突,存入HT19。 56%19=185656与与3737冲突冲突, ,再与再与1717冲突冲突,存入HT20。 55%19=175555与与3636冲突冲突, ,再与再与37,17,5637,17,56冲突冲突, ,再与再与38,39,21,22,1938,39,21,22,19冲突冲突,存入HT5。对于H(k)=k % 19，所有的19a+b为同义词,0b19 如：5,24,

39、43,62,81,. 0 1 2 3 4 517181920HT0.20HT0.20keykey693.平方取中法平方取中法-取关键字平方后的中间某几位为哈希地址,即： H(k)=取k2的中间某几位数字例. 设哈希表为HT0.99,哈希函数为：H(K)=H(K)=取取k k2 2的中间的中间2 2位数位数, 输入关键字序列：39,21,6,36,38,13,用线性探测再散列法解决冲突,构造HT0.99。 K k2 H(K) 39 1521 52 21 0441 44 6 0036 03 36 1296 29 38 1444 44 13 0169 16 6 6 13 13 36 36 21 21

40、 38 38 39 39 0 3 162944455299keykey704.折叠法折叠法 将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。(1)边界折叠法边界折叠法 设表地址范围为0999 k1=056056439439527527 650 + 650 + 439 439 + + 725 =1814725 =1814 H(k1)=814 H(k1)=814 k2=123123486486790790 321 + 321 + 486 486 + + 097 =907097 =907 H(k2)=907 H(k2)=907 k3=300300600600007007 003

41、+ 003 + 600 600 + + 700 =1303700 =1303 H(k2)=303 H(k2)=303300600007056439527123486790 0 1 303814907999HT0. 999HT0. 999714.折叠法折叠法 将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。(2)移位折叠法移位折叠法( (移位法移位法) ) 设表地址范围为0999 k1=056056439439527527 056 + 056 + 439 439 + + 527 =1022527 =1022 H(k1)=022H(k1)=022 k2=123123486486

42、790790 123 + 123 + 486 486 + + 790 =1399790 =1399 H(k2)=399 H(k2)=399 k3=300300600600007007 300 + 300 + 600 600 + + 007 =907007 =907 H(k2)=907 H(k2)=907056439527123486790300600007 0 1 22399907999HT0. 999HT0. 999725.数字分析法数字分析法 设哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干分布均匀的位组成哈希地址。若干分布均匀的位组成哈希地址。 k H(k)902 200 0

43、6 67 206 904 443 31 13 431901 134 45 56 145 904 443 32 26 432 905 532 24 43 524906 617 79 91 679901345690200679044313904432690532439061791145206431 432524679HT0.999HT0.999736.随机数法随机数法 H(key)=random(key) random(key)为产生伪随机数的函数7.灵活构造哈希函数灵活构造哈希函数例.设哈希表为HT0.40HT0.40,哈希函数为： H(K)=H(K)=取取k k2 2的中间的中间2 2位数位数

44、*40/99*40/99 其中40/99将其0099压缩到0040之内， 输入关键字序列：39,21,6,36,38,13, 用线性探测再散列线性探测再散列法解决冲突。 K k2 H(K) 39 1521 52*40/99=21 21 0441 44*40/99=17 6 0036 03*40/99=1 77 5929 92*40/99=37 38 1444 44*40/99=17 13 0169 16*40/99=6 6 13 21 38 39 77 0 0 1 3 617 18 21374040keykey749.3.3 如何解决冲突1.开放地址法开放地址法( (开式寻址法开式寻址法) )

45、 假定记录Ri,RX的关键字Ki,KX为同义词，散列地址为q q,Ri已存入HT0.m-1中的HTq中，则RX 存入HT中的某个空位上。依次在地址: q+1,q+2,.,m-1,0,1,.,q-1q+1,q+2,.,m-1,0,1,.,q-1 中寻找一个空位，叫做线性探测再散列。 (1) 线性探测再散列线性探测再散列 Ki.HT0.m-1 0 1 q-1 qq+1m-1RiRX75课堂练习：设 H(k)=k的首字母在字母表中的序号的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，构造哈希表 HT0.28。 k H(k) A 1 DEC 4 ZMN 26 DAB 4 ZE

46、26 ANT 1 YY 25 ZOO 26 CAD 3 YES 25 ZY 26 LL 12 DE 4 0 1 2 3 4 5 6 7 121325262728HT0.28HT0.28 1 2 3 4 5 6 7 8 91011121376例 设 H(k)=k k的首字母在字母表中的序号的首字母在字母表中的序号，用线性探测再散列 法解决冲突，依次用下列关键字，构造哈希表HT0.28。 YES A ANT CAD DEC DAB ZY DE LL YY ZMN ZE Z00 k k H(k)H(k) 1 A 11 A 1 2 DEC 4 2 DEC 4 3 ZMN 26 3 ZMN 26 4 D

47、AB 4 4 DAB 4 5 ZE 26 5 ZE 26 6 ANT 1 6 ANT 1 7 YY 25 7 YY 25 8 ZOO 26 8 ZOO 26 9 CAD 3 9 CAD 310 YES 2510 YES 2511 ZY 2611 ZY 2612 LL 12 12 LL 12 13 DE 4 13 DE 4 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 12122525262627272828HT0.28HT0.2877(2) 二次探测再散列二次探测再散列 假定记录Ri和Rj的关键字Ki和Kj为同义词，散列地址为q, Ri已存入HT0.m-1中的HTq中。若依次

48、在地址q+1q+12 2,q-1,q-12 2,q+2,q+22 2,q-2,q-22 2,.,q+i,.,q+i2 2,q-i,q-i2 2 ,.,.中寻找一个空位，叫做二次探测再散列。例: 设记录X和A为同义词，散列地址为50, 二次探测再散列的地址序列为：51,49,54,46,59,41,66,34,75,.HT0.99G GE EC C A A B BD DF F0 34 41 46 49 50 51 54 59 66 75 99XXXXXXXXGE EC C A A B BD DF FX X0 34 41 46 49 50 51 54 59 66 75 99782.2.链地址法链地

49、址法 将关键字为同义词的所有记录存入同一链表中。（表头插入）例 设设H(k)=kH(k)=k的首字母在字母表中的序号的首字母在字母表中的序号,用下列关键字造哈希表 HT1.26 k H(k) A 1 DEC 4 ZMN 26 DAB 4 ZE 26 ANT 1 YY 25 ZOO 26 CAD 3 YES 25 ZY 26 LL 12 DE 4 1 2 3 4 5 6 7 8 910111213HT1.26ZEZOOZYZMN DEYESYYCAD ANT ADABDEC LL 1 2 3 4122526792.链地址法链地址法 将关键字为同义词的所有记录存入同一链表中。(表尾插入)例 设H(

50、k)=kH(k)=k的首字母在字母表中的序号的首字母在字母表中的序号, ,用下列关键字造哈希表 HT1.26 k H(k) A 1 DEC 4 ZMN 26 DAB 4 ZE 26 ANT 1 YY 25 ZOO 26 CAD 3 YES 25 ZY 26 LL 12 DE 4 1 2 3 4 5 6 7 8 910111213HT1.26ZOOZEZMNZYDECYYYES CAD A ANT DABDELL 1 2 3 4122526803.建立公共溢出区建立公共溢出区 将发生冲突的所有记录存入一个公共溢出表公共溢出表OT0.vOT0.v中。例 设H(k)=kH(k)=k的首字母在字母表中

51、的序号的首字母在字母表中的序号, ,用下列关键字生成基本表HT1.26和溢出表OT0.50 k H(k) 1 A 1 2 DEC 4 3 ZMN 26 4 DAB 4 5 ZE 26 6 ANT 1 7 YY 25 8 ZOO 26 9 CAD 310 YES 2511 ZY 2612 LL 12 13 DE 4 ACADDECLLYYZMNHT1.26 1 2 3 4122526DABZEANTZOOYESZYDEOT0.50 1 2 3 4 5 6 750 814.再哈希法再哈希法 发生冲突时，使用下一个哈希函数计算哈希地址： j1=H1(K)j1=H1(K)；j2=H2(K)j2=H2(

52、K)；j3=H3(K)j3=H3(K)；.9.3.4 哈希表的查找及其分析ZEZOOZYZMNDEYESYYCADANT ADABDECLL例1(链地址法链地址法) )假定每个记录的查找概率相等，查找成功时的平均查找长度： ASL=(1+2+1+1+2+3+1+1+2+ 1+2+3+4)/13 = 24/13 1.8582例2 （给定线性探测再散列得到的哈希表如右所示)假定每个记录的查找概率相等，查找成功时的平均查找长度. 关键字关键字K H(K) K H(K) 比较次数比较次数 YES 25 5 A 1 1 ANT 1 2 CAD 3 1 DEC 4 1 DAB 4 2 ZY 26 10 D

53、E 4 4 LL 12 1 YY 25 1 ZMN 26 1 ZE 26 2 Z00 26 3 合计 34 YES A ANT CAD DEC DAB ZY DE LL YY ZMN ZE Z00HT0.28 0 1 2 3 4 5 6 7 121325262728ASLsucc=34/132.6283 YES A ANT CAD DEC DAB ZY DE LL YY ZMN ZE Z00HT0.28 0 1 2 3 4 5 6 7 121325262728ASLunsucc=108/28 3.857例2(续) (线性探测再散列)查找不成功时的平均查找长度.需统计不成功时比较次数H(K) 比较次数 H(K) 比较次数0 91 8 15 12 7 16 13 6 17 14 5 18 15 4 19 16 3 20 17 2 21 18 1 22 19 1 23 110 1 24 111 1 25 1312 2 26 1213 1 27 1114 128 1084一般情况：平均查找长度依赖于哈希表的装填因子： =(表中填入记录数)/(哈希表的长度)解决冲突的方法平均查找长度查找成功查找失败线性探测再散列二次探测再散列链地址85个人观点供参考，欢迎讨论