【正文】 (a) 選出最小關(guān)鍵字為 13 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49 27 38 27 38 65 76 27 49 38 65 97 76 ∞ 27 49 輸出 13之后 (b) 選出次小關(guān)鍵字為 27 在輸出最小關(guān)鍵字之后，僅需將葉子結(jié)點(diǎn)中的最小關(guān)鍵字（ 13）改為“最大值”，再從下到上開始比較 38 38 38 65 76 49 38 65 97 76 49 ∞ ∞ 49 49 輸出 13， 27之后 (c) 選出居第三的關(guān)鍵字為 38 樹形選擇排序的時間復(fù)雜度：由于含有 n個葉子結(jié)點(diǎn)的完全二叉樹的深度為 ? ?1lo g 2 ?n則在樹形選擇排序中，除了最小關(guān)鍵字之外，每選擇一個次小關(guān)鍵 字僅需進(jìn)行 次比較，因此它的時間復(fù)雜度為 O(nlog2n)。 （ 2）簡單選擇排序的改進(jìn) 選擇排序的主要操作是進(jìn)行 關(guān)鍵字間的比較 。 ② 一趟快速排序 假設(shè)待排序序列為 {[s], [s+1], … , [t]}, 首先任意選取一個記錄（通?？蛇x為第一個關(guān)鍵字 [s]）作為 樞軸 . 然后按下述原則重新排列其余記錄：將所有關(guān)鍵字較它小的記錄 都安置在它的位置 之前 ，將所有關(guān)鍵字較它 大的記錄 都安置在它的位置 之后 。 復(fù)雜度與增量序列有關(guān) , 目前還未求得最好的增量序列 . ￡ 快速排序 （ 1）起泡排序 起泡排序 （ Bubble Sort）的 過程 ： 1) 首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序（ [1].key [2].key），則將兩個記錄交換之 。 //0號單元為表頭結(jié)點(diǎn) int length。 綜上所述，直接插入排序的時間復(fù)雜度為 O(n2)。 ￡ 概述 （ 2） 內(nèi)部排序的分類 ① 按排序過程中依據(jù)的不同原則： ； ； ； ； ② 按排序過程中所需的工作量： 1．簡單的排序方法， 其時間復(fù)雜度為 O(n2)； 2．先進(jìn)的排序方法，其時間復(fù)雜度為 O(nlogn)； 3．基數(shù)排序，其時間復(fù)雜度為 O(d*n)。 例 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為： H(key)=key MOD 13, 用鏈地址法處理沖突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ￡ 哈希表的查找及其分析 （ 1）相關(guān)術(shù)語 查找過程 ： (1) 給定 K值，根據(jù)造表時設(shè)定的哈希函數(shù)求得哈希地址， 若表中此位置上沒有記錄，則查找不成功 ； (2) 否則比較關(guān)鍵字，若和給定值相等，則查找成功； (3) 否則根據(jù)造表時設(shè)定的處理沖突的方法找“下 一地址”，直至哈希表中某個位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值為止。,2178。 間界疊加 ：從一端向另一端沿分割界來回折疊，然后對齊相加。在計算機(jī)內(nèi)可用兩位八進(jìn)制數(shù)表示字母和數(shù)字 . 如圖 (a)所示。 若要查 1970年出生的人，則只要查第 (1970－ 1948)＝ 22項(xiàng)即可。稱這個對應(yīng)關(guān)系 f為哈希函數(shù)。 因此 ， 二叉排序樹查找的最好時間復(fù)雜度為 O(log2n)， 最壞的時間復(fù)雜度為 O(n)， 一般情形下 ， 其時間復(fù)雜度大致可看成 O(log2n)， 比順序查找效率要好 ， 但比二分查找要差 。 if (!p) T = s。} //查找不成功 else if EQ(key, T－ ) { p = T。 else return (SearchBST (T－ rchild, key))。 1)(212 12 11111??????????? ????ssnsbisjbLLA S L sibjwbbsASLbs＝ Lb＋ Lw ① 用順序查找確定所在塊 ? ?snb /? ；又假定表中每個記錄的查找概率相等，則每 一般情況下，為進(jìn)行分塊查找，可以將長度為 n的表均勻地分成 b塊，每 塊含有 s個記錄，即 塊查找的概率為 1/b，塊中每個記錄的查找概率為 1/s。查找 21的過程如紅線所示，查找 85的過程如藍(lán)線所示。 else low = mid + 1。 ￡ 有序表的查找 （ 1）有序表查找的實(shí)現(xiàn) 折半查找 （ Binary Search）的 查找過程 ：先選定待查記錄所在范 圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 ――i)。 查找算法的平均查找長度＝ 查找成功時的平均查找長度 ＋ 查找不成功時的平均查找長度 ￡ 順序表的查找 （ 1）順序存儲結(jié)構(gòu)的類型定義 typedef struct { ElemType *elem。 查找 （ Searching）：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。第九章 查找 ￡ 查找表 ￡ 概述 查找表 （ Search Table）：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu) 成的集合。 查找成功：查找表中存在關(guān)鍵字等于給定值的記錄。 //數(shù)據(jù)元素存儲空間基址，建表時按 //實(shí)際長度分配， 0號單元留空 int length。 //從后往前找 return i。 特點(diǎn) : 查找過程：每次將待查記錄所在區(qū)間縮小一半 適用條件：采用順序存儲結(jié)構(gòu)的有序表 算法實(shí)現(xiàn) : 設(shè)表長為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn) ,k為給定值 初始時，令 low=1,high=n,mid=?(low+high)/2? 讓 k與 mid指向的記錄比較 若 k==r[mid].key， 查找成功 若 kr[mid].key， 則 high=mid1 若 kr[mid].key， 則 low=mid+1 重復(fù)上述操作，直至 lowhigh時，查找失敗 int Search_Bin (SSTable ST, KeyType key) { //在有序表 ST中折半查找其關(guān)鍵字等于 key的數(shù)據(jù)元素。 //繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 } // while return 0。 圖 判定樹和查找 21(紅線 )， 85(藍(lán)線 )的過程 6 3 9 1 4 7 10 2 5 8 11 1 34 67 910 12 23 45 56 78 89 1011 11 ② 折半查找的平均查找長度 假定有序表的長度 n＝ 2h－ 1（反之， h＝ log2(n+1)），則描述折半 查找的判定樹是深度為 h的滿二叉樹。則分塊查找的平均長 度為： ② 用折半查找確定所在塊 2)1(lo g 2 ssnLAS bs ????ASL（平均查找長度） 最大 最小 兩者之間 表結(jié)構(gòu) 有序表、無序表 有序表 分塊有序表 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 查找方法比較 順序查找 折半查找 分塊查找 特點(diǎn) ：表結(jié)構(gòu)本身是在 查找過程中動態(tài)生成的 ，即對于給定值 key， 若表中存在其關(guān)鍵字等于 key的記錄，則查找成功返回，否則插入關(guān)鍵字 等于 key的記錄。 //在右子樹中繼續(xù)查找 } // SearchBST 算法 (a)如下： ④ 二叉排序樹的插入和刪除 1．插入算法 i． 算法思想 ：根據(jù)二叉排序樹的特點(diǎn)，易知，新插入的結(jié)點(diǎn)一定是一個新添加的葉子結(jié)點(diǎn)，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點(diǎn)的左孩子或右孩子。 return TRUE。 //被插結(jié)點(diǎn) *s為新的根結(jié)點(diǎn) else if LT(, p－ ) //被插結(jié)點(diǎn) *s為左孩子 p－ lchild = s。 （ 2）平衡二叉樹 ① 定義 平衡二叉樹 （ Balanced Binary Tree 或 HeightBalanced Tree）又稱 AVL樹。 基本思想 ：在記錄的 存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 ；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法 關(guān)鍵字 集合 存儲地址 集合 hash ? 哈希表 —— 應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 ~ ? 哈希查找 —— 又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程叫 ~ 例 30個地區(qū)的各民族人口統(tǒng)計表 編號 地區(qū)別 總?cè)丝? 漢族 回族 …... 1 北京 2 上海 …... …... 以 編號 作關(guān)鍵字， 構(gòu)造 哈希函數(shù)： H(key)=key H(1)=1 H(2)=2 以 地區(qū)別 作關(guān)鍵字，取地區(qū) 名稱第一個拼音字母的序號 作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 從例子可見： 哈希函數(shù) 只是一種 映象 ，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可 沖突： key1≠key2，但 H(key1)=H(key2)的現(xiàn)象叫 ~ 同義詞 ：具有相同函數(shù)值的兩個關(guān)鍵字，叫該哈希函數(shù)的 ~ 哈希函數(shù)通常是一種壓縮映象，所以 沖突不可避免 ，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法 ￡ 哈希函數(shù)的構(gòu)造 （ 1）直接定址法 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。 表 直接定址哈希函數(shù)例子二 （ 2）數(shù)字分析法 主要思想 ：假設(shè)關(guān)鍵字是以 r為基的數(shù)（如：以10為基的十進(jìn)制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。取表示符在計算機(jī)中的八進(jìn)制數(shù)為它的關(guān)鍵字。 使用前提 : 關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻時。,3178。 ￡ 哈希表的查找及其分析 （ 1）相關(guān)術(shù)語 影響查找過程中需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的因素 (p260)： 1．哈希函數(shù) 2．沖突處理方法 3．哈希表的裝填因子 裝填因子 ： 哈希表的長度表中填入的記錄數(shù)??其中， α標(biāo)志哈希表的裝滿程度。 ￡ 插入排序 ￡ 直接插入排序 （ 1）主要思想 直接插入排序（ Straight Insertion Sort）：是一種最簡單的排序方法，它的基本操作是將一個記錄插入到 已排好序的有序表中 ，從而得到一個新的、記錄數(shù)增 1的有序表。 ￡ 其他插入排序 （ 1）折半插入排序 ① 主要思想 折半插入排序（ Binary Insertion Sort）：插入排序的基本操作是在一 個有序表中進(jìn)行查找和插入，這個“查找 ”操作若利用“折半查找”來實(shí)現(xiàn)， 則由此進(jìn)行的插入排序稱為折半插入排序。 //鏈表當(dāng)前長度 } SLinkListType。 2) 然后比較第二個記錄和第三個記錄的關(guān)鍵字。 由此可以該“樞軸”記錄最后落的位置 i作分界線，將序列 {[s], … , [t]} 分割成兩個子序列 {[s], [s+1], … , [i － 1]}和 {[i＋ 1], [i+2], … , [t]} 。因此改進(jìn)簡單選擇排序應(yīng)減少“比較”。 ? ?n2log? 堆排序 ? 堆的定義： n個元素的序列 (k1,k2,……kn) ，