【正文】 的分?jǐn)偞鷥r(jià)之和 ， 即 O(n log n + e)。 i n。amp。 dist[v] = 0。 // 選擇 u，使得對(duì)于所有 s[x] = // FALSE， dist[u] = 最小的 dist[x] 9 s[u] = TRUE。 path[w] = u。因此，該循環(huán)的總時(shí)間是 O(n2)。 每次迭代，都需要確定頂點(diǎn) u，使得 u? ，且dist[u] = 。 S]}[{m in xd istSx?SSJYP 37 初始時(shí) ， 含 n – 1個(gè)頂點(diǎn) 。 因此 ， 算法的時(shí)間復(fù)雜性是 O(n log n + e)。 將記錄 R0和 Rfirst交換 。 于是可將 R0的 link字段設(shè)置為 first， 表示原位于 R0的記錄已移到 Rfirst。 一般地 ， 設(shè)記錄表 R0, … , Ri1已在物理上按序排列 ， Rfirst是剩余記錄 Ri, … , Rn1鏈表的首記錄 ， 記錄Ri和 Rfirst交換后 ， 將新 Ri記錄的 link字段設(shè)置為 first，表示原位于 Ri的記錄已移到 Rfirst。 i++) { // 找到應(yīng)放到位置 i的記錄。 list[i] = list[first]。 } } JYP 42 例 對(duì) (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 進(jìn)行鏈表排序后 ， 所得鏈表如下所示： JYP 43 list的 for循環(huán)每次迭代后記錄表的狀態(tài)如下 ， 變化用粗體字表示 ， 虛擬結(jié)點(diǎn)的 link字段用帶下劃線的字體表示： JYP 44 JYP 45 JYP 46 JYP 47 JYP 48 對(duì) list的分析： 設(shè)有 n個(gè)記錄 ， for循環(huán)迭代 n–1次 。 在 while循環(huán)中 ， 任何結(jié)點(diǎn)最多被檢查一次 ， 所以while循環(huán)的總時(shí)間是 O(n)。 映射表單元起著對(duì)記錄間接尋址的作用 。 JYP 50 JYP 51 有時(shí)為了避免間接尋址，還需要根據(jù)映射表 t確定的置換在物理上重新排列記錄。 函數(shù) table首先沿著包含 R0的環(huán)路將記錄移到其正確位置。 i n – 1。 list[j] = list[k]。 list[j] = p。如果對(duì)于某些 i的取值， t[i] ? i，則存在一個(gè)包含 k 1個(gè)不同記錄 Ri, Rt[i], …, Rtk1[i]的環(huán)路。記錄移動(dòng)的總次數(shù)是 )1(20,0?????nkjjjkJYP 55 當(dāng) = n且存在 ?n/2?個(gè)非平凡環(huán)路時(shí)，記錄移 動(dòng)的總次數(shù)達(dá)到最大值 — ?3n/2?。 JYP 57 二叉樹的例子 : 其中，（ a）不是二叉查找樹，（ b）和（ c）是。 （ 2） (A, B)： 構(gòu)建 C， C由原來在 A和 B中的元素構(gòu)成。最后將 A設(shè)置為空。 JYP 61 2路結(jié)合可通過 3路結(jié)合實(shí)現(xiàn)： 如果 A（ 或 B） 是空樹 ， 則將 （ 或 ） ， 并將 （ 或 ） 設(shè)置為 0即可 。 JYP 62 分裂操作的實(shí)現(xiàn)： 在根結(jié)點(diǎn) （ 即 i == ?） 的分裂很容易 。 JYP 63 JYP 64 一般地 ， 可以在 A中向下查找關(guān)鍵字為 i的元素的過程中構(gòu)造二叉查找樹 B和 C。 若 i == t?， 則應(yīng)將 t的左 、 右子樹分別加入 B、 C中 ， 并將 t?data復(fù)制到 x。B, ElementTypeamp。} // 空樹 BstNodeType *Y = new BstNodeType。 JYP 67 BstNodeType *t = root。 delete t。 delete Z。 } else if (i t?) { L?LeftChild = t。 R = t。 delete Y。 return 0。 B和 C的高度不超過 A的高度 。 JYP 71 圖 （ b） 的擴(kuò)展二叉樹如下所示： JYP 72 n個(gè)結(jié)點(diǎn)的二叉樹有 n + 1個(gè)外部結(jié)點(diǎn)。 圖 I = 0 + 1 + 1 + 2 = 4 其外部路徑長(zhǎng)度 E是 E = 2 + 2 + 2 + 3 + 3 = 12 JYP 73 引理 ： 如果二叉樹 T有 n 個(gè)（ n≥0）內(nèi)部結(jié)點(diǎn)，I是其內(nèi)部路徑長(zhǎng)度， E是其外部路徑長(zhǎng)度，則 E = I + 2n。 考慮一棵有 m + 1個(gè)內(nèi)部結(jié)點(diǎn)的樹，設(shè)該樹的內(nèi)部路徑長(zhǎng)度為 I，外部路徑長(zhǎng)度為 E。 v的每個(gè)子女到根結(jié)點(diǎn)的路徑長(zhǎng)度是 k + 1，所以外部路徑長(zhǎng)度應(yīng)減少 2(k + 1)再加上新外部結(jié)點(diǎn) v到根結(jié)點(diǎn)的路徑長(zhǎng)度 k。 在二叉樹完全偏斜時(shí) I達(dá)到最大值。這樣，最小的 I是 I = ? ???nii12lo gJYP 78 利用數(shù)學(xué)推導(dǎo)可得： = (n + 1)q – 2(q + 1) + 2， 其中， q = ?log2(n + 1)? 因此，在最好情況的二叉查找樹中進(jìn)行成功查找的平均比較次數(shù) Sn為 Sn = = ? log2(n + 1) –1?log2n–1 () ? ???nii12lo g1?nI 122)1( )1( ???? ?nqn q)1( 1n?JYP 79 3 平均情況 Sn — 平均成功查找所需的比較次數(shù) Un — 平均不成功查找所需的比較次數(shù) 在樹中查找到任何關(guān)鍵字所需的比較次數(shù)正好是含該關(guān)鍵字的元素首次插入所需的比較次數(shù)加 1，而插入該元素所需的比較次數(shù)與該元素不在樹中的不成功查找的相同。 JYP 85 最佳二叉查找樹 （ ） 如果一個(gè)符號(hào)表固定，只對(duì)其進(jìn)行查找操作，則稱其為 靜態(tài)符號(hào)表 。 JYP 86 當(dāng)查找各標(biāo)識(shí)符的概率不相同時(shí)，完全二叉樹不一定是最佳的。不在二叉查找樹中的標(biāo)識(shí)符可被劃分為 n+1個(gè)類 Ei，0≤i≤n。 JYP 88 設(shè) qi是所查找的標(biāo)識(shí)符屬于 Ei的概率 ， 則全部失敗結(jié)點(diǎn)的代價(jià)是 該二叉查找樹的總代價(jià)是 () 表示 a1, a2, …, a n的最佳二叉查找樹應(yīng)使 ()式的值最小。 當(dāng) n較大時(shí) ， 這種方法是沒有實(shí)用價(jià)值的 。 由定義 ， cii = 0。 于是， T0n是包含標(biāo)識(shí)符 a1, a2, …, a n的最佳二叉查找樹，其代價(jià)是 c0n，其根結(jié)點(diǎn)標(biāo)識(shí)符的下標(biāo)是 r0n。 要使 cij最小， L的代價(jià)應(yīng)等于 ci,k1， R的代價(jià)應(yīng)等于 ckj，因此 cij = pk+ci,k1+ckj+wi,k1+wkj = wij+ci,k1+ckj () JYP 97 由于 Tij是最佳的，根據(jù) ()式， rij = k應(yīng)滿足 wij + ci,k1 + ckj = 或 ci,k1 + ckj = () 根據(jù) ()和 ()式，并利用動(dòng)態(tài)規(guī)劃方法，可以從 Tii = ?和 cii = 0開始，逐步得到 T0n 和 c0n。重復(fù)此過程，最終可得到 w0 c03和 r03。 T12的根結(jié)點(diǎn)含標(biāo)識(shí)符 a2，其左子樹是 T11，右子樹是 T22。 當(dāng) j – i = m時(shí)，需要計(jì)算 n – m + 1個(gè) cij。 因此，當(dāng) j – i = m時(shí)， 1≤r0,m1≤r1,m≤r2,m+1 ≤ … ≤r nm+1,n≤n，總計(jì)算時(shí)間改進(jìn)為 ≤2n – m + 1 = O(n) )(12????nmmnm)1( 1,0,1 ?? ?????? jimniji rrJYP 104 當(dāng) j – i = m，且 m = 1時(shí)的總計(jì)算時(shí)間為 n – m + 1。最后調(diào)用 build構(gòu)造最佳二叉查找樹。 c[i][i] = 0。 } w[n][n] = q[n]。 m++) // 含 m個(gè)結(jié)點(diǎn)的最佳二叉查找樹 for (i = 0。 int k。 u++) { float t = c[i][u1] + c[u][j]。 // ()式 r[i][j] = k。 int k = r[i][j]。 return p。 B+樹就是這種改進(jìn)的結(jié)果，也是現(xiàn)實(shí)中最常用的一種 B樹變種。 JYP 109 定義： 一棵 m階 B+樹或者為空，或者滿足下列性質(zhì)： （ 1） 中間結(jié)點(diǎn)最多有 m棵子樹，且具有下列結(jié)構(gòu)： n, A0, (K1, A1), (K2, A2), …, (K n, An) 其中， Ai是子樹指針， 0≤i≤n m， Ki是關(guān)鍵字，1≤i≤n m。 （ 5） 根結(jié)點(diǎn)至少有 2棵子樹，其它中間結(jié)點(diǎn)至少有?m/2?棵子樹。 JYP 111 B+樹的葉結(jié)點(diǎn)被鏈接成雙鏈表 ， 以便范圍查詢 。 即使中間結(jié)點(diǎn)中已有需要查找的關(guān)鍵字，但那也只是“路標(biāo)”，并不提供實(shí)際元素的地址。 JYP 113 往 B+樹中 插入 關(guān)鍵字為 x的元素的方法與 B樹的類似。再將結(jié)點(diǎn)q中最小關(guān)鍵字和指針 q插入結(jié)點(diǎn) p的雙親。 首先 ， 定位到關(guān)鍵字 x所在的葉結(jié)點(diǎn) p。 JYP 120 如果刪除后結(jié)點(diǎn) p中只有 ?mleaf/2? – 2個(gè)關(guān)鍵字 ，且其最鄰近兄弟 q至少有 ?mleaf/2?個(gè)關(guān)鍵字 ， 則可從結(jié)點(diǎn) q移一個(gè)到結(jié)點(diǎn) p， 從而使這兩個(gè)結(jié)點(diǎn)都滿足要求 。 這又可能導(dǎo)致雙親結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)不足 ， 引起新一輪的旋轉(zhuǎn)與合并 ， 直至刪除根結(jié)點(diǎn) 。 如果分配的表空間過大，則會(huì)浪費(fèi)空間；如果分配的表空間過小，則會(huì)導(dǎo)致沖突頻繁，而且當(dāng)數(shù)據(jù)量大于散列表的容量時(shí)整個(gè)散列表需要重組。記錄存儲(chǔ)在 頁(yè)面 （或桶）中，每個(gè)頁(yè)面的容量是 p個(gè)記錄。 給定一個(gè)散列表 ht， 關(guān)鍵字 x在 ht中的位置可通過其編碼的 k個(gè)最低二進(jìn)制位確定 。 JYP 129 下面通過一個(gè)例子來觀察目錄的動(dòng)態(tài)擴(kuò)展過程。每個(gè)頁(yè)面可容納 2個(gè)記錄。但 b已滿，從而發(fā)生溢出。因?yàn)?a中關(guān)鍵字的 2個(gè)最低位是 00，在 00前面加上 0或 1得到000或 100，由此對(duì)應(yīng)的 2個(gè)目錄項(xiàng)都指向頁(yè)面 a。 在圖（ b）中，頁(yè)面 b和 e分別只被 1個(gè)目錄項(xiàng)指向，局部深度為 3；其余頁(yè)面都被 2個(gè)目錄項(xiàng)指向，局部深度為 2；全局深度為 3。 JYP 135 還需要一個(gè) 散列函數(shù)簇 ，因?yàn)樵谡麄€(gè)表動(dòng)態(tài)變化的不同時(shí)刻，需要不同的二進(jìn)制位個(gè)數(shù)來區(qū)分關(guān)鍵字。 這兩個(gè)頁(yè)面中的關(guān)鍵字的 i個(gè)最低位相同，稱它們?yōu)?伙伴 。 如果 i + 1大于全局深度，則整個(gè)目錄增長(zhǎng)一倍，全局深度加 1。 template class Type struct page { // 頁(yè)面結(jié)構(gòu) record names[PageSize]。 // 該目錄項(xiàng)所指頁(yè)面的局部深度 pageType* paddr。 // 全局深度，要求 1≤gdepth≤KeySize， // 假設(shè) KeySize是已定義的常數(shù) int NumGdepthPage。 // 根據(jù)指向一個(gè)頁(yè)面的目錄項(xiàng)下 // 標(biāo) index，返回指向其伙伴頁(yè)面的目錄項(xiàng)下標(biāo)，這可 // 以通過對(duì) index的首個(gè)二進(jìn)制位作取反操作實(shí)現(xiàn) template class Type int size(const pageType* p)。 // 在頁(yè)面 p中查找關(guān)鍵字 key。 template class Type void PageDelete(const Typeamp。 key) { // 在整個(gè)表中查找關(guān)鍵 // 字為 key的記錄。 else return 0。 // 檢查 key是否已存在 if (p) return