《數(shù)據(jù)結構查找課件.ppt》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構查找課件.ppt（71頁珍藏版）》請在匯文網(wǎng)上搜索。

1、數(shù)據(jù)結構數(shù)據(jù)結構第第9 9章章 查找查找n什么是查找？什么是查找？n靜態(tài)查找靜態(tài)查找n動態(tài)查找動態(tài)查找n哈希表哈希表1 1數(shù)據(jù)結構數(shù)據(jù)結構n集合關系集合關系n查找表（查找表（search tablesearch table）2 2數(shù)據(jù)結構數(shù)據(jù)結構查找的基本概念查找的基本概念n n查查查查找找找找表表表表（Search Search Search Search TableTableTableTable）：是是是是由由由由一一一一些些些些具具具具有有有有相相相相同同同同可可可可辨辨辨辨認特性的數(shù)據(jù)元素（或記錄）構成的集合。認特性的數(shù)據(jù)元素（或記錄）構成的集合。認特性的數(shù)據(jù)元素（或記錄）構成的集合。

2、認特性的數(shù)據(jù)元素（或記錄）構成的集合。n n對查找表經(jīng)常進行的對查找表經(jīng)常進行的對查找表經(jīng)常進行的對查找表經(jīng)常進行的操作操作操作操作有：有：有：有：（1 1 1 1）查詢某個）查詢某個）查詢某個）查詢某個 特定的特定的特定的特定的 數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；（2 2 2 2）查找某個）查找某個）查找某個）查找某個 特定的特定的特定的特定的 數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；（3 3 3 3）在查找表中插入一個數(shù)據(jù)元素；）在查找表中插入一個數(shù)據(jù)元素；）在查找表中插入一個數(shù)據(jù)元素；）在查找表中插入一

3、個數(shù)據(jù)元素；（4 4 4 4）從查找表中刪除某個數(shù)據(jù)元素。）從查找表中刪除某個數(shù)據(jù)元素。）從查找表中刪除某個數(shù)據(jù)元素。）從查找表中刪除某個數(shù)據(jù)元素。n靜靜態(tài)態(tài)查查找找表表（Static Static Search Search TableTable）：在在使使用用時時主主要要作作前前兩兩種種統(tǒng)統(tǒng)稱稱為為“查查找找”的的操操作作。即即查查查查找找找找的的的的前前前前后后后后不會改變查找表的內容。不會改變查找表的內容。不會改變查找表的內容。不會改變查找表的內容。n動態(tài)查找表動態(tài)查找表（Dynamic Search TableDynamic Search Table）3 3數(shù)據(jù)結構數(shù)據(jù)結構n n關鍵

4、字關鍵字：是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，：是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標識（識別）一個數(shù)據(jù)元素。若用它可以標識（識別）一個數(shù)據(jù)元素。若此關鍵字可以唯一地標識一個元素，則稱此關鍵字可以唯一地標識一個元素，則稱此關鍵字此關鍵字為主關鍵字為主關鍵字（Primary keyPrimary key）（對）（對不同的元素，其主關鍵字均不同）。反之，不同的元素，其主關鍵字均不同）。反之，稱用以識別若干元素的關鍵字為稱用以識別若干元素的關鍵字為次關鍵字次關鍵字（secondary keysecondary key）。當數(shù)據(jù)元素只有一個）。當數(shù)據(jù)元素只有一個數(shù)據(jù)項時，其關鍵字即為該數(shù)據(jù)元素的值。數(shù)據(jù)項時，

5、其關鍵字即為該數(shù)據(jù)元素的值。4 4數(shù)據(jù)結構數(shù)據(jù)結構n n查找查找查找查找（searchingsearchingsearchingsearching）：是根據(jù)給定的某個值，在查）：是根據(jù)給定的某個值，在查）：是根據(jù)給定的某個值，在查）：是根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素。找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素。找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素。找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素。若表中存在這樣的一個元素，則稱查找是若表中存在這樣的一個元素，則稱查找是若表中存在這樣的一個元素，則稱查找是若表中存在這樣的一個元素，則稱查找是成功的成功的成功的成功

