数据结构课件-查找

第九章查找第九章和第十章介绍数据处理中常用的两种操作：查找和排序。许多软件都为用户提供了查找和排序功能。

例如：文本编辑软件Word，

各种信息管理软件。在前面讨论的数据结构：线性表、树、图等，都可以根据实际情况（需要），将查找或排序作为它们的基本操作。

查找和排序操作应用面广，使用频率高，所以对查找和排序算法的质量，如时间效率，空间效率要求比较高。事实上任何软件系统的核心程序，如操作系统,使用频率高，因此操作系统的各种算法，无论是文件管理、内存管理程序也都需要有很高的质量。下面两章专门讨论查找和排序，讨论应用中常用的几种查找方法，排序方法，它们的特点及适用场合。

第九章查找9.1静态表查找表9.2动态表查找表9.3哈希表

查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。在这里，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个或一组数据元素。

一、查找表的概念1.查找表：由同一类型数据元素（或记录）构成的集合。在查找表中数据元素除了同属一个集合，不考虑元素之间其它关系。2.查找表基本操作1）构造查找表Create(&ST,n)2）销毁查找表Destroy(&ST)3）各种查找操作二、查找的有关概念1.静态查找表、动态查找表查找表最基本的操作是查找，常用的查找操作：

1）查询某个“特定”元素是否在表中；

2）检索某个“特定”元素的各种属性；

3）查找某个“特定”元素是否在表中，若不在，则将该元素插入表中；

4）从查找表中删除某个“特定”元素；

若对查找表只有1）、2）两种查找，称为静态查找表；

若查找表提供3）、4）两种查找操作，称为动态查找表；2记录、关键字记录：由若干数据项构成的数据元素称为记录关键字：数据元素（或记录）中某个数据项,可以标识数据元素。

学号姓名专业年龄

01 王洪 计算机17

02孙文计算机18

03谢军计算机18

04 李辉 计算机20

05沈祥福计算机25

06余斌 计算机19

07 巩力计算机17

08 王辉计算机18例：学生管理系统，若想按姓名查找，可将姓名作为关键字，若想按学号查找，可将学号作为关键字。说明：

①记录的任何数据项都可作为关键字；

②若此关键字的值能唯一标识记录，则称该关键字为

主关键字，否则次关键字；例：学号是主关键字，姓名不重名时可以作为主关键字。其他数据项都可以作为次关键字。3查找

应用中有各种各样的查找，本章讨论的查找操作定义如下：查找：给定某个值，在查找表中查找关键字值等于给定值的记录，若表存在这样的记录，则称查找成功，查找结果为该记录（在表中）的位置，否则称为查找不成功，查找结果为0或nu11。

4平均查找长度(ASL:AverageSearchLength)

要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中Ｐi为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，Ｃi为查找第i个元素所需要的比较次数。三、查找表的组织与查找如何在查找表中查找？取决于如何组织查找表

例1：

查找索引号为TP312.12的图书

1)若图书馆中的图书无序地摆放，则只能顺序查找；

2)若图书按索引号顺序摆放，则可先找到TP类图书，再找到TP3

例2

在词典中查找单词

are

1)先找到a打头的单词，再在a打头的单词中找

2)若词典中无序排列，则只能顺序查找；

本章介绍：

静态查找表的组织方法与查找动态查找表的组织方法与查找哈希表的组织方法与查找

约定：假设1)本章查找是关于主关键字查找；2）假设本章涉及的关键字为整型类型；3）为使查找的图示简洁，对于查找表中的每一记录，只写出其关键字；

关键字类型定义为

typedef

int

KeyType;

记录类型定义为：

stypedef

struct{

KeyTypekey;//关键字域

…//其它域}ElemType;

R={01,02,03,04,05,06,07,08}4)本章所讨论的查找方法，只要稍加修改即可用于其他类型的查找例学号姓名专业年龄

01 王洪 计算机17

02孙文计算机18

03谢军计算机18

04 李辉 计算机20

