数据结构与算法 课件 第8章 查找

第8章查找在数据处理领域，查找也是使用最为频繁的基本操作之一。例如，计算机从通电开机就开始各种查找操作，操作系统中的文件读写、编辑软件中的查找、搜索引擎的搜索、数据库系统的信息维护等都涉及大量的查找运算。1【本章重点】

①顺序查找、折半查找的过程及性能分析；

②二叉排序树中结点的查找、插入操作；

③散列表的构造和查找方法。【本章难点】

①折半查找、分块查找；

②

二叉排序树的操作；

③散列表的构造。2【本章内容】查找概述线性表的查找树表的查找散列表的查找习题38.1查找概述查找的基本概念查找的定义：在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。若查找到，称为查找成功，返回该记录的信息或者位置；否则，称为查找失败，返回相应的提示信息。每个记录结点由若干个数据项组成，其中用以唯一标识该记录的关键字称为主关键字，而用以识别若干个记录的关键字称为次关键字。查找表可分为静态查找表和动态查找表。对表的静态查找只是查找，不改变表的内容；对表的动态查找不仅查找，还会改变表的内容。45

查找算法的性能查找是将记录的关键字与给定值进行比较，通常以比较次数的平均值（平均查找长度）作为衡量查找算法优劣的标准。平均查找长度ASL定义为

n表示问题的规模，即查找集合中的记录个数

表示查找第i个记录的概率，若对各个记录的查找概率均等，则

表示查找第i个记录所需的比较次数68.2线性表的查找在线性表中进行的查找通常属于静态查找对线性表的查找方法：顺序查找、折半查找和分块查找。选择线性表的查找方法，除了需要考虑查找效率之外，还应当考虑线性表是顺序还是链式存储结构，记录的关键字是否有序等因素。7顺序查找顺序查找的过程：从表的一端开始，逐个将记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功；若直至最后一个记录，都没有找到与给定值相等的关键字，则表明表中没有所查的记录，查找失败。顺序查找对线性表存储结构和记录关键字有序性的要求：（1）线性表可以是顺序或链式存储结构；（2）记录的关键字有序或者无序。8顺序表的顺序查找算法在线性表一章中已经讲过，这里介绍一种带有监视哨的顺序查找算法。算法8.1顺序表的顺序查找算法。typedefstruct{ keytypekey; //关键字项

datatypeother; //其他域

}Table;TableR[n+1];//记录表表长，R[0]作为监视哨单元intSeqSearch(TableR[],keytypek)//在R中顺序查找关键字为k的记录；若查找成功，函数返回记录下标，否则返回0{ inti; R[0].key=k;//在表头设置监视哨

for(i=n;R[i].key!=k;i--);//从表尾开始向前扫描 returni;//查找成功时i>0；查找失败时i=0}//SeqSearch9在等概率情况下，顺序查找成功时的平均查找长度为若待查找的关键字k不在表中，则必须进行n+1次比较才能确定查找失败。顺序查找的平均查找长度应当综合考虑查找成功时的平均查找长度和查找失败时的查找长度。顺序查找的算法简单，对线性表的存储结构和关键字的有序性无任何要求，但是当n很大时，这种方法的查找效率较低。因此，顺序查找只适用长度较小的线性表。10折半查找（二分查找）折半查找是一种效率较高的查找方法。折半查找对线性表的要求：必须是顺序存储结构的有序表，即表中记录按关键字有序。折半查找关键字值k的过程：每次将k先与表的中间记录相比较，如果未找到则判断k是在表的左半部还是右半部，以缩小查找范围；逐步缩小查找区间直至查找成功或查找区间不存在时结束。折半查找可以采用非递归或递归的方法。11算法8.2折半查找非递归算法。intBinSearch1(tableR[],keytypek)//对有序表R进行折半查找，成功时返回结点的位置，失败时返回0{ intlow,mid,high; low=1;high=n;//置查找区间的下界和上界初值

while(low≤high)//当前查找区间非空

