數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt

數(shù)據(jù)結(jié)構(gòu)與算法（C語言版）第2版上作者：郭龍源、胡虛懷、何光明、戴仕明數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第1頁。第1章緒論數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第2頁。本章主要內(nèi)容1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義1.2數(shù)據(jù)結(jié)構(gòu)1.3抽象數(shù)據(jù)類型1.4算法1.5算法分析數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第3頁。1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義1.1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1.1.2學(xué)習(xí)算法的意義

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第4頁。1.1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

數(shù)據(jù)結(jié)構(gòu)為研究非數(shù)值計算問題提供了數(shù)據(jù)的表示與操作途徑。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運用計算機(jī)來解決實際問題，僅掌握幾種計算機(jī)程序設(shè)計語言是難以應(yīng)付眾多復(fù)雜課題的。要想有效地使用計算機(jī)，充分發(fā)揮計算機(jī)的功能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。扎實地打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的基礎(chǔ)，對于學(xué)習(xí)計算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫管理系統(tǒng)、軟件工程及人工智能等都是十分有益的。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第5頁。1.1.2學(xué)習(xí)算法的意義

學(xué)習(xí)和研究算法可以明確分析所得到的算法的好壞，尋找能滿足要求的較優(yōu)算法，從而更加高效地解決問題。學(xué)習(xí)算法設(shè)計的方法和算法分析的技術(shù)后，可以幫助我們設(shè)計較好的算法，分析算法的優(yōu)、缺點，從而找出解決某一問題的最好方法。

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第6頁。1.2數(shù)據(jù)結(jié)構(gòu)

1.2.1數(shù)據(jù)結(jié)構(gòu)概述1.2.2基本概念和相關(guān)術(shù)語

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第7頁。1.2.1數(shù)據(jù)結(jié)構(gòu)概述

數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域中廣泛使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(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ī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第8頁。1.2.2基本概念和相關(guān)術(shù)語

數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)分為兩類：數(shù)值型數(shù)據(jù)(主要用于數(shù)學(xué)計算等)和非數(shù)值型數(shù)據(jù)(文字、圖形、圖像、音頻和視頻等)。數(shù)據(jù)元素(dataelement)是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。一個數(shù)據(jù)元素可由不可分割的若干個數(shù)據(jù)項(dataitem)組成。數(shù)據(jù)對象(dataobject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)(datastructure)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間總是存在聯(lián)系的。把某一數(shù)據(jù)對象及該數(shù)據(jù)對象中所有數(shù)據(jù)成員之間的關(guān)系組成的實體叫做數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有以下4種基本結(jié)構(gòu)。

(1)集合結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“屬于同一個集合”的關(guān)系，如圖1.2(a)所示。

