數(shù)據(jù)結(jié)構(gòu)第一章(存儲版)
【正文】 插入排序運行時間 最好運行時間 Ω(n) 最壞運行時間 O(n2) 插入排序的運行時間在 Ω(n)和 O(n2)之間 漸近記號與不等號的類比 f(n)～ a， g(n)～ b f(n)= O(g(n)) ≈ a≤b f(n)=Ω(g(n)) ≈ a≥b f(n)=Θ(g(n)) ≈ a ＝ b 數(shù)據(jù)結(jié)構(gòu)的選擇和評價 ? 仔細分析所要解決的問題，特別是求解問題所涉及的數(shù)據(jù)類型和數(shù)據(jù)間邏輯關(guān)系 ? 數(shù)據(jù)結(jié)構(gòu)的初步設(shè)計往往在算法設(shè)計之先 ? 注意數(shù)據(jù)結(jié)構(gòu)的可擴展性。 f(n)∈ Θ(g(n)) → f(n)=Θ(g(n)) g(n)是 f(n)的漸緊界 ? f(n)=Θ(g(n))表明 ， 當(dāng) n→ ∞時 ， f(n)和 g(n)趨于無窮大的階是相同的。 算法的特性 ? 算法的特性（續(xù)） ? 可行性 ? 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次來實現(xiàn)。 操作結(jié)果：用 ImagPart返回復(fù)數(shù) Z的虛部值。Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實部和虛部分別被賦以參數(shù) v1 和 v2 的值。 char name[20]。 ? 問題抽象 、數(shù)據(jù)抽象、算法抽象 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定 關(guān)系 的數(shù)據(jù) 元素 的集合 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) ? 圖 ?樹 ?二叉樹 ?線性表 ? 數(shù)據(jù)的 存儲結(jié)構(gòu) ? 順序方法、鏈接方法 ? 數(shù)據(jù)的 運算 ? 增、刪、查、改 ? 排序、檢索 存儲 數(shù)據(jù)結(jié)構(gòu) 邏輯 運算 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)（表示為結(jié)點集合 D），以及這些數(shù)據(jù)之間的一組二元關(guān)系（關(guān)系集合 S）來表示： ( D ， S ) ? 其中 ? D 是數(shù)據(jù)元素的有限集， 是由有限個結(jié)點組成的集合，每一個結(jié)點都代表一個數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù) ? S 是 D上關(guān)系的有限集， 是定義在集合 D上的一組關(guān)系，用它描述結(jié)點數(shù)據(jù)之間的邏輯關(guān)系 Data_Structures = (D, S) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 元素的數(shù)據(jù)類型 ? 高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱 ? 例 C語言中 ? 基本數(shù)據(jù)類型： int, char, float等 ? 構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、枚舉 ? 指針、空 (void)類型 ? 用戶也可用 typedef 自己定義數(shù)據(jù)類型 ? 結(jié)點的類型可以是基本數(shù)據(jù)類型，也可以根據(jù)應(yīng)用的需要來靈活定義 typedef struct { int num。 ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對象： 〈 數(shù)據(jù)對象的定義 〉 數(shù)據(jù)關(guān)系： 〈 數(shù)據(jù)關(guān)系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類型名 抽象數(shù)據(jù)類型 例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義： ADT Complex { 數(shù)據(jù)對象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 | e1是復(fù)數(shù)的實數(shù)部分； e2 是復(fù)數(shù)的虛數(shù)部分 } 基本操作： AssignComplex( amp。ImagPart ) 初始條件：復(fù)數(shù)已存在。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，相同的輸入只能得出相同的輸出。 算法分析舉例： InsertionSort InsertSort on the array A= 5,2,4,6,1,3 算法分析舉例： InsertionSort ? INSERTIONSORT(A) ? 1 for j← 2 to length[A] ? 2 do key ← A[j] ? 3 ★ Insert A[j] into the sorted sequence A[1… j1] ? 4 i ← j1 ? 5 while i0 and A[i]key ? 6
公司管理相關(guān)推薦
鄂ICP備17016276號-1