數(shù)據(jù)結構(嚴蔚敏)課件第1章(編輯修改稿)
2024-09-01 07:41 本頁面
【文章內(nèi)容簡介】 果 z3 = z1 + z2 即為用戶企求的結果 2022年 9月 5日星期三 第 37頁 ADT 有兩個重要特征 : 數(shù)據(jù)抽象 用 ADT描述程序處理的實體時，強調(diào)的是其 本質(zhì)的特征 、 其所能完成的功能 以及它和 外部用戶的接口 （即 外界使用它的方法 ）。 數(shù)據(jù)封裝 將實體的 外部特性和其內(nèi)部實現(xiàn)細節(jié)分離 ，并且 對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。 2022年 9月 5日星期三 第 38頁 抽象數(shù)據(jù)類型的描述方法 抽象數(shù)據(jù)類型可用 （ D， S， P） 三元組表示。 其中： D 是數(shù)據(jù)對象； S 是 D 上的關系集； P 是對 D 的基本操作集。 2022年 9月 5日星期三 第 39頁 ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對象： 〈 數(shù)據(jù)對象的定義 〉 數(shù)據(jù)關系： 〈 數(shù)據(jù)關系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類型名 其中基本操作的定義格式為 : 基本操作名 （參數(shù)表） 初始條件： 〈 初始條件描述 〉 操作結果 ： 〈 操作結果描述 〉 2022年 9月 5日星期三 第 40頁 賦值參數(shù) 只為操作提供輸入值。 引用參數(shù) 以 amp。打頭，除可提供輸入值外， 還將返回操作結果。 初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。 操作結果 說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。若初始條件為空，則省略之。 2022年 9月 5日星期三 第 41頁 抽象數(shù)據(jù)類型的表示和實現(xiàn) 抽象數(shù)據(jù)類型需要通過 固有數(shù)據(jù)類型 (高級編程語言中已實現(xiàn)的數(shù)據(jù)類型 )來實現(xiàn)。 例如，對以上定義的復數(shù)。 2022年 9月 5日星期三 第 42頁 typedef struct { float realpart； float imagpart； }plex； // 存儲結構的定義 // 基本操作的函數(shù)原型說明 void Assign( plex amp。Z, float realval, float imagval )； // 構造復數(shù) Z,其實部和虛部分別被賦以參數(shù) // realval 和 imagval 的值 2022年 9月 5日星期三 第 43頁 float GetReal( cpmplex Z )； // 返回復數(shù) Z 的實部值 float Getimag( cpmplex Z )； // 返回復數(shù) Z 的虛部值 void add( plex z1, plex z2, plex amp。sum )； // 以 sum 返回兩個復數(shù) z1, z2 的和 2022年 9月 5日星期三 第 44頁 // 基本操作的實現(xiàn) void add( plex z1, plex z2, plex amp。sum ) { // 以 sum 返回兩個復數(shù) z1, z2 的和 = + 。 = + 。 } { 其它省略 } 2022年 9月 5日星期三 第 45頁 算法和算法分析 一、算法 二、算法設計的原則 三、算法效率的衡量方法和準則 四、算法的存儲空間需求 2022年 9月 5日星期三 第 46頁 算法 是為了解決某類問題而規(guī)定的一個有限長的 操作序列 。一個算法必須滿足以下 五 個重要 特性 ： 1． 有窮性 2． 確定性 3． 可行性 4． 有輸入 5． 有輸出 一、算法 2022年 9月 5日星期三 第 47頁 1． 有窮性 對于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結束，即： 算法中的每個步驟都能在 有限時間 內(nèi)完成。 2． 確定性 對于 每種情況 下所應執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。 并且 在任何條件下，算法都只有一條執(zhí)行路徑。 2022年 9月 5日星期三 第 48頁 3． 可行性 算法中的所有操作都必須 足夠基本 ，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。 4． 有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。 2022年 9月 5日星期三 第 49頁 5． 有輸出 它是一組與 “ 輸入 ” 有確 定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。 2022年 9月 5日星期三 第 50頁 二、算法設計的原則 設計算法時，通常應考慮達到以下目標： 1． 正確性 2. 可讀性 3． 健壯性 4． 高效率與低存儲量需求 2022年 9月 5日星期三 第 51頁 1． 正確性 首先， 算法應當 滿足 以特定的 “ 規(guī)格說明 ” 方式給出的 需求 。 其次， 對算法是否 “ 正確 ” 的 理解可以有以下 四個層次 ： a． 程序中不含語法錯誤； b． 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結果； 2022年 9月 5日星期三 第 52頁 c．程序?qū)τ?
環(huán)評公示相關推薦
鄂ICP備17016276號-1