資源描述：
《靜態(tài)搜索結(jié)構(gòu)動態(tài)搜索結(jié)構(gòu)散列可擴充散列簡介》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、靜態(tài)搜索結(jié)構(gòu)動態(tài)搜索結(jié)構(gòu)散列可擴充散列第十章搜索查找搜索搜索結(jié)構(gòu)同一數(shù)據(jù)類型（紀錄）的元素構(gòu)成的數(shù)據(jù)集合。搜索在數(shù)據(jù)集合中尋找滿足條件的對象（數(shù)據(jù)元素）。關(guān)鍵字數(shù)據(jù)元素中某個字段（數(shù)據(jù)項）的值。主關(guān)鍵字唯一地表示一個紀錄。次關(guān)鍵字標識若干紀錄搜索成功找到滿足條件的數(shù)據(jù)對象報告該對象在結(jié)構(gòu)中的位置給出整個紀錄的信息搜索失敗搜索不成功靜態(tài)搜索搜索結(jié)構(gòu)在搜索前后不發(fā)生變化動態(tài)搜索搜索的同時執(zhí)行插入或刪除結(jié)構(gòu)自行調(diào)整提高效率先排序，分類，編目，索引優(yōu)化結(jié)構(gòu)一、靜態(tài)搜索結(jié)構(gòu)基于數(shù)組的數(shù)據(jù)表類順序表——線性表、數(shù)組、鏈表。(1)
2、順序搜索從頭至尾逐個比較最快O(1)最慢O(n)搜索成功的等概率平均時間復雜性O(shè)((n+1)/2)(1+2+3+······+n)/n=(n+1)/2搜索失敗O(n+1)搜索的等概率平均時間復雜性O(shè)(3(n+1)/4)搜索成功失敗各半((1+2+······+n)+n(n+1))/2n=3(n+1)/4(2)有序表的搜索折半搜索對已排序的搜索結(jié)構(gòu)先確定中點，比較待查關(guān)鍵字與中點關(guān)鍵字的大小，反復直到成功。求n個數(shù)據(jù)折半查找的等概率成功搜索的平均時間復雜性1234567891012233334441+2*2+4*3+3
3、*4=29O(29/10)S=1+2*2+4*3+8*4+······+2k-1*k=1+2*2+3*4+4*8+······+k*2k-1ks=∑j·2j-1其中n=2k-1j=11223333444滿二叉樹n個數(shù)據(jù)的總查找次數(shù)：44444滿二叉樹n個數(shù)據(jù)的總查找次數(shù)：ks=∑j·2j-1其中n=2k-1j=1S=1+2·2+3·4+4*8+5*16+·····+k·2k-1=1+2+4+8+16+···+2k-1+2+2·4+3·8+4·16+····+(k-1)·2k-1=1+2+4+8+16+···+2k-1
4、+2·(1+2·2+3·4+4*8+5*16+·····+(k-1)·2k-2)=1+2+4+···+2k-1+2·(1+2+4+···+2k-2)+22·(1+2+4+···+2k-3)+·····+2k-2·(1+2)+2k-1=2k-1+2·(2k-1-1)+22·(2k-2-1)+·····+2k-2·(22-1)+2k-1(2-1)=k·2k-(1+2+4+···+2k-1)=k·2k-(2k-1)=(k-1)·2k+1滿二叉樹n個數(shù)據(jù)的總查找次數(shù)：ks=∑j·2j-1其中n=2k-1j=1令s=f(k),
5、k=1,2,3,4,······f(1)=1f(2)=5f(3)=17f(4)=49f(5)=129·······f(k)-1=0,22,24,3·24，27，······=0·21,1·22,2·23,3·24，4·25·····猜想f(k)-1=(k-1)·2kkf(k)=s=∑j·2j-1其中n=2k-1j=1f(k)-1=(k-1)2k證明1)f(1)-1=02)f(k+1)-1=f(k)+(k+1)·2k–1=(k-1)2k+(k+1)·2k=2·k·2k=k·2k+1=(k+1-1)·2k+1S=(k-1
6、)2k+1滿二叉樹n個數(shù)據(jù)的總查找次數(shù)：ks=∑j·2j-1其中n=2k-1j=1S=(k-1)·2k+1由n=2k-1得k=log2(n+1)S=(n+1)(log2(n+1)-1)+1=(n+1)log2(n+1)-n滿二叉樹n個數(shù)據(jù)的搜索成功平均概率時間復雜性((n+1)/n)log2(n+1)-1當n>50時近似于log2(n+1)-1n個元素的折半搜索2k-1≤n<2k+1-1搜索成功平均概率時間復雜性介于log2(2k)-1和log2(2k+1)-1之間即k-1和k之間k=[log2(n+1)]n個元素的
7、折半搜索成功平均概率時間復雜性log2(n+1)-1/2斐波那契搜索根據(jù)斐波那契序列的特點對有序表分割0.618法斐波那契序列1235813213455······f(n)······f(n+2)=f(n)+f(n+1)從20個數(shù)的數(shù)表中查找一個紀錄先找比較第13個，如果小，再比較第8個，····如果大比較后幾個數(shù)的第5個······每次都比較位于這個數(shù)列的黃金分割點0.618處以下序列中查找元素10的過程123456789101112131415平均查找性能優(yōu)于折半查找O(log2n)最壞情況比折半查找差（3）靜態(tài)
8、樹表的搜索不等概率查找時折半查找不一定好，以每點查找次數(shù)（概率）為這點的權(quán)wi帶權(quán)二叉樹總路徑長度PH=∑wihiiPH最小的二叉樹叫靜態(tài)最優(yōu)二叉樹不同于霍夫曼樹：每個結(jié)點都有權(quán)值，都要查找。ECAGBDHFI545112343ABCDEFGHI112534435PH=3·1+2·2+2·4+1·3+5·3+4·3+3·3+1·4+5·4=78