05沈祥福计算机25

06余斌 计算机19

07 巩力计算机17

08 王辉计算机189.1静态查找表只提供如下两种查找的查找表，称为静态查找表

1）

查询某个“特定”元素是否在表中；

2）

检索某个“特定”元素的各种属性；对静态查找表介绍三种组织与查找方法顺序表及查找

有序表及查找索引表及查找9.1.1顺序表及查找（线性表及查找）查找表组织：查找表用线性表表示。即将查找表的记录排成一个记录序列。L1=(45,53,12,3,37,24,100,61,90,78)

顺序查找法1）基本思想：从表的最后一个记录（或第一个记录）开始，依次将记录的关键字与给定值比较，若相等：查找成功，否则，继续查找。设查找表用顺序表存储，其类型定义如下：Typedef

struct{

ElemType*elem;

intlength;}SSTable2)算法int

Search_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。ST.elem[0].key=key;//ST.elem[0].key为“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].key);-

-i)//从后向前找returni;//若表中不存在待查元素，i=0

}//Search_Seq

3)平均查找长度

假设在每个位置查找的概率相等，即有pi=1/n，由于查找是从后往前扫描，则有每个位置的查找比较次数Cn=1，Cn-1=2，…，C1=n，于是，查找成功的平均查找长度ASL====,即它的时间复杂度为O(n)。这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须进行n+1次比较之后才能确定查找失败。另外，从ASL可知，当n较大时，ASL值较大，查找的效率较低。顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。顺序查找对存储结构无要求，算法也很简单，所以在元素较少时，算法还是很有效的。因此，平时应用较为广泛。*已知每个元素的Pi不等且其顺序已知

p1<p2……<pn

按pi的大小存储元素，即可节省时间。如：哈夫曼编码。*已知每个元素的pi不等，但不知其顺序。对每个r[i]，记录r[i]的查找次数，每次查找与它后面记录r[i+1]的次数比较，大于就后移。9.1.2有序表的查找

有序表：若线性表中的记录按关键字有序，则称为有序表查找表组织：查找表用有序表表示。即将查找表的记录排成按关键字有序的序列。二分查找法（也称为折半查找法）1）基本思想：将查找范围中间位置的记录关键字与给定值比较：

＜：继续在前半个表中用二分查找法查找

=：查找成功，返回记录位置

＞：继续在后半个表中中用二分查找法查找

例1

L2=(3,12,24,37,45,53,61,78,90,100)，查找

Key=24的记录

12345678910

31224374553617890100lowmid

high

12345678910

31224374553617890100lowmid

high

24＜45继续在前半个表中用二分查找法查找

12345678910

31224374553617890100Lowmidhigh

24＞12继续在后半个表中用二分查找法查找查找成功算法int

Search_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。Low=1;high=ST.length;While(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key,ST.elem[mid].key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//表中不存在待查元素

}//Search_Bin设查找每一个记录的概率相同，即均为1/10，平均查找长度ASL

=在查找过程中与给定值比较的关键字个数的数学期望值

PiCi=（1+2

2+4

3+3

4）/10二分查找法查找过程可用判定树描述

12345678910

例

L2=(3,12,24,37,45,53,61,78,90,100)，查找过程可用如下判定树描述

5

4

3

1

6

7

9

8

210Key=24的查找路径为5,2,3,所需的比较次数为3查找第5个记录需的比较次数为1查找第2、8个记录需的比较次数均为2 说明：折半查找法效率比顺序查找高;平均查找长度ASLbs=log2（n+1）-1要求表中的记录按关键字有序；表中的记录要用顺序结构存储； 例在有1000个记录的查找表查找，顺序查找法平均要比较500次，折半查找法平均要比较9次，可见折半查找法效率比顺序查找高。9.1.3分块查找（索引表查找）顺序查找简单并且对存储结构无要求，折半查找有效但要求表有序，将二者结合起来，取各自的优点，就是分块查找。将表分为若干子表，子表内部无序，子表之间有序。（后续表中任一关键字均大于前驱表中的最大关键字。k1k2k3…….

