數(shù)據(jù)結(jié)構(gòu)與算法-補(bǔ)充考研內(nèi)容

11補(bǔ)充考研內(nèi)容內(nèi)容提要11.4.1B樹

11.4.2B+樹12.1多維數(shù)組12.2廣義表和存儲(chǔ)管理補(bǔ)充考研內(nèi)容2/112第11章基本概念11.1線性索引11.2靜態(tài)索引11.3倒排索引11.4動(dòng)態(tài)索引——B/B+樹11.5位索引技術(shù)11.6紅黑樹——以前的錄像補(bǔ)充考研內(nèi)容3/112索引索引(indexing)——(關(guān)鍵碼，指針)指針指向“主文件”中的完整記錄索引文件(indexfile)索引技術(shù)是組織大型數(shù)據(jù)庫(kù)的一種重要技術(shù)高效率的檢索插入、更新、刪除(20,a9)(21,a10)(45,a13)(47,a14)(50,a5)(52,a16)4/112補(bǔ)充考研內(nèi)容線性索引文件按照關(guān)鍵碼的順序進(jìn)行排序文件中的指針指向存儲(chǔ)在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置92733755數(shù)據(jù)庫(kù)記錄線性索引文件5/112補(bǔ)充考研內(nèi)容基本概念動(dòng)態(tài)索引結(jié)構(gòu)索引結(jié)構(gòu)本身也可能發(fā)生改變?cè)谙到y(tǒng)運(yùn)行過(guò)程中插入或刪除記錄時(shí)目的保持較好的性能例如較高的檢索效率6/112補(bǔ)充考研內(nèi)容11.4.1B樹一種平衡的多分樹

(BalancedTree)

3階B樹2-3樹7/112補(bǔ)充考研內(nèi)容B樹隱含指針8/112補(bǔ)充考研內(nèi)容(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)關(guān)鍵碼文件頁(yè)內(nèi)地址主文件9/112補(bǔ)充考研內(nèi)容m階B樹的結(jié)構(gòu)定義(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；(2)除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有個(gè)子結(jié)點(diǎn)；(3)根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn)唯一例外的是根結(jié)點(diǎn)就是葉結(jié)點(diǎn)時(shí)沒有子結(jié)點(diǎn)此時(shí)B樹只包含一個(gè)結(jié)點(diǎn)(4)所有的葉結(jié)點(diǎn)在同一層；(5)有k個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個(gè)關(guān)鍵碼。

10/112補(bǔ)充考研內(nèi)容B樹的性質(zhì)(1)樹高平衡，所有葉結(jié)點(diǎn)都在同一層；(2)關(guān)鍵碼沒有重復(fù)，父結(jié)點(diǎn)中的關(guān)鍵碼是其子結(jié)點(diǎn)的分界；(3)B樹把（值接近）相關(guān)記錄放在同一個(gè)磁盤頁(yè)中，從而利用了訪問局部性原理；(4)B樹保證樹中至少有一定比例的結(jié)點(diǎn)是滿的這樣能夠改進(jìn)空間的利用率減少檢索和更新操作的磁盤讀取數(shù)目11/112補(bǔ)充考研內(nèi)容B樹的結(jié)點(diǎn)結(jié)構(gòu)B樹的一個(gè)包含j個(gè)關(guān)鍵碼，j+1個(gè)指針的結(jié)點(diǎn)的一般形式為：其中Ki是關(guān)鍵碼值，K1<K2<…<Kj，Pi是指向包括Ki到Ki+1之間的關(guān)鍵碼的子樹的指針。還有指針嗎？12/112補(bǔ)充考研內(nèi)容2-3樹=3階B樹1833122330481015202124314547505213/112補(bǔ)充考研內(nèi)容B樹的查找交替的兩步過(guò)程1.把根結(jié)點(diǎn)讀出來(lái)，在根結(jié)點(diǎn)所包含的關(guān)鍵碼K1，…，Kj中查找給定的關(guān)鍵碼值找到則檢索成功2.否則，確定要查的關(guān)鍵碼值是在某個(gè)Ki和Ki+1之間，于是取pi所指向的結(jié)點(diǎn)繼續(xù)查找如果pi指向外部空結(jié)點(diǎn)，表示檢索失敗

