《數(shù)據(jù)結構a》第06章(文件)
【正文】 2 23 查找 42 恭喜！！ 85 14 78 42 23 查找 52 遺憾！！ ∞ ∞ 南京郵電大學計算機學院 2022年 1月 有序表的順序搜索 template class T ResultCode ListSetT::Search(Tamp。 if (l[i]==x) { x=l[i]。amp。 程序： 22ni1n 11)1i(1n 11A SL1n1in0iF ????????? ?????結論： 無序表和 有序表在搜索成功時 ASL相同；但是在搜索失敗時 ， 有序表的 ASL是無序表的一半 ， 效率高 。 （ 2） 當 x= =am時 ， 則搜索成功 。 南京郵電大學計算機學院 2022年 1月 template class T int ListSetT::BSearch(Tamp。 else return m。 if (i==1) return NotPresent。 x)const { int m,low=0,high=n1。 else { x=l[m]。如果 x==l[m]， 則算法在該結點處成功終止 。 反之 ， 在 x與 l[m]比較之后有xl[m]， 且算法終止 ， 那么 ， 結點 m的右孩子用一個方形結點表示 ， 結點標號為 m。 如果搜索成功 ， 則算法在內(nèi)結點處終止 ， 否則算法在外結點處終止 。 南京郵電大學計算機學院 2022年 1月 定理 對半搜索算法在搜索成功時的 平均時間復雜度 為 O(log2n)。 從定理 7－ 1可知 ， E=I+2n，因此 ， As(n)=(1+1/n)Au(n)?1= O(log2n) 定理得證 。 對于失敗搜索 ， 假定待查元素 x的值落在區(qū)間 （ l[m]， l[m+1]） ， 0?mn1， 區(qū)間xl[0]和區(qū)間 xl[n1]， 總共 n+1個區(qū)間中的概率是相等的 。 對于不成功的搜索 ， 算法需要作 ?log2n?或 ?log2n?+1次比較 。換句話說 ， 如果算法在方形結點 m處終止 ， 這意味著： （ a） 當 0?mn1時 ， l[m]xl[m+1]之間； （ b） 當 m=1時 ， xl[0]； （ c） 當 m=n1時 ， xl[n1]。 （ 3） 結點 m的左孩子 是當 xl[m]時 ， 算法接下去與x比較的元素下標 ， 其 右孩子 是當 xl[m]時 ,算法接下去與 x比較的元素下標 。 //搜索成功 } } return NotPresent。 if (xl[m]) high=m1。return Success。 //搜索失敗 } 南京郵電大學計算機學院 2022年 1月 template class T ResultCode ListSetT::Search( Tamp。 //對半分割 if (xl[m]) return BSearch(x,low,m1)。 南京郵電大學計算機學院 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
環(huán)評公示相關推薦
鄂ICP備17016276號-1