第9章 查找(上课用)

数据结构主讲人：张立震E-mail:system0@9.1静态查找表9.2动态查找表9.3哈希表第9章查找查找的概念静态查找表二叉排序树平衡二叉树（不讲）哈希表本章主要内容查找(Search)的概念

查找表:是由同一类型的数据元素(或记录)组成的数据集合。

在查找表中一般有四个操作：

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

(2)检索某个“特定”的数据元素的各种属性

(3)在查找表中插入一个元素

(4)在查找表中删除一个元素

查找表的分类：静态查找表动态查找表关键字：数据元素中某个数据项的值，用以标识一个数据元素（或记录）。主关键字：可唯一地标识一个数据元素的关键字。使用基于主关键字的查找，查找结果应是唯一的！查找：就是在数据集合中寻找一个关键字等于某个给定值的数据元素（记录）。

查找的结果通常有两种可能：

查找成功

给出记录信息或记录所在的位置信息。

查找不成功

作为结果，给出“空记录”或“空指针”表示查找失败。为在上图中，如果我们查找主关键字“代码”的主关键字为“sh601398”的记录时就可以得到第二条唯一一个记录。如果查找次关键字“涨跌额”为“-0.11”的记录时，可以得到两条记录。平均查找长度ASL(AverageSearchLength)

衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数或平均读写磁盘次数。设查找第i

个元素的概率为pi，查找到第i

个元素所需比较次数为ci，则查找成功的平均查找长度:

以上讨论的是“基本上每次查找都成功”，若查找不成功的情况不可忽略，则应是查找成功的平均长度与查找不成功的平均长度之和。以后主要讨论在查找成功下的ASL(哈希表除外)。此外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。

9.1静态查找表

静态查找表有不同的表示方法，不同的表示方法中查找方法也不同。可分为：

顺序查找表有序查找表静态树表的查找（不讲解）索引查找表

9.1.1顺序表的查找

(SequentialSearch)所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找。其顺序存储结构如下：typedefstruct{//元素类型定义KeyTypekey;//元素的关键字InfoTypedata;//元素的其他数据}ElemType;typedefstruct{//顺序表类型定义

ElemType*elem;//存储空间的基址，建表时0号单元留用

intlength;//表的长度}SSTable;

SSTabletb;i01234567891011

513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：顺序查找算法(p217算法9.1)intSearch_Seq(SSTableST,KeyTypekey){

//顺序查找的算法，0号元素为监视哨。inti=ST.length;ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(ST.elem[i].key,key);--i)//从后往前找returni;//找不到时,i为0}优点：算法简单适用，对表中元素没有要求，链表中查找可以类似思路实现。缺点：当表长较大时，平均查找长度较大。for(i=ST.length;ST.elem[i].key!=key;--i)顺序查找成功时的平均查找长度在顺序查找情形，ci=n-i+1,i=1,,n，因此在等概率情形，pi=1/n,i=0,1,,n-1。

在不等概率情况下：使表中记录按查找概率由小到大重新排序，以便提高查找效率。若查找概率不确定，则附设一个访问频率，利用频率大小来调整记录所在位置。9.1.2有序表的查找折半查找：先求位于查找区间正中的对象的下标mid，用其关键字与给定值x比较:

elem[mid].key==x，查找成功；

elem[mid].key>x，把查找区间缩小到表的前半部分，再继续进行折半查找；

elem[mid].key<x，把查找区间缩小到表的后半部分，再继续进行折半查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个对象，仍未找到想要查找的对象，则查找失败。查找成功的例子 查找失败的例子有序表查找的例子(1)mid=(low+high)/2」

(2)比较ST.elem[mid].key==key?

如果ST.elem[mid].key==key，则查找成功，返回mid值如果ST.elem[mid].key>key，则置high=mid-1

如果ST.elem[mid].key<key，则置low=mid+1(3)重复计算mid

以及比较ST.elem[mid].key与key，当low>high时，表明查找不成功，查找结束。折半查找算法实现折半查找递归算法intBinSearch(SSTableST,intlow,inthigh,KeyTypekey){if(low>high)return0;//顺序表中不存在待查元素else{mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))//继续在前半区间进行查找returnBinSearch(ST,low,mid-1,key)

elsereturnBinSearch(ST,mid+1,high,key)

//继续在后半区间进行查找

}}初次调用时，BinSearch(ST,1,ST.length,key)折半查找非递归算法(p220算法9.2)intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;//置区间初值

while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找

elselow=mid+1;//继续在后半区间进行查找

}return0;//顺序表中不存在待查元素}//Search_Bin先看一个有11个元素的表的例子：n=11i1234567891011Ci12233334444折半查找的性能分析判定树：描述查找过程的二叉树。有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过log2n+16391425781011假设n=2h-1并且查找概率相等，则查找成功时折半查找的平均查找长度

