[其它]數(shù)據(jù)結(jié)構(gòu)第9章(編輯修改稿)
2024-11-14 22:27 本頁面
【文章內(nèi)容簡(jiǎn)介】 ? ? ? ????折半查找成功時(shí)的平均查找長(zhǎng)度 ASL 假定表的長(zhǎng)度 n=2h1，則相應(yīng)判定樹必為深度是 h的滿二叉樹，h=log2(n+1)。又假設(shè)每個(gè)記錄的查找概率相等， 則折半查找成功時(shí)的平均查找長(zhǎng)度為： 當(dāng) n較大 (n50)時(shí)，有近似結(jié)果： 2l og ( 1 ) 1bsA SL n? ? ? 25 10 30 2 15 28 35 3 20 29 40 311 44342211A S L s u c c ＝＝ ???????折半查找判定樹 (1)在查找成功時(shí) ,會(huì)找到圖中某個(gè)圓形結(jié)點(diǎn) ,則成功時(shí)的平均查找長(zhǎng)度： (2)在查找不成功時(shí) ,會(huì)找到圖中某個(gè)方形結(jié)點(diǎn) ,則不成功時(shí)的平均查找長(zhǎng)度： 4834A S L u n s u c c ＝＝ ??? (分塊查找 ) 是一種性能介于順序查找和折半查找之間的查找方法 。 將表 [1..n]均分為 b塊 ,前 b1塊中記錄個(gè)數(shù)為 s=?n/b?,最后一塊即第 b塊的記錄數(shù)小于等于 s；表是 “ 分塊有序 ” 的； 索引表是一個(gè)遞增有序表 。 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 22 12 B1 B2 B3 22 1 48 7 86 13 最大關(guān)鍵字 起始地址(下標(biāo) ) 索引表 LB：查找索引表的 ASL； LW ： 塊內(nèi)進(jìn)行順序查找的 ASL。 ASLbs=LB+LW b塊 ， 每塊含 s個(gè)元素 。 查找概率相等 ， 則每個(gè)索引項(xiàng)的查找概率為 1/b， 塊中每個(gè)元素的查找概率為 1/s。 ?若用順序查找法確定待查元素所在的塊 ， 則有 111 1 11 ( ) 122bsb s B Wjib s nA S L L L j i sb s s???? ? ? ? ? ? ? ? ???21l o g211)1(l o g22ssnsbA S Lbs ??????? ????????若用折半查找法確定待查元素所在的塊，則有 ?靜態(tài)查找表的三種查找方法的比較 ? 順序查找對(duì)對(duì)于表有序、無序均適用；折半查找僅適用于有序表；分塊查找要求表分塊后“分塊有序”。 ? 從表的存儲(chǔ)結(jié)構(gòu)上看，順序查找和分塊查找對(duì)于表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用，而折半查找只適用于順序存儲(chǔ)結(jié)構(gòu)。 ? 平均查找長(zhǎng)度 ASL而言，折半最?。?log2(n+1)1），分塊次之，當(dāng) 時(shí)（ ），順序最大（ (n+1)/2）。 1n?sn? 動(dòng)態(tài)查找表 動(dòng)態(tài)查找表的特點(diǎn) ：表結(jié)構(gòu)本身在查找過程中動(dòng)態(tài)生成，即對(duì)于 給定值 key，若表中存在關(guān)鍵字等于 key的記錄，則查找成功，否 則插入關(guān)鍵字等于 key的記錄。 二叉排序樹、 平衡二叉排序樹和 B樹等。 動(dòng)態(tài)查找表的主要運(yùn)算 ?創(chuàng)建 、 銷毀 ?查找 、 插入和刪除 ?遍歷 1. 二叉排序樹 BST (Binary Sort Tree) 的定義 (二叉檢索樹、二叉查找樹 ) 或者是一棵空樹 ， 或者是具有如下性質(zhì)的二叉樹： (1)若它的左子樹不空 ， 則左子樹上所有結(jié)點(diǎn)的值 均小于 根結(jié)點(diǎn)的值； (2)若它的右子樹不空 ， 則右子樹上所有結(jié)點(diǎn)的值 均大于 根結(jié)點(diǎn)的值； (3)它的左右子樹也分別為二叉排序樹。 二叉排序樹示例 typedef struct BiTNode{ /*記錄類型 */ KeyType key。 /*關(guān)鍵字項(xiàng) */ InfoType data。 /*其他數(shù)據(jù)域 */ struct BiTNode *lchild,*rchild。 /*左右孩子指針 */ } BiTNode, *BiTree。 45 12 53 3 37 100 90 24 61 78 CAO ZHAO DING CHEN WANG LI XIA DU MA 2. 二叉排序樹上的查找 二叉排序樹可看做是一個(gè)有序表 ， 在二叉排序樹上進(jìn)行查找 ,和折半查找類似 ,也是一個(gè)逐步縮小查找范圍的過程 。 BiTree SearchBST(BiTree T, KeyType key) { if (!T || key==Tkey) /*遞歸終結(jié)條件 */ return T。 else if (key Tkey) return SearchBST(Tlchild, key)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1