数据结构实验集-第九章查找

数据结构课程的内容一、教学内容：1、 线性表的查找；2、 树表查找；3、 哈希表查找。二、教学要求：1、熟练掌握顺序表和有序表的查找算法及其性能分析方法；2、熟练掌握二叉排序树的构造和查找算法及其性能分析方法；3、理解AVL树的维护平衡方法；4、 理解B_树、B+的特点、查找及构造方法；5、 熟练掌握哈希函数的构造及解决冲突的方法。第9章查找9.1基本概念9.2静态查找表9.3动态查找表9.4哈希表第9章查找教材第8、11和12章省略，因《操作系统》课程会涉及。9.1基本概念——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录

(预先确定的记录的某种标志)

——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

（3)有哪些查找方法？

查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？

给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。（4）如何评估查找方法的优劣？针对静态查找表的查找算法主要有：

9.2静态查找表静态查找表的抽象数据类型参见教材P216。一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）一、顺序查找（Linearsearch，又称线性查找）（1）顺序表的机内存储结构：typedefstruct{

ElemType*elem;

//表基址，0号单元留空。表容量为全部元素

intlength;

//表长，即表中数据元素个数}SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。

对顺序结构如何线性查找？见下页之例或教材P216；对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！顺序查找演示（2）算法的实现：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(SSTableST,KeyTypekey){

//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0

ST.elem[0].key=key;

//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。

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

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

//若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回i=0。讨论②

查找效率怎样计算？——用平均查找长度ASL衡量。讨论①

查不到怎么办？讨论③如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2

，时间效率为O(n)二、折半查找（又称二分查找或对分查找）优点：算法简单，且对顺序结构或链表结构均适用。缺点：

ASL太长，时间效率太低。这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法？

——见下页之例，或见教材（P219）对单链表结构如何折半查找？

——无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？

——可借助二叉排序树来查找（属动态查找表形式）。

如何改进？讨论④顺序查找的特点：②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].key<key，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low

（意即区间长度小于0）解：①先设定3个辅助标志:

low,high,mid，折半查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置

已知如下11个元素的有序表：

（0513192137566475808892）,请查找关键字为21

和85的数据元素。显然有：mid=(low+high)/2二分查找演示讨论①若关键字不在表中，怎样得知和停止？——典型标志是：当查找范围的上界≤下界时停止查找。讨论②二分查找的效率（ASL）1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处…4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处………则第m次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素＝2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推导过程平均每个数据的查找时间还要除以n，所以：（详细推导过程见教材P221的附录1）课堂练习（多项选择）：Ａ．采用链式存贮结构 Ｂ．记录的长度≤128Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序√√使用折半查找算法时，要求被查文件：思考：假设在有序线性表a[20]上进行折半查找，则平均查找长度为

。查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。

找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。

比较的关键字个数：为该结点在判定树上的层次数。

查找成功时比较的关键字个数最多不超过树的深度d:d=log2n+1

若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。

查找不成功的过程就是走了一条从根结点到外部结点的路径。折半查找效率分析法（参见教材P220）：三、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块224886例：2248861713特点：块间有序，块内无序查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5分块查找演示5.实现程序下面函数以二分法查找块,以顺序法查找分块内的方法,实现了线性表的分块查找。其中参数a为顺序存储的线性表,idx为索引表,v为要查找的给定值,m为总块数。

typedefstruct{intkey;intstart;intlen;}IDX;

intblk_search(a,idx,v,m)IDXidx[];inta[],v,m;{intlow=0,high=m-1,mid,i,h;while(low<=high){mid=(low+high)/2;if(v<idx[mid].key)high=mid-1;elseif(v>idx[mid].keylow=mid+1;

else

{low=mid;break;}}

if(low>=m)return(-1);i=idx[low].start;h=i+idx[low].len;while(i<h&&a[i]!=v)i++;if(a[i]!=v)i=-l;return(i);}

特点：一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树五、B-树和B+树9.2动态查找表表结构在查找过程中动态生成。要求：对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。典型的动态表———二叉排序树一、二叉排序树的定义（a）（b）练：下列2种图形中，哪个不是二叉排序树？----或是一棵空树；或者是具有如下性质的非空二叉树：

（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。讨论：对(a)中序遍历后的结果是什么？二、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：①查找过程与顺序结构有序表中的折半查找相似，查找效率高；②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！——这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。4524531290如果待查找的关键字序列输入顺序为：（24，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回讨论1：二叉排序树的插入和查找操作

则生成二叉排序树的过程为：例：输入待查找的关键字序列=（45，24，53，45，12，24，90）则生成的二叉排序树形态不同：查找成功，返回查找成功，返回二叉排序树的查找&插入算法如何实现？查找算法静态查找算法动态查找算法（插入）二叉排序树的静态查找思想若二叉排序树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。（2）二叉排序树查找的算法实现1)递归函数

NODE*search(t,x)NODE*t;charx;{if(t==NULL)return(NULL);

else

{if(t->data==x)return(t);if(x<(t->data)return(search(t->lchild,x));

else

return(search(t->lchild,x));}}2)非递归函数

NODE*search(NODE*t,charx){NODE*p;

p=t;while(p!=NULL){if(p->data==x)return(p);if(x<p->data)p=p->lchild;else

p=p->rchlid;}printf(“找不到值为%x的结点!”,x);return(NULL);}二叉排序树的动态查找算法查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。（P228算法9.5（b））插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。（P228算法9.6）二叉排序树的建立对于已给定一待排序的数据序列,通常采用逐步插入结点的方法来构造二叉排序树,即只要反复调用二叉排序树的插入算法即可，算法描述为：BiTree*Creat(intn)//建立含有n个结点的二叉排序树{BiTree*BST=NULL;for(inti=1;i<=n;i++){scanf(“%d”,&x);//输入关键字序列

InsertBST(BST,x);}return(BST);}二叉排序树的生成演示二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或f->rchild=NULLp只有左子树或右子树p只有左子树，用p的左孩子代替p(1)(2)p只有右子树，用p的右孩子代替p(3)(4)p左、右子树均非空