{ mid=(low+high)/2; if(k==R[mid].key)returnmid;//查找成功

elseif(k<R[mid].key)high=mid-1;//查找区间缩小为左子表

elselow=mid+1; //查找区间缩小为右子表

} return0;//查找失败}12算法8.3折半查找递归算法。intBinSearch2(tableR[],intlow,inthigh,keytypek)//对有序表R进行折半查找，low和high分别为查找区间的下界和上界，查找成功时返回结点的位置，失败时返回0{ if(low>high)return0;//查找失败

else{ mid=(low+high)/2; if(k<R[mid]) returnBinSearch2(R,low,mid-1,k);//在左子表继续查找

elseif(k>R[mid]) returnBinSearch2(R,mid-1,high,k);//在右子表继续查找

elsereturnmid;//查找成功

}}13【例】（教材P200）已知有序表中关键字序列为：9,15,21,33,47,59,64,77,84,91，现要查找关键字为15及80的记录，其查找过程如下：查找k=15的记录初始查找区间为R[1]~R[10]首先取，由于k=15<R[5].key，查找区间缩小为R[1]~R[4]取，由于k=15==R[2].key，查找成功。

(2)查找k=80的记录初始查找区间为R[1]~R[10]首先取，由于k=80>R[5].key，查找区间缩小为R[6]~R[10]

取，由于k=80>R[8].key，查找区间缩小为R[9]~R[10]

再取，由于k=80<R[9].key，取high=mid

1=8，由于low>high，查找区间不存在，则查找失败。

14折半查找的过程和性能分析可以通过折半查找判定树来描述在折半查找二叉树中，利用当前查找区间的中值记录作为根，将有序表的左子表和右子表的记录分别作为根的左子树和右子树。树中圆形结点称为内部结点，结点内的数字表示该结点在有序表中的位置；所有内部结点的空指针域相当于指向一个方形结点，称为外部结点，可用于表示两个内部结点之间的有效关键字区间。成功的查找过程恰好走了一条由根结点到被查结点的路径，与关键字进行比较的次数即为被查结点在树中的层数；而查找失败的过程是一条从根结点到外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。查找关键字为15的记录，也即第二个记录，只需比较2次；关键字值80处于第8、9个记录的关键字之间，其关键字的比较次数为3，查找最后落到外部结点8~9，此时该区间不存在，即查找失败。15折半查找的平均查找长度

当n较大时，可以用近似公式：