…k1

…k2

…k3……

索引表的项数与主表的块数相等，每一个表项对应主表的一个子表。索引表有序。查找方法：

1)在索引表中查找给定值对应的子表（可以顺序查找，也可以折半查找）。2)在相应子表中顺序查找。也称为索引顺序查找。存储结构：索引表可用顺序或链式。主表：子表中用顺序，子表之间用链式。

索引表当索引表较大时，可以采用二分查找在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级12345678910111213141516171822121389203342443824486058745786532248861713查38

平均查找长度：假设表长为n，分为b块，子表长：s=n/b,索引表长为b

则：ASL=(b+1)/2+(s+1)/2

当s为n开平方时，效率最高。

三种查找方法比较顺序查找折半查找分块查找表的存储结构顺序、链式顺序索引表---顺序、链式主表----顺序、链式、顺序、链式混合关键字的有序性无有序索引有序主表分块有序ASL最大最小居中9.2动态查找表动态查找表

如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表中，对这类表除了提供1）、2）两种查找外，还要提供动态查找功能：3）

查找某个“特定”元素是否在表中，若不在，则将该元素插入表中；

4）

查找某个“特定”元素是否在表中，若在，从表中删除该元素；如何组织动态查找表？线性表：顺序查找效率低有序表：二分查找法须用顺序结构存储有序表，插入删除操作要移动元素；本节介绍动态查找表的一种组织形式——二叉排序树9.2.1

二叉排序树和平衡二叉树

1.二叉排序树二叉排序树（BinarySortTree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树分别为二叉排序树；二叉排序树4537245310061907831245372453100619078312根据二叉排序树的定义，对二叉树进行LDR遍历得到是递增序列。3,12,24,37,45,53,61,78,90,1002二叉排序树的查找在二叉排序树中查找关键字为key的记录基本思想若二叉排序树为空树，查找失败，返回null或0；否则，将key与根结点的关键字比较：若key=根结点的关键字,查找成功，返回该记录在二叉排序树中的位置；若key

根结点的关键字，继续在左子树中查找；若key

根结点的关键字，继续在右子树中查找；例在如下二叉排序树中查找关键字为24的记录24

45继续在左子树中查找24

12继续在右子树中查找24

37继续在左子树中查找Key=24查找成功！45372453100619078312例在如下二叉排序树中查找关键字为60的记录查找失败！查找路径左子树为空45372453100619078312算法BiTree