(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對一”的關(guān)系，如圖1.2(b)所示。

(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對多”的關(guān)系，如圖1.2(c)所示。

(4)圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“多對多”的關(guān)系，如圖1.2(d)所示。圖1.24類基本數(shù)據(jù)結(jié)構(gòu)示意圖數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第10頁。數(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ī)中的表示，它包括數(shù)據(jù)元素的表示和關(guān)系表示。數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有兩種不同的表示方法：順序存儲和非順序存儲。順序存儲結(jié)構(gòu)是把邏輯上相鄰的元素存儲在物理位置相鄰的兩個單元中，它是一種最基本的存儲方法，一般采用數(shù)組來實現(xiàn)。鏈?zhǔn)酱鎯Y(jié)構(gòu)對邏輯上相鄰的元素不要求其物理位置也相鄰，元素間的邏輯關(guān)系通過指針來表示，一般采用鏈表來實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第11頁。1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(AbstractDataType，ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型由元素、關(guān)系及操作3種要素來定義。抽象數(shù)據(jù)類型用三元組來表示：

(D、R、P)

其中：D是數(shù)據(jù)對象；R是D上的關(guān)系集；P是對D的基本操作集。抽象數(shù)據(jù)類型名稱定義的一般形式為：

ADT抽象數(shù)據(jù)類型名稱{

數(shù)據(jù)對象：

…

數(shù)據(jù)關(guān)系：

…

操作集合：操作名1;……

操作名n;}ADT抽象數(shù)據(jù)類型名稱數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第12頁。1.4算法1.4.1算法概述1.4.2算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系1.4.3算法的度量數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第13頁。1.4.1算法概述算法(Algorithm)是解題的步驟，是指令的有限序列。一個算法應(yīng)該具有以下特征：

(1)有窮性。對于任何合法的輸入值，一個算法必須保證執(zhí)行有限步之后結(jié)束。

(2)確定性。算法的每一步必須有確切的含義，無二義性，并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對相同的輸入只能得出相同的輸出。

(3)輸入。一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身設(shè)定了初始條件。

(4)輸出。一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。

(5)可行性。算法原則上能夠精確地運行，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第14頁。對算法的學(xué)習(xí)包括下面5個方面的內(nèi)容：

(1)設(shè)計算法。設(shè)計一個好的算法，通常要考慮正確性、可讀性、健壯性、高效性這幾個方面的要求。

(2)描述算法。描述算法的方法有多種形式，例如自然語言和算法語言，各自有適用的環(huán)境和特點。

(3)確認(rèn)算法。算法確認(rèn)的目的是使人們確信這一算法能夠正確無誤地工作，即該算法具有可計算性。

(4)分析算法。算法分析是對一個算法需要多少計算時間和存儲空間作定量分析。

(5)驗證算法。用計算機(jī)語言描述的算法是否可計算、有效合理，須對程序進(jìn)行測試，測試程序的工作由調(diào)試和對算法運行所需時間和空間進(jìn)行分析。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第15頁。1.4.2算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系

著名的計算機(jī)科學(xué)家沃思(NikiklausWirth)提出一個公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序這個公式說明了算法與數(shù)據(jù)結(jié)構(gòu)的重要性，也說明了算法與數(shù)據(jù)結(jié)構(gòu)之間存在著相輔相成的關(guān)系。解決一個問題可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，也可以選擇不同的算法。數(shù)據(jù)結(jié)構(gòu)的選擇決定著算法執(zhí)行時所需要的時間與空間，影響著算法的效率。反之，算法的優(yōu)劣又決定著某個數(shù)據(jù)結(jié)構(gòu)是否適合解決這個問題。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第16頁。1.4.3算法的度量1.算法的時間復(fù)雜度算法的時間復(fù)雜度是指運行算法時所需要消耗的時間資源。其定義是：如果一個問題的規(guī)模是n，解決這一問題的某一算法所需要的時間為T(n)，它是n的某一函數(shù)。T(n)就稱為算法的時間復(fù)雜度。當(dāng)輸入量n逐漸增大時，時間復(fù)雜度的極限情形稱為算法的漸近時間復(fù)雜度。2.算法的空間復(fù)雜度算法的空間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量。存儲空間具體是指編寫程序時，程序的存儲空間、變量占用空間、系統(tǒng)堆棧的使用空間等。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第17頁。1.5算法分析1.5.1數(shù)學(xué)基礎(chǔ)1.5.2所需分析的問題1.5.3運行時間的計算1.5.4檢驗?zāi)愕姆治鰯?shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第18頁。1.5.1數(shù)學(xué)基礎(chǔ)定義

1

如果存在正常數(shù)c和，使得當(dāng)時，則記為。上述的定義用來描述算法的漸近時間復(fù)雜度，它表明，如果對于足夠大的N，或大于某自然數(shù)，存在正數(shù)c，使得T不大于cf，則T是f的大O表示。T和f的關(guān)系可以理解為f(N)為T(N)的一個上界，也可以理解為T至多增長得和f一樣快。定義

2

如果存在正常數(shù)c和，使得當(dāng)時，則記為。上述定義表明，如果有一正數(shù)c，對于幾乎所有的N，使得T不小于cf，則T是f的大表示，也就是說，cf(N)是T(N)的下界，T至少增長得和f一樣快。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第19頁。定義

3

如果存在正常數(shù)、和，使得當(dāng)時，，則記為。上述定義表明，T與f有著相同的階數(shù)，或者兩者最終以相同的階數(shù)增長。若，且，則。上面這些函數(shù)定義的目的是要在函數(shù)間建立一種相對的級別，通常比較的是它們的相對增長率(relativerateofgrowth)。還需要掌握以下幾個重要的結(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)是一個k次多項式，則T(N)=。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第20頁。1.5.2所需分析的問題在進(jìn)行分析時，要分析的最重要的資源一般來說就是運行時間。有一些因素影響著程序的運行時間，但是諸如所使用的編譯器和計算機(jī)的性能這些因素不在考慮范圍之內(nèi)，只考慮所使用的算法以及對該算法的輸入。大多數(shù)情況下，把輸入的大小作為主要考慮的因素。定義兩個函數(shù)Tavg(N)和Tworst(N)，分別是輸入量為N時算法所花費的平均運行時間和最壞情況下的運行時間。顯然，Tavg(N)≤Tworst(N)。一般說來，如果沒有明確指出，計算的時間復(fù)雜度為最壞情況下的運行時間。其原因之一是它對所有的輸入提供了一個界限，包括特別壞的情況下的輸入，而平均時間復(fù)雜度不具有這個界限；還有一個原因是平均時間復(fù)雜度的計算較為復(fù)雜。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第21頁。1.5.3運行時間的計算

計算運行時間要遵循下面的法則。

1.法則1——賦值語句的運行時間每一條賦值語句的運行時間為1。

2.法則2——for循環(huán)的運行時間一次for循環(huán)的運行時間至多是該for循環(huán)內(nèi)語句(包括測試)的運行時間乘以迭代的次數(shù)。

3.法則3——嵌套for循環(huán)的運行時間從里面到外面分析這些循環(huán)。每一層循環(huán)的運行時間等于該層的for循環(huán)語句的運行時間乘以該層循環(huán)內(nèi)所有的for循環(huán)的運行時間。

4.法則4——順序語句的運行時間將各個語句的運行時間求和即可，根據(jù)1.5.1小節(jié)中的定理1中的(1)可知，總的運行時間為其中的最大值。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第22頁。5.法則5——IF/ELSE語句的運行時間對于以下程序片段

if(condition)S1elseS2

它的運行時間不超過判斷再加上S1與S2中運行時間的最長者。顯然這種估計在有些情況下會過高，但是絕不會估計過低。6.法則6——遞歸函數(shù)的復(fù)雜度分析遞歸函數(shù)的復(fù)雜度分析比較困難。

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第23頁。1.5.4檢驗?zāi)愕姆治?/p>

算法分析一旦結(jié)束，就需要對所分析得到的結(jié)果進(jìn)行檢查。一種可行的方法是編寫程序并比較實際觀察到的運行時間，與通過分析得到的描述時間是否匹配。另一種驗證一個程序的運行時間是否是O(f(N))的方法是對N進(jìn)行不同的取值，并計算比值T(N)/f(N)，其中T(N)是憑經(jīng)驗觀察到的運行時間。在實際驗證時，由于計算機(jī)計算得很快，很難估計其運行時間?？梢圆捎媒y(tǒng)計關(guān)鍵語句的執(zhí)行次數(shù)來代替T(N)和f(N)。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第24頁。第2章線性表數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第25頁。本章主要內(nèi)容2.1線性表的定義2.2線性表的順序存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4線性表的應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第26頁。2.1線性表的定義2.1.1線性表概述2.1.2線性表的抽象數(shù)據(jù)類型2.1.3線性表的相關(guān)操作

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第27頁。2.1.1線性表概述

線性表(Linear_List)是數(shù)據(jù)結(jié)構(gòu)中最常用和最簡單的結(jié)構(gòu)。在線性表中，數(shù)據(jù)間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其他數(shù)據(jù)元素都是首尾相接的。并且，線性表中的數(shù)據(jù)元素的類型是相同的。線性表的數(shù)學(xué)定義如下：線性表是具有相同類型的n(n≥0)個數(shù)據(jù)元素組成的序列，通常用下面的形式來表示：

L=(a1,a2,a3,…,an)

其中：L為表的名稱；ai(i=1,2,…,n)為表的元素；n為線性表的表長。當(dāng)n=0時，則稱線性表為空表。線性表的邏輯結(jié)構(gòu)簡單，便于實現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第28頁。2.1.2線性表的抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型的定義為：

