数据结构 Chap8学习资料

第八章查找8.1查找的基本概念8.3基于树的查找法8.2基于线性表的查找法8.4计算式查找---哈希法8.1查找的基本概念1、

列表(查找表):是由同一类型的数据元素(或记录)构成的集合,可由任意数据结构实现。2、关键字:数据元素中某数据项的值,用以标识(识别)一个(组)数据元素(记录)。

若关键字可以唯一的识别一个记录，则称之为“主关键字”；若关键字识别的记录不唯一，则称之为“次关键字”。3、查找

根据某个给定值,在列表中确定其关键字等于给定值的数据元素(记录)的过程称为查找。

若列表中存在待查记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在列表中的位置；

若列表中不存在待查纪录,则称“查找不成功”.查找结果给出“空记录”或“空指针”。4、查找表的分类1)静态查找表:仅作查询和检索操作的列表。2)动态查找表:不仅作查询和检索操作，还经常进行插入和删除操作的列表。

在查找算法中要用到三类参量，即：①查找对象K（找什么）②查找范围L（在哪找）③查找的结果（K在L中的位置）其中①②为输入参量，在函数中不可缺少；③为输出参量，可用函数返回值表示。5、平均查找长度

为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于长度为n的列表，查找成功时的平均查找长度为：nASL=P1C1+P2C2+…+PnCn

=

i=1PiCi其中：Pi为查找列表中第i个数据元素的概率，

Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。6、查找的基本方法：查找方法：比较式查找法计算式查找法－HASH(哈希)查找法基于线性表的查找法基于树的查找法8.2基于线性表的查找法有顺序查找、折半查找和分块查找法三种一、顺序查找法

顺序查找的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构：顺序结构链式结构数据元素类型的定义为:typedef

struct{

keyType

key;//关键字域

……

//其它属性域}

ElemType;1、顺序结构数据类型定义：假设静态查找表的顺序存储结构为typedef

struct{

elem[MaxSize];//数据元素存储空间基址，建表时

//按实际长度分配，0号单元留空

int

length;//表的长度}

SSTable;ElemType顺序查找过程示例：或ii假设给定值k=64,要求elem[i].key=k,问:i=?结果:i=72137881992

5

6456807513…

901234567891011

niiiiiii2、顺序查找算法int

SeqSearch（SSTablel,KeyTypek）{i=l.length;while(i>=1&&l.elem[i].key!=k)i--;if(i>=1)return（i）elsereturn(0);}循环条件i>=1判断查找是否越界。设置监视哨的顺序查找算法int

SeqSearch（SSTablel,KeyTypek）{l.elem[0].key=k;i=l.length;while(l.elem[i].key!=k)i--;return（i）;}l.r[0]为监视哨，可以防止越界。例：2137881992

5

6456807513…

901234567891011

niik=562137881992

5

6456807513…

901234567891011

n56结果:i=8iik=6060结果:i=03、顺序查找的时间复杂度分析åi=1PiCiASL=n

因为：对顺序表而言：Ci=n-i+1在等概率查找的情况下：顺序表查找成功的平均查找长度为：顺序表查找不成功的平均查找长度为：

ASLus=n+1所以，顺序表查找的时间复杂度为:O(n)二、折半查找法（二分搜索法）条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。查找方法：由于列表是按关键字有序排列，所以可以基于“折半确定区间”的思想进行查找。优点：比较次数少，查找速度快;缺点：要求表为有序表，插入、删除困难。1、概念例如:nk=64

的查找过程如下：lowhighmid

mid

midlow

：指示查找区间的下界high：指示查找区间的上界mid=(low+high)/2:每次比较、划分区间的“点”lowhigh0123456789101105131921375664758088922、折半查找算法int

BinSrch

（SqListl,KeyTypek）{low=1;high=l.length;/*置区间初值*/while(low<=high){mid=(low+high)/2;

if(k==l.elem[mid].key)return（mid）;

/*找到待查元素*/

elseif(k<l.elem[mid].key)high=mid-1;

/*继续在前半区间查找*/

elselow=mid+1;

/*继续在后半区间查找*/}return(0);}先看一个具体的情况，假设：n=11判定树i1234567891011Ci342341342343149671028115找到有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，给定值进行比较的关键字个数恰是该结点在判定树上的层次数。ASLsuccss=(1

1+2

2+4

3+4

4)/11=33/11ASLunsucc=(4

4+8

5)/12=56/12折半查找的判定树是唯一的。3、折半查找时间复杂度分析

一般情况,表长为n的折半查找判定树的深度和含有n个结点的完全二叉树的深度相同。假设n=2h-1并且查找概率相等则ASLbs»log2(n+1)-1

所以，折半查找的时间复杂度为:O(logn)最坏情况查找长度为二叉树的深度：log2n+1

查找不成功时的比较次数最多也为：log2n+2当n>50时近似为三、分块查找法(索引顺序表查找)分块查找要将列表组织成以下索引顺序结构：★首先将列表分成若干个块(子表),一般情况下块的长度均匀,最后一块可以不满。每块中元素任意排列(块内无序)，但块与块之间有序。★构造一个索引表,其中每个索引项对应一个块,

记录每块的起始位置及每块中的最大关键字

(或最小关键字)。索引表按关键字有序排列。

整个表由两部分组成：基本块表与索引表。例：224886

1

6

12索引表各块最大关键字

各块起始地址221213

8

9

3342382448287449…12345678910111213…

分块查找过程1)由索引确定记录所在的块(折半或顺序查);2)在块内进行查找(顺序查)。索引可以根据查找表的特点来构造。可见:

索引顺序表查找的过程也是一个“缩小区间”的查找过程。

分块查找时间复杂度分析分块查找的平均查找长度=

查找“索引”的平均查找长度

+“块内”查找的平均查找长度

若n个记录分为b块，每块含s个记录，则等概率情况下,顺序查找索引时：

ASL=(b+1)/2+(s+1)/2=(n/s+s)/2+1

可以证明：当s=√n时,ASL取最小值√n+1折半查找索引时：ASL=log2(n/s+1)+s/2.8.3基于树的查找法

一、二叉排序树二、平衡二叉排序树（略）

8.3.1二叉排序树（二叉查找树）一、定义二、查找三、插入四、删除（略）五、性能分析一、定义：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；二叉排序树：或者是一棵空树，或者是具有如下特性的二叉树：（3）左、右子树也分别为二叉排序树。（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；例如:是二叉排序树。不50308020901085403525238866*中序遍历一个二叉排序树,可以得到一个递增有序序列。

typedef

structnode{KeyTypekey;/*关键字的值*/

……

structnode*lchild,*rchild;/*左右指针*/}bstnode,*BSTree;

通常用二叉链表作为二叉排序树的存储结构二叉排序树的存储结构二、查找根据二叉排序树的特点，查找过程如下：（1）k=t：则查找成功，返回根结点地址；（2）k<t：则进一步查左子树；（3）k>t：则进一步查右子树。

显然这是一个递归过程，可用递归算法实现查找。

若二叉排序树为空，则查找不成功；否则将待查关键字k与根结点关键字t进行比较，如果：例如:50308020908540358832二叉排序树查找关键字==50,505035,503040355090,50809095从上述查找过程可见：在查找过程中，生成了一条查找路径：

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。——查找成功——查找不成功三、插入1、若二叉排序树为空树，则s成为二叉排序树的根；2、若二叉树排序树非空，则将key与二叉树排序树根结点的值t进行比较，如果:

已知关键字值为Key的结点由指针s指示，将其插入二叉排序树的过程为：（1）key=t：不进行插入；（2）key<t：则将s插入左子树；（3）key>t：则将s插入右子树。

显然，可以用递归算法实现插入。fT设key=48fTfT22pfTfTTTTfffp30201040352523二叉排序树的生成给定一个元素序列，将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就将新元素插入到当前已生成的二叉排序树中，直至元素序列插入完毕。例如：

元素输入序列为：45,24,53,12,28,90,按上述算法生成的二叉排序树的过程：空树45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90

对同样一组元素值，如果输入的顺序不同，所建的二叉排序树形态也不同。241228539045如将上述关键字顺序变为:24,53,90,12,28,45,则生成的二叉排序树为：所以，二叉排序树的形态完全由一个输入序列决定，一个无序序列可以通过构造一棵二叉排序树而得到一个有序序列五、二叉排序树的查找性能

