第九章_查找 課1

1、1第九章第九章 查查 找找2第九章第九章 查查 找找3第九章第九章 查查 找找4第九章第九章 查查 找找若表中存在特定元素，稱查找成功，應(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)特定元素特定元素是否在表中。是否在表中。只查找，不改變集合

2、內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(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ù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)識(shí)別若干記錄的關(guān)鍵字識(shí)別若干記錄的關(guān)鍵字5第九章第九章 查查 找找6取決于查找表的結(jié)構(gòu)，即：記錄在查找表中所處的位置。取決于查找表的結(jié)構(gòu)，即：記錄在查找表中所處的位置。 查找表本身是一種很松散的結(jié)構(gòu)，因此，為了提高

3、查找表本身是一種很松散的結(jié)構(gòu)，因此，為了提高查找的效率，需要在查找表中的元素之間人為地附加某查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說(shuō)，用另外一種結(jié)構(gòu)來(lái)表示查找種確定的關(guān)系，換句話說(shuō)，用另外一種結(jié)構(gòu)來(lái)表示查找表，以便按某種規(guī)則進(jìn)行查找。表，以便按某種規(guī)則進(jìn)行查找。 第九章第九章 查查 找找7（2）對(duì)查找表常用的操作有）對(duì)查找表常用的操作有哪些？哪些？ v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；v在查找表中插入一元素；在查找表中插入一元素；v從查找表中刪除一元素。

4、從查找表中刪除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式查找方法取決于表中數(shù)據(jù)的排列方式;討論：討論：（1）查找的過(guò)程是怎樣的？）查找的過(guò)程是怎樣的？ 給定一個(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)查找表的查找方法也有所不同?！疤囟ǖ奶囟ǖ摹?關(guān)鍵字關(guān)鍵字8明確：明確

5、：查找的過(guò)程就是將給定的查找的過(guò)程就是將給定的K K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為劣。稱為平均查找長(zhǎng)度平均查找長(zhǎng)度（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是找到第是找到第i i個(gè)記錄時(shí)所經(jīng)歷的

6、比較次數(shù)。個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的統(tǒng)計(jì)意義上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每一假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為元素所需的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時(shí)間效率越高。值越小，時(shí)間效率越高。 如何評(píng)估查找方法的優(yōu)劣？如何評(píng)估查找方法的優(yōu)劣？1niiiASLP C910針對(duì)靜態(tài)查找表的查找算法主要有：針對(duì)靜態(tài)查找表的查找算法主要有： 靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材P216。9.1.1 順序查找（線性查找）順序查找（線

7、性查找）9.1.2 折半查找（二分或?qū)Ψ植檎遥┱郯氩檎遥ǘ只驅(qū)Ψ植檎遥?.1.4 分塊查找（索引順序查找）分塊查找（索引順序查找）11 順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。顯然是最直接的辦法。v對(duì)對(duì)順序結(jié)構(gòu)順序結(jié)構(gòu)如何線性查找？；如何線性查找？；v對(duì)對(duì)單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針很容易編寫；只要知道頭指針headhead就可以就可以“順藤摸順藤摸瓜瓜”；v對(duì)對(duì)非線性樹結(jié)構(gòu)非線性樹結(jié)構(gòu)如何順序查找如何順序查找? ?可借助各種遍歷操可借助各

8、種遍歷操作！作！12數(shù)據(jù)元素存儲(chǔ)空間基址，建數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空號(hào)單元留空表長(zhǎng)度表長(zhǎng)度13能不能把i= 0 加進(jìn)加進(jìn) for語(yǔ)句。語(yǔ)句。1516 例：查找例：查找 key = 8 的結(jié)點(diǎn)所在的數(shù)組元素的下標(biāo)的結(jié)點(diǎn)所在的數(shù)組元素的下標(biāo)012n-3n-2n-1ni數(shù)組數(shù)組 ST.elemkey8100100813012n-3n-2n-1ni數(shù)組數(shù)組 ST.elemkey8100100813012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100813i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100813i

