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

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

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

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

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

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

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

8、算程序設(shè)計(jì)問題中的計(jì)算機(jī)的操計(jì)算機(jī)的操作對象作對象以及它們之間以及它們之間關(guān)系關(guān)系和和操作操作等的學(xué)科。等的學(xué)科。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) 所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號的集合。處理的符號的集合。1 1、數(shù)據(jù)、數(shù)據(jù)(data)(data) 是計(jì)算機(jī)操作的對象的總稱。是計(jì)算機(jī)操作的對象的總稱。 是計(jì)算機(jī)處理的信息的某種特定的符號表是計(jì)算機(jī)處理的信息的某種特定的符號表示形式。示形式。是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”

9、。2 2、數(shù)據(jù)元素、數(shù)據(jù)元素(data element)(data element)是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位基本單位 3、數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(data item)(data item)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位最小單位數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合例如：描述學(xué)生的數(shù)據(jù)元素可以是年年月月日日稱之為組合項(xiàng)稱之為組合項(xiàng)學(xué)號學(xué)號姓名姓名性別性別年齡年齡出生日期出生日期成績成績是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(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）可以認(rèn)為是帶結(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中六個(gè)元素之間存在兩個(gè)關(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)是一個(gè)二元組 Data_Structures = (D, S)其中:D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是 D上關(guān)系的有限集關(guān)系的有限集。例4，復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中，C=c1,c2;R=P,而P是定義在D上的一種關(guān)系用來表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(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ù)元素?cái)?shù)據(jù)元素”的映象的映象 ？“關(guān)系關(guān)系”的映象的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)元素的映象方法：用二進(jìn)制位(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)系。整個(gè)存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息整個(gè)存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息2 2、非順序映象、非順序映象 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面，以后大家會看到，任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)選定的數(shù)據(jù)據(jù)( (邏輯邏輯) )結(jié)構(gòu)，結(jié)構(gòu)，而算法的實(shí)現(xiàn)依

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

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

17、可以了嗎？三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型 (Abstract Data Type 簡稱簡稱ADT) 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type簡寫為簡寫為ADT)指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算的運(yùn)算,而不考慮計(jì)算機(jī)的具體存儲結(jié)構(gòu)和運(yùn)算的而不考慮計(jì)算機(jī)的具體存儲結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。具體實(shí)現(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 有兩個(gè)重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象用用ADTADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。其內(nèi)部實(shí)現(xiàn)細(xì)節(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)出錯(cuò)信息。操作結(jié)果操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始

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

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

22、好處：對外部用戶隱藏其內(nèi)部細(xì)節(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)造了三個(gè)元組T，元素e1,e2和e3分別被賦以參數(shù)v1,v2和v3的值。 DestroyTriplet(&T) 操作結(jié)果：三元組T被銷毀Get(T , i, &e ) 初始條件：三元組T已存在，1i3 操作結(jié)果：用e返回T的第i個(gè)元的值。Put(&T, i, e ) 初始條件：三元組T已存在

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

24、的表示和實(shí)現(xiàn)二、抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)二、抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)二、抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù)類型類型來表示和實(shí)現(xiàn)。例例8 8 抽象數(shù)據(jù)類型三元組（抽象數(shù)據(jù)類型三元組（Trip1etTrip1et）的表）的表示和實(shí)現(xiàn)。示和實(shí)現(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的三個(gè)元素按降序排列，的三個(gè)元素按降序排列，/則返回則返回1 1，否則返回，否則返回0 0。Status IsAscending (Triplet T)Status IsAscending (Triplet T)；/初始條件：三元組初始條件：三元組T T已存在。已存在。/操

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

29、T T已存在。已存在。/操作結(jié)果：用操作結(jié)果：用e e返回返回T T的三個(gè)元素中的最大值。的三個(gè)元素中的最大值。/- - - - -/- - - - -基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)- - - - - - - - - - - - Status InitTriplet(Triplet &T，ElemType vl，ElemType v2，ElemType v3) /構(gòu)造二元組構(gòu)造二元組T T，依次置，依次置T T的三個(gè)元素的初值為的三個(gè)元素的初值為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的三個(gè)元素按升序排列，則返回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)個(gè)初始數(shù)據(jù)的輸入。 （5 5）輸出數(shù)據(jù)）輸出數(shù)據(jù)-一個(gè)算法有一個(gè)或多個(gè)與輸入有某種關(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ū)別程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的求解過程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。算法用特定的程序設(shè)計(jì)語言來描述，就成了程序。1.4.2 1.4.2 算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求通常設(shè)計(jì)一個(gè)通常設(shè)計(jì)一個(gè)“好好”的算法應(yīng)考慮達(dá)到以下目的算法應(yīng)考慮達(dá)到以下目標(biāo)：標(biāo)：(1)(1)正確性正確性 (Correctness) p14(Correctness) p14(2)(2)可讀性可讀性(Readability)(Readability)

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

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

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

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

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

