算法与数据结构查找课件.ppt

《算法与数据结构查找课件.ppt》由会员分享，可在线阅读，更多相关《算法与数据结构查找课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据算法与数据结构构查找找第1页，此课件共67页哦BUPT8.1 基本概念与术语基本概念与术语查找表查找表 同一类型的记录(数据元素)的集合集合。查找查找 指定某个值，在查找表中确定是否存在一个记录，该记录的关键关键字字等于给定值。关键字关键字 记录(数据元素)中的某个数据项的值。主关键字主关键字 该关键字可以唯一地标识一个记录。次关键字次关键字 该关键字不能唯一标识一个记录。静态查找表静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表动态查找表 在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找成功查找成功 查找表中存在满足查找条件的记录。查找不

2、成功查找不成功 查找表中不存在满足查找条件的记录。第2页，此课件共67页哦BUPT内查找内查找 整个查找过程都在内存中进行。外查找外查找 在查找过程中需要访问外存。平均查找长度平均查找长度ASL查找方法时效的度量 为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数 pi：查找第i个记录的概率，(不特别声明时认为等概率 pi=1/n)ci：找到第i个记录所需的比较次数约定：无特殊说明，一般默认关键字的类型为整型约定：无特殊说明，一般默认关键字的类型为整型第3页，此课件共67页哦BUPT8.2 顺序表的查找顺序表的查找 0 1 n-1 n r

3、0.n a0 a1 an-1 rn.key=K算法描述算法描述int seqsearch(int*a,const int n,const int K)int i=0;an=K;while(ai!=K)i+;return i;第4页，此课件共67页哦BUPT程序设计技巧程序设计技巧 设置监视哨，提高算法效率。性能分析性能分析v空间：一个辅助空间。v时间：1)查找成功时的平均查找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+.+n)/n=(n+1)/2 2)查找不成功时的平均查找长度 ASLf=n+1算法特点算法特点v算法简单，对表结构无任何要求vn很大=查找效率较低v改进措施：非等概

4、率查找时，可将查找概率高的记录尽量排在表前部。第5页，此课件共67页哦BUPT8.3 二分查找二分查找满足满足 ri.key ri+1.key,0 i n-1 仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。折半折半(二分二分)查找法查找法 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid high =(low+high)/2 K=21 l h m K=85 l h m 1 11 6 1 11 6 1 5 3 7 11 9 4 5 4 10 11 10 10 9第6页，此课件共67页

5、哦BUPT算法描述算法描述int binsearch(int K,int v,int n)int low,high,mid;low=1;high=n;while(low=high)mid=(low+high)/2;if(K vmid)low=mid+1;else/*找到了匹配的值找到了匹配的值*/return mid;return-1;/*没有查到没有查到*/第7页，此课件共67页哦BUPT性能分析性能分析 h=log2n+1 同完全二叉树，二叉树性质4成功查找时的平均查找长度（等概率）：ASLs=例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找时的查找长度：h-1或h次

6、-13-46-79-101-22-34-55-67-88-910-1111-639147 102581112h判定树判定树（描述查找过程的二叉树）外结点内结点lc,flag)；/中序遍历左子树 if(pre=NULL)pre=t；/中序的第一个结点不判断 else if(pre-datadata)pre=t；/前驱指针指向当前结点 else flag=FLASE；/不是完全二叉树 JudgeBST(t-rc,flag)；/中序遍历右子树 第19页，此课件共67页哦BUPT方法2：照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最