9、17012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100813ii = n-2012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100813ii = n-2 查找成功，則查找成功，則 i 是是key 值為值為 8 的結(jié)點(diǎn)所在的結(jié)點(diǎn)所在的數(shù)組元素的下標(biāo)。的數(shù)組元素的下標(biāo)。18012n-3n-2n-1ni數(shù)組數(shù)組 ST.elemkey8100100713012n-3n-2n-1ni數(shù)組數(shù)組 ST.elemkey8100100713012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey81

10、00100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i19012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey8100100713i012n-3n-2n-1n數(shù)組數(shù)

11、組 ST.elemkey8100100713i20012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey查找失敗，則查找失敗，則 i = 0; 8100100713012n-3n-2n-1n數(shù)組數(shù)組 ST.elemkey查找失敗，則查找失敗，則 i = 0; 8100100713 查找失敗，則查找失敗，則i=0。21返回特殊標(biāo)志，例如返回空記錄或空返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了指針。前例中設(shè)立了“哨兵哨兵”，就是將關(guān)，就是將關(guān)鍵字送入末地址鍵字送入末地址ST.elemST.elem0 0.key.key使之結(jié)束使之結(jié)束并返回并返回 i=0i=0。討論討論 查找效率怎樣計(jì)算

12、？查找效率怎樣計(jì)算？用平均查找長(zhǎng)度用平均查找長(zhǎng)度ASL衡量。衡量。討論討論 查不到怎么辦？查不到怎么辦？22討論討論 如何計(jì)算如何計(jì)算ASL？分析：分析：查找第查找第1個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為1；查找第查找第2個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為2；查找第查找第n個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：總計(jì)全部比較次數(shù)為：12n = (1+n)n/2未考慮查找不成功的未考慮查找不成功的情況：查找哨兵所需情況：查找哨兵所需的比較次數(shù)為的比較次數(shù)為n+1n+1這是查找成功的情況這是查找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一

13、個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率），即：即： ASL（1n）/2 ，時(shí)間效率為，時(shí)間效率為 O(n)23成功時(shí)的平均查找長(zhǎng)度成功時(shí)的平均查找長(zhǎng)度) 1(4321) 1(211nninnASLni查找成功時(shí)查找不成功時(shí)24 順序查找的優(yōu)缺點(diǎn)：順序查找的優(yōu)缺點(diǎn)：25折半查找（又稱二分查找或?qū)Ψ植檎遥┱郯氩檎遥ㄓ址Q二分查找或?qū)Ψ植檎遥┻@是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與正中元素相比，若與正中元素相比，若keykey小，則縮小至右半部?jī)?nèi)查找；再

14、取其中小，則縮小至右半部?jī)?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)如何折半查找？如何折半查找？ 無(wú)法實(shí)現(xiàn)！無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針因全部元素的定位只能從頭指針headhead開始開始v 對(duì)對(duì)非線性非線性(樹樹)結(jié)構(gòu)結(jié)構(gòu)如何折半查找？如何折半查找？ 可借助二叉排序樹來(lái)查找（屬動(dòng)態(tài)查找表形式）。可借助二叉排序樹來(lái)查找（屬動(dòng)態(tài)查找表形式

15、）。 26 運(yùn)算步驟運(yùn)算步驟：(1) (1) low =1,high =11 ,mid =6 low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,111,11；(2) (2) 若若 ST.elemmid.key ST.elemmid.key key keykey，說(shuō)明，說(shuō)明keykey low ,midlow ,mid-1-1 ， 則令：則令：high =midhigh =mid1 1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.elem mid .key = key= key，說(shuō)明查找成功，元素序號(hào)，說(shuō)明查找成功，元素序