对于一组相同的关键字序列，关键字插入的先后次序不同，所构成的二叉排序树的形态及深度也不同。二叉排序树的平均查找长度ASL与二叉排序树的形态有关：二叉排序树的各分支越均衡,树的深度越浅，其平均查找长度ASL越小。例如：452412375393(a)输入关键字序列为{45,24,53,12,37,93}时的二叉排序树12122437455393(b)输入关键字序列为{12,24,37,45,53,93}时的二叉排序树

假设每个元素的查找概率相等，则它们的平均查找长度分别是：ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6

由此可见，在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。

若考虑把n个结点，按各种可能的次序插入到二叉排序树中，则有n！棵二叉排序树（其中有的形态相同）,可以证明，这些二叉排序树的平均查找长度仍然是O(log2n)。已知长度为12的表：(Jan,

Feb,

Mar,

Apr,

May,

June,

July,

Aug,

Sep,

Oct,

Nov,

Dec)。例：试按表中元素的顺序建立二叉排序树，并求其在等概率情况下查找成功的平均查找长度。若对表中元素先进行排序构成有序表，再求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecASLsuss=(1+2＊2+3＊3

+3＊4+2＊5+6)/12

=42/12=3.5JanFebMarAprJuneMayAugJulySepDecOctNovApr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,SepASLsuss=(1+2＊2+4＊3+5＊4)/12

=37/121234567891011123154967112812108.3.2平衡二叉排序树

对于二叉排序树,高度越低查找速度就越快。为此可在构造二叉排序树的过程中进行树形的优化，即平衡化处理,使其成为平衡二叉排序树。

树中每个结点的左、右子树深度之差的绝对值不大于1，。1、定义：平衡二叉树(AVL树)或是一颗空树，或者是具有如下特性的二叉排序树：例如：5472是平衡树不是平衡树547218结点的平衡因子：结点的左子树的深度减去它的右子树的深度。

平衡二叉树上所有结点的平衡因子只可能是-1、0、1，否则不是平衡二叉树。8.4计算式查找---哈希法

一、哈希表的定义二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希法性能分析8.4.1哈希表的定义以上讨论的各种查找表的共同特点为：

记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程是“基于”比较。查找的效率取决于和给定值进行比较的次数,这类方法的平均查找长度为O(logn)---O(n)。对频繁使用的查找表,希望ASL---〉0。能否做到？能！

只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为000~999的顺序表表示之。如：为招收的1000名新生建立一张查找表,

其关键字为学号,其值的范围为xx000~xx999(前两位为年份)。

则查找过程可以简单进行：取给定学号的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。

另例：1、各年龄人口信息统计表；

2、解放后各年国民经济信息统计表。上述几例的特点为：

记录在表中的位置与其关键字之间存在一种确定的对应关系,按此对应关系可根据关键字的值寻址，从而获得待查纪录。这种查找表称为哈希表，关键字与记录地址间的对应关系称为哈希函数f(key)

。{Zi,Qi,Su,Li,Wu,Ci,He,Ye,Du}

又例：对于如下9个关键字设

哈希函数f(key)=

(Ord(第一个字母)-Ord('A')+1)/2

CiZiQiSuLiWuHeYeDu问题:

若需添加关键字Zh,怎么办？此类问题称为“冲突”，如何解决？

0123

4567

8

9

10

11

12

13从上述例子可见：哈希表的构造、使用中有两个问题有待研究：1、如何根据关键字集合的特点，选择合适的哈希函数，使关键字均匀的散列到表中？2、当不同的关键字所得的哈希函数值相同时，即f(k1)=f(k2),如何有效的处理这类“冲突”现象（碰撞），使建表、查找均能有效地进行？

根据选定的函数H(key)

和处理冲突的方法,将一组关键字映象到一个有限的、连续的地址集(区间)上，并以每个关键字在地址集中的“映象”作为相应记录在表中的存储位置，由此构造所得的查找表称为“哈希表”(散列表、杂凑表),所选择的函数H(key)称为哈希函数。哈希表的定义：

若是非数字关键字，则需先对其进行数字化处理。1.

