數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏 -第9章 查找1-靜態(tài)查找表(劉)

1、數(shù)據(jù)結(jié)構(gòu)講義數(shù)據(jù)結(jié)構(gòu)講義 - 靜態(tài)查找表靜態(tài)查找表 若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄； 否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置） 查找表查找表 查查 找找 查找成功查找成功 查找不成功查找不成功 靜態(tài)查找表靜態(tài)查找表 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 關(guān)鍵字關(guān)鍵字 主關(guān)鍵字主關(guān)鍵字 次關(guān)鍵字次關(guān)鍵字 由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。 查詢查詢(Searching)特定元素特定元素是否在表中。是否在表中。 只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找

2、，不改變集合內(nèi)的數(shù)據(jù)元素。 既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。 記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄 ( 預(yù)先確定的記錄的某種標(biāo)志預(yù)先確定的記錄的某種標(biāo)志 ) 可以可以唯一唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字 例如例如“學(xué)號(hào)學(xué)號(hào)” 例如例如“女女” 識(shí)別若干記錄的關(guān)鍵字識(shí)別若干記錄的關(guān)鍵字 （2）對(duì)查找表常用的操作有）對(duì)查找表常用的操作有哪些？哪些？ v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中； v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性

3、； v在查找表中插入一元素；在查找表中插入一元素； v從查找表中刪除一元素。從查找表中刪除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式查找方法取決于表中數(shù)據(jù)的排列方式; （1）查找的過程是怎樣的？）查找的過程是怎樣的？ 給定一個(gè)值給定一個(gè)值K K，在含有，在含有n n個(gè)記錄的文件中進(jìn)行搜索，尋找個(gè)記錄的文件中進(jìn)行搜索，尋找 一個(gè)關(guān)鍵字值等于一個(gè)關(guān)鍵字值等于K K的記錄，如找到則輸出該記錄，否則輸出的記錄，如找到則輸出該記錄，否則輸出 查找不成功的信息。查找不成功的信息。 針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也

4、有所不同。 明確：明確：查找的過程就是將給定的查找的過程就是將給定的K K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字 項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu)項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu) 劣。稱為劣。稱為平均查找長度平均查找長度（ASLASL：average search lengthaverage search length）。）。 其中：其中： n n是文件記錄個(gè)數(shù)；是文件記錄個(gè)數(shù)； P Pi i是查找第是查找第i i個(gè)記錄的查找概率（通常取等概率個(gè)記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ; C Ci i是找

5、到第是找到第i i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。 統(tǒng)計(jì)意義上的統(tǒng)計(jì)意義上的 數(shù)學(xué)期望值數(shù)學(xué)期望值 物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每假設(shè)每一元素被查找的概率相同，則查找每 一元素所需的比較次數(shù)之總和再取平均，即為一元素所需的比較次數(shù)之總和再取平均，即為ASLASL。 顯然，顯然，ASLASL值越小，時(shí)間效率越高。值越小，時(shí)間效率越高。 （4）如何評(píng)估查找方法的優(yōu)劣？）如何評(píng)估查找方法的優(yōu)劣？ 1 n ii i ASLP C 針對(duì)靜態(tài)查找表的查找算法主要有：針對(duì)靜態(tài)查找表的查找算法主要有： 靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)參見教材靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)參見

6、教材P216。 一、順序查找（線性查找）一、順序查找（線性查找） 二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥?三、靜態(tài)樹表的查找三、靜態(tài)樹表的查找 四、分塊查找（索引順序查找）四、分塊查找（索引順序查找） （1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)： typedef struct ElemType *elem; /表基址，表基址，0 0號(hào)單元留空。表容量為全部元素號(hào)單元留空。表容量為全部元素 int length; /表長，即表中數(shù)據(jù)元素個(gè)數(shù)表長，即表中數(shù)據(jù)元素個(gè)數(shù) SSTable; 順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的辦法順序

7、查找關(guān)鍵字，這顯然是最 直接的辦法。直接的辦法。 v 對(duì)對(duì)順序結(jié)構(gòu)順序結(jié)構(gòu)如何線性查找？如何線性查找？見下頁之例見下頁之例或教材或教材P216P216； v 對(duì)對(duì)單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易如何線性查找？函數(shù)雖未給出，但也很容易 編寫；只要知道頭指針編寫；只要知道頭指針headhead就可以就可以“順藤摸瓜順藤摸瓜”； v 對(duì)對(duì)非線性樹結(jié)構(gòu)非線性樹結(jié)構(gòu)如何順序查找如何順序查找? ?可借助各種遍歷操作！可借助各種遍歷操作！ 技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），）， 這樣可以加快執(zhí)行速度。這樣可以加快

