第9章-查找lianxi 数据结构

复习最短路径

求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。v2在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：

它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。其余最短路径的特点：再下一条路径长度次短的最短路径的特点:

它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。

它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329课堂练习1试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，列表写出执行算法过程中各步的状态。解答练习2试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，列表写出执行算法过程中各步的状态。15bgdeafc122894510246数据结构第9章查找9.1查找的基本概念9.2

线性表的查找9.3

树表的查找9.4哈希表的查找教学内容1.熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法；2.熟练掌握二叉排序树的构造和查找算法及其性能分析方法；3.掌握二叉排序树的插入算法，了解二叉排序树的删除算法；4.熟练掌握哈希函数（除留余数法）的构造5.熟练掌握哈希函数解决冲突的方法及其特点

教学目标教学目的和要求：了解各种查找算法的思想。掌握各种查找算法的写法。重点和难点：各种查找算法思想。算法的实现及其时间、空间复杂度分析。授课时间：6课时本章将讨论一种在实际中大量使用的数据结构——查找表，它或者基于线性结构构建，或者基于非线性结构构建。查找表的例子：编译程序中的符号表、网络中的路由表、OS中的文件分配表等。几个概念

查找表：用于查找的数据元素集合称为查找表。查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。查找表的操作（1）查询某个“特定的”数据元素是否在查找表中；（2）检索某个“特定的”数据元素的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删去某个数据元素。静态查找表：若对查找表仅作查询和检索操作，则称此类查找表为静态查找表（StaticSearchTable）。动态查找表：若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表（DynamicSearchTable）。关键字：所谓关键字(key)，是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。主关键字：若此关键字能唯一标识一个数据元素，则称此关键字为主关键字（PrimaryKey）。次关键字：能够标识多个记录的关键字，称为次关键字。查找成功：查找表中查找出其关键字等于给定值的数据元素。若表中有这样的元素，则称查找成功查找不成功：查找表中查找出其关键字等于给定值的数据元素。若表中没有这样的元素，则称查找不成功9.1静态查找表9.1静态查找表 表中数据是固定不变的。9.1.1顺序表的顺序查找 以顺序表或链表作为静态查找表，都可以用顺序查找方法来查找元素。我们在这里介绍顺序表的顺序查找。1、一般的顺序查找 思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值表角相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。一般查找算法：#include<iostream>#include<vector>usingnamespacestd;intsearch1(vector<int>v,inte){ inti=v.size()-1;

while(1) { if(i==0)return0; if(v[i]==e)returni; i--; }}2、带“哨兵”的顺序查找intsearch2(vector<int>v,inte){ inti=v.size()-1; v[0]=e;//哨兵

while(1) { if(v[i]==e)returni; i--; }}intSearch_Seq(SSTableST,KeyTypekey){

//若成功返回其位置信息，否则返回0

ST.R[0].key=key;

for(i=ST.length;ST.R[i].key!=key;--i);

//不用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

}比较这两个算法可以发现，循环内插了一条比较语句。市价表明，这个改进能使顺序查找在表长大于1000时，进行一次查找所需的平均时间几乎减少一半。3、性能分析平均查找长度的概念：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。①等概率查找246810查找表：现在有100人对表中数据进行查询：20人查找2，从左向右查找，需要表1次20人查找4，从左向右查找，需要表2次20人查找6，从左向右查找，需要表3次20人查找8，从左向右查找，需要表4次20人查找10，从左向右查找，需要表5次那么这100人共需查找多少次，才能各自找到自己需要的数据？共需：SL=20*1+20*2+20*3+20*4+20*5平均查找次数：ASL=SL/100 =20%*1+20%*2+20%*3+20%*4+20%*5那么其中的百分数可以理解为查找某个元素的概率。所以平均查找长度可以用公式表示为：其中：Pi为查找表中第i个元素的概率Ci为查找表中第i个元素需要比较的次数根据上面式子，等概率查找时，P1=P2=P3=…=Pn=1/n②非等概率查找 如某人有很多人的联系电话，存放在一个顺序表中，他一定会把联系得最频繁的号码放在最前面，以利于查找。空间复杂度：一个辅助空间。时间复杂度：1)查找成功时的平均查找长度设表中各记录查找概率相等

ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功时的平均查找长度ASLf

