1、第9章 查找9.1 靜態(tài)查找表9.2 動態(tài)查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函數(shù)的構造方法 9.3.3 處理沖突的方法 9.3.4 哈希表的查找及其分析9.3.1 什么是哈希表哈希表技術的主要目標是提高查找效率。1. 哈希函數(shù)： 根據(jù)關鍵字直接計算出元素所在位置的函數(shù)。 例：設哈希函數(shù)為：H(K)=K/3+1，則構造關鍵字序列為 1、2、5、9、11、13、16、21、27 的散列表（哈希表）為：2.沖突 兩個不同的關鍵字具有相同的存儲位置。3.哈希表 根據(jù)設定的哈希函數(shù) H(key) 和處理沖突的方法將一組關鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關鍵字

2、在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映象過程稱為哈希造表或散列，所得存儲位置稱為哈希地址或散列地址。 在哈希存儲中，若發(fā)生沖突，則必須采取特殊的方法來解決沖突問題，才能使哈希查找能順利進行。雖然沖突不可避免，但發(fā)生沖突的可能性卻與三個方面因素有關。 (1)裝填因子； 裝填因子是指哈希表中己存入的元素個數(shù) n 與哈希表的大小 m 的比值，即=n/m（ 724+518+69 =13116. 隨機數(shù)法 選擇一個隨機函數(shù)，取關鍵字的隨機函數(shù)值為它的哈希地址，即H(key)=random (key)，其中random為隨機函數(shù)。 通常，當關鍵字長度不等時采用此法構造哈希函

3、數(shù)較恰當。 實際工作中需視不同情況采用不同的哈希函數(shù)。通常考慮的因素： (1)計算哈希函數(shù)所需時間(包括硬件指令的因素)； (2)關鍵字的長度； (3)哈希表的大??； (4)關鍵字的分布情況； (5)記錄的查找頻率。第9章 查找9.1 靜態(tài)查找表9.2 動態(tài)查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函數(shù)的構造方法 9.3.3 處理沖突的方法 9.3.4 哈希表的查找及其分析9.3.3 處理沖突的方法1.開放地址法 開放地址就是表中尚未被占用的地址，當新插入的記錄所選地址已被占用時，即轉而尋找其它尚開放的地址。（1）線性探測法 設散列函數(shù) H（K）=K mod m （m為表

4、長），若發(fā)生沖突，則沿著一個探查序列逐個探查，那么，第i次計算沖突的散列地址為： Hi=(H(K)+di) mod m (di=1,2,m-1) 例 關鍵碼集為 47，7，29，11，16，92，22，8，3，設：哈希表表長為m=11； 哈希函數(shù)為Hash(key)=key mod 11； 擬用線性探測法處理沖突。建哈希表：0 1 2 3 4 5 6 7 8 9 10291116922283線性探測法的優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點：可能使第i 個哈希地址的同義詞存入第i+1 個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個

5、哈希地址的同義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。 可采用二次探測法或偽隨機探測法，以改善“堆積”問題。 1.開放地址法（2）二次探測法 二次探測法對應的探查地址序列的計算公式為： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,j2,-j2 (jm/2)。0 1 2 3 4 5 6 7 8 9 10若di偽隨機序列，就稱為偽隨機探測法例 關鍵碼集為 47，7，29，11，16，92，22，8，3，設：哈希表表長為m=11； 哈希函數(shù)為Hash(key)=key mod 11；擬用二次探測法處理沖突。建哈希表如下

6、： Hi = ( H(k)+di ) mod m其中di =12,-12,22,-22,j2,-j2 (jm/2)2.鏈地址法優(yōu)點：插入、刪除方便。缺點：占用存儲空間多。基本思想： 將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設 m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。例：設 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函數(shù)為：Hash(key)=key mod 11，用拉鏈法處理沖突，建表。 0 1 2 3 4 5 6 7 8 91022118934737922971650810有沖突的元素可以

7、插在表尾,也可以插在表頭。3.再哈希法Hi= RHi(key) RHi 均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。不易產(chǎn)生“聚集”，但是增加了計算時間。 4.建立一個公共溢出區(qū)第9章 查找9.1 靜態(tài)查找表9.2 動態(tài)查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函數(shù)的構造方法 9.3.3 處理沖突的方法 9.3.4 哈希表的查找及其分析9.3.4 哈希表的查找及其分析 散列表的目的主要是用于快速查找。 在建表時采用何種散列函數(shù)及何種解決沖突的辦法，在查找時，也采用同樣的散列函數(shù)及解決沖突的辦法。例：設有一組關鍵字 19, 01,

8、23, 14, 55, 20, 84, 27, 68, 11, 10, 77 ，采用哈希函數(shù)為： H（k）=k mod 13。采用開放地址的線性探測法解決沖突，試在018的散列地址空間中，對該關鍵字序列構造哈希表。解：依題意 m=19，得到線性探測法對應的探查地址序列計算公式為： di=(H(k)+j) mod 19; j=1,2,18 其計算函數(shù)如下： H(19)=19 mod 13=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=14 mod 13=1 (沖突)H(14)=(1+1) mod 19=2H(55)=55 mod 13=3H(20)=20 m