14/112補(bǔ)充考研內(nèi)容B樹檢索長(zhǎng)度設(shè)B樹的高度為h獨(dú)根樹高為1在自頂向下檢索到葉結(jié)點(diǎn)的過(guò)程中可能需要進(jìn)行h次讀盤

15/112補(bǔ)充考研內(nèi)容B樹插入注意保持性質(zhì)，特別是等高和階的限制

1)找到最底層，插入

2)若溢出，則結(jié)點(diǎn)分裂，中間關(guān)鍵碼連同新指針插入父結(jié)點(diǎn)

3)若父結(jié)點(diǎn)也溢出，則繼續(xù)分裂分裂過(guò)程可能傳達(dá)到根結(jié)點(diǎn)(則樹升高一層)16/112補(bǔ)充考研內(nèi)容B樹的插入外部空結(jié)點(diǎn)（即失敗檢索）處在第I層的B樹，插入的關(guān)鍵碼總是在第I-1層插入143階B樹18331223304810

2021243145475052151417/112補(bǔ)充考研內(nèi)容m=3，插入5518331223304810152021243145475052插入5550525518/112補(bǔ)充考研內(nèi)容

m=3，葉結(jié)點(diǎn)分裂，把52提升到父結(jié)點(diǎn)結(jié)點(diǎn)分裂183312233048101520212431454750525552505519/112補(bǔ)充考研內(nèi)容插入引起3階B樹根結(jié)點(diǎn)分裂的例子插入19183312233048101520212431454750521919202120/112補(bǔ)充考研內(nèi)容

m=3葉結(jié)點(diǎn)分裂1833122330481015243145475052192021192123302021/112補(bǔ)充考研內(nèi)容

m=3第二層結(jié)點(diǎn)分裂192118331248101524314547505220233030

2018332322/112補(bǔ)充考研內(nèi)容

m=3根結(jié)點(diǎn)分裂3019211248101524314547505220

23

183323/112補(bǔ)充考研內(nèi)容訪外次數(shù)上述插入關(guān)鍵碼19的過(guò)程有10次對(duì)B樹的訪外操作其中讀盤3次（a、c、g）寫盤7次（g、g’、c、c’、a、a’、t）這里不考慮對(duì)主數(shù)據(jù)文件的訪外操作，也不考慮申請(qǐng)新磁盤塊的開銷24/112補(bǔ)充考研內(nèi)容B樹操作的訪外次數(shù)假設(shè)內(nèi)存工作區(qū)足夠大，使得在向下檢索時(shí)讀入的結(jié)點(diǎn)在插入后向上分裂時(shí)不必再?gòu)拇疟P讀入讀盤次數(shù)與查找相同最少寫盤次數(shù)：一次不分裂，寫出這個(gè)關(guān)鍵碼所插入到的結(jié)點(diǎn)25/112補(bǔ)充考研內(nèi)容一次插入操作最多讀寫次數(shù)總共h層，每層都需要分裂（包括根）分裂一個(gè)非根結(jié)點(diǎn)要向磁盤寫出2個(gè)結(jié)點(diǎn)，分裂根結(jié)點(diǎn)（最后一次）要寫出3個(gè)結(jié)點(diǎn)

=找插入結(jié)點(diǎn)向下讀盤次數(shù)++分裂非根結(jié)點(diǎn)時(shí)寫盤次數(shù)++分裂根結(jié)點(diǎn)時(shí)寫盤次數(shù)

=h+2(h-1)+3=3h+126/112補(bǔ)充考研內(nèi)容B樹的刪除刪除的關(guān)鍵碼不在葉結(jié)點(diǎn)層先把此關(guān)鍵碼與它在B樹里的后繼對(duì)換位置，然后再刪除該關(guān)鍵碼