直接定址法3.平方取中法5.除留余数法4.分段叠加法6.随机数法2.数字分析法

“好的”哈希函数应该是“均匀”的，对数字型关键字，一般有下列哈希函数的构造方法：二、构造哈希函数的方法哈希函数为关键字的线性函数

H(key)=key

或者

H(key)=a

key+b

其中a和b为常数(此哈希函数称为自身函数),所得的地址集合的大小等于关键字集合的大小,这种哈希函数不会发生冲突。1.

直接定址法此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体,去掉数字重复出现频度很高的位,提取数字均匀分布的若干位或它们的组合作为地址。2.

数字分析法

以关键字平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”,平方值的中间几位与整个关键字中的每一位数字都相关。

此方法适合于:

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

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。

此方法适合于:

关键字的数字位数特别多，且每一位的数字分布大致均匀。4.分段叠加法设定哈希函数为:

H(key)=keyMODp其中：p≤m

(表长)

也可对2,3,4种方法的结果取模。

这是一种简单且适用范围很广的哈希函数，但要求：1、P不能取关键字基数的幂；

2、P应尽可能的取质数，或不包含小于20的质因数的合数；

3、P应尽可能的接近m。5.除留余数法设定哈希函数为:

H(key)=Random(key)其中，Random为伪随机函数

通常，此方法用于对长度不等的关键字构造哈希函数。6.随机数法

实际造表时,采用何种方法来构造哈希函数,考虑的因素有：建表的关键字集合的情况(包括关键字的范围和形态),哈希表的大小,哈希函数计算时间和查找频率。总的原则是:减少集聚现象,在关键字取值范围内,使哈希函数值尽量均匀散列在函数值范围内,从而使产生冲突的可能性尽量减小。为产生冲突的关键字寻找下一个哈希地址。1.开放定址法2.链地址法

除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”

的方法。其含义是：3.建立公共溢出区三、处理冲突的方法

为产生冲突的关键字H(key)求得一个探测地址序列(在其中逐个探测空哈希地址)：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+

di

)MODm

di

为探测增量有三种，i=1,2,…,m-1

1.开放定址法(1)线性探测再散列

di=c

i

最简单的情况

c=1(2)平方探测再散列

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

di

是一组伪随机数列或者

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

di

的三种取法：即：产生的Hi

均不相同,且m-1个Hi值能覆盖

哈希表中所有地址。则要求：

注意：增量di

应具有“完备性”※

随机探测时的m

和di

应没有公因子；※

平方探测时的表长

m

应为形如4j+3

的素数（如:7,11,19,23,…等）；※

避免二次聚集。012345678910例如哈希表长m=11，现有关键字集合：

{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11

190123145568(1)采用线性探测再散列处理冲突1182361121362510123456789101901231468(2)采用二次探测再散列处理冲突55118236112121412ASL=22/9ASL=15/9设：H2(key)=(3key)MOD10+1

di=i×H2(key)190123145568118236211121214ASL=15/9012345678910(3)采用双散列函数探测线性探测处理冲突时：ASL=双散列探测处理冲突时：ASL=22/915/9二次探测处理冲突时：ASL=15/9本例不同的处理冲突方法的ASL为：将所有哈希地址相同的记录都链接在同一链表中。

012345614

0136198223116855

ASL=(6×1+2×2+3)/9=13/9设哈希函数为：H(key)=keyMOD7显然不会发生二次聚集2.链地址法：

按哈希函数的值域的范围设立向量为基本表,另设立同样大小的向量为公共溢出区,将所有发生冲突的记录都顺序存放在公共溢出区中。

3.建立公共溢出区

哈希表的查找过程和造表过程一致。

对于给定值K，计算哈希地址i=H(K)若r[i]=NULL则查找不成功若r[i].key=K则查找成功否则“求下一地址Hi”，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)为止。

采用开放定址处理冲突，则查找过程为：四、哈希表的查找决定哈希表查找ASL的因素：

(1)选用的哈希函数；

(2)选用的处理冲突的方法；

(3)哈希表饱和的程度，即装载因子α=n/m

值的大小（n—记录数，m—表的长度）

从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。五、哈希法性能分析

一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。

因此，哈希表的ASL是处理冲突方法