ADTLinear_List{數(shù)據(jù)對象：任意數(shù)據(jù)元素的集合

D={ai|ai∈elementset,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：除第一個和最后一個外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。

R={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n,n≥0}基本操作：

ListInit(L) //初始化操作。構(gòu)造一個空的線性表LListLength(L) //求線性表長度。返回線性表L中所含元素的個數(shù)

ListGet(L,i) //取元素。若1≤i≤ListLength(L)，返回線性表L中第i個元素；否則返為NULL。這里稱i為該元素在線性表L中的位序

ListLocate(L,x) //定位函數(shù)。若線性表L中存在其值和x相等的數(shù)據(jù)元素，則返回該元素在線性表中的位序；否則返回NULL(或者0)。若線性表L中值與x相同的元素不止一個，則返回這些元素中位序最小的一個數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第29頁。

ListPrior(L,e) //求前驅(qū)函數(shù)。已知e為線性表L中的某一元素，若它的位序大于1，則返回e的前驅(qū)，否則返回NULLListNext(L.e) //求后繼函數(shù)。已知e為線性表L中的某一元素，若它的位序小于ListLength(L)，則返回e的后繼，否則返回NULLListInsert(L,i.e)//前插操作。在線性表L中第i個元素之前插入一個新的元素e，使得線性表L變?yōu)殚L度為ListLength(L)+1的線性表

ListDelete(L,i)//刪除操作。若1≤i≤ListLength(L)，則刪除線性表L中的第i個元素，使得線性表Ｌ變?yōu)殚L度為ListLength(L)+1的線性表。否則返回出錯信息

ListEmpty(L) //判空表函數(shù)。若線性表L為空表，則返回“true”，否則返回“false”ListClear(L) //清空表函數(shù)。將線性表L置為空表

}ADTLinear_List數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第30頁。2.1.3線性表的相關(guān)操作1．線性表的遍歷線性表的遍歷操作就是訪問線性表中的每一個元素，并且每個元素只訪問一次。線性表的遍歷操作的思想是：首先利用判表空操作，查看是否需要對線性表進(jìn)行遍歷，然后找到線性表的第一個元素，依次向后掃描每一個元素進(jìn)行訪問。2．線性表的合并線性表的合并操作就是將兩個線性表La和Lb合并成一個長度為ListLengh(La)+ListLength(Lb)的線性表Lc。線性表的合并操作有下面兩種情況。

1)直接合并設(shè)線性表La表示的集合為A，線性表Lb表示的集合為B，直接合并就是完成A=A∪B的操作。

2)保序合并保序合并操作發(fā)生在兩個有序的線性表中。它是將兩個已經(jīng)有的線性表La和Lb歸并為一個新的線性表Lc，并且保證線性表Lc仍然是有序的。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第31頁。2.2線性表的順序存儲結(jié)構(gòu)2.2.1線性表的順序存儲結(jié)構(gòu)2.2.2相關(guān)操作的實現(xiàn)2.2.3順序存儲結(jié)構(gòu)的分析數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第32頁。2.2.1線性表的順序存儲結(jié)構(gòu)在計算機(jī)中存儲線性表，一種最簡單的方法就是順序存儲。這種存儲方式的特點是，線性表中所有元素所占用的存儲空間是連續(xù)的。設(shè)a1為線性表第一個元素的存儲地址，且每個元素在內(nèi)存中占用L個存儲單元，則第i個元素的存儲地址LOC(ai)的計算如下：

LOC(ai)=LOC(a1)+(i-1)*L1≤i≤n數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第33頁。2.2.2相關(guān)操作的實現(xiàn)1.順序表的初始化順序表的初始化操作SeqListInit(L)定義一個空的線性表。這里只需要將length值設(shè)為0即可。2.順序表的求長度操作順序表在定義時采用變量length存儲其長度，因此，對于求順序表的長度操作SeqListLength(L)，只需要將length的值返回即可。3.順序表的取元素操作順序表的取元素操作SeqListGet(L,i)，只需要查看i是否小于length，如果小于則直接返回第i個元素的值就可以。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第34頁。4.順序表的定位操作順序表的定位操作SeqListLocate(L,e)是將順序表中找到第一個與e值相等的元素。從第一個元素a1進(jìn)行比較，直至找到一個與e相等的元素，返回這個元素在順序表中的位置。5.順序表的求前驅(qū)操作順序表的求前驅(qū)操作SeqListPrior(L,e)，首先判斷e是否為第一個元素，如果不是則返回e的前一個元素；否則返回NULL。6.順序表的求后繼操作順序表的求后繼操作SeqListPrior(L,e)，首先判斷e是否為最后一個元素，如果不是則返回e的后一個元素；否則返回NULL。7.順序表的前插操作順序表的前插操作SeqListInsert(L,i,b)，將順序表L中的第i個元素之前插入一個新的數(shù)據(jù)元素b，順序表的長度變?yōu)樵瓉淼膌ength+1。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第35頁。8.順序表的刪除操作順序表的刪除操作SeqListDel(L,i)，將順序表L中的第i個元素刪除，順序表的長度變?yōu)樵瓉淼膌ength-1。9.順序表的判空操作順序表的判空操作SeqListEmpty(L)，判斷順序表

L

是否為空。實現(xiàn)它只需查看變量length的值是否為0，如果為0則返回true；否則返回false。10.順序表的置空操作實現(xiàn)順序表的置空操作與初始化順序表的實現(xiàn)方法相同。11.順序表的遍歷操作順序表的遍歷操作SeqListTraverse(L)，將依次訪問順序表中的元素，其目的是為了直觀地將訪問操作設(shè)定為輸出元素。12.順序表的合并操作順序表的直接合并操作與保序合并操作算法與程序清單2-2、2-3類似。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第36頁。2.2.3順序存儲結(jié)構(gòu)的分析本節(jié)介紹了線性表的順序存儲結(jié)構(gòu)，這種存儲方式有以下優(yōu)、缺點。(1)實現(xiàn)方法簡單。(2)每個元素的存儲位置可以用一個簡單的公式來計算。(3)遍歷操作和定位操作都以線性的時間執(zhí)行，取元素操作只需要花費常數(shù)的時間。(4)順序存儲的空間是靜態(tài)分配的，需要事先指定MAXSIZE的大小，因此，在事先不知道線性表大小的情況下，很容易造成空間的浪費。(5)插入與刪除操作的花費是很昂貴的。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第37頁。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1線性鏈表與相關(guān)操作實現(xiàn)2.3.2雙向鏈表與相關(guān)操作實現(xiàn)2.3.3循環(huán)鏈表與其相關(guān)操作實現(xiàn)2.3.4鏈?zhǔn)酱鎯Y(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第38頁。2.3.1線性鏈表與相關(guān)操作實現(xiàn)1.單鏈表的初始化操作單鏈表初始化就是建立一個空的鏈表。2.單鏈表的求表長操作單鏈表求表長操作需要設(shè)定當(dāng)前指針p和一個計數(shù)器j，初始時p指向鏈表中的第一個結(jié)點，當(dāng)p每向下移動一個結(jié)點時，j就加1，直到p鏈表的尾部。3.單鏈表的取元素操作單鏈表的取元素操作就是查找鏈表中的第i個元素。設(shè)定p為當(dāng)前結(jié)點，當(dāng)p指向鏈表的第一個結(jié)點，并向下移動i次，最后p所指向的元素就是需要查找的第i個元素。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第39頁。4.單鏈表的定位操作單鏈表的定位操作也稱按值查找操作，它得到元素e第一次出現(xiàn)的位置。首先從鏈表的第一個結(jié)點開始，判斷當(dāng)前結(jié)點的值是否等于e，等于則返回該結(jié)點的指針，否則將繼續(xù)向后查找，直至到達(dá)鏈表的最后。5.單鏈表的插入操作單鏈表的插入操作就是在結(jié)點p之前插入一個新的結(jié)點q，該結(jié)點的數(shù)據(jù)域為e。對于不帶頭結(jié)點的單鏈表，p的位置有所不同，插入操作有下面兩種情況。

1)在鏈表的表頭插入在表頭插入新的結(jié)點時，需要執(zhí)行下面3個步驟。