39、操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和成正比成正比 從算法中選取一種對于所研究的問題來說是 基本操作基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次在算法中重復(fù)執(zhí)行的次數(shù)數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。例例兩兩個(gè)個(gè)矩矩陣陣相相乘乘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基本操作: 賦值賦值操作時(shí)間復(fù)雜度: O(nO(n2 2) ) change = FALSE; / change 為元素進(jìn)行交換標(biāo)志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡(1)(1)當(dāng)當(dāng)a a中初始序列為自小至大有序，基本操中初始序列為自小至大有序，基本操作的執(zhí)行次數(shù)為作的執(zhí)行次數(shù)為0 0；(2)(2)當(dāng)當(dāng)a a中初始序列為自大至小有序時(shí)，基本中初始序列為自大至小有序時(shí)，基本操作的執(zhí)行次數(shù)為操作的執(zhí)行次數(shù)為n(n-1)/2.n(n-1)/2.對于這類算法的分析，一種解決的

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

42、基本運(yùn)算次數(shù)與問題規(guī)模一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模n n無關(guān)無關(guān), ,記作記作O(1),O(1),也稱作常數(shù)階。也稱作常數(shù)階。 一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問一個(gè)只有一重循環(huán)的算法的基本運(yù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 求兩個(gè)求兩個(gè)n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分分析其時(shí)間復(fù)雜度。析其時(shí)間復(fù)雜度。 #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; 該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語句該算法中的基本運(yùn)算是兩重循環(huán)中最

44、深層的語句Cij=Aij+Bij,分析它的頻度分析它的頻度,即即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的時(shí)分析以下算法的時(shí)間復(fù)雜度。間復(fù)雜度。 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)則該算法的時(shí)間復(fù)雜度則該算法的時(shí)間復(fù)雜度為為O(n3)。 niijjk0001例：兩個(gè)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； “乘法乘法”運(yùn)算是運(yùn)算是“矩陣相乘問題矩陣相乘問題”的基本操作。整的基本操作。整個(gè)算法的執(zhí)行時(shí)間與該基本操作個(gè)算法的執(zhí)行時(shí)間與該基本操作( (乘法乘法) )重復(fù)執(zhí)行的重復(fù)執(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 算法的存儲空間需求算法的存儲空間需求算法的空間復(fù)雜度定義為空間復(fù)雜度定義為: : 表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增大，算法的增大，算法運(yùn)行所需存儲量的增長率與運(yù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)教程 李春葆李春葆 清華大學(xué)出版社清華大學(xué)出版社 200520052 2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C(C語言描述語言描述) )學(xué)習(xí)指導(dǎo)與習(xí)題解答學(xué)習(xí)指導(dǎo)與習(xí)題解答 徐孝凱徐孝凱 賀桂英編著賀桂英編著 清華大學(xué)出版社清華大學(xué)出版社 199719973 3、從、從數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析第第2 2版李春葆編著，版李春葆編著，清華大學(xué)出版社清華大學(xué)出版社20042004年年2 2月第二版中選擇習(xí)題留作業(yè)月第二版中選擇習(xí)題留作業(yè) 。1 1、熟

