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

數(shù)據(jù)結(jié)構(gòu)與算法（C語(yǔ)言版）第2版上作者：郭龍?jiān)?、胡虛懷、何光明、戴仕明?shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第1頁(yè)。第1章緒論數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第2頁(yè)。本章主要內(nèi)容1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的意義1.2數(shù)據(jù)結(jié)構(gòu)1.3抽象數(shù)據(jù)類(lèi)型1.4算法1.5算法分析數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第3頁(yè)。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語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第4頁(yè)。1.1.1學(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ù)專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類(lèi)型的數(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ī)專(zhuān)業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)管理系統(tǒng)、軟件工程及人工智能等都是十分有益的。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第5頁(yè)。1.1.2學(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)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第6頁(yè)。1.2數(shù)據(jù)結(jié)構(gòu)

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

數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第7頁(yè)。1.2.1數(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ù)存在的形式。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第8頁(yè)。1.2.2基本概念和相關(guān)術(shù)語(yǔ)

數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)分為兩類(lèi)：數(shù)值型數(shù)據(jù)(主要用于數(shù)學(xué)計(jì)算等)和非數(shù)值型數(shù)據(jù)(文字、圖形、圖像、音頻和視頻等)。數(shù)據(jù)元素(dataelement)是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。一個(gè)數(shù)據(jù)元素可由不可分割的若干個(gè)數(shù)據(jù)項(xiàng)(dataitem)組成。數(shù)據(jù)對(duì)象(dataobject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第9頁(yè)。數(shù)據(jù)結(jié)構(gòu)(datastructure)是指相互之間存在著一種或多種關(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)系，如圖1.2(a)所示。

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

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

(4)圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“多對(duì)多”的關(guān)系，如圖1.2(d)所示。圖1.24類(lèi)基本數(shù)據(jù)結(jié)構(gòu)示意圖數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第10頁(yè)。數(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ù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第11頁(yè)。1.3抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型(AbstractDataType，ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類(lèi)型由元素、關(guān)系及操作3種要素來(lái)定義。抽象數(shù)據(jù)類(lèi)型用三元組來(lái)表示：

(D、R、P)

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

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

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

…

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

…

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

操作名n;}ADT抽象數(shù)據(jù)類(lèi)型名稱數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第12頁(yè)。1.4算法1.4.1算法概述1.4.2算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系1.4.3算法的度量數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第13頁(yè)。1.4.1算法概述算法(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)。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第14頁(yè)。對(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)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第15頁(yè)。1.4.2算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系

著名的計(jì)算機(jī)科學(xué)家沃思(NikiklausWirth)提出一個(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)題。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第16頁(yè)。1.4.3算法的度量1.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指運(yùn)行算法時(shí)所需要消耗的時(shí)間資源。其定義是：如果一個(gè)問(wèn)題的規(guī)模是n，解決這一問(wèn)題的某一算法所需要的時(shí)間為T(mén)(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ù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第17頁(yè)。1.5算法分析1.5.1數(shù)學(xué)基礎(chǔ)1.5.2所需分析的問(wèn)題1.5.3運(yùn)行時(shí)間的計(jì)算1.5.4檢驗(yàn)?zāi)愕姆治鰯?shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第18頁(yè)。1.5.1數(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(mén)(N)的一個(gè)上界，也可以理解為T(mén)至多增長(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一樣快。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第19頁(yè)。定義

3

如果存在正常數(shù)、和，使得當(dāng)時(shí)，，則記為。上述定義表明，T與f有著相同的階數(shù)，或者兩者最終以相同的階數(shù)增長(zhǎng)。若，且，則。上面這些函數(shù)定義的目的是要在函數(shù)間建立一種相對(duì)的級(jí)別，通常比較的是它們的相對(duì)增長(zhǎng)率(relativerateofgrowth)。還需要掌握以下幾個(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)=。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第20頁(yè)。1.5.2所需分析的問(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ù)雜。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第21頁(yè)。1.5.3運(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í)間等于該層的for循環(huán)語(yǔ)句的運(yùn)行時(shí)間乘以該層循環(huán)內(nèi)所有的for循環(huán)的運(yùn)行時(shí)間。

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

if(condition)S1elseS2

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

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

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

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

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

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

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

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

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

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

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

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

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

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個(gè)元素之前插入一個(gè)新的元素e，使得線性表L變?yōu)殚L(zhǎng)度為L(zhǎng)istLength(L)+1的線性表

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

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

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

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

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

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

L

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

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

(1)創(chuàng)建了一個(gè)新的結(jié)點(diǎn)q。

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

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

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

(1)創(chuàng)建了一個(gè)新的結(jié)點(diǎn)q。

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

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

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

1)

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

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

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

2)

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

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

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

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

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

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

ADTStack{

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

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

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

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

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

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

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

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

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

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

3*4+5+6*7

可以將上述的計(jì)算順序書(shū)寫(xiě)為

34*5+67*+

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

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

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

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

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

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

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

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

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

ADTQueue{

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

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

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

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

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

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

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

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

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

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

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

s

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

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

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

ADTSTRING{

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

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

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

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

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

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

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

(1)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。

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

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

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

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

KMP算法中關(guān)鍵問(wè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)的最大值。此時(shí)的next[j+1]有下面兩種情況。數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第86頁(yè)。(1)若P[k]=P[j]，則說(shuō)明

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語(yǔ)言版)第2版上ppt全文共112頁(yè)，當(dāng)前為第87頁(yè)。4.3.3其他模式匹配算法1．Boyer-Moore算法此算法試圖從右到左地比較模式串P和目標(biāo)串S，在不匹配的情況下，Boyer-Moore算法把P向右移動(dòng)S中未涉及比較的字符數(shù)，因此Boyer-Moore算法可以跳過(guò)S中的字符來(lái)提高速度。

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

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

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

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

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

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

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

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

A=(A1,A2,…,An)

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

A1=(ai1,ai2,…,ain)

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

ADTARRAY{

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

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

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

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

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

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

Locate操作

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

Value操作

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

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

aij=aji0≤i，j≤n-1

則稱方陣A為對(duì)稱矩陣。

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

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