(1)創(chuàng)建了一個新的結(jié)點q。

(2)將此新結(jié)點的數(shù)據(jù)域賦值為e，并將它的next指針指向第一個結(jié)點，即L。

(3)將L修改為指向新的結(jié)點q。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第40頁。

2)在鏈表的中間插入在鏈表的中間插入時，需要執(zhí)行下面4個步驟。

(1)創(chuàng)建了一個新的結(jié)點q。

(2)將此新結(jié)點的數(shù)據(jù)域賦值為e，并將它的next指針指向p。

(3)查找到p的前驅(qū)結(jié)點pre。

(4)將pre的next指針指向新創(chuàng)建的結(jié)點q。6.單鏈表的刪除操作單鏈表的刪除操作就是刪除鏈表中的某個元素e，如果e在鏈表中出現(xiàn)不止一次，將刪除第一次出現(xiàn)的e，否則什么也不做。對于不帶頭結(jié)點的單鏈表，由于所需要刪除的元素e的位置不同，存在著以下兩種情況。假設(shè)用指針p找到元素x所在的結(jié)點。

1)

p是鏈表中的第一個結(jié)點刪除表中的第一個結(jié)點時，需要執(zhí)行下面兩個步驟。

(1)將L指向p->next。

(2)釋放p。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第41頁。

2)

p是鏈表中的其他結(jié)點刪除表的其他結(jié)點時，需要執(zhí)行下面3個步驟。

(1)找到p的前驅(qū)結(jié)點pre。

(2)將pre->next指向p->next。

(3)釋放p。7.創(chuàng)建單鏈表操作單鏈表的創(chuàng)建方法有兩種，一種是頭插法，另一種是尾插法。頭插法是將新增結(jié)點插入第一個結(jié)點之前。尾插法就是將新增的結(jié)點插入最后一個結(jié)點之后。8.單鏈表保序合并操作按照保序合并的思想，首先，需要設(shè)置3個指針pa、pb、pc，pa和pb分別指向鏈表La與Lb的當(dāng)前待比較插入結(jié)點，pc指向鏈表Lc的最后一個結(jié)點。當(dāng)pa->data≤pb->data時，將pa所指的結(jié)點插入到pc后面，否則就將pb所指的結(jié)點插入到pc后面。最后，當(dāng)有一個表合并完以后，只需要將另一個表剩余的結(jié)點全插入到pc即可。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第42頁。2.3.2雙向鏈表與相關(guān)操作實現(xiàn)1．雙向鏈表的插入操作因為雙向鏈表本身就帶有一個指向前驅(qū)結(jié)點的指針，因此在p結(jié)點前插入元素e的操作可以通過下面幾個步驟來完成。(1)創(chuàng)建一個新的結(jié)點q，讓q->data等于需要插入的元素e。(2)將q->prior指向p->prior。(3)將p->prior->next指向q。(4)將q->next指向p。(5)將p->prior指向q。2．雙向鏈表的刪除操作雙向鏈表的刪除結(jié)點p操作要修改兩個指針，需要執(zhí)行下面3個步驟。(1)將p->prior->next指向p->next。(2)將p->next->prior指向p->prior。(3)釋放p。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第43頁。2.3.3循環(huán)鏈表與其相關(guān)操作實現(xiàn)循環(huán)鏈表是一種特殊的線性表，它的第一個結(jié)點之前就是最后一個結(jié)點；反之亦然。單向循環(huán)鏈表的操作與非循環(huán)鏈表的操作相同，只是將原來控制條件由判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已。根據(jù)不同的需求，循環(huán)鏈表還可以和雙向鏈表組合形成雙向循環(huán)鏈表，它的操作和雙向鏈表的操作類似，只需要將原來控制條件由判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第44頁。2.3.4鏈?zhǔn)酱鎯Y(jié)構(gòu)分析1.鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)、缺點鏈表是線性表的另一種存儲方式，與線性表相比，鏈表具有以下的優(yōu)、缺點。(1)鏈表的存儲空間是動態(tài)分配的，只要內(nèi)存尚有空間，就不會產(chǎn)生溢出。(2)便于實現(xiàn)插入和刪除操作。(3)由于鏈表的不連續(xù)存儲，因此它的內(nèi)容分散，有時會導(dǎo)致調(diào)試的不方便。(4)鏈表中的每個結(jié)點既有數(shù)據(jù)域又有指針域，增加了線性表的存儲開銷。(5)在鏈表中查找結(jié)點時，需要從頭指針開始遍歷，增加了時間。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第45頁。在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，主要有單鏈表、雙向鏈表、循環(huán)鏈表3種，下面就對這3種結(jié)構(gòu)鏈表的優(yōu)、缺點進(jìn)行分析。(1)雙向鏈表解決了單鏈表的單向性問題，使得鏈表查找前驅(qū)結(jié)點變得簡單，但是它增加了結(jié)點的存儲空間，使維護(hù)操作變得困難。(2)循環(huán)鏈表解決了單鏈表必須從頭指針進(jìn)行遍歷的限制。2.選擇存儲結(jié)構(gòu)遵循的原則(1)當(dāng)線性表的長度變化較大，難以估計其存儲的規(guī)模時，一般采用鏈表作為存儲結(jié)構(gòu)。(2)當(dāng)線性表的長度變化不大，易于事先確定其大小時，宜采用順序表作為存儲結(jié)構(gòu)，這樣可以節(jié)省存儲空間。(3)當(dāng)線性表的主要操作是查找，并且很少進(jìn)行插入和刪除操作時，宜采用順序表作為存儲結(jié)構(gòu)。(4)若線性表需要頻繁地進(jìn)行插入和刪除操作時，為了提高性能，宜采用鏈表作為存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第46頁。2.4線性表的應(yīng)用2.4.1一元多項式的抽象數(shù)據(jù)類型2.4.2多項式的順序表實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第47頁。2.4.1一元多項式的抽象數(shù)據(jù)類型在數(shù)學(xué)中，一個一元多項式可以按升冪寫成以下形式：

