數(shù)據(jù)結(jié)構(gòu)課件

1、數(shù)據(jù)結(jié)構(gòu)講課教師：杜雅娟Emil:電話Q:295858698課程介紹數(shù)據(jù)結(jié)構(gòu)課程教學目標 使學生學會分析數(shù)據(jù)對象的特征，掌握數(shù)據(jù)組織方法和計算機中的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和算法，初步掌握算法空間分析的技巧，培養(yǎng)良好的程序設(shè)計技能。學習數(shù)據(jù)結(jié)構(gòu)的學習方法 學習數(shù)據(jù)結(jié)構(gòu)必須經(jīng)過大量的實踐，在實踐中體會構(gòu)造思維方法，掌握數(shù)據(jù)組織和程序設(shè)計的技術(shù)。 要求： （1）獨立完成作業(yè) （2）獨立完成實驗任務(wù) 考核要求：平時作業(yè)10% 實驗成績20% 期末卷面分數(shù)70% 為什么要學習數(shù)據(jù)結(jié)構(gòu)？為什么要學習數(shù)據(jù)結(jié)構(gòu)？v計算機加工處理的對象 純粹的數(shù)值

2、字符、表格和圖象等為了編寫一些“好”的程序，必須分析待處理對象的特性以及各處理對象間的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門學科形成和發(fā)展的原因。 1 1、“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”學科形成和發(fā)展的背學科形成和發(fā)展的背景景v計算機的應(yīng)用: 科學計算(數(shù)值計算) 控制、管理及數(shù)據(jù)處理(非數(shù)值計算)具有一定結(jié)構(gòu)的數(shù)據(jù)具有一定結(jié)構(gòu)的數(shù)據(jù)“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”學科形成和發(fā)展的背景學科形成和發(fā)展的背景形成階段：形成階段： 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學計算機科學系的教學計劃。發(fā)展階段：發(fā)展階段： 數(shù)據(jù)結(jié)構(gòu)的概念不斷擴充，包括了網(wǎng)絡(luò)

3、、集合代數(shù)論、關(guān)系等“離散數(shù)學結(jié)構(gòu)”的內(nèi)容。 70年代后期，我國高校陸續(xù)開設(shè)該課程。如今已成熟 數(shù)據(jù)結(jié)構(gòu)的研究目的是尋求有效的組織和處理非數(shù)值數(shù)據(jù)的理論技術(shù)和方法,這類數(shù)據(jù)具有量大且具有一定內(nèi)在邏輯關(guān)系的特點。 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容包括三個方面:數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu),存儲結(jié)構(gòu)存儲結(jié)構(gòu)以及相應(yīng)的基基本操作運算的定義和實現(xiàn)本操作運算的定義和實現(xiàn)。2 2、數(shù)據(jù)結(jié)構(gòu)的研究目的和研究內(nèi)容、數(shù)據(jù)結(jié)構(gòu)的研究目的和研究內(nèi)容前期課程前期課程后期課程后期課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計算機基礎(chǔ)計算機基礎(chǔ)C語言語言離散數(shù)學離散數(shù)學操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理數(shù)據(jù)庫原理數(shù)據(jù)庫原理軟件工程軟件工程承上承上啟下啟下 3

4、3、“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”是計算機及相關(guān)專業(yè)的專業(yè)基礎(chǔ)課之是計算機及相關(guān)專業(yè)的專業(yè)基礎(chǔ)課之一，是門十分重要的核心課程一，是門十分重要的核心課程。C語言語言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 軟件工程軟件工程掌握基本編掌握基本編程方法程方法掌握數(shù)據(jù)組掌握數(shù)據(jù)組織和數(shù)據(jù)處織和數(shù)據(jù)處理的方法理的方法掌握大型軟掌握大型軟件開發(fā)方法件開發(fā)方法學習識字學習識字學習寫作文學習寫作文學習寫小說學習寫小說基本要求課程關(guān)系與語文學習過程類比4 4、C C語言語言、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和和軟件工程軟件工程三門課之間的關(guān)系：三門課之間的關(guān)系：1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.2 1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 1

5、.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4 1.4 算法和算法分析算法和算法分析 一般來說，用計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：（1）首先要從具體問題抽象出一個適當?shù)臄?shù)學模型；（2）然后設(shè)計一個解此數(shù)學模型的算法；（3）最后編出程序、進行測試、調(diào)整直至得到最終解答。1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學的語言加以描述。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學模型為線性方程組；預報人口增長情況的數(shù)學模型為微分方程。然而，更多的非數(shù)值計算問題無法用數(shù)學方程加以描述。下面請看三個例子： 尋求數(shù)學

6、模型的實質(zhì)：例1:圖書館的書目檢索系統(tǒng)的自動化 在書目檢索系統(tǒng)中可以建立一張按登錄號順序排列的書目文件和三張分別按書名、作者名和分類號順序排列的索引表。 由這由這4 4張表構(gòu)成的文件張表構(gòu)成的文件便是書目自動檢索的數(shù)學便是書目自動檢索的數(shù)學模型，其中計算機處理的模型，其中計算機處理的對象之間存在著線性關(guān)系，對象之間存在著線性關(guān)系，這類數(shù)學模型可稱為線性這類數(shù)學模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。例例2 2：人和計算機對弈：人和計算機對弈算法：算法：模型：模型：對弈的規(guī)則和策略棋盤及棋盤的格局(a)(a)棋盤格局示例棋盤格局示例 計算機處理的對象之間有樹關(guān)系，計算機處理的對象之間有樹關(guān)系，對弈

