《数据结构》课件第8章

第8章查找8.1查找的基本概念8.2基于线性表的查找法8.3基于树的查找8.4计算式查找法——哈希法本章小结习题八实训8-1分块查找实训8-2二叉排序树的建立

【教学目标】通过本章的学习，掌握查找的基本概念；重点掌握顺序查找、折半查找的思想与算法及平均查找长度；掌握二叉排序树的查找、插入和删除方法；掌握哈希表查找的思想；掌握构造哈希函数的几种常用方法；掌握用链地址法和开放定址法解决哈希冲突。查找不是一种数据结构，而是一种基于数据结构的对数据进行处理时经常使用的一种操作。查找又称为检索，它是计算机科学中重要的研究课题之一，查找的目的就是从确定的数据集合中找出某个特定的元素。查找的方法很多，而且与数据的结构密切相关，查找算法的优劣对计算机系统的运行效率影响很大。本章主要学习查找的基本概念、顺序查找算法、折半查找算法、二叉排序树和哈希查找算法等。8.1查找的基本概念在日常生活中，人们几乎每天都要进行“查找”工作。例如，在奥运跨栏运动员信息表中查找某人的报名成绩，在电话号码本中查找某人或某单位的电话号码等等。要进行查找操作，必须首先明确要查找的对象，也就是要查找的数据元素的特征。在计算机中，一个数据元素通常是一条记录，具有多个数据项，如表8-1所示。表8-1查找表表8-1就是一张查找表，每行是一个数据元素，称为一条记录(Record)。下面给出相关的一些概念：

(1)查找表。是由同一类型的数据元素(或记录)构成的集合，可利用任意数据结构实现。

(2)查找表的操作：①查询某个“特定的”数据元素是否在查找表中。②检索某个“特定的”数据元素的各种属性。③在查找表中插入一个数据元素。④从查找表中刪去某个数据元素。若对查找表只进行前两种“查找”操作，则称此类查找表为静态查找表(StaticSearchTable)；若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表(DynamicSearchTable)。

(3)关键字。数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，如上表中的“学号”，否则为次关键字，如上表中的“高等数学”。当数据元素仅有一个数据项时，数据元素的值就是关键字。

(4)查找。根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。关键字(key)可以作为查找的依据。在本章的各个算法及示例中，只给出各数据元素的关键字，而忽略其它数据项的内容，如无特别说明，均认为要查找的数据集合中元素的类型如下：typedefstructelem{KeyTypekey； /*关键字*/

… /*其他数据项*/}ET；衡量查找算法效率的标准是平均查找长度。为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的查找表，查找成功时的平均查找长度为

ASL

=

P1C1 + P2C2 + …

+ Pn Cn = 其中，Pi为查找第i个数据元素的概率，Ci为找到第i个数据元素时已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，因此可用平均查找长度来衡量查找算法的性能。查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH(哈希)查找法。8.2基于线性表的查找法基于线性表的查找可以分为顺序查找法、折半查找法(或称二分查找法)以及分块查找法。8.2.1顺序查找顺序查找(SequentialSearch)又称为线性查找，是一种最简单的查找方法。其基本思想是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。下面给出用C语言描述的顺序结构有关数据类型的定义：#defineLISTSIZE20#defineKeyTypeint /*关键字类型*/#defineOtherTypeint /*其他数据项类型*/typedefstruct{KeyTypekey;OtherTypeother-data;}RecordType;typedefstruct{RecordTyper[LISTSIZE+1]; /*r[0]为工作单元*/intlength;}RecordList;基于顺序结构的线性查找算法如下：intSeqSearch(RecordListl,KeyTypek)/*在顺序表l中顺序查找其关键字等于k的元素，查找成功则返回该元素在表中的位置，否则为0*/{inti;l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return(i);}其中l.r[0]称为监视哨，即l.r[0].key =w k，以便控制循环最多执行到数组中下标为0的元素位置，可以起到防止越界的作用。不用监视哨的算法如下：intSeqSearch(RecordListl,KeyTypek)/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{inti;i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return(i)elsereturn(0);}其中，循环条件i >=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i + 1次比较，即Ci = n-i + 1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为查找失败时的平均查找长度为n。假设被查找记录在查找表中的概率为P，则不在查找表中的概率为1-P，考虑到查找成功和失败两种情况下的平均查找长度为可见，顺序查找虽然简单，但查找效率却很低。8.2.2折半查找我们先来玩一个“猜数”游戏：甲先在心中想好一个100以内的整数x，然后让乙来猜，每次甲可提示乙所猜的数是比x大还是比x小，乙怎样才能猜得快呢？学习完这一节，相信你就能得到答案。再来看看查英文字典的方法，我们并不需要从最前或最后开始逐个查找，为什么呢？因为字典是按字母的次序排列的。换句话说，在按某关键字排序的有序表中进行查找，效率会比顺序查找更高。这就是在有序表中采用的折半查找。折半查找法(BinarySearch)又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录时查找成功，或直到子表不存在为止，此时查找不成功。