6、的，此時查找的結果為給出整個數(shù)據(jù)元素的信息，或此時查找的結果為給出整個數(shù)據(jù)元素的信息，或此時查找的結果為給出整個數(shù)據(jù)元素的信息，或此時查找的結果為給出整個數(shù)據(jù)元素的信息，或指示該數(shù)據(jù)元素在查找表中的位置；若表中不存指示該數(shù)據(jù)元素在查找表中的位置；若表中不存指示該數(shù)據(jù)元素在查找表中的位置；若表中不存指示該數(shù)據(jù)元素在查找表中的位置；若表中不存在這樣的元素，則稱查找在這樣的元素，則稱查找在這樣的元素，則稱查找在這樣的元素，則稱查找不成功不成功不成功不成功，此時查找的結，此時查找的結，此時查找的結，此時查找的結果可給出一個果可給出一個果可給出一個果可給出一個“null”null”null”null”元

7、素（或空指針）。元素（或空指針）。元素（或空指針）。元素（或空指針）。n n查找算法的評價標準查找算法的評價標準查找算法的評價標準查找算法的評價標準：查找過程的主要操作是關查找過程的主要操作是關鍵字的比較，所以通常以鍵字的比較，所以通常以“平均比較次數(shù)平均比較次數(shù)”來衡來衡量查找算法的時間效率。量查找算法的時間效率。n n對對對對于于于于具具具具有有有有n n n n個個個個數(shù)數(shù)數(shù)數(shù)據(jù)據(jù)據(jù)據(jù)元元元元素素素素的的的的集集集集合合合合，查查查查找找找找某某某某元元元元素素素素成成成成功功功功的的的的平均查找長度為：平均查找長度為：平均查找長度為：平均查找長度為：ASLASL 5 5數(shù)據(jù)結構數(shù)據(jù)結構

8、靜態(tài)查找表靜態(tài)查找表n n順序表的查找（順序查找）順序表的查找（順序查找）n n有序表的查找（折半查找）有序表的查找（折半查找）n n索引順序表的查找（分塊查找）索引順序表的查找（分塊查找）6 6數(shù)據(jù)結構數(shù)據(jù)結構順序表的查找（順序查找）順序表的查找（順序查找）n n順序表的查找將集合中的數(shù)據(jù)元素構成一個序順序表的查找將集合中的數(shù)據(jù)元素構成一個序順序表的查找將集合中的數(shù)據(jù)元素構成一個序順序表的查找將集合中的數(shù)據(jù)元素構成一個序列列列列，以順序表或線性鏈表表示靜態(tài)查找表。，以順序表或線性鏈表表示靜態(tài)查找表。n n順序查找的過程順序查找的過程順序查找的過程順序查找的過程：從表的一端開始，順序（逐：從表

9、的一端開始，順序（逐：從表的一端開始，順序（逐：從表的一端開始，順序（逐個）掃描線性表，依次將掃描到的結點關鍵字個）掃描線性表，依次將掃描到的結點關鍵字個）掃描線性表，依次將掃描到的結點關鍵字個）掃描線性表，依次將掃描到的結點關鍵字和給定值和給定值和給定值和給定值KeyKeyKeyKey相比較，若當前掃描到的結點關鍵相比較，若當前掃描到的結點關鍵相比較，若當前掃描到的結點關鍵相比較，若當前掃描到的結點關鍵字與字與字與字與KeyKeyKeyKey相等，則查找成功；若掃描結束后，仍相等，則查找成功；若掃描結束后，仍相等，則查找成功；若掃描結束后，仍相等，則查找成功；若掃描結束后，仍未找到關鍵字等于

10、未找到關鍵字等于未找到關鍵字等于未找到關鍵字等于KeyKeyKeyKey的結點，則查找失敗。的結點，則查找失敗。的結點，則查找失敗。的結點，則查找失敗。7 7數(shù)據(jù)結構數(shù)據(jù)結構順序查找的實現(xiàn)順序查找的實現(xiàn)n#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100/線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10#define LISTINCREMENT 10 /線性表存儲空間的分配增量線性表存儲空間的分配增量 typedef typedef structstruct ElemTypeElemTyp

11、e*elemelem;/;/存儲空間基址存儲空間基址intint length;/length;/當前長度當前長度intint listsizelistsize;/;/當前分配的存儲容量當前分配的存儲容量 SSTableSSTable;8 8數(shù)據(jù)結構數(shù)據(jù)結構n nintintintint Search_Seq(SSTableSearch_Seq(SSTableSearch_Seq(SSTableSearch_Seq(SSTable ST,KeyTypeST,KeyTypeST,KeyTypeST,KeyType key)key)key)key)intintintint k=ST.len-1;k

