【正文】 ? 靜態(tài)搜索結(jié)構(gòu) ? 動態(tài)搜索結(jié)構(gòu) ? 散列 ? 可擴充散列 查找 搜索 搜索結(jié)構(gòu) 同一數(shù)據(jù)類型（紀(jì)錄）的元素 構(gòu)成的 數(shù)據(jù)集合。 搜索 在數(shù)據(jù)集合中 尋找 滿足條件的對 象（數(shù)據(jù)元素）。 關(guān)鍵字 數(shù)據(jù)元素中某個字段（ 數(shù)據(jù)項 ） 的值。 主關(guān)鍵字 唯一地表示一個紀(jì)錄 。 次關(guān)鍵字 標(biāo)識若干紀(jì)錄 搜索成功 找到 滿足條件的數(shù)據(jù) 對象 報告 該對象在結(jié)構(gòu)中的 位置 給出 整個 紀(jì)錄 的信息 搜索失敗 搜索不成功 靜態(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) 順序搜索 從頭至尾逐個比較 最快 O(1) 最慢 O(n) 搜索成功的 等概率平均時間復(fù)雜性 O((n+1)/2) (1+2+3++n) /n=(n+1)/2 搜索失敗 O(n+1) 搜索的等概率平均時間復(fù)雜性 O(3(n+1)/4) 搜索成功失敗各半 ((1+2++n)+n(n+1)) /2n =3(n+1)/4 (2)有序表的搜索 折半搜索 對已排序的搜索結(jié)構(gòu)先確定中點，比較待查關(guān)鍵字與中點關(guān)鍵字的大小，反復(fù)直到成功。 求 n個數(shù)據(jù)折半查找的等概率成功搜索的平均時間復(fù)雜性 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 3 3 4 4 4 1+2*2+4*3+3*4=29 O(29/10) S=1+2*2+4*3+8*4++2k1*k = 1+2*2+3*4+4*8++k*2k1 k s =∑j2j1 其中 n=2k1 j=1 1 2 2 3 3 3 3 4 4 4 滿二叉樹 n個數(shù)據(jù)的總查找次數(shù)： 4 4 4 4 4 滿二叉樹 n個數(shù)據(jù)的總查找次數(shù)： k s =∑j2j1 其中 n=2k1 j=1 S=1+22+34+4*8+5*16++k2k1 = 1+2+4+8+16++2k1+ 2+24+38+416++(k1)2k1 = 1+2+4+8+16++2k1+ 2(1+22+34+4*8+5*16++(k1)2k2) = 1+2+4++2k1+2(1+2+4++2k2)+ 22(1+2+4++2k3)++2k2(1+2)+2k1 =2k1+2(2k11)+22(2k21)++2k2(221)+ 2k1(21) =k2k(1+2+4++2k1)=k2k(2k1)=(k1)2k+1 滿二叉樹 n個數(shù)據(jù)的總查找次數(shù)： k s =∑j2j1 其中 n=2k1 j=1 令 s=f(k), k=1,2,3,4, f(1)=1 f(2)=5 f(3)=17 f(4)=49 f(5)=129 f(k)1= 0, 22, 24, 324， 27， = 021, 122, 223, 324， 425 猜想 f(k)1=(k1)2k k f(k)= s =∑j2j1 其中 n=2k1 j=1 f(k)1=(k1)2k 證明 1) f(1)1=0 2) f(k+1)1=f(k)+(k+1)2k –1 = (k1)2k+ (k+1)2k =2k2k=k2k+1 =(k+11)2k+1 S=(k1)2k+1 滿二叉樹 n個數(shù)據(jù)的總查找次數(shù)： k s =∑j2j1 其中 n=2k1 j=1 S= (k1)2k+1 由 n=2k1 得 k=log2(n+1) S=(n+1)(log2(n+1)1)+1 = (n+1)log2(n+1)n 滿二叉樹 n個數(shù)據(jù)的搜索成功平均概率時間復(fù)雜性 ((n+1)/n) log2(n+1)1 當(dāng) n50時 近似于 log2(n+1)1 n個元素的折半搜索 2k1≤n2k+11 搜索成功平均概率時間復(fù)雜性 介于 log2(2k)1 和 log2(2k+1)1 之間 即 k1 和 k 之間 k=[log2(n+1)] n個元素的折半搜索成功平均概率時間復(fù)雜性 log2(n+1)1/2 斐波那契搜索 根據(jù) 斐波那契序列的特點對有序表分割 斐波那契序列 1 2 3 5 8 13 21 34 55f(n) f(n+2)=f(n)+f(n+1) 從 20個數(shù)的數(shù)表中查找一個紀(jì)錄 先找比較第 13個，如果小，再比較第 8個， 如果大 比較后幾個數(shù)的第 5個