7、大值而小于右子树的最小值。bool JudgeBST(BTree t)if(t=NULL)return TRUE；if(JudgeBST(t-lc)&JudgeBST(t-rc)m=max(t-llink)；n=min(t-rlink)；/左子树中最大值和右子树中最小值 return(t-datam&t-datarc！=null)p=p-rc；return p-data；int min(BTree p)/求右子最小值 if(p=NULL)return maxint；else while(p-lc!=NULL)p=p-lc；return p-data；第20页，此课件共67页哦BUPT在二叉排序

8、树上的操作在二叉排序树上的操作1.查找查找例例 K=28 K=32bst45241228bst455390241228325390 查找步骤：若根结点的关键字值等于查找的关键字，成功。查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字值，查其右子树。若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。第21页，此课件共67页哦BUPTBitree SearchBST(BiTree T,KeyType key)/在二叉分类树查找关键字之值为 key 的结点，找

9、到返回该结 /点的地址，否则返回空。T 为根结点的指针。if (T=NULL)|(key=T-data)return(T);else if(key data.key )return(SearchBST(T-lc,key);else return(SearchBST(T-rc,key);查找算法查找算法第22页，此课件共67页哦BUPT2.插入插入首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。3.生成生成算法步骤算法步骤 反复执行以下

10、操作 a.读入一个记录，设其关键字为K；b.调用查找算法，确定插入位置；c.调用插入算法，实施插入结点的操作；第23页，此课件共67页哦BUPT例：将序列122、99、250、110、300、280 作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099第24页，此课件共67页哦BUPT4.删除删除依据被删除结点p的不同情况分析：1.p是叶子结点：修改其双亲指针即可2.p只有左孩子：用p的左子树代替以p为根的子树 p只有右孩子：用p的右子树代替以p为根的子树3.p有两个孩子：找到p的中序后继(或前趋)结点q，q的数据复

11、制给p，删除只有右子(或左子)/无孩子的q第25页，此课件共67页哦BUPT例：(1)(2)(2)(3)5320901050869541241528891304539878992第26页，此课件共67页哦BUPTvoid Delete(BSTree T,keytype X)/在二叉排序树T上，删除为X的结点。BSTree f,p=T;while(p&p-key!=X)/查找值为X的结点 if(p-keyX)f=p;p=p-lc;/f为p的双亲 else f=p;p=p-rc;if(p=NULL)printf(“无关键字为X的结点n”);exit(0);if(p-lc=NULL)/被删结点无左子

12、树 if(f-lc=p)f-lc=p-rc;/将被删结点的右子树接到其双亲上 else f-rc=p-rc;else/被删结点有左子树 q=p;s=p-lc;while(s-rc!=NULL)/查左子树中最右下的结点（中序最后结点）q=s;s=s-rc;p-key=s-key;/结点值用其左子树最右下的结点的值代替 if(q=p)p-lc=s-lc;/被删结点左子树的根结点无右子女 else q-rc=s-lc;/s是被删结点左子树中序序列最后一个结点 free(s);第27页，此课件共67页哦BUPT4.性能分析性能分析v给定树的形态，等概率查找成功时的ASL=ci/n最差(单支树)：(n+

13、1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2nv关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树第28页，此课件共67页哦BUPT8.7 平衡二叉树平衡二叉树(AVL树树)1.定义定义平衡二叉树平衡二叉树或者是空树，或者是满足如下性质的二叉排序树：1)它的左、右子树的高度之差的绝对值不超过1；2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子平衡因子：该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二

14、叉树：每个结点的平衡因子都为平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉排序树。的二叉排序树。第29页，此课件共67页哦BUPT2.结点的存储结构结点的存储结构 lc bf key otherinfo rc lc：左孩子指针 rc：右孩子指针 bf：平衡因子 key：记录的关键字 otherinfo：记录的其它数据成分第30页，此课件共67页哦BUPT4.在平衡二叉树上的操作在平衡二叉树上的操作查找查找查找方法同二叉排序树。插入插入 插入新结点之后仍应保持平衡二叉树的性质不变。例 平衡二叉树的生成过程15001525-1-2-1000000-1-1001-2-20000-115253

15、53525152515359015253590651525653590第31页，此课件共67页哦BUPT调整范围的确定调整范围的确定 插入结点后，找到离插入结点最近且平衡因子绝对值超过1的祖先结点（危机节点），则以该危机节点为根的子树将是可能不平衡的最小子树，可将重新平衡的范围局限于这棵子树。调整的类型调整的类型 LL型型-表示新插入结点在危机结点的左子左子的左子树左子树上LR型型-表示新插入结点在危机结点的左子左子的右子右子树上RL型型-表示新插入结点在危机结点的右右子子的左子树左子树上RR型型-表示新插入结点在危机结点的右右子子的右右子树子树上第32页，此课件共67页哦BUPT调整的方法调

16、整的方法LL型平衡旋转型平衡旋转一次顺时针旋转AB+1h-10+2+1hh-1h-1LL 型调整型调整BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点调整前：高度为调整前：高度为 h+1 中序序列：中序序列：ABBLBRAR调整后：高度为调整后：高度为 h+1 中序序列：中序序列：ABBLBR注意：注意：调整调整后后 平衡平衡因子因子为为 0ABAR第33页，此课件共67页哦BUPTLR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整型调整BLAR危机结点危机结点CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CL

17、h-1-10ABBLARCCLCR调整后：调整后：高度为高度为 h+1 中序序列：中序序列：ABBLARCCLCRA调整前：调整前：高度为高度为 h+1 中序序列：中序序列：h-1情形情形A注意：注意：调整调整后后 平衡平衡因子因子为为+1,0,0第34页，此课件共67页哦BUPTLR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整型调整BLAR危机结点危机结点调整前：调整前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2

18、+10ABBLARCCRCL调整后：调整后：高度为高度为 h+1 中序序列：中序序列：AABBLARCCRCL情形情形B第35页，此课件共67页哦BUPT注意：注意：调整调整后后 平衡平衡因子因子为为 0,0,0LR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+10+2-1LR 型调整型调整危机结点危机结点调整前：调整前：高度为高度为 2 中序序列：中序序列：CBC0ABCA新插入结点新插入结点ABC调整后：调整后：高度为高度为 2 中序序列：中序序列：ca0b00情形情形C第36页，此课件共67页哦BUPTRR型平衡旋转型平衡旋转一次逆时针旋转AB-1h-10-2-1hh-1h-1

19、RR 型调整型调整BLBRALBA0h0h-1h-1BLAL危机结点危机结点调整前：高度为调整前：高度为 h+1 中序序列：中序序列：BAALBLBR调整后：高度为调整后：高度为 h+1 中序序列：中序序列：注意：注意：调整调整后后 平衡平衡因子因子为为 0ABBRBAALBLBR第37页，此课件共67页哦BUPTRL型平衡旋转型平衡旋转一次顺时针旋转+一次逆时针旋转AALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1 h-211(-1)00(1)-1(0)危机结点危机结点第38页，此课件共67页哦BUPT删除删除 （思路同插入）v将删除结点q转化为q最

20、多有一个孩子的情形，即若q有两个孩子，则以其中序前驱/后继结点r取代它，删除r；v若树的平衡性被破坏，利用单一/双重旋转恢复。性能性能定理：一个具有n个结点的平衡二叉树形，其高度h为 log2(n+1)h 1.4404log2(n+2)-0.328 结论：最坏情况下，AVL树的高度约为1.44log2n，而完全平衡的二叉树高度约为log2n，因此AVL树是接近最优的，其平均查找长度与log2n同数量级。第39页，此课件共67页哦BUPT8.7 B+树与树与B-树树采用B+与B-树的意义大量数据存放在外存中，由于是海量数据，不可能一次调入内存。因此，要多次访问外存，速度慢。所以，主要矛盾变为减少

21、访外次数。内存内存第40页，此课件共67页哦BUPT用用二叉树组织文件，需访问外存次数太多。如：当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！502510751535609020304055708095索索引引文文件件数据数据文件文件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件存在内存、数据文件存在盘上文件访问示意图：索引文件存在内存、数据文件存在盘上第41页，此课件共67页哦BUPTB-树树B-树是一种平衡的多路查找树。应用于文件系统。1.定义定义 一棵 m 阶阶B-树树，或为空树，或为满足下列特性的 m 叉树

22、：1、树中每个结点最多有 m 棵子树；2、若根结点不是叶子结点，则最少有两两棵子树；3、除根之外的所有非终端结点最少有 m/2 棵子树；4、所有非终端结点包含（n,A0,K1,A1,K2,Kn,An）信息数据；其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。5、所有叶子结点在同一层上，且不带信息。第42页，此课件共67页哦BUPT例如：m=4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数至少为 m/2 =2 个；结点的关键字个数至少为 1。该 B_ 树的深度为 4。叶子结点都在第 4 层上。1，993，47，58，641，391，271，112，43，781，181，

23、35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)m/2 m棵子树棵子树叶第43页，此课件共67页哦BUPT2.B-树结点结构树结点结构(n,A0,K1,A1,K2,A2,.,Kn,An)n:关键字的个数A0：K1 且 Kn 的结点的地址（指在该 B_ 树中）K1=K2=.=Kn第44页，此课件共67页哦BUPT127阶B-树中每个结点最多有_个关键字；除根结点外所有非终端结点至少有_棵子树；65阶B+树中除根结点外所有结点至少有_个关键字；最多有_棵子树。高度为5（除叶子层之外）的三阶B-树至少有_个结点。31126643365思考：高

24、度为思考：高度为h的的m阶阶B-树（除叶子层）至少有多少个结点？树（除叶子层）至少有多少个结点？第45页，此课件共67页哦BUPT3.B-树查找过程树查找过程类似于二叉树的查找。如查找关键字为 KEY 的记录。从根开始查找，如果 Ki=KEY 则查找成功。若 Ki KEY Ki+1;查找 Ai 指向的结点若 KEY Kn;查找 An指向的结点若 找到叶子，则查找失败。第46页，此课件共67页哦BUPT设关键字的总数为 N，求 m阶 B_ 树的最大层次 L。层次层次 结点数结点数关键字的个数（最少）关键字的个数（最少）1 1 1 2 2 2(m/2 -1)3 2(m/2)2(m/2)(m/2 -

25、1)4 2(m/2)2 2(m/2)2(m/2 -1)L 2(m/2)L-2 2(m/2)L-2(m/2 -1)L+1 2(m/2)L-1 所以，N=2(m/2)L-1-1故：Llog m/2(N+1)/2)+1设设 N 1000，000 且且 m256，则则 L m-1,则该结点满。必须分裂成两个结点。否则不满结束。如结点原为：(m-1,A0,K1,A1,K2,A2,Km-1,Am-1)插入一个关键字之后变为：(m,A0,K1,A1,K2,A2,Km,Am)该结点以K m/2 为界，进行分裂：.(K m/2 ,p).(m/2-1,A0,(K1,A1)(K m/2-1,A m/2-1)(m-m

26、/2,A m/2,K m/2+1 Km,Am)生成新结点 p,将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。(K m/2 ,p)数据项插数据项插入上层结点之中入上层结点之中PP第48页，此课件共67页哦BUPT例：例：3 阶阶 B_ 树的插入树的插入key=73，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入插入第49页，此课件共67页哦BUPT5.B-树删除过程树删

27、除过程1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4。3、否则，则首先生成“替身”。用该关键字的右边子树中的最左面的结点的关键字取代。然后，删除第 L 层上的该关键字。4、从第 L 层开始进行删除。A、不动：若删除关键字值的那个结点的关键字的个数仍处于m/2-1和 m-1之间。则结束。B、借：若删除关键字值的那个结点的关键字的个数原为 m/2-1。而它们左右兄弟结点的关键字个数 m/2-1;则借一关键字过来，结束。C、并：若该结点的左右兄弟结点的关键字的个数为m/2-1;则执行合并结点的操作。如结点原为：（.(Ki,Ai),(K

28、i+1,Ai+1),.）（A0,(K1,A1)）（A0,(K1,A1)）K1 第第 L 层：找到了被删结点的替身。层：找到了被删结点的替身。第50页，此课件共67页哦BUPT例如：3 阶 B_ 树的删除操作。3244553 90371005061，70被删关键字被删关键字3244561 90371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445 903710061，703，2445 9010061，703，24 45 9010061，70并并并并并并并：和父结点的一个关键字、及兄弟合并。有可能进行到根，使并：和父结点的一个关键字、及兄弟合并

29、。有可能进行到根，使B_ 树的深度降低一层！树的深度降低一层！假定再删除该关键字假定再删除该关键字第51页，此课件共67页哦BUPTB+树树B+树是一种B-树的变形树。应用于索引顺序文件系统。1.m阶阶B+树与树与 B-树的不同之处树的不同之处1)有 n 棵子树的结点中有 n 个关键字；2)非叶结点可以看成是索引部分 索引集索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字3)所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链接；数据集数据集第52页，此课件共67页哦BUPT结点结构结点结构非叶结点 (A1,K1,.,Ai,

30、Ki,.,An,Kn)索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字叶结点 全部关键字及指向关键字记录的指针 数据集2 15 334 40 47 58 672 79 853 90 96 1052 85 1323 33 67 852 105 1322 114 1324阶B+树rootsqt第53页，此课件共67页哦BUPT2.B+树上的基本运算树上的基本运算1)查找查找v方式1：从根结点开始，利用索引集结构，向下查找直到叶子结点v方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入插入 仅在叶子结点上进行，关键字个数大于m则分裂3)删除删除 也仅在叶子结点上进