12、=ST.len-1;k=ST.len-1;k=ST.len-1;while(k=0&while(k=0&while(k=0&while(k=0&ST.elemkST.elemkST.elemkST.elemk!=key)k-;!=key)k-;!=key)k-;!=key)k-;return(kreturn(kreturn(kreturn(k););););n nintintintint Search_Seq(SSTableSearch_Seq(SSTableSearch_Seq(SSTableSearch_Seq(SSTable ST,KeyTypeST,KeyTypeST,KeyTypeS

13、T,KeyType key)key)key)key)intintintint k=ST.len-1;k=ST.len-1;k=ST.len-1;k=ST.len-1;ST.elem0.key=key;/ST.elem0.key=key;/ST.elem0.key=key;/ST.elem0.key=key;/哨兵哨兵哨兵哨兵 while(while(while(while(ST.elemkST.elemkST.elemkST.elemk!=key)k-;!=key)k-;!=key)k-;!=key)k-;return(kreturn(kreturn(kreturn(k););););9 9數(shù)

14、據(jù)結構數(shù)據(jù)結構順序查找算法分析順序查找算法分析n n由順序查找過程可見，查找表中最后一個元素時，由順序查找過程可見，查找表中最后一個元素時，由順序查找過程可見，查找表中最后一個元素時，由順序查找過程可見，查找表中最后一個元素時，僅需比較一次；僅需比較一次；僅需比較一次；僅需比較一次；查找表中第一個元素時，需比較查找表中第一個元素時，需比較查找表中第一個元素時，需比較查找表中第一個元素時，需比較n n次；次；次；次；對任一元素對任一元素對任一元素對任一元素i i i i需比較需比較需比較需比較n-i+1n-i+1n-i+1n-i+1次。次。次。次。n n設順序表中每個記錄的查找概率相同，即設順序

15、表中每個記錄的查找概率相同，即設順序表中每個記錄的查找概率相同，即設順序表中每個記錄的查找概率相同，即Pi=1/nPi=1/nPi=1/nPi=1/n，則順序查找算法查找成功時的平均查找長度為：，則順序查找算法查找成功時的平均查找長度為：，則順序查找算法查找成功時的平均查找長度為：，則順序查找算法查找成功時的平均查找長度為：ASLseqASLseqASLseqASLseq=n n可以證明，在不等概率查找的情況下，可以證明，在不等概率查找的情況下，可以證明，在不等概率查找的情況下，可以證明，在不等概率查找的情況下，ASLseqASLseqASLseqASLseq在在在在 時取極小值，這就是說，如

16、果事先時取極小值，這就是說，如果事先時取極小值，這就是說，如果事先時取極小值，這就是說，如果事先已經(jīng)知道查找表中各個關鍵字的查找概率的話，則已經(jīng)知道查找表中各個關鍵字的查找概率的話，則已經(jīng)知道查找表中各個關鍵字的查找概率的話，則已經(jīng)知道查找表中各個關鍵字的查找概率的話，則應該按照關鍵字的查找概率從小而大存放數(shù)據(jù)元素。應該按照關鍵字的查找概率從小而大存放數(shù)據(jù)元素。應該按照關鍵字的查找概率從小而大存放數(shù)據(jù)元素。應該按照關鍵字的查找概率從小而大存放數(shù)據(jù)元素。1010數(shù)據(jù)結構數(shù)據(jù)結構有序表的查找（折半查找）有序表的查找（折半查找）n n折半查找要求線性表的結點按其關鍵字從小到大折半查找要求線性表的結點按其關鍵字從小到大折半查找要求線性表的結點按其關鍵字從小到大折半查找要求線性表的結點按其關鍵字從小到大（或從大到小）按序排列，并采用（或從大到小）按序排列，并采用（或從大到小）按序排列，并采用（或從大到?。┌葱蚺帕?，并采用順序存儲順序存儲順序存儲順序存儲結構。結構。結構。結構。n n采用折半查找時，先求位于搜索區(qū)間正中的對象采用折半查找時，先求位于搜索區(qū)間正中的對象采用折半查找時，先求位于搜索區(qū)間