【文档说明】[计算机软件及应用]DS08查找课件.ppt，共(83)页，559.020 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2117.html

以下为本文档部分文字说明：

第八章查找▪基本概念▪线性表的查找▪树表的查找▪散列(Hash)技术第八章查找第八章查找8.1查找的基本概念查找（Searching）的定义是：在含有n条记录的表（文件）中找出关键字等于给定值K的记录。若找到，则查找成功，返

回该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信息。第八章查找若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（DynamicSearchTable）。否则称之

为静态查找表(StaticSearchTable)。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找查找表的数据结构表示第八章查找如何分析算法优劣？主要分析算法运算时所需要的时间和其

存储结构占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，即平均查找长度ASL（AverageSearchLength）第八章查找其中：1、n是结点的个数；2、Pi是查找第i个结点的概率。若不

特别声明，认为每个结点的查找概率相等，即pl=p2……=pn=1/n3、ci是找到第i个结点所需进行的比较次数ASL==niiicp1平均查找长度ASL（AverageSearchLength）定义为：第八章查找一、顺序查找(Sequent

ialSearch)基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。8.2线性表的查找第八章查找基于顺序结构的顺序查找算法类型

说明typedefstruct{KeyTypekey；/*KeyType由用户定义*/InfoTypeotherinfo；/*此类型依赖于应用*/}NodeType；typedefNodeTypeSeqlist[n+1]；/*多出0号单元用作监视哨*/第八章查找具体算法int

SeqSearch(SeqlistR，KeyTypeK){/*在顺序表R[1..n]中顺序查找关键字为K的结点，*//*成功时返回找到的结点位置，失败时返回0*/inti；R[0].key=K；/*设置

监视哨*/for(i=n；R[i].key!=K;i--)；/*从表后往前找*/returni；/*若i为0，表示查找失败，否则R[i]为要找的结点*/}/*SeqSearch*/第八章查找算法分析查找成功时的

顺序查找的平均查找长度：在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为ASL==(n+…+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。=niiicp1第

八章查找顺序查找的缺点查找效率低。顺序查找的优点算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。第八章查找二分查找又称折半查找，它是一种效率较高的查找方法。二分查

找要求：要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。二、二分查找第八章查找（1）首先确定该区间的中点位置mid=（2）然后将中间位置记录的键值R[mid].ke

y和所给关键字K进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。high)/2(low+二分查找的基本思想是：第八章查找例：设算法的输入实例中有序的关键字序列为：05，13，19，2

1，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，92lowmidhigh第八章查找第二步：mid=(1+5)/2=305，13，19，21，37

，56，64，75，80，88，92lowmidhigh第三步：mid=(4+5)/2=405，13，19，21，37，56，64，75，80，88，92此时R[mid].key＝K，returnmi

d＝4。lowhighmid第八章查找二分查找算法intBinSearch(SeqListR，KeyTypeK){intlow=1，high=n，mid；while(low<=high){mid=(low+high)/2；/*求中间位置*/i

f(R[mid].key==K)returnmid；if(R[mid].key>K)high=mid-1;elselow=mid+1；}return0；}确定新的查找区间第八章查找二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子

树和右子树。由此得到的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。二分查找判定树第八章查找二分查找判定树的组成如对表R{3，7，11，19，30，115，136，141}的查找过程：371119301151361413711193

0115136141LowmidhighLowmidhigh46782135第八章查找如k=115的记录结点编号为6，处于第二层，则比较次数只有两次就可找到（这样的记录共有两个21=2）；查找第三层的记录需要三次比较（这样的记录共有四个22=4）；查找第k层的记

录需要k次比较（这样的记录共有2k-1个）;等等。假定每个记录的查找概率相等，即为1/n，则其平均查找次数为：ASL==1/nci=1/n(1*20+2*21+3*22+…+k*2k-1+……)=1/ni

*2i-1;而i*2i-1=k2k-2k-1=niiicp1=niiicp1=niiicp1k=niiicp1又根据二叉树的性质：k=log2(n+1)故：ASL=[（n+1）/n]log2(n+1)-1≈log2(n)当n很大时第八章查找二分查找的平均查找长度二

分查找成功时的平均查找长度为：ASLbn≈log2(n)二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：)1lg(+n第八章查找二分查找的优点和缺点虽然二分查找的效率高，但是要将表按

关键字排序（有序表）。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。第八章查找三、分块查找（索引顺序查找）分块查找表存储结构分块查找的特点是：按表内记录的某种属性把表（文件）分成b个块（子表），并建立一个相应的“索引表”，索引表中每个元素

对应一个块，而在索引表中是按其关键字有序，但是每一块中的记录的存放是任意的，块与块之间必须是有序的。即分块查找的前提是：文件由"分块有序"的线性表和索引表组成。第八章查找分块查找表由"分块有序"的线性表和索引表组成。（1）"分块有序"的线性表将表（文件）R[1...n]平均分为

b块；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。（2）索引表抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i块的最大关键字

及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。1、分块查找表的存储结构第八章查找分块查找的基本思想是：（1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待

查的结点在哪一块。（2）然后在已确定的块中进行顺序查找由于块内无序（也可有序），只能用顺序查找。2、分块查找的基本思想第八章查找例：图8.2所示的表及其索引表是满足上述要求的分块查找表，其中R只有18个结点，被分成3块，每块中有6个结点，第一块中最大关键字22小于第二块中最小关键字2

4，第二块中最大关键字48小于第三块中最小关键字49。22488617132212138920334244382448605874498653ID块内最大键值块内第一个元素序号第八章查找（1）先在索引表中查找,来确定关键字等于给定值K=24的结点所在的块因为索引表小，不妨用顺序查找方法查找索引表。

即首先将K依次和索引表中各关键字比较，直到找到第1个关键字大小等于K的结点，由于K<48，所以关键字为24的结点若存在的话，则必定在第二块中；然后，由ID[2].addr找到第二块的起始地址7，从该地址开始在R[7..12]

中进行顺序查找，直到R[11].key=K为止。（2）在所确定的块内查找关键字等于给定值K=30的结点在第二块内查找。因在该块中查找不成功，故说明表中不存在关键字为30的结点。进行下列查找：第八章查找算法分析分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长

度之和。以二分查找来确定块，分块查找成功时的平均查找长度(在索引表中用二分查找，在块内用顺序查找)ASLblk=ASLbn+ASLsq≈log2(b+1)-1+(s+1)/2≈log2(n/s+1)+s/2以顺序查找确定块，分块查找成功时的平均查找长度ASL’blk

=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)第八章查找①在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。分块查找的优点第八章查找8.3树表的查找1、二叉排序树的定义二

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

