1、第九章第九章 查找查找查找表查找表查找表： 是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合對(duì)查找表經(jīng)常進(jìn)行的對(duì)查找表經(jīng)常進(jìn)行的操作：操作：（1）、查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；（2）、檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；（3）、在查找表中插入一個(gè)數(shù)據(jù)元素；（4）、從查找表中刪除一個(gè)數(shù)據(jù)元素；查找 根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值得數(shù)據(jù)元素（或記錄）關(guān)鍵字關(guān)鍵字 是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)志一個(gè)數(shù)據(jù)元素（或記錄）。 若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱為“主關(guān)鍵字主關(guān)鍵字”。 若此關(guān)鍵字能識(shí)別若干個(gè)記錄，則稱之為“次關(guān)鍵字關(guān)鍵字”。查找 根據(jù)給

2、定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值得數(shù)據(jù)元素（或記錄） 若查找表中存在這樣一個(gè)記錄，則稱“查找成功查找成功”，查找結(jié)果為：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱為“查找不成功查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”如何進(jìn)行查找？如何進(jìn)行查找？取決于查找表的結(jié)構(gòu) 然而，查找表本身是一種松散的結(jié)構(gòu)，因此，為了提高查找的效率，需要在查找表中的勻速之間人為地附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來(lái)表示查找表。根據(jù)操作類型的不同：根據(jù)操作類型的不同： 1、 靜態(tài)查找表 （僅作查詢與檢索操作） 2、動(dòng)態(tài)查找表數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：D是具有相

3、同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable 1.抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)每個(gè)數(shù)據(jù)元素含有類型相同的據(jù)元素含有類型相同的關(guān)鍵字關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。 主關(guān)鍵字主關(guān)鍵字 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：9.1靜態(tài)查找表靜態(tài)查找表1.順序表查找2.有序表查找3.靜態(tài)樹表查找4.索引順序表查找靜態(tài)查找表的查找算法靜態(tài)查找表的查找算法1)順序查找順序查找即用逐一比較的

4、辦法順序查找關(guān)鍵字，即用逐一比較的辦法順序查找關(guān)鍵字，技巧：技巧： 把待查關(guān)鍵字把待查關(guān)鍵字key存入表頭或表尾存入表頭或表尾（俗稱（俗稱“哨兵哨兵”），），即用即用逐一比較逐一比較的辦法順序查找關(guān)鍵字，的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。這顯然是最直接的辦法。技巧：技巧： 把待查關(guān)鍵字把待查關(guān)鍵字key存入表頭或表尾存入表頭或表尾（俗稱（俗稱“哨兵哨兵”），這樣可以加快執(zhí)行），這樣可以加快執(zhí)行速度。速度。21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92

5、05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64示例：已知靜態(tài)查找表ST如下：int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí)，i為0 / Search_Seqint Search_Seq(SSTable ST, KeyType key) pd=0; / 判斷標(biāo)記 for (i=1;i=ST.length; i+) if (ST.e