例8.1

已知含有11个数据元素的有序表，其关键字序列如下：(7，13，18，25，46，55，58，61，67，69，72)现要查找关键字为58，30的数据元素。用指针low和high分别指示待查元素所在范围的下界与上界，指针mid指示区间的中间位置，则有初始时，取low=0，high=10。下面先看查找关键字为58的数据元素的过程：第一次比较：mid=5，58＞55，则low=mid+1=6，high不变。第二次比较：mid=8，58＜67，则low不变，high=mid–1=7。第三次比较：mid=6，58==58查找成功。三次查找比较如图8.1所示。下面再看查找关键字为30的数据元素的过程：第一次比较：mid=5，30＜55，则low不变，high=4。第二次比较：mid=2，30＞18，则low=3，high不变。第三次比较：mid=3，30＞25，则low=4，high不变。第四次比较：mid=4，30＜46，则low不变，high=3。此时，low>high，结束查找，说明查找不成功。四次查找比较如图8.2所示。图8.1折半查找成功图8.2折半查找失败折半查找算法用C语言描述如下：intBinSrch(SqListl,KeyTypek)/*在有序表l中折半查找其关键字等于k的元素，查找成功则返回该元素在表中的位置，查找失败返回0*/{intlow,high,mid；low=0; /*置区间初值*/high=l.length-1; while(low<=high){mid=(low+high)/2;if(k==l.r［mid］.key) /*找到待查元素*/return(mid+1); /*数组下标从0开始，元素位置从1开始，为mid+1*/elseif(k<l.r［mid］.key)high=mid-1; /*未找到，则继续在前半区间进行查找*/elselow=mid+1; /*未找到，继续在后半区间进行查找*/}return(0);}下面我们来分析折半查找的平均查找长度。折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号(或用数组下标表示)。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。由二叉树的性质可知，判定树的深度为 

log2n

+1，因此，折半查找在查找成功与不成功时和给定值进行比较的关键字个数最多不超过

log2n

 + 1。对于例8.1中长度为11的有序表，它的折半查找的二叉判定树(用数组下标表示)如图8.3所示。在进行查找时，首先要进行比较的记录是r[5]，因此该二叉判定树的根结点表示为⑤。若x==r[5].key，则查找成功；若x＜r[5].key，则沿着根结点的左子树继续下层结点的比较；若x＞r[5].key，则沿着根结点的右子树继续下层结点的比较；所以一次成功的查找所需的比较次数最多不超过对应的二叉判定树深度。图8.3折半查找的二叉判定树例如查找关键字为58的记录所走的路径为⑤→⑧→⑥，比较3次。一次不成功的查找所需的比较次数也不会超过对应的二叉判定树深度。例如查找关键字为30的记录所走的路径为⑤→②→③→④，比较4次。那么折半查找的平均查找长度是多少呢？为便于讨论，假定表的长度n = 2h-1，则相应判定树必是深度为h的满二叉树，h = log2(n + 1)。又假设每个记录的查找概率相等Pi=1/n，则折半查找成功时的平均查找长度为当n较大时，有ASL = log2(n + 1)-1可见，折半查找的效率比顺序查找要高，但折半查找只适用于顺序存储的有序表。8.3基于树的查找基于树的查找法又称为树表查找法，是将待查表组织成特定树的形式并在树结构上实现查找的方法，主要包括二叉排序树、平衡二叉排序树和B树等。本章只介绍二叉排序树。8.3.1二叉排序树的定义二叉排序树或者是空树，或者是满足如下性质的二叉树：

