【文章內(nèi)容簡介】 的查找 遞歸算法 int bisrch1(rectp r[],keytp k,int l, int h)。 參數(shù) r表示有序查找表 ， 參數(shù) k表示指定的關(guān)鍵字 ,l,h分別表示查找范圍的下界 ， 上界 。 功能：在有序表 r中若存在關(guān)鍵字等于 k的記錄 ， 則返回該記錄在有序表中的序號 ， 否則返回值為 0。 處理過程： （ 1） 若 lh,則返回 0， 否則： （ 2） 求中項 m=(l+h)/ 2。將指定值 k與中項的關(guān)鍵字值進行比較 ， 若相等則返回中項的序號 m； 若小于則查找上部即以 （ r,k,l,m1） 為參數(shù)遞歸地調(diào)用本過程；若大于則查找下部即以 （ r,k,m+1,h） 為參數(shù)遞歸地調(diào)用本過程 。 57 二分查找遞歸函數(shù) 程序代碼 int bisrch1(rectp r[],keytp k,int l, int h) {int m。 if (lh) return(0)。 else { m=(l+h)/ 2。 if (k==r[m].key ) return(m)。 else if (kr[m].key) return(bisrch1(r,k,l,m1))。 else return(bisrch1(r,k,m+1,h))。 }。 }。 58 二分查找遞歸函數(shù) 執(zhí)行實例： 假設(shè) n=11,有序查找表中的關(guān)鍵字序列為： 5 13 19 21 37 56 64 75 80 88 92 則使用上述遞歸算法分別查找 k=21,k=22的遞歸調(diào)用過程及執(zhí)行結(jié)果如下： 對于 k=21： bisrch（ r,k,1,11） bisrch（ r,k,1,5） bisrch（ r,k,4,5） 返回 4 對于 k=22： bisrch（ r,k,1,11） bisrch（ r,k,1,5） bisrch（ r,k,4,5） bisrch（ r,k,5,5） bisrch（ r,k,5,4） lh,返回 0 59 靜態(tài)樹表的查找 判定樹 通常稱描述查找過程的二叉樹為判定樹 。 樹中的每個結(jié)點表示查找表中的一個記錄 ， 結(jié)點中的值為該記錄在表中的位置序號 。 3 1 4 2 5 3 1 4 2 5 60 判定樹與帶權(quán)路徑長度 PH PH＝ *2 + *3 + *1 + *2 + *3 = PH＝ *3 + *2 + *3 + *1 + *2 = 3 1 4 2 5 3 1 4 2 5 4 2 5 3 1 ??niiihwPH1＝61 靜態(tài)樹表的查找 最優(yōu)查找樹 對于一個有序的查找序列 (r1, r2,…… , rn), 其各結(jié)點中的權(quán)值為 (w1, w2,…… , wn)， 構(gòu)造一棵二叉 (判定 )樹 ， 其各結(jié)點的路徑長度即層次數(shù)為 (h1, h2,…… , hn), 如果 PH的值最小 ， 則該二叉樹稱為最優(yōu)查找樹 。 62 靜態(tài)樹表的查找 次優(yōu)查找樹 可以使用一種既非常近似又非常有效的算法構(gòu)造成一棵二叉樹 ,其 PH的值近似地達到最小 。 這種二叉樹稱為 次優(yōu)查找樹 . 次優(yōu)查找樹的構(gòu)造方法 : 設(shè)有序序列為 (rl, rl+1,…… , rh), 結(jié)點中的權(quán)值為 (wl, wl+1,…… , wh)， 在有序序列中取第 i（ l=i=h） 號元素 ， 使 比其它各點都小 。 將 i號元素作為根 ， 然后對左右二邊的子序列以同樣的方法構(gòu)造左右子樹 。 ?????????11iljjnijji WWP63 靜態(tài)樹表的查找 次優(yōu)查找樹 Δ Pi表示第 i號元素左右兩邊的權(quán)值之和的差的絕對值 。Δ Pi 最小 ， 即為左右兩邊的權(quán)值之和的差的絕對值最小 ，或為左右兩邊的權(quán)值之和相差最小 。 例如有序序列中有9個元素 ， 其權(quán)值依次為 1,1,2,5,3,4,4,3,5。則每一個元素的 Δ Pi如下所示 。 23 15 8 0 7 15 22 25 27 ?pj 5 3 4 4 3 5 2 1 1 wj 9 8 7 6 5 4 3 2 1 j 64 靜態(tài)樹表的查找 次優(yōu)查找樹 實現(xiàn)技巧 : 為了計算 Δ Pi 使用一個數(shù)組 sw[0..n]存放累計權(quán)值之和 然后依次求 Δ Pi＝ | (swh + swl1 ) – swi – swi1 | 5 3 4 4 3 5 2 1 1 wj 23 15 8 0 7 15 22 25 27 ?pj 28 23 20 16 12 9 4 2 1 swj 9 8 7 6 5 4 3 2 1 j 65 靜態(tài)樹表的查找 次優(yōu)查找樹生成實例 23 15 8 0 7 15 22 25 27 ?pj F 樹根 7 1 8 9 1 6 9 11 ?pj H D 樹根 0 0 0 2 1 3 ?pj I G E B 樹根 0 0 ?pj 5 3 4 4 3 5 2 1 1 wj C A 樹根 28 23 20 16 12 9 4 2 1 swj 9 8 7 6 5 4 3 2 1 j 66 靜態(tài)樹表的查找 次優(yōu)查找樹生成實例 5 3 4 4 3 5 2 1 1 I H G F E D C B A F D H I G E B C A 67 索引順序表 結(jié)構(gòu)特點 ? 分塊、塊間有序、塊內(nèi)無序 ? 建立索引表，其每個表項都與一個分塊相對應(yīng)，其內(nèi)容包括該分塊的起始序號以及分塊中的最大關(guān)鍵字。因此索引順序表由順序表與索引表二部分組成。 53 86 49 74 58 60 48 24 38 44 42 33 20 9 8 13 12 22 13 7 1 86 48 22 68 索引順序表 查找過程： 第一步是查找索引表 ， 以確定指定值 K落在那個分塊中 ，即確定 K所對應(yīng)的分塊的開始序號 。 由于索引表中的關(guān)鍵字是有序的 ， 因此查找索引表可采用順序查找法或二分查找法 。 第二步是查找順序表 ， 即在分塊中查找以確定在查找表中是否能找到關(guān)鍵字等于指定值的記錄 。 由于塊內(nèi)元素的關(guān)鍵字是無序的 ， 因此這一步只能采用順序查找法 。 例如：指定值 K＝ 38， 先查索引表 ， 確定必落在第二塊中 ，且通過查索引知道第二塊的開始序號為 7。 第二步是在分塊中查找 ， 即自第七個元素開始順序查找 ， 直到第十個元素時關(guān)鍵字與指定值相等 ， 即查找成功 。 假如該塊中沒有關(guān)鍵字等于 K的元素 （ 例如 K＝ 29） ， 則查到第 12個元素時該塊的元素查完 ， 沒有關(guān)鍵字與指定值相等的元素 ， 則查找不成功 。 69 動態(tài)查找表 基本特點 查找表的結(jié)構(gòu)在查找過程中要發(fā)生變化，即對于給定值K， 若表中存在其關(guān)鍵字等于 K的記錄，則查找成功，否則插入關(guān)鍵字等于 K的記錄。動態(tài)查找表可以在查找過程中動態(tài)地生成，即從初始狀態(tài)的空表開始，在查找過程中逐漸形式一個較完整的查找表。 例如：排序二叉樹即為動態(tài)查找表（樹），下面介紹排序二叉樹的有關(guān)算法。 70 排序二叉樹的動態(tài)生成過程 32,16,43,14,25,57,18,52,61 32 57 43 18 61 52 16 25 14 P=nil 32 16 32 43 16 25 14 32 71 排序二叉樹的查找（遞歸函數(shù)） template class elemtp Tnode elemtp *Tpxrc elemtp:: sear0(elemtp el,Tnode elemtp *pxrc) 其中 el表示要查找的結(jié)點關(guān)鍵碼 ， pxrc表示指向排序二叉樹根結(jié)點的指針 。 功能：若在 pxrc所指的排序二叉樹中存在關(guān)鍵碼等于 el的結(jié)點 ， 則返回指向該結(jié)點的指針 ， 否則返回空指針NULL。 處理過程：若 pxrc為空 ， 則返回空指針 NULL， 否則： (1) 若 el小于 pxrc所指結(jié)點的關(guān)鍵碼 ， 則在 pxrc所指結(jié)點的左子樹中查找 ， 即以左子樹根結(jié)點指針為參數(shù)遞歸調(diào)用本函數(shù)； (2)若 el大于 pxrc所指結(jié)點的關(guān)鍵碼 ， 則在 pxrc所指結(jié)點的右子樹中查找 ， 即以右子樹根結(jié)點指針為參數(shù)遞歸調(diào)用本函數(shù)； (3)否則返回 pxrc。 72 排序二叉樹的查找（遞歸函數(shù)） template class elemtp Tnode elemtp *Tpxrc elemtp:: sear0(elemtp el,Tnode elemtp *pxrc) { if (pxrc==NULL ) return(NULL)。 else if (el == pxrcdata) return(pxrc)。 else if (el pxrcdata) return(sear0( el,pxrclchild))。 else return(sear0( el,pxrcrchild))。 }。 接口函數(shù)： template class elemtp Tnode elemtp *Tpxrc elemtp:: sear(elemtp el) {return(sear0(el,root))。} 73 排序二叉樹的查找（非遞歸函數(shù)） template class elemtp Tnode elemtp *Tpxrc elemtp:: sear1(elemtp el) 功能：在當(dāng)前的排序二叉樹中查找元素值為 el的結(jié)點 ， 并返回該結(jié)點的指針 。 處理過程： 設(shè)置 p為根結(jié)點 。 若 p為空 ， 返回空指針 NULL， 否則 (1)若 el小于 p所指結(jié)點的關(guān)鍵碼 ， 則令 p指向所指結(jié)點的左兒子；若 el大于 p所指結(jié)點的關(guān)鍵碼 ， 則令 p指向所指結(jié)點的右兒子； (2)重復(fù) (1)直至 p為空或 p所指結(jié)點的關(guān)鍵碼與 el相等； (3) 返回 p。 74 排序二叉樹的查找（非遞歸函數(shù)） template class elemtp Tnode elemtp *Tpxrc elemtp:: sear1(elemtp el) {Tnode elemtp *p。 p=root。 while(p!=NULL) if (el pdata) p=plchild。 else if (el pdata) p=prchild。 else break。 return(p)。 } 75 排序二叉樹的查找 執(zhí)行實例 在以下的排序二叉樹中 （ 1） 查 52 （ 2） 查 53 57 43 18 61 52 16 25 14 32 76 具有插入功能的查找（遞歸） template class elemtp void Tpxrc elemtp:: inst0(Tnode elemtp *p,Tnode elemtp *amp。pxrc) 其中 p表示要插入結(jié)點的指針 ， pxrc表示要插入的排序二叉樹的根結(jié)點指針 。 這二個參數(shù)的類型均為結(jié)點指針類型 ， 由于參數(shù) pxrc的值可能改變 ， 所以要加上引用符號 ’ amp?！? 功能：將 p所指向的結(jié)點插入在 pxrc所指向的排序二叉樹 處理過程： （ 1） 若 pxrc為空 ， 則令其為 p； 否則： （ 2） 若 p所指結(jié)點的關(guān)鍵碼小于 pxrc的關(guān)鍵碼 ， 則通過遞歸調(diào)用將 p插入在 pxrc的左子樹上 ， 否則插入在 pxrc的右子樹上 。 77 具有插入功能的查找（遞歸） template class elemtp void Tpxrc elemtp:: inst0(Tnode elemtp *p,Tnode elemtp *amp。pxrc) { if (pxrc==NULL ) pxrc=p。 else if (pdata pxrcdata ) inst0( p,pxrclchild)。 else inst0( p,pxrcrchild)。 }。 78 具有插入功能的查找（接口函數(shù)） template class elemtp void Tpxrc elemtp ::inst(elemtp el)； 功能為：在當(dāng)前的排序二叉樹上查找關(guān)鍵字等于給定值 el的結(jié)點 ， 當(dāng)查找成功時輸出相應(yīng)的信息 ， 否則建立一個新結(jié)點并插入在當(dāng)前排序二叉樹的適當(dāng)位置中 。 { Tnode elemtp *p。 p = sear(el)。 if