数据结构与算法-补充考研内容

11补充考研内容内容提要11.4.1B树

11.4.2B+树12.1多维数组12.2广义表和存储管理补充考研内容2/112第11章基本概念11.1线性索引11.2静态索引11.3倒排索引11.4动态索引——B/B+树11.5位索引技术11.6红黑树——以前的录像补充考研内容3/112索引索引(indexing)——(关键码，指针)指针指向“主文件”中的完整记录索引文件(indexfile)索引技术是组织大型数据库的一种重要技术高效率的检索插入、更新、删除(20,a9)(21,a10)(45,a13)(47,a14)(50,a5)(52,a16)4/112补充考研内容线性索引文件按照关键码的顺序进行排序文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置92733755数据库记录线性索引文件5/112补充考研内容基本概念动态索引结构索引结构本身也可能发生改变在系统运行过程中插入或删除记录时目的保持较好的性能例如较高的检索效率6/112补充考研内容11.4.1B树一种平衡的多分树

(BalancedTree)

3阶B树2-3树7/112补充考研内容B树隐含指针8/112补充考研内容(18,a1)(33,a2)(10,a7)(15,a8)(20,a9)(21,a10)(24,a11)(31,a12)(45,a13)(47,a14)(50,a5)(52,a16)(12,a3)(23,a4)(30,a5)(48,a6)关键码文件页内地址主文件9/112补充考研内容m阶B树的结构定义(1)每个结点至多有m个子结点；(2)除根结点和叶结点外，其它每个结点至少有个子结点；(3)根结点至少有两个子结点唯一例外的是根结点就是叶结点时没有子结点此时B树只包含一个结点(4)所有的叶结点在同一层；(5)有k个子结点的非根结点恰好包含k-1个关键码。

10/112补充考研内容B树的性质(1)树高平衡，所有叶结点都在同一层；(2)关键码没有重复，父结点中的关键码是其子结点的分界；(3)B树把（值接近）相关记录放在同一个磁盘页中，从而利用了访问局部性原理；(4)B树保证树中至少有一定比例的结点是满的这样能够改进空间的利用率减少检索和更新操作的磁盘读取数目11/112补充考研内容B树的结点结构B树的一个包含j个关键码，j+1个指针的结点的一般形式为：其中Ki是关键码值，K1<K2<…<Kj，Pi是指向包括Ki到Ki+1之间的关键码的子树的指针。还有指针吗？12/112补充考研内容2-3树=3阶B树1833122330481015202124314547505213/112补充考研内容B树的查找交替的两步过程1.把根结点读出来，在根结点所包含的关键码K1，…，Kj中查找给定的关键码值找到则检索成功2.否则，确定要查的关键码值是在某个Ki和Ki+1之间，于是取pi所指向的结点继续查找如果pi指向外部空结点，表示检索失败

14/112补充考研内容B树检索长度设B树的高度为h独根树高为1在自顶向下检索到叶结点的过程中可能需要进行h次读盘

15/112补充考研内容B树插入注意保持性质，特别是等高和阶的限制

1)找到最底层，插入

2)若溢出，则结点分裂，中间关键码连同新指针插入父结点

3)若父结点也溢出，则继续分裂分裂过程可能传达到根结点(则树升高一层)16/112补充考研内容B树的插入外部空结点（即失败检索）处在第I层的B树，插入的关键码总是在第I-1层插入143阶B树18331223304810

2021243145475052151417/112补充考研内容m=3，插入5518331223304810152021243145475052插入5550525518/112补充考研内容

m=3，叶结点分裂，把52提升到父结点结点分裂183312233048101520212431454750525552505519/112补充考研内容插入引起3阶B树根结点分裂的例子插入19183312233048101520212431454750521919202120/112补充考研内容

m=3叶结点分裂1833122330481015243145475052192021192123302021/112补充考研内容

m=3第二层结点分裂192118331248101524314547505220233030