=n+1顺序查找的性能分析算法简单，对表结构无任何要求（顺序和链式）n很大时查找效率较低改进措施：非等概率查找时，可按照查找概率进行排序。顺序查找算法有特点9.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给的值K的记录；(1)相同，有序n+1;无序n+1（2）查找成功，且表中只有一个关键字等于给定值K的记录；(2)相同，有序(n+1)/2；无序(n+1)/2（3）查找成功，且表中有若干关键字等于给定值K的记录，要求找出所有这些记录。(3)不相同，对于有序表，找到了第一个与K相同的元素后，只要再找到与K不同的元素，即可停止查找；对于无序表，则要一直查找到最后一个元素。9.1.2有序表的查找——折半查找一、折半查找的前提条件必须是顺序表顺序表中元素必须是有序的二、折半查找算法演示1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowmidmid=（low+high）/2=(1+11)/2=6v1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowmidkey=21<v[mid]=56。所以key应该处于区间[low，mid-1]中v1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(1+5)/2=31、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidkey=21>v[mid]=19。所以key应该处于区间[mid+1，high]中1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(4+5)/2=4取不大于小数的整数1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidkey=21==v[mid]=21。查找成功，返回。2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(1+11)/2=62、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85>v[mid]=56。所以key应该处于区间[mid+1,high]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(7+11)/2=92、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85>v[mid]=80。所以key应该处于区间[mid+1,high]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(10+11)/2=102、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85<v[mid]=88。所以key应该处于区间[low,mid-1]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv因为high<low，查找失败3、算法实现intBinSearch(vector<ElemType>ST,ElemTypeelem){ intlow=1; inthigh=ST.size()-1; while(low<high) { intmid=(low+high)/2; if(ST[mid]==elem)returnmid; elseif(ST[mid]>elem)high=mid-1; elselow=mid+1; } return0;}4、算法分析12345678910110513192137566475808892v12345678910110513192137566475808892v5605，13，19，21，3764，75，80，88，924、算法分析12345678910110513192137566475808892v5605，13，64，75，198021，3788，924、算法分析12345678910110513192137566475808892v56198051352137647592884、算法分析如上面演示过程，按照折半查找过程，可以相应的画出一棵二叉树，称为折半查找对应的判定树。所以，折半查找实际上就是其判定树的查找。而每次查找所要比较的次数均不会超过树的高度。结论:对于n个数据（n>50）,进行折半查找时，平均查找长度近似为：-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点内结点><=ASL＝1/11*(1*1＋2×2＋4×3+4*4)＝33/11=3练习:假定每个元素的查找概率相等，求查找成功时的平均查找长度。查找成功时比较次数：为该结点在判定树上的层次数，不超过树的深度d=log2n+1查找不成功的过程就是走了一条从根结点到外部结点的路径d或d-1。-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点内结点><=查找过程：每次将待查记录所在区间缩小一半，比顺序查找效率高,时间复杂度O(log2n)适用条件：采用顺序存储结构的有序表，不宜用于链式结构折半查找的性能分析9.1.4索引顺序表的查找1、索引顺序表思想演示 对于索引的概念，最典型的就是字典。1234567891011121314151617182212138920334244382448605874498653

对于顺序表，如果表中数据分块有序，则可进行索引顺序查找。1234567891011121314151617182212138920334244382448605874498653

如上图，其中的数据总体上可以平均划分成3部分，后面一部分中的数据均比前面一部分中最大数据大1234567891011121314151617182212138920334244382448605874498653

可以为每一块建立一个索引项，包括两个域：一个是该块中最大的关键字的值；一个是该块的起始位置。1234567891011121314151617182212138920334244382448605874498653最大关键字起始地址1234567891011121314151617182212138920334244382448605874498653最大关键字22起始地址11234567891011121314151617182212138920334244382448605874498653最大关键字2248起始地址171234567891011121314151617182212138920334244382448605874498653最大关键字224886起始地址17132、查找方法演示(1)查找381234567891011121314151617182212138920334244382448605874498653最大关键字224886起始地址17131234567891011121314151617182212138920334244382448605874498653最大关键字224886起始地址1713先从索引表中查找，可以采取顺序查找，也可以采取折半查找。发现22<38<48,可以判定38如果存在，就应该在第二块中。根据第二块的起始地址和第三块的起始地址，我们可以确定38的范围[7，13）之间。1234567891011121314151617182212138920334244382448605874498653最大关键字224886起始地址1713在确定的范围内进行顺序查找，如果能找到，则查找成功；否则，查找失败。3、算法分析从总体上可以知道，查找时间可以分为两部分：索引表的查找块的查找假设有n个数据，被均匀的分成b块，则每块有s=n/b个数据那么索引表应该有b项对索引表进行折半查找，近似为在块中进行顺序查找，为：所以，索引顺序表的平均查找长度近似为：静态查找表与动态查找表的根本区别在于

。A)它们的逻辑结构不一样