7、過程就是從樹根到樹葉的過程。對弈過程就是從樹根到樹葉的過程。(b)(b)對弈樹的局部對弈樹的局部例例3 3 多叉路口交通燈的管理問題多叉路口交通燈的管理問題ABCDE 在路口有13條可行的通路，其中有的可以同時通行，如A至B和E至C，而有的不能同時通行，如E至B和A至D。 這類交通、道路問題的數(shù)學模型是一種稱為“圖”的數(shù)據(jù)結(jié)構(gòu)。五叉路口交通管理問題等價于對圖的頂點的染色問題。即要求對圖上的每個頂點染一種顏色，并且要求有連線的兩個頂點不能具有相同的顏色。BDBCDBABACADBADADCEAEBECED概括地說：概括地說： 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算程序設(shè)計問題中的

8、算程序設(shè)計問題中的計算機的操計算機的操作對象作對象以及它們之間以及它們之間關(guān)系關(guān)系和和操作操作等的學科。等的學科。1.2 1.2 基本概念基本概念一、一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、二、數(shù)據(jù)類型數(shù)據(jù)類型三、三、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 所有能被輸入到計算機中，且能被計算機所有能被輸入到計算機中，且能被計算機處理的符號的集合。處理的符號的集合。1 1、數(shù)據(jù)、數(shù)據(jù)(data)(data) 是計算機操作的對象的總稱。是計算機操作的對象的總稱。 是計算機處理的信息的某種特定的符號表是計算機處理的信息的某種特定的符號表示形式。示形式。是數(shù)據(jù)（集合）中的一個“個體”

9、。2 2、數(shù)據(jù)元素、數(shù)據(jù)元素(data element)(data element)是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位基本單位 3、數(shù)據(jù)項數(shù)據(jù)項(data item)(data item)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位最小單位數(shù)據(jù)元素可以是數(shù)據(jù)項的集合數(shù)據(jù)元素可以是數(shù)據(jù)項的集合例如：描述學生的數(shù)據(jù)元素可以是年年月月日日稱之為組合項稱之為組合項學號學號姓名姓名性別性別年齡年齡出生日期出生日期成績成績是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。整數(shù)數(shù)據(jù)對象是集合整數(shù)數(shù)據(jù)對象是集合N=0N=0，1 1，2 2，字母字符數(shù)據(jù)對象是集合字母字符數(shù)據(jù)對象是集合C=AC=A，BB，ZZ。 4 4、數(shù)據(jù)對象、數(shù)據(jù)對象

10、(Data Object)(Data Object)例如：5 5、數(shù)據(jù)結(jié)構(gòu)（、數(shù)據(jù)結(jié)構(gòu)（data structuredata structure）可以認為是帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序次序”關(guān)系關(guān)系 a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如: :又例，在2行3列的二維數(shù)組a1, a2, a3, a4, a5, a6中六個元素之間存在兩個關(guān)系: a1 a2 a3 a4 a5 a

11、6行的次序關(guān)系行的次序關(guān)系:列的次序關(guān)系列的次序關(guān)系: :row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合再例，在一維數(shù)組 a1, a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系次序關(guān)系:| i=1, 2, 3, 4, 5數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合可見，不同的“關(guān)系關(guān)系”構(gòu)成不同的“結(jié)構(gòu)結(jié)構(gòu)” 或者說，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)可歸結(jié)為以下四類四類: :

12、線性線性結(jié)構(gòu)樹形樹形結(jié)構(gòu)圖狀圖狀結(jié)構(gòu)集合集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structures = (D, S)其中:D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是 D上關(guān)系的有限集關(guān)系的有限集。例4，復數(shù)是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中，C=c1,c2;R=P,而P是定義在D上的一種關(guān)系用來表示c1是復數(shù)的實部，c2是復數(shù)的虛部。Group = (PGroup = (P，R) R) 例例5 5（P5 P5 例例1-51-5）其中其中: P = T: P = T，G1G1，GnGn，S11SnmS11Snm1=n=31=n=3

13、，1=m=21=m=2， R = R1, R2R = R1, R2R1 = | 1=i=n, 1=n=3 R1 = | 1=i=n, 1=n=3 R2 = | 1=i=n, 1=j=m, R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 1=n=3, 1=m=2 數(shù)據(jù)的數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu) 邏輯結(jié)構(gòu)在存儲器中的映象邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素數(shù)據(jù)元素”的映象的映象 ？“關(guān)系關(guān)系”的映象的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)元素的映象方法：用二進制位(bit)的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001

14、000001)2關(guān)系的映象方法：關(guān)系的映象方法：（表示x, y的方法）1 1、順序映象、順序映象借助元素在存儲器中的借助元素在存儲器中的相對位置相對位置來來表示數(shù)據(jù)元表示數(shù)據(jù)元素之間的關(guān)系素之間的關(guān)系借助指示元素存儲地址的指針（借助指示元素存儲地址的指針（PointerPointer）表示）表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)元素之間的邏輯關(guān)系。整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息2 2、非順序映象、非順序映象 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面，以后大家會看到，任何一個算法的設(shè)計取決于選定的數(shù)選定的數(shù)據(jù)據(jù)( (邏輯邏輯) )結(jié)構(gòu)，結(jié)構(gòu)，而算法的實現(xiàn)依