(1)若其左子树非空，则左子树上所有结点的值均小于根结点的值。

(2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值。

(3)其左右子树本身又各是一棵二叉排序树。如图8.4所示就是两棵二叉排序树。图8.4二叉排序树(a)二叉排序树示例；(b)根据ASCII码大小排序的二叉排序树示例由二叉排序树的定义不难发现，按中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列。8.3.2二叉排序树上的操作

1.查找因为二叉排序树可看作是一个有序表，所以在二叉排序树上进行查找与折半查找类似，也是一个逐步缩小查找范围的过程。根据二叉排序树的特点，首先将待查关键字k与根结点关键字t进行比较，如果：

(1) k = t，则返回根结点地址。

(2) k＜t，则进一步查左子树。

(3) k＞t，则进一步查右子树。显然这是一个递归过程。用C语言描述如下：typedefstructnode{

KeyTypekey;

structnode*lchild;

structnode*rchild;}BSTNode,BSTree;BSTree*SearchBST(BSTree*T,KeyTypex)/*在根指针T所指二叉排序树中，递归查找某关键字等于x的元素，若查找成功，则返回指向该元素结点指针，否则返回空指针*/{if(!T)returnNULL; /*树为空，查找失败，返回*/elseif(T->key==x)returnT;/*查找成功*/

else

if(x<T->key) returnSearchBST(T->lchild,x);

/*在左子树中继续查找*/ else returnSearchBST(T->rchild,x);

/*在右子树中继续查找*/}

例8.2

在图8.5中查找关键字为55和关键字为40的两个节点。

解：55大于根结点关键字值50，因而向它的右子树查找；55小于右子树根结点的关键字的值60，然后向左子树找；此时的左子树根结点关键字值为55，与所找结点的值相同，查找成功。图8.5二叉排序树再来看一下关键字值为40的结点，首先40小于根结点关键字值50，因而向根结点的左子树查找；40大于根结点关键字值10，因而向关键值为10的结点的右子树查找；40大于根结点关键值30，继续向键值为30结点的右子树找，但此时它的右子树为空，查找失败，返回空指针NULL。

2.插入与生成已知一个关键字值为x的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行：

(1)若二叉排序树是空树，则x成为二叉排序树的根；

(2)若二叉排序树非空，则将x与二叉排序树的根进行比较。如果x的值等于根结点的值，则停止插入；如果x的值小于根结点的值，则将x插入左子树；如果x的值大于根结点的值，则将x插入右子树。相应的递归算法如下：voidInsertBST(BSTree*T,KeyTypex)/*若在二叉排序树中不存在关键字等于x的元素，插入该元素*/{BSTree*s;if(T==NULL) /*递归结束条件*/{ s=(BSTree*)malloc(sizeof(BSTNode)); /*申请新的结点s*/ s->key=x;s->lchild=NULL; s->rchild=NULL; T=s; } elseif(x<T->key) InsertBST(T->lchild,x); /*将s插入左子树*/ elseif(key>T->key) InsertBST(T->rchild,x); /*将s插入右子树*/}假若给定一个元素序列，可以利用上述算法创建一棵二叉排序树。首先，将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点并插入到当前已生成的二叉排序树中，即调用上述二叉排序树的插入算法将新结点插入。生成二叉排序树的算法如下：voidCreateBST(BSTree*T)/*从键盘输入元素的值，创建相应的二叉排序树*/{KeyTypekey; T=NULL; scanf(″%d″,&key); while(key!=ENDKEY)

/*ENDKEY为自定义常数*/{InsertBST(T,key);scanf(″%d″,&key);}}

例8.3

对于关键字值序列(45，24，53，12，28，90)，求出建立二叉排序树的过程。

解：建立二叉排序树的过程如图8.6所示。值得注意的是，对于同一个关键字值集合，如果插入的顺序不同，生成的二叉排序树也可能不同。上例中如果关键字序列为(24，12，53，28，45，90)，则得到的二叉排序树如图8.7所示：图8.6二叉排序树的建立过程空树；(b)插入45；(c)插入24；(d)插入53；(e)插入12；(f)插入28；(g)插入90图8.7输入顺序不同所建立的不同二叉排序树

3.删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。也就是说，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。删除操作首先要查找，以确定被删结点是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子(右孩子的情况类似)。下面分三种情况讨论：

(1)若p为叶子结点，则可直接将其删除：

f->lchild=NULL；

free(p)；如图8.8所示，这叫“无后而终”。图8.8删除二叉排序树中叶子结点(a)原树；(b)删除2后

(2)若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树，即：

f->lchild = p->lchild(或f->lchild = p->rchild)；

free(p)；如图8.9所示，这叫“子承父业”。图8.9删除二叉排序树中只有一棵子树的结点(a)原树；(b)删除30和65后

(3)若p既有左子树，又有右子树，如图8.10(a)所示。这时要首先找到p结点在中序序列中的直接前驱s结点，然后可采用两种不同的处理方法。s是p的左子树上“最右边”的结点，它的右子树一定为空，否则s的直接后继就会在它的右子树上，而不会是p了。方法1：首先找到p结点在中序序列中的直接前驱s结点，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：

f->lchild = p->lchild；

s->rchild =p->rchild；

free(p)；结果如图8.10(b)所示，这叫“左子继位，右子接前驱”。方法2：首先找到p结点在中序序列中的直接前驱s结点，然后用s结点的值替代p结点的值，原s结点的左子树改为s的双亲结点sf的右子树，再将s结点删除：

p->data = s->data；

sf->rchild=s->lchild；

free(s)；结果如图8.10(c)所示，这叫“前驱替代，依次升级”。图8.10删除二叉排序树中有左右子树的结点(a)原树；(b)删除10后(方法1)；(c)删除10后(方法2)8.3.3性能分析在二叉排序树上进行查找时，若查找成功，则显然是从根结点出发走了一条从根结点到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根结点到叶子结点的路径。因此二叉排序树的查找与折半查找类似，其查找比较次数不超过树的高度。但是，折半查找二叉判定树的结点是记录在表中的位置序号，树的形态与数据值无关，其平均查找长度是一定的。而从例8.3可以看出，对于同一个关键字值集合，如果结点插入的先后次序不同，所形成的二叉排序树形态就可能不同，则平均查找长度也就不同。给定二叉排序树的形态，等概率查找成功时的ASL=∑Ci/n(Ci为第i个结点所在的层)。最坏的情况下，二叉排序树是通过把一个有序表的n个结点依次插入生成的，由此得到的二叉排序树退化在一棵高度为n的单支树，对它的查找相当于对线性表的查找，平均查找长度为(n+1)/2。最好的情况下，二叉排序树在生成过程中，树的形态比较均匀，所得二叉排序树类似折半查找的判定树，此时平均查找长度约为log2n。如果插入的数据是随机的，则平均查找长度为O(log2n)。8.4计算式查找法——哈希法在前面介绍的几种查找方法中，无论是线性查找表还是树表，记录在存储结构中的位置是随机的，即存储位置与记录关键字之间没有确定的关系，其查找操作是通过给定值与记录关键字之间的比较进行的，查找的效率与比较的次数密切相关。哈希(Hash)法又称散列法、杂凑法或关键字地址计算法等，相应的表称为哈希表。哈希技术既是一种存储方法，又是一种查找方法。它是通过某种方法的计算，在记录关键字与其存储位置之间建立确定的对应关系，这种关系一旦确定，每条记录都存储在固定的存储单元中，查找时只需根据这种对应关系，找到给定值对应的存储位置，从而达到按关键字直接存取记录的目的。8.4.1哈希法哈希法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p = H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p = H(k)，从而达到按关键字直接存取元素的目的。例如某个会议按与会者的姓名笔画总数排定座位号，则关键字为“姓名”，哈希函数为“求笔画总数”，计算的结果是存取地址“座位号”。则“丁三”的位置是5号，“王五”的位置是8号，他们按此号就座，查找时也可按此号直接找到。当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突，此时称k1和k2为同义词。例如按上面的座位号计算函数，“刘二”的位置也是8号，与“王五”位置相同，这就发生了冲突。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。综上所述，哈希法主要包括以下两方面的内容：

(1)如何构造哈希函数。

(2)如何处理冲突。8.4.2哈希函数的构造方法

Hash表查找技术的主要目标是提高查找效率，缩短查表时间。而在查找关键字为k的元素时，计算哈希函数H(k)的工作量也是影响查找效率的一个因素。如果哈希函数的计算比较复杂，即使冲突的机会很少，也会降低查找效率。因此，在实际设计哈希函数时，要考虑以下两方面的因素:

(1)使各关键字尽可能均匀地分布在哈希表中，即哈希函数值的均匀性要好。

(2)哈希函数值的计算要尽量简单。以上两个方面在实际应用中往往是矛盾的。为了保证哈希函数值的均匀性比较好，其哈希函数值的计算就必然要复杂；反之，如果哈希函数值的计算比较简单，则其均匀性就比较差。因此，在实际设计哈希函数值时，要根据具体情况，选择一个比较合理的方案。构造哈希函数的方法多种多样，下面只介绍一些比较常用的、计算比较简单的方法。

1.数字分析法如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。例如，以学号作为关键字，关键字为9位十进制整数d1d2d3…d7d8d9，d1～d2表示入学年份，d3～d4表示院系，d5～d6表示专业，d7表示班级，d8～d9表示学生序号，07级计算机系软件专业一班15号同学的学号为07

04

01

1

15。该班共有学生50人，如哈希表长取100，则哈希表的地址空间为：00～99。经过分析，各关键字中d8和d9的取值分布较均匀，则哈希函数为：H(key) = H(d1d2d3…d7d8d9)=d8d9。例如，H(070401143) = 43，H(070401106) = 06。相反，经过分析，各关键字中其他位的取值分布都极不均匀，d1都等于0，d7都等于1，此时，如果哈希函数为：H(key)=H(d1d2d3…d7d8) = d1d7，则所有关键字的地址码都是01，显然不可取。

2.平方取中法当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方值中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。例如：把英文字母在字母表中的位置序号作为该英文字母的内部编码。K，E，Y，A，B的内部编码分别为11，05，25，01,02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如表8-2所示。表8-2平方取中法求得的哈希地址

3.除留余数法这是一种最常用的方法，是用关键字k除以一个不大于哈希表长的最大素数，将所得的余数作为Hash函数值。假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

H(k)=k%p,(p≤m),其中%为模p取余运算。例如，已知待散列元素为(18，75，60，43，54，90，46)，表长m = 10，p = 7，则有H(18)=18%7=4H(75)=75%7=5H(60)=60%7=4H(43)=43%7=1H(54)=54%7=5H(90)=90%7=6H(46)=46%7=4此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：H(18)=18%13=5H(75)=75%13=10H(60)=60%13=8H(43)=43%13=4H(54)=54%13=2H(90)=90%13=12H(46)=46%13=7

4.分段叠加法按散列表地址位数将关键字分成位数相等的几部分(最后一部分可以较短)，然后将这几部分相加，舍弃最高进位后的结果，即是该关键字的散列地址。具体方法有折叠法和移位法。移位法是将分割后的每部分低位对齐相加；折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序，偶数段为倒序)，然后将各段相加。例key = 12360324711202065，散列表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得Hash地址为105和907，如图8.11所示。图8.11由叠加法计算Hash地址(a)移位叠加；(b)折叠叠加