16、號(hào)=mid;=mid;結(jié)束條件結(jié)束條件（1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlow highlow （意即區(qū)間長(zhǎng)度小于（意即區(qū)間長(zhǎng)度小于0 0）解：解： 先設(shè)定先設(shè)定3個(gè)輔助標(biāo)志個(gè)輔助標(biāo)志: low,high,midlow,high,mid，折半查找舉例：LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如

17、下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 27012mid=4 但但 key=9 10, 向左向左key4891011131934567high=7low=1012mid=4 但但 key=9 8, 向向右右key4891011131934567high=3（mid-1）low=1012mid=2; 但但 key=9 8, 向向右右key4891011131934567high=3（mid-1）low=1012k

18、ey4891011131934567high=3low=3（mid+1）mid=2012key4891011131934567high=3low=3（mid+1）mid=230012key4891011131934567high=3low=3012key4891011131934567high=3low=3012m id=3; 但但 key=9 中中 點(diǎn)點(diǎn) 值值 也也 為為 9 ，找找 到到key4891011131934567high=3low =3012m id=3; 但但 key=9 中中 點(diǎn)點(diǎn) 值值 也也 為為 9 ，找找 到到key4891011131934567high=3low

19、=331012mid=4 但但 key=5 10, 向左向左key4891011131934567high=7low=1012mid=4 但但 key=5 10, 向左向左key4891011131934567high=7low=1012mid=4key4891011131934567high=3（mid-1）low=1012mid=4key4891011131934567high=3（mid-1）low=132012mid=2key4891011131934567high=3low=1012mid=2key4891011131934567high=3low=1012mid=2; 但但 key

20、=5 8, 向向左左key4891011131934567high=3low=1012mid=2; 但但 key=5 4, 向向右右key4891011131934567high=1low=1012mid=1; 但但 key=5 4, 向向右右key4891011131934567high=1low=1012mid=1; 但但 key=5 4, 向右向右key4891011131934567high=1low=2 （mid+1）失敗條件：失敗條件：low high; 處于處于間隙中的鍵值導(dǎo)致這種情況！間隙中的鍵值導(dǎo)致這種情況！012mid=1; 但但 key=5 4, 向右向右key48910

21、11131934567high=1low=2 （mid+1）012mid=1; 但但 key=5 4, 向右向右key4891011131934567high=1low=2 （mid+1）失敗條件：失敗條件：low high; 處于處于間隙中的鍵值導(dǎo)致這種情況！間隙中的鍵值導(dǎo)致這種情況！3536mjjj112討論討論 若關(guān)鍵字不在表中，怎樣得知和停止？若關(guān)鍵字不在表中，怎樣得知和停止？典型標(biāo)志是：當(dāng)查找范圍的上界典型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。下界時(shí)停止查找。討論討論 二分查找的效率（二分查找的效率（ASLASL平均查找長(zhǎng)度）平均查找長(zhǎng)度）1次比較就查找成功的元素有次比較就查找成功

22、的元素有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í)查找成功的元素會(huì)有（2m-1）個(gè)；）個(gè)；為方便起見，假設(shè)表中全部為方便起見，假設(shè)表中全部n個(gè)元素個(gè)元素 2m-1個(gè)個(gè)，此時(shí)就不討論第此時(shí)就不討論第m次比較后還有剩余元素

