【正文】 List[3] 用二分法，確定在索引表中的位置為 mid=2， key值 60與 a[2]比較， 60a[2],取第 3個(gè)塊 。在第 3塊中用順序法查找 ,比較兩次 ,就可以找出 60的元素來(lái)。 下一頁(yè) 上一頁(yè) 停止放映 [第 20頁(yè) /81] 索引表結(jié)構(gòu)定義 typedef struct { int key。 /* 塊最大值 */ int link。 /* 指向塊入口地址 */ } index。 示例 下一頁(yè) 上一頁(yè) 停止放映 [第 21頁(yè) /81] 動(dòng)態(tài)查找技術(shù) ? 前兩種查找方法各有千秋。二分法查找效率高，順序法可以采用鏈表存儲(chǔ)結(jié)構(gòu)，操作靈活。能否設(shè)計(jì)更好的算法？使其既有二分法的高效率，又有鏈表靈活性的查找方法？ ? 動(dòng)態(tài)查找技術(shù)所依賴(lài)的查找表就是這樣的算法，例如二叉排序樹(shù)等。它們的共同特點(diǎn)是結(jié)構(gòu)靈活，易于實(shí)現(xiàn)插入、刪除等操作。這里主要介紹簡(jiǎn)單易用的二叉排序樹(shù)。 ? 二叉排序樹(shù)實(shí)際上就是將數(shù)據(jù)元素組織成二叉樹(shù)形式 ， 以達(dá)到與二分法相同的查找效率 ， 而又具有鏈表的插入 、 刪除操作的靈活性 。 下一頁(yè) 上一頁(yè) 停止放映 [第 22頁(yè) /81] 二叉排序樹(shù)的定義： 二叉排序樹(shù) 可能為一棵空的二叉樹(shù)，若非空則 必須 滿(mǎn)足以下特征： （ 1）根結(jié)點(diǎn)左子樹(shù)中所有結(jié) 點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān) 鍵字； （ 2）根結(jié)點(diǎn)右子樹(shù)中所有結(jié) 點(diǎn)的關(guān)鍵字大于或等于根結(jié) 點(diǎn)的關(guān)鍵字； （ 3）根結(jié)點(diǎn)的左右子樹(shù)也都 是二叉排序樹(shù)。 一棵二叉排序樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 [第 23頁(yè) /81] 算法描述： step1 首先建立起二叉排序樹(shù) 。 step2 將待查關(guān)鍵字值與樹(shù)根結(jié)點(diǎn)進(jìn)行比較 ， 若相等 ， 查找成功； step3 否則根據(jù)比較結(jié)果確定查找路徑： 若小于根結(jié)點(diǎn)的關(guān)鍵字值 ， 則與左子樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較； 若大于等于根結(jié)點(diǎn)的關(guān)鍵字值 ， 則與右子樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較 。 step4 重復(fù)上述步驟 ， 直到要么找到 ， 查找成功；要么找不到 ， 查找失敗 。 下一頁(yè) 上一頁(yè) 停止放映 [第 24頁(yè) /81] 二叉排序樹(shù)結(jié)點(diǎn)結(jié)構(gòu) typedef struct BinNode { ElemType x。 //關(guān)鍵字 struct BinNode *left； //左子指針 struct BinNode *right。 //右子指針 }*BinNodePtr。 下一頁(yè) 上一頁(yè) 停止放映 [第 25頁(yè) /81] 二叉排序樹(shù)生成算法 建立二叉樹(shù) Create_btree() 查詢(xún)結(jié)點(diǎn) Search_btree() 打印二叉樹(shù) Print_btree() 主程序 下一頁(yè) 上一頁(yè) 停止放映 [第 26頁(yè) /81] 主程序框圖 開(kāi)始 初始化 輸入結(jié)點(diǎn)數(shù)據(jù)循環(huán) ！ ROOT root=create_btee（） create_btree() 結(jié)束 ? N Y 打印該樹(shù) 查找指定結(jié)點(diǎn) Print_btree() Search_btree() 下一頁(yè) 上一頁(yè) 停止放映 [第 27頁(yè) /81] 主程序 void main ( ) { char *s,*c,key=??。 struct tree *create_btree(),*search_btree(),*root=0。 do //輸入插入元素的循環(huán) { cout“Enter a letter:”。 gets(s)。 if (!root) root=create_btree(root,root,*s)。 //插入頭結(jié)點(diǎn) else create_btrr(root,root,*s)。 //插入子結(jié)點(diǎn) } while (*s) 。 print_btree(root,0)。 //打印二叉樹(shù) key=?1?。 while( key) //反復(fù)搜索循環(huán) { cout“Enter a key to find:”。 cinc。 key=search_btree(root,c)。 //搜索二叉樹(shù) cout“press to continue\n”。 } } 下一頁(yè) 上一頁(yè) 停止放映 [第 28頁(yè) /81] 生成二叉排序樹(shù)程序 struct tree create_btree(struct tree *root, struct tree *r, char info) { if (r == 0 ) { r = new (struct tree)。 //生成一個(gè)結(jié)點(diǎn)空間 if ( r == 0) //空間滿(mǎn) ,返回 { cout“Out of memory\n”。 exit(0)。 } rleft= 0。 rright=0。 rinfo=info。 if (root) //若根非空 { if(inforootinfo) root left=r。 //插入左子 else rootright=r。 //或插入右子 } else //若根為空 { rright=0。 rleft = 0。 } return r。 } if (inforinfo) create_btree(r,rleft,info)。 //插入左子樹(shù) if(info=rinfo) create_btree(r,rright,info)。 //插入右子樹(shù) } 二叉樹(shù)生成 下一頁(yè) 上一頁(yè) 停止放映 [第 29頁(yè) /81] 打印二叉排序樹(shù)程序 print_btree(struct tree *r, int l) { int i； if (r = = 0) return ； print_tree(rleft,l+1)； //打印左子樹(shù) for(i=0。il。i++) cout“ ”； coutrinfo； //打印根結(jié)點(diǎn) print_btree(rright,l+1) ； //打印右子樹(shù) } 下一頁(yè) 上一頁(yè) 停止放映 [第 30頁(yè) /81] struct tree *search_btree(struct tree *root,char key) { if (!root) { cout“Emptu btree”。 return root。 } while(rootinfo!=key) // 查找 key循環(huán) { if(keyrootinfo) root=rootleft。 //沿左路查找 else root=rootright。 //沿右路查找 if(root==0) //到葉結(jié)點(diǎn)也沒(méi)找到 { cout“Search Failure\n”。 break 。 } } if (root !=0) //查找成功 cout“Successful search! key=”rootinfoendl。 return root 。 } 查詢(xún)二叉排序樹(shù)程序 下一頁(yè) 上一頁(yè) 停止放映 [第 31頁(yè) /81] 舉例 輸入： 輸出： h ? b d ? d p ? e r ? h b ? p e ? r ? 例子 h p r d b e 前序遍歷序列： h d b e p r 中序遍歷序列： b d e h p r 后序遍歷序列： b e d r p h 下一頁(yè) 上一頁(yè) 停止放映 [第 32頁(yè) /81] 動(dòng)態(tài)查找 過(guò)程也是 生成 二叉排序樹(shù)的過(guò)程。假定由整數(shù)序列 {10， 6， 19， 22， 8， 2}生成一棵二叉排序樹(shù)，可以采用逐個(gè)元素插入的方法實(shí)現(xiàn)。 (1) 首先將 10作為根結(jié)點(diǎn) (2) 然后插入 6時(shí)，通過(guò)比較知 610，所以將 6作為 10的左孩子插入； (3) 同理將 19作為 10的右孩子插入； (4) 整數(shù) 22通過(guò)和 19比較后，作為 19的右孩子插入。 (5) 依次插入剩余的其他元素 下一頁(yè) 上一頁(yè) 停止放映 [第 33頁(yè) /81] 哈希（ hash）查找 哈希查找也稱(chēng)為散列查找 。 它不同于前面介紹的幾種查找方法 。 上述方法都是把查找建立在比較的基礎(chǔ)上 ， 而哈希查找則是通過(guò)計(jì)算存儲(chǔ)地址的方法進(jìn)行查找的 。 計(jì)算是計(jì)算機(jī)的特點(diǎn)之一 ， 因此 ， 建立在計(jì)算基礎(chǔ)上的哈希查找是一種快速查找方法 。 下一頁(yè) 上一頁(yè) 停止放映 [第 34頁(yè) /81] 哈希查找的基本概念 哈希表 由哈希函數(shù)的值組成的表 。 哈希查找是建立在哈希表的基礎(chǔ)上 ， 它是線(xiàn)性表的一種重要存儲(chǔ)方式和檢索方法 。 在哈希表中可以實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的快速檢索 。 哈希函數(shù) 哈希表中元素是由哈希函數(shù)確定的 。將數(shù)據(jù)元素的關(guān)鍵字 K作為自變量 ， 通過(guò)一定的函數(shù)關(guān)系 （ 稱(chēng)為哈希函數(shù) ） ， 計(jì)算出的值 ，即為該元素的存儲(chǔ)地址 。 表示為： Add