【正文】 數(shù)據(jù)結(jié)構(gòu)與算法（ C語(yǔ)言版）第 2版上 作者：郭龍?jiān)?、胡虛懷、何光明、戴仕? 第 1章 緒 論 本章主要內(nèi)容 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義 數(shù)據(jù)結(jié)構(gòu) 抽象數(shù)據(jù)類型 算法 算法分析 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 學(xué)習(xí)算法的意義 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 數(shù)據(jù)結(jié)構(gòu)為研究非數(shù)值計(jì)算問(wèn)題提供了數(shù)據(jù)的表示與操作途徑。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言是難以應(yīng)付眾多復(fù)雜課題的。要想有效地使用計(jì)算機(jī)，充分發(fā)揮計(jì)算機(jī)的功能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。扎實(shí)地打好“數(shù)據(jù)結(jié)構(gòu)”這門(mén)課程的基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)管理系統(tǒng)、軟件工程及人工智能等都是十分有益的。 學(xué)習(xí)算法的意義 學(xué)習(xí)和研究算法可以明確分析所得到的算法的好壞，尋找能滿足要求的較優(yōu)算法，從而更加高效地解決問(wèn)題。 學(xué)習(xí)算法設(shè)計(jì)的方法和算法分析的技術(shù)后，可以幫助我們?cè)O(shè)計(jì)較好的算法，分析算法的優(yōu)、缺點(diǎn)，從而找出解決某一問(wèn)題的最好方法。 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)概述 基本概念和相關(guān)術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)概述 數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中廣泛使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分構(gòu)成？以什么方式構(gòu)成？呈現(xiàn)什么樣的結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。 基本概念和相關(guān)術(shù)語(yǔ) ? 數(shù)據(jù) (data)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)分為兩類：數(shù)值型數(shù)據(jù) (主要用于數(shù)學(xué)計(jì)算等 )和非數(shù)值型數(shù)據(jù)(文字、圖形、圖像、音頻和視頻等 )。 ? 數(shù)據(jù)元素 (data element)是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。一個(gè)數(shù)據(jù)元素可由不可分割的若干個(gè)數(shù)據(jù)項(xiàng) (data item)組成。 ? 數(shù)據(jù)對(duì)象 (data object)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 ? 數(shù)據(jù)結(jié)構(gòu) (data structure)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素之間總是存在聯(lián)系的。把某一數(shù)據(jù)對(duì)象及該數(shù)據(jù)對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成的實(shí)體叫做數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有以下 4種基本結(jié)構(gòu)。 (1) 集合結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“屬于同一個(gè)集合”的關(guān)系，如圖 (a)所示。 (2) 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)一”的關(guān)系，如圖 (b)所示。 (3) 樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)多”的關(guān)系，如圖 (c)所示。 (4) 圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“多對(duì)多”的關(guān)系，如圖 (d)所示。 圖 4類基本數(shù)據(jù)結(jié)構(gòu)示意圖 ? 數(shù)據(jù)結(jié)構(gòu)的形式定義為 Data_Structure = (D, R) 其中， D是數(shù)據(jù)元素的有限集； R是 D上關(guān)系的有限集。 ? 數(shù)據(jù)結(jié)構(gòu)可以分為邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的形式化定義為邏輯結(jié)構(gòu)。物理結(jié)構(gòu)為數(shù)據(jù)在計(jì)算機(jī)中的表示，它包括數(shù)據(jù)元素的表示和關(guān)系表示。 ? 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序存儲(chǔ)和非順序存儲(chǔ)。順序存儲(chǔ)結(jié)構(gòu)是把邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的兩個(gè)單元中，它是一種最基本的存儲(chǔ)方法，一般采用數(shù)組來(lái)實(shí)現(xiàn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)邏輯上相鄰的元素不要求其物理位置也相鄰，元素間的邏輯關(guān)系通過(guò)指針來(lái)表示，一般采用鏈表來(lái)實(shí)現(xiàn)。 抽象數(shù)據(jù)類型 ? 抽象數(shù)據(jù)類型 (Abstract Data Type， ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 ? 抽象數(shù)據(jù)類型由元素、關(guān)系及操作 3種要素來(lái)定義。抽象數(shù)據(jù)類型用三元組來(lái)表示： (D、 R、 P) 其中： D是數(shù)據(jù)對(duì)象； R是 D上的關(guān)系集； P是對(duì) D的基本操作集。 ? 抽象數(shù)據(jù)類型名稱定義的一般形式為： ADT 抽象數(shù)據(jù)類型名稱 { 數(shù)據(jù)對(duì)象： ? 數(shù)據(jù)關(guān)系： ? 操作集合： 操作名 1。 ? ? 操作名 n。 }ADT抽象數(shù)據(jù)類型名稱 算 法 算法概述 算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系 算法的度量 算法概述 ? 算法 (Algorithm)是解題的步驟，是指令的有限序列。 ? 一個(gè)算法應(yīng)該具有以下特征： (1) 有窮性。對(duì)于任何合法的輸入值，一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束。 (2) 確定性。算法的每一步必須有確切的含義，無(wú)二義性，并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)相同的輸入只能得出相同的輸出。 (3) 輸入。一個(gè)算法有 0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂 0個(gè)輸入是指算法本身設(shè)定了初始條件。 (4) 輸出。一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的。 (5) 可行性。算法原則上能夠精確地運(yùn)行，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。 ? 對(duì)算法的學(xué)習(xí)包括下面 5個(gè)方面的內(nèi)容： (1) 設(shè)計(jì)算法。設(shè)計(jì)一個(gè)好的算法，通常要考慮正確性、可讀性、健壯性、高效性這幾個(gè)方面的要求。 (2) 描述算法。描述算法的方法有多種形式，例如自然語(yǔ)言和算法語(yǔ)言，各自有適用的環(huán)境和特點(diǎn)。 (3) 確認(rèn)算法。算法確認(rèn)的目的是使人們確信這一算法能夠正確無(wú)誤地工作，即該算法具有可計(jì)算性。 (4) 分析算法。算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析。 (5) 驗(yàn)證算法。用計(jì)算機(jī)語(yǔ)言描述的算法是否可計(jì)算、有效合理，須對(duì)程序進(jìn)行測(cè)試，測(cè)試程序的工作由調(diào)試和對(duì)算法運(yùn)行所需時(shí)間和空間進(jìn)行分析。 算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系 著名的計(jì)算機(jī)科學(xué)家沃思 (Nikiklaus Wirth)提出一個(gè)公式： 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 這個(gè)公式說(shuō)明了算法與數(shù)據(jù)結(jié)構(gòu)的重要性，也說(shuō)明了算法與數(shù)據(jù)結(jié)構(gòu)之間存在著相輔相成的關(guān)系。解決一個(gè)問(wèn)題可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，也可以選擇不同的算法。數(shù)據(jù)結(jié)構(gòu)的選擇決定著算法執(zhí)行時(shí)所需要的時(shí)間與空間，影響著算法的效率。反之，算法的優(yōu)劣又決定著某個(gè)數(shù)據(jù)結(jié)構(gòu)是否適合解決這個(gè)問(wèn)題。 算法的度量 ? 1. 算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度是指運(yùn)行算法時(shí)所需要消耗的時(shí)間資源。其定義是：如果一個(gè)問(wèn)題的規(guī)模是 n，解決這一問(wèn)題的某一算法所需要的時(shí)間為 T(n)，它是 n的某一函數(shù)。 T(n)就稱為算法的時(shí)間復(fù)雜度。當(dāng)輸入量 n逐漸增大時(shí)，時(shí)間復(fù)雜度的極限情形稱為算法的漸近時(shí)間復(fù)雜度。 ? 2. 算法的空間復(fù)雜度 算法的空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。存儲(chǔ)空間具體是指編寫(xiě)程序時(shí)，程序的存儲(chǔ)空間、變量占用空間、系統(tǒng)堆棧的使用空間等。 算 法 分 析 數(shù)學(xué)基礎(chǔ) 所需分析的問(wèn)題 運(yùn)行時(shí)間的計(jì)算 檢驗(yàn)?zāi)愕姆治? 數(shù)學(xué)基礎(chǔ) ? 定義 1 如果存在正常數(shù) c和，使得當(dāng) 時(shí)， 則記為 。 上述的定義用來(lái)描述算法的漸近時(shí)間復(fù)雜度，它表明，如果對(duì)于足夠大的 N，或大于某自然數(shù)，存在正數(shù) c，使得 T不大于 cf，則 T是 f的大 O表示。 T和 f的關(guān)系可以理解為 f(N)為 T(N)的一個(gè)上界，也可以理解為 T至多增長(zhǎng)得和 f一樣快。 ? 定義 2 如果存在正常數(shù) c和，使得當(dāng) 時(shí)， 則記為 。 上述定義表明，如果有一正數(shù) c，對(duì)于幾乎所有的 N，使得 T不小于 cf，則 T是 f的大表示，也就是說(shuō)， cf(N)是 T(N)的下界， T至少增長(zhǎng)得和 f一樣快。 0Nn≥ ( ) ( )T N cf N≤( ) ( ( ))T N O f N?0Nn≥( ) ( )T N cf N≥( ) ( ( ))T N f N??? 定義 3 如果存在正常數(shù) 、 和 ，使得當(dāng) 時(shí)， ，則記為 。 上述定義表明， T與 f有著相同的階數(shù)，或者兩者最終以相同的階數(shù)增長(zhǎng)。若 ，且 ，則 。 ? 上面這些函數(shù)定義的目的是要在函數(shù)間建立一種相對(duì)的級(jí)別，通常比較的是它們的相對(duì)增長(zhǎng)率 (relative rate of growth)。 ? 還需要掌握以下幾個(gè)重要的結(jié)論。 定理 1 如果 且 ，那么 (1) T1(N) + T2(N) = max(O(f(N)), O(g(N))) (2) T1(N) * T2(N) = O(f(N)*g(N)) 定理 2 如果 T(N)是一個(gè) k次多項(xiàng)式，則 T(N )= 。 1c 2c 0n 0Nn≥12( ) ( ) ( )c f N T N c f N≤ ≤ ( ) ( ( ))T N f N??( ) ( ( ))T N O f N? ( ) ( ( ))T N O f N? ( ) ( ( ))T N f N??1 ( ) ( ( ))T N O f N? 2 ( ) ( ( ))T N O g N?()kN? 所需分析的問(wèn)題 ? 在進(jìn)行分析時(shí)，要分析的最重要的資源一般來(lái)說(shuō)就是運(yùn)行時(shí)間。有一些因素影響著程序的運(yùn)行時(shí)間，但是諸如所使用的編譯器和計(jì)算機(jī)的性能這些因素不在考慮范圍之內(nèi)，只考慮所使用的算法以及對(duì)該算法的輸入。 ? 大多數(shù)情況下，把輸入的大小作為主要考慮的因素。定義兩個(gè)函數(shù) Tavg(N)和 Tworst(N)，分別是輸入量為 N時(shí)算法所花費(fèi)的平均運(yùn)行時(shí)間和最壞情況下的運(yùn)行時(shí)間。顯然，Tavg(N)≤ Tworst(N)。一般說(shuō)來(lái)，如果沒(méi)有明確指出，計(jì)算的時(shí)間復(fù)雜度為最壞情況下的運(yùn)行時(shí)間。其原因之一是它對(duì)所有的輸入提供了一個(gè)界限，包括特別壞的情況下的輸入，而平均時(shí)間復(fù)雜度不具有這個(gè)界限；還有一個(gè)原因是平均時(shí)間復(fù)雜度的計(jì)算較為復(fù)雜。 運(yùn)行時(shí)間的計(jì)算 計(jì)算運(yùn)行時(shí)間要遵循下面的法則。 1. 法則 1—— 賦值語(yǔ)句的運(yùn)行時(shí)間 每一條賦值語(yǔ)句的運(yùn)行時(shí)間為 1。 2. 法則 2—— for循環(huán)的運(yùn)行時(shí)間 一次 for循環(huán)的運(yùn)行時(shí)間至多是該 for循環(huán)內(nèi)語(yǔ)句 (包括測(cè)試 )的運(yùn)行時(shí)間乘以迭代的次數(shù)。 3. 法則 3—— 嵌套 for循環(huán)的運(yùn)行時(shí)間 從里面到外面分析這些循環(huán)。每一層循環(huán)的運(yùn)行時(shí)間等于該層