抽象數(shù)據(jù)類型與面向?qū)ο蟾拍?文庫吧在線文庫
【正文】 每步定義都是確切無歧義的； ? 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束； ? 有效性 每一條運算應(yīng)足夠基本。 False, True ? Boolean, +、 、 、 ==、 =等都是可用的服務(wù)。 ? 基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)分類 ? 線性結(jié)構(gòu)。 ? 數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。 ? 數(shù)值性數(shù)據(jù)； ? 非數(shù)值性數(shù)據(jù)。 ?整數(shù)數(shù)據(jù)對象 ： N = { 0, ?1, ?2, … } ?學(xué)生數(shù)據(jù)對象。 ? 順序存儲表示 ? 鏈接存儲表示 ? 索引存儲表示 ? 散列存儲表示 主要用于內(nèi)存的存儲表示 主要用于外存 (文件 ) 的存儲表示 抽象數(shù)據(jù)類型及面向?qū)ο蟾拍? ? 數(shù)據(jù)類型。 抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types) ? 由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。 ? 類 (class)，實例 (instance) ? 具有 相同屬性 和 服務(wù) 的對象歸于同一類，形成類。 ? 解決方案： 逐個選擇最小數(shù)據(jù)。 //從 a[i]查到 a[n1], 找最小整數(shù) , 在 a[k] for ( int j = i+1。 int ArraySize。 endif 類中所有操作作為模板函數(shù)的實現(xiàn) ifndef SELECTTM_H define SELECTTM_H include “ ” template class Type void dataList Type :: Swap (int m1, int m2) { //交換由 m1, m2為下標(biāo)的數(shù)組元素的值 Type temp = Element [m1]。 i 。 for (int i = 0。 if ( j != i ) swap (j, i)。 } 性能分析與度量 ? 算法的性能標(biāo)準(zhǔn) ? 算法的后期測試 ? 算法的事前估計 算法的性能標(biāo)準(zhǔn) ? 正確性 ? 可使用性 ? 可讀性 ? 效率 ? 健壯性 算法的后期測試 在算法中的某些部位插裝時間函數(shù) time ( ) 測定算法完成某一功能所花費時間。 time (stop)。 ? 語法上或語義上有意義的一段指令序列。 return s。 } //針對賦值語句 count++。 例如：賦值語句 x = sum (R, n) 本身的程序步數(shù)為 1； 一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程序步數(shù)為 2*n+3； 一次執(zhí)行的程序步數(shù)為 1+2*n+3 = 2*n+4 計算 累加和 程序 程序步數(shù) 計算工作表格 程 序 語 句一次執(zhí)行所需程序步數(shù)執(zhí)行頻度 程序 步數(shù){ 0 1 0 float s = 。 j n。 y = 0。 j++ ) y ++。 } for ( i = 0。 //假定元素未交換 for ( int j = ArraySize1。 ? 算法的語句 i 的頻度不僅與 n 有關(guān)，還與 A[ ] 中各元素的取值 ，以及 k 的取值 有關(guān)。 i++) { value *= i * 2。 i++ ) if ( !calc ( A, i ) ) { cout failed at i endl。 return 1。 可有如下三種不同的出錯處理方式： ? 用 cerr 及 exit (1) 語句來終止執(zhí)行并報告錯誤； ? 用返回整數(shù)函數(shù)值 0, 1 來實現(xiàn)算法 ，以區(qū)別是正常返回還是錯誤返回； ? 在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某中錯誤返回 。 //做“發(fā)生交換”標(biāo)志 } } 漸進(jìn)時間復(fù)雜度 O(f (n)*g (n)) = O(n2) ??????11 21ni)n(ni)(n?BubblrSort n1趟 BubbleExchange ( ) ni次比較 ? 有時 , 算法的時間復(fù)雜度不僅依賴于問題規(guī)模 n，還與輸入實例的初始排列有關(guān)。 int exchange = 1。 i++ ) { //x中各行 sum[i] = 。 for ( int i = 0。 k++ ) … n2(n+1) C[i][j] = C[i][j] + A[i][k] * B[k][j]。 1 n n retur n s 。 i n。 i n。 ? 程序步確定方法 ? 插入計數(shù)全局變量 count ? 建表，列出個語句的程序步 例 以迭代方式求累加和的函數(shù) float sum ( float a[ ], int n ) { float s = 。 ? 可變部分 尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和 delete命令動態(tài)使用空間。 return i。 cout TestList endl。 } return InStream。 return OutStream。 for (int k = low+1, k = high, k++) if ( Element[max]
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1