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

1、 - 靜態(tài)查找表靜態(tài)查找表若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功靜態(tài)查找表靜態(tài)查找表動態(tài)查找表動態(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ù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集

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

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

4、文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)項進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為劣。稱為平均查找長度平均查找長度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是文件記錄個數(shù)；是文件記錄個數(shù)；P Pi i是查找第是查找第i i個記錄的查找概率（通常取等概率個記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i個記錄時所經(jīng)歷的比較次數(shù)。個記錄時所經(jīng)歷的比較次數(shù)。統(tǒng)計意義上的統(tǒng)計意義

5、上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為一元素所需的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時間效率越高。值越小，時間效率越高。 （4）如何評估查找方法的優(yōu)劣？）如何評估查找方法的優(yōu)劣？1niiiASLP C針對靜態(tài)查找表的查找算法主要有：針對靜態(tài)查找表的查找算法主要有： 靜態(tài)查找表的順序存儲結(jié)構(gòu)參見教材靜態(tài)查找表的順序存儲結(jié)構(gòu)參見教材P216。一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分?/p>

6、對分查找）三、靜態(tài)樹表的查找三、靜態(tài)樹表的查找四、分塊查找（索引順序查找）四、分塊查找（索引順序查找）（1）順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：typedef struct ElemType *elem; /表基址，表基址，0 0號單元留空。表容量為全部元素號單元留空。表容量為全部元素 int length; /表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。直接的辦法。 v 對對順序結(jié)構(gòu)順序結(jié)構(gòu)如何線性查找？如何線性查找？見下頁之例見下頁之例或教材或

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