27/112補(bǔ)充考研內(nèi)容B樹的刪除(續(xù))刪除的關(guān)鍵碼在葉結(jié)點(diǎn)層刪除后關(guān)鍵碼個(gè)數(shù)不小于直接刪除關(guān)鍵碼個(gè)數(shù)小于如果兄弟結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)不等于從兄弟結(jié)點(diǎn)移若干個(gè)關(guān)鍵碼到該結(jié)點(diǎn)中來(lái)(父結(jié)點(diǎn)中的一個(gè)關(guān)鍵碼要做相應(yīng)變化)如果兄弟結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)等于合并28/112補(bǔ)充考研內(nèi)容120150

2550

103

5階B樹刪除示例acedfghbi1115

3543

8195100

108110115118134146

156177

29/112補(bǔ)充考研內(nèi)容

刪除120，先與后繼交換，刪后下溢出，向左鄰借關(guān)鍵碼

150

2550

103

acedfghbi1115

3543

8195100

108110115

146

156177

120

134

與后繼交換刪除120,h溢出向左鄰借關(guān)鍵碼118146

146

134

30/112補(bǔ)充考研內(nèi)容1182550

103

cedfghbi1115

3543

8195100

108110115

134146

177

156150繼續(xù)刪除150與后繼交換刪除150,i溢出向左鄰借關(guān)鍵碼借不到，h,i合并177

134146

a31/112補(bǔ)充考研內(nèi)容1182550

103

cedfgh’b1115

3543

8195100

108110115

134146156177h,i合并成為h’c溢出，向左鄰借關(guān)鍵碼借不到，b,c結(jié)點(diǎn)合并1182550

a2550103118

a’32/112補(bǔ)充考研內(nèi)容11.4.2B+樹是B樹的一種變形在葉結(jié)點(diǎn)上存儲(chǔ)信息的樹所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點(diǎn)上

各層結(jié)點(diǎn)中的關(guān)鍵碼均是下一層相應(yīng)結(jié)點(diǎn)中最大關(guān)鍵碼（或最小關(guān)鍵碼）的復(fù)寫

33/112補(bǔ)充考研內(nèi)容B+樹的結(jié)構(gòu)定義m階B+樹的結(jié)構(gòu)定義如下：(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；(2)每個(gè)結(jié)點(diǎn)(除根外)至少有個(gè)子結(jié)點(diǎn)；(3)根至少有兩個(gè)子結(jié)點(diǎn)；(4)所有的葉結(jié)點(diǎn)在同一層；(5)有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必有k個(gè)關(guān)鍵碼。其實(shí)，根可以為空，或者獨(dú)根34/112補(bǔ)充考研內(nèi)容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ǔ)充考研內(nèi)容B+樹的查找查找應(yīng)該到葉結(jié)點(diǎn)層在上層已找到待查的關(guān)鍵碼，并不停止而是繼續(xù)沿指針向下一直查到葉結(jié)點(diǎn)層的這個(gè)關(guān)鍵碼B+樹的葉結(jié)點(diǎn)一般鏈接起來(lái)，形成一個(gè)雙鏈表

適合順序檢索（范圍檢索）實(shí)際應(yīng)用更廣需要的話，每一層結(jié)點(diǎn)也可以順序鏈接36/112補(bǔ)充考研內(nèi)容B+樹的插入插入——分裂過(guò)程和B樹類似注意保證上一層結(jié)點(diǎn)中有這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵碼（或最小關(guān)鍵碼）37/112補(bǔ)充考研內(nèi)容3階B+樹abefghkldijc506070407090809075808590657055604548503540253015510201020304038/112補(bǔ)充考研內(nèi)容40在上圖3階B+樹中插入15后，樹增高一層a’befghkldijc50607080907580859065705560454850354025305101520102030402070904090ta39/112補(bǔ)充考研內(nèi)容B+樹的刪除當(dāng)關(guān)鍵碼不滿時(shí)，與左右兄弟進(jìn)行調(diào)整、合并的處理和B樹類似關(guān)鍵碼在葉結(jié)點(diǎn)層刪除后，其在上層的復(fù)本可以保留，做為一個(gè)“分界關(guān)鍵碼”存在也可以替換為新的最大關(guān)鍵碼（或最小關(guān)鍵碼）40/112補(bǔ)充考研內(nèi)容準(zhǔn)備在3階B+樹中刪除7541/112補(bǔ)充考研內(nèi)容沿a、d、k查找，找到葉結(jié)點(diǎn)在k中刪去75，發(fā)生下溢出，剩余關(guān)鍵碼80與右鄰l結(jié)點(diǎn)合并為新k’（80，85，90）父結(jié)點(diǎn)d中原分界碼80刪除d結(jié)點(diǎn)下溢出借左鄰c的關(guān)鍵碼，c和d的關(guān)鍵碼平分父結(jié)點(diǎn)a中的分界碼70修改為60