5.伪随机数法选择一个伪随机函数，取关键字的伪随机函数值为它的哈希地址。即H(key) = random(key)其中，random为伪随机函数。在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：(1)计算哈希函数所需的时间(简单)。(2)关键字的长度。(3)哈希表的大小。(4)关键字的分布情况。(5)记录查找的频率。8.4.3处理冲突的方法通过构造性能良好的哈希函数，可以减少冲突，但一般情况下不可能完全避免冲突，因此解决冲突是哈希技术的另一个关键问题。下面介绍两种常用的解决哈希冲突的方法。

1.开放定址法这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi = (H(key) + di)%m(i=1,2,…,m)其中，H(key)为哈希函数，m为表长，di称为增量序列。使用这种方法时,首先计算出它的直接哈希地址H(key)，若该单元已被其它记录占用，继续查看地址为H(key) + d1的单元，若该单元也已被占用，继续查看地址为H(key) + d2的单元，如此下去，当发现某个单元为空时，将关键字为key的记录存放到该单元中。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

1)线性探测再散列

di = 1，2，3，…，m-1这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

2)二次探测再散列

di = 12，-12，22，-22，…，k2，-k2(k≤m/2)这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3)伪随机探测再散列

di = 伪随机数序列。具体实现时，应建立一个伪随机数发生器，(如i=(i+p)%m)，并给定一个随机数做起点。