SearchBST(BiTreeT,KeyTypekey){//二叉排序树用二叉链表存储。在根指针T所指二叉排序树中递归地查找//关键字等于key的记录，若查找成功，则返回该记录结点的指针，否则//返回空指针

if(!T)||EQ(key,T->data.key)return(T);//若T为空或查找成功，返回elseifLT(key,T->data.key)

return(SearchBST(T->1child,key));//在左子树中继续查找

return(SearchBST(T->rchild,key))//在右子树中继续查找}//SearchBST性能分析：二叉排序树的查找效率与树的形态有关，若树的形态为“单枝”，二叉排序树的查找就“退化”为顺序查找；若树的形态比较“平衡”，二叉排序树的查找与二分查找类似；为获得较高的查找效率，需要构造“平衡”的二叉排序树。关于如何构造平衡二叉树，后面介绍。5345372410061907831253453724613123二叉排序树的插入、删除二叉排序树是动态查找表的组织形式,动态查找表要提供插入删除数据元素的操作。在一般二叉树的基本操作中只有插入、删除子树操作，没有插入、删除结点操作。原因是:除了叶子结点外，在二叉树中插入、删除结点将破坏树的结构。下面介绍如何在二叉排序树中插入、删除。二叉排序树是作为动态查找表的组织形式，目的是获得较高的查找效率并且能方便地进行插入删除操作。因此在二叉排序树中插入、删除结点的原则是：插入、删除结点后仍是二叉排序树。1）二叉排序树的插入

新插入的结点为叶子结点，并且是查找不成功时，查找路径上最后一个结点的左孩子或右孩子。

将新结点插入二叉排序树基本步骤：

从二叉排序树的根结点开始，若二叉排序树为空树，新插入结点作为根结点，否则，若当前结点为叶子结点，若新插入结点的关键字

当前结点的关键字，则将新结点作为当前结点的左孩子，否则作为右孩子；否则，若新插入结点的关键字

根结点的关键字，将新结点插入左子树；否则插入右子树45372453100619078312算法(先改写前面的查找算法,以便查找不成功时返回插入位置)StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指针T所指二叉排序树中递归地查找关键字等于key的记录，若查找成功，则//用P返回该记录结点的指针，并返回TRUE,否则P指向查找路径上访问的最后一个结点//并返回FLASE,指针f指向T的双亲,其初始调用值为NULL

if(!T){p=f;returnFLASE;}//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}

//若T为空或查找成功，返回elseifLT(key,T->data.key)return(SearchBST(T->lchild,key,T,p));

//在左子树中继续查找elsereturn(SearchBST(T->rchild,key,T,p))

//在右子树中继续查找}//SearchBST插入算法

StatusInsertBST(BiTree&T,ElemTypee){

//指针T所指二叉排序树中不存在关键字等于key的记录时插入，并返回TRUE；否则返回FLASE

if(!SearchBST(T,key,NULL,p){

//查找不成功s=(BiTree)malloc(sizeof(BITNode));

s->data=e;s->lchild=s->rchild=NULL;

if(!p)T=s;//被插入的结点为根结点elseifLT(e,p->data.key)p->lchild=s;elsep->rchild=s;returnTRUE;}

return

FLASE;}//InsertBST例在如下二叉排序树中插入结点40为查找插入位置走过的路径插入结点40！4537245310061907831240插入首先执行查找算法，找出被插结点的双亲结点。判断被插结点是其双亲结点的左、右孩子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。例：将序列：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。122992503002801102）二叉排序树的删除在二叉排序树中删除结点的原则是：删除结点后仍是二叉排序树。对二叉排序树进行中序遍历，所得到的中序序列是一有序序列。如对如图所示的二叉排序树进行中序遍历，其中序序列为：3，12，24，37，45，53，61，78，90，100，在二叉排序树中删除一个结点相当于在有序序列删除一个结点，只要删除结点后仍保持二叉排序树的特性。如何在二叉排序树中删除一个结点?？45372453100619078312在二叉排序树中删除一个结点，分三种情况：(1)p仅有一个结点（被删除的结点是叶子），新树t=null(2)p仅有一棵子树。T=p->lchild

或t=p->rchild(3)p有两棵子树，情况比较复杂，问题可以归结为在一棵子树中删除根结点，根结点删除后，二叉排序树变成两棵子树。最后的问题是将两棵二叉排序树合成一棵新的二叉排序树。有两种方法解决，我们分别讨论。tPPLPRPPPRPLPR

CCLSL

Q

SQL

F(a)

F

C

SPRCL

QQLSL(b)SL

F

C

PPRCL

Q

SQL删除P前的二叉排序树P既有左子树PL也有右子树PR

,如图，二叉排序树的中序序列为(…FCLC…QLQSLSPPR…)S是P的直接前趋，S是P的左子树的最右下结点，S至少没有右子树。在删除P后,为保持中序序列中其它元素之间的相对位置不变，可有两种方法(a)令P的左子树的根C作为新树的根，而P的右子树为S的右子树；（b)用P的直接前趋S代替P，然后从二叉排序树删除P的直接前趋S；方法（a):t=p->lchild;s=t;while(s->rchild)s=s->rchilds->rchild=p->rchild

同理，可将p的右子树的根作为新树的根，将PL

插入p的右子树的适当位置。这种方法，删除后树的深度增加了。会降低查找效率。方法(b)：找到PL的右支末端结点s将p->data=s->data。然后删除s,s可能无左右子树，也可能有一个左子树。S删除后，它的左子树应连在s的双亲右子树上。但是，若PL无右子树，可将PL的左子树连在p的左子树上。

t=p;q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}p->data=s->data;if(q!=p)q->rchild=s->lchild