42/112補(bǔ)充考研內(nèi)容另一種B+樹葉結(jié)點(diǎn)中關(guān)鍵碼數(shù)目與非葉的不同內(nèi)部非葉結(jié)點(diǎn)構(gòu)成B樹葉的階與B+樹一致例如，葉結(jié)點(diǎn)階5，內(nèi)部階443/112補(bǔ)充考研內(nèi)容補(bǔ)充：VSAMVSAM(VirtualStorageAccessMethod)—虛擬存儲(chǔ)存取方法B+樹的應(yīng)用一種索引順序文件的組織方式與存儲(chǔ)設(shè)備無(wú)關(guān)，存儲(chǔ)單位是“邏輯”的44/112補(bǔ)充考研內(nèi)容45/112補(bǔ)充考研內(nèi)容11.4.1B樹

11.4.2B+樹12.1多維數(shù)組12.2廣義表和存儲(chǔ)管理補(bǔ)充考研內(nèi)容46/112基本概念數(shù)組（Array）是數(shù)量和元素類型固定的有序序列靜態(tài)數(shù)組必須在定義它的時(shí)候指定其大小和類型動(dòng)態(tài)數(shù)組可以在程序運(yùn)行才分配內(nèi)存空間47/112補(bǔ)充考研內(nèi)容基本概念（續(xù)）多維數(shù)組（Multi-array）是向量的擴(kuò)充向量的向量就組成了多維數(shù)組可以表示為：

ELEMA[c1..d1][c2..d2]…[cn..dn]ci和di是各維下標(biāo)的下界和上界。所以其元素個(gè)數(shù)為：

48/112補(bǔ)充考研內(nèi)容數(shù)組的空間結(jié)構(gòu)二維數(shù)組三維數(shù)組d1[1..3],d2[1..5],d3[1..5]分別為3個(gè)維49/112補(bǔ)充考研內(nèi)容數(shù)組的存儲(chǔ)內(nèi)存是一維的，所以數(shù)組的存儲(chǔ)也只能是一維的

以行為主序（也稱為“行優(yōu)先”）以列為主序（也稱為“列優(yōu)先”）50/112補(bǔ)充考研內(nèi)容Pascal的行優(yōu)先存儲(chǔ)

a11a12a13a14a15…a1nam1am2am3am4am5…amna21a22a23a24a25…a2na31a32a33a34a35…a3na41a42a43a44a45…a4n…………………51/112補(bǔ)充考研內(nèi)容FORTRAN的列優(yōu)先存儲(chǔ)

am2am3am4am5…amn…a2na32a33a34a35…a3na42a43a44a45…a4nam1a31a41…………………a12a13a14a15…a1na11a22a23a24a25a21next52/112補(bǔ)充考研內(nèi)容C/C++、Pascal行優(yōu)先先排最右的下標(biāo)從右向左最后最左的下標(biāo)例如對(duì)于三維數(shù)組a[1..k,1..m,1..n]的元素axyz可以如下排列：53/112補(bǔ)充考研內(nèi)容Pascal語(yǔ)言的行優(yōu)先存儲(chǔ)

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補(bǔ)充考研內(nèi)容FORTRAN列優(yōu)先先排最左的下標(biāo)從左向右最后最右的下標(biāo)例如對(duì)于三維數(shù)組a[1..k,1..m,1..n]的元素axyz可以如下排列：55/112補(bǔ)充考研內(nèi)容FORTRAN的列優(yōu)先存儲(chǔ)

