数据结构第9章 查找

第九章查找

查找表（SearchTable）是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。关键字（key）是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。主关键字唯一地标识一个元素，次关键字识别若干元素查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度(AverageSearchLength)。查找表通常可分两类：

1.静态查找表

2.动态查找表如何评价查找算法的时间效率？对查找表经常进行的操作有：

（1）查询某个"特定的"数据元素是否在表中；

（2）检索某个"特定的"数据元素的各种属性；

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

（4）从查找表中删除某个数据元素。9.1静态查找表9.1.1顺序表的查找实现静态查找表的最简单的方法是以“顺序存储结构的线性表-顺序表”表示之。查找过程为：从第一个或最后一个数据元素起，逐个进行“比较”直至其中某个数据元素的关键字等于给定值为止。缺点：其平均查找长度较大，特别是当表中记录数n很大时，查找效率较低。优点：算法简单且适应面广，无论表中记录是否按关键字有序排列均可应用，而且，上述讨论对链式存储的线性表也同样适用。9.1.2有序表的查找

折半查找(BinarySearch)又称二分查找折半查找的过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间”或“后半个区间”之后继续进行查找。例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找关键字为21和85的数据元素。算法

int

Search_Bin(SSTableST,KeyType

kval)

{

//在有序表ST中折半查找其关键字等于kval的数据元素，

//若找到，则函数值为该元素在表中的位置，否则为0。

low=1;high=ST.length;

//置区间初值

while(low<=high){

mid=(low+high)/2;

if(kval==ST.elem[mid].key)

returnmid;

//找到待查元素

else

if(kval<ST.elem[mid].key)

high=mid-1;

//继续在前半区间内进行查找

elselow=mid+1;

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

}//while

return0;

//有序表中不存在待查元素

}//Search_Bin9.1.3索引顺序表的查找

线性表中的记录按关键字“分段有序”称它为"分块有序表")，同时，另建一个"索引"，由"分块有序表"和相应的"索引"构成一个"索引顺序表"，

索引表13718648225386497458604824384442332098131222最大关键字起始地址9.2动态查找表9.2.1动态查找表的类型定义

动态查找表的特点：在查找过程中尚需进行"插入"或"删除"的操作。因此，表示动态查找表的结构应不仅便于查找，还应便于插入和删除。抽象数据类型动态查找表的定义参见教材P226-2279.2.2二叉查找树

一、二叉查找树的定义

二叉查找树或者是一棵空树；或者是具有如下特性的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；

（3）它的左、右子树也都分别是二叉查找树。

例如，下图所示是一棵二叉查找树

二叉链表作为二叉查找树的存储结构typedef

struct

BiTNode

{

//结点结构

ElemTypedata;

//数据元素

struct

BiTNode

*lchild,*rchild;

//左右孩子指针

}

BiTNode,*BSTree;

例如，下图所示是不是一棵二叉查找树？

二、二叉查找树的查找算法

若二叉查找树为空，则查找不成功；否则

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

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

3）若给定值大于根结点的关键字，则继续在右子树上进行查找。

三、二叉查找树的插入算法

二叉查找树结构本身正是从空树开始逐个插入生成的。插入的原则：若二叉查找树为空树，则插入的结点为新的根结点；否则，插入的结点必为一个新的叶子结点，其插入位置由查找过程确定。例如，若给定值序列为{50,30,40,80,20,36,90,40,38}

四、二叉查找树的删除算法

分三种情况讨论：

(1)被删结点为“叶子”，仅需修改其双亲结点的相应指针；(2)被删结点只有左子树或右子树，则只需保持该结点的子树和其双亲之间原有的关系(3)被删结点的左右子树均不空。四、二叉查找树的删除算法

FPPLPRfp（a）（b）fFPCPRCLQQLSLScpqs四、二叉查找树的删除算法

FCCLfc（c）SLPRSs方法1*p的左子树为*f的左子树*p的右子树为*s的右子树（b）fFPCPRCLQQLSLScpqs四、二叉查找树的删除算法

（d）fFSCPRCLQQLSLcpq方法2*p的直接前驱或直接后继代替*p，然后再从二叉排序树中删除它的直接前驱或直接后继。（b）fFPCPRCLQQLSLScpqs参见教材p230算法9.7算法9.89.2.3平衡二叉(查找)树

