數(shù)據(jù)結(jié)構(gòu)第一章(存儲(chǔ)版)
【正文】 插入排序運(yùn)行時(shí)間 最好運(yùn)行時(shí)間 Ω(n) 最壞運(yùn)行時(shí)間 O(n2) 插入排序的運(yùn)行時(shí)間在 Ω(n)和 O(n2)之間 漸近記號(hào)與不等號(hào)的類(lèi)比 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)的選擇和評(píng)價(jià) ? 仔細(xì)分析所要解決的問(wèn)題，特別是求解問(wèn)題所涉及的數(shù)據(jù)類(lèi)型和數(shù)據(jù)間邏輯關(guān)系 ? 數(shù)據(jù)結(jié)構(gòu)的初步設(shè)計(jì)往往在算法設(shè)計(jì)之先 ? 注意數(shù)據(jù)結(jié)構(gòu)的可擴(kuò)展性。 f(n)∈ Θ(g(n)) → f(n)=Θ(g(n)) g(n)是 f(n)的漸緊界 ? f(n)=Θ(g(n))表明 ， 當(dāng) n→ ∞時(shí) ， f(n)和 g(n)趨于無(wú)窮大的階是相同的。 算法的特性 ? 算法的特性（續(xù)） ? 可行性 ? 算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次來(lái)實(shí)現(xiàn)。 操作結(jié)果：用 ImagPart返回復(fù)數(shù) Z的虛部值。Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值。 char name[20]。 ? 問(wèn)題抽象 、數(shù)據(jù)抽象、算法抽象 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定 關(guān)系 的數(shù)據(jù) 元素 的集合 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) ? 圖 ?樹(shù) ?二叉樹(shù) ?線(xiàn)性表 ? 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) ? 順序方法、鏈接方法 ? 數(shù)據(jù)的 運(yùn)算 ? 增、刪、查、改 ? 排序、檢索 存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu) 邏輯 運(yùn)算 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)（表示為結(jié)點(diǎn)集合 D），以及這些數(shù)據(jù)之間的一組二元關(guān)系（關(guān)系集合 S）來(lái)表示： ( D ， S ) ? 其中 ? D 是數(shù)據(jù)元素的有限集， 是由有限個(gè)結(jié)點(diǎn)組成的集合，每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù) ? S 是 D上關(guān)系的有限集， 是定義在集合 D上的一組關(guān)系，用它描述結(jié)點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系 Data_Structures = (D, S) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 元素的數(shù)據(jù)類(lèi)型 ? 高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱(chēng) ? 例 C語(yǔ)言中 ? 基本數(shù)據(jù)類(lèi)型： int, char, float等 ? 構(gòu)造數(shù)據(jù)類(lèi)型：數(shù)組、結(jié)構(gòu)體、共用體、枚舉 ? 指針、空 (void)類(lèi)型 ? 用戶(hù)也可用 typedef 自己定義數(shù)據(jù)類(lèi)型 ? 結(jié)點(diǎn)的類(lèi)型可以是基本數(shù)據(jù)類(lèi)型，也可以根據(jù)應(yīng)用的需要來(lái)靈活定義 typedef struct { int num。 ADT 抽象數(shù)據(jù)類(lèi)型名 { 數(shù)據(jù)對(duì)象： 〈 數(shù)據(jù)對(duì)象的定義 〉 數(shù)據(jù)關(guān)系： 〈 數(shù)據(jù)關(guān)系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類(lèi)型名 抽象數(shù)據(jù)類(lèi)型 例如，抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義： ADT Complex { 數(shù)據(jù)對(duì)象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 | e1是復(fù)數(shù)的實(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號(hào)-1