在n>50时，可得近似结果一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。折半查找的性能分析折半查找的效率比顺序查找高。折半查找只能适用于有序表，并且以顺序存储结构存储。顺序表有序表表的特性无序有序存储结构顺序或链式顺序插删操作易于进行需移动元素ASL的值(n+1)/2大(n+1)/n·log2(n+1)-1小时间复杂度O(n)O(log2n)顺序表和有序表的比较在建立顺序表的同时，建立一个索引项，包括两项：关键字项和指针项。索引表按关键字有序，表则为分块有序。12345678910111213141516171822121389203342443824486058744986532248861713索引顺序表=索引(有序)+顺序表(无序)顺序表索引表9.1.4索引顺序表的查找——分块查找最大关键字指针索引顺序查找又称分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。适用条件：分块有序表算法实现：用数组存放待查记录,每个数据元素至少含有关键字域。建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针12345678910111213141516171822121389203342443824486058745786532248861713索引表查38例如分块查找方法评价容易证明，在给定n的前提下，当s取时，ASLbs取最小值查找方法比较ASL值最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表顺序查找折半查找分块查找

9.2动态查找表动态查找表的特点:

表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值key的记录，表明查找成功；否则插入关键字等于key的记录。

二叉排序树（二叉查找树）或者是一棵空树，或者是具有下列性质的二叉树：

每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同。

左子树(若非空)上所有结点的关键字都小于根结点的关键字。

右子树(若非空)上所有结点的关键字都大于根结点的关键字。

左子树和右子树也是二叉排序树。二叉排序树(BinarySortTree)50308020901085406625238835是二叉排序树吗？例如：以二叉链表形式存储typedefstruct{//元素类型定义KeyTypekey;//元素的关键字InfoTypedata;//元素的其他数据}TElemType;typedefstructBiTNode{//结点结构

TElemTypedata;//元素structBiTNode*lchild,*rchild;//左右指针

}BiTNode,*BiTree;BiTreeT;二叉排序树的存储结构1.二叉排序树的查找算法若二叉排序树为空，则查找不成功；否则

(1)若给定值等于根结点的关键字，则查找成功；

(2)若给定值小于根结点的关键字，则继续在左子树上进行查找；

(3)若给定值大于根结点的关键字，则继续在右子树上进行查找。在二叉排序树中查找关键字值分别为50,35,90,955030802090854035883250505030403550508090查找失败BiTreeSearchBST(BiTreeT,KeyTypekey){//

在根指针T所指二叉排序树中递归查找关键字等于key的数据元素,

//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。

if((!T)||EQ(key,T->data.key))returnT; elseifLT(key,T->data.key)returnSearchBST(T->lchild,key); elsereturnSearchBST(T->rchild,key);}二叉排序树的递归查找算法(P228算法9.5(a))2.二叉排序树的插入算法二叉排序树是一种动态数表，树的结构不是一次生成，而是在查找过程中，当树中不存在关键字等于给定值时再进行插入。若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。intSearchBST(BiTreeT,KeyTypekey,BiTreef,

BiTree&p){

//二叉排序树的递归查找算法

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); else

returnSearchBST(T->rchild,key,T,p);}

P

即为位置形参，查找成功返回数据结点所在位置，不成功则返回查找路径上访问的最后一个结点的指针。f

指向

T

的双亲结点，即

p

的上一步结点指针。二叉排序树的改进查找算法(P228算法9.5(b))intInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){ s=newBiTNode;//为新结点分配空间

s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s;//插入s为新的根结点

elseif(LT(e.key,p->data.key)) p->lchild=s;//插入*s为*p的左孩子

elsep->rchild=s;//插入*s为*p的右孩子

returnTRUE;//插入成功

}elsereturnFALSE;}//InsertBST在以T为根节点的BST上插入一个关键字等于e.key的元素——非递归算法intInsert_BST(BiTree&T,BiTreeS){BiTreep,q;if(!T)T=S;else{p=T;while(p){q=p;//q指向p结点的双亲结点

if(S->data.key<p->data.key)p=p->lchild;elseif(S->data.key>p->data.key)p=p->rchild; elsep=NULL;} if(S->data.key==q->data.key)return0;if(S->data.key<q->data.key)q->lchild=S;elseq->rchild=S; }return1;}将指针S所指的结点插入到根结点指针为T的

二叉排序树中的非递归算法从空树出发，依次插入R1～Rn各数据值：

(1)如果二叉排序树是空树，则插入结点就是二叉排序树的根结点；

(2)如果二叉排序树是非空的，则插入值与根结点比较，若小于根结点的值，就插入到左子树中去；否则插入到右子树中。构造二叉排序树过程输入数据，建立二叉排序树的过程输入数据序列

{53,78,65,17,87,09,81,45,23}构造二叉排序树的算法voidCreat_BST(BiTree&T){intx;BiTreeS;T=NULL;scanf(“%d”,&x),while(x!=0){S=(BiTNode*)malloc(sizeof(BitNode));S->data.key=x;S->lchild=NULL;S->rchild=NULL;Insert_BST(T,S);}return;}一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列；每次插入的新结点都是二叉排序树上新的叶子结点；插入时不必移动其它结点，仅需修改某个结点的指针；中序遍历二叉排序树可得到一个关键字有序序列。结论3.二叉排序树的删除算法

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：