8、執(zhí)行速度。 例：例：若將待查找的特定值 若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號(hào)單號(hào)單 元），則順序查找的實(shí)現(xiàn)方案為：元），則順序查找的實(shí)現(xiàn)方案為：從后向前從后向前逐個(gè)比較！逐個(gè)比較！ int Search_Seq( SSTable ST , KeyType key ) /在順序表在順序表STST中，查找關(guān)鍵字與中，查找關(guān)鍵字與keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位 置信息，否則返回置信息，否則返回0 0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過程中每一步設(shè)立哨兵，可免去查找過程中每一步 都要檢測(cè)是否查找

9、完畢。當(dāng)都要檢測(cè)是否查找完畢。當(dāng)n1000n1000時(shí)，查找時(shí)間將減少一半。時(shí)，查找時(shí)間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+) return i; /若到達(dá)若到達(dá)0 0號(hào)單元才結(jié)束循環(huán)，說明不成功，返回號(hào)單元才結(jié)束循環(huán)，說明不成功，返回0 0值值(i=0)(i=0)。 成功時(shí)則返回找到的那個(gè)元素的位置成功時(shí)則返回找到的那個(gè)元素的位置i i。 / Search_S

10、eq 技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），）， 這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度。 例：例：若將待查找的特定值 若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號(hào)單號(hào)單 元），則順序查找的實(shí)現(xiàn)方案為：元），則順序查找的實(shí)現(xiàn)方案為：從后向前從后向前逐個(gè)比較！逐個(gè)比較！ int Search_Seq( SSTable ST , KeyType key ) ST.elem0.key =key; for( i=ST.length; ST.elem i .key!=key; - - i ); ret

11、urn i; / Search_Seq 返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨哨 兵兵”，就是將關(guān)鍵字送入末地址，就是將關(guān)鍵字送入末地址ST.elemST.elem0 0.key.key使之結(jié)束并返回使之結(jié)束并返回 i=0i=0。 討論討論 查找效率怎樣計(jì)算？查找效率怎樣計(jì)算？ 用平均查找長度用平均查找長度ASL衡量。衡量。 討論討論 如何計(jì)算如何計(jì)算ASL？ 分析：分析： 查找第查找第n個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為1； 查找第查找第n-1個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為2； 查找第查找第1個(gè)元素所需

12、的比較次數(shù)為個(gè)元素所需的比較次數(shù)為n； 總計(jì)全部比較次數(shù)為：總計(jì)全部比較次數(shù)為：12n = (1+n)n/2 未考慮查找不成功的未考慮查找不成功的 情況：查找哨兵所需情況：查找哨兵所需 的比較次數(shù)為的比較次數(shù)為n+1n+1 這是查找成功的情況這是查找成功的情況 若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率）， 即：即： ASL（1n）/2 ，時(shí)間效率為，時(shí)間效率為 O(n) 優(yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。 缺點(diǎn)：缺點(diǎn)： ASL 太長，時(shí)間效率太低。太長，時(shí)間效率太低。 這是一

13、種容易想到的查找方法。這是一種容易想到的查找方法。 先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey 與正中元素相比，若與正中元素相比，若keykey小，則縮小至右半部內(nèi)查找；再取其中小，則縮小至右半部內(nèi)查找；再取其中 值比較，每次縮小值比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。 v 對(duì)對(duì)順序表結(jié)構(gòu)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？如何編程實(shí)現(xiàn)折半查找算法？ 見下頁之例見下頁之例，或見教材（，或見教材（P219P219） v 對(duì)對(duì)單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何折半查找？如何折半查找？

14、 無法實(shí)現(xiàn)！無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針因全部元素的定位只能從頭指針headhead開始開始 v 對(duì)對(duì)非線性非線性(樹樹)結(jié)構(gòu)結(jié)構(gòu)如何折半查找？如何折半查找？ 可借助二叉排序樹來查找（屬動(dòng)態(tài)查找表形式）。可借助二叉排序樹來查找（屬動(dòng)態(tài)查找表形式）。 如何改進(jìn)？如何改進(jìn)？ 討論討論 順序查找的特點(diǎn)：順序查找的特點(diǎn)： 運(yùn)算步驟運(yùn)算步驟： (1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,111,11； (2) (2) 若若 ST.elemmid.keyST.elemmid.key key keyk

15、ey，說明，說明keykey low ,midlow ,mid-1-1 ， 則令：則令：high =mid1high =mid1; ;重算重算 mid mid ； (4)(4)若若 ST.elemST.elem mid .key mid .key = key= key，說明查找成功，元素序號(hào)，說明查找成功，元素序號(hào)=mid;=mid; 結(jié)束條件：結(jié)束條件： （1 1）查找成功）查找成功 ： ST.elemmid.keyST.elemmid.key = key = key （2 2）查找不成功）查找不成功 ： lowlowhigh （意即區(qū)間長度小于（意即區(qū)間長度小于0 0） 解：解： 先設(shè)定先

16、設(shè)定3個(gè)輔助標(biāo)志個(gè)輔助標(biāo)志: low,high,midlow,high,mid， LowLow指向待查元素指向待查元素 所在區(qū)間的下界所在區(qū)間的下界 highhigh指向待查元素所指向待查元素所 在區(qū)間的上界在區(qū)間的上界 midmid指向待查元素所在指向待查元素所在 區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個(gè)元素的個(gè)元素的有序表有序表： （05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為請(qǐng)查找關(guān)鍵字為21 和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。 顯然有：顯然有：mid= (low+high)/2 m j j j 1 1 2 典型標(biāo)志是：當(dāng)查找范圍的上界典

17、型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。下界時(shí)停止查找。 討論討論 二分查找的效率（二分查找的效率（ASLASL） 1次比較就查找成功的元素有次比較就查找成功的元素有1個(gè)個(gè)（20），即），即中間值；中間值； 2次比較就查找成功的元素有次比較就查找成功的元素有2個(gè)個(gè)（21），即），即1/4處（或處（或3/4）處；）處； 3次比較就查找成功的元素有次比較就查找成功的元素有4個(gè)個(gè)（22），即），即1/8處（或處（或3/8）處）處 4次比較就查找成功的元素有次比較就查找成功的元素有8個(gè)個(gè)（23），即），即1/16處（或處（或3/16）處）處 則第則第m次比較時(shí)查找成功的元素會(huì)有次比較時(shí)查找成功的元素

18、會(huì)有（2m-1）個(gè)個(gè)； 為方便起見，假設(shè)表中全部為方便起見，假設(shè)表中全部n個(gè)元素個(gè)元素 2m-1個(gè)，個(gè)，此時(shí)就不討論第此時(shí)就不討論第m 次比較后還有剩余元素的情況了。次比較后還有剩余元素的情況了。 全部比較總次數(shù)為全部比較總次數(shù)為120221322423m2m1 推推 導(dǎo)導(dǎo) 過過 程程 （詳細(xì)推導(dǎo)過程見教材（詳細(xì)推導(dǎo)過程見教材P221的附錄的附錄1） 課堂練習(xí)課堂練習(xí)（多項(xiàng)選擇）：（多項(xiàng)選擇）： 采用鏈?zhǔn)酱尜A結(jié)構(gòu)采用鏈?zhǔn)酱尜A結(jié)構(gòu) 記錄的長度記錄的長度128 采用順序存貯結(jié)構(gòu)采用順序存貯結(jié)構(gòu) 記錄按關(guān)鍵字遞增有序記錄按關(guān)鍵字遞增有序 nn n n j n ASL m j j 22 1 1 log

