【正文】 可釋放結(jié)點(diǎn) 5 ，并使結(jié)點(diǎn) 2成為結(jié)點(diǎn) 30的新的左子女。 } 設(shè) h是查找樹的高度 ， 則插入的計(jì)算時(shí)間是 O(h) 。 else p = p?RightChild。該查找不成功，且最后一個(gè)檢查的是結(jié)點(diǎn) 40。 if (k t? LeftSize) t = t?LeftChild。 if (k t?) t = t?LeftChild。 JYP 128 二叉查找樹的查找、插入和刪除操作 1 查找 假設(shè)需要查找關(guān)鍵字為 k的元素 ， 根據(jù)二叉查找樹的性質(zhì) ， 很容易得到其查找方法： ? 查找從樹根開始 。 // 如果 name在符號(hào)表 // 中，則用 attr替換原有屬性，否 // 則將 (name, attr)插入符號(hào)表中 JYP 125 void Delete(Name name)。本章學(xué)習(xí)各種有效實(shí)現(xiàn)符號(hào)表的查找結(jié)構(gòu)。 } } 其中用到函數(shù) List::DeleteMinWeight( )，List::Size( )和 List::Insert( )。 JYP 115 函數(shù) huffman利用一個(gè)由擴(kuò)展二叉樹構(gòu)成的表 list。 BinaryTreeNode *RightChild。信息編碼字中的二進(jìn)制位決定了到達(dá)正確外部結(jié)點(diǎn)需經(jīng)過(guò)的各層分枝。 前面兩棵樹的加權(quán)外部路徑長(zhǎng)度分別是 3?3 + 4?3 + 8?2 + 21?1 = 58 和 3?2 + 4?2 + 8?2 + 21?2 = 72。平均而言， runs生成的歸并段長(zhǎng)度是傳統(tǒng)方法的兩倍。 r[l[t]].key r[q].key)) { // t是勝者 29 int temp = q。 // 生成虛擬記錄，以把實(shí) // 際記錄“頂”出敗者樹 20 else { 21 ReadRecord (r[q])。 int rmax = 1。 5 for ( int i = 0。 ? rc存放當(dāng)前歸并段號(hào)。 JYP 92 設(shè)內(nèi)存可容納 k個(gè)記錄，用 r[0], r[1], …, r[k –1]表示，記錄的輸入和輸出通過(guò) IO緩沖實(shí)現(xiàn)。 歸并 logkm遍的 CPU處理時(shí)間是 O(n log2k logkm) = O(n log2m)， 即與 k無(wú)關(guān) 。 下面將分別討論這些問(wèn)題。 例 ，生成初始?xì)w并段需要 1遍數(shù)據(jù)掃描， 歸并需要 遍數(shù)據(jù)掃描。 其中，就數(shù)據(jù)傳輸而言，尋找和等待都是輔助性的，但其時(shí)間卻較長(zhǎng)。 JYP 75 JYP 76 JYP 77 JYP 78 實(shí)驗(yàn)作業(yè)： P260—25 JYP 79 外排序 概述 需要排序的記錄表大到計(jì)算機(jī)內(nèi)存不能容納時(shí)，內(nèi)排序已不足以解決問(wèn)題。} list[last].link = 1。 f[j] == 1。 j++) f[j] = 1。 i n–1。 JYP 71 假設(shè)記錄表是 R0, …, R n1。 我們按最低位優(yōu)先 （ 簡(jiǎn)稱 LSD） 策略應(yīng)用箱排序解決此問(wèn)題： ? 首先根據(jù) K1將卡片逐張分配到 0號(hào)箱到 9號(hào)箱中 。 這里用關(guān)鍵字值來(lái)確定記錄在最終就序數(shù)組中的位置。 // 重建堆 } } JYP 60 例 用 HeapSort對(duì) (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序過(guò)程： JYP 61 JYP 62 JYP 63 JYP 64 JYP 65 分析： 設(shè) 2k–1≤n 2k，則與記錄表對(duì)應(yīng)的完全二叉樹有 k層，第 i層的結(jié)點(diǎn)數(shù) ≤2i–1。 i = 1。 // 較大者 if (k = tree[j].getKey( )) break。 堆排序通過(guò)最大堆的插入和刪除操作實(shí)現(xiàn)排序： ? 首先將 n個(gè)記錄插入一個(gè)初始為空的堆， ? 接著逐個(gè)從堆中取出記錄。 } JYP 54 函數(shù) rMergeSort利用 ListMerge實(shí)現(xiàn)遞歸歸并排序 ， 并返回已排好序鏈表的首記錄指針： template class KeyType int rMergeSort(ElementKeyType *list, const int left, const int right) { // 將 list[left], …, list[right] 按 key排序。 iResult = i1。 i1 = list[start1].link。 // 1表示空指針 }。 ? 遞歸排序這些子表。 } JYP 47 對(duì) MergeSort的分析： 對(duì)輸入表進(jìn)行多次掃描。 t++) resultList[t] = initList[t]。 如果 i≤n–2len， 則至少還有兩個(gè)長(zhǎng)度都是 len的子表需要?dú)w并 ， 否則需要作特殊邊界處理 。循環(huán)之外的 if語(yǔ)句總共最多移動(dòng) n–l+1個(gè)記錄。 i2++。 在迭代歸并排序中，需要?dú)w并的兩個(gè)表： ? (initListl, … , initList m) ? (initListm+1, … , initList n) 生成的結(jié)果表是 (mergedListl, … , mergedList n)。 JYP 36 InterChange(list, left, j)。 JYP 35 ? 快速排序的最大遞歸深度是 n。兩個(gè)子表的長(zhǎng)度為 j和 n–1–j，相應(yīng)的平均時(shí)間是 Tavg(j) + Tavg(n–1–j)。 為了簡(jiǎn)化邊界判斷，假設(shè)記錄 list[n]的關(guān)鍵字不小于其余關(guān)鍵字。 while (list[j].getKey( ) pivot)。 JYP 22 因此 ， 根據(jù) Ri的關(guān)鍵字大小 ， 整個(gè)記錄表被劃分為左子表 (Rleft, … , Rs(i)–1)和右子表 (Rs(i)+1, … , Rright)，如下圖所示： 由于左 、 右子表的記錄分別在位置 s(i)的左 、 右邊 ， 可獨(dú)立地對(duì)這兩個(gè)子表排序 。 for (int start = 0。 (( ) list[i].getKey( ))) { list[i+incr] = list[i]。 ? 每完成一次上述過(guò)程 ， 增量減少 ， 繼續(xù)利用插入排序?qū)Π葱略隽縿澐值拿總€(gè)子表排序 。 ? 由于算法簡(jiǎn)單，對(duì)于較小的 n（例如 n≤20），插入排序幾乎是最快的。 ????20)1(nii}{max0 jij K??}{m a x0 jijK??JYP 10 插入步驟中的循環(huán)只對(duì)左出序記錄迭代。 // list[i+1] 總是可用于存放記錄 } list[i+1] = e。 假設(shè)在 KeyType被實(shí)例化時(shí)，相應(yīng)實(shí)參類型的 、 =、 = 和 == 等已定義。否則就是不穩(wěn)定的。 ? 表 — 記錄的有限集合。本章學(xué)習(xí)最典型的排序算法，特別討論內(nèi)、外排序的不同策略。 ? 核對(duì)兩個(gè)已按學(xué)號(hào)排序的學(xué)生記錄表可用 O(m+n)時(shí)間完成。 JYP 5 ? 排序 — 確定一種置換 p，使得記錄表（ Rp(0), Rp(1), …, R p(n1)）的關(guān)鍵字滿足性質(zhì)Kp(0)≤Kp(1)≤…≤K p(n1)。}。amp。 } JYP 9 分析： 在最壞情況下， insert(e, list, i)在插入前要作 i+1次比較。 JYP 12 例 設(shè) n = 5， 輸入關(guān)鍵字為 2, 3, 4, 5, 1， 則每次插入后表中記錄的排列如下： 這時(shí)只有 R4是左出序的 。 如果首次 交換 8和 1， 則可減少 2個(gè)左出序記錄 。 為了反映增量，對(duì) InsertionSort及其調(diào)用的 insert作少量修改，得到用于希爾排序的 InsertionSort2以及 insert2。 j += incr) insert2 (list[j + incr], list, j, incr)。 這比插入排序有實(shí)質(zhì)性的改進(jìn) 。 do { do i++。 // 排序左子表 QuickSort(list, j + 1, right)。而且，實(shí)驗(yàn)結(jié)果表明，快速排序的平均性能最好。則 Tavg(m)≤cm + = cm + ≤cm + () )(102 jTmjavgm ???)(1224 jTmjavgmmb ????????1224 l ogmjemkmb jjJYP 32 由于 jlogej是 j的遞增函數(shù)，由 () 式可得 Tavg(m)≤cm + = cm + = cm + = kmlogem + (cm + ) ?? m emkmb x d xx224 l o g][ 42l og24 22 mmmm km b e ??24 l o g kmemb mkm ??24 kmmb ?JYP 33 當(dāng) m≥2， cm + ≤0，所以 Tavg(m)≤kmlogem ? 作業(yè)： P259—7 24 kmmb ?JYP 34 對(duì)基本快速排序算法的改進(jìn) *： ? 基準(zhǔn)記錄的選擇：選當(dāng)前記錄表的第一、中間和最后一個(gè)記錄中關(guān)鍵字為中間值的記錄。 while (list[j].getKey( ) pivot)。 } } } JYP 37 設(shè) S(n)為 ImpQuickSort所需的棧空間 ， 每層遞歸調(diào)用需要棧空間為 c， 則 S(n) ≤ c + S(n/2) ≤ 2c + S(n/4) … ≤clog2n + S(1) = O(log n)。 iResult++) if ( initList[i1].getKey ( ) = initList[i2].getKey ( )) { mergedList[iResult] = initList[i1]。 t = m。 ? 再歸并這 n/2個(gè)表 ， 如此繼續(xù)直到只剩下一個(gè)已排序的表 。 // 剩下的記錄數(shù) 2len if (i+len–1 n–1) // 歸并最后兩個(gè)長(zhǎng)短不一的子表 merge(initList, resultList, i, i+len–1, n–1)。 l*=2。 歸并排序的總時(shí)間為 O(n log n)。 // 關(guān)鍵字 int link。記錄 // 之間通過(guò)整型下標(biāo)鏈接。 } while (i1 1 amp。 } if (i1== 1) list[iResult].link = i2。 } 當(dāng)需要對(duì) list[0], … , list[n–1]排序時(shí) ， 可調(diào)用rMergeSort(list, 0, n–1)。 for (int j = 2*root。 由于第一個(gè)記錄的關(guān)鍵字總是堆中最大的，經(jīng)過(guò)交換該記錄一定是就序的。 list[i+1] = list[1]。 )(22/2/22)(211111111111 nOniniiikkiiikikkiikkii ?????? ????????????????????JYP 66 作業(yè)： P259—16 JYP 67 基數(shù) 排序 當(dāng) n個(gè)記錄的關(guān)鍵字 list[i].key（ 0≤in）的取值是0到 n–1范圍內(nèi)的整數(shù)時(shí)，可以用下列代碼對(duì)其排序： for (int i = 0。 為了有效地利用箱排序的思想，可以將關(guān)鍵字解釋為多個(gè)子關(guān)鍵字： K0, …, K d–1（ K0