這個多項式由n+1個系數(shù)唯一確定。那么，就可以用一個線性表P來存儲這些系數(shù)，即那么，通過這個線性表，就可以編寫一些多項式的加、減、乘、微分等操作的算法。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第48頁。2.4.2多項式的順序表實現(xiàn)很顯然，可以采用順序表實現(xiàn)這個多項式。下面給出了多項式的順序表實現(xiàn)的類型聲明。

typedefstructNode{intCoefArray[MaxDegree+1];intHighPower;}*SeqPolynomial;數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第49頁。第3章棧和隊列數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第50頁。本章主要內(nèi)容3.1棧3.2棧的應(yīng)用3.3隊列3.4隊列的應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第51頁。3.1棧3.1.1棧概述3.1.2棧的實現(xiàn)3.1.3棧的實現(xiàn)方式的比較數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第52頁。3.1.1棧概述棧(stack)是限定僅在表尾進(jìn)行插入和刪除操作的線性表。表尾又稱為棧頂(top)，表頭稱為棧底(bottom)。棧又稱為后進(jìn)先出(LastInFirstOut，LIFO)的線性表。棧的抽象數(shù)據(jù)類型定義為：

ADTStack{

數(shù)據(jù)對象：任意數(shù)據(jù)元素的集合

D={ai|ai∈elementset，i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：數(shù)據(jù)之間呈線性關(guān)系，除第一個和最后一個外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。

R={<ai-1，ai>|ai-1，ai∈D,i=1,2,…,n,n≥0}數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第53頁。3.1.2棧的實現(xiàn)1．順序棧利用順序表實現(xiàn)的棧稱為順序棧。1)順序棧的初始化順序棧的初始化就是將棧初始化為一個空棧。2)棧判空操作順序棧的棧判空操作就是查看top是否為-1，如果top=-1則說明這是一個空棧，返回true，否則返回false。3)入棧操作因為順序棧用數(shù)組實現(xiàn)，因此在實現(xiàn)順序棧的入棧操作時，需要對S進(jìn)行是否棧滿判斷。只有在棧不滿的情況下才能進(jìn)行入棧操作。棧滿的條件為top=MAXSIZE-1。4)出棧操作順序棧的出棧操作，只需要將top--。5)取棧頂元素數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第54頁。2．鏈棧下面將給出鏈棧的基本操作的算法。1)鏈棧的初始化鏈棧初始化的算法如下所示。voidLinkedStackInit(LinkedStackS){S->top=NULL;}2)判?？詹僮飨旅娼o出了鏈棧判?？詹僮鞯乃惴?。BOOLLinkedStackEmpty(LinkedStackS){if(S->top==NULL)returnTRUE;elsereturnFALSE;}數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第55頁。

3)入棧操作由于鏈棧采用動態(tài)的存儲方式，不存在棧滿的情況，因此，在進(jìn)行入棧操作時，只需要將創(chuàng)建的新結(jié)點插入到棧中即可。

4)出棧操作雖然鏈棧的入棧操作不需要判定棧是否已滿，但是鏈棧的出棧操作仍需要判斷棧是否為空。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第56頁。3.1.3棧的實現(xiàn)方式的比較順序棧與鏈棧操作的時間復(fù)雜度均為O(1)。順序棧主要的缺點是，需要預(yù)先定義?？臻g的大小，當(dāng)棧中的元素不多時容易造成空間的浪費，當(dāng)棧的入棧操作過多時，又可能出現(xiàn)?？臻g的不足。鏈棧的主要缺點是鏈棧需要增加每個結(jié)點的存儲開銷。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第57頁。3.2棧的應(yīng)用3.2.1平衡符號3.2.2表達(dá)式求值3.2.3函數(shù)調(diào)用3.2.4遞歸與棧數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第58頁。3.2.1平衡符號

人們稱符號“(”、“[”、“{”為開分隔符(openingdelimiter)，稱“)”、“]”、“}”為閉分隔符(closingdelimiter)。平衡符號的算法主要分為以下3步。

(1)設(shè)置空棧S。

(2)依次讀入文件中的字符，如果讀到的字符屬于開分隔符，則將其壓入到棧S中，如果讀到的字符屬于閉分隔符，則將棧S中的棧頂元素彈出，并與此閉分隔符比較，如果二者不匹配，則報錯，否則繼續(xù)讀入下一個字符，直到文件結(jié)尾。

(3)最后如果棧S為空棧，則說明符號匹配成功，否則匹配不成功，報錯。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第59頁。3.2.2表達(dá)式求值對于表達(dá)式

3*4+5+6*7

可以將上述的計算順序書寫為

34*5+67*+

以上的記法稱為后綴(posfix)或逆波蘭(reversePolish)記法。并且用后綴記法描述的表達(dá)式稱為后綴式。后綴式的計算方法是上面所描述的過程，采用?？梢院苋菀椎貙崿F(xiàn)上面的過程。算法的主要思想分為以下3步。(1)設(shè)置一個空棧S。(2)依次讀取表達(dá)式中的元素，如果元素是一個數(shù)，則將其壓入棧S中；否則，元素為一個計算符，這時將棧S的兩個棧頂元素彈出，并采用此運算符做相應(yīng)的操作。直到整個表達(dá)式計算完畢。(3)最后棧S中唯一的元素即為表達(dá)式的求值結(jié)果。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第60頁。棧不僅可以用來計算一個后綴式的值，而且還可以用棧將一個標(biāo)準(zhǔn)形式的表達(dá)式(又稱為中綴式(infix))轉(zhuǎn)換為后綴式。(1)設(shè)置空棧S(用來存放操作符)。(2)依次讀入中綴表達(dá)式中的元素。(3)最后，直至讀到輸入的表達(dá)式的末尾。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第61頁。3.2.3函數(shù)調(diào)用在進(jìn)行函數(shù)調(diào)用時，系統(tǒng)將所需要的信息存放在棧中。在系統(tǒng)中，每個函數(shù)(包括main函數(shù))的狀態(tài)是由函數(shù)中的局部變量、函數(shù)參數(shù)值、函數(shù)的返回地址決定的。存儲這些信息的數(shù)據(jù)區(qū)域稱為活動記錄(activationrecord)，或叫做棧幀(stackframe)，它是運行時系統(tǒng)棧上分配的空間，只要函數(shù)是正在執(zhí)行的，它的活動記錄就一直存在，只有當(dāng)函數(shù)退出時才釋放其空間。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第62頁。3.2.4遞歸與棧