15、賴于采用的存儲結(jié)構(gòu)采用的存儲結(jié)構(gòu)。如何描述存儲結(jié)構(gòu)？ 通常只在高級語言（例如，C/C+）的層面上討論存儲結(jié)構(gòu)。即用高級編程語言中提供的數(shù)據(jù)類型描述之。 在用高級程序語言編寫的程序中在用高級程序語言編寫的程序中, ,必必須對程序中出現(xiàn)的每個變量、常量或表須對程序中出現(xiàn)的每個變量、常量或表達式達式, ,明確說明它們所屬的數(shù)據(jù)類型。不明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量同類型的變量, ,其所能取的值的范圍不同其所能取的值的范圍不同, ,所能進行的操作不同。所能進行的操作不同。 二、數(shù)據(jù)類型二、數(shù)據(jù)類型如如C/C+C/C+中的中的intint就是整型數(shù)據(jù)類型。就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合

16、它是所有整數(shù)的集合( (在在1616位計算機中位計算機中為為3276832768到到3276732767的全體整數(shù)的全體整數(shù)) )和相關(guān)和相關(guān)的整數(shù)運算的整數(shù)運算( (如、等如、等) )。例如，C 語言中提供的基本數(shù)據(jù)類型基本數(shù)據(jù)類型有:整型整型 int浮點型浮點型 float字符型字符型 char邏輯型邏輯型 bool （ C+語言）語言）雙精度型雙精度型 double實型（實型（ C+語言）語言） 數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。 不同類型的變量，其所能取的值的范圍值的范圍不同，所能進行的操作進行的操作不同。 那么，我們僅用高級編程語言中提供的數(shù)據(jù)類型描述存儲結(jié)構(gòu)就

17、可以了嗎？三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型 (Abstract Data Type 簡稱簡稱ADT) 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type簡寫為簡寫為ADT)指的是用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學模指的是用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學模型中抽象出來的邏輯數(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)和運算的具體實現(xiàn)算法。具體實現(xiàn)算法。 抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（抽象數(shù)據(jù)類型可用（D D，S S，P P）三元組表示。）三元組表示。其

18、中：其中：D D 是數(shù)據(jù)對象；是數(shù)據(jù)對象； S S 是是 D D 上的關(guān)系集；上的關(guān)系集； P P 是對是對 D D 的基本操作集。的基本操作集。 ADT ADT 有兩個重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象用用ADTADT描述程序處理的實體時，強調(diào)的是其本描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝數(shù)據(jù)封裝將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分離，并將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。其內(nèi)部實現(xiàn)細節(jié)。ADTADT 抽

19、象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義 ADT ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述 賦值參數(shù)賦值參數(shù) 只為操作提供輸入值。引用參數(shù)引用參數(shù) 以& &打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作結(jié)果操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始

20、條件為空，則省略之。例例6 6，抽象數(shù)據(jù)類型復數(shù)復數(shù)的定義： 數(shù)據(jù)對象：數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復數(shù)的實數(shù)部分 | e2 是復數(shù)的虛數(shù)部分 ADT Complex 基本操作：基本操作：AssignComplex( &Z, v1, v2 )AssignComplex( &Z, v1, v2 ) 操作結(jié)果：構(gòu)造復數(shù) Z,其實部和虛部 分別被賦以參數(shù) v1 和 v2 的值。DestroyComplex( &Z) 操作結(jié)果：復數(shù)Z被銷毀。 GetReal( Z, &realPart )GetReal( Z,

21、 &realPart ) 初始條件：復數(shù)已存在。 操作結(jié)果：用realPart返回復數(shù)Z的實部值。 GetImag( Z, &ImagPart )GetImag( Z, &ImagPart )初始條件：復數(shù)已存在。操作結(jié)果：用ImagPart返回復數(shù)Z的虛部值。 Add( z1,z2, &sum )Add( z1,z2, &sum )初始條件：z1, z2是復數(shù)。操作結(jié)果：用sum返回兩個復數(shù)z1, z2 的和值。 ADT Complex假設(shè):z1和z2是上述定義的復數(shù)則 Add(z1, z2, z3) 操作的結(jié)果z3 = z1 + z2即抽象數(shù)據(jù)類型的

22、好處：對外部用戶隱藏其內(nèi)部細節(jié)例例7 7：抽象數(shù)據(jù)類型三元組的定義：抽象數(shù)據(jù)類型三元組的定義ADTTriplet 數(shù)據(jù)對象：D=e1,e2,e3 | e1,e2,e3ElemSet 數(shù)據(jù)關(guān)系：R1=, 基本操作： InitTriplet(&T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三個元組T，元素e1,e2和e3分別被賦以參數(shù)v1,v2和v3的值。 DestroyTriplet(&T) 操作結(jié)果：三元組T被銷毀Get(T , i, &e ) 初始條件：三元組T已存在，1i3 操作結(jié)果：用e返回T的第i個元的值。Put(&T, i, e ) 初始條件：三元組T已存在

23、，1i3 操作結(jié)果：改變T的第i個元的值。IsAscending(T) 初始條件：三元組T已存在 操作結(jié)果：如果T的元素按升序排列，則返回1，否則返回0。 IsDscending(T) 初始條件：三元組T已存在 操作結(jié)果：如果T的元素按降序排列，則返回1，否則返回0。 Max(T,&e) 初始條件：三元組T已存在 操作結(jié)果：用e返回T的3個元素中的最大值。Min(T,&e) 初始條件：三元組T已存在 操作結(jié)果：用e返回T的3個元素中的最小值。ADT Triplet1.3 1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)一、介紹介紹C/C+C/C+命令命令二、抽象數(shù)據(jù)類型

