數(shù)據(jù)結(jié)構(gòu)c語言版第八章 查找

1、第八章第八章查找查找重點(diǎn)難點(diǎn)重點(diǎn)難點(diǎn)要求理解“查找表“的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性；熟練掌握順序查找和折半查找的方法；熟悉描述折半查找過程的判定樹的構(gòu)造方法；熟練掌握二叉排序樹的構(gòu)造和查找方法；理解二叉平衡樹的構(gòu)造過程；理解B和B樹的特點(diǎn)、基本操作和二者的區(qū)別。熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別；掌握各種不同查找方法之間的區(qū)別和各自的適用情況，能按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均

2、查找長度。典型例題典型例題1.若對(duì)具有n個(gè)元素的有序的順序表和無序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長度：(1)查找不成功，即表中無關(guān)鍵字等于給定值K的記錄；(2)查找成功，即表中有關(guān)鍵字等于給定值K的記錄?！窘狻坎檎也怀晒r(shí)，需進(jìn)行n1次比較才能確定查找失敗。因此平均查找長度為n1，這時(shí)有序表和無序表是一樣的。查找成功時(shí)，平均查找長度為(n1)2有序表和無序表也是一樣的。因?yàn)轫樞虿檎遗c表的初始

3、序列狀態(tài)無關(guān)。2.畫出對(duì)長度為18的有序的順序表進(jìn)行二分查找的判定樹，并指出在等概率時(shí)查找成功的平均查找長度，以及查找失敗時(shí)所需的最多的關(guān)鍵字比較次數(shù)?！窘狻康雀怕是闆r下，查找成功的平均查找長度為：ASL=(122344853)18=3.556查找失敗時(shí)，最多的關(guān)鍵字比較次樹不超過判定樹的深度，此處為5.3.為什么有序的單鏈表不能進(jìn)行折半查找├──┤6│∧│├──┤7│∧│├──┤8│∧│├──┤9│∧│├──┤10│∧│└──┘(2)

4、線性探查法如下圖：下標(biāo)012345678910┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐T[0..10]│33│1│13│12│34│38│27│22││││└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘探查次數(shù)11134178用拉鏈法的查找成功平均查找長度為：ASLsucc=(142331)8=1.625查找失敗時(shí)平均查找長度為：ASLunsucc=(23100020000)11=0.73用線性探查法查找成功時(shí)平均查找長度為：AS

5、Lsucc=(11134178)8=3.25查找失敗時(shí)平均查找長度為：ASLunsucc=(98765432111)11=4.3裝填因子α拉鏈=411=0.36α線性探查=811=0.737.試寫一算法判別給定的二叉樹是否為二叉排序樹，設(shè)此二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不相同?！窘狻坑啥媾判驑涞亩x可得：二叉排序樹中左子樹的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，所有右子樹中結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。那么只要對(duì)待判定的二叉樹中