1．遞歸的定義遞歸是指一個直接調(diào)用自己或者通過一系列的過程調(diào)用語句間接地調(diào)用自己的過程。根據(jù)調(diào)用的方式不同，遞歸還可以分為直接遞歸和間接遞歸。若一個過程在執(zhí)行前直接調(diào)用其本身就稱其為直接遞歸。若一個過程A調(diào)用了過程B，而過程B又調(diào)用了過程A，則過程A通過過程B來調(diào)用自身的方式稱為間接遞歸。遞歸定義必須同時滿足以下兩個條件。(1)被定義項在定義中應(yīng)具有更小的“尺度”。(2)被定義項在最小“尺度”上的定義不是遞歸的。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第63頁。

2．遞歸調(diào)用的剖析在執(zhí)行函數(shù)時，系統(tǒng)跟蹤運行時棧上的所有調(diào)用，并且通過返回地址來記錄調(diào)用完畢后從哪一個位置繼續(xù)程序的運行。在系統(tǒng)中為每一行代碼指定一個數(shù)，如果這一行是一個函數(shù)調(diào)用，該數(shù)就為該函數(shù)的返回值。

3．遞歸的消除最一般的消除遞歸的方法是將原由系統(tǒng)管理的棧改為由程序員管理。采用棧來模擬遞歸時，采用了以下步驟。

(1)構(gòu)造一個棧。

(2)為了能夠一次將參數(shù)、返回地址和函數(shù)的返回值壓入棧中，設(shè)置了一個結(jié)構(gòu)ELEM，它含有3個變量rd、pn和pf，對于rd并不是函數(shù)的真實的返回地址，只是為了模擬時設(shè)置標(biāo)號的值。

(3)將標(biāo)號L0賦值給算法的第一條可執(zhí)行語句。

(4)接下來通過標(biāo)號語句與goto語句的使用，完成了將不同狀態(tài)的參數(shù)、返回地址、返回值壓入棧中。

(5)最后利用標(biāo)號L1與goto語句，完成了出棧操作。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第64頁。3.3隊列3.3.1隊列概述3.3.2隊列的實現(xiàn)3.3.3隊列實現(xiàn)方法比較數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第65頁。3.3.1隊列概述隊列(queue)與棧一樣，都屬于線性表。與棧不同的是，隊列只允許在表的一端插入，在另一端刪除。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。隊列的抽象數(shù)據(jù)類型如下：

ADTQueue{

數(shù)據(jù)對象：任意數(shù)據(jù)元素的集合

D={ai|ai∈elementset，i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：數(shù)據(jù)之間呈線性關(guān)系，除第一個和最后一個外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。

R={<ai-1，ai>|ai-1，ai∈D,i=1,2,…,n,n≥0}數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第66頁。3.3.2隊列的實現(xiàn)1．順序隊列順序隊列采用順序表的方式來實現(xiàn)隊列。順序隊列的操作主要有以下幾種。1)判空操作如果一個順序隊列為空，則front=rear。2)入隊操作在進(jìn)行入隊操作時需要對隊列進(jìn)行判滿操作。3)出隊操作順序隊列在進(jìn)行操作時，需要對隊列進(jìn)行判空操作。順序隊列與棧一樣，也會存在溢出現(xiàn)象，它的溢出分為以下3種情況。1)

“下溢”現(xiàn)象當(dāng)隊列為空時，做出隊運算產(chǎn)生的溢出現(xiàn)象。2)

“真上溢”現(xiàn)象當(dāng)隊列滿時，做進(jìn)棧運算產(chǎn)生空間溢出的現(xiàn)象。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第67頁。3)

“假上溢”現(xiàn)象由于入隊和出隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用，這時隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，而尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為“假上溢”現(xiàn)象。2．循環(huán)隊列為了充分利用空間，克服“假上溢”的現(xiàn)象，人們將存儲隊列的一維數(shù)組空間想象成一個首尾相接的圓環(huán)，這樣的隊列稱為循環(huán)隊列(circularqueue)。1)初始化操作循環(huán)隊列的初始化操作就是將循環(huán)隊列初始化為一個空的隊列，與順序隊列一樣，只需要設(shè)置front=rear=-1。2)判隊空操作判斷一個循環(huán)隊列是否為空，只需要查看這個隊列中的front指針是否為-1即可。3)入隊操作在執(zhí)行入隊操作時，需要查看循環(huán)隊列是否已滿。4)出隊操作循環(huán)隊列進(jìn)行出隊操作時，需要判定隊列是否為空。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第68頁。3．鏈隊列采用線性鏈表表示的隊列稱為鏈隊列。在鏈隊列中，鏈表的第一個結(jié)點存放隊列的隊頭結(jié)點，最后一個結(jié)點存放隊列的隊尾結(jié)點。1)鏈隊列的初始化操作鏈隊列的初始化操作，就是創(chuàng)建一個空隊列。2)判隊空操作因為存在一個頭結(jié)點，因此，只有當(dāng)鏈隊列為空時，它們的front與rear指針才會同時指向同一個結(jié)點，即頭結(jié)點。因此一個鏈隊列Q為空的條件是：

Q->front=Q->rear3)入隊操作由于鏈表的空間是動態(tài)分配的，因此鏈隊列入隊操作不需要判斷隊列是否已滿。4)出隊操作鏈隊列進(jìn)行出隊操作時，需要判斷隊列是否為空。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第69頁。3.3.3隊列實現(xiàn)方法比較(1)順序隊列的空間利用率不高，容易出現(xiàn)“假上溢”的現(xiàn)象。(2)循環(huán)隊列克服了順序隊列的“假上溢”現(xiàn)象，但是它和順序隊列一樣，存儲空間是事先分配好的。(3)鏈隊列克服了順序隊列空間固定的缺點，在對鏈隊列進(jìn)行入隊操作時，不需要考慮上溢和隊滿問題。(4)鏈隊列和鏈表一樣，需要增加結(jié)點的空間開銷，并且還有運行malloc和free的開銷。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第70頁。3.4隊列的應(yīng)用3.4.1排列問題3.4.2非排列問題數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第71頁。3.4.1排列問題在計算機(jī)科學(xué)中，也有很多的排隊問題要用隊列來解決。這些問題主要分為兩個方面。

