数据结构第9章

第九章查找重点：掌握顺序查找、折半查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。难点：二叉排序树的删除算法及B-树上的插入和删除算法。相关定义----查找表查找表(SearchTable)定义：由同一类型的数据元素(或记录)构成的集合。

“集合”中的数据元素之间存在着完全松散的关系查找表是一种非常灵便的数据结构操作查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；相关定义----查找表及其分类操作在查找表中插入一个数据元素；从查找表中删去某个数据元素。查找表的分类静态查找表：仅作查询和检索操作的查找表。动态查找表：在查询过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。相关定义----关键字关键字定义：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称之为主关键字；若此关键字能识别若干记录，则称之为次关键字。相关定义----查找查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

若查找表中存在这样一个记录，则称查找是成功的，此时查找结果为给出整个记录的信息，或指示该记录在查找表中的位置；

否则称查找不成功，此时查找结果可给出一个空记录或空指针。相关定义----类型定义typedefstruct{KeyTypekey; //关键字域

…… //其它域}ElemType;根据具体的关键字类型,定义用于比较的、带参的宏#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)原型：externintstrcmp(constchar*s1,constchar*s2);

用法：#include<string.h>功能：比较字符串s1和s2。

说明：当s1<s2时，返回值<0当s1=s2时，返回值=0当s1>s2时，返回值>09.1.1顺序查找查找表结构：以顺序表或线性链表表示基本思想：从一端开始向另一端，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，若直至另一端，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。

查找成功示例：

(34,44,43,12,53,55,73,64,77)，key=64

查找不成功示例：

(34,44,43,12,53,55,73,64,77)，key=889.1.1顺序查找对顺序表的顺序查找typedefstruct{ElemType*elem;//数据元素存储空间基址

intlength; //表长度}SSTable;i01234567891011

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

intSearch_Seq(SSTableST,KeyTypekey)

{

//在顺序表ST中顺序查找其关键字等于key的数据元素。

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

ST.elem[0].key

=key;

//“哨兵”

//从后往前找

for(i=ST.length;ST.elem[i].key!=key;--i);

returni;

//找不到时，i为0

}//Search_Seq

哨兵的作用：免去查找过程中每一步都要检测整个表是否查找完毕。

上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。9.1.2有序表的查找----折半查找1.设表长为n，low、high和mid分别指向待查元素所在区间的下界上界和中点,key为给定值。

2.初始时，令

low=1,high=n,mid=(low+high)/2

让key与mid指向的记录比较

若key==ST[mid].key，查找成功

若key<ST[mid].key，则high=mid-1

若key>ST[mid].key，则low=mid+1

3.重复上述操作，直至low>high时，查找失败。9.1.2有序表的查找-折半查找折半查找(二分查找)查找表结构：有序表基本思想：查找区间逐步缩小(折半)

查找成功示例：

123456789

(12,33,40,45,53,55,64,66,77)，key=64

low指示查找区间的下界;

high指示查找区间的上界;

mid=(low+high)/2

。9.1.2有序表的查找-折半查找lowhighmidlowlowmidmid9.1.2有序表的查找-折半查找基本思想：查找区间逐步缩小(折半)

查找不成功示例：

123456789

(12,33,40,45,53,55,64,66,77)，key=68lowhighmidlowlowmidmidlowlowmidmidlowlowmidmidhighhigh9.1.2有序表的查找-折半查找intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;

//置区间初值

while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;

//找到待查元素

elseif(LT(key,ST.elem[mid].key))high=mid-1;

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

elselow=mid+1;

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

}return0;

//顺序表中不存在待查元素}//Search_Bin9.1.2有序表的查找-折半查找性能分析判定树：折半查找的查找过程可以用二叉树描述。n=ST.length=10时，判定树的形态为：

52816397410查找成功时的ASL=该结点在判定树中的层次判定树的形态与n直接相关，与关键字的取值无关查找不成功时练习：画出对长度为12的有序表进行折半查找的判定树9.1.2有序表的查找-折半查找第九章查找9.1顺序查找9.2动态查找表9.3哈希表9.2.1二叉排序树----定义二叉排序树(二叉查找树)

BinarySort/SearchTree定义(递归)：或者是一棵空树，或者是具有如下特性的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也分别是二叉排序树。503080209010854035252388例如:是二叉排序树。66不9.2.1二叉排序树----定义通常，取二叉链表作为二叉排序树的存储结构。typedefstruct

BiTNode

{//结点结构

TElemTypedata;structBiTNode*lchild,*rchild;

//左右孩子指针}BiTNode,*BiTree;9.2.1二叉排序树----定义1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。否则若二叉排序树为空，则查找不成功；9.2.1-二叉排序树:查找算法50308020908540358832例如:二叉排序树查找关键字==50,505035,503040355090,50809095,9.2.1-二叉排序树:查找算法从上述查找过程可见，在查找过程中，生成了一条查找路径:

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

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功——查找不成功9.2.1-二叉排序树:查找算法9.2.1二叉排序树----插入二叉排序树的插入新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。示例：从空树出发，待插的关键字序列为33,44,23,46,12,37334423461237中序遍历二叉排序树可得到一个关键字的有序序列。该例中，中序遍历结果为：12,23,33,37,44,46

若从一棵空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。且对其进行中序遍历可得到一个关键字的有序序列。这说明一个无序序列可通过构造一棵二叉排序树而变成一棵有序序列。

9.2.1-二叉排序树:改进的查找算法503080209010854035252388中序序列为：1020232530354050808588909.2.1-二叉排序树:改进的查找算法9.2.1二叉排序树----删除二叉排序树的删除假设被删结点为*p，其双亲结点为*f，*p为叶子结点：删去*p，并修改*f的孩子域。*p只有左子树PL或只有右子树PR：令PL或PR直接成为*f的子树334423461237464633442346124544464546459.2.1二叉排序树----删除二叉排序树的删除*p的左子树PL和右子树PR均不为空33442346123744405048353846504833231237403538方法1：PL

接替*p成为*f的子树，PR成为PL最右下结点(中序遍历PL所得序列的最后一个结点)的右子树。40这种方法可能会导致二叉排序树高度的增长！本例中高度：564846509.2.1二叉排序树----删除二叉排序树的删除*p的左子树PL和右子树PR均不为空334423461237444050483538332312方法2：与方法1对称，PR接替*p成为*f的子树，PL成为PR最左下结点(中序遍历PR所得序列的最前一个结点)的左子树。46374035389.2.1二叉排序树----删除二叉排序树的删除*p的左子树PL和右子树PR均不为空方法3、令*p的中序遍历的直接前驱替代*p，再从二叉排序树中删去它的直接前驱。这种方法不会导致二叉排序树高度的增长！本例中高度：55删除时，如何不增长树的高度？334423461237444050483538404038383344234612374440504835389.2.1二叉排序树----删除二叉排序树的删除*p的左子树PL和右子树PR均不为空方法4：与方法3对称，令*p的中序遍历的直接后继替代*p，再从二叉排序树中删去它的直接后继。334423461244504837403538464648504850334423461237444050483538334423461237444050483538334423461237444050483538404038389.2.1二叉排序树----删除算法9.2.1二叉排序树----性能分析二叉排序树的查找分析与给定值比较的关键字个数不超过二叉排序树的深度示例：从空树出发，待插的关键字序列为33,44,23,46,12,37334423461237二叉排序树的形态与关键字的插入次序直接相关！如：将上例的关键字插入次序调整为：

12,23,33,44,37,46122333374446查找成功且各记录的查找概率相等时

ASL(a)=(1+2*2+3*3)/6=14/6查找成功且各记录的查找概率相等时ASL(b)=(1+2+3+4+5*2)/6=20/69.2.1二叉排序树----性能分析9.2.1二叉排序树----性能分析对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率和顺序查找一样。第九章查找9.1顺序查找9.2动态查找表9.3哈希表9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表9.1和9.2节讨论的各查找方法记录在查找表中的位置和它的关键字之间不存在确定的关系；查找是建立在比较的基础上(给定值vs.表中的关键字）查找效率依赖于查找过程中所进行的比较次数如何一次存取便能得到所查记录？记录的存储位置和它的关键字之间建立一个确定的对应关系H，以H(key)作为关键字为key的记录在表中的位置，称这个对应关系H为哈希(Hash)函数。9.3.1什么是哈希表例：30个地区的各民族人口统计表编号地区名总人口汉族回族…1北京2上海┆┆以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区名的第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=199.3.1什么是哈希表哈希函数是一个映象，哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可；冲突：key1≠key2，但H(key1)=H(key2)的现象

具有相同哈希函数值的关键字称做同义词。根据设定的哈希函数

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

H(key)=key或者H(key)=a·key+b此法仅适合于：地址集合的大小==关键字集合的大小，其中a和b为常数；例：解放后出生的人口调查表H(key)=key-1948地址010203…22…年份194919501951…1970…人数…………15000…┆9.3.2哈希函数的构造方法数字分析法关键字是以r为基的数，且哈希表中可能出现的关键字都是事先知道的，则取关键字的若干数位组成哈希地址。例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位，或两位与另两位的叠加作哈希地址9.3.2哈希函数的构造方法平方取中法取关键字平方后的中间几位作为哈希地址求“关键字平方”的目的是“扩大差别”，同时平方值的中间几位数和关键字的每一位都相关。9.3.2哈希函数的构造方法(4)折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取它们的叠加和(舍去进位)为哈希地址。移位叠加：将分割后的几部分低位对齐相加；间界叠加：从一端沿分割界来回折迭，然后对齐相加。例：关键字为0442205864，哈希地址分别为586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加9.3.2哈希函数的构造方法除留余数法H(key)=keyMODp,p≤mp为质数或不包含小于20的质因子的合数

为什么？例：给定一组关键字为:12,39,18,24,33,21，若取p=9,则它们对应的哈希函数值将为:

3,3,0,6,6,3

可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。

注意：p最好选取小于或等于表长m的最大素数。如表长为20，那么p选19，若表长为25，则p可选23，…。表长m与模p的关系可按下表对应：

m=8，16，32，64，128，256，512，1024，…

p=7，13，31，61，127，251，503，1019，…9.3.3处理冲突的方法“处理冲突”的实际含义是：

为产生冲突的地址寻找下一个哈希地址。处理冲突的方法

开放定址法、链地址法、再哈希法、建立公共溢出区开放定址法为产生冲突的地址H(key)求得一个地址序列：

H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm，其中：i=1,2,…,s H(key)为哈希函数; m为哈希表长; di为增量序列；9.3.3处理冲突的方法开放定址法对增量di的三种取法：线性探测再散列

di=c×i，最简单的情况c=1平方探测再散列

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

di

是一伪随机数序列二次聚集：在处理同义词的冲突过程中又添加了非同义词的冲突，这种现象称作“二次聚集”。9.3.3处理冲突的方法开放定址法例:给定关键字集合构造哈希表

{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突012345678910191011232141551683116822365012345678910191011232141551684113821362二次探测会降低“二次聚集”发生的概率9.3.3处理冲突的方法链地址法将所有关键字为同义词的记录存储在同一线性链表中例:关键字