elseq->lchild=s->lchild

该方法，算法复杂一些，但树的深度没有增加。

Pqspq=psPqs算法

StatusDeleBST(BiTree&T,KeyTypekey){//在根指针T所指二叉排序树中存在key,则删除并返回TRUE,否则返回FLASE

if(!T)returnFLASE;//查找不成功else{ifEQ(key,T->data.key){returnDelete(T)}

;//若T为空或查找成功，返回elseifLT(key,T->data.key)return(DeleBST(T->lchild,key));elsereturn(DeleBST(T->rchild,key));}//DeleBSTDelete算法

StatusDelete(BiTree&p){//从二叉排序树删除结点p，并重接它的左或右子树

if(!p->rchild){q=p;p=p->lchild;free(q);}//右子树空elseif{(!p->lchild){q=p;p=p->rchild;free(q);}

//左子树空else{

//左右子树均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;

free(s)}returntrue}//Delete二叉排序树的删除操作例子

叶子结点：直接删除。如：删除数据为15、70的结点。1560703020506030205012225030011020099105230216400450500若被删结点的左孩子为空或者右孩子为空。如下图所示，删除结点的数据值为200的结点。删除20012225030023021640045050011099105被删结点的左、右子树皆不空1222503001102009910523021640045050011025030010520099230216400450500二叉排序树的查找效率与树的形态有关，而树的形态取决于建立二叉排序树时的输入序列。例：{8，12，3，10，18，2，7}

ASL=(n+1)/nlog2(n+1)-1{8,18,7,10,2,12,3}{2,3,7,8,10,12,18}

ASL=(n+1)/2由此，二叉排序树的查找效率相差比较大，平均性能ASL=1+4log2n183210718128238718101223课堂练习1222503001102009910523021640045050011025030010520099230216400450500删除250、230删除400、230平衡二叉树1.定义：平衡二叉树(BalancedBinaryTree或Hight-BalancdeTree)，是由阿德尔森一维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。2.平衡因子：将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balancefactor)。

这就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。如下图(a)所示二叉排序树，是一棵平衡二叉树，而下图(b)

所示二叉

排序树，就不是一棵平衡二叉树。

图(a)53453724100619078312图(b)53453724619078312二叉排序树的查找效率与树的形态有关，而树的形态取决于建立二叉排序树时的输入序列。如果对任何的输入序列建成的二叉排序树都是AVL树。要用建立二叉排序树的方法，建立平衡二叉树，在树不平衡时做适当的调整。3.修改二叉排序树的插入算法*判定树的不平衡性，每个结点增加一个表示平衡因子的数据项bf。*平衡操作，确定平衡处理的范围并进行平衡处理。

9

53

9

53

9

5353453724100907812924912平衡处理的范围：最小的一个不平衡子树。4.平衡操作

(1)RR旋转（单向左旋平衡处理）：设a指向最小不平衡子树的根。在a的右子树的右子树插入新结点，造成a子树的不平衡。a的bf由-1变为-2。设a的左子树AL高为h-1,b子树高为h,b的左子树BL和b的右子树BR高均为h-1。在树中有AL<a<BL<b<BR，平衡后仍然要保持这个关系。进行一次向左的逆时针旋转，可以将不平衡的树平衡，并且保持旋转前的大小关系。abALBLBRabALBLBR

(2)LL旋转（单向右旋平衡处理）：设a指向最小不平衡子树的根。在a的左子树的左子树插入新结点，造成a子树的不平衡。a的bf由1变为2。

进行一次向右的顺时针旋转。abARBLBRabARBLBR

