提升篇課件提高第7章

1、主講人第1章緒第5章樹主講人第1章緒第5章樹和二叉第2章線性第6章第3章棧和隊(duì)列第7章查找第4章串、數(shù)組和廣義第8章排第7章查找第7章查找板塊一：本章基礎(chǔ)板塊一：本章基礎(chǔ)鞏固7.1 查找的基本概查找表由同一類型的數(shù)7.1 查找的基本概查找表由同一類型的數(shù)據(jù)元素（靜態(tài)查找表）的集查找的同時(shí)對(duì)查找表不做修改操作（動(dòng)態(tài)查找表查找的同時(shí)對(duì)查找表具有修改操和刪除中某個(gè)數(shù)據(jù)項(xiàng)的中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別唯一標(biāo)識(shí)數(shù)據(jù)元可以標(biāo)識(shí)若干個(gè)數(shù)據(jù)元關(guān)鍵字的平均比較次數(shù)，也稱平均搜關(guān)鍵字的平均比較次數(shù)，也稱平均搜索長(zhǎng)度ASL(Average Search SL 的個(gè)的概率 (通常認(rèn)為pi =1/n) 線性表的查一、順

2、序查找（線性查找線性表的查一、順序查找（線性查找應(yīng)用范圍順序表或線性鏈表表示的靜態(tài)查表內(nèi)應(yīng)用范圍順序表或線性鏈表表示的靜態(tài)查表內(nèi)間無順序表的表typedefstruct*R;/表基第2章在順序表L中查找值為eLocateELem(SqListL,ElemTypee) for (i=0;i L.length;i+)if(L.elemi=e)returnreturn改進(jìn)：把待查關(guān)鍵字key存入表頭（“哨兵”），第2章在順序表L中查找值為eLocateELem(SqListL,ElemTypee) for (i=0;i L.length;i+)if(L.elemi=e)returnreturn改進(jìn)：

3、把待查關(guān)鍵字key存入表頭（“哨兵”），空間復(fù)雜度：一個(gè)輔助空間時(shí)間復(fù)雜度查找成功時(shí)的平空間復(fù)雜度：一個(gè)輔助空間時(shí)間復(fù)雜度查找成功時(shí)的平均查找長(zhǎng)設(shè)表中查找概率相2算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)絥很算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)絥很大時(shí)查找效率較改進(jìn)措施：非等概率查找時(shí)，可按照行排序練習(xí):判斷對(duì)查找概率相等時(shí)，ASL相同查找概率不等時(shí)，如果從前向后查找，則按查找概率由大到小排列的有序表其L要比無序表L小。n個(gè)數(shù)練習(xí):判斷對(duì)查找概率相等時(shí)，ASL相同查找概率不等時(shí)，如果從前向后查找，則按查找概率由大到小排列的有序表其L要比無序表L小。n個(gè)數(shù)存在一維數(shù)組A1.n中，在進(jìn)行順序查找

4、時(shí)這n個(gè)數(shù)的排列有序或無序其平均查找長(zhǎng)度ASL不同折半查找（非遞歸算法設(shè)表長(zhǎng)為n，low、high和mid中點(diǎn),k初始時(shí)，令讓k與mid若k=Rmid.key若kRmid.key，則重復(fù)上述操作，直至lowhigh折半查找（非遞歸算法設(shè)表長(zhǎng)為n，low、high和mid中點(diǎn),k初始時(shí)，令讓k與mid若k=Rmid.key若kRmid.key，則重復(fù)上述操作，直至lowhigh【算法描述】-算法【算法描述】-算法折半查找（遞歸算法if(lowhigh)return/折半查找（遞歸算法if(lowhigh)return/查找不到時(shí)返回if(key等于emmid.key) returnelse if

