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