24、的表示和實現(xiàn)二、抽象數(shù)據(jù)類型的表示和實現(xiàn)二、抽象數(shù)據(jù)類型的表示和實現(xiàn)二、抽象數(shù)據(jù)類型的表示和實現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù)類型類型來表示和實現(xiàn)。例例8 8 抽象數(shù)據(jù)類型三元組（抽象數(shù)據(jù)類型三元組（Trip1etTrip1et）的表）的表示和實現(xiàn)。示和實現(xiàn)。/-/-采用動態(tài)分配的順序存儲結(jié)構(gòu)采用動態(tài)分配的順序存儲結(jié)構(gòu)typedef ElemType *Triplet；/Triplet/Triplet類型是類型是ElemTypeElemType類型的指針，類型的指針，/存放存放ElemTypeElemType類型的地址。類型的地址。/-/-基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明-

25、 Status InitTriplet (Triplet &TStatus InitTriplet (Triplet &T，ElemType vlElemType vl，ElemType v2ElemType v2， ElemType v3)ElemType v3)； /操作結(jié)果：構(gòu)造了三元組操作結(jié)果：構(gòu)造了三元組T T，元素，元素e1e1，e2e2和和e3e3分別被賦以參數(shù)分別被賦以參數(shù)v1v1，v2v2和和v3v3的值。的值。Status DestroyTriplet (Trlplet &T)Status DestroyTriplet (Trlplet &T

26、)； /操作結(jié)果：三元組操作結(jié)果：三元組T T被銷毀。被銷毀。Status Put(Triplet &TStatus Put(Triplet &T，int iint i，ElemType e )ElemType e ) ; ; / /初始條件：三元組初始條件：三元組T T已存在，已存在，1i31i3。 /操作結(jié)果：改變操作結(jié)果：改變T T的第的第i i元的值為元的值為e eStatus Get(Triplet TStatus Get(Triplet T，int iint i，ElemType &e)ElemType &e)；/初始條件：三元組初始條件：三元組T

27、T已存在，已存在，1i31i3。/操作結(jié)果：用操作結(jié)果：用e e返回返回T T的第的第i i元的值。元的值。Status IsDescending (Triplet T)Status IsDescending (Triplet T)；/初始條件：三元組初始條件：三元組T T已存在。已存在。/操作結(jié)果：如果操作結(jié)果：如果T T的三個元素按降序排列，的三個元素按降序排列，/則返回則返回1 1，否則返回，否則返回0 0。Status IsAscending (Triplet T)Status IsAscending (Triplet T)；/初始條件：三元組初始條件：三元組T T已存在。已存在。/操

28、作結(jié)果：如果操作結(jié)果：如果T T的三個元素按升序排列，則返的三個元素按升序排列，則返回回1 ,1 ,否則返回否則返回0 0。Status Min(Triplet TStatus Min(Triplet T，ElemType &e)ElemType &e)；/初始條件：三元組初始條件：三元組T T已存在。已存在。/操作結(jié)果：用操作結(jié)果：用e e返回返回T T的三個元素中的最小值。的三個元素中的最小值。Status Max(Triplet TStatus Max(Triplet T，ElemType &e)ElemType &e)；/初始條件：三元組初始條件：三元組