(3)RL旋转（双向旋转先右后左）：设a指向最小不平衡子树的根。在a的右子树的左子树插入新结点，造成a子树的不平衡。a的bf由-1变为-2。

先向右的顺时针旋转，后向左的逆时针旋转。abALBLBRabALCLBRcCRRL平衡处理后的二叉树abALCLBRcCR

(4)LR旋转（双向旋转先左后右）：设a指向最小不平衡子树的根。在a的左子树的右子树插入新结点，造成a子树的不平衡。

平衡处理方法：与RL旋转对称，先向左的逆时针旋转，后向右顺时针旋5.平衡操作小结：

1)LL和RR，LR和RL在操作方法上分别是对称的。2)在bf不等于0的结点下插入新结点，或者破坏平衡，或者不破坏平衡。3)插入破坏平衡时，最小不平衡子树插入前的树高和插入后并做平衡处理后树高一样，因此，该子树外的结点平衡因子不受影响4)在插入路径上，从a到插入点（除a以外），新结点的祖先的平衡因子要重新确定。5)a,b(或含c)，他们的互相连接关系改变，但是不改变他们的大小顺序。

为了从任何的输入关键字序列得到二叉排序树均为AVL树,需要对二叉排序树的插入算法做如下修改。（1）判别插入结点之后是否产生不平衡（2）找到失去平衡的最小子树（3）判别旋转类型并做相应平衡处理由此，算法分下面三步：（1）插入，找插入点的同时检查每个结点的bf，记录

bf不等于0的结点（有可能成为不平衡子树的根）,插入结点。（2）判定平衡性，不平衡则做相应的平衡处理（3）修改a到新插入点路径上的bf注：找a的同时，要记录a的双亲，以便a子树平衡后的子树可以插入在a原来的位置。在平衡二叉树上插入一个新的数据元素的算法见P2379.11左平衡处理算法9.12,右平衡处理算法类似9.12，算法9.9和9.10在平衡处理中进行右旋操作和左旋操作时修改指针的情况。

在平衡二叉树上进行查找的时间复杂度为O(logn)例：avl树例题..\avl树例题1.ppt课堂练习:

关键字序列为{8，6，4，10，12，9，7}，画出生成AVL树的步骤并指出平衡操作的类型。9.2.2B-树

B-树是一种平衡多叉树。在文件系统中非常有用，数据库系统的文件组织很多系统用B-树。1.B-树的定义一个m阶的B-树，或为空树，或为满足下列特性的m叉树(1)树中每个结点至多有m棵子树；(2)若根结点不是叶结点，则至少有两棵子树；(3)除根之外的所有的非终端结点至少有

m/2棵子树(4)所有的非终端结点中包含下列信息(n,A0,K1,A1,K2,A2,……Kn,An)

其中：Ki(i=1,2,……,n)为关键字，且Ki<Ki+1(i=1,2,……,n-1);Ai(i=0,1,2,……,n)为指向子树根结点的指针，且Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,……,n),An所指子树中所有的关键字均大Kn,n(

m/2-1nm-1)为关键字的个数(n+1为子树个数。)(5)所有的叶子结点都出现在同一层次上，并不带信息。3阶B-树（又叫2-3树）70852440977177515735122.B-树的查找在一个结点中可以折半查找（key有序），也可以顺序查找（key较少），整个查找按树查找。

结点的类型说明：#definem3//B-树的阶

typedef

struct