23、的情況了。次比較后還有剩余元素的情況了。全部比較總次數(shù)為全部比較總次數(shù)為120221322423m2m1 推推導(dǎo)導(dǎo)過(guò)過(guò)程程37平均每個(gè)數(shù)據(jù)的查找時(shí)間還要除以平均每個(gè)數(shù)據(jù)的查找時(shí)間還要除以n，所以：所以：（詳細(xì)推導(dǎo)過(guò)程見教材（詳細(xì)推導(dǎo)過(guò)程見教材P221的附錄的附錄1）課堂練習(xí)課堂練習(xí)（多項(xiàng)選擇）：（多項(xiàng)選擇）：采用鏈?zhǔn)酱尜A結(jié)構(gòu)采用鏈?zhǔn)酱尜A結(jié)構(gòu) 記錄的長(zhǎng)度記錄的長(zhǎng)度128 采用順序存貯結(jié)構(gòu)采用順序存貯結(jié)構(gòu) 記錄按關(guān)鍵字遞增有序記錄按關(guān)鍵字遞增有序nnnnjnASLmjj2211log1) 1(log121使用折半查找算法時(shí)，要求被查文件：使用折半查找算法時(shí)，要求被查文件：上述平均查找長(zhǎng)度（ASL）

24、計(jì)算成立的前提是第m次比較時(shí)恰好剩余2m-1個(gè)。個(gè)。38填空：填空：假設(shè)在有序線性表假設(shè)在有序線性表a20上進(jìn)行折半查找，則比較一上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)；比較兩次查找成功的結(jié)點(diǎn)數(shù)為數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8 ；平均查找長(zhǎng)度為平均查找長(zhǎng)度為 3.7 。 顯然，平均查找長(zhǎng)度顯然，平均查找長(zhǎng)度O（log2n）5次（次（25）。但具體是）。但具體是多少次，則不應(yīng)當(dāng)按照公式多少次，則不應(yīng)當(dāng)按照公式) 1(log12nnnASL來(lái)計(jì)算（來(lái)計(jì)算（即（即（21log221）/204.6次并不正確！次

25、并不正確！）。因?yàn)檫@是在假）。因?yàn)檫@是在假設(shè)設(shè)n2m-1的情況下推導(dǎo)出來(lái)的公式。的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列：應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為（全部元素的查找次數(shù)為（122438455）74； ASL74/20=3.7 ！39查找過(guò)程可用查找過(guò)程可用二叉樹二叉樹描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過(guò)程的二叉樹稱為中值為該記錄在表中位置，這個(gè)描述查找過(guò)程的二叉樹稱為判定樹判定樹。n個(gè)元素的表的折半查找的判定樹是唯一的，即：判個(gè)元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個(gè)數(shù)決定。定樹由表中元素個(gè)數(shù)決

26、定。 找到有序表中任一記錄的過(guò)程就是找到有序表中任一記錄的過(guò)程就是：走了一條從根結(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ù)最多不超過(guò)樹的深度最多不超過(guò)樹的深度 d : d = log2 n + 1 查找不成功的過(guò)程查找不成功的過(guò)程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。徑。折半查找效率分析法（參見教材折半查找效率分析法（參見教材P220）：）：4041是一種順序查找的另一種改進(jìn)方

27、法。是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)先讓數(shù)據(jù)分塊有序分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)，即分成若干子表，要求每個(gè)子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值小（但子表內(nèi)部未必有序）。有序）。然后將各子表中的然后將各子表中的最大關(guān)鍵字最大關(guān)鍵字構(gòu)成一個(gè)構(gòu)成一個(gè)索引表索引表，表中還要包，表中還要包含每個(gè)子表的起始地址（即頭指針）。含每個(gè)子表的起始地址（即頭指針）。索引表索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第第1 1塊塊第第2 2塊塊第第3 3塊塊224886例：例：22

28、48861713特點(diǎn)：塊間有特點(diǎn)：塊間有序，塊內(nèi)無(wú)序序，塊內(nèi)無(wú)序42387363521406012345678947索引索引順序表順序表83660147塊最大關(guān)鍵字塊最大關(guān)鍵字塊起始地址塊起始地址索引表索引表塊最大關(guān)鍵字有序塊最大關(guān)鍵字有序塊內(nèi)關(guān)鍵字無(wú)序（也可有序）塊內(nèi)關(guān)鍵字無(wú)序（也可有序）387363521406012345678947索引索引順序表順序表83660147塊最大關(guān)鍵字塊最大關(guān)鍵字塊起始地址塊起始地址索引表索引表塊最大關(guān)鍵字有序塊最大關(guān)鍵字有序塊內(nèi)關(guān)鍵字無(wú)序（也可有序）塊內(nèi)關(guān)鍵字無(wú)序（也可有序）434445查找步驟查找步驟分兩步進(jìn)行分兩步進(jìn)行： 對(duì)索引表使用折半查找法（因?yàn)樗饕?/p>