折半查找的时间复杂度为O(log2n)对于有序表，折半查找的效率显然高于顺序查找。但是为得到有序表必须进行排序。16分块查找（索引顺序查找）分块查找要求数据表分块有序，索引表有序。【例】（教材P202）如图8.3所示，线性表含有18个记录，被分为三个子表(R1,R2,…,R6)、(R7,R8,…,R12)、(R13,R14,…,R18)。对每个子表（或称块）建立一个索引项，其中包含两项内容：关键字值项（为该子表内的最大关键字值）和指针项（指示该子表的第一个记录在表中的位置）。分块查找需分两步进行，首先可用顺序查找或折半查找索引表，确定待查记录所在的块，然后在块中顺序查找所需的记录。17查找关键字值为k=44的结点，由于索引表小，可用顺序查找方法查找索引表，直至找到第一个关键字大于等于k的结点，即关键字为48的结点。由于22<k<48，关键字为44的结点若存在的话，则必定在第二个子表中，因此根据同一索引项中的指针指示，从第二个子表中第一个记录，也即分块有序表中的第7个记录起进行顺序查找，直到R[9].key=k为止。若此子表中没有关键字值等于k的记录，即在第7～12个记录这段区间没有关键字和k相等，则查找不成功。18【例8.1】在记录表中分块查找关键字为k的记录。设索引表Idx的长度为m且有序，对索引表采用折半查找，记录表R的块内采用顺序查找。typedefstruct{ KeyTypekey; //块内最大关键字

intlink; //指向的起始位置}IdxType;//索引表结点结构类型19intIdxSearch(IdxTypeIdx[],intm,SeqListR[],intk){ //索引表Idx的长度为m，R为记录表，查找关键字为k的记录

//在索引表中折半查找

intlow=0,high=m-1,mid,i,j; while(low<=high) { mid=(low+high)/2; if(Idx[mid].kek>=k) high=mid-1; //修改查找区间的上界

elselow=mid+1;

//修改查找区间的下界

} if(low<m) { //在索引表中找到所要找的块，接下来在记录表的块内顺序查找

i=Idx[low+1].link-1; //i为该块最后一个数组元素下标

j=Idx[low].link; //j为该块第一个数组元素下标

while(R[i].key!=k&&i>=j)//块内从后向前顺序查找

i--; if(i>=j)returni; //查找成功，返回记录在记录表中的位置信息

} return-1; //查找失败，返回-1}208.3树表的查找二叉排序树和平衡二叉树是两类常用的树表。（平衡二叉树不讲）树表具有查找效率高，插入和删除效率也高的特点。二叉排序树（1）二叉排序树（BST）的定义：二叉排序树或者是空树，或者是满足如下性质的非空二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又是一棵二叉排序树。21由BST性质可知二叉排序树中任一结点x的关键字必大(小)于其左(右)子树中任一结点y(若存在)的关键字，可以认为各结点关键字是唯一的。在实际应用中，如果不能保证数据集中各结点元素的关键字互不相同，可以将二叉排序树定义中“小于”改为“小于等于”，或将“大于”改为“大于等于”。本章我们仍然只讨论二叉排序树中各结点关键字互不相同的情况。22对二叉排序树进行中序遍历可得到一个关于关键字的有序序列。【例】（P204）遍历图8.4所示的二叉排序树：（1）LDR序列为递增序列：1，2，3，4，5，6，7，8，9（2）RDL序列为递减序列：9,8,7,6,5,4,3,2,123二叉排序树的结点类型定义如下：typedefintkeytype;typedefstructnode{ keytypekey;//关键字项

datatypeother;//其它数据项

structnode*lchild,*rchild;//左、右指针域}bstnode;（2）二叉排序树的插入和生成生成一棵二叉排序树的过程：从空的二叉排序树开始，逐个把结点插入到二叉排序树。当前插入的结点一定是叶子结点。具体步骤如下：241）若二叉排序树T为空，则令新插入的结点为根；2）若二叉排序树T不为空，则将待插的结点值s和根结点的值r比较：(a)若s＝r，则说明树中已有此值，无须插入;(b)若s<r，则将其插入根的左子树中;(c)若s>r，则将其插入根的右子树中。以上步骤是一个递归的过程，即子树中的插入过程与二叉排序树T的插入过程相同。在二叉排序树中插入新结点有递归算法（算法8.4）和非递归算法（算法8.5）。二叉排序树的生成算法（算法8.6）需调用二叉排序树的插入算法（算法8.4或算法8.5）。25算法8.4二叉排序树插入新结点的递归算法。bstnode*InsertBST1(bstnode*t,bstnode*s)//t为二叉排序树的根结点指针，s为待插入的结点指针{if(t==NULL)t=s;//原树为空,返回s作为根指针elseif(s->key<t->key)t->lchild=InsertBST1(t->lchild,s);//插入到左子树elseif(s->key<t->key)t->rchild=InsertBST1(t->rchild,s);//插入到右子树

returnt;}26算法8.5二叉排序树插入新结点的非递归算法。bstnode*InsertBST2(bstnode*t,bstnode*s)//t为二叉排序树的根指针，s为插入的结点指针{bstnode*f,*p;p=t;while(p!=NULL){f=p;//f指向*p结点双亲

if(s->key==p->key)returnt;//树中已有结点*s；无须插入if(s->key<p->key)p=p->lchild;//在左子树中查找插入位置

elsep=p->rchild;//在右子树中查找插入位置}if(t==NULL)returns;//原树为空,返回s作为根指针if(s->key<f->key)f->lchild=s;//将*s插入，作为*f的左孩子elsef->rchild=s;//将*s插入，作为*f的右孩子returnt;}27算法8.6二叉排序树的生成算法bstnode*CreatBST()//生成二叉排序树{bstnode*t,*s;keytypekey,endflag=0;//endflag为结点结束标志datatypedata;t=NULL;//设置二叉排序树的初态为空树