1.解決主機(jī)與外部設(shè)備之間速度不匹配的問題例如，主機(jī)和打印機(jī)之間不匹配。

2.解決由多用戶引起的資源競爭問題例如，CPU的競爭問題。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第72頁。3.4.2非排列問題有很多的非排列問題也會用到隊列。例如，二項式(a+b)n展開后，其系數(shù)構(gòu)成楊輝三角形，試打印這個三角形。這里采用鏈隊列的結(jié)構(gòu)來實現(xiàn)這個算法。通過分析楊輝三角形，得到它的第i列元素是由第i-1列元素得到的，它們之前存在著以下的關(guān)系：從上面的關(guān)系可以看出，第i行要用到第i-1行所有元素。因此，可以考慮使用一個隊列存儲元素。在依次輸出每一行數(shù)據(jù)的同時，計算下一行的數(shù)據(jù)，然后再將其插入隊列中，為了區(qū)分每一行，在各行系統(tǒng)之間插入一個0。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第73頁。第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第74頁。本章主要內(nèi)容4.1串的定義4.2串的存儲實現(xiàn)4.3串的模式匹配數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第75頁。4.1串的定義4.1.1串4.1.2串的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第76頁。4.1.1串

串(string)是字符串的簡稱。它是由零個或多個字符組成的有限序列。串一般記為

s

=‘a(chǎn)1a2…an’(n≥0)。其中，s是串名，a1a2…an是串值，用一對單引號括起來，ai可以是字母、數(shù)字或其他字符；n表示串的長度，當(dāng)n=0時表示串沒有任何字符，因此又稱沒有任何字符的串為空串，記作：s=‘’。如果一個串s1是另一個串s2中連續(xù)的一段子序列，則串s1就稱為串s2的子串。串s2稱為串s1的主串。另外，空串是任意串的子串，任意串是其自身的子串。通常稱字符在序列中的序號為該字符在串的位置，子串在主串的位置是以子串的第一個字符在主串的位置來表示。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第77頁。還需要了解，通常在程序中使用的串可以分為串變量和串常量。

(1)串變量和其他類型的變量一樣，它的值是可以改變的。

(2)串常量的值和整常數(shù)、實常數(shù)一樣，在程序中只能被引用而不能改變其值。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第78頁。4.1.2串的抽象數(shù)據(jù)類型串的抽象數(shù)據(jù)類型如下。

ADTSTRING{

數(shù)據(jù)對象：任意數(shù)據(jù)元素的集合

D={ai|ai∈elementset,i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：數(shù)據(jù)之間呈線性關(guān)系，除第一個和最后一個外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。

R={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n,n≥0}(1)串的前3個操作：串賦值(StringAssign)、判等操作(StringEqual)、求串長(StringLength)是串的最基本操作，其他操作都可以通過這3個操作得到。

(2)串的連接操作需要注意參數(shù)的順序。

(3)有的書將串的插入操作定義為前插。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第79頁。4.2串的存儲實現(xiàn)4.2.1串的順序存儲結(jié)構(gòu)4.2.2串的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第80頁。4.2.1串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)，也稱順序串，與順序表存儲方式類似，即用一組地址連續(xù)的存儲單元依次存放串中的各個字符。1.串的賦值串的賦值就是將串T的值賦給串S，如果串S非空時，需要將串的內(nèi)存釋放掉再進(jìn)行賦值操作2.串的連接串的連接操作就是將串T連接到串S的后面，需要注意的是，進(jìn)行連接操作時要將串S中的元素先暫存起來，然后才能進(jìn)行空間申請，否則會造成串S的內(nèi)容丟失。3.判串等操作判串等操作首先判斷兩個串的串長是否相等。4.求子串操作求子串操作的過程也是復(fù)制字符序列的過程。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第81頁。4.2.2串的鏈?zhǔn)酱鎯Y(jié)構(gòu)

可以采用鏈表的形式存儲串，鏈表中每個結(jié)點存儲串中的一個字符，如圖4.1(a)所示。也可以用鏈表的一個結(jié)點存放k個字符，如圖4.1(b)所示，稱采用鏈?zhǔn)浇Y(jié)構(gòu)存儲的串為鏈串。圖4.1串的鏈?zhǔn)酱鎯κ疽鈭D數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第82頁。采用圖4.1(b)所示結(jié)構(gòu)存儲串時，需要注意以下3個要點。

(1)為了提高存儲密度，可使每個結(jié)點存放多個字符。

(2)當(dāng)結(jié)點可以存儲的字符數(shù)大于1時，串的長度不一定正好是結(jié)點大小的整數(shù)倍，因此需要用特殊字符來填充最后一個結(jié)點，以表示串結(jié)束。

(3)雖然提高結(jié)點的可存儲字符的數(shù)量可以使存儲密度增大，但是做插入和刪除操作時，可能會引起大量的字符移動，給運算帶來不便。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第83頁。4.3串的模式匹配4.3.1簡單模式匹配算法4.3.2KMP算法4.3.3其他模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第84頁。4.3.1簡單模式匹配算法

人們很容易想到的模式匹配算法就是將目標(biāo)串S的第一個字母和模式串P的第一個字母開始比較，如果不匹配，就將S的第二個字母與P的第一個字母相比較，依此下去，直到匹配成功或者已經(jīng)到了S的最后一個字母。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第85頁。4.3.2KMP算法

KMP算法在每一趟匹配過程中出現(xiàn)不相等的情況時，不需要回溯指針i，而是將模式串P向右滑動一個適當(dāng)?shù)木嚯x，重新進(jìn)行比較。這個算法可以在O(m+n)的時間復(fù)雜度下完成模式匹配。

KMP算法中關(guān)鍵問題是next函數(shù)的求解。next函數(shù)可以用遞推的方式得到，分析如下。根據(jù)定義有

next[0]=-1(4.2)

設(shè)next[j]=k，則有

P(0..k-1)=P(j-k+1..j-1)(4.3)

其中1<k<j，并且k是滿足式(4.3)的最大值。此時的next[j+1]有下面兩種情況。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第86頁。(1)若P[k]=P[j]，則說明

P(0..k)=P(j-k+1..j)(4.4)根據(jù)式(4.2)，有next[j+1]=k+1，即