29、表是有序表）；對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w對(duì)索引表查找的對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的對(duì)塊內(nèi)查找的ASL)21(log2) 1(log22nASLnssnASLbsbsS為每塊內(nèi)部的記錄個(gè)數(shù)，為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目即塊的數(shù)目例如當(dāng)例如當(dāng)n=9n=9，s=3s=3時(shí)時(shí)，ASLASLbsbs= =3.53.5, ,而折半而折半法為法為3.13.

30、1, ,順序法為順序法為5 5。46查查找找算算法法 存存儲(chǔ)儲(chǔ)結(jié)結(jié)構(gòu)構(gòu) 優(yōu)優(yōu)點(diǎn)點(diǎn) 缺缺點(diǎn)點(diǎn) 適適用用于于 順順序序查查找找 順順序序結(jié)結(jié)構(gòu)構(gòu) 鏈鏈表表結(jié)結(jié)構(gòu)構(gòu) 算算 法法 簡(jiǎn)簡(jiǎn) 單單 且且 對(duì)對(duì) 表表 的的結(jié)結(jié)構(gòu)構(gòu)無(wú)無(wú)任任何何要要求求 查查找找效效率率低低 n n 較較小小的的表表的的查查找找和和查查找找較較少少但但改改動(dòng)動(dòng)較較多多的的表表( (用用鏈鏈表表作作存存儲(chǔ)儲(chǔ)結(jié)結(jié)構(gòu)構(gòu)) ) 二二分分查查找找 順順序序結(jié)結(jié)構(gòu)構(gòu) 查查找找效效率率高高 關(guān)關(guān)鍵鍵字字要要有有序序且且只只能能用用順順序序存存儲(chǔ)儲(chǔ)結(jié)結(jié)構(gòu)構(gòu)實(shí)實(shí)現(xiàn)現(xiàn) 特特 別別 適適 用用 于于 一一 經(jīng)經(jīng) 建建 立立 就就 很很少少 改改 動(dòng)動(dòng)

31、 又又 經(jīng)經(jīng) 常常 需需 要要 查查 找找 的的線線性性表表 分分塊塊查查找找 順順序序結(jié)結(jié)構(gòu)構(gòu) 鏈鏈表表 在在 表表 中中 插插 入入 或或 刪刪 除除記記 錄錄 時(shí)時(shí) 就就 只只 要要 在在 該該記記錄錄所所屬屬塊塊內(nèi)內(nèi)操操作作，因因 為為 塊塊 內(nèi)內(nèi) 記記 錄錄 的的 存存放放是是隨隨意意的的，所所以以插插入入和和刪刪除除比比較較容容易易 要要增增加加一一個(gè)個(gè)輔輔助助數(shù)數(shù)組組的的存存儲(chǔ)儲(chǔ)空空間間，并并要要進(jìn)進(jìn)行行將將初初始始表表分分塊塊排排序序運(yùn)運(yùn)算算 適適用用于于有有分分塊塊特特點(diǎn)點(diǎn)的的記記錄錄，如如 一一 個(gè)個(gè) 學(xué)學(xué) 校校 的的 學(xué)學(xué) 生生 登登 記記 表表可可按按系系號(hào)號(hào)或或班班號(hào)

32、號(hào)分分塊塊。 4748查找表查找表：用于頻繁進(jìn)行插入、刪除、查找的：用于頻繁進(jìn)行插入、刪除、查找的查找表。查找表。 特點(diǎn)：特點(diǎn)：表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成的。表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成的。 要求：要求：即對(duì)于給定值即對(duì)于給定值key，若表中存在其關(guān)鍵字，若表中存在其關(guān)鍵字等于等于key的記錄，則查找成功返回，否則插入關(guān)的記錄，則查找成功返回，否則插入關(guān)鍵字等于鍵字等于491定義：定義：二叉排序樹。二叉排序樹。 50（a）（b）練：下列練：下列2種圖形中，哪個(gè)不是二叉排序樹種圖形中，哪個(gè)不是二叉排序樹 ？-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：或是一棵空樹；或者是具有如下性質(zhì)

33、的非空二叉樹： （1 1）左子樹的所有結(jié)點(diǎn)均小于根的值；）左子樹的所有結(jié)點(diǎn)均小于根的值； （2 2）右子樹的所有結(jié)點(diǎn)均大于根的值；）右子樹的所有結(jié)點(diǎn)均大于根的值； （3 3）它的左右子樹也分別為二叉排序樹）它的左右子樹也分別為二叉排序樹。討論：討論：對(duì)左圖中序遍歷后的結(jié)果是什么？對(duì)左圖中序遍歷后的結(jié)果是什么？511222503001102009910523021612225030011020099105230216LNPEMCYLNPEMCY522. 2. 將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)：將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)： 查找過(guò)程與順序結(jié)構(gòu)有序表中的查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找折半

