【正文】 離 。 這對(duì)應(yīng)于 上的刪除最小元素操作 。 這對(duì)應(yīng)于 上的關(guān)鍵字減少操作 。刪除最小元素操作的總次數(shù)是 n – 1。 如果以 dist為關(guān)鍵字 ，將 組織為斐波納契堆 ， 則需要 n – 1次插入操作初始化斐波納契堆 。 所有這些操作的代價(jià)是各操作的分?jǐn)偞鷥r(jià)之和 ， 即 O(n log n + e)。 當(dāng)e遠(yuǎn)小于 n2時(shí) ， 這顯然是一種改進(jìn) 。 i n。 dist[i] = length[v][i]。amp。 else path[i] = – 1。 dist[v] = 0。 i n2。 // 選擇 u，使得對(duì)于所有 s[x] = // FALSE， dist[u] = 最小的 dist[x] 9 s[u] = TRUE。 w n。 path[w] = u?！? 結(jié)束 14} JYP 35 分析： 第 2行的 for循環(huán)需要 O(n)時(shí)間。因此，該循環(huán)的總時(shí)間是 O(n2)。 即使采用鄰接表，第 10到 12行的總時(shí)間可減少到O(e)（因?yàn)橹挥朽徑幼?u的頂點(diǎn)的 dist可能變化），第 8行的總時(shí)間仍然是 O(n2)。 每次迭代，都需要確定頂點(diǎn) u，使得 u? ，且dist[u] = 。 由于 u加入 S， 中與 u鄰接的頂點(diǎn)的 dist值可能減少。 S]}[{m in xd istSx?SSJYP 37 初始時(shí) ， 含 n – 1個(gè)頂點(diǎn) 。 接著需要執(zhí)行 n – 2次刪除最小元素操作和最多 e次關(guān)鍵字減少操作 。 因此 ， 算法的時(shí)間復(fù)雜性是 O(n log n + e)。 考察題 ： P223 — 23（每個(gè)同學(xué)單獨(dú)完成，并提交報(bào)告，作為本課程主要成績因素） SSJYP 38 基于鏈表和映射表排序結(jié)果的順序化（ ） 對(duì)于基于鏈表的排序結(jié)果 ， 有時(shí)需要按次序就地重新排列 ， 使它們?cè)谖锢砩弦彩琼樞虻?。 將記錄 R0和 Rfirst交換 。 如果能夠修改 Rx的link字段 ， 使其指向原位于 R0的記錄的新位置 first，則剩余記錄 R1, … , Rn1也是按關(guān)鍵字非遞減次序鏈接的 。 于是可將 R0的 link字段設(shè)置為 first， 表示原位于 R0的記錄已移到 Rfirst。借助此虛擬結(jié)點(diǎn) ， 我們可找到剩余記錄鏈表的首結(jié)點(diǎn) 。 一般地 ， 設(shè)記錄表 R0, … , Ri1已在物理上按序排列 ， Rfirst是剩余記錄 Ri, … , Rn1鏈表的首記錄 ， 記錄Ri和 Rfirst交換后 ， 將新 Ri記錄的 link字段設(shè)置為 first，表示原位于 Ri的記錄已移到 Rfirst。 函數(shù) list實(shí)現(xiàn)了上述方法： template class KeyType void list(ElementKeyType *list, const int n, int first) { // 重新排序由 first指向的鏈表中的記錄，使 list[0],…,list[n 1] // 中的關(guān)鍵字按非遞減次序排列 for (int i = 0。 i++) { // 找到應(yīng)放到位置 i的記錄。 // 經(jīng)過虛擬結(jié)點(diǎn) JYP 41 int q = list[first].link。 list[i] = list[first]。 list[i].link = 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次 。 如果每個(gè)記錄的長度為 m， 則每次交換的代價(jià)是 3m。 在 while循環(huán)中 ， 任何結(jié)點(diǎn)最多被檢查一次 ， 所以while循環(huán)的總時(shí)間是 O(n)。 JYP 49 鏈表排序不適用于希爾排序 、 快速排序和堆排序 ，因?yàn)橛涗洷淼捻樞虮硎臼沁@些方法的基礎(chǔ) 。 映射表單元起著對(duì)記錄間接尋址的作用 。 如果要求交換 Ri和 Rj， 則只需交換表單元 t[i]和 t[j]。 JYP 50 JYP 51 有時(shí)為了避免間接尋址，還需要根據(jù)映射表 t確定的置換在物理上重新排列記錄。含記錄 i的環(huán)路由 i, t[i], t2[i], …, t k[i]構(gòu)成，且 tk[i] = i。 函數(shù) table首先沿著包含 R0的環(huán)路將記錄移到其正確位置。由此繼續(xù)移動(dòng)包含 R2, R3, …, R n2的環(huán)路，最終得到物理上就序的記錄表。 i n – 1。 int j = i。 list[j] = list[k]。 j = k。 list[j] = p。 } } JYP 53 例 一個(gè)根據(jù)映射表 t對(duì)記錄順序化的例子： JYP 54 對(duì) table的分析： 設(shè)每個(gè)記錄占用 m個(gè)存儲(chǔ)單元，則所需輔助空間為 O(m)個(gè)存儲(chǔ)單元。如果對(duì)于某些 i的取值， t[i] ? i，則存在一個(gè)包含 k 1個(gè)不同記錄 Ri, Rt[i], …, Rtk1[i]的環(huán)路。 設(shè) kj是在 for循環(huán)中 i = j時(shí)以 Rj開頭的非平凡環(huán)路的記錄個(gè)數(shù)。記錄移動(dòng)的總次數(shù)是 )1(20,0?????nkjjjkJYP 55 當(dāng) = n且存在 ?n/2?個(gè)非平凡環(huán)路時(shí)，記錄移 動(dòng)的總次數(shù)達(dá)到最大值 — ?3n/2?。 ? jkJYP 56 二叉查找樹的結(jié)合與分裂 （ ） 首先回顧二叉查找樹的 定義： 二叉查找樹是一棵二叉樹。 JYP 57 二叉樹的例子 : 其中，（ a）不是二叉查找樹，（ b）和（ c）是。假設(shè) A中元素的關(guān)鍵字小于 ， B中元素的關(guān)鍵字大于 。 （ 2） (A, B)： 構(gòu)建 C， C由原來在 A和 B中的元素構(gòu)成。最后將 A和 B設(shè)置為空。最后將 A設(shè)置為空。 最后將 0。 JYP 61 2路結(jié)合可通過 3路結(jié)合實(shí)現(xiàn)： 如果 A（ 或 B） 是空樹 ， 則將 （ 或 ） ， 并將 （ 或 ） 設(shè)置為 0即可 。 再執(zhí)行 3路結(jié)合操作(A?, x, B)即可完成整個(gè)操作 。 JYP 62 分裂操作的實(shí)現(xiàn)： 在根結(jié)點(diǎn) （ 即 i == ?） 的分裂很容易 。 如果 i小于根結(jié)點(diǎn)的關(guān)鍵字 ， 根結(jié)點(diǎn)及其右子樹應(yīng)屬于 C， 如圖 （ b） 所示 。 JYP 63 JYP 64 一般地 ， 可以在 A中向下查找關(guān)鍵字為 i的元素的過程中構(gòu)造二叉查找樹 B和 C。 若 i t?， 則結(jié)點(diǎn) t及其右子樹應(yīng)加入 C中 。 若 i == t?， 則應(yīng)將 t的左 、 右子樹分別加入 B、 C中 ， 并將 t?data復(fù)制到 x。 為了避免判斷樹為空的情況 ， 在開始時(shí)為 B和 C分別引入頭結(jié)點(diǎn) Y和 Z。B, ElementTypeamp。C) { // 根據(jù)關(guān)鍵字 i分裂 if (!root) { = = 0。} // 空樹 BstNodeType *Y = new BstNodeType。 BstNodeType *Z = new BstNodeType。 JYP 67 BstNodeType *t = root。 L?LeftChild = t?RightChild。 delete t。 delete Y。 delete Z。 return amp。 } else if (i t?) { L?LeftChild = t。 t = t?LeftChild。 R = t。 } R?RightChild = L?LeftChild = 0。 delete Y。 delete Z。 return 0。 由此容易證明算法的正確性 。 B和 C的高度不超過 A的高度 。 這些方結(jié)點(diǎn)又稱為外部結(jié)點(diǎn) 。 JYP 71 圖 （ b） 的擴(kuò)展二叉樹如下所示： JYP 72 n個(gè)結(jié)點(diǎn)的二叉樹有 n + 1個(gè)外部結(jié)點(diǎn)。 二叉樹的 外部路徑長度 E定義為所有外部結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度之和。 圖 I = 0 + 1 + 1 + 2 = 4 其外部路徑長度 E是 E = 2 + 2 + 2 + 3 + 3 = 12 JYP 73 引理 ： 如果二叉樹 T有 n 個(gè)（ n≥0）內(nèi)部結(jié)點(diǎn)，I是其內(nèi)部路徑長度， E是其外部路徑長度，則 E = I + 2n。 當(dāng) n = 0， E = I = 0，引理 。 考慮一棵有 m + 1個(gè)內(nèi)部結(jié)點(diǎn)的樹，設(shè)該樹的內(nèi)部路徑長度為 I，外部路徑長度為 E。設(shè) k是結(jié)點(diǎn) v到根結(jié)點(diǎn)的路徑長度。 v的每個(gè)子女到根結(jié)點(diǎn)的路徑長度是 k + 1，所以外部路徑長度應(yīng)減少 2(k + 1)再加上新外部結(jié)點(diǎn) v到根結(jié)點(diǎn)的路徑長度 k。 ? JYP 75 查找二叉查找樹的時(shí)間依賴于所考察的內(nèi)部結(jié)點(diǎn)個(gè)數(shù)，假設(shè)一個(gè)內(nèi)部結(jié)點(diǎn)的計(jì)算時(shí)間用 一次比較 度量，下面分析具有 n個(gè)內(nèi)部結(jié)點(diǎn)的二叉查找樹的性能。 在二叉樹完全偏斜時(shí) I達(dá)到最大值。在與根結(jié)點(diǎn)的距離為 1處最多可有 2個(gè)結(jié)點(diǎn)，距離為 2處最多可有 4個(gè)結(jié)點(diǎn)，一般地，最小的 I是 0 + 2 ? 1 + 4 ? 2 + 8 ? 3 + … + 完全二叉樹就是一種具有最小內(nèi)部路徑長度的樹。這樣，最小的 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ù)與該元素不在樹中的不成功查找的相同。由此可得： Sn = 1 + nUUU n 110 . . . ????JYP 80 同時(shí)， Sn = ， Un = ， E = I + 2n，所以， Sn = = 即 Sn = Un – 1 () 1?nI 1?nE)1( 1n?12)1( ??? n nUn n12 ??n nEJYP 81 又由 Sn = 和 Sn = 1 + 可得 I = U0 + U1 + …+ U n1 再由 Un = = 可得 1?nInUUU n 110 . . . ????1?nE12??nnIJYP 82 (n + 1)Un = 2n + U0 + U1 + …+ U n1 為解此遞歸式，用 n – 1替換 n： n Un1 = 2(n – 1) + U0 + U1 + …+ U n2 兩式相減，得： Un = Un1 +