查找及應(yīng)用實驗

1、2022-5-111實驗實驗 查找及其應(yīng)用查找及其應(yīng)用信息管理學(xué)院信息管理學(xué)院2022-5-112實驗?zāi)康膶嶒災(zāi)康?. . 掌握順序查找、折半查找方法；掌握順序查找、折半查找方法；2. 2. 進一步理解各查找算法的特點、使進一步理解各查找算法的特點、使用范圍和效率，并能夠使用高級程序用范圍和效率，并能夠使用高級程序設(shè)計語言實現(xiàn)查找算法設(shè)計語言實現(xiàn)查找算法；3. 3. 進一步理解哈希表構(gòu)造算法與哈希進一步理解哈希表構(gòu)造算法與哈希查找算法查找算法；2022-5-113實驗內(nèi)容實驗內(nèi)容1.編程實現(xiàn)順序查找算法（順序查找、設(shè)置監(jiān)視哨的編程實現(xiàn)順序查找算法（順序查找、設(shè)置監(jiān)視哨的順序查找）；順序查找）；

2、2.比較兩種順序查找算法的不同；比較兩種順序查找算法的不同；3.編程實現(xiàn)折半查找算法；編程實現(xiàn)折半查找算法；4.理解順序查找算法和折半查找算法的使用范圍。理解順序查找算法和折半查找算法的使用范圍。2022-5-114基本知識基本知識1.1.什么是查找？什么是查找？根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。于給定值的數(shù)據(jù)元素或（記錄）。若查找表中存在這樣一個記錄，則稱若查找表中存在這樣一個記錄，則稱“查找成功查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位

3、置；找表中的位置； 否則稱否則稱“查找不成功查找不成功”。查找結(jié)果給出。查找結(jié)果給出“空記錄空記錄”或或“空指針空指針”。2022-5-115基本知識基本知識2.2.關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標(biāo)識（識別）一個數(shù)據(jù)元素項的值，用以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）。（或記錄）。若此關(guān)鍵字可以識別唯一的一個記錄，則稱若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂之謂“主關(guān)鍵字主關(guān)鍵字”。若此關(guān)鍵字能識別若干記錄，則稱若此關(guān)鍵字能識別若干記錄，則稱之謂之謂“次關(guān)鍵字次關(guān)鍵字”。2022-5-116基本知識基本知識3.3.如何進行查找？如何進行查找

4、？查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。由于查找表中的數(shù)據(jù)元素之間不存在明顯的由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。組織規(guī)律，因此不便于查找。 為了提高查找的效率，為了提高查找的效率， 需要在查找表中需要在查找表中的元素之間人為地的元素之間人為地 附加某種確定的關(guān)系，附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。換句話說，用另外一種結(jié)構(gòu)來表示查找表。2022-5-117基本知識基本知識4.4.查找的過程就是將給定的查找的過程就是將給定的K K值與文件值與文件中各記錄的關(guān)鍵字項進行比較的過程中各記錄的關(guān)鍵字項進行比較的過程（基本操作）。

5、所以用比較次數(shù)的平（基本操作）。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為均值來評估算法的優(yōu)劣。稱為平均查平均查找長度找長度（ASLASL：Average Search Average Search Length) Length) 。2022-5-118基本知識基本知識5.5.常見的查找表常見的查找表 靜態(tài)查找表靜態(tài)查找表 動態(tài)查找表動態(tài)查找表 哈希表哈希表2022-5-119實驗步驟實驗步驟假設(shè)靜態(tài)查找表為假設(shè)靜態(tài)查找表為順序存儲順序存儲結(jié)構(gòu)結(jié)構(gòu)typedeftypedef float float KeyTypeKeyType; /#define ElemType; /#define El

6、emType float floattypedef inttypedef int KeyTypeKeyType; ; typedeftypedef char char KeyTypeKeyType； /char /char * * 字符串型字符串型數(shù)據(jù)元素類型定義：數(shù)據(jù)元素類型定義：typedef structtypedef struct KeyTypeKeyType key; / key; / 關(guān)鍵字域關(guān)鍵字域 . /. /其他數(shù)據(jù)域（數(shù)據(jù)項）其他數(shù)據(jù)域（數(shù)據(jù)項） ElemType ElemType; ;靜態(tài)查找表的靜態(tài)查找表的順序存儲順序存儲結(jié)構(gòu)的定義結(jié)構(gòu)的定義 - -順序表順序表type

7、def structtypedef struct ElemType ElemType * *elemelem; /; /表基址，表基址，0 0號單元留空。號單元留空。 intint length; / length; /表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTableSSTable; ;2022-5-1110實驗步驟實驗步驟順序查找順序查找：它從表的一端開始，順序掃描：它從表的一端開始，順序掃描線性表，依次掃描節(jié)點關(guān)鍵字，和給定線性表，依次掃描節(jié)點關(guān)鍵字，和給定值值KeyKey相比，直到找到為止。相比，直到找到為止。常規(guī)方法：從常規(guī)方法：從表頭表頭開始，用給定值開始，用給定值K