8、現(xiàn)方案為：元），則順序查找的實現(xiàn)方案為：從后向前從后向前逐個比較！逐個比較！int Search_Seq( SSTable ST , KeyType key ) /在順序表在順序表STST中，查找關(guān)鍵字與中，查找關(guān)鍵字與keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否則返回置信息，否則返回0 0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過程中每一步設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)都要檢測是否查找完畢。當(dāng)n1000n1000時，查找時間將減少一半。時，查找時間將減少一半。 for( i=ST.length; ST.elem

9、 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號單元才結(jié)束循環(huán)，說明不成功，返回號單元才結(jié)束循環(huán)，說明不成功，返回0 0值值(i=0)(i=0)。成功時則返回找到的那個元素的位置成功時則返回找到的那個元素的位置i i。 / Search_Seq技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），），這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度

10、。例：例：若將待查找的特定值若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號單號單元），則順序查找的實現(xiàn)方案為：元），則順序查找的實現(xiàn)方案為：從后向前從后向前逐個比較！逐個比較！int Search_Seq( SSTable ST , KeyType key )ST.elem0.key =key; for( i=ST.length; ST.elem i .key!=key; - - i ); return i; / Search_Seq返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨哨兵兵”，就是將關(guān)鍵字送入

11、末地址，就是將關(guān)鍵字送入末地址ST.elemST.elem0 0.key.key使之結(jié)束并返回使之結(jié)束并返回 i=0i=0。討論討論 查找效率怎樣計算？查找效率怎樣計算？用平均查找長度用平均查找長度ASL衡量。衡量。討論討論 如何計算如何計算ASL？分析：分析：查找第查找第n個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為1；查找第查找第n-1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為2；查找第查找第1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：總計全部比較次數(shù)為：12n = (1+n)n/2未考慮查找不成功的未考慮查找不成功的情況：查找哨兵所需情況：查找哨兵所需的比較次

12、數(shù)為的比較次數(shù)為n+1n+1這是查找成功的情況這是查找成功的情況若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率），即：即： ASL（1n）/2 ，時間效率為，時間效率為 O(n)優(yōu)點：優(yōu)點：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點：缺點： ASL 太長，時間效率太低。太長，時間效率太低。這是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與正中元素相比，若與正中元素相比，若ke

13、ykey小，則縮小至右半部內(nèi)查找；再取其中小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小值比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。v 對對順序表結(jié)構(gòu)順序表結(jié)構(gòu)如何編程實現(xiàn)折半查找算法？如何編程實現(xiàn)折半查找算法？ 見下頁之例見下頁之例，或見教材（，或見教材（P219P219）v 對對單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何折半查找？如何折半查找？ 無法實現(xiàn)！無法實現(xiàn)！因全部元素的定位只能從頭指針因全部元素的定位只能從頭指針headhead開始開始v 對對非線性非線性(樹樹)結(jié)構(gòu)結(jié)構(gòu)如何折半查找？如何折半查找？ 可借助二叉排序樹來查找（屬動態(tài)查找表形式）。可借

14、助二叉排序樹來查找（屬動態(tài)查找表形式）。 如何改進(jìn)？如何改進(jìn)？討論討論 順序查找的特點：順序查找的特點： 運算步驟運算步驟：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,111,11；(2) (2) 若若 ST.elemmid.key ST.elemmid.key key keykey，說明，說明keykey low ,midlow ,mid-1-1 ， 則令：則令：high =mid1high =mid1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.e

15、lem mid .key = key= key，說明查找成功，元素序號，說明查找成功，元素序號=mid;=mid;結(jié)束條件：結(jié)束條件： （1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： lowlowhigh （意即區(qū)間長度小于（意即區(qū)間長度小于0 0）解：解： 先設(shè)定先設(shè)定3個輔助標(biāo)志個輔助標(biāo)志: low,high,midlow,high,mid，LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指

16、向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個元素的個元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請查找關(guān)鍵字為請查找關(guān)鍵字為21 和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。顯然有：顯然有：mid= (low+high)/2 mjjj112典型標(biāo)志是：當(dāng)查找范圍的上界典型標(biāo)志是：當(dāng)查找范圍的上界下界時停止查找。下界時停止查找。討論討論 二分查找的效率（二分查找的效率（ASLASL）1次比較就查找成功的元素有次比較就查找成功的元素有1個個（20），即），即中間值；中間值；2次比較就查找成功的元素有次比較就查找成功的元素有2

17、個個（21），即），即1/4處（或處（或3/4）處；）處；3次比較就查找成功的元素有次比較就查找成功的元素有4個個（22），即），即1/8處（或處（或3/8）處）處 4次比較就查找成功的元素有次比較就查找成功的元素有8個個（23），即），即1/16處（或處（或3/16）處）處 則第則第m次比較時查找成功的元素會有次比較時查找成功的元素會有（2m-1）個個；為方便起見，假設(shè)表中全部為方便起見，假設(shè)表中全部n個元素個元素 2m-1個，個，此時就不討論第此時就不討論第m次比較后還有剩余元素的情況了。次比較后還有剩余元素的情況了。全部比較總次數(shù)為全部比較總次數(shù)為120221322423m2m1 推推導(dǎo)

18、導(dǎo)過過程程（詳細(xì)推導(dǎo)過程見教材（詳細(xì)推導(dǎo)過程見教材P221的附錄的附錄1）課堂練習(xí)課堂練習(xí)（多項選擇）：（多項選擇）：采用鏈?zhǔn)酱尜A結(jié)構(gòu)采用鏈?zhǔn)酱尜A結(jié)構(gòu) 記錄的長度記錄的長度128 采用順序存貯結(jié)構(gòu)采用順序存貯結(jié)構(gòu) 記錄按關(guān)鍵字遞增有序記錄按關(guān)鍵字遞增有序nnnnjnASLmjj2211log1) 1(log121使用折半查找算法時，要求被查文件：使用折半查找算法時，要求被查文件：思考：思考：假設(shè)在有序線性表假設(shè)在有序線性表a20上進(jìn)行折半查找，則上進(jìn)行折半查找，則平均查找長度為平均查找長度為 。查找過程可用查找過程可用二叉樹二叉樹描述：每個記錄用一個結(jié)點表示；描述：每個記錄用一個結(jié)點表示；結(jié)點

19、中值為該記錄在表中位置，這個描述查找過程的二結(jié)點中值為該記錄在表中位置，這個描述查找過程的二叉樹稱為判定樹。叉樹稱為判定樹。n個元素的表的折半查找的判定樹是唯個元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個數(shù)決定。一的，即：判定樹由表中元素個數(shù)決定。 找到有序表中任一記錄的過程就是找到有序表中任一記錄的過程就是：走了一條從根結(jié)點：走了一條從根結(jié)點到與該記錄相應(yīng)的結(jié)點的路徑。到與該記錄相應(yīng)的結(jié)點的路徑。 比較的關(guān)鍵字個數(shù)：比較的關(guān)鍵字個數(shù)：為該結(jié)點在判定樹上的層次數(shù)。為該結(jié)點在判定樹上的層次數(shù)。 查找成功時查找成功時比較的關(guān)鍵字個數(shù)最多不超過樹的深度比較的關(guān)鍵字個數(shù)最多不超過樹的深度

20、 d : d = log2 n + 1 若所有結(jié)點的空指針域設(shè)置為一個指向一個方形結(jié)點的若所有結(jié)點的空指針域設(shè)置為一個指向一個方形結(jié)點的指針，稱方形結(jié)點為判定樹的外部結(jié)點；對應(yīng)的，圓形指針，稱方形結(jié)點為判定樹的外部結(jié)點；對應(yīng)的，圓形結(jié)點為內(nèi)部結(jié)點。結(jié)點為內(nèi)部結(jié)點。 查找不成功的過程查找不成功的過程 就是走了一條從根結(jié)點到外部結(jié)點就是走了一條從根結(jié)點到外部結(jié)點的路徑。的路徑。這是一種順序查找的另一種改進(jìn)方法。這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)先讓數(shù)據(jù)分塊有序分塊有序，即分成若干子表，要求每個子表中的，即分成若干子表，要求每個子表中的關(guān)關(guān)鍵字的鍵字的值都比后一值都比后一子表要子表要小（但子表內(nèi)部未必有序）。?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表索引表，表中還要包，表中還要包含每個子表的起始地址（即頭指針）。含每個子表的起始地址（即頭指針）。索引表索引表最大關(guān)鍵字起始地址22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53第第1 1塊塊第第2 2塊塊第第3 3塊塊224886例：例：2248861713特點：塊間有特點：塊間有序，塊內(nèi)無序序，塊內(nèi)無序 對索引表使用折半查找法（因為索引表是有序表）；對索引表使用折半查找法（因為索引表是有序表）；