算法和数据结构查找

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

2、T共七十页，创作于2022年6月BUPT SCSTBUPT内查找 整个查找过程都在内存中进行。外查找 在查找过程中需要访问外存。平均查找长度ASL查找方法时效的度量 为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。 查找成功时的ASL计算方法： n：记录的个数 pi：查找第i个记录的概率， ( 不特别声明时认为等概率 pi =1/n ) ci：找到第i个记录所需的比较次数约定：无特殊说明，一般默认关键字的类型为整型第三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT8.2 顺序表的查找 0 1 n-1 n r0.n a0 a1 an-1 rn.key=K算法描

3、述int seqsearch (int *a, const int n, const int K ) int i = 0; an = K; while (ai != K) i+; return i;第四张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT程序设计技巧 设置监视哨，提高算法效率。性能分析空间：一个辅助空间。时间： 1) 查找成功时的平均查找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/2 2)查找不成功时的平均查找长度 ASLf =n+1算法特点算法简单，对表结构无任何要求n很大=查找效率较低改进措施：非等概率查找时，可将

4、查找概率高的记录尽量排在表前部。第五张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT8.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第六张，PPT共七十页

5、，创作于2022年6月BUPT SCSTBUPT算法描述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; /* 没有查到*/第七张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT性能分析 h=log2n+1 同完全二叉树，二叉树性质4成功查找时

6、的平均查找长度（等概率）： ASLs= 例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找时的查找长度：h-1或h次 -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)；/ 中序遍历右子树 第十九张，PPT

7、共七十页，创作于2022年6月BUPT SCSTBUPT方法2：照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。 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(

8、BTree p)/求右子最小值 if (p=NULL) return maxint； else while(p-lc!=NULL) p=p-lc； return p-data； 第二十张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT在二叉排序树上的操作1.查找例 K=28 K=32bst45241228bst455390241228325390 查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。 在左右子树上的操作类似。第二十一张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT

9、Bitree SearchBST ( BiTree T, KeyType key ) / 在二叉分类树查找关键字之值为 key 的结点，找到返回该结 / 点的地址，否则返回空。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 ); 查找算法第二十二张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT2.插入首先执行查找算法，

10、找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。3.生成算法步骤 反复执行以下操作 a. 读入一个记录，设其关键字为K； b. 调用查找算法，确定插入位置； c. 调用插入算法，实施插入结点的操作；第二十三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT例：将序列122、99、250、110、300、280 作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099第二十四张，PPT共七十页

11、，创作于2022年6月BUPT SCSTBUPT4.删除依据被删除结点p的不同情况分析：1. p是叶子结点：修改其双亲指针即可2. p只有左孩子：用p的左子树代替以p为根的子树 p只有右孩子：用p的右子树代替以p为根的子树3. p有两个孩子：找到p的中序后继(或前趋)结点q， q的数据复制给p， 删除只有右子(或左子)/无孩子的q第二十五张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT例：(1)(2)(2)(3)5320901050869541241528891304539878992第二十六张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTvoid Dele

12、te(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) /被删结点无左子树 if (f-lc=p) f-lc=p-rc;/将被删结点的右子树接到其双亲上 else f-rc=p-rc; else /被删结点有左子树 q=p; s=p-lc; while (s-r

13、c !=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); 第二十七张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT4. 性能分析给定树的形态，等概率查找成功时的ASL=ci /n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2n关键字有序出现时，构造出“退化”的二叉排

14、序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树第二十八张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT8.7 平衡二叉树(AVL树)1. 定义平衡二叉树或者是空树，或者是满足如下性质的二叉排序树： 1)它的左、右子树的高度之差的绝对值不超过1； 2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子： 该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉排序树。第二十九张，PPT共七十页，创作于2022年6月BUP

15、T SCSTBUPT2.结点的存储结构 lc bf key otherinfo rc lc：左孩子指针 rc：右孩子指针 bf：平衡因子 key：记录的关键字 otherinfo：记录的其它数据成分第三十张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT4. 在平衡二叉树上的操作查找查找方法同二叉排序树。插入 插入新结点之后仍应保持平衡二叉树的性质不变。例 平衡二叉树的生成过程15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590第三十一张，PPT共七十页，创作于2022年6月B

16、UPT SCSTBUPT调整范围的确定 插入结点后，找到离插入结点最近且平衡因子绝对值超过1的祖先结点（危机节点），则以该危机节点为根的子树将是可能不平衡的最小子树，可将重新平衡的范围局限于这棵子树。调整的类型 LL型-表示新插入结点在危机结点的左子的左子树上LR型-表示新插入结点在危机结点的左子的右子树上RL型-表示新插入结点在危机结点的右子的左子树上RR型-表示新插入结点在危机结点的右子的右子树上第三十二张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT调整的方法LL型平衡旋转一次顺时针旋转AB+1h-10+2+1hh-1h-1LL 型调整BLBRARBA0h0h-1h-1