31、行，关键字个数小于m/2时，需进行合并第54页，此课件共67页哦BUPT8.8 哈希表哈希表哈希表的基本思想哈希表的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。术语术语 哈希表哈希表 一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。哈希函数哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)冲突冲突 对于keyikeyj，i j，出现的H(keyi)=H(keyj)的现象。第55页，此课件共67页哦BUPT 同义词同义词 在同一地址出现冲突的各关键字。哈希哈希(散列散列)地址

32、地址 根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。装填因子装填因子 表中填入的记录数n和哈希表表长 m之比。=n/m设计哈希表的过程设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。哈希表bb+(m-1)L第56页，此课件共67页哦BUPT哈希函数的基本构造方法哈希函数的基本构造方法构造原则：算法简单，运算量小；均匀分布，减少冲突。1.直接定址法直接定址法H(key)=a*key+b a、b为常数e.g:令：a、b为1，有两个

33、关键字k1,k2 值为 10、1000；选10、1000 作为存放地址。特点：计算简单，冲突最少。2.数字分析法数字分析法/基数转换法基数转换法取关键字在某种进制下的若干数位作为哈希地址。e.g:key=236076 基数为10，看成是 13 进制的。则：(236075)13 =8 4154 7；选取 4154 作为散列地址(假设 表长m=10000)。第57页，此课件共67页哦BUPT3.平方取中法平方取中法取关键字平方后的中间几位作为哈希地址。e.g:(4731)2 =223 82 361；选取；选取 82（假设（假设 m=100）。）。4.随机数法随机数法 H(key)=random(k

34、ey)特点：较适于关键字长度不等时的情况。5.折叠法折叠法 将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。e.g:key=381，412，975选取选取 768 或或 570 作为散列地作为散列地址（址（假设假设 m=1000）。）。381 412 9751 768 975 214 381 1 570第58页，此课件共67页哦BUPT6.除留余数法除留余数法H(key)=key MOD p (pm)m:哈希表的表长；p:最好为素数最常用，余数总在 0 p-1 之间。通常p选 m 的最大质数如：m=1024,则 p=1019。e.g:

35、选取选取 p 为质数的理由：为质数的理由：设设 key 值都为奇数，选值都为奇数，选 p 为偶数；为偶数；则则 H(key)=key MOD p，结果为奇数，结果为奇数，一半单元被浪费掉。一半单元被浪费掉。设设 key 值都为值都为 5 的倍数，选的倍数，选 p 为为 95；则则 H(key)=key MOD p，结果为：，结果为：0、5、10、15、90奇数。奇数。4/5 的单元被浪费掉。的单元被浪费掉。第59页，此课件共67页哦BUPT处理冲突的常用方法处理冲突的常用方法1.开放定址法开放定址法(空缺编址法空缺编址法)Hi=(H(key)+di)MOD m 0 H(key)m-1 i=1,

36、2,.,k (km-1)m:哈希表的表长；di:增量序列1)线性探测再散列线性探测再散列 di=1,2,.,m-1缺陷：有聚集(堆积)现象非同义词地址冲突。第60页，此课件共67页哦BUPTe.g:假定采用的 hashing 函数为：H(key)=key MOD 11 假定的关键字序列为：17、60、29、38 ；它们的散列过程为：H(17)=6H(60)=5H(29)=7 H(38)=5012345678910Hashing 表表1760293838当散列当散列 38 时发生冲突，时发生冲突，同同 60 争夺第争夺第 5 个单元个单元解决办法解决办法：探测下一个：探测下一个 空单元空单元Hi