a111a211a311

…ak11a121a221a321

…ak21

…………

a1m1a2m1a3m1

…akm1

a112a212a312

…ak12

a122a222a322

…ak22

…………

a1m2a2m2a3m2

…akm2

┇

a11na21na31n

…ak1n

a12na22na32n

…ak2n

…………

a1mna2mna3mn

…akmn

1

2

3

k

12m

56/112補(bǔ)充考研內(nèi)容

C++多維數(shù)組ELEMA[d1][d2]…[dn];57/112補(bǔ)充考研內(nèi)容用數(shù)組表示特殊矩陣三角矩陣：上三角、下三角對(duì)稱矩陣對(duì)角矩陣稀疏矩陣58/112補(bǔ)充考研內(nèi)容下三角矩陣圖例一維數(shù)組list[0..(n2+n)/2-1]矩陣元素ai,j與線性表相應(yīng)元素的對(duì)應(yīng)位置為

list[(i2+i)/2+j]（i>=j）59/112補(bǔ)充考研內(nèi)容對(duì)稱矩陣元素滿足性質(zhì)ai,j=aj,i，0<=（i,j）<n例如無(wú)向圖的相鄰矩陣存儲(chǔ)其下三角的值，對(duì)稱關(guān)系映射

存儲(chǔ)于一維數(shù)組sa[0..n(n+1)/2-1]

sa[k]和矩陣元ai,j之間存在著一一對(duì)應(yīng)的關(guān)系：60/112補(bǔ)充考研內(nèi)容對(duì)角矩陣對(duì)角矩陣是指所有的非零元素都集中在主對(duì)角線及以它為中心的其他對(duì)角線上。如果

|i-j|>1，那么數(shù)組元素a[i][j]=0。下面是一個(gè)3對(duì)角矩陣：a0,0a1,1a0,1a1,0an-1,n-2an-1,n-1an-2,n-1a1,200………………61/112補(bǔ)充考研內(nèi)容稀疏矩陣非零元素非常少，且分布不規(guī)律的矩陣62/112補(bǔ)充考研內(nèi)容稀疏因子在m×n的矩陣中，有t個(gè)非零元素，則稀疏因子為:當(dāng)這個(gè)值小于0.05時(shí)，可以認(rèn)為是稀疏矩陣三元組(i,j,aij)：輸入/輸出常用i是該元素的行號(hào)j是該元素的列號(hào)aij是該元素的值63/112補(bǔ)充考研內(nèi)容稀疏矩陣的十字鏈表十字鏈表有兩組鏈表組成行和列的指針序列每個(gè)結(jié)點(diǎn)都包含兩個(gè)指針：同一行的后繼，同一列的后繼030056200

013

115

202

列鏈表頭指針

行

鏈表頭指針

126

∧

∧

∧

∧

∧

∧

64/112補(bǔ)充考研內(nèi)容經(jīng)典矩陣乘法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補(bǔ)充考研內(nèi)容p=d1-c1+1，m=d3-c3+1，n=d2-c2+1；A為p×m的矩陣，B為m×n的矩陣，乘得的結(jié)果C為p×n的矩陣經(jīng)典矩陣乘法所需要的時(shí)間代價(jià)為O(p×m×n)66/112補(bǔ)充考研內(nèi)容稀疏矩陣乘法

=012

101

02-2

214

∧∧∧∧∧06-1004é?êù?ú6列鏈表頭指針

行

鏈表頭指針

003

035

∧∧11-1

022