B)施加于其上的操作不同

C)所包含的数据元素的类型不一样

D)存储实现不一样采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数与对应判定树的的高度（假定高度不小于2）的关系为

。A)前者小于后者

B)前者大于后者

C)前者等于后者

D)前者大于等于后者对线性表进行二分法查找，其前提条件是

。A)线性表以顺序方式存储，并且按关键码值排好序

B)线性表以顺序方式存储，并且按关键码值的检索频率排好序C)线性表以链接方式存储，并且按关键码值排好序

D)线性表以链接方式存储，并且按关键码值的检索频率排好序

设有100个元素，用折半查找法进行查找时，最大比较次数是_____。A.25 B.50 C.10 D.79.2动态查找表

动态查找表的特点是：表结构本身是在查找过程中生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。 动态查找表也可以有不同的表示方法，本节将讨论以各种树结构表示时的实现方法。9.2.1二叉排序树和平衡二叉树

1、二叉排序树及其查找过程

二叉排序树的概念： 二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（3）左、右子树本身又各是一棵二叉排序树。

234578234578两棵二叉排序树

（a）（b）二叉排序树的形态：练习下列图形中，哪个不是二叉排序树？451253337241006190783，12，24，37，45，53，61，78，90，100递增得到一个关键字的递增有序序列练习中序遍历二叉排序树后的结果有什么规律？若查找的关键字等于根结点，成功否则若小于根结点，查其左子树若大于根结点，查其右子树在左右子树上的操作类似12225030011020099105230216二叉排序树的操作－查找（1）若二叉排序树为空，则查找失败，返回空指针。（2）若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：①若key等于T->data.key，则查找成功，返回根结点地址；②若key小于T->data.key，则进一步查找左子树；③若key大于T->data.key，则进一步查找右子树。【算法思想】BSTreeSearchBST(BSTreeT,KeyTypekey){if((!T)||key==T->data.key)returnT; elseif(key<T->data.key)returnSearchBST(T->lchild,key); //在左子树中继续查找

elsereturnSearchBST(T->rchild,key); //在右子树中继续查找}//SearchBST【算法描述】二叉排序树的操作－插入插入的元素一定在叶结点上若二叉排序树为空，则插入结点应为根结点否则，继续在其左、右子树上查找树中已有，不再插入树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子4512533372410061907820插入结点20二叉排序树的操作－插入{10，18，3，8，12，2，7}10101810183101838101838121018381221018381227从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树二叉排序树的操作－生成二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}初始情况下，为空树。45在树中不存在，应该插入。设关键字序列为{45，24，53，45，12，24，90}4524在树中不存在，应该插入，且插入位置为45的左孩子。二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}4553在树中不存在，应该插入，且插入位置为45的右孩子。24二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}4545在树中存在，忽略。2453二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}45245312在树中不存在，应该插入，且插入位置为24的左孩子。二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}4524531224在树中存在，忽略。二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}4524531290在树中不存在，应该插入，且插入位置为53的右孩子。二叉排序树的手工构造过程设关键字序列为{45，24，53，45，12，24，90}45245312完毕！！！90二叉排序树的手工构造过程4524531290中序序列为：12，24，45，53，90中序遍历二叉排序树得到一个关键字的有序序列：不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序树的操作－生成作业3、二叉排序树的删除 怎样从二叉排序树中删除一个结点呢？假设在二叉排序树上被删结点为p，其双亲结点为f，设p是f的左孩子（不失一般性，p是f的右孩子时，方法一样）。下面分3种情况进行讨论：

（1）若p是叶子结点，由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点指向其的指针为空即可。（2）若p结点只有左子树PL或者只有右子树PR，此时只要令PL或者PR直接成为其双亲结点f的左子树即可。（因为前提是p是f的左孩子）

（3）若p结点的左子树和右子树均不空，处理起来有些复杂。可以有两种处理方法，我们结合图来说明。

2023/2/3SQPLP中序遍历：QSPLPSQP中序遍历：QSP(2)SPPLQ中序遍历：PLPSQSPQ中序遍历：PSQ(1)（1）若p是叶子结点，由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点指向其的指针为空即可。（2）若p结点只有左子树PL或者只有右子树PR，此时只要令PL或者PR直接成为其双亲结点f的左子树即可。（因为前提是p是f的左孩子）

（3）若p结点的左子树和右子树均不空，处理起来有些复杂。可以有两种处理方法，我们结合图来说明。

2023/2/3SQPLP中序遍历：QSPLPSQPL中序遍历：QSPL(2)SPPLQ中序遍历：PLPSQSPLQ中序遍历：PLSQ(1)2023/2/3中序遍历：PPRSQSPRQ中序遍历：PRSQ(3)SPPRQ中序遍历：QSPPRSQPR中序遍历：QSPR(4)SQPRP（1）若p是叶子结点，由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点指向其的指针为空即可。（2）若p结点只有左子树PL或者只有右子树PR，此时只要令PL或者PR直接成为其双亲结点f的左子树即可。（因为前提是p是f的左孩子）

（3）若p结点的左子树和右子树均不空，处理起来有些复杂。可以有两种处理方法，我们结合图来说明。

2023/2/3例805012060110150557053删除508060120110150557053删除60805512011015053701032581354删除1083255134删除58325413第一种方式：FPCQSPRCLQLSLfpcqs删除结点p前的二叉树FCQSPRCLQLSLfcqs（a）删除p，以PR作为S的右子树的情形第二种方式FPCQSPRCLQLSLfpcqs删除结点p前的二叉树FSCQPRCLQLfpcqSL（b）删除p，以S替代P的情形4、二叉排序树的查找分析（1）同样的n个关键字，输入顺序不同，构造出的二叉排序树不同。①输入序列为{45，24，53，12，37，93}①输入序列为{45，24，53，12，37，93}45①输入序列为{45，24，53，12，37，93}4524①输入序列为{45，24，53，12，37，93}452453①输入序列为{45，24，53，12，37，93}45245312①输入序列为{45，24，53，12，37，93}4524531237①输入序列为{45，24，53，12，37，93}452453123793②输入序列为{12，24，37，45，53，93}②输入序列为{12，24，37，45，53，93}12②输入序列为{12，24，37，45，53，93}1224②输入序列为{12，24，37，45，53，93}122437②输入序列为{12，24，37，45，53，93}12243745②输入序列为{12，24，37，45，53，93}1224374553②输入序列为{12，24，37，45，53，93}122437455393退化成了单链表结构。第i层结点需比较i次。在等概率的前提下，上述两图的平均查找长度为：40245512371224374055查找的性能分析平均查找长度和二叉树的形态有关，即，最好：log2n（形态匀称，与二分查找的判定树相似）最坏:（n+1)/2（单支树）查找的性能分析40245512371224374055问题：如何提高二叉排序树的查找效率？