(1)被删除的结点是叶子；

(2)被删除的结点只有左子树或者只有右子树；

(3)被删除的结点既有左子树，也有右子树。其双亲结点中相应指针域的值改为“空”50308020908540358832(1)被删除的结点是叶子结点key=88其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。50308020908540358832(2)被删除的结点只有左子树或者只有右子树key=80以其前驱替代之，然后再删除该前驱结点50308020908540883532(2)被删除的结点既有左子树，也有右子树key=50二叉排序树查找性能的分析在二叉排序树上查找关键字等于给定值的结点的过程，恰走了一条从根结点到该结点的路径的过程。和给定值比较的关键字个数等于给定结点所在的层数，不超过树的深度（类似判定树）由值相同的n个关键字，由于输入的序列顺序不一样，构造所得不同形态的二叉排序树，平均查找长度的值不同，甚至可能差别很大。由关键字序列3，1，2，5，4构造而得的二叉排序树由关键字序列1，2，3，4，5构造而得的二叉排序树，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2结论：n个结点的二叉排序树的平均查找长度和树的形态有关；若插入的关键字有序，则构成的二叉排序树蜕变为单支树，即为顺序表的查找，平均查找长度为(n+1)/2；最好情况下，二叉树的形态和折半查找的判定树相同，ASL和log2n成正比。前面两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系。这类查找方法建立在“比较”的基础上顺序查找折半查找、二叉排序树查找==><≠查找效率依赖于比较次数能否不经过任何比较呢？只有一个办法：

预先知道所查关键字在表中的位置。即，要求记录在表中的位置和其关键字之间存在一种确定的关系。

9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表

只有一个办法：预先知道所查关键字在表中的位置。即，要求：记录在表中的位置和其关键字之间存在一种确定的关系。对于频繁使用的查找表，希望ASL=0。哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系，以H(key)作为关键字为key的记录在表中的位置，通常称这个函数H(key)为哈希函数。哈希查找：又叫散列查找，利用哈希函数进行查找的过程。

012345678910111213{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Du

}例如：对于如下9个关键字设哈希函数

H(key)=

(Ord(第一个字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDu从例子可见，哈希函数只是一种映象，即：将关键字的集合映射到某个地址集合上，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。261719122338254

012345678910111213{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Du

}例如：对于如下9个关键字设哈希函数

H(key)=

(Ord(第一个字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDu261719122338254问题:

若添加关键字Lu,怎么办？冲突：key1key2，但H(key1)=H(key2)

的现象。哈希表：根据设定的哈希函数

H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。这一映象过程称为哈希造表或散列，所得的位置为哈希地址或散列地址。9.3.1什么是哈希表9.3.2哈希函数的构造方法直接定址法

数字分析法平方取中法折叠法除留余数法(最常用*)随机数法对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理。哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.

直接定址法此法仅适合于：地址集合的大小==关键字集合的大小2.数字分析法此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。例：

H1(key)=首字母序号H2(key)=首字母序号+尾字母序号以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法在词典处理中使用十分广泛。它先计算构成关键字的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。3.

平方取中法

4.折叠法

例

关键字为：0442205864，哈希地址位数为458644220041

0088H(key)=0088移位叠加5864022404

6092H(key)=6092间接叠加将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：

移位叠加：将分割后的几部分低位对齐相加。间接叠加：从一端沿分割界来回折送，然后对齐相加。此法适合于：关键字的数字位数特别多，而且关键字中每一位上数字分布大致均匀。5.除留余数法----常用方法设定哈希函数为:H(key)=keyMOD

p

(p≤m)其中，m

为表长，p

为不大于m

的素数或是不含20以下的质因子。为什么要对p

加限制？例如：给定一组关键字为:12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3。可见，若p

中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。6.随机数法设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数。此法适用于：对长度不等的关键字构造哈希函数。选取哈希函数考虑的因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率

9.3.3处理冲突的方法开放定址法（闭散列*）再哈希法（双散列）链地址法（开散列*）“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。通常有下列几种方法：1.开放定址法(闭散列)——是处理溢出的一种常用的方法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm

其中：i=1,2,…,s；

H(key)为哈希函数；

m为哈希表长；

di为增量序列。1.开放定址法(闭散列)对增量di

有三种取法：(1)线性探测再散列

di=1，2，3，…，m-1(2)二次探测再散列

di=12,-12,22,-22,…,(3)伪随机探测再散列

di

是一组伪随机数列或者

di=i×H2(key)(又称双散列函数探测)例

表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11，现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中012345678910601729(1)H(38)=38MOD11=5冲突

H1=(5+1)MOD11=6冲突

H2=(5+2)MOD11=7冲突

H3=(5+3)MOD11=8不冲突38(2)H(38)=38MOD11=5冲突

H1=(5+1²)MOD11=6冲突

H2=(5-1²)MOD11=4不冲突38(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：

H1=(5+9)MOD11=3不冲突38线性探测二次探测伪随机探测例如:

关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)1901231455681901231468若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突118236551182361121362511121214

132.再哈希