2018332322/112补充考研内容

m=3根结点分裂3019211248101524314547505220

23

183323/112补充考研内容访外次数上述插入关键码19的过程有10次对B树的访外操作其中读盘3次（a、c、g）写盘7次（g、g’、c、c’、a、a’、t）这里不考虑对主数据文件的访外操作，也不考虑申请新磁盘块的开销24/112补充考研内容B树操作的访外次数假设内存工作区足够大，使得在向下检索时读入的结点在插入后向上分裂时不必再从磁盘读入读盘次数与查找相同最少写盘次数：一次不分裂，写出这个关键码所插入到的结点25/112补充考研内容一次插入操作最多读写次数总共h层，每层都需要分裂（包括根）分裂一个非根结点要向磁盘写出2个结点，分裂根结点（最后一次）要写出3个结点

=找插入结点向下读盘次数++分裂非根结点时写盘次数++分裂根结点时写盘次数

=h+2(h-1)+3=3h+126/112补充考研内容B树的删除删除的关键码不在叶结点层先把此关键码与它在B树里的后继对换位置，然后再删除该关键码

27/112补充考研内容B树的删除(续)删除的关键码在叶结点层删除后关键码个数不小于直接删除关键码个数小于如果兄弟结点关键码个数不等于从兄弟结点移若干个关键码到该结点中来(父结点中的一个关键码要做相应变化)如果兄弟结点关键码个数等于合并28/112补充考研内容120150

2550

103

5阶B树删除示例acedfghbi1115

3543

8195100

108110115118134146

156177

29/112补充考研内容

删除120，先与后继交换，删后下溢出，向左邻借关键码

150

2550

103

acedfghbi1115

3543

8195100

108110115

146

156177

120

134

与后继交换删除120,h溢出向左邻借关键码118146

146

134

30/112补充考研内容1182550

103

cedfghbi1115

3543

8195100

108110115

134146

177

156150继续删除150与后继交换删除150,i溢出向左邻借关键码借不到，h,i合并177

134146

a31/112补充考研内容1182550

103

cedfgh’b1115

3543

8195100

108110115

134146156177h,i合并成为h’c溢出，向左邻借关键码借不到，b,c结点合并1182550

a2550103118

a’32/112补充考研内容11.4.2B+树是B树的一种变形在叶结点上存储信息的树所有的关键码均出现在叶结点上

各层结点中的关键码均是下一层相应结点中最大关键码（或最小关键码）的复写

33/112补充考研内容B+树的结构定义m阶B+树的结构定义如下：(1)每个结点至多有m个子结点；(2)每个结点(除根外)至少有个子结点；(3)根至少有两个子结点；(4)所有的叶结点在同一层；(5)有k个子结点的结点必有k个关键码。其实，根可以为空，或者独根34/112补充考研内容2阶B+树的例子

70

95

10

20

35

40

44

51

65

70

85

91

93

95

20

40

51

70

91

95

40

70

95

35/112补充考研内容B+树的查找查找应该到叶结点层在上层已找到待查的关键码，并不停止而是继续沿指针向下一直查到叶结点层的这个关键码B+树的叶结点一般链接起来，形成一个双链表

适合顺序检索（范围检索）实际应用更广需要的话，每一层结点也可以顺序链接36/112补充考研内容B+树的插入插入——分裂过程和B树类似注意保证上一层结点中有这两个结点的最大关键码（或最小关键码）37/112补充考研内容3阶B+树abefghkldijc506070407090809075808590657055604548503540253015510201020304038/112补充考研内容40在上图3阶B+树中插入15后，树增高一层a’befghkldijc50607080907580859065705560454850354025305101520102030402070904090ta39/112补充考研内容B+树的删除当关键码不满时，与左右兄弟进行调整、合并的处理和B树类似关键码在叶结点层删除后，其在上层的复本可以保留，做为一个“分界关键码”存在也可以替换为新的最大关键码（或最小关键码）40/112补充考研内容准备在3阶B+树中删除7541/112补充考研内容沿a、d、k查找，找到叶结点在k中删去75，发生下溢出，剩余关键码80与右邻l结点合并为新k’（80，85，90）父结点d中原分界码80删除d结点下溢出借左邻c的关键码，c和d的关键码平分父结点a中的分界码70修改为60