37、=(H(key)+di)MOD 11其中：其中：di 为为 1、210冲突：冲突：初级冲突：不同关键字值的结点得到初级冲突：不同关键字值的结点得到同一个散列地址。同一个散列地址。二次聚集：同不同二次聚集：同不同散列地址的结点争夺同一个单元。散列地址的结点争夺同一个单元。结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到 O(n)级代价。级代价。思考思考：假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行多少次探测？k(k+1)/2第61页，此课件共67页哦BUPT2)二次探测再散列二次探测再散列 di=12,-12,22,-22,32,.,k2 k

38、 m/2缺陷：不易探查到整个散列空间。3)伪随机探测再散列伪随机探测再散列 di=伪随机数序列4)双重散列函数探查法双重散列函数探查法 di=i*h1(key)0 i m-1要求：h1(key)的值与m互素。m为素数时，h1(key)可取1到m-1之间的任何数，建议：h1(key)=key mod(m-2)+1m为2的方幂时，h1(key)可取1到m-1之间的任何奇数注意：开放定址法不宜执行删除操作注意：开放定址法不宜执行删除操作第62页，此课件共67页哦BUPT2.再哈希法再哈希法Hi=RHi(key)i=1,2,.,k出现冲突时，采用多个 hashing 函数计算散列地址，直到找到空单元为