next[j+1]=next[j]+1(4.5)(2)若P[k]P[j]，則表明在模式串P中

P(0..k)P(j-k+1..j)數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第87頁。4.3.3其他模式匹配算法1．Boyer-Moore算法此算法試圖從右到左地比較模式串P和目標(biāo)串S，在不匹配的情況下，Boyer-Moore算法把P向右移動S中未涉及比較的字符數(shù)，因此Boyer-Moore算法可以跳過S中的字符來提高速度。

Boyer-Moore算法中出現(xiàn)不匹配時，移動的規(guī)則有以下3條。

(1)沒有出現(xiàn)時。如果不匹配的字符S[i]在P中沒有出現(xiàn)，就對齊P[0]和S[j+1]。

(2)右端出現(xiàn)時。如果S[i]與P[j]不匹配，且P[j]的右端有一個字符等于S[i]，P就移動一個位置。

(3)左端出現(xiàn)時。如果S[i]與P[j]不匹配，且P[j]的左端有一個字符ch等于S[i]，S[i]就與最靠近P[j]的P[k]=ch對齊。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第88頁。2．模糊匹配算法在許多情況下，其實并不需要完全匹配，只要模式P與目標(biāo)串T之間有一定程度的相似，就認(rèn)為匹配成功。這種模式匹配算法稱為字符串的模糊匹配。下面來學(xué)習(xí)兩個字符串模糊匹配算法：MonteCarlo算法和LasVegas算法。

MonteCarlo(蒙特卡羅)算法的思想是：對于目標(biāo)串S，求出其S(j)=S[j]S[j+1]…S[j+m-1](從S第j位開始、長度與P一樣的子串)的指紋Ip(S(j))，與P的指紋Ip(P)，如果它們相等則認(rèn)為P是S的子串，并且得到位置j；否則比較S(j+1)與P的指紋，一直比較n-m+1次，如果沒有一個S(j)與P的指紋相等，則認(rèn)為P不是S的子串。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第89頁。

LasVegas(拉斯維加斯)算法的思想是：它與MonteCarlo算法相似，只是在Ip(P)=Ip(S(j))時，不直接返回匹配成功，而是轉(zhuǎn)去比較P與S(j)是否真的相等。因此，采用LasVegas算法得出P是S的子串的結(jié)果總是正確的。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第90頁。第5章數(shù)組及廣義表數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第91頁。本章主要內(nèi)容5.1數(shù)組的定義5.2數(shù)組的順序存儲5.3矩陣的壓縮存儲5.4廣義表數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第92頁。5.1數(shù)組的定義

5.1.1數(shù)組的基本概念5.1.2數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第93頁。5.1.1數(shù)組的基本概念一維數(shù)組：是存儲于計算機(jī)的連續(xù)存儲空間中的多個具有統(tǒng)一類型的數(shù)據(jù)元素。它們定義的一般格式為類型標(biāo)識符數(shù)組名[常量表達(dá)式];二維數(shù)組：存放的是有規(guī)律地按行、列排列的同一類型數(shù)據(jù)。二維數(shù)組定義的一般格式為類型標(biāo)識符數(shù)組名[常量表達(dá)式1][常量表達(dá)式2];數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第94頁。5.1.2數(shù)組的抽象數(shù)據(jù)類型

將二維數(shù)組Amn看成一個線性表

A=(A1,A2,…,An)

其中每一個元素都是一個行向量或列向量的線性表，以行向量為例，Ai又可以表示為

A1=(ai1,ai2,…,ain)

將上面的分析推廣到多維數(shù)組，它的每個元素可以表示為一個(n-1)維的向量。根據(jù)前面的分析，可以將數(shù)組的抽象數(shù)據(jù)類型定義如下：

ADTARRAY{

數(shù)據(jù)對象：

數(shù)據(jù)關(guān)系：R={R1,R2,…,Rn}

數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第95頁。多維數(shù)組一般不進(jìn)行插入和刪除操作，數(shù)組一旦給定以后，每個元素之間的關(guān)系就不會發(fā)生變化了。因此數(shù)組的操作主要有兩個。(1)取數(shù)組元素的值(Value(A，&e，index1，…，indexn))。(2)修改數(shù)組元素的值(Assign(&A，e，index1，…，indexn))。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第96頁。5.2數(shù)組的順序存儲5.2.1數(shù)組的順序存儲方式5.2.2數(shù)組的順序存儲的基本操作數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第97頁。5.2.1數(shù)組的順序存儲方式因為多維數(shù)組主要執(zhí)行的是取值和修改元素的操作，因此宜采用順序存儲的方式。為了便于查找，人們規(guī)定二維數(shù)組以行序為主進(jìn)行存儲或以列序為主進(jìn)行存儲。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第98頁。5.2.2數(shù)組的順序存儲的基本操作下面給出了數(shù)組的順序存儲的類型聲明structArray{ElemType*base;//數(shù)組的元素基址，也就是第一個元素的存儲位置

intdim;//數(shù)組的維數(shù)

int*bounds;//數(shù)組中的每一維的大小

int*constants;//數(shù)組的映像函數(shù)的常量的基址，即c0的存儲位置};typedefstructArrayArray;1.

Locate操作

Locate操作就是根據(jù)下標(biāo)值求出元素在數(shù)組中的存儲相對地址。2.

Value操作

Value操作就是根據(jù)下標(biāo)取出數(shù)組中元素的值。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第99頁。5.3矩陣的壓縮存儲5.3.1特殊矩陣5.3.2稀疏矩陣數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第100頁。5.3.1特殊矩陣特殊矩陣是指矩陣中元素的存儲具有一定的規(guī)律。

1．對稱矩陣在一個n個方陣中，如果元素滿足下述的性質(zhì)

aij=aji0≤i，j≤n-1

則稱方陣A為對稱矩陣。

2．三角矩陣以主對角線進(jìn)行劃分，三角矩陣可以分為上三角矩陣和下三角矩陣兩種。上三角矩陣的下三角(不包括主對角線)中的元素均為常數(shù)c(c一般為0)，下三角矩陣與上三角矩陣正好相反，它的主對角線上方的元素均為常數(shù)c。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第101頁。

3．對角矩陣對角矩陣中所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零的矩陣為對角矩陣。數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)第2版上ppt全文共112頁，當(dāng)前為第102頁。5.3.2稀疏矩陣設(shè)矩陣Amn中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱A為稀疏矩陣。為了能更確切地描述遠(yuǎn)遠(yuǎn)小于這一情況，人們引入了稀疏因子。假設(shè)在m