【正文】 JYP 1 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) (上 ) 教材： 《 數(shù)據(jù)結(jié)構(gòu)（ C++描述） 》（金遠平編著，清華大學出版社） JYP 2 第 1章 基本概念和方法 本章論述學習和研究數(shù)據(jù)結(jié)構(gòu)所必須的并且將反復出現(xiàn)的基本概念和方法。 JYP 3 數(shù)據(jù)結(jié)構(gòu)與軟件系統(tǒng) ? 設(shè)計解決實際問題的計算機軟件系統(tǒng)，首先需要建立被處理對象的數(shù)據(jù)模型。 ? 數(shù)據(jù)和世上萬物一樣，都是具有結(jié)構(gòu)的。人們很自然地用數(shù)據(jù)結(jié)構(gòu)表示應用領(lǐng)域的被處理對象。例如，樹和圖。 ? 數(shù)據(jù)結(jié)構(gòu) 由一個數(shù)據(jù)對象以及該對象中的所有數(shù)據(jù)元素之間的關(guān)系組成。 ? 數(shù)據(jù)元素 本身可以是數(shù)據(jù)結(jié)構(gòu)，因此，可以構(gòu)造非常復雜的數(shù)據(jù)結(jié)構(gòu)。 JYP 4 ? 為了模擬實際問題的求解過程和現(xiàn)實對象的行為，還必須提供對數(shù)據(jù)結(jié)構(gòu)的相應 操作 。 ? 數(shù)據(jù)結(jié)構(gòu)的 實現(xiàn) 是以下一層數(shù)據(jù)結(jié)構(gòu)表示上一層數(shù)據(jù)結(jié)構(gòu)，直至以程序設(shè)計語言提供的基本數(shù)據(jù)類型表示的過程。 ? 評價數(shù)據(jù)結(jié)構(gòu)表示能力的標準主要是它能否方便且有效地實現(xiàn)需要的操作，而實現(xiàn)操作的算法設(shè)計及其效率高低也依賴于數(shù)據(jù)結(jié)構(gòu)表示。 ? 數(shù)據(jù)結(jié)構(gòu)的定義、表示及其操作的實現(xiàn)相互關(guān)聯(lián)，都是數(shù)據(jù)結(jié)構(gòu)研究的重要內(nèi)容。 JYP 5 ? 計算機軟件系統(tǒng)可看成是通過不同層次的數(shù)據(jù)結(jié)構(gòu)及其操作實現(xiàn)的。例如： JYP 6 ? 中間層數(shù)據(jù)結(jié)構(gòu)起著核心作用，稱之為 建模層 。 ? 對數(shù)據(jù)結(jié)構(gòu)的研究產(chǎn)生了一批通用性強、具有很高實用價值的中間層數(shù)據(jù)結(jié)構(gòu)，如數(shù)組、字符串、集合、線性表、棧、隊列、鏈表、樹、圖、符號表等。 ? 系統(tǒng)地學習進而掌握數(shù)據(jù)結(jié)構(gòu)的知識和方法，對于提高設(shè)計與開發(fā)軟件系統(tǒng)尤其是復雜軟件系統(tǒng)的能力，無疑是十分重要的。 JYP 7 數(shù)據(jù) 抽象與封裝 ? 抽象和封裝的概念在日常生活中是普遍存在的，例如，人們常用的手機。 ? 通過 數(shù)據(jù)封裝 ，將一個數(shù)據(jù)對象的內(nèi)部結(jié)構(gòu)和實現(xiàn)細節(jié)對外屏蔽。 ? 通過 數(shù)據(jù)抽象 ，將一個數(shù)據(jù)對象的規(guī)格說明與其實現(xiàn)分離，對外提供簡潔、清晰的接口。 ? 數(shù)據(jù)結(jié)構(gòu)多層表示的過程反過來也就是從基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)到應用領(lǐng)域數(shù)據(jù)結(jié)構(gòu)的不斷抽象與封裝的過程。 JYP 8 ? 用抽象數(shù)據(jù)類型（ ADT）描述數(shù)據(jù)抽象與封裝是一種自然、有效的方法。 ? 數(shù)據(jù)類型 由一個數(shù)據(jù)對象的集合和一組作用于這些數(shù)據(jù)對象的操作組成。例如， C++的基本數(shù)據(jù)類型 char、 int、 float和 double等。 ? 抽象數(shù)據(jù)類型 是一個數(shù)據(jù)類型，該數(shù)據(jù)類型的組織遵循將數(shù)據(jù)對象及對這些數(shù)據(jù)對象的操作的規(guī)格說明與這些數(shù)據(jù)對象的表示、操作的實現(xiàn)相分離的原則。 JYP 9 ? 當強調(diào)一個數(shù)據(jù)對象的結(jié)構(gòu)時，使用數(shù)據(jù)結(jié)構(gòu)的概念。 ? 與數(shù)據(jù)結(jié)構(gòu)的概念對比，抽象數(shù)據(jù)類型包含了一個數(shù)據(jù)結(jié)構(gòu)的集合，還包含了對數(shù)據(jù)結(jié)構(gòu)的操作。 ? 抽象數(shù)據(jù)類型成為描述數(shù)據(jù)結(jié)構(gòu)及其操作的有效方式。 ? 定義 ADT的語言本質(zhì)上不依賴具體的程序設(shè)計語言，這里采用 C++描述。 JYP 10 例 抽象數(shù)據(jù)類型 ? 圓 ? 的定義為： class Circle { // 對象 : 幾何圓 public: Circle(float r)。 // 構(gòu)造函數(shù)，創(chuàng)建一個半徑為 r的對象實例 float Circumference( )。 // 返回該實例的周長 float Area( )。 // 返回該實例的面積 }。 該抽象數(shù)據(jù)類型的名稱為 Circle，數(shù)據(jù)對象定義為幾何圓，操作包括構(gòu)造函數(shù)、計算周長和面積等。注意：這些定義不依賴于數(shù)據(jù)對象的具體表示，也沒有給出操作實現(xiàn)的過程。 JYP 11 數(shù)據(jù)抽象和封裝機制的意義： （ 1） 簡化軟件開發(fā)： 假設(shè)一個問題經(jīng)分析將使用 A、 B、 C三個數(shù)據(jù)類型和協(xié)調(diào)代碼求解。 （ a）四位程序員，可由其中三位程序員各開發(fā)一個數(shù)據(jù)類型，另一位程序員實現(xiàn)協(xié)調(diào)代碼。 （ b）一位程序員，數(shù)據(jù)抽象也可減少其在某一具體時間需要考慮的范圍。 JYP 12 （ 2） 易于測試和排除錯誤： 如下圖所示，數(shù)據(jù)抽象明顯提高了測試和排除錯誤的效率。 JYP 13 （ 3）有利于重用： 數(shù)據(jù)抽象和封裝機制使開發(fā)人員可以將數(shù)據(jù)結(jié)構(gòu)及其操作實現(xiàn)為可重用的軟件組件。這些組件具有清晰的界面定義，更容易從一個軟件系統(tǒng)中提取出來，應用于另一個軟件系統(tǒng)。 （ 4）便于改變數(shù)據(jù)類型的表示： 由于數(shù)據(jù)封裝，外界不能直接訪問數(shù)據(jù)類型的內(nèi)部表示。因此，只要操作接口不變，數(shù)據(jù)類型內(nèi)部表示和實現(xiàn)的改變不會影響使用該數(shù)據(jù)類型的其他程序。 JYP 14 算法定義 數(shù)據(jù)結(jié)構(gòu)的操作實際上是以算法的形式實現(xiàn)的。 定義： 算法 是一個有限的指令集合，執(zhí)行這些指令可以完成某一特定任務。一個算法還應當滿足以下特性： 輸入 零個或多個由外界提供的輸入量。 輸出 至少產(chǎn)生一個輸出量。 確定性 每一指令都有確切的語義，無歧義。 有限性 在執(zhí)行有限步驟后結(jié)束。 有效性 每一條指令都應能經(jīng)過有限層的表示轉(zhuǎn)化為計算平臺的基本指令，即算法的指令必須是可行的。 JYP 15 ? 程序和算法不同，程序可以不滿足有限性。例 如，一個軟件的總控程序在未接受新的任務之前一直處于 ? 等待 ? 循環(huán)中。 ? 實現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作的程序總是可結(jié)束的，因此，后面將不再嚴格區(qū)分算法和程序這兩個術(shù)語。 ? 必須保證指令的有效性，例如，指令 ? if （哥德巴赫猜想是真） then x = y； ? 是無效的。 作業(yè)： P25—3 JYP 16 遞歸算法 ? 直接遞歸 ：函數(shù)在執(zhí)行過程中調(diào)用本身。 ? 間接遞歸 ：函數(shù)在執(zhí)行過程中調(diào)用其它函數(shù)再經(jīng)過這些函數(shù)調(diào)用本身。 ? 表達力： 函數(shù)定義 賦值 ifelse while 函數(shù)定義 賦值 ifelse 遞歸 JYP 17 ? 當問題本身是遞歸定義的，其解法適合用遞歸描述。 例 階乘函數(shù)的定義是 1 當 n=1 n! = n(n1)！ 當 n1 用遞歸方法計算階乘函數(shù)簡明扼要，易于理解，如下所示： long Factorial ( long n ) { if ( n = = 1 ) return 1。 // 終止條件 else return n*Factorial ( n1)。 // 遞歸步驟 } JYP 18 用參數(shù) n= 5調(diào)用 Factorial的過程如下： Factorial (5) = (5* Factorial (4)) = (5* (4* Factorial (3))) = (5* (4* (3* Factorial (2)))) = (5* (4* (3* (2* Factorial (1))))) = (5* (4* (3* (2* 1)))) = (5* (4* (3* 2))) = (5* (4* 6)) = (5* 24) = 120 JYP 19 ? 遞歸算法有四個特性： （ 1） 必須有可最終達到的終止條件 ， 否則程序?qū)⑾萑霟o窮循環(huán)； （ 2） 子問題在規(guī)模上比原問題小 ， 或更接近終止條件； （ 3） 子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解； （ 4） 子問題的解應能組合為整個問題的解 。 JYP 20 例 全排列生成器：給定一個具有 n≥1 個元素的集合，打印該集合的全排列。 分析四個元素 (a， b， c， d)的情況，結(jié)果可以如下構(gòu)造： （ 1） a后接 (b， c， d)的全排列 （ 2） b后接 (a， c， d)的全排列 （ 3） c后接 (a， b， d)的全排列 （ 4） d后接 (a， b， c)的全排列 這表明，如果能生成 n – 1個元素的全排列，就能生成 n個元素的全排列。 JYP 21 對于只有 1個元素的集合，可以直接生成其全排列。于是，全排列生成問題的遞歸步驟和終止條件可以確定。 求解函數(shù) perm： void perm (char *a, const int k， const int n) { // n 是數(shù)組 a的元素個數(shù)，生成 a[k],…,a[n 1]的全排列 int i。 if (k = = n1) { // 終止條件，輸出排列 for ( i=0。 in。 i++) cout a[i] “ ”。 // 輸出包括前 // 綴，以構(gòu)成整個問題的解 cout endl。 } JYP 22 else { // a[k],…,a[n 1] 的排列大于 1，遞歸生成 for ( i = k。 i n。 i++) { char temp = a[k]。 a[k] = a[i]。 a[i] = temp。 // 交換 a[k] // 和 a[i] perm(a,k+1,n)。 // 生成 a[k+1],…,a[n 1]的全排列 temp = a[k]。 a[k] = a[i]。 a[i] = temp。 // 再次交換 a[k] 和 // a[i] , 恢復原順序 } } // else結(jié)束 } // perm結(jié)束 通過調(diào)用 perm(a, 0, n)，可以生成 n個元素的全排列。 JYP 23 用 n = 3 和 a[0..2] = (a, b, c)調(diào)用 perm的示意如下： JYP 24 ? 當算法操作的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的時候也適合使用遞歸。后面將有許多此類的重要例子 。 作業(yè)： P25—5， 6 JYP 25 性能分析 ? 除了正確性、可用性、可讀性和容錯性以外， 算法的性能 是評價算法優(yōu)劣的重要指標。 ? 空間復雜性 ：算法開始運行直至結(jié)束過程中所需要的最大存儲資源開銷的一種度量。 ? 時間復雜性 ：算法開始運行直至結(jié)束所需要的執(zhí)行時間的一種度量。 ? 性能評價 分為 事前估計 和 事后測量 。 ? 性能分析 就是指對算法的空間復雜性和時間復雜性進行事前估計。 JYP 26 空間復雜性 ? 程序 P的空間需求 S(P) = c + SP(實例特性 ) 其中， c是常數(shù)， SP(實例特性 ) 是實例特性的函數(shù)。 ? 分析的重點是 SP(實例特性 )。 ? 對于一個給定問題，首先要確定其實例特性，才可能分析求解算法的空間要求。 ? 確定實例特性與具體問題密切相關(guān)。 JYP 27 例如 : 1 float rsum (float *a, const int n) { 2 if (n = 0 ) return 0。 // 當 n = 1時返回 a[0] 3 else return rsum( a, n–1) + a[n–1]。 4 } rsum是一個遞歸求和算法，其實例特性是 n。每次遞歸調(diào)用需在棧頂保存 n的值、 a的值、返回值和返回地址，共需 4個存儲單元。 由于算法的遞歸深度是 n+1，故所需棧空間是4(n+1)，即 Srsum(n) = 4(n+1)。 JYP 28 時間復雜性 ? 算法 P的運行時間 T(P) = c + TP(實例特性 ) ? 時間復雜性分析的目的在于揭示算法的運行時間隨著其實例特性變化的規(guī)律。 ? 將一組與實例特性無關(guān)的操作抽象為一個程序步，從而有效地簡化性能分析的過程。 ? 程序步 ：算法中的一個在語法和語義上有意義的指令序列，而且該序列執(zhí)行時間與算法的實例特性無關(guān)。 JYP 29 ? 各類 C++語句的程序步數(shù)詳見教科書。 ? 可以通過列出各個語句的程序步數(shù)確定整個程序的程序步數(shù)。 例 程序 sum： 1 float sum (float *a, const int n) { 2 float