42/112补充考研内容另一种B+树叶结点中关键码数目与非叶的不同内部非叶结点构成B树叶的阶与B+树一致例如，叶结点阶5，内部阶443/112补充考研内容补充：VSAMVSAM(VirtualStorageAccessMethod)—虚拟存储存取方法B+树的应用一种索引顺序文件的组织方式与存储设备无关，存储单位是“逻辑”的44/112补充考研内容45/112补充考研内容11.4.1B树

11.4.2B+树12.1多维数组12.2广义表和存储管理补充考研内容46/112基本概念数组（Array）是数量和元素类型固定的有序序列静态数组必须在定义它的时候指定其大小和类型动态数组可以在程序运行才分配内存空间47/112补充考研内容基本概念（续）多维数组（Multi-array）是向量的扩充向量的向量就组成了多维数组可以表示为：

ELEMA[c1..d1][c2..d2]…[cn..dn]ci和di是各维下标的下界和上界。所以其元素个数为：

48/112补充考研内容数组的空间结构二维数组三维数组d1[1..3],d2[1..5],d3[1..5]分别为3个维49/112补充考研内容数组的存储内存是一维的，所以数组的存储也只能是一维的

以行为主序（也称为“行优先”）以列为主序（也称为“列优先”）50/112补充考研内容Pascal的行优先存储

a11a12a13a14a15…a1nam1am2am3am4am5…amna21a22a23a24a25…a2na31a32a33a34a35…a3na41a42a43a44a45…a4n…………………51/112补充考研内容FORTRAN的列优先存储

am2am3am4am5…amn…a2na32a33a34a35…a3na42a43a44a45…a4nam1a31a41…………………a12a13a14a15…a1na11a22a23a24a25a21next52/112补充考研内容C/C++、Pascal行优先先排最右的下标从右向左最后最左的下标例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：53/112补充考研内容Pascal语言的行优先存储

a111a112a113

…a11n

a121a122a123

…a12n

…………

a1m1a1m2a1m3

…a1mn

a211a212a213

…a21n

a221a222a223

…a22n

…………

a2m1a2m2a2m3

…a2mn

┇

ak11ak12ak13

…ak1n

ak21ak22ak23

…ak2n

…………

akm1akm2akm3

…akmn12m

2

2

2

2

2

2

2

2

2

2

2

2

54/112补充考研内容FORTRAN列优先先排最左的下标从左向右最后最右的下标例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：55/112补充考研内容FORTRAN的列优先存储

a111a211a311

…ak11a121a221a321

…ak21

…………

a1m1a2m1a3m1

…akm1

a112a212a312

…ak12

a122a222a322

…ak22

…………

a1m2a2m2a3m2

…akm2

┇

a11na21na31n

…ak1n

a12na22na32n

…ak2n

…………

a1mna2mna3mn

…akmn

1

2

3

k

12m

56/112补充考研内容

C++多维数组ELEMA[d1][d2]…[dn];57/112补充考研内容用数组表示特殊矩阵三角矩阵：上三角、下三角对称矩阵对角矩阵稀疏矩阵58/112补充考研内容下三角矩阵图例一维数组list[0..(n2+n)/2-1]矩阵元素ai,j与线性表相应元素的对应位置为

list[(i2+i)/2+j]（i>=j）59/112补充考研内容对称矩阵元素满足性质ai,j=aj,i，0<=（i,j）<n例如无向图的相邻矩阵存储其下三角的值，对称关系映射

存储于一维数组sa[0..n(n+1)/2-1]

