数据结构 ch09学习.pptx

2023/3/251本章学习导读本章学习导读 查找就是在数据集中找出一个查找就是在数据集中找出一个“特定元素特定元素”。在软件设计中，通。在软件设计中，通常是将待查找的数据元素集按照一定的存储结构存入计算机中，变常是将待查找的数据元素集按照一定的存储结构存入计算机中，变为计算机可处理的数据结构，从而构成一种新的数据结构为计算机可处理的数据结构，从而构成一种新的数据结构查找表查找表。9.1 9.1 基本概念基本概念 本章主要系统地讨论了各种查找方法。主要包括线性表的查找、树表的查找和哈希表的查找以及各种查找的性能分析等。通过本章学习，读者应该熟练掌握以下内容：了解查找及查找表的相关概念掌握各种不同的查找表的查找算法和性能分析 掌握哈希表的各种构造方法、冲突处理和性能分析 第1页/共84页2023/3/252 查找表是记录的集合，每个记录至少包含一个查找表是记录的集合，每个记录至少包含一个关键字关键字。所谓查找就是。所谓查找就是根据给定的关键字值，在查找表中找出一个记录，该记录的关键字值等根据给定的关键字值，在查找表中找出一个记录，该记录的关键字值等于给定的值。于给定的值。若在查找的同时对表做修改运算（如插入和删除），则相应的表称若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为之为动态查找表动态查找表，否则称之为，否则称之为静态查找表静态查找表。由由于于查查找找表表的的范范围围和和给给定定的的关关键键字字值值的的不不同同，查查找找有有两两种种可可能能的的结结果果：一一种种是是找找到到了了相相应应的的记记录录，称称为为查查找找成成功功。通通常常要要求求返返回回该该记记录录的的存存储储位位置置，以以便便对对该该记记录录作作进进一一步步处处理理；一一种种是是找找不不到到相相应应的的记记录录，称称为为查查找失败找失败。此时应返回一个能表示查找失败的值。此时应返回一个能表示查找失败的值。采采用用何何种种查查找找方方法法，取取决决于于使使用用哪哪种种数数据据结结构构来来表表示示“表表”。即即表表中中记记录是按何种方式组织的，根据不同的数据结构采用不同的查找方法。录是按何种方式组织的，根据不同的数据结构采用不同的查找方法。第2页/共84页2023/3/253 查找算法中的基本运算是记录的关键字与给定值所进行的比较。其执行时间通查找算法中的基本运算是记录的关键字与给定值所进行的比较。其执行时间通常取决于关键字的比较次数，也称为常取决于关键字的比较次数，也称为平均查找长度平均查找长度。比较次数的多少就是相应算法。比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。平均查找长度的时间复杂度，它是衡量一个查找算法优劣的重要指标。平均查找长度ASLASL定义为：定义为：n n 是查找表中记录的个数是查找表中记录的个数P Pi i 是查找第是查找第i i个记录的概率个记录的概率C Ci i 是找到第是找到第i i个记录所需进行的比较次数。个记录所需进行的比较次数。第3页/共84页2023/3/2549.2 9.2 顺序表的静态查找顺序表的静态查找定义被查找的顺序表类型定义如下定义被查找的顺序表类型定义如下：#define MAXLEN define MAXLEN typedef structtypedef struct KeyType key;/KeyType KeyType key;/KeyType为关键字的数据类型为关键字的数据类型 infoType data;/infoType data;/其他数据其他数据 SeqList;SeqList;在顺序表中的查找，根据元素之间是否具有递增（减）特性又可分为三种情况：简单顺序查找、二分查找和分块有序查找。各种情况的查找方法及其性能存在较大差异。第4页/共84页2023/3/2559.2.1 9.2.1 简单顺序查找简单顺序查找 基基本本思思想想是是：从从表表的的一一端端开开始始，逐逐个个把把每每条条记记录录的的关关键键字字值值与与给给定定值值k k进进行行比比较较。若若某某个个记记录录关关键键字字值值与与给给定定值值k k相相等等，则则查查找找成成功功，返返回回找找到到的的记记录录位位置置。反反之之，若若已已查查找找到到表表的的另另一一端端，仍仍未未找找到到关关键键字字值值与与给给定定值值相相等等的的记记录录，则则查查找找不不成成功，返回功，返回-1-1。Typedef int KeyType;int SeqSearch(SeqList A,int n,KeyType k)int i;int find=0;for(i=0;in;i+)if(Ai.key=k)find=1;break;return(find?i:-1);第5页/共84页2023/3/256算法分析 从顺序查找过程可见（不考虑越界比较），顺序查找不论给定值k k为何，若第1 1个记录符合给定值，只要比较1 1次。若第n n个记录符合给定值，要比较n n次，即ci=ici=i。若每个记录的查找概率相等，且每次查找都是成功的。则在等概率的情况下，顺序查找的平均查找长度为：查找成功时的平均比较次数约为表长的一半。若k k值不在表中，则须进行n+1n+1次比较之后才能确定查找失败。顺序查找算法的时间复杂性为O(n)O(n)。第6页/共84页2023/3/2579.2.2 9.2.2 二分查找二分查找 二二分分查查找找的的基基本本思思想想是是：首首先先确确定定待待查查记记录录所所在在的的范范围围（区区域域）。假假设设用用变变量量lowlow和和highhigh分分别别表表示示当当前前查查找找区区域域的的首首尾尾下下标标。将将待待查查关关键键字字k k和和该该区区域域的的中中间间元元素素，其其下下标标为为mid=(low+high)mid=(low+high)2 2的的关关键键字字进进行行比比较较。比比较较的结果有如下三种情况：的结果有如下三种情况：（1 1）k=Amid.keyk=Amid.key：查找成功，返回查找成功，返回midmid的值。的值。（2 2）kAmid.keykAmid.keykAmid.key：说说明明元元素素只只可可能能在在右右边边区区域域（下下标标从从mid+1mid+1到到highhigh）。因此应在此区域继续取中间位置记录的关键字进行比较。因此应在此区域继续取中间位置记录的关键字进行比较。第7页/共84页2023/3/258int BinSearch(SeqList A,int n,KeyType k)int low=0,high=n-1,mid;while(lowk)high=mid-1;else low=high+1;return-1;第8页/共84页2023/3/259有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找18的示意图。第9页/共84页2023/3/2510有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找39的示意图。第10页/共84页2023/3/2511算法分析 二分查找算法的计算复杂性可以用二叉树来进行分析。我们把当前查找区间的中间位置上的记录作为根。左子表和右子表中的记录分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树判定树或比较树比较树。具有11个记录的有序表可用右图所示的判定树来表示。树中每个结点表示一个记录，结点的编号为该记录在表中的位置。找到一个记录的过程就是走了一条从根结点到与该记录结点的路径。和给定值进行比较的次数正好是该结点所在的层次数。二分查找在查找成功时和给定值进行比较的关键字的个数至多为log2n+1。同理，查找不成功的过程也是走了一条从根结点到某一个终端结点的路径，其所用的比较次数等于树的深度。第11页/共84页2023/3/2512 在查找概率相同的情况下，Pi=1/nPi=1/n。查找成功的平均查找长度为：二分查找算法比顺序查找算法平均查找长度为 n/2的比较次数少，查找速度快。虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，即使采用高效率的排序方法也要花费O(nlog2n)的时间。另外，二分查找只适用顺序存储结构，不适于线性链表结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。二分查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。第12页/共84页2023/3/25139.2.3 9.2.3 分块查找分块查找 基基本本思思想想是是：首首先先把把表表长长为为n n的的线线性性表表分分成成b b块块，前前b-1b-1块块记记录录个个数数为为s=n/bs=n/b，第第b b块块的的记记录录个个数数小小于于等等于于s s。在在每每一一块块中中，结结点点的的存存放放不不一一定定有有序序，但但块块与与块块之之间间必必须须是是分分块块有有序序的的（假假定定按按结结点点的的关关键键字字值值递递增增有有序序）。即即指指后后一一个个块块中中所所有有记记录录的的关关键键字字值值都都应应比比前前一一个个块块中中所所有有记记录录的的关关键键字字值值大大。为为实实现现分分块块检检索索，还还需需建建立立一一个个索索引引表表。索索引引表表的的每每个个元元素素对对应应一一个个块块，其其中中包包括括该该块块内内最最大大关关键键字字值值和和块块中中第第一个记录位置的地址指针。显然这个索引顺序表是一个递增有序表。一个记录位置的地址指针。显然这个索引顺序表是一个递增有序表。第13页/共84页2023/3/2514 分块有序表的索引存储表示 第14页/共84页2023/3/2515索引表结点的数据类型定义如下：#define MaxIndex typedef struct KeyType key;int link;IdxType;在这种结构下，查找过程要分为两步：首先查找索引表。因为索引表是有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的块中进行顺序查找。第15页/共84页2023/3/2516分块查找算法如下：int IdxSerch(SeqList A,IdxType index,int b,KeyType k,int n)/分块查找关键字为k的记录，索引表为index0.b-1 int low=0,high=b-1,mid,i;int s=n/b;/每块记录个数 while(low=high)/在索引表中进行二分查找，找到的位置放在low中 mid=(low+high)/2;if(indexmid.keyk)low=mid+1 else high=mid-1;if(lowb)/在顺序表中顺序查找 for(i=indexlow.link;i=indexlow.link+s-1&ikey=k)return;/树中已有k，无须插入 f=p;/f保存当前查找的记录 if(p-keyk)p=p-lchild;else p=p-rchild;p=(BsTree*)malloc(sizeof(BsTree);p-key=k;p-lchild=p-rchild=NULL;/创建一个新记录 if(*BST=NULL)*BST=p;/原树为空，新插入的记录为新的根 else if(kkey)f-lchild=p;/原树非空时将*p作为*f的左孩子插入 else f-rchild=p;第21页/共84页2023/3/25222二叉排序树的查找基本思想是：（1）当二叉树为空树时，检索失败。（2）如果二叉排序树根结点的关键字等于待检索的关键字，则检索成功。（3）如果二叉排序树根结点的关键字小于待检索的关键字，则在根结点的右子树中用相同的方法继续检索。（4）如果二叉排序树根结点的关键字大于待检索的关键字，则在根结点的左子树中用相同的方法继续检索。第22页/共84页2023/3/2523非递归算法：BsTree*BstSeareh(BsTree*BST,KeyType k,BsTree*parent)BsTree*p=BST,*q=NULL;/p指向根结点，q指向*p的双亲结点 while(p!=NULL)if(k=p-key)/查找成功 *parent=q;return(p);q=p;if(kkey)p=p-lchild；/在左子树中查找 else p=p-rchild;/在右子树中查找 *parent=q;return(p);/查找失败，返回空 第23页/共84页2023/3/25243二叉排序树的删除 基本思想是：（1）若待删除的结点是叶结点，直接删去该结点。（2）若待删除的结点只有左子树而无右子树。根据二叉排序树的特点，可以直接将其左子树的根结点放在被删结点的位置。（3）若待删除的结点只有右子树而无左子树。与(2)情况类似，可以直接将其右子树的根结点放在被删结点的位置。（4）若待删除的结点同时有左子树和右子树。根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或右子树中选择关键字最小的结点放在被删去结点的位置上。假如选取右子树上关键字最小的结点，那么该结点一定是右子树的最左结点。第24页/共84页2023/3/2525第25页/共84页2023/3/2526第26页/共84页2023/3/2527void DelBstree(BsTree*BST,KeyType k)BsTree*p,*q,*s,*r;q=BstSearch(*BST,k,&p);if(q)/查找成功 if(q-lchild=NULL&q-rchild=NULL)/待删除的是叶子结点 if(p)/待删除结点有双亲 if(p-lchild=q)p-lchild=NULL;else p-rchild=NULL;else*BST=NULL;/原来的树只有一个根结点 /不是叶子结点，且待删除结点的左子树为空 else if(q-lchild=NULL)if(p)if(p-lchild=q)p-lchild=q-rchild;else p-rchild=q-rchild;else*BST=q-rchild;else if(q-rchild=NULL)/待删除结点的右子树为空 用C语言描述的在二叉排序树中删除结点的算法如下：第27页/共84页2023/3/2528 if(p)if(p-lchild=q)p-lchild=q-lchild;else p-rchild=q-lchild;else*BST=q-lchild;else s=q;r=s-rchild;while(r-lchild!=NULL)/找右子树关键字值最小的结点 s=r;r=r-lchild;r-lchild=q-lchild;/把待删除结点的左子树做为*r的左子树 if(q!=s)s-lchild=r-rchild;/把*r的右子树做为其父结点*s的左子树 r-rchild=q-rchild;/把待删除结点的右子树做为*r的右子树 if(p)/待删除结点有父结点 if(p-lchild=q)p-lchild=r;else p-rchild=r;else*BST=r;free(q);第28页/共84页2023/3/2529二叉排序树查找算法分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程。和给定值比较的关键字次数等于路径长度加1 1（或结点所在层次数）。含有n n个结点的二叉排序树并不唯一，其平均查找长度和树的形态有关。例如，（a)图和(b)图是结点数为6 6的两棵二叉排序树。(a)图中树的深度为3 3，而(b)图树的深度为6 6。第29页/共84页2023/3/2530 从平均查找长度分析，假设6 6个记录的查找概率相等，即为1 16 6。则图(a)a)树的平均查找长度为：而图(b)树的平均查找长度为：当表中记录按关键字有序时，构成的二叉排序树蜕变 为 歪 斜 树。树 的 深 度 为 n n，其 平 均 查 找 长 度 为(n+1)/2n+1)/2（和顺序查找相同），这是最差的情况。显然，最好情况下平均查找长度和loglog2 2n n成正比。为了避免出现歪斜树，在构造二叉排序树的过程中需要不断进行平衡处理，使其成为平衡二叉树。第30页/共84页2023/3/25319.3.2 9.3.2 平衡二叉树平衡二叉树 平衡二叉树或是一棵空树，或是具有下列性质的二叉排序树：（1）它的左子树和左子树的深度之差的绝对值不超过1。（2）它的左、右子树都是平衡二叉树。1.平衡二叉树和不平衡二叉树 第31页/共84页2023/3/2532 在算法中，通过平衡因子来具体实现上述平衡二叉树的定义。平衡二叉树中每个结点设有一个平衡因子域，其中存放的是该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子取值均为1、0或-l，则该二叉树称为平衡二叉树。第32页/共84页2023/3/25332平衡二叉树的调整 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。第33页/共84页2023/3/2534（1）LL型平衡旋转法 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。第34页/共84页2023/3/2535（2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。第35页/共84页2023/3/2536（3）LR型平衡旋转法 由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。第36页/共84页2023/3/2537（4）RL型平衡旋转法 由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。第37页/共84页2023/3/2538 例：将一组记录的关键字按4，5，7，2，1，3，6次序进行插入，生成及调整成平衡二叉树的过程。结点旁的数字是该结点的平衡因子。第38页/共84页2023/3/2539第39页/共84页2023/3/2540平衡二叉树上进行查找算法分析平衡二叉树上进行查找算法分析 在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n n个结点的平衡树的最大深度为：因此，在平衡树上进行查找的时间复杂性为O(logn)O(logn)。第40页/共84页2023/3/25419.3.3 B-树 B-树又称为多路平衡查找树。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：（1）根结点或者为叶子，或者至少有两棵子树，至多有m棵子树。（2）除根结点外，所有非终端结点至少有棵子树，至多有m棵子树。（3）所有叶子结点都在树的同一层上。（4）每个结点的结构为：（n，A0，K1，A1，K2，A2，Kn，An）其中，Ki(1in)为关键字，且Kikey0=k;for(i=q-n;kkeyi;i-);if(i0&q-keyi=k)*pos=i;return q;*p=q;/*p为q的双亲结点 q=q-soni;/继续在第i棵子树上查找 return NULL;在B-树root中非递归查找关键字k。成功时函数返回找到的结点的地址第44页/共84页2023/3/25452.B-树的插入插入的过程分两步完成：（1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。（2）判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n ，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。（2）如果被删关键字所在结点的关键字个数n等于 ，说明删去该关键字后该结点将不满足B-树的定义，需要调整。调整过程为：如果其左右兄弟结点中有“多余”的关键字。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。第48页/共84页2023/3/2549 （3）如果左右兄弟结点中没有“多余”的关键字，这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。如果因此使双亲结点中关键字个数小于 ，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。第49页/共84页2023/3/2550在如图（a）所示的3阶B-树中删除75,52,55,30四个关键字 第50页/共84页2023/3/25519.4 9.4 哈希表查找哈希表查找 哈希表又称哈希表又称散列表散列表。哈哈希希表表存存储储的的基基本本思思想想是是：以以数数据据表表中中的的每每个个记记录录的的关关键键字字 k k为为自自变变量量，通通过过一一种种函函数数H(k)H(k)计计算算出出函函数数值值。把把这这个个值值解解释释为为一一块块连连续续存存储储空空间间（即即数数组组空空间间）的的单单元元地地址址（即即下下标标），将将该该记记录录存存储储到到这这个个单单元元中中。在在此此称称该该函函数数H H为为哈哈希希函函数数或或散列函数散列函数。按这种方法建立的表称为。按这种方法建立的表称为哈希表哈希表或或散列表散列表。第51页/共84页2023/3/2552 例如，要将关键字值序列（3 3，1515，2222，2424），存储到编号为0 0到4 4的表长为5 5的哈希表中。计算存储地址的哈希函数可取除5 5的取余数算法H(k)=k%5H(k)=k%5。则构造好的哈希表如图所示。第52页/共84页2023/3/2553 理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同 的 关 键 字 对 应 一 个 存 储 地 址。即 k1k2k1k2，但H(k1)=H(k2H(k1)=H(k2)，这种现象称为冲突冲突。把这种具有不同关键字值而具有相同哈希地址的对象称“同义词同义词”。在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。对于哈希技术，主要研究两个问题：（1 1）如何设计哈希函数以使冲突尽可能少地发生。（2 2）发生冲突后如何解决。第53页/共84页2023/3/2554 构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。1直接定址法 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为：H(k)=k+c (c0)这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。9.4.2 哈希函数的构造方法第54页/共84页2023/3/2555例：统计某地区从1949年到1995年每年出生的人数，列在一张表中。年份为关键字，因共有47年，所以表中位置范围是147。设置H(k)=k-1948即可，其中k为年份数。这样的哈希表示意如下：若要查1970年的出生人数，则根据（1970-1948=22）计算，在表的第22个位置即可找到。第55页/共84页2023/3/25562除留余数法 取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即：H(k)=km 这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m取值为素数（质数）时，冲突可能性相对较少。第56页/共84页2023/3/25573平方取中法 取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。设有一组关键字ABC，BCD,CDE，DEF，其对应的机内码如表所示。假定地址空间的大小为1000，编号为0-999。现按平方取中法构造哈希函数，则可取关键字机内码平方后的中间三位作为存储位置。计算过程如下表所示：第57页/共84页2023/3/25584折叠法 这种方法适合在关键字的位数较多，而地址区间较小的情况。将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址（若超出范围，可再取模）。例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加。即有5355+8101+1046+430=14932，舍去高位。则有H(430104681015355)=4932为该身份证关键字的哈希函数地址。第58页/共84页2023/3/25595数值分析法 若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造出相应的哈希函数。例：对如下一组关键字通过分析可知：每个关键字从左到右的第l，2，3位和第6位取值较集中，不宜作哈希地址。剩余的第4，5，7和8位取值较分散，可根据实际需要取其中的若干位作为哈希地址。第59页/共84页2023/3/2560 若取最后两位作为哈希地址，则哈希地址的集合为下表所示：第60页/共84页2023/3/25619.4.3 冲突的解决方法 假设哈希表的地址范围为0m-l，当对给定的关键字k，由哈希函数H(k)算出的哈希地址为i（0im-1）的位置上已存有记录，这种情况就是冲突现象。处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，则再求下一个，依次类推。直至新的哈希地址不再发生冲突为止。常用的处理冲突的方法有开放地址法、链地址法两大类 第61页/共84页2023/3/25621开放定址法 用开放定址法处理冲突就是当冲突发生时，形成一个地址序列。沿着这个序列逐个探测，直到找出一个“空”的开放地址。将发生冲突的关键字值存放到该地址中去。如 Hi=(H(k)+d（i）)%m,i=1，2，k (km-1)其中H(k)为哈希函数，m为哈希表长，d为增量函数，d(i)=dl，d2dn-l。增量序列的取法不同，可得到不同的开放地址处理冲突探测方法。第62页/共84页2023/3/2563（1）线性探测法 线性探测法是从发生冲突的地址（设为d）开始，依次探查d+l，d+2，m-1（当达到表尾m-1时，又从0开始探查）等地址，直到找到一个空闲位置来存放冲突处的关键字。若整个地址都找遍仍无空地址，则产生溢出。线性探查法的数学递推描述公式为：d0=H(k)di=(di-1+1)%m (1im-1)第63页/共84页2023/3/2564【例】已知哈希表地址区间为0 01010，给定关键字序列（2020，3030，7070，1515，8 8，1212，1818，6363，1919）。哈希函数为H(k)=kH(k)=kllll，采用线性探测法处理冲突，则将以上关键字依次存储到哈希表中。试构造出该哈希表，并求出等概率情况下的平均查找长度。假设数组为A,A,本题中各元素的存放过程如下：H(20)=9H(20)=9，可直接存放到A9A9中去。H(30)=8H(30)=8，可直接存放到A8A8中去。H(70)=4H(70)=4，可直接存放到A4A4中去。H(15)=4H(15)=4，冲突；d0=4d0=4 d1=(4+1)%11=5 d1=(4+1)%11=5，将1515放入到A5A5中。H(8)=8H(8)=8，冲突；d0=8 d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突；d2=(8+2)%11=10 d2=(8+2)%11=10，将8 8放入到A10A10中。第64页/共84页2023/3/2565H(12)=lH(12)=l，可直接存放到A1A1中去。H(18)=7H(18)=7，可直接存放到A7A7中去。H(63)=8H(63)=8，冲突；d0=8 d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突;d2=(8+2)%11=10 d2=(8+2)%11=10，仍冲突;d3=(8+3)%11=0 d3=(8+3)%11=0，将6363放入到A0A0中。H(19)=8H(19)=8，冲突；d0=8 d0=8 d1=(8+1)%11=9 d1=(8+1)%11=9，仍冲突;d2=(8+2)%11=10 d2=(8+2)%11=10，仍冲突;d3=(8+3)%11=0d3=(8+3)%11=0，仍冲突;d4=(8+4)%11=1 d4=(8+4)%11=1，仍冲突;d5=(8+5)%11=2 d5=(8+5)%11=2，将1919放入到A2A2中。第65页/共84页2023/3/2566由此得哈希表如图所示 在等概率情况下成功的平均查找长度为：（1*5+2+3+4+6）/9=20/9 利用线性探查法处理冲突容易造成关键字的“堆积”问题。这是因为当连续n个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发生非同义冲突。造成平均查找长度的增加。为了克服堆积现象的发生，可以用下面的方法替代线性探查法。第66页/共84页2023/3/2567（2）平方探查法 设发生冲突的地址为d，则平方探查法的探查序列为：d+12，d+22，直到找到一个空闲位置为止。平方探查法的数学描述公式为：d0=H(k)di=(d0+i2)%m (1im-1)第67页/共84页2023/3/2568 【例】已知哈希表地址区间为010，给定关键字序列（20，30，70，15，8，12，18，63，19）。哈希函数为H(k)=kll，采用平方探查法处理冲突。【解】H(20)=9，可直接存放到A9中去。H(30)=8，可直接存放到A8中去。H(70)=4，可直接存放到A4中去。H(15)=4，冲突；d0=4 d1=(4+12)%11=5，放到A5中。第68页/共84页2023/3/2569H(8)=8，冲突；d0=8 d1=(8+12)%11=9，仍冲突 d2=(8+22)%11=1 放到A1中。H(12)=l，冲突；d0=1 d1=(1+12)%11=2，放到A2中。H(18)=7，可直接存放到A7中去。第69页/共84页2023/3/2570H(63)=8，冲突；d0=8 d1=(8+12)%11=9，仍冲突 d2=(8+22)%11=1，仍冲突 d3=(8+32)%11=6，放到A6中。H(19)=8，冲突；d0=8 d1=(8+12)%11=9，仍冲突 d2=(8+22)%11=1，仍冲突 d3=(8+32)%11=6，仍冲突 d4=(8+42)%11=2，仍冲突 d5=(8+52)%11=0，放到A0中 第70页/共84页2023/3/2571建立的哈希表如图所示建立的哈希表如图所示：在等概率情况下成功的平均查找长度为：（1*4+2*2+3+4+6）/9=21/9 平方探查法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。例如，若表长m=13，假设在第3个位置发生冲突，则后面探查的位置依次为4、7、12、6、2、0，即可以探查到一半单元。若解决冲突时，探查到一半单元仍找不到一个空闲单元。则表明此哈希表太满，需重新建立哈希表。第71页/共84页2023/3/25722链地址法 用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。第72页/共84页2023/3/2573链地址法查找分析 由于在各链表中的第一个元素的查找长度为l l，第二个元素的查找长度为2 2，依此类推。因此，在等概率情况下成功的平均查找长度为：(1*5+2*2+3*(1*5+2*2+3*l+4*1)l+4*1)9=169=169 9 虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。第73页/共84页2023/3/2574 哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关。第一:与装填因子有关 所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即 =n/m。当 越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。9.4.4 哈希表的查找及性能分析第74页/共84页2023/3/2575第二:与所构造的哈希函数有关 若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生。否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。第三:与解决冲突的哈希冲突函数有关 哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。第75页/共84页2023/3/25769.4.5 有关哈希表的算法 1基于开放地址法的哈希表的建立#define NIL-1#define M 997 /表长度typedef int KeyType;typedef struct node /哈希表结点类型KeyType key;/其他数据域HashType;用除余法求K的哈希地址的函数h int h(KeyType K)return K%M;第76页/共84页2023/3/2577Increment是求增量序列的函数,它依赖于解决冲突的方法int Increment(int i)/用线性探查法求第i个增量di return i;求在哈希表T0.M-1中第i次探查的哈希地址hi，0iM-1int Hash(KeyType k,int i)return(h(k)+Increment(i)%M;在哈希表T0.M-1中查找K,成功时返回1。失败有两种情况：找到一个开放址时返回0;表满未找到时返回-1int HashSearch(HashType T,KeyType K,int*pos)int i=0;/记录探查次数 do*pos=Hash(K,i);/求探查地址hi if(T*pos.key=K)return 1;if(T*pos.key=NIL)return 0;/查找到空结点返回 while(+i0)printf(重复的关键字!