提升篇課件提高第7章

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

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

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

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

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

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

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

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

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