子树非空，则右子树上所有结点的值均大于根结点的值；（3）左、右子树本身又各是一棵二叉排序树。第八章查找（1）二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。（2）二叉

排序树中，各结点关键字是惟一的。（3）按中序遍历该树所得到的中序序列是一个递增有序序列。二叉排序树的特点第八章查找要查找键值等于k的记录，最先与根结点的键值比较，若二者相等，则查找成功。若k值小于根结点的键值，则继续查找左子树，反

之查找右子树。若沿某条路经碰到一个端点（叶子）还末查到，则查找不成功，这也是静态表的查找。二叉排序树的查找算法：第八章查找二叉排序树的存储结构typedefintKeyType；typedefstructnode{KeyTypekey；/*关键字类型

*/infoTypeotherinfo；/*结点其它信息类型*/structnode*lchild，*rchild；}BSTNode；/*二叉排序树的结点类型*/typedefBSTNode*BSTree；lchildkeyotherinforchild第八章查找在二

叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是：1)若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；2)若二叉排序树T不为空，则将key和根的关键字比较：(a)若二者相等，则说明树中已有此关键字key

，无须插入。(b)若key<T→key，则将key插入根的左子树中。(c)若key>T→key，则将它插入根的右子树中。二叉排序树插入新结点的过程第八章查找二叉排序树插入新结点的算法voidInsertBST(BSTreeTptr，Keytypekey){BSTNode

*f，*p=Tptr；while(p)/*p不空*/{if(p->key==key)return；/*找到了，则不插入*/f=p；/*f是p的双亲*/p=(key<p->key)?p->lchild:p-rchild;}第八章查找p=(BS

TNode*)malloc(sizeof(BSTNode))；p->key=key；p->lchild=p->rchild=NULL；if(TPtr==NULL)/*是空树*/Tptr=p；/*新结点作为根插入*/else/*不是空树*/if(key<f->key)f->lchild=p；/*

新结点作为左孩子插入*/elsef->rchild=p；/*新结点作为右孩子插入*/}第八章查找从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。二叉排序树的生成第八章查找BSTreeCreateBST(

void){BSTreeT=NULL；KeyTypekey；scanf(“％d”，&key)；/*输入一个键值为key的结点*/while(key){InsertBST(&T，key)；/*将键值为key的结点插入到二叉树中*/scanf("％d"，&key)；/*输入

一个键值为key的结点*/}returnT；}第八章查找输入实例(5，3，7，2，4，8)，根据生成二叉排序树算法生成二叉排序树的过程553253753725374253748第八章查找二叉排序树的删除从二叉排序