29、T T已存在。已存在。/操作結(jié)果：用操作結(jié)果：用e e返回返回T T的三個元素中的最大值。的三個元素中的最大值。/- - - - -/- - - - -基本操作的實現(xiàn)基本操作的實現(xiàn)- - - - - - - - - - - - Status InitTriplet(Triplet &T，ElemType vl，ElemType v2，ElemType v3) /構(gòu)造二元組構(gòu)造二元組T T，依次置，依次置T T的三個元素的初值為的三個元素的初值為v1v1，v2v2和和v3v3。 T = (ElemType *)malloc(3 * sizeof(ElemType)； if ( !T )

30、exit (OVERFLOW)； /分配存儲空間失敗 T0 = v1； T1 = v2；T2 = v3； return OK； /InitTriplet Status DestroyTriplet (Triplet &T)/銷毀三元組T。free(T)；T = NULL； eturn OK；/ DestroyTripletStatus Get ( Triplet T，int i，ElemType &e) /1i3，用e返回T的第i元的值。if(i3) return ERROR；e = Ti-1；return OK； /GetStatus Put(Triplet &T，i

31、nt i，ElemType e) /1i3，置T的第i元的值為e。if (i3) return ERROR；Ti-1 = e；return OK；/PutStatus lsAscending (Triplet T)/如果T的三個元素按升序排列，則返回1，否則返回0。return(T0=T1)&(T1=T1)&(T1=T2)； /IsDescending Status Max( Triplet T，ElemType e)/用e返回指向T的最大元素的值。e = (T0 =T1) ? ( (T0 =T2)? T0 : T2) : ( (T1=T2)? T1 : T2) ；return

32、 OK； /MaxStatus Min (Triplet T，ElemType e)/用e返回指向T的最小元素的值。e = (T0=T1)? ( (T0 =T2)? T0 : T2) : ( (T1=0)個初始數(shù)據(jù)的輸入。 （5 5）輸出數(shù)據(jù)）輸出數(shù)據(jù)-一個算法有一個或多個與輸入有某種關(guān)系的有效信息的輸出。 思考：算法與程序有何區(qū)別？例例9 考慮下列兩段描述：考慮下列兩段描述：(1)void exam1( ) n2; while (n%20) nn+2; printf(%dn,n); (2)void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 這兩段描述

33、均不能滿足算法的特征這兩段描述均不能滿足算法的特征,試問試問它們違反了哪些特征？它們違反了哪些特征？算法與程序的區(qū)別算法與程序的區(qū)別程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的求解過程，而程序則是算法在計算機上的實現(xiàn)。算法用特定的程序設(shè)計語言來描述，就成了程序。1.4.2 1.4.2 算法設(shè)計的要求算法設(shè)計的要求通常設(shè)計一個通常設(shè)計一個“好好”的算法應(yīng)考慮達到以下目的算法應(yīng)考慮達到以下目標：標：(1)(1)正確性正確性 (Correctness) p14(Correctness) p14(2)(2)可讀性可讀性(Readability)(Readability)

34、 (3)(3)健壯性健壯性(Robustness)(Robustness) (4)(4)效率與低存儲量需求效率與低存儲量需求 (1) (1) 正確性正確性 首先，首先，算法應(yīng)當滿足滿足以特定的“規(guī)格說明規(guī)格說明”方式給出的需求需求。 其次，其次，對算法是否“正確正確”的的理解可以有以下四個層次四個層次：a a程序中不含語法錯誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c.程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第c c層意義的正確性作為衡量一個算法是否合格的標準。 d.d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；(2) (2)

35、 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計算機執(zhí)行，因此算法應(yīng)該易易于于人的理解理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試。(3) (3) 健壯性健壯性 當輸入的數(shù)據(jù)非法非法時，算法應(yīng)當恰當?shù)刈鞒龇从郴蜻M行相應(yīng)處理進行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個表示錯表示錯誤或錯誤性質(zhì)的值誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。(4) (4) 高效率與低存儲量需求高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模

36、有關(guān)。1.4.3 1.4.3 算法效率的度量算法效率的度量度量一個程序的執(zhí)行時間通常有兩種方法：度量一個程序的執(zhí)行時間通常有兩種方法：(1)(1)事后統(tǒng)計的方法事后統(tǒng)計的方法( (算法編為程序后算法編為程序后) )(2)(2)事前分析估算的方法事前分析估算的方法 P14P14事后統(tǒng)計法事后統(tǒng)計法事前分析估算法事前分析估算法缺點：缺點：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)和算法執(zhí)行時間時間相關(guān)的因素因素：1 1算法算法選用的策略的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言語言4 4編譯編譯程序產(chǎn)生的機器代碼的質(zhì)量的質(zhì)量5 5計算機計算機執(zhí)行指令的速度的速度 一個特定算法的算法的“運行工