9、od 13=7H(84)=84 mod 13=6 (沖突)H(84)=(6+1) mod 19=7 (沖突)H(84)=(6+2) mod 19=8H(27)=27 mod 13=1（沖突）H(27)=(1+1) mod 19=2 (沖突)H(27)=(1+2) mod 19=3 (沖突)H(27)=(1+3) mod 19=401234567891011121314151617181919,01,23,14,55,20,84,27,68,11,10,770123145520842777101168 哈希查找的性能分析 哈希查找按理論分析，它的時間復雜度應為O(1)，它的平均查找長度應為ASL

10、=1，但實際上由于沖突的存在，它的平均查找長度將會比1大。下面將分析幾種方法的平均查找長度。1.線性探查法的性能分析 由于線性探查法解決沖突是線性地查找空閑位置的，平均查找長度與表的大小m無關，只與所選取的哈希函數(shù)H及裝填因子的值和該處理方法有關。 這時的成功的平均查找長度為： ASL= (1+1/(1-)/22.鏈地址法查找的性能分析 由于鏈地址法查找就是在單鏈表上查找，查找單鏈表中第一個結點的次數(shù)為1，第二個結點次數(shù)為2，其余依次類推。 平均查找長度： ASL=1+/2例：給定關鍵字序列11，78，10，1，3，2，4，21，試分別用順序查找、二分查找、二叉排序樹查找、平衡二叉樹查找、哈希

11、查找(用線性探查法和拉鏈法)來實現(xiàn)查找，試畫出它們的對應存儲形式(順序查找的順序表，二分查找的判定樹，二叉排序樹查找的二叉排序樹及平衡二叉樹查找的平衡二叉樹，兩種哈希查找的哈希表)，并求出每一種查找的成功平均查找長度。設哈希函數(shù)為： H(k)=k mod 11，哈希表表長m=11。順序查找的順序表（一維數(shù)組） 由圖可得：順序查找的成功平均查找長度為 ASL=(1+2+3+4+5+6+7+8)/8=4.5二分查找的判定樹（中序序列為從小到大排列的有序序列） 由圖可得：二分查找的成功平均查找長度為 ASL=(1+2*2+3*4+4)/8=2.625二叉排序樹（關鍵字順序已確定，該二叉排序樹應唯一）

12、如圖(a)所示，平衡二叉樹（關鍵字順序已確定，該平衡二叉樹也應該是唯一的），如圖(b)所示。 由圖(a)可得：二叉排序樹查找的成功平均查找長度為 ASL=(1+2*2+3*2+4+5*2)/9=3.125由圖(b)可得：平衡二叉樹的成功平均查找長度為 ASL=(1+2*2+3*3+4*2)/8=2.75 11 10 1 3 2 4 78 21 3 1 11 2 10 4 78 21(a)二叉排序樹(b)平衡二叉樹線性探查法解決沖突的哈希表如圖所示。 由圖可得：線性探查法的成功平均查找長度為 ASL=（1+1+2+1+3+2+8+1）/8=2.375鏈地址法解決沖突的哈希表如圖所示。由圖可得：鏈

13、地址法的成功平均查找長度為 ASL=(1*6+2*2)/8=1.25小結 1. 掌握查找的基本概念； 2. 熟練掌握靜態(tài)查找表的查找算法思想并靈活應用； 3. 熟練掌握動態(tài)查找表的特點以及二叉排序樹、平衡二叉樹的各種操作思想 4. 了解B-、B+樹的概念及插入和刪除操作； 5. 熟練掌握哈希表的基本概念、哈希函數(shù)的構造方法和解決沖突的方法，并能計算平均查找長度。第10章 內(nèi)部排序10.1 排序的基本概念10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種內(nèi)部排序方法的比較10.1 排序的基本概念1.排序 設含有n個記錄的文件R1，R2，Rn，

14、相應的關鍵字為K1，K2，Kn，需確定一種排列P(1),P(2)P(n)使其相應的關鍵字滿足遞增(或遞減)關系： KP(1)KP(2)KP(n) 或 KP(1)KP(2)KP(n)使上述文件成為一個按其關鍵字線性有序的文件RP(1)，RP(2) ，RP(n)，這種運算就稱為排序。 將數(shù)據(jù)元素的無序序列調(diào)整為有序序列的過程。2.排序算法的穩(wěn)定性排序碼（Key） 作為排序依據(jù)的記錄中的一個屬性。它可以是任何一種可比的有序數(shù)據(jù)類型，它可以是記錄的關鍵字，也可以是任何非關鍵字。 如果待排序的序列中，存在多個具有相同排序碼的數(shù)據(jù)元素，若經(jīng)過排序這些數(shù)據(jù)元素的相對次序保持不變，則稱這種排序算法是穩(wěn)定的，若

15、經(jīng)過排序，這些數(shù)據(jù)元素的相對次序發(fā)生了改變，則稱這種排序算法是不穩(wěn)定的。3.內(nèi)部排序與外部排序內(nèi)部排序 指當文件的數(shù)據(jù)量不太大時，全部信息放內(nèi)存中處理的排序方法。外部排序 當文件的數(shù)據(jù)量較大時，排序過程中需要在內(nèi)、外存之間不斷地進行數(shù)據(jù)交換才能達到排序的目的，這種排序稱為外排序。4.內(nèi)部排序的方法 內(nèi)部排序的過程是一個逐步擴大記錄的有序序長度的過程。在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。使有序區(qū)中記錄的數(shù)目增加一個或幾個的操作稱為一趟排序。 內(nèi)部排序的方法很多，每種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境(如記錄的初始排列狀態(tài)等)下使用。 排序簡單排序方法，其時間復雜

16、度為O(n2)先進排序方法，其時間復雜度為O(nlogn)基數(shù)排序，其時間復雜度為O(dn)按內(nèi)部排序過程中所需的工作量來區(qū)分： 插入類（直插排序、二分排序、希爾排序） 交換類（冒泡排序、快速排序） 選擇類（直選排序、樹型排序、堆排序） 歸并類（二路歸并排序、多路歸并排序） 分配類（多關鍵字排序、基數(shù)排序）按排序過程中依據(jù)的原則分排序#define MAXSIZE 20 /一個順序表的最大長度typedef int KeyType; /定義關鍵字為整數(shù)類型Typedef struct KeyType key; /關鍵字項 InfoType otherinfo; /其他數(shù)據(jù)項RedType; /

17、記錄類型Typedef struct RedType rMAXSIZE+1; /r0用作哨兵單元 int length; /順序表長度SqList; /順序表類型第10章 內(nèi)部排序10.1 排序的基本概念10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種內(nèi)部排序方法的比較10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希爾排序1）一趟直接插入排序的基本思想 將記錄L.ri插入到有序子序列L.r1.i-1中，使記錄的有序序列從L.r1.i-1變?yōu)長.r1.i。 完成這個“插入”分三步進行： 1查找L.ri在有序子序

