抽象數(shù)據(jù)類型與面向?qū)ο蟾拍?完整版)
【正文】 Element[k] ) max = k。} void Sort ( )。 a[i] = a[k]。 若最小整數(shù)在 a[k], 交換 a[i]與 a[k]。 數(shù)據(jù)結(jié)構(gòu)的抽象層次 算法定義 ? 定義： 一個有窮的指令集 ，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列。 Function: 對于所有的 x, y ? NaturalNumber。 ? 構(gòu)造數(shù)據(jù)類型由 不同成分類型 構(gòu)成。 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 從邏輯關(guān)系上描述數(shù)據(jù) ， 與數(shù)據(jù)的存儲無關(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ù)據(jù)項 是 具有獨立含義的最小標(biāo)識單位 。 數(shù)據(jù)元素 (data element) ? 數(shù)據(jù)的 基本單位 。 什么是數(shù)據(jù)結(jié)構(gòu) 定義 : 由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。 定義： 一組性質(zhì)相同的值的集合 , 以及定義于這個值集合上的一組操作的總稱。 ? 由 基本的數(shù)據(jù)類型 組成 , 并包括 一組相關(guān)的服務(wù) （或稱操作）。 ? 類中的對象為該類的實例。 ? 算法框架： for ( int i = 0。 j n。 void Swap (int m1, int m2)。 Element [m1] = Element [m2]。 i++) OutStream [i] ‘ ’ 。 i 。 } } 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。 double runTime = stop start。 ? 執(zhí)行時間與實例特性無關(guān)。 } 在求累加和程序中加入 count語句 float sum ( float a[ ], int n ) { float s = 。 //針對 for 的最后一次 count++。 1 1 1 for ( int i= 0 。 j++ ) { … n(n+1) C[i][j] = 0。 for ( int k = 0。 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) = O(f (n)*g (m)) ? 漸進的空間復(fù)雜度 S (n) = O(f (n)) ? 兩個并列循環(huán)的例子 void exam ( float x[ ][ ], int m, int n ) { float sum [ ]。 i m。 j = i。 ? 例：設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為 100n2 和 2n，問：要使前者快于后者， n 至少要取多大？ 解答： 問題是找出滿足 100n2 = 2n 的最小的n。 if ( value MaxInt / n / 2 ) return 0。 break。 } T[n] = value。 出錯處理問題舉例 ? 試編寫一個函數(shù)計算 n!*2n 的值，結(jié)果存放于數(shù)組 A[arraySize] 的第 n 個數(shù)組元素中 (0 ≤ n ≤ arraySize) ? 若設(shè)計算機中允許的整數(shù)的最大值為 maxInt，則當(dāng) n arraySize 或者對于某一個 k ( 0 ≤ k ≤ n )，使得 k!*2k maxInt 時，應(yīng)按出錯處理。 //發(fā)生逆序 , 交換 exchange = 1。 } 漸進時間復(fù)雜度為 O(max (m*n, m)) template class Type //起泡排序 void dataListType :: bubbleSort ( ) { //對表逐趟比較 , ArraySize 是表當(dāng)前長度 int i = 1。 i m。 k ++ ) x ++。 k n。 i+ + ) 1 n+1 n+1 s += a [ i] 。 } 執(zhí)行結(jié)束得 程序步數(shù) count = 2*n+3 程序的簡化形式 void sum ( float a[ ], int n ) { for ( int i = 0。 //count 統(tǒng)計執(zhí)行語句條數(shù) for ( int i = 0。 表達式 ：程序步數(shù)為 1。 算法的事前估計 ? 空間復(fù)雜度 ? 時間復(fù)雜度 空間復(fù)雜度度量 ? 存儲空間的固定部分 程序指令代碼的空間，常數(shù)、簡單變量、定長成分 (如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等 )變量所占空間。 if ( i == n ) return 1。 cin TestList。 InStream [i]。 O
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1