抽象數(shù)據(jù)類型與面向?qū)ο蟾拍?存儲版)
【正文】 計算機語言的實現(xiàn)； ? 數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。 ? 數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。 ? 由一組 屬性值 和在這組值上的一組 服務 （或稱操作）構(gòu)成。 ? 明確問題： 遞增排序。 i++ ) { int k = i。 用模板定義用于排序的數(shù)據(jù)表類 ifndef DATALIST_H define DATALIST_H include template class Type class dataList { private: Type *Element。 }。 for (int i = 0。 cout “ 錄入數(shù)組元素值 : \n” 。 i ) { int j = MaxKey (0, i)。 return 0。 int k = seqsearch (a, n, x)。 ? 程序步。 i++ ) s += a[i]。 count++。 } 注意 ： 一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。 i++ ) … n+1 for ( int j = 0。 ? 當 n趨于無窮大時，把時間復雜度的數(shù)量級（階）稱為算法的漸進時間復雜度 T(n) = O(n3) 大 O表示法 時間復雜度的漸進表示法 ? 加法規(guī)則 針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) ? 各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n! 變量計數(shù) x = 0。 j n。 j++ ) sum[i] += x[i][j]。 } //一趟比較 } template class Type void dataListType:: BubbleExchange(int i, int exchange ){ exchange = 0。 return i。 i n。 i arraySize。 //n!*2n ? T[n] } void main ( ) { int A[arraySize], i。 include define arraySize 100 define MaxInt 0x7fffffff int calc ( int T[ ], int n ) { int i, value = 1。 ? 在數(shù)組 A[n] 中查找給定值 k 的算法： int i = n1。 //當 exchange 為 0 則停止排序 while ( i ArraySize exchange ) { BubbleExchange ( i, exchange )。 //數(shù)據(jù)累加 for ( int j = 0。 i n。 … n3 } } 2n3 + 3n2 + 2n +1 時間復雜度的漸進表示法 ? 算法中所有語句的頻度之和是 矩陣階數(shù) n的函數(shù) T(n) = 2n3 + 3n2 + 2n +1 ? 一般地，稱 n 是問題的規(guī)模。 1 1 1} 0 1 0 總程序步數(shù) 2n+3 時間復雜度的漸進表示法 例 求兩個 n階方陣的乘積 C = A?B void MatrixMultiply ( int A[n][n], int B[n][n], int C[n][n] ) { for ( int i = 0。 i++ ) count += 2。 i++ ) { count++。 for ( int i = 0。 時間復雜度度量 ? 編譯時間。 } 插裝 time( ) 的計時程序 double start, stop。 ( )。 } template class Type void dataListType :: Sort ( ) { //按非遞減順序?qū)?ArraySize個關(guān)鍵碼 //Element[0]到 Element[ArraySize1]排序 for ( int i = ArraySize 1。 } template class Type istream operator (istream InStream, dataListType InList) { //輸入對象為 InList，輸入流對象為 InStream cout “ 錄入數(shù)組當前大小 : ” 。 return max。 friend ostream operator (ostream outStream, datalistType outList)。 a[k] = temp。 } ? 細化程序： 程序 SelectSort 算法設(shè)計 自頂向下，逐步求精 void selectSort ( int a[ ], const int n ) { //對 n個整數(shù) a[0],a[1],…,a[n 1]按遞增順序排序 for ( int i = 0。 ? 特性： ? 輸入 有 0個或多個輸入； ? 輸出 有一個或多個輸出 (處理結(jié)果 )； ? 確定性
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1