【正文】 均搜索長度。 ? 在等概率情形， pi = 1/n, i = 1, 2, ? , n。搜索成功的平均搜索程度為： ? 在搜索不成功情形， ASLunsucc = n+1。 .)()(1????????? nis u c cnnnninA S L 0 212111121 ? 采用遞歸方法搜索值為 x 的元素，每遞歸一層就向待查元素逼近一個(gè)位置，直到到達(dá)該元素。假設(shè)待查元素在第 i（ 1≤i≤n）個(gè)位置，則算法遞歸深度達(dá) i（ 1～ i）。 10 20 30 40 50 60 i = 1 搜索 30 10 20 30 40 50 60 i = 2 10 20 30 40 50 60 i = 3 遞 歸 順序搜索的遞歸算法 22 順序搜索的遞歸算法 template class E, class K int dataListE, K:: SeqSearch (const K x, int loc) const { //在數(shù)據(jù)表 Element[1..n] 中搜索其關(guān)鍵碼與給定值 //匹配的對(duì)象 , 函數(shù)返回其表中位置。參數(shù) loc 是在 //表中開始搜索位置 if (loc CurrentSize) return 0。 //搜索失敗 else if (Element[loc1].key == x) return loc。 //搜索成功 else return Search (x, loc+1)。 //遞歸搜索 }。 基于有序順序表的順序搜索算法 template class Type int searchListType :: Search ( const Typeamp。 x ) const { //順序搜索關(guān)鍵碼為 x的數(shù)據(jù)對(duì)象 for ( int i = 0。 i CurrentSize。 i++ ) if ( Element[i].key == x ) return i。 //成功 else if ( Element[i].key x ) break。 return 1。 //順序搜索失敗 , 返回失敗信息 } ? 有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 ? ?27161 50??? ??is u c c iA S L? ?7276171 50?????????????iun s uc ciA S L基于有序順序表的折半搜索 ? 設(shè) n個(gè)對(duì)象 存放在一個(gè)有序順序表中 ， 并按其關(guān)鍵碼從小到大排好了序 。 ? 折半搜索時(shí) , 先求位于搜索區(qū)間正中的對(duì)象的下標(biāo)mid， 用其關(guān)鍵碼與給定值 x比較 : ? Element[mid].key == x， 搜索成功 ； ? Element[mid].key x， 把搜索區(qū)間縮小 到表的 前半部分 ， 繼續(xù)折半搜索 ； ? Element[mid].key x， 把搜索區(qū)間縮小 到表的 后半部分 ， 繼續(xù)折半搜索 。 ? 如果搜索區(qū)間已縮小到一個(gè)對(duì)象 ， 仍未找到想要搜索的對(duì)象 ， 則搜索失敗 。 搜索成功的例子 1 0 1 3 4 6 8 10 12 6 0 1 2 3 4 5 6 7 8 搜索 low mid high 6 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6 搜索失敗的例子 1 0 1 3 4 6 8 10 12 5 0 1 2 3 4 5 6 7 8 搜索 low mid high 5 6 8 10 12 5 6 7 8 low mid high 6 5 5 low mid high 5 template class Type class orderedList : public dataListType { //有序表的類定義 ,繼承了數(shù)據(jù)表 public: orderedList (int sz = 10) : dataListType (sz) { } ~orderedList ( ) { } int BinarySearch ( const Typeamp。 x ) const。 }。 template class Type int orderedListType :: //折半搜索算法 BinarySearch ( const Type amp。 x, const int low, const int high ) const { //折半搜索的遞歸算法 int mid = 1。 if ( low = high ) { mid = ( low + high ) / 2。 if ( Element[mid].key x ) mid = BinarySearch ( x, mid +1, high )。 else if ( Element[mid].key x ) mid = BinarySearch ( x, low, mid 1 )。 } return mid。 } templateclass Type int orderedList Type:: BinarySearch ( const Type amp。 x ) const { //折半搜索的迭代算法 int high = CurrentSize1, low = 0, mid。 while ( low = high ) { mid = ( low + high ) / 2。 if ( Element[mid].key x ) low = mid + 1。 //右縮搜索區(qū) else if ( Element[mid].key x ) high = mid 1。 //左縮搜索區(qū)間 else return mid。 //搜索成功 } return 1。 //搜索失敗 } 有序順序表的折半搜索的判定樹 ( 10, 20, 30, 40, 50, 60 ) 10 50 = = = = = = 30 20 40 60 ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 ? 搜索成功時(shí)檢測(cè)指針停留在樹中某個(gè)結(jié)點(diǎn)。 ? 搜索不成功時(shí)檢測(cè)指針停留在某個(gè)外結(jié)點(diǎn)（失敗結(jié)點(diǎn)）。 35 15 45 50 25 10 20 30 搜索 22 搜索 45 折半搜索性能分析 ? 若設(shè) n = 2h1，則描述折半搜索的判定樹是高度為 h1 的滿二叉樹。 2h = n+1, h = log2(n+1) ? 第 0層結(jié)點(diǎn)有 1個(gè) , 搜索第 0層結(jié)點(diǎn)要比較 1次 。 第 1層結(jié)點(diǎn)有 2個(gè) , 搜索第 1層結(jié)點(diǎn)要比較 2次 。 …, 第 i (0 ≤ i ? h) 層結(jié)點(diǎn)有 2i 個(gè) , 搜索第 i 層結(jié)點(diǎn)要比較 i+1次， … 。 ? 假定每個(gè)結(jié)點(diǎn)的搜索概率相等，即 pi = 1/n，則搜索成功的平均搜索長度為 34 二叉搜索樹 ( Binary Search Tree ) ? 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： ? 每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。 ? 左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。 ? 右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。 ? 左子樹和右子樹也是二叉搜索樹。 35 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼； ? 右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼； ? 注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。 36 ? 如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。 ? 二叉搜索樹的類定義 include include template class E, class K struct BSTNode { //二叉樹結(jié)點(diǎn)類 E data。 //數(shù)據(jù)域 BSTNodeE, K *left, *right。 //左子女和右子女 37 BSTNode() { left = NULL。 right = NULL。 } //構(gòu)造函數(shù) BSTNode (const E d, BSTNodeE, K *L = NULL, BSTNodeE, K *R = NULL) { data = d。 left = L。 right = R。} //構(gòu)造函數(shù) ～ BSTNode() {} //析構(gòu)函數(shù) void setData (E d) { data = d。 } //修改 E getData() { return data。 } //提取 bool operator (const Eamp。 x) //重載：判小于 { return 。 } 38 bool operator (const Eamp。 x) //重載：判大于 { return 。 } bool operator == (const Eamp。 x) //重載：判等于 { return == 。 } }。 template class E, class K class BST { //二叉搜索樹類定義 public: BST() { root = NULL。 } //構(gòu)造函數(shù) BST(K value)。 //構(gòu)造函數(shù) ～ BST() {}。 //析構(gòu)函數(shù) 39 bool Search (const K x) const //搜索 { return Search(x,root) != NULL。 } BSTE, Kamp。 operator = (const BSTE, Kamp。 R)。 //重載：賦值 void makeEmpty() //置空 { makeEmpty (root)。 root = NULL。} void PrintTree() const { PrintTree (root)。 } //輸出 E Min() { return Min(root)data。 } //求最小 E Max() { return Max(root)data。 } //求最大 bool Insert (const Eamp。 e1) //插入新元素 { return Insert(e1, root)。}