【正文】 中與 v鄰接的頂點(diǎn)的 dist值可能減少 。 這對(duì)應(yīng)于 上的關(guān)鍵字減少操作 。 TVTV ]}[{m in xd is tTVx ?TVTVTVJYP 32 關(guān)鍵字減少操作的總次數(shù)最多是圖中邊的條數(shù) 。刪除最小元素操作的總次數(shù)是 n – 1。 初始時(shí) ， 含 n – 1個(gè)頂點(diǎn) 。 如果以 dist為關(guān)鍵字 ，將 組織為斐波納契堆 ， 則需要 n – 1次插入操作初始化斐波納契堆 。 接著需要執(zhí)行 n – 1次刪除最小元素操作和最多 e次關(guān)鍵字減少操作 。 所有這些操作的代價(jià)是各操作的分?jǐn)偞鷥r(jià)之和 ， 即 O(n log n + e)。 因此 ， 算法的時(shí)間復(fù)雜性變?yōu)?O(n log n + e)。 當(dāng)e遠(yuǎn)小于 n2時(shí) ， 這顯然是一種改進(jìn) 。 TVTVJYP 33 斐波納契堆在 最短路徑算法中的應(yīng)用 先回憶一下經(jīng)典的最短路徑算法： 1 void Graph::ShortestPath(const int n, const int v) { 2 for (int i = 0。 i n。 i++) { 3 s[i] = FALSE。 dist[i] = length[v][i]。 4 if ( i != v amp。amp。 dist[i] LARGEINT) path[i] = v。 else path[i] = – 1。 5 } 6 s[v] = TRUE。 dist[v] = 0。 7 for (i = 0。 i n2。 i++) { // 確定從 v開(kāi)始的 n – 1條路徑 8 int u = choose(n)。 // 選擇 u，使得對(duì)于所有 s[x] = // FALSE， dist[u] = 最小的 dist[x] 9 s[u] = TRUE。 JYP 34 10 for ( int w = 0。 w n。 w++) 11 if (!s[w]) 12 if (dist[u] + length[u][w] dist[w]) { dist[w] = dist[u] + length[u][w]。 path[w] = u。 } 13 } // for (i = 0。…) 結(jié)束 14} JYP 35 分析： 第 2行的 for循環(huán)需要 O(n)時(shí)間。第 7行的for循環(huán)執(zhí)行 n – 2次，每次需要 O(n)時(shí)間用于第 8行的選擇和第 10到 12行的更新 dist值。因此，該循環(huán)的總時(shí)間是 O(n2)。 整個(gè)算法的時(shí)間是 O(n2)。 即使采用鄰接表，第 10到 12行的總時(shí)間可減少到O(e)（因?yàn)橹挥朽徑幼?u的頂點(diǎn)的 dist可能變化），第 8行的總時(shí)間仍然是 O(n2)。 JYP 36 S 應(yīng)用斐波納契堆 和鄰接表，可使算法的時(shí)間復(fù)雜性減少為 O(n log n + e)。 每次迭代，都需要確定頂點(diǎn) u，使得 u? ，且dist[u] = 。這對(duì)應(yīng)于 上的刪除最小元素操作。 由于 u加入 S， 中與 u鄰接的頂點(diǎn)的 dist值可能減少。這對(duì)應(yīng)于 上的關(guān)鍵字減少操作。 S]}[{m in xd istSx?SSJYP 37 初始時(shí) ， 含 n – 1個(gè)頂點(diǎn) 。 如果以 dist為關(guān)鍵字 ，將 組織為斐波納契堆 ， 則需要 n – 1次插入操作 。 接著需要執(zhí)行 n – 2次刪除最小元素操作和最多 e次關(guān)鍵字減少操作 。 所有這些操作的代價(jià)是各操作的分?jǐn)偞鷥r(jià)之和 ，即 O(n log n + e)。 因此 ， 算法的時(shí)間復(fù)雜性是 O(n log n + e)。 當(dāng) e遠(yuǎn)小于 n2時(shí) ， 這種實(shí)現(xiàn)顯然更好 。 考察題 ： P223 — 23（每個(gè)同學(xué)單獨(dú)完成，并提交報(bào)告，作為本課程主要成績(jī)因素） SSJYP 38 基于鏈表和映射表排序結(jié)果的順序化（ ） 對(duì)于基于鏈表的排序結(jié)果 ， 有時(shí)需要按次序就地重新排列 ， 使它們?cè)谖锢砩弦彩琼樞虻?。 設(shè)記錄表 R0, … , Rn1經(jīng)排序后的結(jié)果是一個(gè)按關(guān)鍵字非遞減次序鏈接的鏈表 ， 且 first是鏈表的首記錄指針 。 將記錄 R0和 Rfirst交換 。 如果 first ? 0， 則表中應(yīng)有一個(gè)記錄 Rx， 其 link字段值為 0。 如果能夠修改 Rx的link字段 ， 使其指向原位于 R0的記錄的新位置 first，則剩余記錄 R1, … , Rn1也是按關(guān)鍵字非遞減次序鏈接的 。 JYP 39 但在單鏈表中 ， 我們無(wú)法快速確定結(jié)點(diǎn) R0的前驅(qū)Rx。 于是可將 R0的 link字段設(shè)置為 first， 表示原位于 R0的記錄已移到 Rfirst。 這樣 ， R0還作為 R1, … , Rn1鏈表中的 虛擬結(jié)點(diǎn) 。借助此虛擬結(jié)點(diǎn) ， 我們可找到剩余記錄鏈表的首結(jié)點(diǎn) 。 重復(fù)上述過(guò)程 n–1次即可完成重新排列 。 一般地 ， 設(shè)記錄表 R0, … , Ri1已在物理上按序排列 ， Rfirst是剩余記錄 Ri, … , Rn1鏈表的首記錄 ， 記錄Ri和 Rfirst交換后 ， 將新 Ri記錄的 link字段設(shè)置為 first，表示原位于 Ri的記錄已移到 Rfirst。 JYP 40 同時(shí) ， 注意到作為剩余記錄 Ri, … , Rn1鏈表的首記錄下標(biāo)的 first總是大于或等于 i， 我們可以經(jīng)過(guò)虛擬結(jié)點(diǎn) ， 找到剩余記錄鏈表的首記錄下標(biāo) 。 函數(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 n – 1。 i++) { // 找到應(yīng)放到位置 i的記錄。由于位置 0, 1, …, i 1的記錄已 // 就位，該記錄下標(biāo)一定 ≥i while (first i) first = list[first].link。 // 經(jīng)過(guò)虛擬結(jié)點(diǎn) JYP 41 int q = list[first].link。 // list[q]是按非遞減次序的下一個(gè) // 記錄，可能是虛擬記錄 if (first != i) { // 交換 list[i] 和 list[first]，并將 list[i].link // 設(shè)置為原 list[i]的新位置 ElementKeyType t = list[i]。 list[i] = list[first]。 list[first] = t。 list[i].link = first。 } first = q。 } } 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次 。每次最多交換 2個(gè)記錄 ， 需要 3次記錄移動(dòng) 。 如果每個(gè)記錄的長(zhǎng)度為 m， 則每次交換的代價(jià)是 3m。 所以 ，最壞情況下記錄移動(dòng)的總代價(jià)是 O(mn)。 在 while循環(huán)中 ， 任何結(jié)點(diǎn)最多被檢查一次 ， 所以while循環(huán)的總時(shí)間是 O(n)。 顯然 ， list所需的輔助空間是 O(m)。 JYP 49 鏈表排序不適用于希爾排序 、 快速排序和堆排序 ，因?yàn)橛涗洷淼捻樞虮硎臼沁@些方法的基礎(chǔ) 。 對(duì)于這些方法可以采用映射表 t， 表的每一個(gè)單元對(duì)應(yīng)一個(gè)記錄 。 映射表單元起著對(duì)記錄間接尋址的作用 。 排序開(kāi)始時(shí) ， t[i] = i， 0≤i≤n–1。 如果要求交換 Ri和 Rj， 則只需交換表單元 t[i]和 t[j]。 排序結(jié)束時(shí) ，關(guān)鍵字最小的記錄是 Rt[0]， 最大的記錄是 Rt[n1]， 所要求的記錄排列是 Rt[0], Rt[1], … , Rt[n1]， 如下一頁(yè)所示 。 JYP 50 JYP 51 有時(shí)為了避免間接尋址，還需要根據(jù)映射表 t確定的置換在物理上重新排列記錄。 整個(gè)置換由不相交的環(huán)路組成。含記錄 i的環(huán)路由 i, t[i], t2[i], …, t k[i]構(gòu)成，且 tk[i] = i。 例如，上一頁(yè)的置換由兩個(gè)環(huán)路組成，第一個(gè)包含記錄 R0和 R4，第二個(gè)包含記錄 R1， R3和 R2。 函數(shù) table首先沿著包含 R0的環(huán)路將記錄移到其正確位置。接著，如果包含 R1的環(huán)路未被移動(dòng)過(guò)，則沿著該環(huán)路將記錄移到其正確位置。由此繼續(xù)移動(dòng)包含 R2, R3, …, R n2的環(huán)路，最終得到物理上就序的記錄表。 JYP 52 template class KeyType void table(ElementKeyType *list, const int n, int *t) { // 重新排列 list[0], …, list[n 1]，使其對(duì)應(yīng)序列 list[t[0]], …, // list[t[n1]], n≥1 for (int i = 0。 i n – 1。 i++) if (t[i] != i) { // 存在一個(gè)開(kāi)始于 i的非平凡環(huán)路 ElementKeyType p = list[i]。 int j = i。 do { int k = t[j]。 list[j] = list[k]。 t[j] = j。 j = k。 } while ( t[j] != i )。 list[j] = p。 // p中的記錄應(yīng)該移到位置 j t[j] = j。 } } JYP 53 例 一個(gè)根據(jù)映射表 t對(duì)記錄順序化的例子： JYP 54 對(duì) table的分析： 設(shè)每個(gè)記錄占用 m個(gè)存儲(chǔ)單元，則所需輔助空間為 O(m)個(gè)存儲(chǔ)單元。 for循環(huán)執(zhí)行了 n–1次。如果對(duì)于某些 i的取值， t[i] ? i，則存在一個(gè)包含 k 1個(gè)不同記錄 Ri, Rt[i], …, Rtk1[i]的環(huán)路。重新排列這些記錄需要 k+1次移動(dòng)。 設(shè) kj是在 for循環(huán)中 i = j時(shí)以 Rj開(kāi)頭的非平凡環(huán)路的記錄個(gè)數(shù)。對(duì)于平凡環(huán)路，則令 kj = 0。記錄移動(dòng)的總次數(shù)是 )1(20,0?????nkjjjkJYP 55 當(dāng) = n且存在 ?n/2?個(gè)非平凡環(huán)路時(shí)，記錄移 動(dòng)的總次數(shù)達(dá)到最大值 — ?3n/2?。 移動(dòng)一個(gè)記錄的代價(jià)是 O(m)，總的計(jì)算時(shí)間是O(m n)。 ? jkJYP 56 二叉查找樹(shù)的結(jié)合與分裂 （ ） 首先回顧二叉查找樹(shù)的 定義： 二叉查找樹(shù)是一棵二叉樹(shù)。如果不空，該樹(shù)應(yīng)滿足以下性質(zhì)： （ 1） 每個(gè)元素有一個(gè)關(guān)鍵字，且任何兩個(gè)不同的元素的關(guān)鍵字不相等（即關(guān)鍵字唯一）； （ 2） 左子樹(shù)（如果存在的話）中的關(guān)鍵字小于根結(jié)點(diǎn)中的關(guān)鍵字； （ 3） 右子樹(shù)（如果存在的話）中的關(guān)鍵字大于根結(jié)點(diǎn)中的關(guān)鍵字； （ 4） 左、右子樹(shù)也是二叉查找樹(shù)。 JYP 57 二叉樹(shù)的例子 : 其中，（ a）不是二叉查找樹(shù)，（ b）和（ c）是。 JYP 58 除了查找、插入和刪除操作以外，有的應(yīng)用還需要對(duì)二叉查找樹(shù)進(jìn)行下列操作： （ 1） (A, x, B)： 構(gòu)建 C， C由原來(lái)在 A和 B中的元素以及元素 x構(gòu)成。假設(shè) A中元素的關(guān)鍵字小于 ， B中元素的關(guān)鍵字大于 。最后將 A和 B設(shè)置為空。 （ 2） (A, B)： 構(gòu)建 C， C由原來(lái)在 A和 B中的元素構(gòu)成。假設(shè) A中