8、K逐個逐個與表中與表中keykey值比較，若相等則找到，否值比較，若相等則找到，否則繼續(xù)比較，則繼續(xù)比較，直到表尾直到表尾。很顯然，每次。很顯然，每次比較結(jié)束，都要判斷是否到表尾。比較結(jié)束，都要判斷是否到表尾。2022-5-1111實驗步驟實驗步驟對對ST.elemST.elem查找查找k:k:for(i=1;i=ST.length;+ifor(i=1;i1000時，查找時間將減少一半。時，查找時間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ) ; /不要用不要用for(i=n; i0; - -i) 或或 for(i=1; i ST.

9、elemmid.keykey ST.elemmid.key ，說明，說明 keykey mid+1,high mid+1,high ， 則令：則令：low =mid+1low =mid+1; ;重算重算 midmid (low+high)/2(low+high)/2 ；. .(3) (3) 若若 key ST.elemmid.keykey ST.elemmid.key ，說明，說明keykey lowlow ,mid-1 ,mid-1， 則令：則令：high =mid1high =mid1; ;重算重算 mid mid ；(4)(4)若若 ST.elemST.elem mid .key = k

10、ey mid .key = key，說明查找成功，元素序號，說明查找成功，元素序號=mid;=mid;結(jié)束條件：（結(jié)束條件：（1 1）查找成功查找成功 ： ST.elemmid.keyST.elemmid.key = key = key （2 2）查找不成功查找不成功 ： high low high low （意即區(qū)間長度小于（意即區(qū)間長度小于0 0） 2022-5-1118折半查找算法描述折半查找算法描述 2022-5-1119待查序列為5,13,19,21,37,56,64,75,80,88,92,查找70。lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19

11、 21 37 56 64 75 80 88 92找找70701 1次比較次比較ST.elem2022-5-1120low1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找7070highmid2 2次比較次比較ST.elem2022-5-11211 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找7070low high3 3次比較次比較ST.elemmid2022-5-11221 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75

12、 80 88 92找找7070highlow4 4次比較次比較ST.elemmid2022-5-1123low1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找7070high失敗失敗ST.elem2022-5-1124折半查找的性能分析折半查找的性能分析判定樹:描述折半查找過程的二叉樹叫有n個結(jié)點的判定樹的深度為log2n+1(P220-)折半查找法在查找過程中進行的比較次數(shù)最多不超過其判定樹的深度如何計算折半查找算法的平均查找長度（ASL）？2022-5-1125查找過程的判定樹11118 85 52 210107 74 41

13、 19 93 36 6判定樹判定樹1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92成功成功不成不成功功2022-5-1126查找成功的平均查找長度11118 85 52 210107 74 41 19 93 36 6判定樹判定樹成功成功不成不成功功133(1 1224 344)31111ASL 2022-5-1127查找成功的平均查找長度21hnh設(shè)表長，則判定樹是深度為 的滿二叉樹1ipn設(shè)表中每個記錄的查找概率相等1111221121log (1)1log (1)1niiiniihjjASLp ccnjnnnnn則： 樹中層次為

14、樹中層次為1 1的結(jié)點有的結(jié)點有2 20 0個個 樹中層次為樹中層次為2 2的結(jié)點有的結(jié)點有2 21 1個個 樹中層次為樹中層次為h h的結(jié)點有的結(jié)點有2 2h-1h-1個個(h(h層結(jié)點比較層結(jié)點比較h h次次, ,即即h h* *2 2h-1h-1次次) ) 2022-5-1128查找不成功的平均查找長度11118 85 52 210107 74 41 19 93 36 6判定判定樹樹成功成功不成不成功功144(4 38 4)3.671212 2022-5-1129折半查找算法分析折半查找算法分析折半查找的特點折半查找的特點優(yōu)點優(yōu)點: :查找速度快查找速度快缺點缺點: :表必須有序表必須有

15、序, ,頻繁插入和刪除不方便。頻繁插入和刪除不方便。折半查找折半查找適于表中元素變化很少且查找頻繁的情況適于表中元素變化很少且查找頻繁的情況; ;順序表查找順序表查找適于查找少而表中元素頻繁變化的情況。適于查找少而表中元素頻繁變化的情況。2022-5-1130程序調(diào)試步驟程序調(diào)試步驟1 1. .在只有關(guān)鍵字的數(shù)組上實現(xiàn)查找；在只有關(guān)鍵字的數(shù)組上實現(xiàn)查找；IntInt elem100; elem100;2 2. .在結(jié)構(gòu)體數(shù)組上實現(xiàn)查找；在結(jié)構(gòu)體數(shù)組上實現(xiàn)查找；typedef inttypedef int KeyTypeKeyType; ;typedef structtypedef struct

16、 KeyTypeKeyType key; / key; / 關(guān)鍵字域關(guān)鍵字域 int cjint cj； /其他數(shù)據(jù)域（數(shù)據(jù)項）其他數(shù)據(jù)域（數(shù)據(jù)項） ElemType ElemType; ;typedef structtypedef struct ElemType ElemType * *elemelem; /; /表基址，表基址，0 0號單元留空。號單元留空。 intint length; / length; /表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTableSSTable; ;2022-5-1131程序調(diào)試步驟程序調(diào)試步驟3 3. .應(yīng)用實例應(yīng)用實例- -網(wǎng)購貨物物流查找；網(wǎng)購貨物物流查找；typedef inttypedef int KeyTypeKeyType; ;typedef structtypedef struct KeyTypeKeyType key; / key; / 關(guān)鍵字域關(guān)鍵字域 float jefloat je / /其他數(shù)據(jù)域（數(shù)據(jù)項）其他數(shù)據(jù)域（數(shù)據(jù)項） char dddzchar dddz ElemType ElemType; ;typedef structtypedef struct