37、作量運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長，算算法執(zhí)行時間的增長率和法執(zhí)行時間的增長率和 f(n) f(n) 的增長率相的增長率相同同，則可記作：T (n) = O(f(n)稱稱T (n) T (n) 為算法的為算法的(漸近)時間復雜度。時間復雜度。 記號記號“O”讀作讀作“大大O”,它表示隨問題規(guī)模它表示隨問題規(guī)模n的增的增大算法執(zhí)行時間的增長率和大算法執(zhí)行時間的增長率和f(n)的增長率相同。的增長率相同?！癘”的形式定義為：的形式定義為： 若若f(n)是正整數(shù)是正整數(shù)n的一個函數(shù)的一個函數(shù),

38、則則T(n)=O(f(n)表示表示存在一個正的常數(shù)存在一個正的常數(shù)M,使得當使得當nn0時都滿足：時都滿足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的最高階的最高階,忽略其低階項和常系忽略其低階項和常系數(shù)數(shù),這樣既可簡化這樣既可簡化T(n)的計算的計算,又能比較客觀地反映出又能比較客觀地反映出當當n很大時很大時,算法的時間性能。算法的時間性能。 例如例如,T(n)=3n2-5n+10000=O(n2)如何估算如何估算 算法的時間復雜度？算法的時間復雜度？算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間算法的執(zhí)行時間 =原操作原

39、操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時間的執(zhí)行時間算法的執(zhí)行時間算法的執(zhí)行時間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和成正比成正比 從算法中選取一種對于所研究的問題來說是 基本操作基本操作 的原操作，以該基本操作 在算法中重復執(zhí)行的次在算法中重復執(zhí)行的次數(shù)數(shù)作為算法運行時間的衡量準則。例例兩兩個個矩矩陣陣相相乘乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k1

40、& change; -i) / bubble_sort基本操作: 賦值賦值操作時間復雜度: O(nO(n2 2) ) change = FALSE; / change 為元素進行交換標志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡(1)(1)當當a a中初始序列為自小至大有序，基本操中初始序列為自小至大有序，基本操作的執(zhí)行次數(shù)為作的執(zhí)行次數(shù)為0 0；(2)(2)當當a a中初始序列為自大至小有序時，基本中初始序列為自大至小有序時，基本操作的執(zhí)行次數(shù)為操作的執(zhí)行次數(shù)為n(n-1)/2.n(n-1)/2.對于這類算法的分析，一種解決的

41、辦法是計對于這類算法的分析，一種解決的辦法是計算它的算它的平均值，平均值，即考慮它對所有可能的輸入即考慮它對所有可能的輸入數(shù)據(jù)集的期望值，此時相應(yīng)的時間復雜度為數(shù)據(jù)集的期望值，此時相應(yīng)的時間復雜度為算法的算法的平均時間復雜度。平均時間復雜度。另一種更可行也更常用的辦法是討論算法另一種更可行也更常用的辦法是討論算法在在最壞情況下的時間復雜度，最壞情況下的時間復雜度，即分析最即分析最壞情況以估算算法執(zhí)行時間的一個上界。壞情況以估算算法執(zhí)行時間的一個上界。除特別指明外，除特別指明外，以后討論的時間復雜度均以后討論的時間復雜度均指最壞情況下的時間復雜度。指最壞情況下的時間復雜度。 一個沒有循環(huán)的算法的

42、基本運算次數(shù)與問題規(guī)模一個沒有循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n n無關(guān)無關(guān), ,記作記作O(1),O(1),也稱作常數(shù)階。也稱作常數(shù)階。 一個只有一重循環(huán)的算法的基本運算次數(shù)與問一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模題規(guī)模n n的增長呈線性增大關(guān)系的增長呈線性增大關(guān)系, ,記作記作O(n),O(n),也稱線性也稱線性階。階。 其余常用的還有平方階其余常用的還有平方階O(nO(n2 2) )、立方階、立方階O(nO(n3 3) )、對數(shù)階對數(shù)階O(logO(log2 2n)n)、指數(shù)階、指數(shù)階O(2O(2n n) )等。等。 各種不同數(shù)量級對應(yīng)的值存在著如下關(guān)系：各種不同數(shù)量級對應(yīng)的

43、值存在著如下關(guān)系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!) 例例1.4 求兩個求兩個n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分分析其時間復雜度。析其時間復雜度。 #define MAX 20 /*定義最大的方階定義最大的方階*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 該算法中的基本運算是兩重循環(huán)中最深層的語句該算法中的基本運算是兩重循環(huán)中最

44、深層的語句Cij=Aij+Bij,分析它的頻度分析它的頻度,即即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的時分析以下算法的時間復雜度。間復雜度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); 解：解：該算法的基本操該算法的基本操作是語句作是語句s+,其頻度：其頻度： T(n)= =O(n3)則該算法的時間復雜度則該算法的時間復雜度為為O(n3)。 niijjk0001例：兩個NN矩

45、陣相乘的算法如下 for(i = 1；i = n；+i) for(j = 1；j = n；+j) cij = 0； for(k = = 1；k = n；+k) cij + = aik * bki； “乘法乘法”運算是運算是“矩陣相乘問題矩陣相乘問題”的基本操作。整的基本操作。整個算法的執(zhí)行時間與該基本操作個算法的執(zhí)行時間與該基本操作( (乘法乘法) )重復執(zhí)行的重復執(zhí)行的次數(shù)次數(shù)n n3 3成正比，記作成正比，記作T(n) = O(nT(n) = O(n3 3) )。example(n) if (n = 1)returnfor i = 1 to nx = x + 1example(n/2)1.

46、4.4 1.4.4 算法的存儲空間需求算法的存儲空間需求算法的空間復雜度定義為空間復雜度定義為: : 表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增大，算法的增大，算法運行所需存儲量的增長率與運行所需存儲量的增長率與g(n) g(n) 的增的增長率相同。長率相同。S(n) = O(g(n)算法的存儲量算法的存儲量包括:1 1輸入數(shù)據(jù)所占空間輸入數(shù)據(jù)所占空間2 2程序本身所占空間程序本身所占空間3 3輔助變量所占空間輔助變量所占空間 若輸入數(shù)據(jù)輸入數(shù)據(jù)所占空間只取決于問題本身，和和算法無關(guān)算法無關(guān)，則只需要分析除輸入和程序之外的輔輔助變量助變量所占額外空間額外空間。 若所需額外空間相對于輸入數(shù)據(jù)

47、量來說是常數(shù)，則稱此算法為原地工作原地工作。 若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。數(shù)據(jù)結(jié)構(gòu)參考書數(shù)據(jù)結(jié)構(gòu)參考書: :1、數(shù)據(jù)結(jié)構(gòu)教程數(shù)據(jù)結(jié)構(gòu)教程 李春葆李春葆 清華大學出版社清華大學出版社 200520052 2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C(C語言描述語言描述) )學習指導與習題解答學習指導與習題解答 徐孝凱徐孝凱 賀桂英編著賀桂英編著 清華大學出版社清華大學出版社 199719973 3、從、從數(shù)據(jù)結(jié)構(gòu)習題與解析數(shù)據(jù)結(jié)構(gòu)習題與解析第第2 2版李春葆編著，版李春葆編著，清華大學出版社清華大學出版社20042004年年2 2月第二版中選擇習題留作業(yè)月第二版中選擇習題留作業(yè) 。1 1、熟