BTNode{

int

keynum;//结点中关键字个数

struct

BTNode*parent;//指向双亲结点的指针

keytypekey[m+1];//关键字向量，0单元未用

struct

BTNode*ptr[m+1];//子树指针向量

record*recptr[m+1];//记录指针向量，0单元未用}BTNode,*Btree;//B树结点，B树类型

查找结果的类型说明：

typedef

struct{

BTNode*pt;//指向找到的结点

inti;//结点中关键字的序号

inttag;//1查找成功，0查找失败}Result;//B树的查找结果类型

查找步骤：(1)若树为空，查找失败(2)将给定值与指定结点的关键字组比较，确定kiK<Ki+1(3)Ki=K。查找成功，P指向该结点，i返回结点中关键字的序号tag=1(4)Ai==null,查找失败，P=Ai,i,tag=0(5)取Ai所指结点，转(2)。ResultSearchBTree(BTree

T,keyTypek){p=T;q=null;found=FlASE;i=0;//初始化，p指向待查结点，//q指向p的双亲While(p&&!found){i=Search(p,k);//在p->key[1..keynum]中查找if(i>0&&p->key[i]==k)found=TRUE;//找到kelse{q=p;p=p->ptr[i];}}if(found)return(p,i,1);elsereturn(q,i,0);}//SearchBTree

在B-树上查找所需时间取决与两个因素：1)要查找的关键字所在的层次2)结点中的关键字数目

3.B-树的插入1）在B-树中从根开始查找，找到插入码所在的位置，若该码已经存在，则出错，否则就找到了应插入的最底层的某个非终端结点。

2）在插入后，若被插入结点中项数<m，则插入操作完成。如果被插入的结点项数=m，则分裂结点，并继续向上一级插入，这是一个递归的过程，从最底层的某个非终端结点沿着原来的查找路径反向进行。

插入步骤：1）若树为空，建立新结点2）查找关键字的插入位置3）插入，且keynum+14）如果keynum<m，插入结束5）分裂结点1—m/2-1,放在原结点中，X=key[

m/2],向上一级插入，

m/2+1—m申请新结点。6）以双亲为当前结点，插入X，若双亲存在转2），否则转1）

例子见P242图9.16(a)---(j)算法见P2449.144.删除在B-树上删除一个关键字K，找到K所在的结点P1）P为叶子结点，则删除K，若keynum

m/2，则删除结束，否则合并结点。2）P为非终端结点，若K=Ki,Ki为要删除的关键字，则以指针Ai所指子树中最小的关键字Kx代替Ki，删除Kx（Kx所在的结点P为叶子结点）归结为1）。因此，仅讨论删除叶结点中的关键字。设被删除关键字所在的结点为P1）P中keynum

m/2，则删除Ki和相应的指针Ai。例:P245图9.17(a)删除122）P中keynum=

m/2-1，P的左兄弟或右兄弟中keynum>

m/2-1，则将其左兄弟中最大的关键字或右兄弟中最小的关键字Kx移到双亲结点中，而将其双亲中小于或大于Kx的关键字Ky下移到P中。例:P245图9.17(b)删除503）P和P的左右兄弟结点中的keynum=

m/2-1，没有关键字可借，进行结点的合并。设P有右兄弟（无右兄弟时和左兄弟合并）。把P结点中剩余的关键字和指针，加上双亲结点中的那个关键字（P和右兄弟之间的）一起放到右兄弟结点中。这样双亲结点中删除了一个关键字，则又需要做借关键字或合并处理，这个过程是递归的，最坏情况可能波及到根，此时，整个B-树减少一层。例:P245图9.17(c)、(d)删除53，379.3哈希表

上两节介绍的查找表查找方法的共同特点：通过比较查找，即通过将记录关键字值与给定值比较，来进行查找。查找算法的时间效率取决于查找过程中所进行的比较次数。理想的方法是：不需要比较，根据给定值能直接定位记录的存储位置。显然，要想根据给定值能直接定位记录的存储位置。需要在记录的存储位置与该记录的关键字之间建立一种确定的对应关系，使每个记录的关键字与一个存储位置相对应。例1949-2000年某地区人口统计表

各年度人口统计记录的存储位置=年度-1948年份人数

123515219491950195119992000200021002200440044209.3.1什么是哈希表：

哈希函数用来定义记录的关键字与记录存储位置的对应关系的函数其自变量是记录的关键字，函数值是记录存储位置。

哈希地址：由哈希函数求出的记录存储位置称为哈希地址

哈希表：也叫散列表，是将记录按哈希函数确定的位置存放而构成的表例

1949-2000年某地区人口统计表关键字：年份哈希函数：H（KEY）=KEY-1948哈希表年份人数

12351521949195019511999200020002100220044004420

哈希表是查找表的又一种组织形式，其记录在哈希表的存储位置，由哈希函数决定。根据关键字及实际应用，确定哈希表表长，并构造哈希函数。为获得较高的查找效率，哈希函数应是一些便于计算的简单函数。然而，由于应用中的关键字形形色色，很难保证所构造出的哈希函数都是一对一（或叫单射函数）。实际上，除了特别简单的应用，在大多数情况下，所构造出的哈希函数是多对一的（非单射函数）。即可能有多个不同的关键字，它们对应的哈希函数值是相同的，这意味着不同记录由哈希函数确定的存储位置是相同的。这种情况被称为冲突。例某年全国各城市人口统计表关键字：城市名哈希函数

H（key）=key的第一个字母在字母表中的序号

key北京天津石家庄保定吉林哈尔滨长春H(key)2201921083具有相同哈希函数值的关键字称为同义词构造哈希表要解决两方面的问题：1）构造哈希函数2）处理冲突9.3.2哈希函数的构造方法“好”的哈希函数的条件：简单：易于计算

均匀：减少冲突若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中，任何一个地址的概率是相等的，则称此类哈希函数为均匀的。常用的构造哈希函数的方法有：1）直接定址法：哈希函数为关键字的某个线性函数H（key)=a*key+b