沿p左子树的根C的右子树分支找到S，S的右子树为空法1：令*p的左子树为*f的左子树，*p的右子树为*s的右子树；法2：令*s代替*p将S的左子树成为S的双亲Q的右子树，用S取代p(5)若C无右子树，用C取代p(6)FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：请从下面的二叉排序树中删除结点P。SSLSQPLP中序遍历：QSPLPSQPL中序遍历：QSPL(2)SPPLQ中序遍历：PLPSQSPLQ中序遍历：PLSQ(1)63421815634215删除18中序遍历：PPRSQSPRQ中序遍历：PRSQ(3)SPPRQ中序遍历：QSPPRSQPR中序遍历：QSPR(4)SQPRP6342181215删除1263421815FPCPRCLQQLSSL中序遍历：CLC……QLQSLSPPRFFSCPRCLQQLSL中序遍历：CLC……QLQSLSPRF(5)FPCPRCL中序遍历：CLCPPRFFCPRCL中序遍历：CLCPRF(6)1036241812156342181215删除10二叉排序树删除演示1)二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。

比较的关键字次数＝此结点的层次数;

最多的比较次数＝树的深度（或高度），即log2n+12)一棵二叉排序树的平均查找长度为：三、二叉排序树的查找分析其中：ni是每层结点个数；

Ci是结点所在层次数；m为树深。最坏情况：即插入的n个元素从一开始就有序，

——变成单支树的形态！此时树的深度为n;ASL=(n+1)/2

此时查找效率与顺序查找情况相同。最好情况：即：与折半查找中的判定树相同（形态比较均衡）3）对有n个关键字的二叉排序树的平均查找长度:

设每种树态出现概率相同，查找每个关键字也是等概率的。则ASL求解过程可推导。（详见教材P232）树的深度为：log2n+1；ASL=log2(n+1)–1；与折半查找相同。结论：二叉排序树的ASL≤2（1＋1/n）lnn一般情况：（与logn同阶）问题：如何提高二叉排序树的查找效率？

尽量让二叉树的形状均衡平衡二叉树四、平衡二叉树平衡二叉树又称AVL树，它是具有如下性质的二叉树：为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样，可以得到AVL树的其它性质：即|左子树深度-右子树深度|≤1左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤1(a)平衡树(b)不平衡树例：判断下列二叉树是否AVL树？任一结点的平衡因子只能取：-1、0或

1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。00011-1-120001-1如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：

LL平衡旋转

RR平衡旋转

LR平衡旋转

RL平衡旋转若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：这种调整规则可以保证二叉排序树的次序不变013037024例：请将下面序列构成一棵平衡二叉排序树：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053

五、B-树和B+树一、B-树的基本概念

1.定义

一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:(l)所有的非终端结点的结构如下:

其中,①k1,k2,...,kn为n个按从小到大顺序排列的键值;②p0,pl,p2,...,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1≤i≤n-1)所指向子树中的所有关键字的值均大于ki且小于ki+1;③n(n≤m-1)为键值的个数,即子树个数为(n+l)。

(2)树中每个结点至多有m棵子树。

(3)除非根结点为叶子结点,否则至少有两棵子树。

(4)除根之外的所有非终端结点至少有┌m/2┐棵子树。

(5)所有叶子结点在同一个层次上,且不含有任何信息。

np0k1p1k2p2…kipi…knpn2.说明(1)对于非根结点的所有分支结点,n的取值范围为┌m/2┐-1≤n≤m-1。(2)对于根结点,n的取值范围为1≤n≤m－1。(3)对于叶子结点,其子树均为空树(即没有子结点),又规定不含有任何信息:所,可以把它看作不在树中的外部结点。(4)B-树的阶m可以事先任意指定,一旦指定后,就固定不变。

2-3树的含义图9-13是一棵由10个键值生成的四阶B_树的示意图,该树共有四层,所有叶子点均在第四层上。1501301951251552709023540atbcdfgeh图9-13B-树3758085二、B-树的查找1.查找方法

由B-树的定义可知,在B-树上进行查找的过程与二叉排序树的查找类似。根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。若有k=ki,则查找成功,根据相应的指针即可取得记录:否则,若k在ki和ki+1之间,取指针pi所指的结点,重复这个查找过程,直到在某结点中查找成功,或在某结点处出现pi

为空,查找失败.例如，在图9-13所示B_树中查找关键字80和38。2.性能分析在B-树上进行查找需比较的结点数最多为B-树的高度,B-树的高度与B-树的阶m和键值总数N有关,下面就来讨论它们之间的关系。(1)若B-树的高度为h+1,则h+1层(即叶结点所在的层)的结点数为N+1。因为每个非叶结点中的指针数等于其中的键值数加1,因此有:

结点总数=指针总数+1=(键值总数N+非叶结点数)+l(h+1)层的结点数=叶结点数=结点总数－非叶结点数=N+1。(2)根据B-树的定义,B-树的第一层(即根结点)的结点数至少为1个,第二层的结点数至少为2,第三层的结点数至少为2*┌m/2┐,第四层的结点数至少为2*(┌m/2┐)2,以此类推,第h+1层的结点数至少为2*(┌m/2┐)h-1。(3)综上所述,可得到如下不等式:h≤1+log┌m/2┐(N+1)/2三、B-树的插入

在B-树中插入一个键值k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个键值。且要使插入的结点中的键值字个数≤m－1,将涉及到结点的“分裂"问题。1.插入方法

