《数据结构-C语言版：DS08-查找》由会员分享，可在线阅读，更多相关《数据结构-C语言版：DS08-查找（99页珍藏版）》请在金锄头文库上搜索。
1、 第 八 章 查 找 基本概念基本概念线性表的查找线性表的查找 树表的查找树表的查找 散列散列( (Hash)Hash)技术技术 第八章第八章 查找查找 第 八 章 查 找 8.18.1查找的基本概念查找的基本概念 查找（查找（查找（查找（SearchingSearchingSearchingSearching）的定义是：在含有的定义是：在含有的定义是：在含有的定义是：在含有n n n n条条条条记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定值值值值K K K K的记录。若找到，则查找成功，返回的
2、记录。若找到，则查找成功，返回的记录。若找到，则查找成功，返回的记录。若找到，则查找成功，返回该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信息。息。息。息。 第 八 章 查 找 若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除
3、等），则相应的表称之为，则相应的表称之为，则相应的表称之为，则相应的表称之为动态查找表动态查找表动态查找表动态查找表（DynamicDynamicSearchTableSearchTable）。）。）。）。否则称之为否则称之为否则称之为否则称之为静态查找表静态查找表静态查找表静态查找表( (StaticSearchTable)StaticSearchTable)。若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为内查找内查找内查找内查找；反之，若查找过程中需要访问外存，则称之为反之，若查找过程中需要访
4、问外存，则称之为反之，若查找过程中需要访问外存，则称之为反之，若查找过程中需要访问外存，则称之为外外外外查找查找查找查找查找表的数据结构表示查找表的数据结构表示 第 八 章 查 找 如何分析算法优劣？如何分析算法优劣？主要分析算主要分析算法运算时所需要的时间和其存储结构法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法，占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，次数，所以本章经常用平均比较次数，即即平均查找长度平均查找长度 ASLASL（Average Average Search Length
5、Search Length） 第 八 章 查 找 其中：其中：其中：其中：1 1 1 1、n n n n是结点的个数；是结点的个数；是结点的个数；是结点的个数；2 2 2 2、P P P Pi i i i是查找第是查找第是查找第是查找第i i i i个结点的概率。若不特个结点的概率。若不特个结点的概率。若不特个结点的概率。若不特别声明别声明别声明别声明 ，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即 p p p pl l l l = p = p = p = p2 2 2 2 = = = = p p p pn n
6、n n = = = = 1/n1/n1/n1/n3333、c c c ci i i i是找到第是找到第是找到第是找到第i i i i个结点所需进行的比较个结点所需进行的比较个结点所需进行的比较个结点所需进行的比较次数次数次数次数ASL=ASL= 平均查找长度平均查找长度平均查找长度平均查找长度 ASLASLASLASL（Average Search LengthAverage Search LengthAverage Search LengthAverage Search Length）定义为定义为定义为定义为 ： 第 八 章 查 找 一、顺序查找一、顺序查找一、顺序查找一、顺序查找( (Se
7、quentialSearch)SequentialSearch)基本思想是：从表的一端开始，顺序基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关扫描线性表，依次将扫描到的结点关键字和给定值键字和给定值K K相比较。若当前扫描到相比较。若当前扫描到的结点关键字与的结点关键字与K K相等，则查找成功；相等，则查找成功；若扫描结束后，仍未找到关键字等于若扫描结束后，仍未找到关键字等于K K的结点，则查找失败。的结点，则查找失败。8.2线性表的查找线性表的查找 第 八 章 查 找 基于顺序结构的顺序查找算法基于顺序结构的顺序查找算法 类型说明类型说明类型说明类型说明 typedefty
8、pedeftypedeftypedef structstructstructstruct KeyTypeKeyTypeKeyTypeKeyType key key key key； /*/*/*/*KeyTypeKeyTypeKeyTypeKeyType由用户定义由用户定义由用户定义由用户定义* * * */ / / / InfoTypeInfoTypeInfoTypeInfoType otherinfootherinfootherinfootherinfo； /*/*/*/*此类型依赖于应用此类型依赖于应用此类型依赖于应用此类型依赖于应用* * * */ / / / NodeTypeNode
9、TypeNodeTypeNodeType； typedeftypedeftypedeftypedef NodeTypeNodeTypeNodeTypeNodeType Seqlistn+1 Seqlistn+1 Seqlistn+1 Seqlistn+1； /*/*/*/*多出多出多出多出0 0 0 0号单元用作监视哨号单元用作监视哨号单元用作监视哨号单元用作监视哨* * * */ / / / 第 八 章 查 找 具体算法具体算法具体算法具体算法 intintintint SeqSearchSeqSearchSeqSearchSeqSearch( ( ( (SeqlistSeqlistSeql
10、istSeqlist R R R R，KeyTypeKeyTypeKeyTypeKeyType K) K) K) K) /*/*/*/*在顺序表在顺序表在顺序表在顺序表R1.nR1.nR1.nR1.n中顺序查找关键字为中顺序查找关键字为中顺序查找关键字为中顺序查找关键字为K K K K的结点，的结点，的结点，的结点，* * * */ / / / /* /* /* /*成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回0*/0*/0*/0*/ intintintint i i i i； R0.key=K
11、R0.key=KR0.key=KR0.key=K； /*/*/*/*设置监视哨设置监视哨设置监视哨设置监视哨* * * */ / / / for(i=nfor(i=nfor(i=nfor(i=n；Ri.key!=K;i-)Ri.key!=K;i-)Ri.key!=K;i-)Ri.key!=K;i-)；/*/*/*/*从表后往从表后往从表后往从表后往前找前找前找前找* * * */ / / / return ireturn ireturn ireturn i； /*/*/*/*若若若若i i i i为为为为0 0 0 0，表示查找失败，否则，表示查找失败，否则，表示查找失败，否则，表示查找失败，
12、否则RiRiRiRi为要为要为要为要找的结点找的结点找的结点找的结点* * * */ / / / /*/*/*/*SeqSearchSeqSearchSeqSearchSeqSearch*/*/*/*/ 第 八 章 查 找 算法分析算法分析查找查找查找查找成功时的成功时的成功时的成功时的顺序查找顺序查找顺序查找顺序查找的平均查找长度：的平均查找长度：的平均查找长度：的平均查找长度： 在等概率情况下，在等概率情况下，在等概率情况下，在等概率情况下，p p p pi i i i=1/n(1in)=1/n(1in)=1/n(1in)=1/n(1in)，故成功的故成功的故成功的故成功的平均查找长度为平
13、均查找长度为平均查找长度为平均查找长度为 ASL= ASL= ASL= ASL= =(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。 第 八 章 查 找 顺序查找的缺点顺序查找的缺点顺序查找的缺点顺序查找的缺点 查找效率低。查找效率低。查找效率低。查找效率低。顺序查找的优点顺序查找的优点顺序查找的优点顺序查找的优点算法简单，且对表的结构
14、无任何要求，无算法简单，且对表的结构无任何要求，无算法简单，且对表的结构无任何要求，无算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样适用。适用。适用。适用。 第 八 章 查 找 n n二分查找二分查找二分查找二分查找又称又称又称又称折半查找折半查找折半查找折半查找，它是一种效率较高的查，它是一种效率较高的查，它是一种效率
15、较高的查，它是一种效率较高的查找方法。找方法。找方法。找方法。n n二分查找要求二分查找要求二分查找要求二分查找要求：要求线性表是：要求线性表是：要求线性表是：要求线性表是有序表有序表有序表有序表，即表中结，即表中结，即表中结，即表中结点按关键字有序，并且要用点按关键字有序，并且要用点按关键字有序，并且要用点按关键字有序，并且要用向量作为表的存储结向量作为表的存储结向量作为表的存储结向量作为表的存储结构构构构。不妨设有序表是递增有序的。不妨设有序表是递增有序的。不妨设有序表是递增有序的。不妨设有序表是递增有序的。二、二分查找二、二分查找 第 八 章 查 找 （1 1）首先确定该区间的中点位置）
16、首先确定该区间的中点位置）首先确定该区间的中点位置）首先确定该区间的中点位置mid=（2 2）然后将中间位置记录的键值然后将中间位置记录的键值然后将中间位置记录的键值然后将中间位置记录的键值Rmid.keyRmid.key和所给关键字和所给关键字和所给关键字和所给关键字K K进行比较：若相等，则查找成进行比较：若相等，则查找成进行比较：若相等，则查找成进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，功并返回此位置，否则须确定新的查找区间，功并返回此位置，否则须确定新的查找区间，功并返回此位置，否则须确定新的查找区间，继续二分查找。继续二分查找。继续二分查找。继续二分查找。二分
17、查找的基本思想是：二分查找的基本思想是：二分查找的基本思想是：二分查找的基本思想是： 第 八 章 查 找 例：设算法的输入实例中有序的关键字序列例：设算法的输入实例中有序的关键字序列为：为：05，13，19，21，37，56，64，75，80，88，92。查找的关键字。查找的关键字K=21第一步：这里的n=11,mid=(1+11)/2=605，13，19，21，37，56，64，75，80，88，92 第 八 章 查 找 第二步：mid=(1+5)/2=305，13，19，21，37，56，64，75，80，88，92第三步：mid=(4+5)/2=405，13，19，21，37，56，64
18、，75，80，88，92此时Rmid.keyK，returnmid4。 第 八 章 查 找 二分查找算法二分查找算法二分查找算法二分查找算法intint BinSearchBinSearch( (SeqListSeqListRR，KeyTypeKeyType KK) )intintlow=1low=1，high=nhigh=n，midmid；while(low=high)while(lowif(Rmid.keyKK) )high=mid-1;high=mid-1;elseelselow=mid+1low=mid+1； return0return0；确定新的查找区间确定新的查找区间 第 八 章
19、查 找 二分查找过程可用二叉树来描述：把当二分查找过程可用二叉树来描述：把当二分查找过程可用二叉树来描述：把当二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，前查找区间的中间位置上的结点作为根，前查找区间的中间位置上的结点作为根，前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子表和右子表中的结点分别作为根的左子表和右子表中的结点分别作为根的左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，左子树和右子树。由此得到的二叉树，左子树和右子树。由此得到的二叉树，左子树和右子树。由此得到的二叉树，称为描述二分查找的称为描述二分查找的称为
20、描述二分查找的称为描述二分查找的判定树判定树判定树判定树( ( ( (Decision Decision Decision Decision Tree)Tree)Tree)Tree)或或或或比较树比较树比较树比较树( ( ( (Comparison Tree)Comparison Tree)Comparison Tree)Comparison Tree)。二分查找判定树二分查找判定树 第 八 章 查 找 二分查找判定树的组成二分查找判定树的组成如对表如对表R3，7，11，19，30，115，136，141的查找过程：的查找过程：371119301151361413711193011513614
21、1Low mid highLow mid high46782135 第 八 章 查 找 如如k=115k=115的的记记录录结结点点编编号号为为6 6，处处于于第第二二层层，则则比比较较次次数数只只有有两两次次就就可可找找到到（这这样样的的记记录录共共有有两两个个2 21 1=2=2）；查查找找第第三三层层的的记记录录需需要要三三次次比比较较（这这样样的的记记录录共共有有四四个个2 22 2=4 =4 ）；查查找找第第k k层层的的记记录录需需要要k k次次比比较较（这这样样的的记记录录共共有有2 2k-1k-1个个）; ;等等等等。假假定定每每个个记记录录的的查查找找概概率率相相等等，即即为
22、为1/1/n n，则其平均查找次数为：则其平均查找次数为：ASL= =1/n ASL= =1/n ASL= =1/n ASL= =1/n c c c ci i i i=1/n(1*2=1/n(1*2=1/n(1*2=1/n(1*20 0 0 0+2*2+2*2+2*2+2*21 1 1 1+3*2+3*2+3*2+3*22 2 2 2+ + + +k*2+k*2+k*2+k*2k-1k-1k-1k-1+ + + +) ) ) )= 1/n i*2= 1/n i*2= 1/n i*2= 1/n i*2i-1 ; i-1 ; i-1 ; i-1 ; 而而而而 i*2i*2i*2i*2i-1 i-1
23、 i-1 i-1 =k2=k2=k2=k2k k k k-2-2-2-2k k k k-1 -1 -1 -1 k又又根据二叉树的性质：根据二叉树的性质：k=log2(n+1)故：故：ASL=ASL=ASL=ASL=（n+1n+1n+1n+1）/nlog/nlog/nlog/nlog2 2 2 2(n+1)-1(n+1)-1(n+1)-1(n+1)-1 log log log log2 2 2 2(n) (n) (n) (n) 当当当当n n n n很大时很大时很大时很大时 第 八 章 查 找 二分查找的平均查找长度二分查找的平均查找长度n二分查找成功时的平均查找长度为：二分查找成功时的平均查找
24、长度为： ASLASLbnbnloglog2 2(n) (n) n二分查找在查找失败时所需比较的关二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超坏情况下查找成功的比较次数也不超过判定树的深度。即为：过判定树的深度。即为： 第 八 章 查 找 二分查找的优点和缺点二分查找的优点和缺点 虽然二分查找的效率高，但是要虽然二分查找的效率高，但是要将表按关键字排序（有序表）。将表按关键字排序（有序表）。 二分查找二分查找只适用顺序存储结构只适用顺序存储结构。为保持表的有序性，在顺序结构里为保持表的有序性，在顺序结构里插入和
25、删除都必须移动大量的结点。插入和删除都必须移动大量的结点。 第 八 章 查 找 三、分块查找三、分块查找（索引顺序查找索引顺序查找） 分块分块查找表查找表存储结构存储结构 分块分块查找的特点是：按表内记录的某种查找的特点是：按表内记录的某种属性把表（文件）分成属性把表（文件）分成b b个块（子表），个块（子表），并建立一个相应的并建立一个相应的“索引表索引表”，索引表，索引表中每个元素对应一个块，而在索引表中中每个元素对应一个块，而在索引表中是按其关键字有序，但是每一块中的记是按其关键字有序，但是每一块中的记录的存放是任意的，块与块之间必须是录的存放是任意的，块与块之间必须是有序的。即有序的。
26、即分块查找的前提是：分块查找的前提是：文件由文件由 分块有序分块有序 的线性表和索引表组成的线性表和索引表组成。 第 八 章 查 找 分块查找表由分块查找表由 分块有序分块有序 的线性表和索引表组成。的线性表和索引表组成。（1 1） 分块有序分块有序 的线性表的线性表将表（文件）将表（文件）R1.nR1.n平均分为平均分为b b块；块；每一块中的关键字不每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是小关键字，即表是 分块有序分块有序 的。的。（2 2）索引表）索引表抽取各块中的抽取各块中的最大关键字及其
27、起始位置最大关键字及其起始位置构成一个索引表构成一个索引表IDl.bIDl.b，即：即：IDi(1ib)IDi(1ib)中存放第中存放第i i块的最大关键字块的最大关键字及该块在表及该块在表R R中的起始位置。由于表中的起始位置。由于表R R是分块有序的，所以索是分块有序的，所以索引表是一个递增有序表。引表是一个递增有序表。1 1、分块查找表的存储结构、分块查找表的存储结构 第 八 章 查 找 分块查找的基本思想是：分块查找的基本思想是：（1 1）首先查找索引表）首先查找索引表索索引引表表是是有有序序表表，可可采采用用二二分分查查找找或或顺顺序序查查找找，以确定待查的结点在哪一块。以确定待查的
28、结点在哪一块。 （2 2）然后在已确定的块中进行顺序查找）然后在已确定的块中进行顺序查找 由由于于块块内内无无序序（也也可可有有序序），只只能能用用顺顺序查找。序查找。2 2、分块查找的基本思想、分块查找的基本思想 第 八 章 查 找 例例：图图8.2所示的表及其索引表是满足上述要求的分块查所示的表及其索引表是满足上述要求的分块查找表，其中找表，其中R只有只有18个结点，被分成个结点，被分成3块，每块中有块，每块中有6个结个结点，第一块中最大关键字点，第一块中最大关键字22小于第二块中最小关键字小于第二块中最小关键字24，第二块中最大关键字第二块中最大关键字48小于第三块中最小关键字小于第三块
29、中最小关键字49。 22488617132212138920334244382448605874498653ID块内块内最大键值最大键值块内第一个元素序号块内第一个元素序号 第 八 章 查 找 （1 1）先先在在索索引引表表中中查查找找,来来确确定定关关键键字字等等于于给给定定值值K=24K=24的的结点所在的块结点所在的块因因为为索索引引表表小小，不不妨妨用用顺顺序序查查找找方方法法查查找找索索引引表表。即即首首先先将将K K依依次次和和索索引引表表中中各各关关键键字字比比较较，直直到到找找到到第第1 1个个关关键键字字大大小小等等于于K K的的结结点点，由由于于K48K48，所所以以关关键
30、键字字为为2424的的结结点点 若若 存存 在在 的的 话话 ， 则则 必必 定定 在在 第第 二二 块块 中中 ； 然然 后后 ， 由由ID2.addrID2.addr找找到到第第二二块块的的起起始始地地址址7 7，从从该该地地址址开开始始在在R R7.12中进行顺序查找，直到中进行顺序查找，直到R11.key=K为止。为止。（2）在所确定的块内查找关键字等于给定值）在所确定的块内查找关键字等于给定值K=30的结点的结点在在第第二二块块内内查查找找。因因在在该该块块中中查查找找不不成成功功，故故说说明明表表中中不存在关键字为不存在关键字为30的结点。的结点。进行下列查找：进行下列查找： 第
31、八 章 查 找 算法分析算法分析 分块查找是两次查找过程。整个查找过程分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长的平均查找长度是两次查找的平均查找长度之和。度之和。 以二分查找来确定块，分块查找成功时以二分查找来确定块，分块查找成功时的平均查找长度的平均查找长度( (在索引表中用二分查找，在块内用顺序查找在索引表中用二分查找，在块内用顺序查找) ) ASLASLblkblk= ASL= ASLbnbn+ASL+ASLsqsqloglog2 2(b+1)-(b+1)-1+(s+1)/2log1+(s+1)/2log2 2(n/s+1)+s/2(n/s+1)+s/2
32、以顺序查找确定块，分块查找成功时的以顺序查找确定块，分块查找成功时的平均查找长度平均查找长度 ASLASLblkblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s) 第 八 章 查 找 在表中插入或删除一个记录时，在表中插入或删除一个记录时，只要找到该记录所属的块，就在该只要找到该记录所属的块，就在该块内进行插入和删除运算。块内进行插入和删除运算。 因块内记录的存放是任意的，所因块内记录的存放是任意的，所以插入或删除比较容易，无须移动以插入或删除比较容易，无须移动大量记录。大量记录。 分块查找的优点分块查找的优点 第
33、 八 章 查 找 8.3 8.3 树表的查找树表的查找1 1、二叉排序树的、二叉排序树的定义定义 二叉排序树二叉排序树( (Binary Sort Tree)Binary Sort Tree)又称又称二叉查找二叉查找( (搜搜索索) )树树( (Binary Search Tree)Binary Search Tree)。其定义为：二叉排其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：序树或者是空树，或者是满足如下性质的二叉树：（1 1）若它的左子树非空，则左子树上所有结点的值）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；均小于根结点的值；（2 2）若它的右子树非空，
34、则右子树上所有结点的值）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；均大于根结点的值；（3 3）左、右子树本身又各是一棵二叉排序树）左、右子树本身又各是一棵二叉排序树。 第 八 章 查 找 （1 1） 二叉排序树中任一结点二叉排序树中任一结点x x，其左其左( (右右) )子树中任一结点子树中任一结点y(y(若存在若存在) )的关键字必的关键字必小小( (大大) )于于x x的关键字。的关键字。（2 2） 二叉排序树中，各结点关键字是惟二叉排序树中，各结点关键字是惟一的。一的。（3 3） 按中序遍历该树所得到的中序序列按中序遍历该树所得到的中序序列是一个递增有序序列。是一个递增有
35、序序列。二叉排序树的特点二叉排序树的特点 第 八 章 查 找 要查找键值等于要查找键值等于k的记录，最先与的记录，最先与根根结点的键值比较，若二者相等，则结点的键值比较，若二者相等，则查找成功查找成功。若。若k值值小于小于根结点的键值，根结点的键值，则继续查找则继续查找左左子树，反之查找右子树。子树，反之查找右子树。若沿某条路经碰到一个端点若沿某条路经碰到一个端点（叶子）（叶子）还末查还末查到，则查找不成功，这也是静态表的到，则查找不成功，这也是静态表的查找。查找。二叉排序树的查找算法：二叉排序树的查找算法： 第 八 章 查 找 二叉排序树的存储结构二叉排序树的存储结构typedeftyped
36、ef intint KeyTypeKeyType； typedeftypedef structstruct node node KeyTypeKeyType key key； /*/*关键字类型关键字类型* */ / infoTypeinfoType otherinfootherinfo； /*/*结点其它信息类型结点其它信息类型* */ / structstruct node * node *lchildlchild，* *rchildrchild； BSTNodeBSTNode； /*/*二叉排序树的结点类型二叉排序树的结点类型* */ /typedeftypedef BSTNodeBST
37、Node * *BSTreeBSTree； lchildlchildkeykey otherinfootherinfo rchildrchild 第 八 章 查 找 在二叉排序树中插入新结点，要保证插入后仍满足在二叉排序树中插入新结点，要保证插入后仍满足BSTBST性质。其性质。其插入过程是：插入过程是： 1)1)若二叉排序树若二叉排序树T T为空，则为待插入的关键字为空，则为待插入的关键字keykey申请一个新结点，并令其为根；申请一个新结点，并令其为根； 2)2)若二叉排序树若二叉排序树T T不为空，则将不为空，则将keykey和根的关键字和根的关键字比较：比较：( (a)a)若二者相等，
38、则说明树中已有此关键字若二者相等，则说明树中已有此关键字keykey，无无须插入。须插入。( (b)b)若若keyTkeykeyTkeykeyTkey，则将它插入根的右子树中。则将它插入根的右子树中。 二叉排序树插入新结点的过程二叉排序树插入新结点的过程 第 八 章 查 找 二叉排序树插入新结点的算法二叉排序树插入新结点的算法voidInsertBST(BSTreeTptr，Keytypekey)BSTNode*f，*p=Tptr；while(p)/*p不空不空*/if(p-key=key)return；/*找到了，则不插入找到了，则不插入*/f=p；/*f是是p的的双亲双亲*/p=(keyk
39、ey)?p-lchild:p-rchild; 第 八 章 查 找 p=(BSTNode*)malloc(sizeof(BSTNode)；p-key=key；p-lchild=p-rchild=NULL；if(TPtr=NULL)/*是空树是空树*/Tptr=p；/*新结点作为根插入新结点作为根插入*/else/*不是空树不是空树*/if(keykey)f-lchild=p；/*新结点作为左孩子插入新结点作为左孩子插入*/elsef-rchild=p；/*新结点作为右孩子插入新结点作为右孩子插入*/ 第 八 章 查 找 从空的二叉排序树开始，每输从空的二叉排序树开始，每输入一个结点数据，就调用一
40、次入一个结点数据，就调用一次插入算法将它插入到当前已生插入算法将它插入到当前已生成的二叉排序树中。成的二叉排序树中。 二叉排序树的生成二叉排序树的生成 第 八 章 查 找 BSTreeCreateBST(void)BSTreeT=NULL；KeyTypekey；scanf(“d”，&key)；/*输入一个键值为输入一个键值为key的结点的结点*/while(key)InsertBST(&T，key)；/*将键值为将键值为key的结点插入到二叉树中的结点插入到二叉树中*/scanf(d，&key)；/*输入一个键值为输入一个键值为key的结点的结点*/returnT； 第 八 章 查 找 输入实
41、例输入实例(5(5，3 3，7 7，2 2，4 4，8)8)，根据生成二叉排，根据生成二叉排序树算法序树算法生成二叉排序树的过程生成二叉排序树的过程 553253753725374253748 第 八 章 查 找 二叉排序树的删除二叉排序树的删除 从二叉排序树中删除一个结点，从二叉排序树中删除一个结点，不能把以该结点为根的子树都删不能把以该结点为根的子树都删去，并且还要保证删除后所得的去，并且还要保证删除后所得的二叉树仍然满足二叉树仍然满足BSTBST性质。性质。 第 八 章 查 找 回顾：二叉排序树的特点二叉排序树的特点1.1.若它的左子若它的左子树非空，非空，则左左子子树上所有上所有结点的
42、点的值均均小于根小于根结点的点的值；2.2.若它的右子若它的右子树非空，非空，则右右子子树上所有上所有结点的点的值均均大于根大于根结点的点的值；3.3.按中序遍历该树所得到的按中序遍历该树所得到的中序序列是一个递增有中序序列是一个递增有序序列。序序列。805012060110150557053中序遍历（LVR）：50，53，55，60，70，80，110，120，150 第 八 章 查 找 二叉排序树的删除二叉排序树的删除 删除操作的一般步骤删除操作的一般步骤: :1. 1. 查找要删的结点查找要删的结点 查找时，令工作指针查找时，令工作指针p p指向当前访问指向当前访问到的结点，到的结点，p
43、arentparent指向指向p p的双亲的双亲( (其初其初值为值为NULL)NULL)。若树中找不到被删结点若树中找不到被删结点则返回，否则被删结点是则返回，否则被删结点是* *p p。2.2.如果找到删除结点如果找到删除结点* *p p 应将应将* *p p的子树的子树( (若有若有) )仍连接在树上且仍连接在树上且保持保持二叉排序树的性质不变性质不变FPCPRCLQQLSLS坚持的基本原则：坚持的基本原则：删结点时，保证二叉排序树的性质不变。 第 八 章 查 找 想：想：从一棵二叉排序树中删除一个从一棵二叉排序树中删除一个结点会出现哪几种情况？结点会出现哪几种情况？分析：分析：要删除二
44、叉排序树中的要删除二叉排序树中的* *p p结结点，分三种情况：点，分三种情况：q*p p是叶子是叶子 q*p p只有一个子树只有一个子树FPCPRCLQQLSLS注意：注意：此时有四种情况（此时有四种情况（* *p p本身本身可以为左、右子树，且可以为左、右子树，且* *p p的子树的子树也可以为左、右子树）也可以为左、右子树）*p p有两个子树有两个子树 第 八 章 查 找 1 1* *p p只有左子树，只有左子树，用用* *p p的左子树的的左子树的根代替根代替* *p pSQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ
45、中序遍历：PL S Q(1)if(!p-rchild)/右子树空则只需重接它的左子树 tmp=p; p=p-lchild ; free(tmp);* *p p只有一个子树的情况只有一个子树的情况： 第 八 章 查 找 中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP2.2.* *p p只有右子树，用只有右子树，用* *p p的右子树的根代替的右子树的根代替* *p pif(!p-lchild)/左子树空则只需重接它的右子树 tmp=p; p=p-rchild ; free(tmp); 第 八 章 查
46、 找 * *p p有两个子树的情况：有两个子树的情况：分析分析：针对针对* *p p有两个子树的情有两个子树的情况，把况，把* *p p的两个子树合并为的两个子树合并为一棵树，然后将其连接到一棵树，然后将其连接到* *p p的双亲上。的双亲上。 1.1.删除问题就转化为删除问题就转化为第第种情种情况况。 2.2.要解决的问题转化为要解决的问题转化为如何将如何将两棵二叉排序树合并为一棵二叉两棵二叉排序树合并为一棵二叉排序树排序树。FPCPRCLQQLSLS 第 八 章 查 找 问题：问题：如何将两棵二叉排序树合并为一棵二叉排序树如何将两棵二叉排序树合并为一棵二叉排序树? ?思考思考：还有没有其它
47、的合并方法？SFPCPRCLQQLSLFPCPRCLQQLSLS分析：分析：据二叉排序据二叉排序树的性的性质：右子：右子树的的值大于左大于左子子树的的值。因此，只要找到左子。因此，只要找到左子树中中值最大的最大的结点点（左子（左子树中最右中最右边的的结点，点，该结点一定没有右子点一定没有右子树），使其成使其成为右子右子树的双的双亲。 第 八 章 查 找 SFPCPRCLQQLSLFPCPRCLQQLSLStmp=p-lchild;/1.要删除结点的左子树要删除结点的左子树while(tmp-rchild!=0)tmp=tmp-rchild;/2.找到左子树中最右边的结找到左子树中最右边的结/点
48、，即最大的结点点，即最大的结点tmp-rchild=p-rchild;/3.左子树中最右边的左子树中最右边的成为右成为右/子树的双亲子树的双亲tmp=p;p=p-lchild;/5.变为第二种情况处理变为第二种情况处理(删除删除) free(tmp); /6.释放要删除的结点释放要删除的结点 第 八 章 查 找 FPCPRCLQQLMS小结：小结：二叉排序树的删除二叉排序树的删除要删除二叉排序树中的要删除二叉排序树中的* *p p结点结点, ,分三种情况：分三种情况：* *p p为叶子结点为叶子结点* *p p只有左子树或右子树只有左子树或右子树* *p p只有左子树，用只有左子树，用* *p
49、 p的左孩子代替的左孩子代替* *p p* *p p只有右子树，用只有右子树，用* *p p的右孩子代替的右孩子代替* *p p* *p p左、右子树均非空左、右子树均非空针对针对* *p p有子树的情况，把有子树的情况，把* *p p的两个的两个子树合并为一棵树，然后将其连接子树合并为一棵树，然后将其连接到到* *p p的双亲上。的双亲上。 第 八 章 查 找 二叉排序树删除算法二叉排序树删除算法 voidDelBSTNode(BSTreeTptr，KeyTypekey)BSTNode*parent=NUll，*p=*Tptr，*q，*child；while(p)if(p-key=key)b
50、reak；parent=p；p=(keykey)?p-lchild：p-rchild；if(!p)return；/*找不到被删结点则返回找不到被删结点则返回*/q=p；/*找到时找到时,q记住被删结点记住被删结点p*/if(q-lchild&q-rchild)for(parent=q，p=q-rchild；p-lchild；parent=p，p=p-lchild)；/*找被删结点的后继找被删结点的后继*/if(!parent)Tptr=child；elseif(p=parent-lchild)parent-lchild=child；elseparent-rchild=child；if(p!=q
51、)q-key=p-key；free(p)；child=(p-lchild)?p-lchild：p-rchild； 第 八 章 查 找 二叉排序树上的查找二叉排序树上的查找 在二叉排序树上进行查找，和二分查找类似，在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。也是一个逐步缩小查找范围的过程。递归的查找算法：递归的查找算法：BSTNodeBSTNode * *SearchBSTSearchBST( (BSTreeBSTree T T，KeyTypeKeyType key)key) if(T=NULL|key=T-key) if(T=NULL|key=T-key) retu
52、rn Treturn T； if(keykey)if(keykey) returnreturn SearchBSTSearchBST(T-(T-lchildlchild，key)key)； elseelse return return SearchBSTSearchBST(T-(T-rchildrchild，key)key)； 第 八 章 查 找 在二叉排序树上进行查找时的在二叉排序树上进行查找时的平均查找长度和二叉树平均查找长度和二叉树的形态有关：的形态有关：( (a)a)在最坏情况下，二叉排序树是通过把一个有序表的在最坏情况下，二叉排序树是通过把一个有序表的n n个结点依次插入而生成的，此
53、时所得的二叉排序树蜕个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为化为一棵深度为n n的的单支树单支树，它的平均查找长度和单链，它的平均查找长度和单链表上的顺序查找相同，也是表上的顺序查找相同，也是( (n+1)/2n+1)/2。(b)(b)在最好情况下，二叉排序树在生成的过程中，树的形在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约定树相似的二叉排序树，此时它的平均查找长度大约是是loglog2 2n n。(c)(c)插入、删除和查找算法的时间
54、复杂度均为插入、删除和查找算法的时间复杂度均为O(logO(log2 2n)n)。 第 八 章 查 找 二叉排序树和二分查找的比较二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的查找就平均时间性能而言，二叉排序树上的查找和二分查找差不多。和二分查找差不多。 就维护表的有序性而言，二叉排序树无须移动结就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为均的执行时间均为O(logO(log2 2n)n)，因此更有效。二分查找因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点
55、的所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是操作，则维护表的有序性所花的代价是O(n)O(n)。当有序当有序表是静态查找表时，宜用向量作为其存储结构，而采表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；用二分查找实现其查找操作；若有序表是动态查找表，若有序表是动态查找表，则应选择二叉排序树作为其存储结构。则应选择二叉排序树作为其存储结构。 第 八 章 查 找 n n个结点的平衡的二叉排序的高度个结点的平衡的二叉排序的高度H H（即即lgnlgn）比比B-B-树的高度树的高度h h约大约大lgtlgt倍。倍。 例如例如m=1024m=
56、1024，则则lgtlgt=lg512=9=lg512=9。此时若此时若B-B-树高度为树高度为4 4，则平衡的二叉排序树的高度约为，则平衡的二叉排序树的高度约为3636。显然，若。显然，若m m越越大，则大，则B-B-树高度越小。树高度越小。 若要作为内存中的查找表，若要作为内存中的查找表，B-B-树却不一定比平衡树却不一定比平衡的二叉排序树好，尤其当的二叉排序树好，尤其当m m较大时更是如此。较大时更是如此。 因为查找等操作的因为查找等操作的CPUCPU计算时间在计算时间在B-B-树上是树上是 O(O(mlogtnmlogtn)=0(lgn(m/lgt)=0(lgn(m/lgt) 性能分析
57、性能分析 第 八 章 查 找 8.48.4散列散列( (Hash)Hash)技术技术设所有可能出现的关键字集合记为设所有可能出现的关键字集合记为U(U(简简称全集称全集) )。实际发生。实际发生( (即实际存储即实际存储) )的关键字集的关键字集合记为合记为K K（|K|K|比比| |U|U|小得多）。小得多）。 散列方法是散列方法是: :使用函数使用函数h h将将U U映射到表映射到表T0.m-1T0.m-1的下标上的下标上。 这样以这样以U U中关键字为自变量，以中关键字为自变量，以h h为函数的为函数的运算结果就是相应结点的存储地址。从而达运算结果就是相应结点的存储地址。从而达到在到在O
58、(1)O(1)时间内就可完成查找。时间内就可完成查找。散列表散列表( (Hash Table)Hash Table) 第 八 章 查 找 其中：其中： 称称h h为为散列函数散列函数( (Hash Function)Hash Function)。散列散列函数函数h h的作用是压缩待处理的下标范围，使的作用是压缩待处理的下标范围，使待处理的待处理的| |U|U|个值减少到个值减少到m m个值，从而降低个值，从而降低空间开销。空间开销。 T T为为散列表散列表( (Hash Table)Hash Table)。 h( h(K Ki i)()(K Ki iU)U)是关键字为是关键字为K Ki i结点
59、存储地结点存储地址址( (亦称散列值或亦称散列值或散列地址散列地址) )。 将结点按其关键字的散列地址存储到散将结点按其关键字的散列地址存储到散列表中的过程称为列表中的过程称为散列散列( (Hashing)Hashing) 第 八 章 查 找 冲突：冲突： 两个不同的关键字，由于散列函数值两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置相同，因而被映射到同一表位置( (存储地址存储地址) )上。上。该现象称为冲突该现象称为冲突( (Collision)Collision)或碰撞。发生冲或碰撞。发生冲突的两个关键字称为该散列函数的同义词突的两个关键字称为该散列函数的同义词( (Syn
60、onym)Synonym)。 散列表的冲突现象散列表的冲突现象 第 八 章 查 找 其一是其一是记录的个数记录的个数存储空间的大小存储空间的大小 其二是其二是选择合适的散列函数选择合适的散列函数。怎么样才能完全避免冲突？怎么样才能完全避免冲突？最理想的解决冲突的方法是安全避免冲最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：突。要做到这一点必须满足两个条件： 第 八 章 查 找 通常，哈希函数通常，哈希函数h h是一个压缩映是一个压缩映像。虽然实际发生的键值个数像。虽然实际发生的键值个数| |K|mK|m，但但| |U|mU|m，故无论怎样故无论怎样设计设计h h，也不可能
61、完全避免冲突。也不可能完全避免冲突。 冲突不可能完全避免冲突不可能完全避免 第 八 章 查 找 冲突除了与冲突除了与h h相关外，还与表的填满程相关外，还与表的填满程度相关。度相关。 设设m m为表长，为表长，n n为表中填入的结点数为表中填入的结点数（记录数），则将（记录数），则将=n/m=n/m定义为散列表的定义为散列表的装填因子装填因子( (Load Factor)Load Factor)。越大，表越满，越大，表越满，冲突的机会也越大。通常取冲突的机会也越大。通常取11。 影响冲突的因素影响冲突的因素因此：要尽量减少冲突，就要选择好的因此：要尽量减少冲突，就要选择好的哈希函数哈希函数h(
62、key)和选择恰当的哈希表的长度和选择恰当的哈希表的长度m（既选择好的既选择好的=n/m=n/m）。）。 第 八 章 查 找 常用散列函数常用散列函数平方取中法平方取中法 取关键字的平方值的中间几位数取关键字的平方值的中间几位数 先通过求先通过求关键字的平方值关键字的平方值扩大相近数扩大相近数的差别，然后根据表长度取中间的几位的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的数作为散列函数值。又因为一个乘积的中间几位数中间几位数和乘数的每一位都相关，所和乘数的每一位都相关，所以由此产生的散列地址较为均匀。以由此产生的散列地址较为均匀。 第 八 章 查 找 intHash(in
63、tkey)/*假设假设key是是4位整数位整数*/key*=key；key/=100；/*先求平方值，后去掉末尾的两位数先求平方值，后去掉末尾的两位数*/returnkey1000；/*取中间三位数作为散列地址返回取中间三位数作为散列地址返回*/平方取中法平方取中法用用C程序实现如下：程序实现如下： 第 八 章 查 找 取关键字或关键字的某个线性函数为哈希地址取关键字或关键字的某个线性函数为哈希地址即：即：H(k)=key或或H(k)=a*key+b其中其中a，b为常数为常数直接定址法直接定址法 第 八 章 查 找 是简单常用的一种方法。它是是简单常用的一种方法。它是以以表长表长m m来除关键
64、字，取其余数作来除关键字，取其余数作为散列地址为散列地址, ,即即 h(key)=keyh(key)=keym m 该方法的该方法的关键是选取关键是选取m m。选取的选取的m m应使得散列函数值尽可能与关应使得散列函数值尽可能与关键字的各位相关。键字的各位相关。m m最好为素数最好为素数除余法除余法 第 八 章 查 找 该方法包括两个步骤：该方法包括两个步骤： 首先用关键字首先用关键字keykey乘上某个常数乘上某个常数A(0A1)A(0A1)，并抽取出并抽取出keyAkeyA的小数的小数部分；部分； 然后用然后用m m乘以该小数后取整。乘以该小数后取整。 相乘取整法相乘取整法 第 八 章 查
65、 找 相乘取整法的相乘取整法的C C程序如下：程序如下：intint Hash( Hash(intint key) key) double d=key *Adouble d=key *A； /*不妨设A和m已有定义*/ return (return (intint)(m*()(m*(d-(d-(intint)d)d)； /* (int)表示强制转换后面的表达式为整数*/ 第 八 章 查 找 选择一个随机函数，取关键字选择一个随机函数，取关键字的随机函数值为它的散列地址的随机函数值为它的散列地址 即即 h(key)=random(key)h(key)=random(key)其中其中randomr
66、andom为伪随机函数，但为伪随机函数，但要保证函数值是在要保证函数值是在0 0到到m-1m-1之间。之间。随机数法随机数法 第 八 章 查 找 处理冲突的方法处理冲突的方法 一、一、开放地址法解决冲突的方法开放地址法解决冲突的方法 假设假设哈希表的地址集为哈希表的地址集为0 0m-1m-1，当冲突发生时，即由关当冲突发生时，即由关键字得到的哈希地址为键字得到的哈希地址为j(0jm-1)j(0jm-1)的位置上已存有的位置上已存有记录，则处理冲突就是为该关键字的记录找到另一个记录，则处理冲突就是为该关键字的记录找到另一个“空空”的哈希地址。的哈希地址。为此为此在处理冲突的过程中，需采在处理冲突
67、的过程中，需采用某种探测技术在散列表中形成一个探测序列用某种探测技术在散列表中形成一个探测序列H Hi i , ,i=1,2,3,i=1,2,3,，k(Hk(Hi i00,m-1)m-1) 。沿此序列逐个单元沿此序列逐个单元地查找，直到找到给定的或者碰到一个开放的地址地查找，直到找到给定的或者碰到一个开放的地址( (即即该地址单元为该地址单元为“空空”) )为止（若要插入，在探查到开放为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。的地址，则可将待插入的新结点存人该地址单元）。查找时查找时探查到开放的地址则表明表中无待查的关键字，探查到开放的地址则表明表中无待查的关键
68、字，即查找失败。即查找失败。 第 八 章 查 找 开放地址法的一般形式为：开放地址法的一般形式为： H Hi i=(h(key)+=(h(key)+d di i) )m m 1im-11im-1 其中其中h(key)h(key)为哈希函数，为哈希函数，m m为哈希表长，为哈希表长，d d为增量序列，它可有下列几种取法：为增量序列，它可有下列几种取法： d di i=1=1，2 2，3 3，m-1m-1 d di i=1=12 2，-1-12 2,2,22 2，-2-22 2,3,32 2，kk2 2 ;(k=m/2);(k=m/2) d di i= =伪随机数序列伪随机数序列 第 八 章 查
69、找 按照形成探查序列的方法不同，可将开放定址法区按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。分为线性探查法、二次探查法、双重散列法等。线性探查法线性探查法( (Linear Probing)Linear Probing) 该方法的基本思想是：该方法的基本思想是：将散列表将散列表T0.m-1T0.m-1看成是一个循环向量，若初始看成是一个循环向量，若初始探查的地址为探查的地址为d(d(即即h(key)=d)h(key)=d)，则最长的探查序列为：则最长的探查序列为： d d，d+ld+l，d+2d+2，m-1m-1，0 0，1 1，d-1d-1即即: :
70、探查时从地址探查时从地址d d开始，首先探查开始，首先探查TdTd，然后依次然后依次探查探查Td+1Td+1，直到直到Tm-1Tm-1，此后又循环到此后又循环到T0T0，T1T1，直到探查到直到探查到Td-1Td-1为止。为止。形成探测序列的方法形成探测序列的方法开放地址法解决冲突开放地址法解决冲突 第 八 章 查 找 双重散列法双重散列法( (Double Hashing)Double Hashing) 该方法是开放定址法中最好的方法该方法是开放定址法中最好的方法之一，它的探查序列是：之一，它的探查序列是： h hi i=(h(key)+i*h=(h(key)+i*h1 1(key)(key
71、)m m 0im-10im-1 即即 d di i=i*h=i*h1 1(key)(key) 即即探查序列为：探查序列为：d=h(key),(d+hd=h(key),(d+h1 1(key)(key)m ,(d+2hm ,(d+2h1 1(key)(key)m m，等。等。开放地址法解决冲突开放地址法解决冲突 第 八 章 查 找 若选定的散列表长度为若选定的散列表长度为m m，则可将散列表则可将散列表定义为一个由定义为一个由m m个头指针组成的指针数组个头指针组成的指针数组T0.m-1T0.m-1。凡是散列地址为凡是散列地址为i i的结点，均的结点，均插入到以插入到以TiTi为头指针的单链表中
72、。为头指针的单链表中。T T中中各分量的初值均应为空指针。各分量的初值均应为空指针。二、拉链法解决冲突二、拉链法解决冲突是是将所有关键字为同义词的结点链接在同将所有关键字为同义词的结点链接在同一个单链表中一个单链表中。 第 八 章 查 找 例：例：已知一组已知一组关键字为（关键字为（2626，3636，4141，3838，4444，1515，6868，1212，0606，5151），取表），取表长为长为1313，用拉链，用拉链法解决冲突构造法解决冲突构造这组关键字的散这组关键字的散列表如右图列表如右图 012345869710111226 1541 1236 68 06 3844 51 H（k
73、ey）=key%13拉链法解决冲突拉链法解决冲突 第 八 章 查 找 012345869710111226 15 68 44 06 36 1241 36 3851 上题也可以如下做：上题也可以如下做：m m个头指针组成的指针数组个头指针组成的指针数组T T的每个元素改造成的每个元素改造成两个域，一个存储基本哈希表内容；另一个为指针域，指向同义词的两个域，一个存储基本哈希表内容；另一个为指针域，指向同义词的链表。链表。拉链法解决冲突拉链法解决冲突 第 八 章 查 找 拉链法解决冲突拉链法解决冲突 拉链法的优点拉链法的优点(2)由于拉链法中各链表上的结点空间是动态由于拉链法中各链表上的结点空间是动
74、态申请的，故它更适合于造表前无法确定表长的申请的，故它更适合于造表前无法确定表长的情况；情况；(1)拉链法处理冲突简单，且无堆积现象，即拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度非同义词决不会发生冲突，因此平均查找长度较短；较短； 第 八 章 查 找 (3)开放定址法为减少冲突，要求装填因子开放定址法为减少冲突，要求装填因子较小，故当结点规模较大时会浪费很多空间。较小，故当结点规模较大时会浪费很多空间。而拉链法中可取而拉链法中可取1，且结点较大时，拉链且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空法中增加的指针域可忽略不计，因此节省空间；间；(4)在
75、用拉链法构造的散列表中，删除结点的在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应操作易于实现。只要简单地删去链表上相应的结点即可。的结点即可。 第 八 章 查 找 拉链法的拉链法的缺点缺点是：指针需要额外是：指针需要额外的空间，故当结点规模较小时，的空间，故当结点规模较小时，开放定址法较为节省空间，而若开放定址法较为节省空间，而若将节省的指针空间用来扩大散列将节省的指针空间用来扩大散列表的规模，可使装填因子变小，表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，这又减少了开放定址法中的冲突，从而提高平均查找速度从而提高平均查找速度。 拉链法解决冲突拉链法解决
76、冲突拉链法的缺点拉链法的缺点 第 八 章 查 找 8.4.48.4.4散列表上的运算散列表上的运算 散列表类型说明：散列表类型说明：#defineNIL-1#defineM997typedefstructKeyTypekey；InfoTypeotherinfo；NodeType；TypedefNodeTypeHashTablem； 第 八 章 查 找 散列表的查找过程和建表过程相似。散列表的查找过程和建表过程相似。假设给定的值为假设给定的值为K K，根据建表时设定根据建表时设定的的散列函数散列函数h h，计算出散列地址计算出散列地址h(K)h(K)，若表中该地址单元为空若表中该地址单元为空(
77、(是开放的是开放的) )，则查找失败；否则将该地址中的结，则查找失败；否则将该地址中的结点与给定值点与给定值K K比较。若相等则查找成比较。若相等则查找成功，否则按建表时设定的处理冲突的功，否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去方法找下一个地址。如此反复下去 基于开放地址法的查找算法基于开放地址法的查找算法 第 八 章 查 找 开放地址法一般形式的函数表示开放地址法一般形式的函数表示 intint Hash( Hash(KeytypeKeytype k k，intint i) i) return(h(K)+increment(i) return(h(K)+increment
78、(i)m m； 若散列函数用除余法构造，并假设使用线若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的性探查的开放定址法处理冲突，则上述函数中的h(K)h(K)和和increment(i)increment(i)可定义为：可定义为： intint h( h(KeytypeKeytype K) K) return K return Km m； intint increment( increment(intint i) i) return i; return i; 求哈希函数求哈希函数值的算法值的算法 第 八 章 查 找 intint HashSearchHashSea
79、rch( (HashTableHashTable T T，KeytypeKeytype K K，intint *pos) *pos) intint i=0 i=0； do do *pos=Hash(K *pos=Hash(K，i)i)；/*/*求探查地址求探查地址hi*/ if(T*pos.key=K) return l if(T*pos.key=K) return l；/*/*查找成功查找成功返回返回*/ if(T*pos.key=NIL) return 0if(T*pos.key=NIL) return 0；/*/*查找到空结查找到空结点返回点返回*/ while(+im) while(+
80、i0)printf(“duplicatekey!”)；/*有有重复的关键字重复的关键字*/elseError(hashtableoverflow!)；/*表满错误，终止程序执行表满错误，终止程序执行*/ 第 八 章 查 找 voidCrHTable(HashTableT，NodeTypeA，intn)/*根据根据A0.n-1中结点建立散列表中结点建立散列表T0.m-1*/inti；if(nm)/*用开放定址法处理冲突，装填因子用开放定址法处理冲突，装填因子( (=n/m)=n/m)1)；for(i=0;im；i+)Ti.key=NULL；/*将各关键字清空，使地址将各关键字清空，使地址i为开放
81、地址为开放地址*/for(i=0;in；i+)/*依次将依次将A0.n-1插入到散列表插入到散列表T0.m-1中中*/Hashlnsert(T，Ai)；/*调用插入算法，将调用插入算法，将Ai插入哈希表中插入哈希表中建哈希表建哈希表 第 八 章 查 找 基于开放定址法的散列表不宜基于开放定址法的散列表不宜执行散列表的删除操作。若必须在执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删散列表中删除结点，则不能将被删结点的关键字置为结点的关键字置为UNLLUNLL，而应该将而应该将其置为特定的标记其置为特定的标记DELETEDDELETED。删除删除 第 八 章 查 找 插入插入和和删除
82、删除的时间均取决于查找，故下的时间均取决于查找，故下面只分析查找操作的时间性能。面只分析查找操作的时间性能。虽然散列表在关键字和存储位置之间建虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字立了对应关系，理想情况是无须关键字的比较就可找到待查关键字的记录的比较就可找到待查关键字的记录。但但是由于冲突的存在，散列表的查找过程是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要查找等完全依赖于关键字比较的查找要小得多。小得多。性能分析性能分析