例8.4

有一记录关键字序列(24，3，13，15，20，0，54，43),要将它们存入表长为11的哈希表A中，散列函数为：H(key) = key%11。分别采用线性探测再散列和二次探测再散列解决冲突，试为其构造相应的哈希表。

解：(1)采用线性探测再散列：

H(24) = 2，不冲突，直接存入A[2]。

H(3) = 3，不冲突，直接存入A[3]。

H(13) = 2，冲突，计算下一个哈希地址，H1(13)=(2+1)%11=3，冲突，继续计算H2(13) = (2+2)%11 = 4，不冲突，存入A[4]。

H(15) = 4，冲突，计算下一个哈希地址，H1(15) = (4 + 1)%11 = 5，不冲突，存入A[5]。

H(20) = 9，不冲突，直接存入A[9]。

H(0) = 0，不冲突，直接存入A[0]。

H(54) = 10，不冲突，直接存入A[10]。

H(43) = 10，冲突，计算下一个哈希地址，H1(43) = (10 + 1)%11 = 0，冲突，继续计算H2(43) = (10+2)%11 = 1，不冲突，存入A[1]。用线性探测再散列法构造的哈希表如图8.12所示。图8.12线性探测再散列采用二次探测再散列：

H(24) = 2，不冲突，直接存入A[2]。

