【正文】 O(n2)。 2) 然后比較第二個記錄和第三個記錄的關(guān)鍵字。 （ 1）主要思想 主要思想：先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排 序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序 。 //鏈表當(dāng)前長度 } SLinkListType。 //記錄項 int next。 ￡ 其他插入排序 （ 1）折半插入排序 ① 主要思想 折半插入排序（ Binary Insertion Sort）：插入排序的基本操作是在一 個有序表中進(jìn)行查找和插入，這個“查找 ”操作若利用“折半查找”來實現(xiàn)， 則由此進(jìn)行的插入排序稱為折半插入排序。 ① 當(dāng)待排序列中記錄按關(guān)鍵字非遞減有序排序（“正序”）時，所需進(jìn)行關(guān) ??ni 21鍵字間比較的次數(shù)達(dá)最小值 n－ 1（即 ），記錄不需移動。 ￡ 插入排序 ￡ 直接插入排序 （ 1）主要思想 直接插入排序（ Straight Insertion Sort）：是一種最簡單的排序方法，它的基本操作是將一個記錄插入到 已排好序的有序表中 ，從而得到一個新的、記錄數(shù)增 1的有序表。 若在排序后的序列中 Ri仍領(lǐng)先于 Rj，則稱所用的 排序方法是穩(wěn)定 的； 若可能使排序后的序列中 Rj領(lǐng)先于 Ri，則稱所用的 排序方法是不穩(wěn)定 的。 ￡ 哈希表的查找及其分析 （ 1）相關(guān)術(shù)語 影響查找過程中需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的因素 (p260)： 1．哈希函數(shù) 2．沖突處理方法 3．哈希表的裝填因子 裝填因子 ： 哈希表的長度表中填入的記錄數(shù)??其中， α標(biāo)志哈希表的裝滿程度。) MOD 11=6 沖突 H2=(51178。,3178。 ? 開放定址法 ? 方法： 當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1) 其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列 ? 分類 ? 線性探測再散列： di=1,2,3,……m 1 ? 二次探測再散列： di=1178。 使用前提 : 關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻時。例如，圖 (b)列出了一些標(biāo)識符及它們的哈希地址。取表示符在計算機中的八進(jìn)制數(shù)為它的關(guān)鍵字。假設(shè)這 80個關(guān)鍵字中的一部分如下所列： 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 對關(guān)鍵字全體的分析：第 ①② 位都是“ 8 1”，第 ③ 位只可能取 3或 4，第 ⑧ 位只可能取 5或 7，因此這 4位都不可取。 表 直接定址哈希函數(shù)例子二 （ 2）數(shù)字分析法 主要思想 ：假設(shè)關(guān)鍵字是以 r為基的數(shù)（如：以10為基的十進(jìn)制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。若要詢問 25歲的人有 多少，則只要查表的第 25項即可。 基本思想 ：在記錄的 存儲地址和它的關(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ù)值為哈希地址。 例如，圖 (a)所示為兩棵平衡二叉樹，而 圖 (b)為兩棵不平衡二叉樹，結(jié)點中的值為該結(jié)點 的平衡因子 ② 圖形表示 (a) 平衡二叉樹 1 1 0 0 1 1 1 0 1 0 0 ⑥ 平衡樹查找的分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。 （ 2）平衡二叉樹 ① 定義 平衡二叉樹 （ Balanced Binary Tree 或 HeightBalanced Tree）又稱 AVL樹。 //樹中已有關(guān)鍵字相同的結(jié)點 } // InsertBST 算法 ： iii．例子 例如，從空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉樹。 //被插結(jié)點 *s為新的根結(jié)點 else if LT(, p－ ) //被插結(jié)點 *s為左孩子 p－ lchild = s。 if (!SearchBST (T, , NULL, p)) { //查找不成功 s = (BiTree) malloc (sizeof (BiTree))。 return TRUE。p) { //在根指針 T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素，若 //查找成功，則指針 p指向該數(shù)據(jù)元素結(jié)點，并返回 TRUE，否則指針 p指向 //查找路徑上訪問的最后一個結(jié)點并返回 FALSE，指針 f指向 T的雙親，其初 //始調(diào)用值為 NULL。 //在右子樹中繼續(xù)查找 } // SearchBST 算法 (a)如下： ④ 二叉排序樹的插入和刪除 1．插入算法 i． 算法思想 ：根據(jù)二叉排序樹的特點，易知，新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。 BiTree SearchBST (BiTree T, KeyType key) { //在根指針 T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素， //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，否則返回空指針。則分塊查找的平均長 度為： ② 用折半查找確定所在塊 2)1(lo g 2 ssnLAS bs ????ASL（平均查找長度） 最大 最小 兩者之間 表結(jié)構(gòu) 有序表、無序表 有序表 分塊有序表 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 查找方法比較 順序查找 折半查找 分塊查找 特點 ：表結(jié)構(gòu)本身是在 查找過程中動態(tài)生成的 ，即對于給定值 key， 若表中存在其關(guān)鍵字等于 key的記錄，則查找成功返回，否則插入關(guān)鍵字 等于 key的記錄。如下例所示。 圖 判定樹和查找 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的滿二叉樹。 方形結(jié)點中的值 v為：第 i結(jié)點的值 v 第 i＋ 1結(jié)點的 值； 若 i結(jié)點為第 1個結(jié)點則 v 第 1個結(jié)點的值；若 i結(jié)點為最后一個結(jié)點則 v 最后一個結(jié)點的值。 //繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 } // while return 0。 //low和 high分別指示待查元素所在范圍的下界和上界 while (low = high) { mid = (low + high) / 2。 特點 : 查找過程：每次將待查記錄所在區(qū)間縮小一半 適用條件：采用順序存儲結(jié)構(gòu)的有序表 算法實現(xiàn) : 設(shè)表長為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點 ,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ù)元素。 假設(shè)查找成功與不成功的可能性相同，對每個記錄的查找概率也相等，則 Pi＝ 1/(2n)，此時順序查找的平均查找長度為： )1(21)1(211????? ??ninnA SL niSS )1(43 ?? n缺點：平均查找長度較大，特別是當(dāng) n很大時，查找效率較低。 //從后往前找 return i。 [0].key = key。 //數(shù)據(jù)元素存儲空間基址，建表時按 //實際長度分配， 0號單元留空 int length。 （ 2）查找操作的性能分析 衡量查找算法好壞的 依據(jù) ：其關(guān)鍵字和給定值進(jìn)行過比較的記錄個 數(shù)的平均值。 查找成功：查找表中存在關(guān)鍵字等于給定值的記錄。 ￡ 相關(guān)術(shù)語 關(guān)鍵字 （ Key）：是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用 它可以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）。第九章 查找 ￡ 查找表 ￡ 概述 查找表 （ Search Table）：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu) 成的集合。 動態(tài)查找表 （ Dynamic Search Table）：對查找表不僅作“查找”操 作，在查找過程中還同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找 表中刪除已存在的某個數(shù)據(jù)元素的一類查找表。 查找 （ Searching）：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。此時查找 的結(jié)果可給出一個“空”記錄或“空”指針。 查找算法的平均查找長度＝ 查找成功時的平均查找長度 ＋ 查找不成功時的平均查找長度 ￡ 順序表的查找 （ 1）順序存儲結(jié)構(gòu)的類型定義 typedef struct { ElemType *elem。 //若找到，則函數(shù)值為該元素在表中的位置，否則為 0。 ――i)。則在等概率情況下順序查 找的平均查找長度為： ② 考慮查找成功和查找不成功時的情況 順序查找中，不論給定值 key為何值，查找不成功時和給定值進(jìn)行比較的關(guān) 鍵字個數(shù)均為 n＋ 1。 ￡ 有序表的查找 （ 1）有序表查找的實現(xiàn)