首先要经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字值个数不超过(m-l),直接把键值插就行了;否则需要把结点分裂成两个。分裂的做法是,取一新结点,把原结点上的键和k按升序排序后,从中间位置(即┌m/2┐之处)把键值(不包括中间位置的键值)成两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父亲结点中。如果父结点的键值个数也超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。306580253540556070758550(a)插入前的3阶B_树30252835406580556070758550(b)插入28后的B_树3038252835658055607075855040(c)插入38后的B_树305065805560707585382520283540(d)插入20后的B_树图9-14B_树的插入B树生成过程演示四、B-树的删除

B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的键值个数≥┌m/2┐,将涉及到结点的“合并"问题。

1.删除方法

在深度为(h+l)的m阶B-树中删除一个键值k,首先要查到键值k所在的结点及在结点中的位置。若k所在结点的层数小于h,则把该结点的右边(或左边)指针所指子树中的最小(或最大)键值与k对调,使k移到第h层,这样可根据k所在结点为第h层结点的情况进行删除,从B_树上第h层结点中删除一个键值后,使得该结点的值个数n减1,此时应分以下三种情况进行处理:(1)若删除后结点中键值数目n≥┌m/2┐－1,在该结点中删去键值k连同右边的指针.

(2)若删除后结点中键值数目n<┌m/2┐－1,且左(或右)兄弟结点的关键字数目＞┌m/2┐－1,则把左(或右)兄弟结点中最大(或最小)键值移到父结点中,再把父结点大于(或小于)上移键值的键值下移到被删关键字所在结点中。(3)若删除后结点中键值数目n<┌m/2┐－1,及其左、右兄弟结点的键值数目都等于┌m/2┐－1,则就必须进行结点的“合并”,即把应删的键值删去后,将该结点中的剩余键值和指针连同父结点中指向该结点指针的左边(或右边)一个键值ki一起合并到左兄弟(或右兄弟)结点中,将ki从父结点中删去。如果因此使父结点中关键字数目<┌m/2┐－1,则对此父结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层。3065802535405560707585503065802540556070758550(a)由图9-14(a)删除35后的3阶B_树30657525405560708050(b)删除85后的B_树306525405560707550(c)删除80后的B_树5065707530405560(d)删除25后的B_树图9-15B_树的删除B-树删除过程演示9.4.2B+树一、B+树定义

1.定义

一棵m阶的B+树满足下列条件:(1)每个分支结点至多有m棵子树。(2)除根结点外,其他每个分支结点至少有└(m+1)/2┘棵子树。(3)根结点至少有两棵子树,至多有m棵子树。(4)有n棵子树的结点有n个键值。(5)所有叶结点包含全部(数据文件中记录)键值及指向相应记录的指针(或存放据文件分块后每块的最大键值及指向该块的指针),而且叶结点按键值大小顺序链接(可以把每个叶结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直指向数据文件中的记录)。(6)所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引索引块)中最大键值及指向子结点的指针.对于m阶的B+树和m阶的B-树,定义中的前三点是相同的,主要的差异是:(1)在B+树中,具有n个关键字的结点则含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n个键值的结点含有(n+1)棵子树;(2)在B+树中,每个结点(除树根结点外)中的键值个数n的取值范围是┌m/2┐≤n≤m,根结点n的取值范围是1≤n≤m;而在B_树中,它们的取值范围分别是┌m/2┐－1≤n≤m－l和l≤n≤m－1。(3)B+树中的所有叶子结点包含了全部键值,即其他非叶结点中的键值包含在叶结点中,而在B-树中,叶结点包含的键值与其他结点包含的键值是不重复的。(4)B+树中所有非叶结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该键值对应记录的存储地址。而在B-树中,每个键值对应一个记录的存储地址。(5)通常在B+树上有两个头指针,一个指向根结点,另一个指向键值最小的叶子结点,所有叶结点链接成一个不定长的线性链表。40653540606555654045552025301530401015roothead图9-16B+树二、B+树查找