∧∧∧∧-14finish67/112補(bǔ)充考研內(nèi)容稀疏矩陣乘法時(shí)間代價(jià)A為p×m的矩陣，B為m×n的矩陣，乘得的結(jié)果C為p×n的矩陣若矩陣A中行向量的非零元素個(gè)數(shù)最多為ta矩陣B中列向量的非零元素個(gè)數(shù)最多為tb總執(zhí)行時(shí)間降低為O((ta+tb)×p×n)經(jīng)典矩陣乘法所需要的時(shí)間代價(jià)為O(p×m×n)68/112補(bǔ)充考研內(nèi)容稀疏矩陣的應(yīng)用一元多項(xiàng)式69/112補(bǔ)充考研內(nèi)容12.2廣義表和存儲(chǔ)管理廣義表儲(chǔ)存管理70/112補(bǔ)充考研內(nèi)容12.2.1廣義表基本概念廣義表的各種類型廣義表的存儲(chǔ)廣義表的周游算法71/112補(bǔ)充考研內(nèi)容基本概念

回顧線性表由n（n≥0）個(gè)數(shù)據(jù)元素組成的有限有序序列線性表的每個(gè)元素都具有相同的數(shù)據(jù)類型如果一個(gè)線性表中還包括一個(gè)或者多個(gè)子表，那就稱之為廣義表（GeneralizedLists，也稱Multi-list）一般記作：L＝（x0，x1，…，xi，…，xn-1）72/112補(bǔ)充考研內(nèi)容L＝（x0，x1，…，xi，…，xn-1）L是廣義表的名稱n為長(zhǎng)度每個(gè)xi（0≤i≤n-1）是L的成員可以是單個(gè)元素，即原子（atom)也可以是一個(gè)廣義表，即子表（sublist）廣義表的深度：表中元素都化解為原子后的括號(hào)層數(shù)73/112補(bǔ)充考研內(nèi)容L＝（x0，x1，…，xi，…，xn-1）表頭head=x0表尾tail=（x1，…，xn-1）規(guī)模更小的表有利于存儲(chǔ)和實(shí)現(xiàn)74/112補(bǔ)充考研內(nèi)容

廣義表的各種類型純表（purelist）

從根結(jié)點(diǎn)到任何葉結(jié)點(diǎn)只有一條路徑也就是說(shuō)任何一個(gè)元素（原子、子表）只能在廣義表中出現(xiàn)一次

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

a1

a2

y3z1z2

x3

75/112補(bǔ)充考研內(nèi)容廣義表的各種類型（續(xù)）可重入表其元素(包括原子和子表)可能會(huì)在表中多次出現(xiàn)如果沒有回路圖示對(duì)應(yīng)于一個(gè)DAG對(duì)子表和原子標(biāo)號(hào)(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

特例：循環(huán)表（即遞歸表）76/112補(bǔ)充考研內(nèi)容廣義表的各種類型（續(xù)）循環(huán)表包含回路

循環(huán)表的深度為無(wú)窮大

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

L2

L3

abcL4

d

77/112補(bǔ)充考研內(nèi)容78/112補(bǔ)充考研內(nèi)容圖

再入表

純表(樹)

線性表

廣義表是線性與樹形結(jié)構(gòu)的推廣遞歸表是有回路的再入表廣義表應(yīng)用函數(shù)的調(diào)用關(guān)系內(nèi)存空間的引用關(guān)系LISP語(yǔ)言79/112補(bǔ)充考研內(nèi)容廣義表存儲(chǔ)ADTtypedefenum{ATOM,LIST}TAG;//ATOM=0：?jiǎn)卧?；LIST=1：子表typedefstructGLNode{

TAGtag;

union{

ElemTypedata; GLNode*sublist;//子表的頭指針

};

GLNode*next;//后繼結(jié)點(diǎn)

};80/112補(bǔ)充考研內(nèi)容廣義表存儲(chǔ)ADT（續(xù)）不帶頭結(jié)點(diǎn)的廣義表鏈在刪除結(jié)點(diǎn)的時(shí)候會(huì)出現(xiàn)問題

刪除結(jié)點(diǎn)data就必須進(jìn)行鏈調(diào)整

1

1

1∧

data

0

head

D1

0∧

D2

0∧