平衡二叉树：它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉树，且左右子树深度之差的绝对值不大于1。平衡二叉树非平衡二叉树树中结点内的数值称作结点的"平衡因子"，定义为左子树的深度减去右子树的深度。

"平衡"处理的原则是保证二叉查找树始终处于平衡状态。从空树起（空树是平衡树），每插入一个关键字都需要检查二叉查找树是否失去平衡，如因插入新的结点引起不平衡，则需对它进行"平衡旋转"处理。9.3哈希表

9.3.1何谓哈希表

记录在表中的位置为关键字的某个函数，通常称这种函数为“哈希函数”。若关键字不同而函数值相同，则称这两个关键字（对于该哈希函数而言）为"同义词"，并称这种现象为"冲突"。

根据设定的哈希函数

H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的"象"作为相应记录在表中的存储位置，这种表被称为哈希表，这一映象的过程亦被称为"散列"。

9.3.2构造哈希函数的方法

若对于关键字集合中的任意一个关键字，经哈希函数映象到地址集合中任何一个地址的概率相等，则称此类哈希函数为均匀的哈希函数

构造均匀的哈希函数的方法有如下几种：

一、直接定址法

Hash(key)=key或Hash(key)=akey+b

（a和b均为常数）

直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，决不会产生冲突。但实际应用中能采用直接定址的情况极少。

二、数字分析法

如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行分析，取其中“分布均匀”的若干位或它们的组合作为哈希表的地址。①②③④⑤⑥⑦⑧02146532021722420228742702201367022288170223298202354152023685350231932702395715例如已知80个记录的关键字为8位十进制数（右图列出其中部分），假设哈希表的表长为100，即地址为00～99。三、平方取中法

如果关键字的所有各位分布都不均匀，则可取关键字的平方值的中间若干位作为哈希表的地址。例如：右表八进制数的关键字及其哈希地址

关键字(关键字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624314704314216147347417342162474130474121634745651745四、折叠法若关键字的位数很多，且每一位上数字分布大致均匀，则可采用移位叠加或间界叠加，即将关键字分成若干部分，然后以它们的叠加和(舍去进位)作为哈希地址。

例如，key=110108780428895

，(哈希表的表长为1000)

895

824780

801+）1103410

895428780108+）1102321间界叠加移位叠加五、除留余数法以关键字被某个数p除后所得余数作为哈希地址。即Hash(key)=keyMODp其中，MOD表示"取模"运算，p为不大于表长的素数或不包含小于20的质因素的合数。

六、随机数法

当关键字不等长时，可取关键字的某个伪随机函数值作为哈希地址。

Hash(key)=random(key)

对于非数值型关键字，则需先将它们转化为数字。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。

9.3.3处理冲突的方法有两类处理冲突的方法:

一、开放定址法

二、链地址法

一、开放定址

处理冲突的办法是，设法为发生冲突的关键字"找到"哈希表中另一个尚未被记录占用的位置。哈希表的表长为m（即哈希表中可用地址为：0～m-1），若关键字key，Hash(key)的位置已被占用，则"下一个"地址H1=(Hash(key)+d1)MODm，

若也已被占用，则再H2

=(Hash(key)+d2)MODm，

…，依次类推直至找到一个地址Hs=(Hash(key)+ds)MODm未被占用为止。即Hi是为解决冲突生成的一个地址序列，其值取决于设定"增量序列di"。对于di通常可有三种设定方法：

“线性探测再散列”，di=1,2,3,…,m-1，2.“平方探测再散列”，di=12,-12,

22,

-22,…,

k2(k≤m/2)，3.伪随机探测再散列“或”双散列函数探测再散列

为伪随机数列或者di=i×H2(key)，（H2(key)为关键字的另一个哈希函数）按线性探测再散列处理冲突构造的哈希表为：012345678910562314688270361991按平方探测再散列处理冲突构造的哈希表为：012345678910562314708268361991按双散列函数探测处理冲突构造的哈希表为：012345678910235668147082911936二、链地址法

将所有关键字为"同义词"的记录链接在一个线性链表中例如，假设关键字序列为{19,56,23,14,68,82,70,36,91}，哈希表的表长为7，哈希函数为Hash(key)=key%7，则构建的以链地址处理冲突的哈希表如flash9-4-2所示。

9.4.4开放定址的哈希表的查找和插入

在利用开放定址处理冲突的哈希表中进行查找时，首先应计算给定值的哈希函数值，若表中该位置上没有记录，

则表