48、悉各名詞、術(shù)語的含義，深刻理解基本概念，、熟悉各名詞、術(shù)語的含義，深刻理解基本概念，尤其是理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相尤其是理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關(guān)系?；ラg的關(guān)系。2 2、清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)、清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)。別以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)。3 3、了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。、了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。4 4、理解抽象數(shù)據(jù)類型的概念。、理解抽象數(shù)據(jù)類型的概念。5 5、理解算法的概念及其五個特性，掌握進行簡單算、理解算法的概念及其五個特性，掌握進

49、行簡單算法分析的方法。法分析的方法。教學要求教學要求補充內(nèi)容采用采用C/C+C/C+語言描述算法時應(yīng)該注意的事項語言描述算法時應(yīng)該注意的事項 說明：說明：C+語言中提供了一種語言中提供了一種引用引用運算符運算符“&”,引用是個別名引用是個別名,當建立引用時當建立引用時,程序用另一個程序用另一個已定義的變量或?qū)ο笠讯x的變量或?qū)ο?目標目標)的名字初始化它的名字初始化它,從那從那時起時起,引用作為目標的別名而使用引用作為目標的別名而使用,對引用的改動對引用的改動實際就是對目標的改動。實際就是對目標的改動。 注意：注意：Turbo C不支持引用類型。不支持引用類型。例如：例如： int a

50、=4; /*a為普通的整型變量為普通的整型變量*/ int &b=a; /*b是是a的引用變量的引用變量*/ 這里說明這里說明b變量是變量變量是變量a的引用的引用,b也等于也等于4,之后這兩之后這兩個變量同步改變。當個變量同步改變。當a改變時改變時b也同步改變，同樣，當也同步改變，同樣，當b改變時改變時a也同步改變。也同步改變。 引用常用于函數(shù)形參中引用常用于函數(shù)形參中, ,采用引用型形參時采用引用型形參時, ,在函在函數(shù)調(diào)用時將形參的改變回傳給實參數(shù)調(diào)用時將形參的改變回傳給實參, ,例如例如, ,有如下函數(shù)有如下函數(shù)( (其中的形參均為引用型形參其中的形參均為引用型形參) )： vo

51、id swap(int &x,int &y) void swap(int &x,int &y) / /* *形參前的形參前的“&”&”符號不是指針運算符符號不是指針運算符* */ / int temp=x; int temp=x; x=y;y=temp x=y;y=temp 當用執(zhí)行語句當用執(zhí)行語句swap(a,b)swap(a,b)時時,a,a和和b b的值發(fā)生了交換。的值發(fā)生了交換。 反之，有以下函數(shù)反之，有以下函數(shù)swap1( )，當用執(zhí)行語句，當用執(zhí)行語句swap1(a,b)時時,a和和b的值不會發(fā)生了交換。的值不會發(fā)生了交換。 void

52、 swap1(int x,int y) int temp; temp=a;a=b;b=temp; 在在C語言中，由于不支持引用類型，所以采用指語言中，由于不支持引用類型，所以采用指針的方式來回傳形參的值，需將上述函數(shù)改為：針的方式來回傳形參的值，需將上述函數(shù)改為： int swap2(int *x, int *y) int temp; temp=*a;/*將將a的值放在的值放在temp中中*/*a=*b; /*將將a所指的值改為所指的值改為*b*/ *b=temp；/*將將b所指的值改為所指的值改為temp*/ 上述函數(shù)的調(diào)用改為上述函數(shù)的調(diào)用改為swap2(&a,&b)，顯然

53、遠不，顯然遠不如采用引用方式簡潔。所以本書后面很多算法都采如采用引用方式簡潔。所以本書后面很多算法都采用引用形參。用引用形參。二、介紹二、介紹C/C+C/C+命令命令（1 1）預定義常量和類型：）預定義常量和類型：/函數(shù)結(jié)果狀態(tài)代碼函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status是函數(shù)的類型，其值是函數(shù)結(jié)果是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼狀態(tài)代碼typedef int Status；(2) (2) 數(shù)據(jù)結(jié)構(gòu)的表示數(shù)據(jù)

54、結(jié)構(gòu)的表示數(shù)據(jù)結(jié)構(gòu)的表示(存儲結(jié)構(gòu))用類型定義(typedef)描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。(3) (3) 基本操作的算法都用以下形式的基本操作的算法都用以下形式的函數(shù)描述：函數(shù)描述：函數(shù)類型函數(shù)名(函數(shù)參數(shù)表) /算法說明 語句序列 /函數(shù)名 (4) (4) 賦值語句賦值語句簡單賦值簡單賦值變量名變量名 = = 表達式；表達式；串聯(lián)賦值串聯(lián)賦值變量名變量名1 = 1 = 變量名變量名2 = = 2 = = 變量名變量名k = k = 表達式；表達式；成組賦值成組賦值 ( (變量名變量名1 1，變量名，變量名k) = (k) = (表達式表達式1

55、 1，表達，表達式式k)k)；結(jié)構(gòu)名結(jié)構(gòu)名 = = 結(jié)構(gòu)名；結(jié)構(gòu)名；結(jié)構(gòu)名結(jié)構(gòu)名 = (= (值值1 1，值，值k)k)；變量名變量名 = = 表達式；表達式；變量名變量名 起始下標起始下標.終止下標終止下標 = =變量名變量名 起始下標起始下標.終止下標終止下標 交換賦值交換賦值變量名變量名變量名；變量名；條件賦值條件賦值 變量名變量名 = = 條件表達式？條件表達式？ 表達式表達式 T : T : 表達式表達式 F F（5 5）選擇語句）選擇語句(6)(6)循環(huán)語句循環(huán)語句(7)(7)結(jié)束語句結(jié)束語句(8) (8) 輸入和輸出語句輸入和輸出語句(9) (9) 注釋注釋 單行注釋單行注釋 /