19、1) 1(log 1 2 1 使用折半查找算法時(shí)，要求被查文件：使用折半查找算法時(shí)，要求被查文件： 思考：思考：假設(shè)在有序線性表假設(shè)在有序線性表a20上進(jìn)行折半查找，則上進(jìn)行折半查找，則 平均查找長度為平均查找長度為 。 查找過程可用查找過程可用二叉樹二叉樹描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示； 結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過程的二結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過程的二 叉樹稱為判定樹。叉樹稱為判定樹。n個(gè)元素的表的折半查找的判定樹是唯個(gè)元素的表的折半查找的判定樹是唯 一的，即：判定樹由表中元素個(gè)數(shù)決定。一的，即：判定樹由表中元素個(gè)數(shù)決定。 找到有序

20、表中任一記錄的過程就是找到有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)：走了一條從根結(jié)點(diǎn) 到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。 比較的關(guān)鍵字個(gè)數(shù)：比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)。為該結(jié)點(diǎn)在判定樹上的層次數(shù)。 查找成功時(shí)查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度 d : d = log2 n + 1 若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的 指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形 結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。

21、查找不成功的過程查找不成功的過程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn) 的路徑。的路徑。 這是一種順序查找的另一種改進(jìn)方法。這是一種順序查找的另一種改進(jìn)方法。 先讓數(shù)據(jù)先讓數(shù)據(jù)分塊有序分塊有序，即分成若干子表，要求每個(gè)子表中的，即分成若干子表，要求每個(gè)子表中的關(guān)關(guān) 鍵字的鍵字的值都比后一值都比后一子表要子表要?。ǖ颖韮?nèi)部未必有序）。?。ǖ颖韮?nèi)部未必有序）。 然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表索引表，表中還要包，表中還要包 含每個(gè)子表的起始地址（即頭指針）。含每個(gè)子表的起始地址（即頭指針）。 索引表索引表 最大關(guān)鍵字 起始地址 22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53 第第1 1塊塊第第2 2塊塊第第3 3塊塊 224886 例：例： 224886 1713 特點(diǎn)：塊間有特點(diǎn)：塊間有 序，塊內(nèi)無序序，塊內(nèi)無序 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚粚?duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在