尽量让二叉树的形状均衡左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤1平衡二叉树平衡因子:该结点左子树与右子树的高度差任一结点的平衡因子只能取：-1、0或1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。(a)平衡树(b)不平衡树练习：判断下列二叉树是否AVL树？00011-1-120001-15261374一棵平衡二叉树43821756一棵非平衡二叉树（2）平衡化处理①单向右旋平衡化处理：如果在结点p的左孩子的左子树上插入一个新结点而导致p结点失衡的话，那么就需要一个单向右旋的操作。1087ppvoidR_Rotate(Node*&p){Node*LC=p->lchild;p->lchild=LC->rchild;LC->rchild=p;p=LC;}691110876911LC右旋（2）平衡化处理②单向左旋平衡化处理：如果在结点p的右孩子的右子树上插入一个新结点而导致p结点失衡的话，那么就需要一个单向左旋的操作。101213pvoidL_Rotate(Node*&p){Node*RC=p->rchild;p->rchild=RC->lchild;RC->lchild=p;p=RC;}14911RC101213p14911左旋（2）平衡化处理③先左旋后右旋：如果在结点p的左孩子的右子树上插入一个新结点而导致p结点失衡的话，那么就需要一个先左旋后右旋的操作。10118p976左旋10119p68710119p687voidLR_Rotate(Node*&p){L_Rotate(p->lchild);R_Rotate(p);}右旋（2）平衡化处理③先右旋后左旋：如果在结点p的右孩子的左子树上插入一个新结点而导致p结点失衡的话，那么就需要一个先右旋后左旋的操作。101213p14911RC101213p14911右旋左旋101213p14911voidRL_Rotate(Node*&p){R_Rotate(p->rchild);L_Rotate(p);}013037024练习：请将下面序列构成一棵平衡二叉排序树

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053

