數據結構基礎(下)ppt(編輯修改稿)

　

【文章內容簡介】 作業： P259—13 JYP 48 遞歸 歸并 排序 * 遞歸歸并排序的基本思想： ? 將記錄表劃分成大致等長的左、右子表。 ? 遞歸排序這些子表。 ? 再歸并已排序的子表，從而使整個記錄表就序。 JYP 49 例 對輸入表 (26, 5, 77, 61, 11, 59, 15, 48, 19) 進行遞歸歸并排序過程中的子表劃分： JYP 50 將子表從一個數組歸并到另一個數組需要復制數據。采用鏈表表示可避免數據復制。 假設每個元素至少有兩個字段： link和 key，其結構定義如下： template class KeyType class Element { private: KeyType key。 // 關鍵字 int link。 // 其它字段 public: Element( ) {link = 1。}。 // 1表示空指針 }。 JYP 51 假設： ? 所有訪問 Element私有數據成員的的函數已聲明為Element的友元 。 ? list[i].key和 list[i].link分別是記錄 i的 key和 link字段的值 （ 0≤i≤n–1） 。 ? 初始時 list[i].link = –1（ 0≤i≤n–1） ， 即每個記錄構成一個只含其本身的鏈表 。 JYP 52 函數 ListMerge(list, start1, start2) 將兩個由 start1和 start2指向的按關鍵字非遞減次序鏈接的鏈表歸并為一個按關鍵字非遞減次序鏈接的鏈表 ， 并返回首記錄指針： template class KeyType int ListMerge(ElementKeyType *list, const int start1, const int start2) { // 將分別由 start1和 start2指向的已排序鏈表歸并為 // 一個已排序鏈表，并返回其首記錄的下標。記錄 // 之間通過整型下標鏈接。 int iResult, iStart, i1, i2。 if (list[start1].key = list[start2].key) { // 定位結果表的首記錄 iStart = iResult = start1。 i1 = list[start1].link。 i2 = start2。 } JYP 53 else { iStart = iResult = start2。 i2 = list[start2].link。 i1 = start1。 } while (i1 1 amp。amp。 i2 1) // 歸并 if (list[i1].key = list[i2].key) { list[iResult].link = i1。 iResult = i1。 i1 = list[i1].link。 } else { list[iResult].link = i2。 iResult = i2。 i2 = list[i2].link。 } if (i1== 1) list[iResult].link = i2。 // 鏈接剩余部分 else list[iResult].link = i1。 return iStart。 } JYP 54 函數 rMergeSort利用 ListMerge實現遞歸歸并排序 ， 并返回已排好序鏈表的首記錄指針： template class KeyType int rMergeSort(ElementKeyType *list, const int left, const int right) { // 將 list[left], …, list[right] 按 key排序。返回已 // 排序鏈表的首記錄下標。 if (left = right) return left。 // 最多只含一個記錄 int mid = (left + right)/2。 // 分別排序左、右半部分，并歸并所得的兩個已排序鏈表 return ListMerge(list, rMergeSort(list, left, mid), rMergeSort(list, mid+1, right))。 } 當需要對 list[0], … , list[n–1]排序時 ， 可調用rMergeSort(list, 0, n–1)。 此排序也是穩定的 。 JYP 55 堆 排序 堆排序只需要 O(1)的輔助空間，同時其最壞和平均時間復雜性也都是 O(n log n)。 堆排序通過最大堆的插入和刪除操作實現排序： ? 首先將 n個記錄插入一個初始為空的堆， ? 接著逐個從堆中取出記錄。 然而，還可以通過函數 adjust更快地構建具有 n個記錄的堆。 給定一棵二叉樹 T，其左、右子樹都滿足最大堆的性質，但其根結點卻不一定滿足，函數 adjust調整 T使得整個二叉樹都滿足最大堆性質。 JYP 56 template class KeyType void adjust (ElementKeyType *tree, const int root, const int n) { // 結點下標不大于 n ElementKeyType e = tree[root]。 int k = ( )。 for (int j = 2*root。 j = n。 j *= 2) { if (j n) // j一定有右兄弟 if (tree[j].getKey( ) tree[j+1].getKey( )) j++。 // 較大者 if (k = tree[j].getKey( )) break。 // 如果 k不小于左、右子女 // 中的較大者，則 e可放在 j的雙親處 tree[j/2] = tree[j]。 // 將第 j個記錄上移 } tree[j/2] = e。 } 設以 root為根的樹深為 d，其計算時間為 O(d)。 JYP 57 算法 HeapSort首先利用函數 adjust構建最大堆，如下圖所示： JYP 58 接著對記錄表 list作 n – 1遍處理，每次將當前最大堆的第一個記錄與最后一個交換，并將當前最大堆記錄數減少 1，重新調整。 由于第一個記錄的關鍵字總是堆中最大的，經過交換該記錄一定是就序的。 調用 HeapSort(list, n)即可對 list[1], …, list[n] 排序。 JYP 59 template class KeyType void HeapSort (ElementKeyType *list, const int n) { // 按關 // 鍵字非遞減次序排序 list[1], …, list[n] for (int i = n /2。 i = 1。 i) // 將 list轉化為最大堆 adjust(list, i, n)。 for (i = n – 1。 i = 1。 i) { // 排序 list ElementKeyType t = list[i+1]。 list[i+1] = list[1]。 list[1] = t。 // 交換 list[1]和 list[i+1] adjust(list, 1, i)。 // 重建堆 } } JYP 60 例 用 HeapSort對 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序過程： JYP 61 JYP 62 JYP 63 JYP 64 JYP 65 分析： 設 2k–1≤n 2k，則與記錄表對應的完全二叉樹有 k層，第 i層的結點數 ≤2i–1。第一個 for循環對每個有子女的結點調用 adjust一次。該循環的時間不大于各層結點數與該層結點可移動的最大距離的積之和，即 第二個 for循環調用 adjust共 n–1次，最大深度為 ?log2(n+1)?。 因此，堆排序的總計算時間是 O(n log n)。 而且，只需要 O(1)輔助空間。 )(22/2/22)(211111111111 nOniniiikkiiikikkiikkii ?????? ????????????????????JYP 66 作業： P259—16 JYP 67 基數 排序 當 n個記錄的關鍵字 list[i].key（ 0≤in）的取值是0到 n–1范圍內的整數時，可以用下列代碼對其排序： for (int i = 0。 i n。 i++) result[list[i].key] = list[i]。 這里用關鍵字值來確定記錄在最終就序數組中的位置。這就是最基本的 箱排序 。 其中，我們為 n個關鍵字值安排 n個箱子，并根據關鍵字值將記錄分配到對應的箱中。 此方法效率極高，無論記錄關鍵字的初始順序如何，只需要 O(n) 時間即可完成排序。 JYP 68 在實際應用中，一個箱子可以存放多個記錄，同時關鍵字的取值范圍不必與 n直接關聯。 為了有效地利用箱排序的思想，可以將關鍵字解釋為多個子關鍵字： K0, …, K d–1（ K0是最高位，Kd–1是最低位）。 如果記錄表 R0, …, R n1中的任意兩個記錄 Ri和 Rj（ 0≤i j n）都滿足 則稱該記錄表相對于關鍵字 (K0, …, K d–1) 已排好序。 ),.. .,(),.. .,( 1010 ?? ? djjdii KKKKJYP 69 例如 ， 排序 100張關鍵字值為 0到 99的卡片可看成對兩個子關鍵字 K0和 K1的排序 ， 其中 K0對應十位 ，K1對應個位 。 我們按最低位優先 （ 簡稱 LSD） 策略應用箱排序解決此問題： ? 首先根據 K1將卡片逐張分配到 0號箱到 9號箱中 。 ? 接著 ， 將 8號箱的卡片放在 9號箱的之前 ， … ， 將 0號箱的卡片放在 1號箱的之前 。 ? 再根據 K0按照穩定排序的要求將卡片逐張分配到 0號箱到 9號箱中 ， 按照從 0到 9的箱號順序收集即得到已排序的卡片 。 JYP 70 可見，如果關鍵字是十進制數，可將其中的每個十進制位看成一個子關鍵字，并按 LSD策略用 10個箱子對每個子關鍵字進行箱排序。 一般地，在 基數排序 中，用基數 r分解關鍵字。 當 r = 10，則得到上述十進制分解。 如果關鍵字是長度為 d的小寫英文標識符，則可分解為 d個子關鍵字 (K0, …, K d–1)，其中， Ki ? {‘a’, ‘b’, …, ‘z’} （ 0≤i d）， r = 26。 基數 r排序需要 r個箱子。 JYP 71 假設記錄表是 R0, …, R n1。關鍵字用基數 r分解，每個分解為 d位，每位的取值是 0到 r – 1，則需要 r個箱子。 記錄元素的類定義如下： class Element { public: … private: int key[d]。 // 關鍵字數組， d是常數 // 其它字段 … int link。 }。 JYP 72 每個箱子中的記錄鏈接成隊列 ， f[i]和 e[i]（ 0≤i r） 分別指向第 i個箱子的首 、 尾記錄 。 函數 RadixSort給出了用 LSD策略實現基數 r排序的細節： int RadixSort (Element *list, const int d, const int n) { // 按關鍵字 key[0],…key[d 1]排序 (list[0],…,list[n 1])， // 0≤key[i] radix， radix是常數 int f[radix], e[radix]。 // radix個隊列的首、尾指針 for (int i = 0。 i n–1。 i++) lis