數(shù)據(jù)結(jié)構a第06章(已改無錯字)
2022-08-21 17:38:32 本頁面
【正文】 2022年 1月 （ 續(xù) ） （ 1） 當 xam時 ， 若與 x相同關鍵字值的元素在表中 ， 則必定在子表 （ a0,a1,…,am1） 中 ， 可以在該子表中繼續(xù)進行搜索 。 （ 2） 當 x= =am時 ， 則搜索成功 。 （ 3） 當 xam時 ， 若與 x相同關鍵字值的元素在表中 ， 則必定在子表 （ am+1,am+2,…,an－ 1） 中 ，可以在該子表中繼續(xù)進行搜索 。 南京郵電大學計算機學院 2022年 1月 對半搜索的例子： “ [”=low, “]”=high (1)key=66， 搜索成功 0 1 2 3 4 5 6 7 8 9 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 下標 [ (2) key=35， 搜索失敗 0 1 2 3 4 5 6 7 8 9 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 21 30 36 41 52 54 66 72 83 97 下標 ] [ ] [ ] ] [ [ ] [ ] [ ] [ ] 南京郵電大學計算機學院 2022年 1月 私有遞歸函數(shù) BSearch定義如下： int ListSetT::BSearch(Tamp。 x, int low,int high)const 在范圍為 [low,high]的表中搜索與 x有相同關鍵字值的元素；如果存在該元素 ， 則函數(shù)返回該元素在表中的位置 ， 否則函數(shù)返回－ 1， 表示搜索失敗 。 南京郵電大學計算機學院 2022年 1月 template class T int ListSetT::BSearch(Tamp。 x, int low,int high)const { if (low=high){ int m=(low+high)/2。 //對半分割 if (xl[m]) return BSearch(x,low,m1)。 else if (xl[m]) return BSearch(x,m+1,high)。 else return m。 //搜索成功 } return 1。 //搜索失敗 } 南京郵電大學計算機學院 2022年 1月 template class T ResultCode ListSetT::Search( Tamp。 x)const { int i=BSearch(x,0,n1)。 if (i==1) return NotPresent。 x=l[i]。return Success。 } 函數(shù) Search調(diào)用遞歸函數(shù) BSearch實現(xiàn)有序表的二分搜索 南京郵電大學計算機學院 2022年 1月 template class T ResultCode ListSetT::Search(Tamp。 x)const { int m,low=0,high=n1。 while (low=high){ m=(low+
環(huán)評公示相關推薦
鄂ICP備17016276號-1