sa[k]和矩阵元ai,j之间存在着一一对应的关系：60/112补充考研内容对角矩阵对角矩阵是指所有的非零元素都集中在主对角线及以它为中心的其他对角线上。如果

|i-j|>1，那么数组元素a[i][j]=0。下面是一个3对角矩阵：a0,0a1,1a0,1a1,0an-1,n-2an-1,n-1an-2,n-1a1,200………………61/112补充考研内容稀疏矩阵非零元素非常少，且分布不规律的矩阵62/112补充考研内容稀疏因子在m×n的矩阵中，有t个非零元素，则稀疏因子为:当这个值小于0.05时，可以认为是稀疏矩阵三元组(i,j,aij)：输入/输出常用i是该元素的行号j是该元素的列号aij是该元素的值63/112补充考研内容稀疏矩阵的十字链表十字链表有两组链表组成行和列的指针序列每个结点都包含两个指针：同一行的后继，同一列的后继030056200

013

115

202

列链表头指针

行

链表头指针

126

∧

∧

∧

∧

∧

∧

64/112补充考研内容经典矩阵乘法A[c1..d1][c3..d3]，B[c3..d3][c2..d2],C[c1..d1][c2..d2]。

d3

C＝A×B(Cij＝∑Aik·Bkj)

k=c3

for(i=c1;i<=d1;i++)

for(j=c2;j<=d2;j++){

sum=0;

for(k=c3;k<=d3;k++)

sum=sum+A[i,k]*B[k,j];

C[i，j]=sum;

}65/112补充考研内容p=d1-c1+1，m=d3-c3+1，n=d2-c2+1；A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵经典矩阵乘法所需要的时间代价为O(p×m×n)66/112补充考研内容稀疏矩阵乘法

=012

101

02-2

214

∧∧∧∧∧06-1004éëêùûú6列链表头指针

行

链表头指针

003

035

∧∧11-1

022

∧∧∧∧-14finish67/112补充考研内容稀疏矩阵乘法时间代价A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵若矩阵A中行向量的非零元素个数最多为ta矩阵B中列向量的非零元素个数最多为tb总执行时间降低为O((ta+tb)×p×n)经典矩阵乘法所需要的时间代价为O(p×m×n)68/112补充考研内容稀疏矩阵的应用一元多项式69/112补充考研内容12.2广义表和存储管理广义表储存管理70/112补充考研内容12.2.1广义表基本概念广义表的各种类型广义表的存储广义表的周游算法71/112补充考研内容基本概念

回顾线性表由n（n≥0）个数据元素组成的有限有序序列线性表的每个元素都具有相同的数据类型如果一个线性表中还包括一个或者多个子表，那就称之为广义表（GeneralizedLists，也称Multi-list）一般记作：L＝（x0，x1，…，xi，…，xn-1）72/112补充考研内容L＝（x0，x1，…，xi，…，xn-1）L是广义表的名称n为长度每个xi（0≤i≤n-1）是L的成员可以是单个元素，即原子（atom)也可以是一个广义表，即子表（sublist）广义表的深度：表中元素都化解为原子后的括号层数73/112补充考研内容L＝（x0，x1，…，xi，…，xn-1）表头head=x0表尾tail=（x1，…，xn-1）规模更小的表有利于存储和实现74/112补充考研内容

广义表的各种类型纯表（purelist）

从根结点到任何叶结点只有一条路径也就是说任何一个元素（原子、子表）只能在广义表中出现一次

(x1,(y1,(a1,a2),y3),x3,(z1,z2))x1y1

a1

a2

y3z1z2

x3

75/112补充考研内容广义表的各种类型（续）可重入表其元素(包括原子和子表)可能会在表中多次出现如果没有回路图示对应于一个DAG对子表和原子标号(L1:(a,b),(L1,c,L2:(d)),(L2,e,L3:(f,g)),L3)

(((a,b)),((a,b),c,d),(d,e,f,g),(f,g))