scanf(“%d”,&key);//读入一个结点的关键字while(key!=endflag)//输入非结束标志，执行以下操作{s=(bstnode*)malloc(sizeof(bstnode));//申请新结点s->lchild=s->rchild=NULL;//将新结点的指针域置为空s->key=key;scanf(“%d”,&data);//读入结点的其它数据项s->other=data;

t=InsertBST1(t,s)；//将新结点插入t中，调用InsertBST1或InsertBST2scanf(“%d”,&key)//读入下一个结点的关键字}returnt;}28关键字相同，但序列不同，则生成不同形状的二叉排序树。【例】如图8.5所示，以两个不同的序列（6,2,8,4,9,7,2）和（8,4,2,9,6,7,2）给定一组关键字，分别生成两棵形状不同的二叉排序树。29（3）二叉排序树的删除从二叉排序树中删除一个结点较为复杂，因为必须保证删除结点之后仍然是一棵二叉排序树。在二叉排序树中删除结点p的算法应当考虑以下四种情况：（1）待删除的结点p为叶子结点，只需将其双亲结点q指向它的指针清空，即q->lchild=NULL，然后删除结点p。（2）待删除的结点P只有左子树。将结点P的左子树全部挂接在P的双亲q上，且位置是P在其双亲中原来的位置，即q->lchild=p->lchild,再删除结点p。（3）待删除的结点P只有右子树。将结点P的右子树全部挂接在P的双亲上，且位置是P在其双亲中原来的位置，即q->lchild=p->rchild，再删除结点p。（4）待删除的结点p既有左子树，又有右子树。可以有两种方法，第一种方法是按中序遍历在p的左子树中找出值最大的结点s，然后用结点s的值替换结点p的值，再删除结点s（如图8.8（a）所示）；第二种方法是在p的右子树中找出值最小的结点s，然后用结点s的值替换结点p的值，再删除结点s308.4散列表的查找散列表概述散列表的查找是一种“计算”寻址方式，不经过任何比较，一次就能直接存取所查的记录，因此它的查找效率高。基本思想是：在记录的关键字k和结点的存储地址d之间，建立散列函数d=H(k)。查找时利用该函数H，就可以根据要查找的关键字直接计算记录所在的位置。用散列法存储的线性表叫散列表或哈希表。由散列函数计算的散列地址有可能冲突，即对于不相等的关键字k1和k2，通过散列函数的计算，所得到的函数值（散列地址）是相同的。即k1≠k2，但H(k1)=H(k2)。K1和k2互为同义词。312.散列函数的构造方法为了减少冲突，散列函数的值必须分布均匀。常用的构造散列函数的方法：1．直接定址法2．数字选择法3.平方取中法4.折叠法5.除留余数法6.基数转换法7.随机数法32重点讲一下除留余数法假设散列表长为m，选取适当的正整数p去除关键字，将所得余数作为散列地址，即H(key)=key%p(p≤m)一般情况下，p应该选取小于或等于散列表长度m的某个最大素数。下面给出一些常用取值。m=8,16,32,64,128,256,512,1024p=7,13,31,61,127,251,503,1019333.解决冲突的方法构造合适的散列函数只能够减少冲突，不可能避免冲突，因此有解决冲突的方法。处理冲突的方法不同，所构造的散列表的组织形式也就不同。按散列表的组织形式可以划分为两类散列表：闭散列表和开散列表。闭散列表是将所有记录均匀地存放在散列表HT[m]中，如表8.4（P219）。开散列表是将互为同义词的记录链接成一个单链表，而把单链表的头指针存放在散列表HT[m]中，如图8.16（P221）。闭散列表和开散列表还涉及到装填因子的概念。设散列表的容量为m，记录的个数为n，装填因子α为装填因子α<1，即m>n。装填因子的大小会影响到对散列表进行查找、插入、删除等操作时的比较次数。34下面重点介绍两种处理冲突的方法（1）开放地址法（闭散列表）的线性探测法当发生冲突时，沿着环形表进行线性探测，直到找到一个空地址为止。线性探测公式为

hi=(H(key)+i)%m其中i=1,2,…,m-1。即依次探测H(key)+1,H(key)+2,…,m

1,0,1,…,H(key)