18、列L.r 1.i-1中的插入位置j； 2將L.r j.i-1中的記錄后移一個位置； 3將L.r i復制到L.r j的位置上。 整個排序過程進行n1趟插入，即：先將序列中的第1個記錄著成一個有序的子序列，然后從第2個記錄起逐個插入，直至整個序列變成接關鍵字非遞減有序序列為止。1.直接插入排序待排元素序列： 53 27 36 15 69 42第一次排序：(27) 27 53 36 15 69 42第二次排序：(36) 27 36 53 15 69 42第三次排序：(53) 15 27 36 53 69 42第四次排序：(69) 15 27 36 53 69 42第五次排序: (42) 15 27

19、36 42 53 69 直接插入排序示例（插入操作要進行n-1次）2）直接插入排序算法描述 void InsertionSort ( SqList &L ) / 對記錄序列R1.L.length作直接插入排序。 for ( i=2; i=L.length; +i ) L.r0 = L.ri; / 復制為監(jiān)視哨 for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1 = L.rj; / 記錄后移 L.rj+1 = L.r0; / 插入到正確位置 / InsertSort3）直接插入排序性能分析 實現(xiàn)排序的基本操作有： （1）“比較” 關鍵字的大小 （2）“移動”記

20、錄對于直接插入排序： 最好情況“比較”次數(shù)：n-1；“移動”次數(shù)：2(n-1) 最壞的情況“比較”和“移動”的次數(shù)均達到最大值，分別為：(n+2)(n-1)/2；(n+4)(n-1)/2 由于待排記錄序列是隨機的，取上述二值的平均值。所以直接插入排序的時間復雜度為 O(n2)。 直接插入排序是“穩(wěn)定的”：關鍵碼相同的兩個記錄，在整個排序過程中，不會通過比較而相互交換。2.折半插入排序1）基本思想 考慮到 L.r1.i-1 是按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“ L.r1i-1中查找 L.ri 的插入位置”如此實現(xiàn)的插入排序為折半插入排序。(high36 )( 4253 ) 折半插入

21、排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。例：有6個記錄，前5個已排序的基礎上，對第6個記錄排序。 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 42 53 69 high mid lowlow highmid high lowvoid BinsertSort(SqList &L) int i,low,high,mid; for(i=2; i= L.length; +i) L.r0=L.ri; low=1; high=i-1; While(low=high) mid=(low+high)/2; if (L.r0.key=low; j ) L.rj+1=L.rj; L.rlow=L.r0; 2)折半插入排序算法3)折半插入排序性能分析 折半插入排序減少了關鍵字的比較次數(shù)，但記錄的移動次數(shù)