L1

L2

L3

a

b

d

e

f

g

c

特例：循环表（即递归表）76/112补充考研内容广义表的各种类型（续）循环表包含回路

循环表的深度为无穷大

(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),L4:(d,L4))L1

L2

L3

abcL4

d

77/112补充考研内容78/112补充考研内容图

再入表

纯表(树)

线性表

广义表是线性与树形结构的推广递归表是有回路的再入表广义表应用函数的调用关系内存空间的引用关系LISP语言79/112补充考研内容广义表存储ADTtypedefenum{ATOM,LIST}TAG;//ATOM=0：单元素；LIST=1：子表typedefstructGLNode{

TAGtag;

union{

ElemTypedata; GLNode*sublist;//子表的头指针

};

GLNode*next;//后继结点

};80/112补充考研内容广义表存储ADT（续）不带头结点的广义表链在删除结点的时候会出现问题

删除结点data就必须进行链调整

1

1

1∧

data

0

head

D1

0∧

D2

0∧

finishdata81/112补充考研内容增加头指针，简化删除、插入操作重入表，尤其是循环表mark标志位——图的因素

-1

1

-1

1∧

data

0

head(ref=0)

D1

0∧

head(ref=1)

1

-1

head(ref=2)

D2

0

∧

广义表存储ADT（续）82/112补充考研内容带表头结点的循环广义表83/112补充考研内容(L1:(L2:(a)),L184/112补充考研内容finish(L1:(L2:(a,L1))Lx:L3,L2,:(b)),Ly:(L3,c),L4:(d,))L4(next85/112补充考研内容12.2.2存储管理技术内存管理存在的问题可利用空间表存储的动态分配和回收伙伴系统失败处理策略和无用单元回收86/112补充考研内容动态内存分配new和delete内存管理技术链表、广义表87/112补充考研内容分配与回收

内存管理最基本的问题分配存储空间回收被“释放”的存储空间碎片问题存储的压缩

无用单元收集无用单元：可以回收而没有回收的空间

内存泄漏(memoryleak)

程序员忘记delete已经不再使用的指针88/112补充考研内容虚拟存储：内存溢出的管理溢出发生后，把内存中某些数据暂存到外存选择最近不使用的那些结点0-4k4k-8k8k-12k12k-16k16k-20k0-4k4k-8k8k-12k12k-16k16k-20k20k-24k24k-28k28k-32k32k-36k36k-40k虚拟地址空间物理内存地址1304289/112补充考研内容可利用空间表把存储器看成一组变长块数组一些块是已分配的链接空闲块，形成可利用空间表(freelist)存储分配和回收newp从可利用空间分配deletep把p指向的数据块返回可利用空间表空间不够，则求助于失败策略

90/112补充考研内容91/112补充考研内容可利用空间表的函数重载

template<classElem>classLinkNode{ private: staticLinkNode*avail; //可利用空间表头指针

public: Elemvalue; //结点值

LinkNode*next; //指向下一结点的指针

LinkNode(constElem&val,LinkNode*p); LinkNode(LinkNode*p=NULL); //构造函数

void*operatornew(size_t); //重载new运算符

voidoperatordelete(void*p);//重载delete运算符};92/112补充考研内容//重载new运算符实现template<classElem>void*LinkNode<Elem>::operatornew(size_t){ if(avail==NULL) //可利用空间表为空

return::newLinkNode; //利用系统的new分配空间

LinkNode<Elem>*temp=avail;//从可利用空间表中分配

avail=avail->next; returntemp;}93/112补充考研内容//重载delete运算符实现template<classElem>voidLinkNode<Elem>::operatordelete(void*p){ ((LinkNode<Elem>*)p)->next=avail; avail=(LinkNode<Elem>*)p;}94/112补充考研内容可利用空间表：单链表栈new即栈的删除操作delete即栈的插入操作直接引用系统的new和delete操作符，需要强制用“::n