1，直至找到一个开放地址（空地址）为止。【例8.2】已知一组关键字集{21,32,11,43,35,5,51,12,7}，用线性探测法解决冲突，试构造这组关键字的闭散列表。通常令装填因子

<1，这里取

=0.75。由于关键字个数为n=9，可以确定散列表长m=

n/

=12，因此可以设置一维数组HT[12]存放散列表。我们采用除留余数法构造散列函数，并选p=11，则开放地址为hi=(H(key)+di)%m=(key%11+i)%1235下面重点介绍两种处理冲突的方法（1）开放地址法（闭散列表）线性探测法。当发生冲突时，沿着环形表进行线性探测，直到找到一个空地址为止。线性探测公式为

hi=(H(key)+i)%m其中i=1,2,…,m-1。即依次探测H(key)+1,H(key)+2,…,m

1,0,1,…,H(key)

1，直至找到一个开放地址（空地址）为止。闭散列表存在冲突“堆积”现象，即通过散列函数计算出来的散列地址原本并不冲突，只是由于前面的探测造成后面的冲突。【例8.2】已知一组关键字集{21,32,11,43,35,5,51,12,7}，用线性探测法解决冲突，试构造这组关键字的闭散列表。通常令装填因子

<1，这里取

=0.75。由于关键字个数为n=9，可以确定散列表长m=

n/

=12，因此可以设置一维数组HT[12]存放散列表。我们采用除留余数法构造散列函数，并选p=11，则开放地址为hi=(H(key)+di)%m=(key%11+i)%12

，其中散列函数为H(key)=key%11+i3621%11-10 32%11=10（冲突），11 11%11=043%11=10（冲突），11（堆积），0（堆积），1 35%11=25%11=5 51%11=7 12%11=1（堆积），2（堆积），37%11=7（冲突），8 37（2）拉链法（开散列表）拉链法，又称为链地址法。拉链法的基本思想是：将所有散列地址相同的记录，即所有关键字为同义词的记录存储在一个称为同义词子表的单链表中，在散列表中存储的是所有同义词子表的头指针。开散列表不存在冲突“堆积”现象。

38【例8.3】以例8.2中的关键字集{21,32,11,43,35,5,51,12,7}为例，用拉链法处理冲突，构造这组关键字的开散列表。关键字集有9个关键字，即n=9。设置散列函数为H(key)=key%11，散列表长度m取11，以指针数组HTP[11]作为开散列表。对于散列地址相同的关键字都处于同一个单链表中，即所有散列地址为H(key)=i的关键字，都要链接到第i个单链表中。我们采用尾插法建立单链表。开散列表不存在冲突的“堆积”现象。39散列表的插入、查找和删除操作在闭散列表上的插入、查找和删除对闭散列表的插入和查找与建立比散列表是类似的。插入是利用散列函数和探测公式确定一个空散列地址；查找也是利用散列函数和探测公式进行关键字的查找。对闭散列表的删除操作不能直接删除，需要作删除标记。闭散列表的存储结构定义如下： #definenil0 //nil为空结点标记 #definedel_flag-1 //del_flag为已被删除标记 intht[m]; //闭散列表空间长度为m40散列表的插入、查找和删除操作在闭散列表上的插入、查找和删除查找算法8.8闭散列表的查找算法。intHash_Search(intht[],intx,int*add){

//在散列表ht中查找关键字值为x的记录，记录的地址通过指针add带回 i=0; d=Hash(x); while(ht[d]!=nil&&i<m) { if(ht[d]==x){

*add=d;

return(1); //查找成功，返回1

} elsed=(d+1)%m; //线性探测 i++; } return(0); //查找失败，返回0}41插入算法8.9闭散列表的插入算法。intHash_Insert(intht[],intx){ //在散列表ht中插入关键字值为x的记录 i=0; d=Hash(x); while(i<m) { if(ht[d]==nil||ht[d]==del_flag) { ht[d]=x; return(1); //插入成功，返回1 } else d=(d+1)%m; //线性探测 i++; } return(0); //散列表已满，插入失败，返回0}42删除

算法8.10闭散列表的删除算法。intHash_De