H(3) = 3，不冲突，直接存入A[3]。

H(13) = 2，冲突，计算下一个哈希地址，H1(13) = (2 + 1)%11 = 3，冲突，继续计算H2(13) = (2-1)%11 = 1，不冲突，存入A[1]。H(15) = 4，不冲突，直接存入A[4]。

H(20) = 9，不冲突，直接存入A[9]。

H(0) = 0，不冲突，直接存入A[0]。

H(54) = 10，不冲突，直接存入A[10]。

H(43) = 10，冲突，计算下一个哈希地址，H1(43)=(10+1)%11=0，冲突，继续计算H2(43) = (10-1)%11=9，冲突，计算H3(43) = (10 + 4)%11 = 3，冲突，计算H4(43) = (10-4)%11 = 6，不冲突，存入A[6]。用二次探测再散列法构造的哈希表如图8.13所示。图8.13二次探测再散列在哈希表中怎样查找记录呢？哈希表的查找过程与哈希表的创建过程是一致的。当查找关键字为k的元素时，首先计算p0 = H(key)。如果单元p0为空，则所查元素不存在；如果单元p0中元素的关键字为k，则找到所查元素；否则重复下述解决冲突的过程：按解决冲突的方法，找出下一个哈希地址pi，如果单元pi为空，则所查元素不存在；如果单元pi中元素的关键字为k，则找到所查元素。线性探测再散列方法的优点是简单，且只要散列表不满，就一定能找到一个不冲突的散列地址，而二次探测再散列和伪随机探测再散列则不一定。但线性探测再散列有以下三个主要的缺点：