在B+树中可以采用两种查找方式,一种是直接从最小键值开始进行顺序查找,另一种就是从B+树的根结点开始进行随机查找。这种查找方式与B-树的查找方法相似,只是在分支结点上的键值与查找值相等时,查找并不结束,要继续查到叶结点为止,此时若查找成功,则按所给指针取出对应记录即可。因此,在B+树中,不管查找成功与否,每次查找都是经过了一条从树根结点到叶子结点的路径。

三、B+树插入

与B-树的插入操作相似,B+树的插入也从叶子结点开始,当插入后结点中的键值个数大于m时要分裂成两个结点,它们所含键值个数分别为┌(m+1)/2┐和└(m+1)/2┘,同时要使得它们的双亲结点中包含有这两个结点的最大键值和指向它们的指针。若双亲结点的键值数目因此而大于m,应继续分裂,依此类推。四、B+树删除

B+树的删除也是从叶子结点开始,当叶结点中最大键值被删除时,分支结点中的值可以作为“分界键值”存在。若因删除操作而使结点中键值个数少于┌m/2┐时,则从兄弟结点中调剂键值或和兄弟结点合并,其过程和B-树相似。9.4哈希查找表一、哈希表的概念二、哈希函数的构造方法三、冲突处理方法四、哈希表的查找及分析

前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记录。哈希表它既是一种查找方法，又是一种存贮方法哈希表：即散列存储结构。

散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！例1：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V[01]单元；将2001011810202的所有信息存入V[02]单元；……将2001011810231的所有信息存入V[31]单元。欲查找学号为2001011810216的信息，便可直接访问V[16]！一、哈希表的概念例2：

有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。（注：H（k）＝k称为散列函数）解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：讨论：如何进行散列查找？根据存储时用到的散列函数H(k)表达式，迅即可查到结果！例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。

地址…9…11…14…232425…39…内点：空间效率低！选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。若干术语哈希方法(杂凑法)哈希函数(杂凑函数)哈希表(杂凑表)

冲突哈希方法中使用的转换函数称为哈希函数(杂凑函数)按上述思想构造的表称为哈希表(杂凑表)

有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！0123456所以，哈希方法必须解决以下两个问题：1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。二、哈希函数的构造方法常用的哈希函数构造方法有：直接定址法除留余数法

乘余取整法数字分析法平方取中法折叠法随机数法要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。Hash(key)=a·key+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：01234567899008007005003001001、直接定址法Hash(key)=B*(A*keymod1)

(A、B均为常数，且0<A<1，B为整数)特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。Hash(key)=keymodp(p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数

（也可以是不包含小于20质因子的合数）。3、乘余取整法2、除留余数法（A*keymod1）就是取A*key的小数部分例：欲以学号最后两位作为地址，则哈希函数应为：

H(k)=100*(0.01*k%1)其实也可以用法2实现：H(k)=k%100特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。34705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键码，其样式如下：4、数字分析法讨论：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②

若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。6、折叠法特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。适用于：每一位上各符号出现概率大致相同的情况。法1：移位法──将各部分的最后一位对齐相加。法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13115、平方取中法7、随机数法Hash(key)=random(key)(random为伪随机函数)适用于：关键字长度不等的情况。造表和查找都很方便。①执行速度（即计算哈希函数所需时间）；②关键字的长度；③哈希表的大小；④关键字的分布情况；⑤查找频率。小结：构造哈希函数的原则：三、冲突处理方法常见的冲突处理方法有：开放定址法（开地址法）链地址法（拉链法）再哈希法（双哈希函数法）建立一个公共溢出区1、开放定址法（开地址法）设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。具体实现：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)为哈希函数

m为哈希表长度

di

为增量序列1，2，…m-1，且di=i1.线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。开放定址法建立散列表演示关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用线性探测法处理冲突。建哈希表如下：解释：①47、7（以及11、16、92）均是由哈希函数得到的没有冲突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8为空，因此将29存入。③

另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。其中3

还连续移动了两次（二次聚集）线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可