例1949-2000年某地区人口统计表哈希函数H（KEY）=KEY-1948年份人数

123515219491950195119992000200021002200440044202）数字分析法对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。例如，对如下的关键字序列：430104681015355430101701128352430103720818350430102690605351430105801226356．．．．．．通过对上述关键字序列分析，发现前5位相同，第6、8、10位上的数字变化多些，若规定地址取3位，则散列函数可取它的第6、8、10位。于是有：H（430104681015355）＝480H（430101701128352）＝101H（430103620805351）＝328H（430102690605351）＝296H（430105801226356）＝5023）平方取中法

取关键字平方后的中间几位为散列函数地址。这是一种比较常用的散列函数构造方法，但在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。如图8-16中，随机给出一些关键字，并取平方后的第2到4位为函数地址。

4）折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列函数地址，称为折叠法。例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有5355＋8101＋1046＋430＝14932，舍去高位，则有H（430104681015355）＝4932为该身份证关键字的散列函数地址。5）除留余数法哈希函数为H（key)=keyMODpm为哈希表表长。p为小于等于m的素数除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的p值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。一般情形下，p取为一个素数较理想，并且要求装填因子α最好是在0.6∽0.9之间，所以p最好取1.1n∽1.7n之间的一个素数较好，其中n为散列表中待装元素个数。9.3.3解决冲突的方法：当不同记录由哈希函数确定的存储位置相同，发生冲突。这时需用某种方法解决冲突。常用的解决冲突的方法：1）开放地址法用函数Hi(key)=(H(KEY)+di)mod

m(i=1,2,3…)为发生冲突的记录再求一存储位置。

Hi(key)（i=1,2,3…)是一系列函数，若H1(key)计算出的地址仍冲突，用H2(key)求“下一地址”…,在函数Hi(key)=(H(KEY)+di)mod

m(i=1,2,3…)中：H(KEY)为哈希函数；m为哈希表表长；di为增量序列，有三种取法

a)di=1,2,3…；称为线性探测再散列

b)di=12，-12，22，-2,…,+k2,(k<=m/2)称为二次探测再散列

c)di=伪随机数序列称为伪随机数探测再散列例：设哈希表HT表长为11，哈希函数H(key)=keymod11,试用开放地址法中线性探测再散列解决冲突Hi(key)=(H(KEY)+di)mod11(d1=1,d2=2,d3=3,…),试对下列关键字序列（19，13，33，02，16，29，24）构造哈希表