【正文】 后置條件 ：執(zhí)行該操作后數(shù)據(jù)的狀態(tài) 操作 2 …… …… 操作 n …… endADT ADT的定義形式 數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)） 數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 集合 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu) 非數(shù)值問題 數(shù)據(jù)表示 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法的相關(guān)概念 （ Algorithm） :是對 特定問題 求解步驟的一種描述 ， 是 指令 的 有限序列 。 2. 算法的五大特性： ⑴ 輸入 ：一個(gè)算法有零個(gè)或多個(gè)輸入。 ⑵ 輸出 ：一個(gè)算法有一個(gè)或多個(gè)輸出。 ⑶ 有窮性 ：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。 ⑷ 確定性 ：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。 ⑸ 可行性 ：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 歐幾里德算法 m n r 例：歐幾里德算法 —— 輾轉(zhuǎn)相除法求兩個(gè)自然數(shù) m 和 n 的最大公約數(shù) 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法的描述方法 ——自然語言 優(yōu)點(diǎn)：容易理解 缺點(diǎn)：冗長、二義性 使用方法：粗線條描述算法思想 注意事項(xiàng)：避免寫成自然段 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 ① 輸入 m 和 n； ② 求 m除以 n的余數(shù) r； ③ 若 r等于 0， 則 n為最大公約數(shù) ，算法結(jié)束；否則執(zhí)行第 ④ 步； ④ 將 n的值放在 m中 ， 將 r的值放在 n中； ⑤ 重新執(zhí)行第 ② 步 。 例：歐幾里德算法 自然語言 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 優(yōu)點(diǎn)：流程直觀 缺點(diǎn)：缺少嚴(yán)密性、靈活性 使用方法：描述簡單算法 注意事項(xiàng)：注意抽象層次 算法的描述方法 ——流程圖 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 N 開始 輸入 m和 n r=m % n r=0 m=n； n=r 輸出 n 結(jié)束 Y 流 程 圖 例：歐幾里德算法 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行 缺點(diǎn)：抽象性差，對語言要求高 使用方法：算法需要驗(yàn)證 注意事項(xiàng)：將算法寫成子函數(shù) 算法的描述方法 ——程序設(shè)計(jì)語言 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 include int CommonFactor(int m, int n) { int r=m % n。 while (r!=0) { m=n。 n=r。 r=m % n。 } return n。 } void main( ) { coutCommonFactor(63, 54)endl。 } 程序設(shè)計(jì)語言 例：歐幾里德算法 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 偽代碼 （ Pseudocode）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。 優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解 使用方法： 7 177。 2 算法的描述方法 ——偽代碼 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 1. r = m % n。 2. 循環(huán)直到 r 等于 0 m = n。 n = r。 r = m % n。 3. 輸出 n 。 偽 代 碼 上述偽代碼再具體一些，用 C++的函數(shù)來描述。請同學(xué)們自行完成！ 例：歐幾里德算法 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法分析 度量算法效率的方法： ? 事后統(tǒng)計(jì) ：將算法實(shí)現(xiàn) ， 測算其時(shí)間和空間開銷 。 缺點(diǎn)： ⑴ 編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力； ⑵ 所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素 。 ? 事前分析 ：對算法所消耗資源的一種估算方法 。 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法分析 算法分析 （ Algorithm Analysis） ：對算法所需要的計(jì)算機(jī)資源 ——時(shí)間 和 空間 進(jìn)行估算 。 時(shí)間復(fù)雜性（ Time Complexity） 空間復(fù)雜性（ Space Complexity） 算法及算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 算法的時(shí)間復(fù)雜度分析 算法及算法分析 算法分析 算法的 執(zhí)行時(shí)間 ＝每條語句執(zhí)行時(shí)間之和 執(zhí)行次數(shù) 執(zhí)行一次的時(shí)間 指令系統(tǒng) 、 編譯的代碼質(zhì)量 單位時(shí)間 每條語句 執(zhí)行次數(shù) 之和 for (i=1。 i=n。 i++) for (j=1。 j=n。 j++) x++。 基本語句 的執(zhí)行次數(shù) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 問題規(guī)模： 輸入量的多少 。 基本語句： 是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次 數(shù)成正比的操作指令 。 for (i=1。 i=n。 i++) for (j=1。 j=n。 j++) x++。 問題規(guī)模： n 基本語句： x++ 算法及算法分析 算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 定義 若存在兩個(gè)正的常數(shù) c和 n0，對于任意 n≥ n0，都有 T(n)≤ c f(n)，則稱 T(n)=O(f(n)) n0 問題規(guī)模 n 執(zhí)行次數(shù) n0之前的情況無關(guān)緊要 T(n) c f(n) ?當(dāng)問題規(guī)模充分大時(shí)在漸近意義下的階 算法及算法分析 算法分析 ——大 O符號(hào) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 定理：若 A(n)=amnm+am1nm1+? +a1n+a0是一個(gè)m次多項(xiàng)式 ， 則 A(n)=O(nm)。 說明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)。 算法及算法分析 算法分析 ——大 O符號(hào) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 例 15 ++x。 例 16 for (i=1。 i=n。 ++i) ++x。 例 17 for (i=1。 i=n。 ++i) for (j=1。 j=n。 ++j) ++x。 例 18 for (i=1。 i=n。 ++i) for (j=1。 j=i1。 ++j) ++x。 算法及算法分析 算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 例 19 for (i=1。 i=n。 ++i) for (j=1。 j=n。 ++j) { c[i][j]=0。 for (k=1。 k=n。 ++k) c[i][j]+=a[i][k]*b[k][j]。 } 例 110 for (i=1。 i=n。 i=2*i) ++x。 Ο(1)＜ Ο(log2n)＜ Ο(n)＜ Ο(nlog2n)＜ Ο(n2)＜ Ο(n3) ＜ … ＜ Ο(2n)＜ Ο(n!) 算法及算法分析 算法分析 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 最好情況、最壞情況、平均情況 例：在一維整型數(shù)組 A[n]中順序查找與給定值 k相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為 k） 。 int Find(int A[ ], int n) { for (i=0。 in。 i++) if (A[i]= =k) break。 return i。 } 算法及算法分析 基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關(guān)？ 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 ?最好情況：出現(xiàn)概率較大時(shí)分析 ?最差情況：實(shí)時(shí)系統(tǒng) ?平均情況：已知輸入數(shù)據(jù)是如何分布的， 通常假設(shè)等概率分布 結(jié)論 ：如果問題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。 算法及算法分析 最好情況、最壞情況、平均情況 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 本章小結(jié) ——知識(shí)結(jié)構(gòu)圖 緒 論 數(shù)據(jù)結(jié)構(gòu) 算 法 基本概念 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) ⑴ 數(shù)據(jù) ⑵ 數(shù)據(jù)元素 ⑶ 數(shù)據(jù)對象 ⑷ ADT ⑴ 邏輯結(jié)構(gòu) ⑵ 數(shù)據(jù)結(jié)構(gòu) 的分類 ⑴ 存儲(chǔ)結(jié)構(gòu) ⑵ 常用存儲(chǔ) 方法 基本概念 算法分析 ⑴ 算法 ⑵ 算法特性 ⑶ 評價(jià)算法 ⑷ 描述算法 ⑴ 問題規(guī)模 ⑵ 基本語句 ⑶ 時(shí)間復(fù)雜度 ⑷ 大 O記號(hào) 關(guān) 系 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 作業(yè)： 公元 5世紀(jì)末，我國古代數(shù)學(xué)家張丘建在它所撰定的《算經(jīng)》中，提出這樣一個(gè)問題：“雞翁一，值錢五；雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問雞翁、母、雛各幾何？”意思是說公雞每只 5元，母雞每只 3元，小雞 3只 1元，用 100元錢買 100只雞，求公雞、母雞、小雞的只數(shù)。試設(shè)計(jì)算法求解該問題，并分析你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。（要求：算法分別用偽代碼和 C＋＋描述） 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 第二章 線性表 ? 線性表的邏輯結(jié)構(gòu) ? 線性表的順序存儲(chǔ)及實(shí)現(xiàn) ? 線性表的鏈接存儲(chǔ)及實(shí)現(xiàn) ? 順序表和單鏈表的比較 ? 線性表的其他存儲(chǔ)及實(shí)現(xiàn) 本章的基本內(nèi)容是： 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 學(xué)生成績登記表 線性表的邏輯結(jié)構(gòu) 姓 名 英語 數(shù)據(jù)結(jié)構(gòu) 高數(shù) 學(xué)號(hào) 丁一 96 78 87 0101 李二 87 90 78 0102 張三 67 86 86 0103 孫紅 69 81 96 0104 王冬 87 74 66 0105 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 職工工資登記表 線性表的邏輯結(jié)構(gòu) 姓 名 崗位津貼 基本工資 獎(jiǎng)金 職工號(hào) 丁一 600 278 200 0101 李二 300 190 100 0102 張三 300 186 100 0103 孫紅 500 218 200 0104 王冬 300 190 100 0105 數(shù)據(jù)元素之間的關(guān)系是什么？ 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表： 簡稱表，是 n（ n≥0）個(gè)具有 相同類型 的數(shù)據(jù)元素的 有限序 列 。 線性表的長度： 線性表中數(shù)據(jù)元素的個(gè)數(shù)。 空表： 長度等于零的線性表， 記為： L=( )。 非空表 記為： L＝（ a1, a2 , …, ai1, ai , … , an) 線性表的邏輯結(jié)構(gòu) 線性表的定義 其中， ai（ 1≤i≤n）稱為數(shù)據(jù)元素； 下角標(biāo) i 表示該元素在線性表中的位置或序號(hào) 。 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 a1 a3 a4 an a2 線性表的邏輯結(jié)構(gòu) 線性表的圖形表示 線性表 （ a1, a2 , …, ai1, ai , … , an)的圖形表示如下： 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 a1 a3 a4 an a2 線性表的邏輯結(jié)構(gòu) 線性表的特性 ：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有