【正文】 查找第 k層的記錄需要 k次比較 （ 這樣的記錄共有 2k1個 ） 。查找的關(guān)鍵字 K=21 第一步：這里的 n=11,mid=(1+11)/2=6 05， 13， 19， 21， 37， 56， 64， 75， 80， 88， 92 low? mid? high? 第 八 章 查 找 第二步： mid=(1+5)/2=3 05， 13， 19， 21， 37， 56， 64， 75， 80， 88， 92 low? mid? high?第三步： mid=(4+5)/2=4 05， 13， 19， 21， 37， 56， 64， 75， 80， 88， 92 此時 R[mid].key＝ K， return mid＝ 4。 ? 二分查找要求 ：要求線性表是 有序表 ，即表中結(jié)點按關(guān)鍵字有序，并且要用 向量作為表的存儲結(jié)構(gòu) 。i)； /*從表后往前找 */ return i； /*若 i為 0，表示查找失敗，否則 R[i]為要找的結(jié)點 */ } /*SeqSearch*/ 第 八 章 查 找 算法分析 查找 成功時的 順序查找 的平均查找長度： 在等概率情況下， pi=1/n(1≤i≤n) ，故成功的平均查找長度為 ASL= =(n+… +2+1)/n=(n+1)/2 即查找成功時的平均比較次數(shù)約為表長的一半。而對于查找算法，執(zhí)行的時間通常取決于關(guān)鍵字的比較次數(shù)，所以本章經(jīng)常用平均比較次數(shù)，即 平均查找長度 ASL（ Average Search Length） 第 八 章 查 找 其中： n是結(jié)點的個數(shù)； Pi是查找第 i個結(jié)點的概率。若找到，則查找成功，返回該記錄的信息或該記錄在表（文件）中的位置；否則查找失敗，返回相關(guān)的指示信息。 第 八 章 查 找 若在查找的同時對表做修改操作（如插入和刪除等），則相應(yīng)的表稱之為 動態(tài)查找表 （ Dynamic Search Table）。若不特別聲明 ，認(rèn)為每個結(jié)點的查找概率相等，即 pl = p2…… = pn = 1/n ci是找到第 i個結(jié)點所需進(jìn)行的比較次數(shù) ASL= ??niiicp1平均查找長度 ASL（ Average Search Length）定義為 ： 第 八 章 查 找 一、順序查找 (Sequential Search) 基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點關(guān)鍵字和給定值 K相比較。 ??niiicp1 第 八 章 查 找 順序查找的缺點 查找效率低。不妨設(shè)有序表是遞增有序的。 low? high?mid? 第 八 章 查 找 二分查找算法 int BinSearch(SeqList R， KeyType K) { int low=1， high=n， mid； while(low=high) { mid=(low+high)/2； /*求中間位置 */ if(R[mid].key==K) return mid； if(R[mid].keyK) high=mid1。等等 。 二分查找 只適用順序存儲結(jié)構(gòu) 。 第 八 章 查 找 分塊查找表由 分塊有序 的線性表和索引表組成。 分塊查找表的存儲結(jié)構(gòu) 第 八 章 查 找 分塊查找的基本思想是： （ 1）首先查找索引表 索引表是有序表 ， 可采用二分查找或順序查找， 以確定待查的結(jié)點在哪一塊 。 即首先將 K依次和索引表中各關(guān)鍵字比較 ， 直到找到第 1個關(guān)鍵字大小等于 K的結(jié)點 ， 由于 K48， 所以關(guān)鍵字為 24的結(jié)點若存在的話 ， 則必定在第二塊中；然后 ， 由ID[2].addr找到第二塊的起始地址 7， 從該地址開始在R[7..12]中進(jìn)行順序查找 ， 直到 R[11].key=K為止 。整個查找過程的平均查找長度是兩次查找的平均查找長度之和。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹： （ 1）若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值； （ 2）若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值； （ 3）左、右子樹本身又各是一棵二叉排序樹 。 二叉排序樹的特點 第 八 章 查 找 要查找鍵值等于 k的記錄，最先與根 結(jié)點的鍵值比較，若二者相等，則查找成功 。其 插入過程是： 1)若二叉排序樹 T為空，則為待插入的關(guān)鍵字 key申請一個新結(jié)點，并令其為根； 2)若二叉排序樹 T不為空，則將 key和根的關(guān)鍵字比較： (a)若二者相等，則說明樹中已有此關(guān)鍵字 key，無須插入。 } 第 八 章 查 找 p=(BSTNode*)malloc(sizeof(BSTNode))； pkey=key； plchild=prchild=NULL； if(TPtr==NULL) /*是空樹 */ Tptr=p； /*新結(jié)點作為根插入 */ else /*不是空樹 */ if(keyfkey) flchild=p； /*新結(jié)點作為左孩子插入 */ else frchild=p； /*新結(jié)點作為右孩子插入 */ } 第 八 章 查 找 從空的二叉排序樹開始，每輸入一個結(jié)點數(shù)據(jù)，就調(diào)用一次插入算法將它插入到當(dāng)前已生成的二叉排序樹中。key)； /*輸入一個鍵值為 key的結(jié)點 */ } return T； } 第 八 章 查 找 輸入實例 (5， 3， 7， 2， 4， 8)，根據(jù)生成二叉排序樹算法 生成二叉排序樹的過程 5 5 3 2 5 3 7 5 3 7 2 5 3 7 4 2 5 3 7 4 8 第 八 章 查 找 二叉排序樹的刪除 從二叉排序樹中刪除一個結(jié)點，不能把以該結(jié)點為根的子樹都刪去，并且還要保證刪除后所得的二叉樹仍然滿足 BST性質(zhì)。 *p 應(yīng)將 *p的子樹 (若有 )仍連接在樹上且保持 二叉排序樹的 性質(zhì)不變 F P C PR CL Q QL SL S 堅持的基本原則： 刪結(jié)點時，保證二叉排序樹的性質(zhì)不變。 } *p只有一個子樹的情況 ： 第 八 章 查 找 中序遍歷： P PR S Q S PR Q 中序遍歷： PR S Q (3) S P PR Q 中序遍歷： Q S P PR S Q PR 中序遍歷： Q S PR (4) S Q PR P 2.*p只有右子樹，用 *p的右子樹的根代替 *p if(!plchild){ /左子樹空則只需重接它的右子樹 tmp=p。 第②種情況 。 第 八 章 查 找 S F P C PR CL Q QL SL F P C PR CL Q QL SL S tmp=plchild。 p=plchild。amp。 (c)插入、刪除和查找算法的時間復(fù)雜度均為 O(log2n)。當(dāng)有序表是靜態(tài)查找表時，宜用向量作為其存儲結(jié)構(gòu)，而采用二分查找實現(xiàn)其查找操作； 若有序表是動態(tài)查找表，則應(yīng)選擇二叉排序樹作為其存儲結(jié)構(gòu)。顯然，若 m越大，則 B樹高度越小。實際發(fā)生 (即實際存儲 )的關(guān)鍵字集合記為 K（ |K|比 |U|小得多）。 散列表 (Hash Table) 第 八 章 查 找 其中： ① 稱 h為 散列函數(shù) (Hash Function)。 ④ 將結(jié)點按其關(guān)鍵字的散列地址存