(1)在线性哈希表的填入过程中，当冲突发生时，首先考虑的是下一项，因此，当冲突次数较多时，在线性哈希表中会存在“群聚”的现象，即许多关键字被连续登记在一起，从而会降低查找效率。

(2)若在线性哈希表中删除一条记录，有可能造成某些记录查找不成功，而事实上该记录存在于哈希表中；例如在例8.4中，若已删除24，查找13时，H(13) = 2，但A[2]已为空，便认为查找失败，而事实上13放在了A[4]中。

(3)在线性哈希表的填入过程中，处理冲突时会带来新的冲突，线性哈希表的填入方法是不顾后效的。

2.链地址法这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况，也适用于冲突现象比较严重的情况。

例8.5

已知一组关键字(32，40，36，53，16，46，71，27，42，24，49，64)，哈希表长度为13，哈希函数为：H(key)=key%13，求采用链地址法处理冲突时的平均查找长度。

解：采用链地址法处理冲突时的哈希表如图8.14所示。平均查找长度ASL=(1×7+2×4+3×1)/12=1.5图8.14链地址法处理冲突时的哈希表8.4.4哈希法性能分析由于冲突的存在，哈希法仍需进行关键字比较，因此仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个：哈希函数、处理冲突的方法以及哈希表的装填因子。哈希表的装填因子α的定义如下：

α可描述哈希表的装满程度。显然，α越小，发生冲突的可能性越小，而α越大，发生冲突的可能性越大。假定哈希函数是均匀的，即该哈希函数对同一组中的各个关键字产生冲突的可能性是相同的，则影响平均查找长度的因素只剩下两个：处理冲突的方法以及α。哈希表的平均查找长度是装填因子α的函数，而与待散列元素数目n无关。因此，无论元素数目n有多大，都能通过调整α，使哈希表的平均查找长度较小。在用开放定址法构造哈希表时，会产生非哈希函数引起的冲突，且记录的个数不能大于哈希表表长。采用链地址法则不会出现这些情况，但需要一些额外的空间。本章小结本章学习了与查找有关的一些基本概念，学习了线性表、树表及哈希表查找法。线性表查找法介绍顺序查找和折半查找，折半查找只适用于顺序存储的有序表，其关键字比较次数最多不超过判定树的深度。树表查找法介绍了二叉排序树的查找、插入、删除，二叉排序树上进行查找时的平均查找长度和二叉排序树上的形态有关。哈希查找法是一种计算式查找方法，本章介绍了哈希查找的概念和基本思想。实现哈希查找必须要构造合适的哈希函数，构造哈希函数的方法有多种多样，常用的有数字分析法、平方取中法、除留余数法、分段叠加法和伪随机数法。哈希函数是一种“压缩映射”，它把记录关键字取值很大的数据集合映射到一个范围确定的表中，因此，冲突是不可避免的，本章介绍了两种解决冲突的主要方法，即开放定址法和链地址法。习题八