17、BLBRAR危机结点调整前：高度为 h + 1 中序序列：ABBLBRAR调整后：高度为 h + 1 中序序列：ABBLBR注意：调整后 平衡因子为 0ABAR第三十三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTLR型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整BLAR危机结点CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CLh-1-10ABBLARCCLCR调整后： 高度为 h + 1 中序序列：ABBLARCCLCRA调整前： 高度为 h + 1 中序序列：h-1情形A注意：调整后 平衡因子为 +1,0,0第

18、三十四张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTLR型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整BLAR危机结点调整前： 高度为 h + 1 中序序列：注意：改组后 平衡度为 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL调整后： 高度为 h + 1 中序序列：AABBLARCCRCL情形B第三十五张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT注意：调整后 平衡因子为 0,0,0LR型平衡旋转一次逆时针旋转+一次顺时针旋转AB+10+2-1

19、LR 型调整危机结点调整前： 高度为 2 中序序列：CBC0ABCA新插入结点ABC调整后： 高度为 2 中序序列：ca0b00情形C第三十六张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTRR型平衡旋转一次逆时针旋转AB-1h-10-2-1hh-1h-1RR 型调整BLBRALBA0h0h-1h-1BLAL危机结点调整前：高度为 h + 1 中序序列：BAALBLBR调整后：高度为 h + 1 中序序列：注意：调整后 平衡因子为 0ABBRBAALBLBR第三十七张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTRL型平衡旋转一次顺时针旋转+一次逆时针旋转A

20、ALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1 h-211(-1)00(1)-1(0)危机结点第三十八张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT删除 （思路同插入）将删除结点q转化为q最多有一个孩子的情形，即若q有两个孩子，则以其中序前驱/后继结点r取代它，删除r；若树的平衡性被破坏，利用单一/双重旋转恢复。性能定理：一个具有n个结点的平衡二叉树形，其高度h为 log2(n+1) h 1.4404log2(n+2)-0.328 结论：最坏情况下，AVL树的高度约为1.44log2n，而完全平衡的二叉树高度约为log2n，因此A

21、VL树是接近最优的，其平均查找长度与log2n同数量级。第三十九张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT8.7 B+树与B-树采用B+与B-树的意义大量数据存放在外存中，由于是海量数据，不可能一次调入内存。因此，要多次访问外存，速度慢。所以，主要矛盾变为减少访外次数。内存第四十张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT用用二叉树组织文件，需访问外存次数太多。如：当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！502510751535609020304055708095索引文件数据文

22、件文件头，可常驻内存文件访问示意图：索引文件存在内存、数据文件存在盘上第四十一张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTB-树B-树是一种平衡的多路查找树。应用于文件系统。1. 定义 一棵 m 阶B -树，或为空树，或为满足下列特性的 m 叉树： 1、树中每个结点最多有 m 棵子树； 2、若根结点不是叶子结点，则最少有两棵子树； 3、除根之外的所有非终端结点最少有 m / 2 棵子树； 4、所有非终端结点包含 （n,A0,K1,A1,K2,Kn,An）信息数据；其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。 5、所有叶子结点在同一层上，且不带信息。第四十

23、二张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT例如：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数至少为 m/2 = 2 个；结点的关键字个数至少为 1 。该 B_ 树的深度为 4。叶子结点都在第 4 层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第 1 层第 2 层第 3 层(L层)第 4 层(L1层)m/2 m棵子树叶第四十三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT2. B-树结点结构(n, A0, K1, A1, K2, A2,., Kn, An)n:

24、关键字的个数A0： K1 且 Kn 的结点的地址（指在该 B_ 树中）K1 =K2 = . = Kn第四十四张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT127阶B-树中每个结点最多有_个关键字；除根结点外所有非终端结点至少有_棵子树；65阶B+树中除根结点外所有结点至少有_个关键字；最多有_棵子树。高度为5（除叶子层之外）的三阶B-树至少有_个结点。31126643365思考：高度为h的m阶B-树（除叶子层）至少有多少个结点？ 第四十五张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT3.B-树查找过程类似于二叉树的查找。如查找关键字为 KEY 的记录。

25、从根开始查找，如果 Ki = KEY 则查找成功。 若 Ki KEY Ki+1; 查找 Ai 指向的结点若 KEY Kn; 查找 An指向的结点若 找到叶子，则查找失败。第四十六张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。层次 结点数关键字的个数（最少） 1 1 1 2 2 2(m/2 -1) 3 2(m/2) 2 (m/2) (m/2 -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/

26、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/2,A m/2, K m/2+1 Km, Am)生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到

27、根结点，树可能长高一层。(K m/2 , p ) 数据项插入上层结点之中PP第四十八张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT例：3 阶 B_ 树的插入key=73，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入第四十九张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT5.B-树删除过程1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直

28、接删除（注意：第 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), (Ki+1, Ai+1), . ） （ A

29、0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1 第 L 层：找到了被删结点的替身。第五十张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT例如：3 阶 B_ 树的删除操作。3244553 90371005061，70被删关键字3244561 90371005370借：向被删结点方向旋转假定再删除该关键字32445 903710061，703，2445 9010061，703，24 45 9010061，70并并并并：和父结点的一个关键字、及兄弟合并。有可能进行到根，使B_ 树的深度降低一层！假定再删除该关键字第五十一张，PPT共七十页，创作于2022年6