48、悉各名詞、術(shù)語的含義，深刻理解基本概念，、熟悉各名詞、術(shù)語的含義，深刻理解基本概念，尤其是理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相尤其是理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系。互間的關(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)上施加的運(yùn)算及其實(shí)現(xiàn)。別以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)。3 3、了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。、了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。4 4、理解抽象數(shù)據(jù)類型的概念。、理解抽象數(shù)據(jù)類型的概念。5 5、理解算法的概念及其五個(gè)特性，掌握進(jìn)行簡單算、理解算法的概念及其五個(gè)特性，掌握進(jìn)

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

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

51、id swap(int &x,int &y) void swap(int &x,int &y) / /* *形參前的形參前的“&”&”符號不是指針運(yùn)算符符號不是指針運(yùn)算符* */ / int temp=x; int temp=x; x=y;y=temp x=y;y=temp 當(dāng)用執(zhí)行語句當(dāng)用執(zhí)行語句swap(a,b)swap(a,b)時(shí)時(shí),a,a和和b b的值發(fā)生了交換。的值發(fā)生了交換。 反之，有以下函數(shù)反之，有以下函數(shù)swap1( )，當(dāng)用執(zhí)行語句，當(dāng)用執(zhí)行語句swap1(a,b)時(shí)時(shí),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、遠(yuǎn)不，顯然遠(yuǎn)不如采用引用方式簡潔。所以本書后面很多算法都采如采用引用方式簡潔。所以本書后面很多算法都采用引用形參。用引用形參。二、介紹二、介紹C/C+C/C+命令命令（1 1）預(yù)定義常量和類型：）預(yù)定義常量和類型：/函數(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ù)類型時(shí)自行定義。(3) (3) 基本操作的算法都用以下形式的基本操作的算法都用以下形式的函數(shù)描述：函數(shù)描述：函數(shù)類型函數(shù)名(函數(shù)參數(shù)表) /算法說明 語句序列 /函數(shù)名 (4) (4) 賦值語句賦值語句簡單賦值簡單賦值變量名變量名 = = 表達(dá)式；表達(dá)式；串聯(lián)賦值串聯(lián)賦值變量名變量名1 = 1 = 變量名變量名2 = = 2 = = 變量名變量名k = k = 表達(dá)式；表達(dá)式；成組賦值成組賦值 ( (變量名變量名1 1，變量名，變量名k) = (k) = (表達(dá)式表達(dá)式1

55、 1，表達(dá)，表達(dá)式式k)k)；結(jié)構(gòu)名結(jié)構(gòu)名 = = 結(jié)構(gòu)名；結(jié)構(gòu)名；結(jié)構(gòu)名結(jié)構(gòu)名 = (= (值值1 1，值，值k)k)；變量名變量名 = = 表達(dá)式；表達(dá)式；變量名變量名 起始下標(biāo)起始下標(biāo).終止下標(biāo)終止下標(biāo) = =變量名變量名 起始下標(biāo)起始下標(biāo).終止下標(biāo)終止下標(biāo) 交換賦值交換賦值變量名變量名變量名；變量名；條件賦值條件賦值 變量名變量名 = = 條件表達(dá)式？條件表達(dá)式？ 表達(dá)式表達(dá)式 T : T : 表達(dá)式表達(dá)式 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) 邏輯運(yùn)算約定邏輯運(yùn)算約定 Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第第1卷卷 基本算法（第基本算法（第3版）版）（英文影印版）（英文影印版）作者: Donald E.Knuth / E.KNUTH副標(biāo)題: 第1卷:基本算法(第3版)英文影印版ISBN: 9787302058144 十位: 7302058148定價(jià): 80.00出版社: 清華大學(xué)出版社出版年: 2002-11-

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

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

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

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