39、止。如：H1(key)=key MOD 11 H2(key)=(key+MOD 9)1 H3(key)=.H10(key)=.第63页，此课件共67页哦BUPT3.链地址法链地址法为每个哈希地址建立一个单链表，存储所有具有同义词的记录。100123456789 K1K2K3 K4K5K6 同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。冲突处理简单，无堆积现象，平均查找长度较短；较适合于事先无法确定表长的情况；可取1，当结点信息规模较大时，节省空间删除结点的操作易于实现第64页，此课件共67页哦BUPT4.建立公共溢出区建立公共溢出区将发生冲突的结点都存

40、放在一个公共溢出区内。通常用于组织存在于外存设备上的数据文件。hash表(基本区)只存放一个记录。发生冲突的记录都存放在公共溢出区内。012345678910 K1K2K3K4K5 K2K3K5K6基本区（基本区（hash表）表）公共溢出区公共溢出区第65页，此课件共67页哦BUPT哈希表的查找及其分析哈希表的查找及其分析查找方法同查找方法同 hashing 函数的产生办法。函数的产生办法。例：key =en to tre fire fem seks syv H(key)=2 0 3 0 4 8 1 解决冲突方法：线性探测再散列 0 1 2 3 4 5 6 7 8 ASLs=(1+1+1+2+1+1+5)/7=12/7 ASLf=(7+6+5+4+3+2+1+1+8)/9=37/9 =7/9entotrefirefemsekssyv第66页，此课件共67页哦BUPT平均查找长度与哈希表的装填因子的关系平均查找长度与哈希表的装填因子的关系 在一般情况下，冲突的可能性，ASL，但空间的浪费。成功ASL 失败ASL 线性探测再散列 伪随机探测再散列 链地址法第67页，此课件共67页哦