30、月BUPT SCSTBUPTB+树B+树是一种B-树的变形树。应用于索引顺序文件系统。1. m阶B+ 树与 B- 树的不同之处1)有 n 棵子树的结点中有 n 个关键字；2)非叶结点可以看成是索引部分 索引集Ai ：第i个子结点的指针Ki ：第i个子结点的最大（或最小）关键字3)所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链接；数据集第五十二张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT结点结构非叶结点 ( A1, K1, .,Ai, Ki, ., An,Kn) 索引集Ai ：第i个子结点的指针Ki ：第i个子结点的最大

31、（或最小）关键字叶结点 全部关键字及指向关键字记录的指针 数据集2 15 334 40 47 58 672 79 853 90 96 1052 85 1323 33 67 852 105 1322 114 1324阶B+树rootsqt第五十三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT2. B+树上的基本运算1)查找方式1：从根结点开始，利用索引集结构，向下查找直到叶子结点方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入 仅在叶子结点上进行，关键字个数大于m则分裂3)删除 也仅在叶子结点上进行，关键字个数小于m/2时，需进行合并第五十四张，PPT共七十页

32、，创作于2022年6月BUPT SCSTBUPT8.8 哈希表哈希表的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。术语 哈希表 一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。 哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。 Loc(ri)=H(keyi) 冲突 对于keyikeyj， i j，出现的H(keyi) = H(keyj)的现象。第五十五张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT 同义词 在同一地址出现冲突的各关键字。 哈希(散列)地址 根据设定的哈希函数H(ke

33、y)和处理冲突的方法确定的记录的存储位置。 装填因子 表中填入的记录数n和哈希表表长 m之比。 =n/m设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数的值域。 2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。 3)设定处理冲突的方法。哈希表bb+(m-1)L第五十六张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT哈希函数的基本构造方法构造原则： 算法简单，运算量小； 均匀分布，减少冲突。1. 直接定址法H(key)=a *key + b a、b为常数e.g: 令：a、b为1，有两个关键字k1, k2 值为

34、10 、1000；选10 、1000 作为存放地址。特点：计算简单，冲突最少。2. 数字分析法/基数转换法取关键字在某种进制下的若干数位作为哈希地址。e.g: key = 236076 基数为10，看成是 13 进制的。则：(236075)13 = 8 4154 7；选取 4154 作为散列地址(假设 表长m =10000)。第五十七张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT3. 平方取中法取关键字平方后的中间几位作为哈希地址。e.g: (4731)2 = 223 82 361 ；选取 82 （假设 m = 100）。4. 随机数法 H(key) = random(ke

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

36、 则 p = 1019。e.g: 选取 p 为质数的理由：设 key 值都为奇数，选 p 为偶数；则 H(key) = key MOD p ，结果为奇数，一半单元被浪费掉。 设 key 值都为 5 的倍数，选 p 为 95；则 H(key) = key MOD p ，结果为：0、5、10、15、 90奇数。4/5 的单元被浪费掉。第五十九张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT处理冲突的常用方法1. 开放定址法 (空缺编址法)Hi = ( H(key)+di ) MOD m 0 H(key) m-1 i=1,2, ., k (km-1) m:哈希表的表长； di:增量

37、序列1)线性探测再散列 di= 1,2, ., m-1缺陷：有聚集(堆积)现象非同义词地址冲突。第六十张，PPT共七十页，创作于2022年6月BUPT SCSTBUPTe.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 = ( H(key)+di) MOD 11其中： di

38、为 1、210冲突： 初级冲突：不同关键字值的结点得到同一个散列地址。 二次聚集：同不同散列地址的结点争夺同一个单元。结果：冲突加剧，最坏时可能达到 O(n)级代价。思考：假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行多少次探测？k(k+1)/2第六十一张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT2)二次探测再散列 di= 12, -12, 22, -22, 32,.,k2 k m/2缺陷：不易探查到整个散列空间。3)伪随机探测再散列 di = 伪随机数序列4) 双重散列函数探查法 di= i*h1(key) 0 i m- 1要求：

39、h1(key)的值与m互素。 m为素数时， h1(key)可取1到m-1之间的任何数，建议：h1(key)=key mod (m-2) +1m为2的方幂时， h1(key)可取1到m-1之间的任何奇数注意：开放定址法不宜执行删除操作第六十二张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT2. 再哈希法Hi = RHi(key) i=1,2, . , k出现冲突时，采用多个 hashing 函数计算散列地址，直到找到空单元为止。如：H1(key) = key MOD 11 H2(key) = (key+ MOD 9) 1 H3(key)= . . H10(key)=.第六十三张，PPT共七十页，创作于2022年6月BUPT SCSTBUPT3. 链地址法为每个哈希地址建立一个单链表，存储所有具有同义词的记录。100123456789K1K2K3K4K5K6同义链，同一散列地址。同义链，同一散列地址。冲突处理简单，无堆积现象，平均查找长度较短；较适合于事先无法确定表长的情况；可取1，当结点信息规模较大时，节省空间删除结点的操作易于实现第六十四张，PPT共七十页，创作于202