6、平衡二叉树的查找分析(1)高度为h的平衡二叉树至少有几个结点？N0=0N1=1N2=2N3=4N4=7…Nh=Nh-1+Nh-2+16、平衡二叉树的查找分析(2)含有n个结点的平衡二叉树最大深度为多少？ 由（1）倒着推导。(3)平衡二叉树查找的时间复杂度O（log2n），与树高同一数量级。2023/2/3如：输入关键字序列{16,3,7,11,9,26,18,14,15},给出构造一棵AVL树的步骤。2023/2/37.3哈希表的查找基本思想：记录的存储位置与关键字之间存在对应关系，Loc(i)=H(keyi)

优点：查找速度极快O(1),查找效率与元素个数n无关哈希函数关键字集合存储地址集合hash若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V[01]单元；将2001011810202的所有信息存入V[02]单元；……将2001011810231的所有信息存入V[31]单元。查找2001011810216的信息，可直接访问V[16]！例1数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。…14…11…9…内容地址…39…25242314119232539例2根据哈希函数H（k）＝k

查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，则返回一个特殊值，如空指针或空记录。如何查找…14…11…9…内容地址…39…25242314119232539哈希方法(杂凑法)选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。哈希函数(杂凑函数)：哈希方法中使用的转换函数有关术语冲突：不同的关键码映射到同一个哈希地址哈希表(杂凑表)：按上述思想构造的表有关术语…14…11…9…内容地址…39…25242314119232539同义词：具有相同函数值的两个关键字key1key2，但H(key1)=H(key2)（14，23，39，9，25，11）哈希函数：H(k)=kmod72539239146个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同义词有冲突0123456冲突现象举例冲突是不可能避免的如何减少冲突构造好的哈希函数制定一个好的解决冲突方案哈希函数的构造方法根据元素集合的特性构造地址空间尽量小均匀直接定址法数字分析法平方取中法折叠法除留余数法随机数法Hash(key)=a·key+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空间，空间效率低。直接定址法

例：

{100，300，500，700，800，900}，哈希函数Hash(key)=key/1000123456789900800700500300100直接定址法2023/2/3数字分析法方法：对关键字进行分析，取关键字的若干位或其组合作哈希地址适用于关键字位数比哈希地址位数大，且关键字事先知道的情况例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：位只取8位只取1位只取3、4位只取2、7、5位数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址2023/2/3平方取中法方法：取关键字平方后中间几位作哈希地址适用于不知道全部关键字情况折叠法方法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加Hash(key)=keymodp(p是一个整数)关键：如何选取合适的p？技巧：设表长为m，取p≤m且为质数

除留余数法

（最常用重点掌握）①执行速度（即计算哈希函数所需时间）；②关键字的长度；③哈希表的大小；④关键字的分布情况；⑤查找频率。构造哈希函数考虑的因素1.开放定址法处理冲突的方法2.链地址法基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。1.开放定址法（开地址法）线性探测法二次探测法伪随机探测法Hi=(Hash(key)+di)modm(1≤i<m)

其中：m为哈希表长度

di

为增量序列1，2，…m-1，且di=i一旦冲突，就找下一个空地址存入线性探测法关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11

012345678910477△▲△△291116922283①

47、7、11、16、92没有冲突②Hash(29)=7，有冲突，由H1=(Hash(29)+1)mod11=8，哈希地址8为空，因此将29存入③

3

连续移动了两次线性探测法线性探测法的特点优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率。解决方案：二次探测法二次探测法关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希函数为Hash(key)=keymod11

Hi=(Hash(key)±di)modm其中：m为哈希表长度，m要求是某个4k+3的质数；

di为增量序列

12，-12，22，-22，…，q2

012345678910829716924732211△▲