34、查找相似，查找效率高；相似，查找效率高； 中序遍歷中序遍歷此二叉樹，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（此二叉樹，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)即實(shí)現(xiàn)了排序運(yùn)算了排序運(yùn)算）；）； 如果查找不成功，能夠方便地將被查元素如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子插入到二叉樹的葉子結(jié)點(diǎn)結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。注：注：若若數(shù)據(jù)元素的數(shù)據(jù)元素的輸入順序不同，則得輸入順序不同，則得到的二叉排序樹形態(tài)也不同！到的二叉排序樹形態(tài)也不同！這種既查找又插入的過(guò)程稱為這種既查找又插入的過(guò)程稱為動(dòng)態(tài)查找動(dòng)態(tài)查找。二叉排序樹既有類似

35、于折半查找的特性，又采用了二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。一、二叉排序樹（二叉查找樹）一、二叉排序樹（二叉查找樹）533二叉排序樹的查找算法：二叉排序樹的查找算法：5412225030011020099105230216122250300110200991052302165556查找不成功查找不成功n注意：注意：5745452424535312129090如果待如果待查找的關(guān)鍵字序列輸入順序?yàn)椋翰檎业年P(guān)鍵字序列輸入順序?yàn)椋海?424，5353， 4545，4545，1212，2424，9090），），2

36、4245353454512129090查查找找成成功功，返返回回查查找找成成功功，返返回回討論討論1 1：二叉排序樹的插入和查找操作：二叉排序樹的插入和查找操作 則生成二叉排序則生成二叉排序樹的過(guò)程為：樹的過(guò)程為：例例：輸入待查找的關(guān)鍵字序列輸入待查找的關(guān)鍵字序列= =（4545，2424，5353，4545，1212，2424，9090）則生成的二叉排則生成的二叉排序樹形態(tài)不同：序樹形態(tài)不同：查查找找成成功功，返返回回查查找找成成功功，返返回回581222503001102809912212299122250991222501109912225030011099591222503001109

37、9Tp28012225030011099Tp2806012225030011099Tf：null12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=2806112225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280f12225030011099T:nullKey=280p12225030011099280p1222503001109928062仍然保仍然保持二叉排序樹的特性持二叉排序樹的特性1560703020506030205

38、01560703020506030205063641221222502503003001101102002009999105105230230216216400400450450500500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)122122250250300300200200230230216216400400450450500500110110105105刪除刪除刪除刪除99991221222502503003001101102002009999105105230230216216400400450450500500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)122122250250300300200200230230216216400400450450500500110110105105刪除刪除刪除刪除99996512225030011020099105230216400450500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)122250300230216400450500刪除刪除2001109910512225030011020099105230216400450500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)1222503002