數(shù)據(jù)結(jié)構(gòu)第一章(文件)
【正文】 e Tel： 83683048 第一章 數(shù)據(jù)結(jié)構(gòu)和算法概述 本章內(nèi)容 問(wèn)題的求解 數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型 算法的概念和特性 算法的效率度量 漸進(jìn)表示法和漸進(jìn)記號(hào) 問(wèn)題求解 ? 階段和步驟 ? 獲取需求（問(wèn)題），以保證解決的問(wèn)題正是需要的（ solve the right problem）； ? 分析問(wèn)題，將其分解為粒度更小的部分； ? 針對(duì)問(wèn)題（子問(wèn)題）給出相應(yīng)的解決方案，易于理解和修改； ? 估算解決方案的開(kāi)銷，以事先判斷其可行性； ? 維護(hù)和演化 問(wèn)題求解 ? 通過(guò) ? 問(wèn)題抽象 ? 數(shù)據(jù)抽象 ? 算法抽象 分析問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)設(shè)計(jì)和實(shí)現(xiàn)高效的程序 問(wèn)題求解 ? 例子 ? 從一組人中找出最高、最矮，及身高最適中的人。 char name[20]。 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 關(guān)系 S闡明數(shù)據(jù)結(jié)構(gòu)的特性 ? 集合 ? 同屬于一個(gè)集合 ? 線性結(jié)構(gòu)（ linear structure） ? 一個(gè)對(duì)一個(gè) ? 線性關(guān)系；有向的；全序性和單索性 ? 樹(shù)形結(jié)構(gòu)（ tree structure） ? 一個(gè)對(duì)多個(gè) ? 層次關(guān)系；根節(jié)點(diǎn)；子結(jié)點(diǎn)和父結(jié)點(diǎn) ? 圖狀結(jié)構(gòu)（ graph structure） ? 多個(gè)對(duì)多個(gè) ? 網(wǎng)狀關(guān)系； 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)（ 邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象） ? 對(duì)于數(shù)據(jù)邏輯結(jié)構(gòu)（ D , S ） ? “數(shù)據(jù)元素”的映象 ? 對(duì)它的結(jié)點(diǎn)集合 D建立一個(gè)從 D到存儲(chǔ)器的單元的映射：對(duì)于每一個(gè)結(jié)點(diǎn) d∈ D都對(duì)應(yīng)一個(gè) 唯一的連續(xù)存儲(chǔ)區(qū)域 。Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值。realPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 ImagPart返回復(fù)數(shù) Z的虛部值。 } ADT Complex ? 對(duì)特定問(wèn)題求解過(guò)程的描述，是指令的有限序列，也即，為解決某一特定問(wèn)題而采取的有限的操作步驟。 算法的特性 ? 算法的特性（續(xù)） ? 可行性 ? 算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次來(lái)實(shí)現(xiàn)。運(yùn)行時(shí)間的下界 ? 最壞運(yùn)行時(shí)間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最慢或運(yùn)行步數(shù)最多時(shí)的運(yùn)行時(shí)間。 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ú)窮大的階是相同的。 ? 若 f(n)=Θ(g(n))，則一定有 f(n)=O(g(n))，反之不成立 漸近記號(hào) O The curves for f(n)=O(g(n)) 漸近記號(hào) O 例子： an3+bn2++d= O(n3), a0 例子： an2+bn+c= O(n3), a0 例子： nlgn＝ O(n2), 但是 nlgn≠Θ(n2) 漸近記號(hào) Ω Ω notation: 定義 ：給定一個(gè)函數(shù) g(n)， Ω (g(n))表示一個(gè)函數(shù)集合 Ω (g(n))＝｛ f(n)|存在正常數(shù) C和 n0使得當(dāng) n≥ n0，均有 0≤Cg(n)≤f(n)成立 ｝ 。 插入排序運(yùn)行時(shí)間 最好運(yùn)行時(shí)間 Ω(n) 最壞運(yùn)行時(shí)間 O(n2) 插入排序的運(yùn)行時(shí)間在 Ω(n)和 O(n2)之間 漸近記號(hào)與不等號(hào)的類比 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ù)類型和數(shù)據(jù)間邏輯關(guān)系 ? 數(shù)據(jù)結(jié)構(gòu)的初步設(shè)計(jì)往往在算法設(shè)計(jì)之先 ? 注意數(shù)據(jù)結(jié)構(gòu)的可擴(kuò)展性。 g(n)= (3) f(n)=nlogn+n。2 ( 1 ) 2 2n ini??? ? ? ?。 g(n)=3n n附加：常
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1