数据结构简明教程（第3版）课件 第8章查找(上)

第8章查找8.1

查找的概念8.2静态查找表8.3动态查找表8.4哈希表查找第8章查找1/908.1查找的概念查找是对已存入计算机中的数据所进行的一种运算，采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中数据元素是按何种方式组织的。为了提高查找速度，常常用某些特殊的数据结构来组织表，或对表事先进行诸如排序这样的运算。因此在研究各种查找方法时，必须弄清：①数据结构是什么？②对表中关键字的次序有何要求，例如，是对无序表查找还是对有序表查找？8.1查找的概念2/90若在查找的同时对表做修改运算（如插入和删除），合适这样操作的表称之为动态查找表（既适合查找，也适合删除和插入操作）。否则称之为静态查找表（适合查找，不适合删除和插入操作）。8.1查找的概念3/90由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL（AverageSearchLength）定义为：其中，n是查找表中元素的个数。pi是查找第i（1≤i≤n）个元素的概率，一般地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n，ci是找到第i个元素所需进行的比较次数。8.1查找的概念4/90平均查找长度分为：成功查找情况下的平均查找长度ASLsucc，指在表中找到指定关键字的元素平均所需关键字比较的次数。不成功查找情况下的平均查找长度ASLunsucc，指在表中找不到指定关键字的元素平均所需关键字比较的次数。8.1查找的概念5/908.2静态查找表静态查找表采用顺序存储结构，顺序表是一种典型的顺序存储结构，本节静态查找表采用顺序表组织方式，并假设顺序表中数据元素类型的定义如下：typedefintKeyType;typedefstruct{

KeyTypekey; //存放关键字,KeyType为关键字类型

ElemTypedata; //其他数据,ElemType为其他数据的类型}SqType;8.2静态查找表6/908.2.1顺序查找顺序查找又称为线性查找，是一种最简单的查找方法。基本思路：从表的一端开始顺序扫描顺序表，依次将扫描到的元素关键字和给定值k相比较，若当前扫描到的元素关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的元素，则查找失败。8.2静态查找表7/90

【例8.1】在关键字序列为（3,9,1,5,8,10,6,7,2,4）的顺序表采用顺序查找方法查找关键字为6的元素。39158106724i=0第1次比较39158106724i=1第2次比较39158106724i=2第3次比较8.2静态查找表顺序查找过程如下：8/9039158106724i=3第4次比较39158106724i=4第5次比较39158106724i=5第6次比较39158106724i=6第7次比较8.2静态查找表9/90顺序查找算法如下（在顺序表R[0..n-1]中查找关键字为k的元素，成功时返回找到的元素的逻辑序号，失败时返回0）：intSqSearch(SqTypeR[],intn,KeyTypek)

//顺序查找算法{inti=0;

while(i<n&&R[i].key!=k)

//从表头往后找

i++;

if(i>=n)

//未找到返回0 return0;

else returni+1;

//找到后返回其逻辑序号i+1}8.2静态查找表关键字比较10/90

算法分析：对于含有n个元素的顺序表，元素的查找在等概率的前提下，查找成功的概率pi=1/n。

第1个元素（序号为0的元素）查找成功需比较1次

第2个元素（序号为1的元素）查找成功需比较2次

……

第n个元素（序号为n-1的元素）查找成功需比较n次

即成功找到第i（1≤i≤n）个元素所需关键字比较次数Ci=i，所以查找成功时的平均查找长度为：8.2静态查找表11/90任何一次不成功的查找，都需要和顺序表中n个元素的关键字都比较一次，所以：

ASLunsucc=n。8.2静态查找表顺序查找的时间复杂度为O(n)。12/908.2.2折半查找折半查找又称二分查找，它是一种效率较高的查找方法。折半查找要求顺序表中元素是有序的，即表中元素按关键字有序，假设有序顺序表是递增有序的。

8.2静态查找表13/90

基本思路：设R[low..high]是当前的查找区间，首先确定该区间的中点位置mid=

(low+high)/2

；然后将待查的k值与R[mid].key比较：若R[mid].key=k，则查找成功并返回该元素的逻辑序号。若R[mid].key>k，则由表的有序性可知新的查找区间是左子表R[low..mid-1]。若R[mid].key<k，则新的查找区间是右子表R[mid+1..high]。下一次查找是针对新的查找区间进行的。8.2静态查找表14/90

【例8.2】在有序序列（2,4,7,9,10,14,18,26,32,40）中采用折半查找方法查找关键字为7的元素。

0123456789low=02479101418263240high=9mid=47<100123456789low=02479101418263240high=3mid=101234567897>4low=22

479101418263240high=3mid=27=7成功！8.2静态查找表折半查找过程如下：15/90折半查找算法如下（在有序顺序表R[0..n-1]中进行折半查找，成功时返回元素的逻辑序号，失败时返回0）：intBinSearch(SqTypeR[],intn,KeyTypek)//拆半查找算法{intlow=0,high=n-1,mid;while(low<=high) //当前区间存在元素时循环

{mid=(low+high)/2; //求查找区间的中间位置

if(R[mid].key==k)

returnmid+1; //找到后返回其逻辑序号mid+1

elseif(R[mid].key>k) //继续在R[low..mid-1]中查找

high=mid-1;

else

//R[mid].key<k

low=mid+1; //继续在R[mid+1..high]中查找

}

return0;

//若当前查找区间没有元素时返回0}8.2静态查找表k与R[mid]最多两次比较：只计1次（这样做不影响时间复杂度）16/90

算法分析：折半查找过程构成一个判定树，把当前查找区间的中间位置上的元素作为根，左子表和右子表中的元素分别作为根的左子树和右子树。

n=10即R[0..9]的全部查找情况：R[4]0～9R[0]0～0R[2]2～3R[1]0～3R[7]5～9R[5]5～6R[6]6～6R[8]8～9R[9]9～9查找成功查找不成功8.2静态查找表R[3]3～317/90当折半查找表中元素个数n较大时，可以将整个判定树近似看成是一棵满二叉树，所有的叶子结点集中在同一层。不考虑外部结点，树的高度h=

log2(n+1)

。所以有：ASLunsucc=h=

log2(n+1)

8.2静态查找表折半查找的时间复杂度为O(log2n)。18/90

【例8.3】已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较的次数最多是（）。

A.4

B.5 C.6

D.78.2静态查找表h=

log2(n+1)

=h=

log217

=519/908.2.3索引查找1.基本索引查找一般地，索引存储结构需要在主数据表基础上建立一个关于索引项的索引表。索引表的结构为：

（索引关键字，该关键字元素在主数据表中的相对地址）其中索引关键字项有序排列。8.2静态查找表20/908.2静态查找表地址索引关键字对应地址0k111k20┇┇┇n-1kn-1…索引表主数据表地址索引关键字其他数据项0k2…1k1…┇┇┇n-1kn-1…索引存储结构=主数据表+索引表21/90在索引存储结构中查找关键字为k的元素的过程：先在索引表中查找，由于索引表是按关键字有序排列的，所以可以采用折半查找。当找到后通过其对应地址直接在主数据表中找到其元素。地址索引关键字对应地址0k111k20┇┇┇n-1kn-1…索引表主数据表地址索引关键字其他数据项0k2…1k1…┇┇┇n-1kn-1…8.2静态查找表22/902.分块查找主数据表中的数据呈现这样的规律：主数据表可以分成若干块，每一块中的元素是无序的，但块与块之间元素是有序的，即前一块中的最大关键字小于（或大于）后一块中的最小（或最大）关键字值。索引表中的一项对应主数据表中的一块，索引项由关键字域和链域组成，关键字域存放相应块的最大关键字，链域存放指向本块第一个元素的指针，索引表按关键字值递增（或递减）顺序排列。在这种索引结构中的查找称为分块查找。用索引表表示这种特性8.2静态查找表23/90首先确定待查找的元素属于哪一块，即查找其所在的块。然后在块内查找相应的元素。由于索引表是递增有序的，可以对索引表进行折半查找，当索引表中元素个数（即分块的块数）较少时，也可以对索引表采用顺序查找方法。在进行块内查找时，由于块内元素无序，所以只能采用顺序查找方法。8.2静态查找表分块查找过程分为两步进行：24/90例如，有一个关键字序列为（9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82），给出分块查找的索引结构和查找算法。8.2静态查找表应用示例25/90（9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82）9,22,12,1435,42,44,3848,60,58,4778,80,77,82整个数据是无序的可以划分为4块：块之间是有序的012345678910111213141592212143542443848605847788077822203444760811821215主数据表索引表8.2静态查找表26/90查找48：在索引表中找到关键字恰好大于等于48的块：第3块在第3块中顺序查找：逻辑序号为92203444760811821215索引表01234567891011121314159221214354244384860584778807782主数据表分块查找实际上进行两次查找！性能介于顺序查找和二分查找之间。8.2静态查找表27/90

【例8.5】设数据序列中有100个元素，待查找元素的关键字k=47。如果在查找过程中，和k进行比较的元素依次是27，47，36，28，47，则所采用的查找方法可能是（）。A.顺序查找B.折半查找

C.分块查找D.都不是只有分块查找需要进行两次查找。第一次与47的比较是在索引表中查找，第2次与47的比较是在对应块（该块中最大关键字为47，并且所有关键字均大于27）中查找。C。8.2静态查找表28/908.3动态查找表8.3.1二叉排序树二叉排序树是一种特殊的二叉树，在一般二叉树中，区分左子树和右子树，但结点的值是无序的。在二叉排序树中，不仅区分左子树和右子树，而且整个树的结点是有序的。1.二叉排序树的定义8.3.1二叉排序树29/90

二叉排序树又称二叉查找树，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树：若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；若它的右子树非空，则右子树上所有结点的关键字均大于根结点的关键字；左、右子树本身又各是一棵二叉排序树。8.3.1二叉排序树30/90一棵二叉排序树示例：42135768根结点最左下结点，即为关键字最小的结点根结点最右下结点，即为关键字最大的结点特点：中序序列：1，2，3，4，5，6，7，8中序序列是一个递增有序序列！8.3.1二叉排序树31/90二叉排序树的二叉链存储结构的结点的类型声明如下：typedefstructbstnode{KeyTypekey; //存放关键字

ElemTypedata; //存放其他数据

structbstnode*lchild,*rchild; //存放左、右孩子的指针}BSTNode;8.3.1二叉排序树32/902.二叉排序树的基本运算二叉排序树的基本运算如下：创建二叉排序树CreateBST(bt,str,n)：由关键字数组str建立一棵二叉排序树bt；销毁二叉排序树DestroyBST(bt)：释放二叉排序树bt中所有结点的内存空间。查找结点BSTSearch(bt,k)：在二叉排序树bt中查找关键字为k的结点；插入结点BSTInsert(bt,k)：在二叉排序树bt中插入关键字为k的结点；输出二叉排序树DispBST(bt)：采用括号表示法输出二叉排序树bt；删除结点BSTDelete(bt,k)：在二叉排序树bt中删除关键字为k的结点。8.3.1二叉排序树33/903.二叉排序树基本运算算法实现（1）查找结点运算算法在二叉排序树bt中查找关键字为k的结点，找到后返回该结点的指针，找不到返回NULL。若当前结点p的关键字等于k，则返回p。否则若k小于当前结点的关键字，则在左子树中查找。否则若k大于当前结点的关键字，则在右子树中查找。8.3.1二叉排序树34/90BSTNode*BSTSearch(BSTNode*bt,KeyTypek){BSTNode*p=bt;

while(p!=NULL)

{ if(p->key==k) //找到关键字为k的结点

returnp; elseif(k<p->key)

p=p->lchild; //沿左子树查找

else

p=p->rchild; //沿右子树查找

}

returnNULL; //未找到时返回NULL}8.3.1二叉排序树35/90

【例8.6】在含有27个结点的二叉排序树上，查找关键字为35的结点，以下哪些是可能的关键字比较序列？

A.28,36,18,46,35

B.18,36,28,46,35

C.46,28,18,36,35

D.46,36,18,28,35判断标准：在二叉排序树中的查找路径是原来二叉排序树的一部分，也一定构成一棵二叉排序树。8.3.1二叉排序树36/90A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3528361818362846462818364636182635是一棵二叉排序√

ⅩⅩⅩ8.3.1二叉排序树37/90（2）插入结点运算算法先在二叉排序树bt中查找插入新结点的位置，由于二叉排序树中所有新结点都是作为叶子结点插入的，所以这里是查找插入新结点的双亲即f结点。然后建立一个关键字为k的结点p。若bt为空树，则p结点作为根结点。若k<f->key，将p结点作为f结点的左孩子插入。若k>f->key，将p结点作为f结点的右孩子插入。8.3.1二叉排序树38/90intBSTInsert(BSTNode*&bt,KeyTypek){BSTNode*f,*p=bt;

while(p!=NULL)

//找插入位置,即找插入新结点的双亲f结点

{if(p->key==k)

//不能插入相同的关键字

return0;

f=p;

//f指向p结点的双亲结点

if(k<p->key)

p=p->lchild;

//在左子树中查找

else

p=p->rchild;

//在右子树中查找

}

p=(BSTNode*)malloc(sizeof(BSTNode));

p->key=k; //建立一个存放关键字k的新结点

p->lchild=p->rchild=NULL; //新结点总是作为叶子结点插入的

if(bt==NULL) //原树为空时,p作为根结点插入

bt=p;

elseif(k<f->key)f->lchild=p; //插入p作为f的左孩子

elsef->rchild=p; //插入p作为f的右孩子

return1; //插入成功返回1}8.3.1二叉排序树39/90（3）创建二叉排序树运算算法由包含n个关键字的数组a建立相应的二叉排序树。依次扫描a数组r的所有元素，调用BSTInsert()将其插入到二叉排序树bt中。voidCreateBST(BSTNode*&bt,KeyTypea[],intn){bt=NULL;

//初始时bt为空树

inti=0;

while(i<n)

{BSTInsert(bt,a[i]);//将关键字a[i]插入到二叉排序树bt中

i++;

}}8.3.1二叉排序树40/90

【例8.7】已知一组关键字为

（25,18,46,2,53,39,32,4,74,67,60,11）按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。8.3.1二叉排序树41/90生成的二叉排序树如图所示。25182464113953327467602518462533932474676011生成的二叉排序树8.3.1二叉排序树解42/901825241146393253746760在等概率的情况下，查找成功的平均查找长度为：8.3.1二叉排序树43/901825241146393253746760在等概率的情况下，查找不成功的平均查找长度为：8.3.1二叉排序树44/90由n个关键字构成的二叉排序树有多一棵，如n=3：312312ASLsucc=(1+2+3)/3=2ASLsucc=(1+2*2)/3=1.67一般地，高度为h的二叉排序树查找时间为1～n。但平均起来，由n个关键字构成的二叉排序树的查找时间复杂度为O(log2n)。8.3.1二叉排序树45/90（4）销毁二叉排序树运算算法销毁二叉排序树和第7章介绍的二叉树的算法相似。voidDestroyBST(BSTNode*&bt){if(bt!=NULL)

{ DestroyBST(bt->lchild); //销毁左子树

DestroyBST(bt->rchild); //销毁右子树

free(bt); //释放根结点

}}8.3.1二叉排序树46/90（5）输出二叉排序树运算算法采用括号表示法输出二叉排序树bt，其过程类似二叉树的输出。voidDispBST(BSTNode*bt){if(bt!=NULL)

{printf("%d",bt->key);

//输出根结点

if(bt->lchild!=NULL||bt->rchild!=NULL)

{printf("(");

//根结点有左或右孩子时输出'('

DispBST(bt->lchild);//递归输出左子树

if(bt->rchild!=NULL)//有右孩子时输出','

printf(",");

DispBST(bt->rchild);//递归输出右子树

printf(")");

//输出一个')'

}

}}8.3.1二叉排序树47/90（6）删除结点运算算法在二叉排序树bt中删除关键字为k的结点后，仍需要保持二叉排序树的特性。先在二叉排序树bt中查找关键字为k的结点p，用f指向其双亲结点。删除p结点分以下三种情况。8.3.1二叉排序树48/90

（1）若p结点没有左子树（含p为叶子结点的情况），则用p结点的右孩子替换它。51348762p5348762删除结点18.3.1二叉排序树49/90（2）若p结点没有右子树，则用p结点的左孩子替换它。51348762p删除结点851347628.3.1二叉排序树50/90

（3）若p结点既有左子树又有右子树，用其左子树中最大的结点替代它。通过p结点的左孩子q找到它的最右下结点q1，q1结点就是p结点左子树中最大的结点，将q1结点值替代p结点值，然后将q1结点删除。由于q1结点一定没有有孩子，可以采用（2）的操作删除结点q1。删除结点551348762pqq141387628.3.1二叉排序树51/90intBSTDelete(BSTNode*&bt,KeyTypek){BSTNode*p=bt,*f,*q,*q1,*f1;

f=NULL;

//查找删除的p结点及其双亲结点fif(bt==NULL)return0; //空树返回0

while(p!=NULL) //查找关键字为k的结点p及双亲f

{if(p->key==k) //找到关键字为k的结点,退出循环

break;f=p; //f指向p结点的双亲结点

if(k<p->key)

p=p->lchild;

//在左子树中查找

else

p=p->rchild;

//在右子树中查找

}

if(p==NULL)return0; //未找到关键字为k的结点,返回0查找关键字为k的结点p（被删结点）及其双亲结点fp结点既可能是f的左孩子结点，也可能是右孩子结点8.3.1二叉排序树52/90elseif(p->lchild==NULL) //被删结点p没有左子树的情况

{if(f==NULL) //p是根结点,则用右孩子替换它

bt=p->rchild;pp为根结点…………bt被删结点p没有左子树：分为3种子情况8.3.1二叉排序树53/90 //被删结点p没有左子树的情况elseif(f->lchild==p)

//p是f的左孩子,则用其右孩子替换它

f->lchild=p->rchild;

elseif(f->rchild==p)

//p是f的右孩子,则用其右孩子替换它

f->rchild=p->rchild;

free(p); //释放被删结点

}fpx……p为f的左孩子fpx……p为f的右孩子8.3.1二叉排序树54/90elseif(p->rchild==NULL) //被删结点p没有右子树的情况

{if(f==NULL) //p是根结点,则用左孩子替换它

bt=p->lchild;

if(f->lchild==p) //p是f的左孩子,则用其左孩子替换它

f->lchild=p->lchild;

elseif(f->rchild==p)

//p是f的右孩子,则用其左孩子替换它

f->rchild=p->lchild;

free(p); //释放被删结点}被删结点p没有右子树与p没有左子树的情况对称！8.3.1二叉排序树55/90else

//结点p既有左子树又有右子树的情况{q=p->lchild; //q指向p结点的左孩子

if(q->rchild==NULL) //若q结点无右孩子

{p->key=q->key; //将p结点值用q结点值代替p->data=q->data;

p->lchild=q->lchild; //删除q结点

free(q); //释放q结点

}51pq……特殊情况查找到p结点的左孩子结点q8.3.1二叉排序树56/90else

//若q结点有右孩子{f1=q;q1=f1->rchild;

while(q1->rchild!=NULL)//查找q结点的最右下结点q1

{f1=q1; //f1指向q1结点的双亲结点

q1=q1->rchild;

}

p->key=q1->key;

//将p结点值用q1结点值代替p->data=q1->data;查找p结点左子树中最大结点q1（及其双亲f1），结点值替代pqf1q18.3.1二叉排序树57/90if(f1->lchild==q1)

//删除q1结点:q1是f1的左孩子

f1->lchild=q1->rchild;elseif(f1->rchild==q1)//删除q1结点:q1是f1的右孩子

f1->rchild=q1->lchild;

free(q1);

//释放q1所占空间

}}return1; //删除成功返回1}8.3动态查找表通过q1结点的双亲结点f1来删除结点q1结点q1一定没有右子树用q1的左孩子结点替代它58/90若一棵二叉树中每个结点的左、右子树的高度至多相差1，则称此二叉树为AVL树（默认平衡二叉树指的是AVL树）。二叉树中每个结点设置一个平衡因子（balancdfactor，用bf表示）域。每个结点的平衡因子是该结点左子树的高度减去右子树的高度。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，即平衡因子取值为1、0或-1，则该二叉树称为AVL树。8.3.2平衡二叉树(AVL)8.3.2平衡二叉树59/90平衡二叉树总是二叉排序树5482是平衡树010154821不是平衡树012208.3.2平衡二叉树60/90平衡二叉树中插入新结点方式与二叉排序树相似，只是插入后可能破坏了平衡二叉树的平衡性，解决方法是调整。调整操作可归纳为下列四种情况。8.3.2平衡二叉树AVL中插入结点61/90（1）LL型调整插入的结点8.3.2平衡二叉树62/90

LL调整实例542LL插入关键字20124250008.3.2平衡二叉树63/90（2）RR型调整插入的结点8.3.2平衡二叉树64/90426589426895插入关键字9RR0-1-1-2

RR调整实例8.3.2平衡二叉树65/90（3）LR型调整插入的结点8.3.2平衡二叉树66/901637RL0-2-1

LR调整实例插入7调整以16为根的不平衡子树73160008.3.2平衡二叉树67/90（4）RL型调整插入的结点8.3.2平衡二叉树68/90

RL调整实例73119168RL0101-2插入8调整以7为根的不平衡子树8397111600000-18.3.2平衡二叉树69/908.3.2平衡二叉树创建AVL树将关键字序列依次插入的一棵空AVL树，得到一棵AVL树。70/90

【例8.9】输入关键字序列（16，3，7，11，9，26，18，14，15），给出构造一棵AVL树的步骤。1637160161301623-170LR70301608.3.2平衡二叉树解71/901197316-11110-2107316119LL73119160008.3.2平衡二叉树72/90267311916-11026-2RR73119160000260-18.3.2平衡二叉树73/90187311916261-2180RL731191826001608.3.2平衡二叉树74/90731191826161414101-18.3.2平衡二叉树75/9073119182616-115142150LR731191826150140160构造的结果AVL树8.3.2平衡二叉树76/908.3.2平衡二叉树AVL树的删除平衡二叉树中删除关键字为k的结点方式与二叉排序树删除相似。但删除后可能破坏平衡二叉树的平衡性，解决方法是调整。

77/908.3.2平衡二叉树

首先在AVL树中查找关键字为k的结点x（假定存在这样的结点并且唯一），删除结点x的过程如下：（1）如果结点x左子树为空，用其右孩子结点替换它，即直接删除结点x。（2）如果结点x右子树为空，用其左孩子结点替换它，即直接删除结点x。具体步骤78/908.3.2平衡二叉树

（3）如果结点x同时有左右子树（这种情况下，结点x是通过值替换间接删除的，称为间接删除结点），分为两种情况：若结点x的左子树较高，在其左子树中找到最大结点q，直接删除结点q，用结点q的值替换结点x的值。若结点x的右子树较高，在其右子树中找到最小结点q，直接删除结点q，用结点q的值替换结点x的值。79/908.3.2平衡二叉树RL-21xppR(a)pR的左子树高：RLR