数据结构PPT(第9章 查找)

第9章查找1.掌握顺序查找、二分查找和分块查找的方法。2.掌握二叉排序树的相关运算和查找过程。3.理解平衡二叉树的建树方法。4.掌握哈希表的建立方法和查找过程。5.掌握各种查找方法在等概率下的平均查找长度的计算方法。学习要点基本概念

查找表：是由同一类型的数据元素构成的集合，由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。

有关操作

查询某个“特定的”数据元素是否在查找表中；

在查找表中插入一个数据元素；

从查找表中删去某个数据元素。查找表的分类静态查找表：仅作查询和检索操作的查找表。动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。

关键字是数据元素中某个数据项的值，用以标识一个数据元素。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。基本概念查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。基本概念数据元素类型定义为：typedefstruct{KeyTypekey;//关键字域…//其他域}ElemType;基本概念9.1.1顺序表的查找应用范围：以顺序表或线性链表表示的静态查找表，表内元素之间无序。顺序查找基本思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；若直至第一个记录，其关键字和给定值比较都不等，则查找不成功。顺序存储结构的表示：

typedef

struct{

ElemType*elem;

intlength;}SSTable;9.1静态查找表int

Search_Seq(StableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素

ST.elem[0].key=key;//哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;//查找不成功时i为0}//Search_Seq免去查找过程中每一步都要检测整个表是否查找完毕顺序查找算法int

Search_Seq(StableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素

for(i=0;i<ST.length;++i)

if(ST.elem[i].key==key)returni;return(0);//查找不成功时i为0}//Search_Seq顺序查找算法8012n-3n-2n-1nST.elem

key例1：在下表中查找key=8的结点。………………100100713iiiiiii查找不成功，i=08012n-3n-2n-1nST.elem

key例2：在下表中查找key=8的结点。………………100100813iii查找成功，i=n-2

举例说明1n查找成功情况下：设每个结点的查找概率相等ASL＝∑(n-i+1)＝(n+1)/2i=1n

和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度。性能分析折半查找查找方式：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。

初始时，令low=1，high=n，mid=(low+high)/2。

让k与mid指向的记录比较若k==ST.elem[mid].key，查找成功；

若k<ST.elem[mid].key，则high=mid-1；

若k>ST.elem[mid].key，则low=mid+1。重复上述操作，直至low>high时，查找失败。9.1.2有序表的查找

举例说明(1)low找key=215113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow找key=705113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhigh

举例说明(2)low5113219321437556664775880988109211midhighlow5113219321437556664775880988109211high

举例说明(2)intSearch_bin(SStableST,KeyTypekey){//在有序表ST中折半查找关键字等于key的数据元素low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(ST.elem[mid].key,key)returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0；}//Search_Bin折半查找算法判定树：描述查找过程的二叉树。有n个结点的判定树的深度为log2n+1。

折半查找法在查找过程中进行的比较次数最多不超过log2n+1。其ASL=log2(n+1)-1。

折半查找的优点是比较的次数少，查找速度快，但前提是该表首先要进行排序，而排序是一种很费时运算，并且折半查找只适用于顺序存储的有序表，不适用于链表存储的有序表。5619800521886413753792折半查找性能分析5113219321437556664775880988109211索引顺序查找(分块查找)

查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。适用条件：分块有序表假设按元素关键字升序方式组织表中各块，则要求第一块中任一结点的关键字值都小于第二块中所有结点的关键字值；第二块中任一结点的关键字值都小于第三块中所有结点的关键字值；如此类推。然后选择每块中的最大(或最小)关键字值组成索引表。索引表中的结点个数等于线性表被分割的块数。9.1.4索引顺序表的查找1234567891011121314151617182212138920

334244382448

6058745786532248861713索引表查38最大关键字起始地址表及其索引表LLASLwbbs+=其中：Lb是查找索引表确定所在块的平均查找长度；

Lw是在块中查找元素的平均查找长度。若将表长n为的表平均分成b块，每块含s个记录，并设表中每个记录的查找概率相等，则：用顺序查找确定所在块用折半查找确定所在块ASLbs=1)(21ssn++ASLbs=2)1(log2ssn++分块查找性能分析9.2动态查找表什么是二叉排序树？或者是一棵空树；或者是具有下列性质的二叉树：1.若左子树不空，则左子树上所有结点值均小于根结点值；2.若右子树不空，则右子树上所有结点值均大于根结点值；3.根结点的左、右子树也分别为二叉排序树。45125333710024619078若二叉排序树为空，则查找不成功；否则1.若给定值等于根结点的关键字，则查找成功；2.若给定值小于根结点的关键字，则继续在左子树上进行查找；3.若给定值大于根结点的关键字，则继续在右子树上进行查找。具体实现如下：BiTree

SearchBST(BiTree

T,KeyTypekey){if((!T)||(EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}二叉排序树查找算法例如：在下图中分别查找关键字值等于37，61和95过程。45125333710024619078从上述查找过程可见，在查找过程中，生成了一条查找路径：1.从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点，表明查找成功。2.或者从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止，表明查找不成功。二叉排序树查找过程基本思想：在每一步插入过程中，二叉排序树中原有的结点位置均不动，只是将待插入的结点作为一个叶结点插入到适当的位置，使得树中任何结点与其左、右子树结点之间的关系仍然满足二叉排序树的性质，向二叉树T插入一个新结点s的过程为：若T为空的二叉树，则将新结点作为根结点插入。若新结点s的值等于二叉排序树的根结点，说明该结点已存在，不需要插入。若将新结点s的值小于二叉排序树T的根结点，则将s插入到T的左子树中去。若新结点s的值大于二叉排序树T的根结点，则将s插入到T的右子树中去。二叉排序树的插入操作是一个递归过程。二叉排序树插入算法思想

StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)//若查找成功，则指针p指向该数据元素结点，返回TRUE，否则p指向查找路径上访问的最后一个结点并返回FALSE，f是指向T的双亲

{if(!T){p=f;returnFALSE;}elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}具体实现(1)StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseif(LT(e.key,p->data.key))p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE;}具体实现(2)2712从空树出发，经过一系列的查找插入操作后，便可生成一棵二叉排序树。例对于关键字序列{10，18，3，8，12，2，7}，构造一棵BST。101838注意：对于同样的数据，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大，这样必然会降低查找性能。建立二叉排序树中序遍历二叉排序树便可得到一个关键字的有序序列，也就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。对下图所示的二叉排序进行中序遍历，结果为(2，3，7，8，10，12，18)。每次插入的新结点都是二叉排序树上新的叶子结点，不必移动其它结点，仅需修改某个结点的指针。这相当于在一个有序列上插入一个记录而又不需要移动其他记录。二叉排序树既拥有折半查找的特性，又采用链式存储。7212101838

结论和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。二叉排序树的删除删除叶子结点，只需将其双亲结点指向它的指针置为空，再释放它即可。如：删除关键字值为7的结点。1018381227删除叶子结点删除的结点只有左子树或者只有右子树，则使其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。如：(1)删除关键字值为2的结点，它只有右子树。(2)删除关键字值为18的结点，它只有左子树。1018581223删除的结点只有左子树或只有右子树RQD中序遍历：PL—D—R—Q

删除后：PL—R—QPLRQPLRDQ中序遍历：Q—R—PL—D

删除后：Q—R—PLPLRQPLRQD中序遍历：D—PR—R—Q

删除后：PR—R—QPRRQPRRDQ中序遍历：Q—R—D—PR

删除后：Q—R—PRPRRQPR

具体解释删除叶结点和删除的结点只有左子树或者只有右子树这两种操作，可通过下面语句实现。if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}1018581223p

具体实现方法一：首先将结点D的右子树链接到其中序前驱结点(结点D的左子树中“最右下”且右指针域为空的结点)的右指针域，然后把结点R(结点D的双亲结点)指向结点D的指针链接到结点D的左子树上即可。RDQRRDRCCLQLGLGpfRQRRDRCCLQLGLGf该二叉排序树的中序遍历结果为：CL→C→QL→Q→GL→G→D→DR→R→RR删除的结点既有左子树又有右子树方法二：把结点D的中序前驱结点G的值赋给结点D，因为该中序前驱结点G只有左子树GL，然后将结点G的双亲结点的右指针链接到GL即可。RDQRRDRCCLQLGLGpfRGQRRDRCCLQLGLpf该二叉排序树的中序遍历结果为：CL→C→QL→Q→GL→G→D→DR→R→RR删除的结点既有左子树又有右子树删除的结点既有左子树又有右子树，可通过下面语句实现。q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);RDQRRDRCCLQLGLGpf

具体实现

BST上查找过程，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度+1，最大次数不超过树的深度。但含有n个结点的BST却不唯一。因此，含有n个结点的BST的ASL和树的形态有关。最差情况是退化为单支树，ASL=(n+1)/2(同顺序查找)。最好情况与折半查找相同，与log2n成正比。12452453123793(45,24,53,12,37,93)2437455393(12,24,37,45,53,93)ASL(a)=(1+2+2+3+3+3)/6=14/6ASL(b)=(1+2+3+4+5+6)/6=21/6

查找分析平衡二叉树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树高度之差的绝对值不大于1。若平衡因子定义为结点左子树的高度减去右子树的高度，则平衡二叉树所有结点的平衡因子只可能是-1、0、1的二叉排序树。例如：20210平衡树非平衡树-2-20-100101平衡二叉树

采取的方法是在向平衡二叉树插入结点时进行平衡化旋转。基本思想为：假定向平衡树插入一个结点后破坏了其平衡性，则首先要找出唯一一棵最小不平衡子树，然后再调整该子树中有关结点之间的链接关系，使之成为一棵新的平衡二叉树。最小不平衡子树被调整为平衡子树后，整个二叉排序树又成为一棵平衡树。

最小不平衡子树是指离插入结点最近，且平衡因子绝对值大于1的祖先结点作为根的子树。027511018410-110127511018410-211160构造平衡二叉树的方法(1)单向右旋平衡处理(LL型)：新插入结点在A的左子树根结点的左子树上。A的平衡因子由1增至2，导致失衡。调整规则：将结点A的左孩子B向上旋转成为新二叉树的根，将结点A及其右子树向右下旋转成为结点B的右子树，而结点B原来的右子树BR则成为结点A的左子树。(进行一次顺时针旋转)调整方法分四种情况h+1h-1ABARBRBLh-10+2+1hh-1ABARBRBL00具体实现：lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;p(2)单向左旋平衡处理(RR型)：新插入结点在A的右子树根结点的右子树上。A的平衡因子由-1增至-2，导致失衡。调整规则：将结点A的右孩子B向上旋转成为新二叉树的根，将结点A及其左子树向左下旋转成为结点B的左子树，而结点B原来的左子树BL则成为结点A的右子树。(进行一次逆时针旋转)调整方法分四种情况-2hh-1h-1BABRBLAL-10-1h0BABRBLALh-10具体实现：rc=p->rchild;p->rchild=rc->lchild;rc->rchild=p;p=rc;p(3)先左后右平衡处理(LR型)：新插入结点在A的左子树根结点的右子树上。A的平衡因子由1增至2，导致失衡。调整规则：将A的左孩子的右子树的根结点C旋转到结点A的位置成为新二叉树的根，将结点B及其左子树向左下旋转成为C的左子树，而C结点原来的左子树CL则作为结点B的右子树；将结点A及其右子树向右下旋转成为结点C的右子树，C结点原来的右子树CR作为结点A的左子树。(需进行两次旋转，先逆时针后顺时针)调整方法分四种情况+2-1+1h-1ABARCLBLh-10CCRh-20h-1+1+2h-1CBARCLBLh-10CRh-2A+2h-10CBARCLBL0CRA-1将A的左孩子的右子树的根结点C旋转到结点A的位置成为新二叉树的根，将结点B及其左子树向左下旋转成为C的左子树，而C结点原来的左子树CL则作为结点B的右子树。(第一次逆时针旋转)将结点A及其右子树向右下旋转成为结点C的右子树，C结点原来的右子树CR作为结点A的左子树。(第二次顺时针旋转)调整过程调整方法分四种情况(4)先右后左平衡处理(RL型)：新插入结点在A的右子树根结点的左子树上。A的平衡因子由-1增至-2，导致失衡。调整规则：它与LR旋转情况正好对称的。调整实例假设一组数据对象为(40，28，16，56，50，32，30，63)，按次序插入每个对象生成一棵平衡二叉树，根据插入过程指出每一步的调整类型：“单向左旋转”、“单向右旋转”、“先左后右旋转”、“先右后左旋转”、“无”。解释：左子树的左子树上插入→“单向右旋转”右子树的右子树上插入→“单向左旋转”左子树的右子树上插入→“先左后右旋转”右子树的左子树上插入→“先右后左旋转”9.3哈希表9.3.1什么是哈希表？哈希查找：又叫散列查找，利用哈希函数进行查找的过程。其基本思想是在记录的存储地址和它的关键字之间建立一个确定的对应关系。这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。按这种思想建立的表称为哈希表。例假设有一批关键字序列18，75，60，43，54，90，46，给定散列函数H(k)=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为：

H(18)=18%13=5，H(75)=75%13=10，H(60)=60%13=8H(43)=43%13=4，H(54)=54%13=2，H(90)=90%13=12H(46)=46%13=7于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT(散列表)中，具体表示为：90756046184354151413121110987654321

0HT其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H(75)=75%13=10，则可以在HT[10]中找到75。举例说明上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址。这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突(collision)。即key1≠key2，而f(key1)=f(key2)。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。

冲突问题1.直接定址法

可表示为H(key)=a*key+b，其中a、b均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。实际中使用此方法较少。例关键字集合为{100，300，500，700，800，900}，选取哈希函数为H(key)=key/100，则在哈希表中存放如下：

9.3.2哈希函数的构造方法01001230034500567007800890092.数字选择法对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。例如，对如下的关键字序列：

43010

4681015355

43010

1701128352

43010

3720818350

430102690605351

．．．．．．通过对上述关键字序列分析，发现前5位相同，第6、8、10位上的数字变化多些，若规定地址取3位，则散列函数可取它的第6、8、10位。于是有：

H(430104681015355)＝480H(430101701128352)＝101H(430103620805351)＝328H(430102690605351)＝2969.3.2哈希函数的构造方法3.平方取中法取关键字平方后的中间几位为散列函数地址。在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。如图，随机给出一些关键字，并取平方后的第2到4位为函数地址。9.3.2哈希函数的构造方法关键字0100

(关键字)20010000函数地址010110012001210000144000021044011602061137040043105413703104.折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为散列函数地址，称为折叠法。例如：假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有5355+8101+1046+430=14932，舍去高位，则有H(430104681015355)＝4932为该身份证关键字的散列函数地址。9.3.2哈希函数的构造方法5.除留余数法该方法是用关键字序列中的关键字k除以p(p是小于等于散列表长度m)所得余数作为散列函数的地址，即有H(k)＝k％p。

除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的p值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。

一般情形下，设散列表中允许的地址数为m，取一个不大于m，但最接近于或等于m的质数p。9.3.2哈希函数的构造方法由于散列存贮中选取的散列函数不是线性函数，故不可避免地会产生冲突，下面给出常见的解决冲突方法。1．开放定址法开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突的发生。9.3.3解决冲突的方法假设散列表的地址为0∽m-1，则散列表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，…，m-1(当达到表尾m-1时，又从0，1，2，….开始探查)等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。探查下一位置的公式为di=(di-1+1)%m(1≤i≤m-1)，最后将冲突位置的关键字存入di地址中。线性探查法例给定序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数H(k)=k%13，散列表空间地址为0∽12，用线性探查法建立散列存贮结构。得到的散列表如下图所示。

H(19)=19%13=6;H(14)=14%13=1;H(23)=23%13=10;H(1)=1%13=1;H(68)=68%13=3;H(20)=20%13=7;H(84)=84%13=6;H(27)=27%13=1;H(55)=55%13=3;H(11)=11%13=11;H(10)=10%13=10;H(79)=79%13=1;线性探查法012345678910111219142316820842755111079方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，直到冲突不再发生。即：Hi=Rhi(key)i=1,2,……,k其中：Rhi——不同的哈希函数