finishdata81/112補(bǔ)充考研內(nèi)容增加頭指針，簡(jiǎn)化刪除、插入操作重入表，尤其是循環(huán)表mark標(biāo)志位——圖的因素

-1

1

-1

1∧

data

0

head(ref=0)

D1

0∧

head(ref=1)

1

-1

head(ref=2)

D2

0

∧

廣義表存儲(chǔ)ADT（續(xù)）82/112補(bǔ)充考研內(nèi)容帶表頭結(jié)點(diǎn)的循環(huán)廣義表83/112補(bǔ)充考研內(nèi)容(L1:(L2:(a)),L184/112補(bǔ)充考研內(nèi)容finish(L1:(L2:(a,L1))Lx:L3,L2,:(b)),Ly:(L3,c),L4:(d,))L4(next85/112補(bǔ)充考研內(nèi)容12.2.2存儲(chǔ)管理技術(shù)內(nèi)存管理存在的問題可利用空間表存儲(chǔ)的動(dòng)態(tài)分配和回收伙伴系統(tǒng)失敗處理策略和無(wú)用單元回收86/112補(bǔ)充考研內(nèi)容動(dòng)態(tài)內(nèi)存分配new和delete內(nèi)存管理技術(shù)鏈表、廣義表87/112補(bǔ)充考研內(nèi)容分配與回收

內(nèi)存管理最基本的問題分配存儲(chǔ)空間回收被“釋放”的存儲(chǔ)空間碎片問題存儲(chǔ)的壓縮

無(wú)用單元收集無(wú)用單元：可以回收而沒有回收的空間

內(nèi)存泄漏(memoryleak)

程序員忘記delete已經(jīng)不再使用的指針88/112補(bǔ)充考研內(nèi)容虛擬存儲(chǔ)：內(nèi)存溢出的管理溢出發(fā)生后，把內(nèi)存中某些數(shù)據(jù)暫存到外存選擇最近不使用的那些結(jié)點(diǎn)0-4k4k-8k8k-12k12k-16k16k-20k0-4k4k-8k8k-12k12k-16k16k-20k20k-24k24k-28k28k-32k32k-36k36k-40k虛擬地址空間物理內(nèi)存地址1304289/112補(bǔ)充考研內(nèi)容可利用空間表把存儲(chǔ)器看成一組變長(zhǎng)塊數(shù)組一些塊是已分配的鏈接空閑塊，形成可利用空間表(freelist)存儲(chǔ)分配和回收newp從可利用空間分配deletep把p指向的數(shù)據(jù)塊返回可利用空間表空間不夠，則求助于失敗策略

90/112補(bǔ)充考研內(nèi)容91/112補(bǔ)充考研內(nèi)容可利用空間表的函數(shù)重載

template<classElem>classLinkNode{ private: staticLinkNode*avail; //可利用空間表頭指針

public: Elemvalue; //結(jié)點(diǎn)值

LinkNode*next; //指向下一結(jié)點(diǎn)的指針

LinkNode(constElem&val,LinkNode*p); LinkNode(LinkNode*p=NULL); //構(gòu)造函數(shù)

void*operatornew(size_t); //重載new運(yùn)算符

voidoperatordelete(void*p);//重載delete運(yùn)算符};92/112補(bǔ)充考研內(nèi)容//重載new運(yùn)算符實(shí)現(xiàn)template<classElem>void*LinkNode<Elem>::operatornew(size_t){ if(avail==NULL) //可利用空間表為空

return::newLinkNode; //利用系統(tǒng)的new分配空間

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

avail=avail->next; returntemp;}93/112補(bǔ)充考研內(nèi)容//重載delete運(yùn)算符實(shí)現(xiàn)template<classElem>voidLinkNode<Elem>::operatordelete(void*p){ ((LinkNode<Elem>*)p)->next=avail; avail=(LinkNode<Elem>*)p;}94/112補(bǔ)充考研內(nèi)容可利用空間表：?jiǎn)捂湵項(xiàng)ew即棧的刪除操作delete即棧的插入操作直接引用系統(tǒng)的new和delete操作符，需要強(qiáng)制用“::n