56、文字序列文字序列 (10) (10) 基本函數(shù)基本函數(shù)(11) (11) 邏輯運算約定邏輯運算約定 Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)計算機程序設(shè)計藝術(shù)計算機程序設(shè)計藝術(shù) 第第1卷卷 基本算法（第基本算法（第3版）版）（英文影印版）（英文影印版）作者: Donald E.Knuth / E.KNUTH副標題: 第1卷:基本算法(第3版)英文影印版ISBN: 9787302058144 十位: 7302058148定價: 80.00出版社: 清華大學出版社出版年: 2002-11-

57、1 作者簡介Donald.E.Knuth(唐納德.E.克努特，中文名高德納)是算法和程序設(shè)計技術(shù)的先驅(qū)者，是計算機排版系統(tǒng)TEX和METAFONT的發(fā)明者，他因這些成就和大量創(chuàng)造性的影響深遠的著作(19部書和160篇論文)而譽滿全球。作為斯坦福大學計算機程序設(shè)計藝術(shù)的榮譽退休教授，他當前正全神貫注于完成其關(guān)于計算機科學的史詩性的七卷集。這一偉大工程在1962年他還是加利福尼亞理工學院的研究生時就開始了。Knuth教授獲得了許多獎項和榮譽，包括美國計算機協(xié)會圖靈獎(ACM Turing Award)，美國前總統(tǒng)卡特授予的科學金獎(Medal of Science)，美國數(shù)學學會斯蒂爾獎(AMS

58、Steele Prize)，以及1996年11月由于發(fā)明先進技術(shù)而榮獲的備受推崇的京都獎(Kyoto Prize)。Knuth教授現(xiàn)與其妻Jill生活于斯坦福校園內(nèi)。 訪問Knuth教授的個人主頁，可以獲得有關(guān)本書及本系列其他未出版圖書的更多信息： /knuth 本書自第一版出版以來，已經(jīng)成為世界范圍內(nèi)廣泛使用的大學教材和專業(yè)人員的標準參考手冊。本書全面論述了算法的內(nèi)容，從一定深度上涵蓋了算法的諸多方面，同時其講授和分析方法又兼顧了各個層次讀者的接受能力。各章內(nèi)容自成體系，可作為獨立單元學習。所有算法都用英文和偽碼描述，使具備初步編程經(jīng)驗的

59、人也可讀懂。全書講解通俗易懂，且不失深度和數(shù)學上的嚴謹性。第二版增加了新的章節(jié)，如算法作用、概率分析與隨機算法、線性編程等，幾乎對第一版的各個部分都作了大量修訂。作者簡介作者簡介 Thomasd H.Cormen是達特茅斯學院計算機科學系副教授，Charles E.Leiserson是麻省理工學院計算機科學與電氣工程系教授，Ronald L.Rivest是麻省理工學院計算機科學系教授，Clifford Stein是哥倫比亞大學工程與運營研究所副教授。算法引論：一種創(chuàng)造性方法算法引論：一種創(chuàng)造性方法國外計算機科學教材系列國外計算機科學教材系列作者：（美）曼博（Manber，U.） 著，黃林鵬 等

60、譯 叢書名：國外計算機科學教材系列 出版社：電子工業(yè)出版社 ISBN：9787121016653 出版時間：2005-9-1 版次：1 印次： 頁數(shù)：334 字數(shù)：571000 紙張：膠版紙 包裝：平裝 開本： 線性結(jié)構(gòu)的線性結(jié)構(gòu)的基本特征基本特征為為: :1集合中必存在唯一的一個集合中必存在唯一的一個“第一元素第一元素”；2集合中必存在唯一的一個集合中必存在唯一的一個 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后繼唯一的后繼；4除第一元素之外，均有除第一元素之外，均有 唯一的前驅(qū)唯一的前驅(qū)。線性結(jié)構(gòu)線性結(jié)構(gòu) 是是 一個數(shù)據(jù)元素的一個數(shù)據(jù)元素的有序（次序）集有序（次序）集線性表線性表是一種最簡單的線性結(jié)構(gòu)線性結(jié)構(gòu)2.1 線性表的類型定義線性表的類型定義2.3 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 鏈式映象鏈式映象2.4 一元多項式的表示一元多項式的表示2.2 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 順序映象順序映象2.1線性表的類型定義線性表的類型定義抽象數(shù)據(jù)類型線性表線性表的定義如下：ADT List 數(shù)據(jù)對象數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 稱 n 為線性表的表長表長; 稱 n=0 時的線性表為空表空