一、单选题

1.对线性表进行二分查找时,要求线性表必须

。

A.以顺序方式存储 B.以链接方式存储

C.以顺序方式存储且结点按关键字有序排列

D.以链接方式存储且结点按关键字有序排列

2.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为

。

A. nB. n/2 C. (n + 1)/2D. (n-1)/2

3．采用二分查找长度为n的线性时，每个元素的平均查找长度为

。

A. O(n2) B.O (nlog2n)

C. O(n) D. O(log2n)

4.有一个有序表为(5，7，8，22，32，40，45，62，70，77，82，97，100)，当二分查找值为82的结点时，

次比较后查找成功。

A.

1

B.

3

C.

4 D.

8

5.从一个具有n个结点的单链表中查找其值等于x结点时，查找成功的情况下，需平均比较

个结点。

A.

n

B.

n/2C.

(n–1)/2

D.

(n

+

1)/2

二、填空题

1.假设在有序线性表A[1]，…，A[20]上进行二分查找，则比较一次查找成功的结点数为

，则比较二次查找成功的结点数为

，则比较三次查找成功的结点数为

，则比较四次查找成功的结点数为

，则比较五次查找成功的结点数为

，平均查找长度为

。

2.在散列存储中，装填因子α的值越大，存取数据元素时发生冲突的可能性

；α的值越小，则发生冲突的可能性

。

三、简答题设有一组关键字(19，01，23，14，55，20，84，27，68，11，10，77)，采用哈希函数H(key)=key%13采用开放地址法的线性探测再散列方法解决冲突，试在[0…12]的散列地址空间中对该关键字序列构造哈希表。2.对上题中的关键字序列，采用链地址法，画出相应的哈希表。

3.对有序表(5，8，27，36，45，48，57，72，89，95)，采用二分查找，画出二分查找过程的二叉判定树，并计算其平均查找长度。

四、算法设计题

1.将折半查找算法改写为递归的形式。

2.以线性探测再散列为例，给出散列表的查找算法。实训8-1分块查找【实训目的】掌握顺序查找与折半查找的特点。【实训要求】用分块查找【相关知识】分块查找又称索引顺序查找。它是一种顺序查找的改进方法，用于在分块有序表中进行查找。分块有序表指将长度为n的线性表分成m个子表，各子表的长度可以相等，也可不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。分块有序表的结构可以分为两个部分：

(1)采用顺序存储的线性表。

(2)索引表。在索引表中，对线性表的每一个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。索引表关于数据域是有序的。图8.15是将一个长度n=18的线性表分成m=3个子表的分块有序表示意图。图8.15分块有序表示意图(a)采用顺序存储的线性表；(b)索引表【算法分析】根据分块有序表的结构，其查找过程可以分为以下两步：

(1)查找索引表，以确定被查元素所在的子表。由于索引表数据域的数据是有序的，因此可以采用折半查找。

(2)在相应的子表中采用顺序查找。【程序清单】typedefstructindnode{intkey; /*数据域，存放子表中的最大值*/intk; /*指针域，指示子表中第一个元素在线性表中的序号*/}Inode;

/*折半查找索引表，顺序查找子表*/intinserch(intv[],intn,Inodes[],intm,intx)

/*函数返回被查找元素x在线性表中的序号，如果不存在元素x，则返回-1*/

/*v:待查找表，n:最后元素下标，s:索引表，m:块数，

x:待查值*/{inti,j,t;i=1; /*起始块号*/j=m; /*终止块号*/

/*折半查找索引表*/while(j-i>1) /*块号相差>1，则循环，结束时要确定x在i,i+1两块之中*/{t=(i+j)/2;if(x<=s[t].key)j=t;/*可能在第t块或t块以下*/elsei=t; /*在第t块以上*/}if((i!=j)&&(x>s[i].key))i=j; /*j==i+1,且x不在第i块中，则必在第j块，调整i，使其