5、(key小于else. /遞歸查找過程：每次將待所在區(qū)間比順序查查找過程：每次將待所在區(qū)間比順序查找效率高,時(shí)間復(fù)雜度O(log2 適用條件：采用順于鏈?zhǔn)浇Y(jié)結(jié)構(gòu)的有序表一塊中數(shù)值?。ê總€(gè)子表的起始地址（即頭指針）索引17第2第3第189一塊中數(shù)值?。ê總€(gè)子表的起始地址（即頭指針）索引17第2第3第189 對(duì)索引表使用折半查找法（ 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順查找法（因?yàn)楦魇菬o序表查找效率對(duì)索引表查找的對(duì)塊內(nèi)查找的 n1)n查找效率對(duì)索引表查找的對(duì)塊內(nèi)查找的 n1)n s) 2ASLbs log(log2n 2個(gè)數(shù)，n/s即塊的數(shù)S

6、的優(yōu)點(diǎn)和刪除比較容易，無需進(jìn)行優(yōu)點(diǎn)和刪除比較容易，無需進(jìn)行大量移動(dòng)缺點(diǎn)：要增加一個(gè)索引空間并對(duì)初始索引表進(jìn)行排序運(yùn)適用情況：如果線性表既要快速查找又經(jīng)常動(dòng)態(tài)變化，則可采用分塊找7.3表結(jié)構(gòu)在查找過程中動(dòng)態(tài)7.3表結(jié)構(gòu)在查找過程中動(dòng)態(tài)生對(duì)于給定值若表中存在，則成功返回否關(guān)鍵字等于的二叉排序樹或是空樹，或是滿足如下性質(zhì)的二叉(1非空，則上所有結(jié)點(diǎn)的值均于根結(jié)點(diǎn)的值(2二叉排序樹或是空樹，或是滿足如下性質(zhì)的二叉(1非空，則上所有結(jié)點(diǎn)的值均于根結(jié)點(diǎn)的值(2非空，則上所有結(jié)點(diǎn)的值均于等于根結(jié)點(diǎn)的值(3本身又各是一棵二叉排序】（1）（2）若二叉排序樹非空，將給定值key字T-data.key進(jìn)行比較】（1

7、）（2）若二叉排序樹非空，將給定值key字T-data.key進(jìn)行比較 若key小于T-data.key，則進(jìn)一步；key大于T-data.key，則進(jìn)一步。平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)最好：log平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似:（n+1)/2（單支樹是平衡二叉樹平衡因子:該結(jié)點(diǎn)深度之差的絕1與是平衡二叉樹平衡因子:該結(jié)點(diǎn)深度之差的絕1與的高度練習(xí)：判斷下列二叉樹是否AVL2-010100練習(xí)：判斷下列二叉樹是否AVL2-010100100如果在一棵AVL一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)如果在一棵AVL一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)重新

8、調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)轉(zhuǎn)LL稱調(diào)整平衡過程為保證二叉排序的次序不RRLRRL哈希表的查：的哈希函優(yōu)點(diǎn)：查找哈希表的查：的哈希函優(yōu)點(diǎn)：查找速度極快O(1),查找效率與元素個(gè)數(shù)n哈希表的查哈希表的查例若將學(xué)生信息按如下方式存入計(jì)算機(jī)將2001011810201的所有信息存入V01例若將學(xué)生信息按如下方式存入計(jì)算機(jī)將2001011810201的所有信息存入V01單元將2001011810202的所有信息存入V02單元將2001011810231的所有信息存入V31單元查找2001011810216的信息，可直例數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k地址H（k）k，請(qǐng)畫9例

9、數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k地址H（k）k，請(qǐng)畫99根據(jù)哈希函數(shù)查找key=9,H(9)=9號(hào)地址，若內(nèi)容為9則成功若查不到，則9根據(jù)哈希函數(shù)查找key=9,H(9)=9號(hào)地址，若內(nèi)容為9則成功若查不到，則返回一個(gè)特殊值，如空。已知一組關(guān)鍵字13, 哈希表長(zhǎng)為已知一組關(guān)鍵字13, 哈希表長(zhǎng)為(1，即m2345678911121431139113，H1=(1+1)(1，即m2345678911121431139113，H1=(1+1)0123456789101234567891關(guān)鍵字無序表查找有序關(guān)鍵字無序表查找有序表折半查找使用平均查找長(zhǎng)度ASL來衡量查找算法，ASL表中填入的數(shù) 的哈