树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质。第八章查找回顾：二叉排序树的特点1.若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2.若它的右子树非空，则右子树上所有结点的值均大于根结点的值；3.按中序

遍历该树所得到的中序序列是一个递增有序序列。805012060110150557053中序遍历（LVR）：50，53，55，60，70，80，110，120，150第八章查找二叉排序树的删除删除操作的一般步骤:1.查找要删的结点查找时，

令工作指针p指向当前访问到的结点，parent指向p的双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。2.如果找到删除结点*p应将*p的子树(若有)仍连接在树上且保持二叉排序树的性质不变FPCPRCLQQLSLS坚持的基本原则：删结点时，保证二叉排序

树的性质不变。第八章查找想：从一棵二叉排序树中删除一个结点会出现哪几种情况？分析：要删除二叉排序树中的*p结点，分三种情况：❑①*p是叶子❑②*p只有一个子树FPCPRCLQQLSLS注意：此时有四种情况（*p本身可以为左、

右子树，且*p的子树也可以为左、右子树）③*p有两个子树第八章查找1．*p只有左子树，用*p的左子树的根代替*pSQPLP中序遍历：QSPLPSQPL中序遍历：QSPL(2)SPPLQ中序遍历：PLPSQSPLQ中序遍历：PLSQ(1)if(!p-

>rchild){//右子树空则只需重接它的左子树tmp=p;p=p->lchild;free(tmp);}*p只有一个子树的情况：第八章查找中序遍历：PPRSQSPRQ中序遍历：PRSQ(3)SPPRQ中序遍历：QSPPRSQPR中序遍历：QSPR

(4)SQPRP2.*p只有右子树，用*p的右子树的根代替*pif(!p->lchild){/左子树空则只需重接它的右子树tmp=p;p=p->rchild;free(tmp);}第八章查找*p有两个子树的情况：分析：针对*p有两个子树的情况

，把*p的两个子树合并为一棵树，然后将其连接到*p的双亲上。1.删除问题就转化为第②种情况。2.要解决的问题转化为如何将两棵二叉排序树合并为一棵二叉排序树。FPCPRCLQQLSLS第八章查找问题：如何将两棵二叉排序树合并为一棵二叉排序树?思考：还有没有其它的合并方法？S

FPCPRCLQQLSLFPCPRCLQQLSLS分析：据二叉排序树的性质：右子树的值大于左子树的值。因此，只要找到左子树中值最大的结点（左子树中最右边的结点，该结点一定没有右子树），使其成为右子树的双亲。第八章查找SFPCPRCLQQLSLFPCPRCLQQLS

LStmp=p->lchild;//1.要删除结点的左子树while(tmp->rchild!=0)tmp=tmp->rchild;//2.找到左子树中最右边的结//点，即最大的结点tmp->rchild=p->rchild;//3.左子树中最右边的成为右//子树的双亲tmp=p;p=p

->lchild;//5.变为第二种情况处理(删除)free(tmp);//6.释放要删除的结点第八章查找FPCPRCLQQLMS小结：二叉排序树的删除要删除二叉排序树中的*p结点,分三种情况：*p为叶子结点*p只有左子树或右子树*p只

有左子树，用*p的左孩子代替*p*p只有右子树，用*p的右孩子代替*p*p左、右子树均非空针对*p有子树的情况，把*p的两个子树合并为一棵树，然后将其连接到*p的双亲上。第八章查找二叉排序树删除算法voidDelBSTNode(BSTreeTp

tr，KeyTypekey){BSTNode*parent=NUll，*p=*Tptr，*q，*child；while(p){if(p->key==key)break；parent=p；p=(key<p->k

ey)?p->lchild：p->rchild；}if(!p)return；/*找不到被删结点则返回*/q=p；/*找到时,q记住被删结点p*/if(q->lchild&&q->rchild)for(parent=q，p=q->rchild；p->lc

hild；parent=p，p=p->lchild)；/*找被删结点的后继*/if(!parent)Tptr=child；else{if(p==parent->lchild)parent->lchild=chil

d；elseparent->rchild=child；if(p!=q)q->key=p->key；}free(p)；}child=(p->lchild)?p->lchild：p->rchild；第八章查找二叉排序树上的查找在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范

围的过程。递归的查找算法：BSTNode*SearchBST(BSTreeT，KeyTypekey){if(T==NULL||key==T->key)returnT；if(key<T->key)returnSearchBST(T->lchild，key)；elseretu

rnSearchBST(T->rchild，key)；}第八章查找在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：(a)在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，也是

(n+1)/2。(b)在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是log2n。(c)插入、删除和查找算法的时间复杂度均为O(log2n)。第八章查找二叉排序树和二分

查找的比较就平均时间性能而言，二叉排序树上的查找和二分查找差不多。就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(log2n)，因此更有效。二分查找所涉及的有序表是一个向量

，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其存储结构。第八章查找①n个

结点的平衡的二叉排序的高度H（即lgn）比B-树的高度h约大lgt倍。例如m=1024，则lgt=lg512=9。此时若B-树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B-树高度越小。②若要作为内存中的查找表，B-树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此

。因为查找等操作的CPU计算时间在B-树上是O(mlogtn)=0(lgn·(m/lgt))性能分析第八章查找8.4散列(Hash)技术设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。散列方法是:使用函数h将U映射到表T

[0..m-1]的下标上。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。散列表(HashTable)第八章查找其中：①称h为散列函数(HashFunc

tion)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。②T为散列表(HashTable)。③h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。④将结点按其关键字的散列地址存储到散列表中的过

程称为散列(Hashing)第八章查找冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置(存储地址)上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。散列表的冲突现象第八章查找①其

一是记录的个数≤存储空间的大小②其二是选择合适的散列函数。怎么样才能完全避免冲突？最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：第八章查找通常，哈希函数h是一个压缩映像。虽然实际发生的键值个数|K|≤m，但|U|>m，故无论怎样设计h，也不

可能完全避免冲突。冲突不可能完全避免第八章查找冲突除了与h相关外，还与表的填满程度相关。设m为表长，n为表中填入的结点数（记录数），则将α=n/m定义为散列表的装填因子(LoadFactor)。α越大，

表越满，冲突的机会也越大。通常取α≤1。影响冲突的因素因此：要尽量减少冲突，就要选择好的哈希函数h(key)和选择恰当的哈希表的长度m（既选择好的α=n/m）。第八章查找常用散列函数平方取中法取关键字的平方值的中间几位数先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散

列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。第八章查找intHash(intkey)/*假设key是4位整数*/{key*=key；key/=100；/*先求平方值，后去掉末尾的两位数*/ret

urnkey％1000；/*取中间三位数作为散列地址返回*/}平方取中法用C程序实现如下：第八章查找取关键字或关键字的某个线性函数为哈希地址即：H(k)=key或H(k)=a*key+b其中a，b为常数直接定址法第八章查找是简单常用的一种方法。它是

以表长m来除关键字，取其余数作为散列地址,即h(key)=key％m该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数除余法第八章查找该方法包括两个步骤：首先用关键字key乘上某个常数A(0<A<1)，并抽取出k

ey×A的小数部分；然后用m乘以该小数后取整。相乘取整法第八章查找相乘取整法的C程序如下：intHash(intkey){doubled=key*A；/*不妨设A和m已有定义*/return(int)(m*(d-(int)d))；/*(int)表示强制转换后面的表达式为整数*

/}第八章查找选择一个随机函数，取关键字的随机函数值为它的散列地址即h(key)=random(key)其中random为伪随机函数，但要保证函数值是在0到m-1之间。随机数法第八章查找处理冲突的方法一、开放地址法解决冲突的方法假

设哈希表的地址集为0~m-1，当冲突发生时，即由关键字得到的哈希地址为j(0≤j≤m-1)的位置上已存有记录，则处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。为此在处理冲突的过程中，需采用某种探测技术在散列表中形成一个探测序列

Hi,i=1,2,3,……，k(Hi∈[0,m-1])。沿此序列逐个单元地查找，直到找到给定的或者碰到一个开放的地址(即该地址单元为“空”)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键

字，即查找失败。第八章查找开放地址法的一般形式为：Hi=(h(key)+di)％m1≤i≤m-1其中h(key)为哈希函数，m为哈希表长，d为增量序列，它可有下列几种取法：di=1，2，3，……，m-1di=12，-12,22，-22,32，

…，±k2;(k=m/2)di=伪随机数序列第八章查找按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。线性探查法(LinearProbing)该方法的基本思想是：将散列表

T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：d，d+l，d+2，…，m-1，0，1，…，d-1即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探

查到T[d-1]为止。形成探测序列的方法开放地址法解决冲突第八章查找②双重散列法(DoubleHashing)该方法是开放定址法中最好的方法之一，它的探查序列是：hi=(h(key)+i*h1(key))％m0≤i≤m-1即di=i*h1(key)即探查序列为：d=h(

key),(d+h1(key))％m,(d+2h1(key))％m，…，等。开放地址法解决冲突第八章查找若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。二、

拉链法解决冲突是将所有关键字为同义词的结点链接在同一个单链表中。第八章查找例：已知一组关键字为（26，36，41，38，44，15，68，12，06，51），取表长为13，用拉链法解决冲突构造这组关键字的散列表如右图0123458697101112∧∧∧∧∧∧26∧15

41∧1236∧68∧06∧3844∧51∧H（key）=key%13拉链法解决冲突第八章查找012345869710111226∧∧15∧68∧44∧06∧∧∧∧36∧1241∧36∧3851∧上题也可以如下做

：m个头指针组成的指针数组T的每个元素改造成两个域，一个存储基本哈希表内容；另一个为指针域，指向同义词的链表。拉链法解决冲突第八章查找拉链法解决冲突拉链法的优点(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；(1)拉链法处理冲突简单，且无堆积现象，即

非同义词决不会发生冲突，因此平均查找长度较短；第八章查找(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；(4)在用拉链法

构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。第八章查找拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。拉链法解决冲突

拉链法的缺点第八章查找8.4.4散列表上的运算散列表类型说明：#defineNIL-1#defineM997typedefstruct{KeyTypekey；InfoTypeotherinfo；}NodeType；TypedefNodeTypeHashTable[m]；第八章查找散列表的查找过程和

建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空(是开放的)，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一

个地址。如此反复下去基于开放地址法的查找算法第八章查找开放地址法一般形式的函数表示intHash(Keytypek，inti){return(h(K)+increment(i))％m；}若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K

)和increment(i)可定义为：inth(KeytypeK){returnK％m；}intincrement(inti){returni;}求哈希函数值的算法第八章查找intHashSearch(HashTableT，KeytypeK，int*pos){inti=0；do{*pos=Has

h(K，i)；/*求探查地址hi*/if(T[*pos].key==K)returnl；/*查找成功返回*/if(T[*pos].key==NIL)return0；/*查找到空结点返回*/}while(++i<m)/*最多做m次探

查，m是表长*/return-1；/*表满且未找到时，查找失败*/}通用的开放定址法的散列表查找算法：第八章查找基于开放地址法的插入及建表voidHashlnsert(HashTableT，NodeTypenew){/*将新结点

new插入散列表T[0..m-1]中*/intpos，sign；sign=HashSearch(T，new.key，&pos)；/*在表T中查找new的插入位置if(!sign)/*找到一个开放的地址pos*/T[*pos]=new；/*插入新结点new，插入成功*/el

se/*插入失败*/if(sign>0)printf(“duplicatekey!”)；/*有重复的关键字*/elseError("hashtableoverflow!")；/*表满错误，终止程序执行*/}第八章查

找voidCrHTable(HashTableT，NodeTypeA[]，intn){/*根据A[0..n-1]中结点建立散列表T[0..m-1]*/inti；if(n>m)/*用开放定址法处理冲突，装填因子

(α=n/m)<1*/Error("Loadfactor>1")；for(i=0;i<m；i++)T[i].key=NULL；/*将各关键字清空，使地址i为开放地址*/for(i=0;i<n；i++)/*依次将A[0..

n-1]插入到散列表T[0..m-1]中*/Hashlnsert(T，A[i])；/*调用插入算法，将A[i]插入哈希表Ｔ中＊／}建哈希表第八章查找基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为UNLL，而应

该将其置为特定的标记DELETED。删除第八章查找插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字的记录。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过

散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。性能分析