抽象數(shù)據(jù)類型與面向?qū)ο蟾拍?wenkub
2023-03-16 14:53:55 本頁面
【正文】 儲無關(guān) ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是 從具體問題抽象出來的數(shù)據(jù)模型 ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān) ； ? 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。 ?整數(shù)數(shù)據(jù)對象 ： N = { 0, ?1, ?2, … } ?學(xué)生數(shù)據(jù)對象。 數(shù)據(jù)項 是 具有獨立含義的最小標(biāo)識單位 。 ? 數(shù)值性數(shù)據(jù)； ? 非數(shù)值性數(shù)據(jù)。 數(shù)據(jù)元素 (data element) ? 數(shù)據(jù)的 基本單位 。 ? 數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。 什么是數(shù)據(jù)結(jié)構(gòu) 定義 : 由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。 數(shù)據(jù)的邏輯結(jié)構(gòu)分類 ? 線性結(jié)構(gòu)。 定義： 一組性質(zhì)相同的值的集合 , 以及定義于這個值集合上的一組操作的總稱。 ? 基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 ? 由 基本的數(shù)據(jù)類型 組成 , 并包括 一組相關(guān)的服務(wù) （或稱操作）。 False, True ? Boolean, +、 、 、 ==、 =等都是可用的服務(wù)。 ? 類中的對象為該類的實例。 ? 特性： ? 輸入 有 0個或多個輸入； ? 輸出 有一個或多個輸出 (處理結(jié)果 )； ? 確定性 每步定義都是確切無歧義的； ? 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束； ? 有效性 每一條運算應(yīng)足夠基本。 ? 算法框架： for ( int i = 0。 } ? 細(xì)化程序： 程序 SelectSort 算法設(shè)計 自頂向下，逐步求精 void selectSort ( int a[ ], const int n ) { //對 n個整數(shù) a[0],a[1],…,a[n 1]按遞增順序排序 for ( int i = 0。 j n。 a[k] = temp。 void Swap (int m1, int m2)。 friend ostream operator (ostream outStream, datalistType outList)。 Element [m1] = Element [m2]。 return max。 i++) OutStream [i] ‘ ’ 。 } template class Type istream operator (istream InStream, dataListType InList) { //輸入對象為 InList，輸入流對象為 InStream cout “ 錄入數(shù)組當(dāng)前大小 : ” 。 i 。 } template class Type void dataListType :: Sort ( ) { //按非遞減順序?qū)?ArraySize個關(guān)鍵碼 //Element[0]到 Element[ArraySize1]排序 for ( int i = ArraySize 1。 } } endif 使用模板的選擇排序算法的主函數(shù) include “ ” const int SIZE = 10。 ( )。 順序搜索 (Sequenial Search) int seqsearch ( int a[ ], int n, int x ) { //在 a[0],…,a[n 1]中搜索 x int i = 0。 } 插裝 time( ) 的計時程序 double start, stop。 double runTime = stop start。 時間復(fù)雜度度量 ? 編譯時間。 ? 執(zhí)行時間與實例特性無關(guān)。 for ( int i = 0。 } 在求累加和程序中加入 count語句 float sum ( float a[ ], int n ) { float s = 。 i++ ) { count++。 //針對 for 的最后一次 count++。 i++ ) count += 2。 1 1 1 for ( int i= 0 。 1 1 1} 0 1 0 總程序步數(shù) 2n+3 時間復(fù)雜度的漸進(jìn)表示法 例 求兩個 n階方陣的乘積 C = A?B void MatrixMultiply ( int A[n][n], int B[n][n], int C[n][n] ) { for ( int i = 0。 j++ ) { … n(n+1) C[i][j] = 0。 … n3 } } 2n3 + 3n2 + 2n +1 時間復(fù)雜度的漸進(jìn)表示法 ? 算法中所有語句的頻度之和是 矩陣階數(shù) n的函數(shù) T(n) = 2n3 + 3n2 + 2n +1 ? 一般地，稱 n 是問題的規(guī)模。 for ( int k = 0。 i n。 T1(n) = O(1) T2(n) = O(n) T3(n) = O(n2) T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2) ? 乘法規(guī)則 針對嵌套程序段 T (n, m) = T1 (n) * T2 (m
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1