數(shù)據(jù)結構教案第一章緒論

1、l 主講：蘇仕華1.1 引言1.2 基本概念和術語1.3 抽象數(shù)據(jù)類型1.4 算法和算法分析 1.4.1 算法 1.4.2 算法設計的要求 1.4.3 算法效率的度量 1.4.4 算法的存儲空間的需求l 計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題： 信息的表示和信息的處理 而信息的表示和組織又直接關系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結構又相當復雜。因此，為了編寫一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關系，這就是數(shù)據(jù)結構這門課所要研究的問題。l 在計算機發(fā)展的初期，人們

2、使用計算機的主要目的是處理數(shù)值計算問題。使用計算機解決一個具體問題時，一般需要經(jīng)過下列幾個步驟：l l 由于當時所涉及的運算對象是簡單的整型、實型或布爾等類型的數(shù)據(jù)，所以程序設計者的主要精力是集中于程序設計的技巧上，而無須重視數(shù)據(jù)結構。隨著計算機應用領域的擴大和軟、硬件的發(fā)展，非數(shù)值計算問題越來越顯得重要。據(jù)統(tǒng)計，處理非數(shù)值計算性問題占了90%以上的計算機運行時間，這類問題涉及到的數(shù)據(jù)結構更為復雜，數(shù)據(jù)元素之間的相互關系一般無法用數(shù)學方程式加以描述。因此，解決這類問題的關鍵不再是數(shù)學分析和計算方法，而是要設計出合適的數(shù)據(jù)結構，才能有效地解決問題。l 1.1 引言l 著名的瑞士計算機科學家沃思(

3、N.Wirth)教授曾提出，算法+數(shù)據(jù)結構=程序。這里的數(shù)據(jù)結構指的是數(shù)據(jù)的邏輯結構和存儲結構，而算法則是對數(shù)據(jù)運算的描述。由此可見，程序設計的實質是對實際問題選擇一種好的數(shù)據(jù)結構和設計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結構。因此，要設計出一個“好”的程序，就必須有好的算法，而好的算法必須建立在研究數(shù)據(jù)的特性及數(shù)據(jù)之間存在的關系的基礎上。這些正是數(shù)據(jù)結構結構這門課程所要研究的內容。l 到底什么是數(shù)據(jù)結構呢？先通過一個例子來說明有關數(shù)據(jù)結構的概念。l l例【1.1】電話號碼查詢系統(tǒng)l 設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：l (

4、a1，b1)(a2，b2)(an，bn)l 其中ai，bi(i=1，2n) 分別表示某人的名字和對應的電話號碼要求設計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。l 算法的設計，依賴于計算機如何存儲人的名字和對應的電話號碼，或者說依賴于名字和其電話號碼的結構。l l 數(shù)據(jù)的結構，直接影響算法的選擇和效率。l 上述的問題是一種數(shù)據(jù)結構問題。可將名字和對應的電話號碼設計成：二維數(shù)組、表結構、向量。 假定名字和其電話號碼邏輯上已安排成 n元向量的形式，它的每個元素是一個數(shù)對 (ai，bi)， 1in 數(shù)據(jù)結構

5、還要提供每種結構類型所定義的各種運算的算法。l【例1.2】圖書館信息檢索系統(tǒng)。l 當我們根據(jù)書名查找某本書有關情況的時候；或者根據(jù)作者或某個出版社查找有關書籍的時候，或根據(jù)書刊號查找作者和出版社等有關情況的時候，只要我們建立了相關的數(shù)據(jù)結構，按照某種算法編寫了相關程序，就可以實現(xiàn)計算機的自動檢索。若使用計算機處理上述圖書檢索問題，首先要建立一張圖書基本信息表，列在每一行上的是一本書的信息，一般包括：登錄號、書名、作者、分類號、出版社和出版時間等項，登錄號是唯一的。如表1.1所示。 表1.1 圖書目錄卡片表登錄號書 名作 者出版社出版時間分類號01771778 數(shù)據(jù)結構劉曉陽高等教育2000.0

6、873.96116201509429 操作系統(tǒng)許海平機械工業(yè)1999.1273.75219600592056 數(shù)據(jù)庫原理孫華英人民郵電2001.0573.32326501267435 軟件工程陳大鵬清華大學1998.11 73.561238 l 表中的數(shù)據(jù)元素(一行)可按登錄號、書名、作者名等建立相應的索引表。這些表構成的文件就是圖書目錄檢索的數(shù)學模型。計算機的主要操作是按某個特定要求（如書名、作者）對書目文檔進行查詢檢索。諸如此類的問題還有各種查號系統(tǒng)、倉庫管理系統(tǒng)、帳務處理等。這類問題中的處理對象之間都是一種最簡單的線性關系，它們所對應的數(shù)學模型稱為線性的數(shù)據(jù)結構。l【例1.3】圖的m著色

7、問題。l 圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使地圖的每個區(qū)域著一種顏色，且相鄰區(qū)域的顏色不同。如果把一個區(qū)域收縮為一個頂點，將相鄰兩個區(qū)域用一條邊相連接，就可以把一個區(qū)域圖抽象為一個平面圖和一個區(qū)域鄰接關系圖，如圖1.1(a)、(b)所示。 (a) 抽象的平面圖 (b) 區(qū)域鄰接關系圖 圖1.1 圖的著色問題示意圖l 19世紀50年代，英國學者提出了任何地圖都可以用4種顏色來著色的4著色猜想問題。過了100多年，這個問題才由美國學者在計算機上予以證明，這就是著名的4色定理。如在圖1.1中，顏色用數(shù)字表示，字母表示區(qū)域，則圖中表示了不同區(qū)域的不同著色情況。l 再例如

8、，家族的血統(tǒng)關系、博奕樹問題（人一機下棋）、計算機的文件系統(tǒng)等都是一種樹形結構；而城市之間的交通網(wǎng)絡、工程管理中的活動安排以及多叉路口交通燈管理等問題是圖形結構的。它們都是一種非線性的數(shù)據(jù)結構。l 通過以上幾例可以直接地認為：數(shù)據(jù)結構就是研究數(shù)據(jù)的邏輯結構和物理結構以及它們之間相互關系，并對這種結構定義相應的運算，而且確保經(jīng)過這些運算后所得到的新結構仍然是原來的結構類型。l 1.2 基本概念和術語l數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。例如，一個代數(shù)方程的求解程序中所使用的數(shù)據(jù)是整數(shù)和實數(shù)，而對一個文本編輯程序中使用的數(shù)

9、據(jù)是字符串。隨著計算機的發(fā)展以及計算機應用領域的擴大，數(shù)據(jù)的含義也隨之拓展了。例如，當今計算機可以處理的圖形、圖像、聲音等，它們也都屬于數(shù)據(jù)的范疇。 l數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。l 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。l 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。如前例中的目錄卡片表中的一張卡片（表格中的一行）、樹中的一個節(jié)點、圖的一個頂點等都是數(shù)據(jù)元素，有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（也稱為字段、域、屬性）組成，數(shù)據(jù)項是具有獨立含義的最小標識單位。如圖書卡片信息中的登錄號、書名、作者等。 l數(shù)據(jù)對象(Data Object)

10、：是性質相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。例如，大寫字母數(shù)據(jù)對象就是集合A,B,Z。l 數(shù)據(jù)結構(Data Structure)：是相互之間存在一種或多種特定關系(結構)的數(shù)據(jù)元素的集合。雖然至今沒有一個關于數(shù)據(jù)結構的標準定義，但它一般包括以下三個方面的內容：l (1) 數(shù)據(jù)元素之間的邏輯(或抽象)關系，也稱為數(shù)據(jù)的邏輯結構邏輯結構。l (2) 數(shù)據(jù)元素及其關系在計算機內的存儲方式，稱為數(shù)據(jù)的存儲結構存儲結構(物理結構物理結構)。 (3) 數(shù)據(jù)的運算運算，即對數(shù)據(jù)元素施加的操作(行為)。數(shù)據(jù)結構：數(shù)據(jù)結構：帶結構結構的數(shù)據(jù)元素的集合 一個特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一

11、種或多種特定的關系，則稱為一個數(shù)據(jù)結構。指的是數(shù)據(jù)元素之間存在的關系 這種結構又分為邏輯結構和存儲結構l 數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)的，它與數(shù)據(jù)元素的存儲結構無關，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。l 如上一節(jié)中表1.1所表示的圖書目錄卡片，表中數(shù)據(jù)元素之間的邏輯關系就是一種相鄰關系：對表中任一個結點，與它相鄰且在它前面的結點稱為直直接前趨，接前趨，這種直接前驅最多只有一個；與表中任一結點相鄰且在其后面的結點稱為直接后繼，直接后繼，也最多只有一個。表中只有第一個結點沒有直接前趨，稱之為開始結點開始結點；也只有最后一個結點沒有直

12、接后繼，稱之為終端結點終端結點。例如，表中的“操作系統(tǒng)”所在結點的直接前趨結點和直接后繼結點分別是“數(shù)據(jù)結構”和“數(shù)據(jù)庫原理”所在的結點，這種結點之間的關系就構成了圖書目錄卡片表的邏輯結構。數(shù)據(jù)的邏輯結構又可分為兩大類：l(1)線性結構 線性結構的特征是：數(shù)據(jù)元素(結點)之間存在著一對一的關系，且結構中有僅有一個開始結點和一個終端結點，其余結點都是有僅有一個直接前趨和一個直接后繼。因此，上述圖書目錄卡片表就是一個典型的線性結構。l(2)非線性結構l 非線性結構的特征是：數(shù)據(jù)元素之間存在著一對多或多對多的關系，即一個結點可能有多個直接前趨和多個直接后繼。該結構包括樹形結構、圖形結構和網(wǎng)狀結構等。

13、l 數(shù)據(jù)結構的邏輯結構常又細分為以下四類基本結構：l 一、線性結構 結構中的數(shù)據(jù)元素之間存在一對一的關系。l 二、樹型結構 結構中的數(shù)據(jù)元素之間存在一對多的關系。l 三、圖狀結構或網(wǎng)狀結構 結構中的數(shù)據(jù)元素之間存在多對多的關系。l 四、集合 結構中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關系。l 后三種都屬于非線性結構從關系關系或結構結構分，數(shù)據(jù)結構，數(shù)據(jù)結構可歸結為以下四類四類: : 數(shù)據(jù)結構的形式定義為：數(shù)據(jù)結構是一個二元組： Data-Structure=(D，S) 其中：D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。 例 復數(shù)的數(shù)據(jù)結構定義如下： Complex=(C，R) 其中：C是含

14、兩個實數(shù)的集合C1，C2，分別表示復數(shù)的實部和虛部。R=P，P是定義在集合上的一種關系C1，C2。 例如，當用三個三個 4 位的十進制數(shù)位的十進制數(shù)表示一個含 12 位數(shù)的十進制數(shù)時，位數(shù)的十進制數(shù)時，3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序次序”關系關系 a1, a2 、 a2, a3 3214，6587，9345 6587，3214，9345a1 a2 a3a2 a1 a3又例，在 2 行 3 列的二維數(shù)組中六個元素a1, a2, a3, a4, a5, a6之間存在兩個關系:行的次序關系行的次序

15、關系:row = ,col = , a1 a2 a3 a4 a5 a6列的次序關系列的次序關系: : 若在 6 個數(shù)據(jù)元素a1, a2, a3, a4, a5, a6 之間存在如下的次序關系次序關系:| i=1, 2, 3, 4, 5 數(shù)據(jù)結構數(shù)據(jù)結構是相互之間存在著某種邏相互之間存在著某種邏輯關系的數(shù)據(jù)元素的集合輯關系的數(shù)據(jù)元素的集合。可見，不同的“關系關系”構成不同的“結構結構” 則構成一維數(shù)組一維數(shù)組的定義。 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表示（映象），亦稱為數(shù)據(jù)的物理結構。它包括數(shù)據(jù)元素和關系的表示，是依賴于計算機語言的。數(shù)據(jù)的存儲結構可以用以下四種基本的存儲方法實

16、現(xiàn)：l(1) 順序存儲方法l 該方法是把邏輯上相鄰的結點存儲在物理位置上也相鄰的連續(xù)存儲單元里，由此得到的存儲結構稱為順序存儲結構順序存儲結構。它通常是借助于程序設計語言的數(shù)組來描述的。該方法主要應用于線性的數(shù)據(jù)結構，但非線性的數(shù)據(jù)結構也可通過某種線性化的方法來實現(xiàn)順序存儲。 l(2) 鏈接存儲方法 l 該方法是用一組不一定連續(xù)的存儲單元存儲邏輯上相鄰的元素，元素間的邏輯關系是由附加的指針域表示的。由此得到的存儲結構稱為鏈式存儲結構鏈式存儲結構。它通常是借助于程序設計語言中的指針來描述的l(3) 索引存儲方法l 該方法通常是在存儲元素信息的同時，還建立附加的索引表。表中的索引項一般形式是：(關

17、鍵字，地址)，關鍵字是能唯一標識一個元素的一個數(shù)據(jù)項或多個數(shù)據(jù)項的組合。l(4) 散列存儲方法l 該方法的基本思想是根據(jù)元素的關鍵字直接計算出該元素的存儲地址。 l 無論怎樣定義數(shù)據(jù)結構，都應該將數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構及數(shù)據(jù)的運算這三方面看成一個整體。因此，存儲結構是數(shù)據(jù)結構不可缺少的一個方面。l 同一種邏輯結構采用不同的存儲方法，可以得到不同的存儲結構。選擇何種存儲結構來表示相應的邏輯結構，要視具體的應用系統(tǒng)要求而定，而主要考慮的還是運算方便及算法的時間和空間上的要求。l 數(shù)據(jù)的運算數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結構上的，每種邏輯結構都有一個運算的集合，最常用的運算有：檢索、插入、刪除

18、、更新、排序等。數(shù)據(jù)運算是數(shù)據(jù)結構不可分割的一個方面，在給定了數(shù)據(jù)的邏輯結構和存儲結構之后，按定義的運算集合及其運算性質的不同，可能導致完全不同的數(shù)據(jù)結構。例如，若對線性表的插入、刪除運算限制在表的一端進行，則該線性表稱為棧；若對線性表的插入運算限制在表的一端，而刪除運算限制在表的另一端，則該線性表稱為隊列。 l 數(shù)據(jù)類型：(data type)是和數(shù)據(jù)結構密切相關的一個概念。所謂數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。在使用高級程序設計語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的數(shù)據(jù)類型。類型規(guī)定了在程序執(zhí)行期間變量或表達式可能的取值范圍以及在這些值上所允許的操

19、作運算。l 例如： 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實型、和復數(shù)型 ；在C語言中有：l數(shù)據(jù)類型：基本類型和構造類型l基本類型：整型、浮點型、字符型l構造類型：數(shù)組、結構、聯(lián)合、指針、枚舉型、自定義類型 l C語言中的整數(shù)類型，就給出了一個整型量的取值范圍(依賴于不同的機器或編譯系統(tǒng))，定義了對整型量可施加的加、減、乘、除和取模等算術運算。l 在高級程序設計語言中，按“值”的不同特性，可將數(shù)據(jù)類型分為兩類：一類是其值不可分解的稱為原子類型原子類型(或非結構類型)。例如C語言中的基本類型(整型、實型、字符型和枚舉類型)以及指針類型和空類型等簡單類型；另一類則是結構類型，結構類型，其值

20、可由若干個分量(或成分)按某種結構組成，它的分量可以是非結構型的，也可以是結構型的。l 例如，C語言中數(shù)組、結構等類型。通常數(shù)據(jù)類型可以看作是程序設計語言中已實現(xiàn)的數(shù)據(jù)結構。l 1.3 抽象數(shù)據(jù)類型l 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type,簡稱簡稱ADT)是20世紀70年代提出的一種新概念，它是抽象數(shù)據(jù)的組織和與之相關的操作。一個ADT可以看作是定義了相關操作運算的一個數(shù)學模型。例如，集合與集合的并、交、差運算就可以定義為一個抽象數(shù)據(jù)類型。l 抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立與具體實現(xiàn)。它的特點是將數(shù)據(jù)定義和數(shù)據(jù)操作封裝在一起，使得用戶程序只能通過在ADT

21、中定義的某種操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了信息的隱藏性。這種抽象數(shù)據(jù)類型類似于C+中的類定義。ADT的一般定義形式是：的一般定義形式是：ADT 數(shù)據(jù)對象：數(shù)據(jù)對象： 數(shù)據(jù)關系：數(shù)據(jù)關系： 基本操作：基本操作： ADT 其中數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述。其中數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述。 基本操作的定義是：基本操作的定義是：()初始條件：初始條件： 操作結果：操作結果： 初始條件：描述操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿初始條件：描述操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件足的條件;若不滿足，則操作失敗，返回相應的出錯若不滿足，則操作失敗，返回相應的出錯信息。信息。 操作結果：描述操作正常

22、完成之后，數(shù)據(jù)結構的操作結果：描述操作正常完成之后，數(shù)據(jù)結構的變化狀況和變化狀況和 應返回的結果。應返回的結果。 l 作為一個例子，看一個“圓”數(shù)據(jù)類型的描述。我們知道，要表示一個圓一般應包括圓心的位置和半徑的大小。如果只關心圓的面積，那么這個抽象數(shù)據(jù)類型中就只需要有表示半徑的數(shù)據(jù)。假設要設計一個圓(Circle)抽象數(shù)據(jù)類型，它包括計算面積(area)、周長（circumference）的操作，Circle的抽象數(shù)據(jù)類型描述如下：ADT Circle /圓的抽象數(shù)據(jù)類型描述 Data 非負實數(shù)表示圓的半徑 Operations Constructor 輸入的初值：非負實數(shù) 處理： 給半徑賦初

23、值 Area 輸入：無 處理：計算圓面積 輸出：圓的面積 Circumference 輸入：無 處理：計算圓周長 輸出：圓周長 ADT CircleC+ C+ 類和對象類和對象#include iostream.hclass Circleprivate: double x,y,r; public: void print() cout圓心圓心:(x,y)endl; cout半徑半徑:rendl; void set(double x1,double y1,double r1) x=x1; y=y1; r=r1;void main() Circle p; p.set(0,0,2); p.print(

24、); 引例引例: :圓類定義圓類定義類定義類定義數(shù)據(jù)成員數(shù)據(jù)成員成員函數(shù)成員函數(shù)定義類對象定義類對象對對象調用對對象調用成員函數(shù)成員函數(shù)CircleCircle類將圓的屬性類將圓的屬性（圓心坐標和半徑）（圓心坐標和半徑）和操作（和操作（printprint、setset）封裝在一起封裝在一起l 由于我們是以C語言為基礎來描述算法的，而C語言中沒有提供“類”這一數(shù)據(jù)類型，所以無法實現(xiàn)抽象數(shù)據(jù)類型，因此，我們將不采用ADT的形式來描述數(shù)據(jù)結構。但讀者只需要記住，ADT實際上等價于我們定義的數(shù)據(jù)的邏輯結構以及在邏輯結構上定義的抽象操作。l 1.4 算法和算法分析l算法：是對特定問題求解步驟的一種描述

25、,l 算法是操作指令的有限序列，其中每一條指令表示一個或多個操作。l 例如，我們要用計算機求解一個已知3個坐標點a(x1,y1)、b(x2,y2)、c(x3,y3)所構成的三角形的面積。首先要根據(jù)實際問題，找出求解三角形面積的相關計算公式(抽象出數(shù)學模型)，然后再逐步求解計算。比如要計算面積，就必須先求邊長，求邊長的公式為：l求三角形面積的公式為：l 在有了上述公式(模型)之后，就要給出求解問題的過程（又叫解題的方法或步驟），這就是所謂的算法。該問題的算法描述如下：l（1）輸入三角形的3個坐標點a、b和c；l（2）計算三條邊長及邊長和的一半；l（3）計算三角形的面積area;l（4）輸出三角形

26、的邊長和面積。l 然后再根據(jù)算法的描述，編寫相應的程序代碼上機調試運行直至得出正確結果。 l#include /包含輸入/輸出流l#include /包含數(shù)學函數(shù)的頭文件ldouble edge(double x1,double x2,double y1,double y2)l /求三角形的邊長l double len; l len=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)；/求邊長l return len;llvoid main( )l double x1,x2,x3,y1,y2,y3,s,area,ab,ac,bc；/說明變量l scanf(%lf %lf %

27、lf”,&x1,&x2,&x3);l scanf(%lf %lf %lf”,&y1,&y2,&y3); /輸入坐標值l ab=edge(x1,x2,y1,y2)； /求邊長l ac=edge(x1,x3,y1,y3)； l bc=edge(x2,x3,y2,y3)；l s=(ab+ac+bc)/2； /求邊長和的一半l area=sqrt(s*(s-ab)*(s-ac)*(s-bc)； /計算面積l printf(area=%lfn ”,area)； /輸出三角形面積ll#includelclass Pointl public :l void S

28、etPoint(float a,float b)x=a;y=b; /設置X、Y值l void Print() cout”(”x”,”y”)”endl; l void Move(float a,float b) x=x+a; y=y+b; /移動坐標點l private:l float x,y;l; lvoid main( )ll Point A，B，C;l A.SetPoint(3.0,4.0); B.SetPoint(6.0,8.0);l C.SetPoint(9.0,4.0); A.Print( ); /輸出A點坐標的X、Y值l B.Print( ); C.Print( ); B.Move

29、(2,-3); l C.Move(-3,5); /移動C點坐標的X-3,Y+5l B.Print( ); C.Print( ); /輸出C點坐標的X、Y值ll 從上述的實例可以看出，算法是對問題求解步驟的一種描述。通俗地說：一個算法就是一種解題的方法。算法必須滿足以下五個準則： l（1）有窮性 一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。l（2）確定性 算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。l（3）可行性 一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。l（4）輸入 一個算法有零個或多個輸入，這些

30、輸入取自于某個特定的對象集合。l（5）輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。l 因此，一個程序如果對任何輸入都不會陷入無限循環(huán)，則它就是一個算法。算法的含義與程序十分相似，但二者是有區(qū)別的，程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數(shù)學語言或約定的符號語言來描述。l 例如上述求解三角形面積的算法就是中文語言描述的。目前最常用的描述算法的語言有兩種，一種是用類PASCAL，另一種是類C，類似于C語言，而又不完全同C語言。類C語言借助于C語言的語法結構，輔之以自然語言的敘述，使得用它編寫的算法既具有良好的結構，又不拘泥于具體程序語言的某些

31、細節(jié)。因此，類C語言使得算法易讀易寫。l1.4.2 算法設計要求l評價一個好的算法有以下幾個標準:l (1) 正確性(Correctness ) 算法應滿足具體問題的需求。l (2)可讀性(Readability) 算法應該好讀。以有利于閱讀者對程序的理解。 (3)健狀性(Robustness) 算法應具有容錯處理。當輸入非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn)年莫名其妙的輸出結果。 (4) 效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關。l1.4.3 算法分析（效率的度量）l 求解一個問題可能有多種不同的算法，而算法的

32、好壞直接影響程序的執(zhí)行效率，且不同的算法之間的運行效率相差巨大。那么，又如何來評價算法的優(yōu)劣而從中選擇好的算法呢？顯然，算法的“正確性”是首先要考慮的。所謂一個算法的正確性，是指對于一切合法的輸入數(shù)據(jù)，該算法經(jīng)過有限時間的執(zhí)行都能得到正確的結果，此外，應主要考慮如下幾點：l（1） 執(zhí)行算法所耗費的時間，即時間復雜性；l （2）執(zhí)行算法所耗費的存儲空間，主要是輔助空間，即空間復雜性；l （3）算法應易于理解、易于編程，易于調試等，即可讀性和可操作性。 l 在以上幾點當中，最主要的還是時間復雜性。一個算法所耗費的時間，應是該算法中每條語句的執(zhí)行時間之和。每條語句的執(zhí)行次數(shù)又稱為頻度，頻度，所以每條

33、語句的執(zhí)行時間就是該語句的執(zhí)行次數(shù)（頻度頻度）與該語句執(zhí)行一次所需時間的乘積。l 由于計算機之間的性能千差萬別，不能以一個統(tǒng)一的標準來度量，因此，通常就將每條語句的執(zhí)行時間忽略，而以語句的執(zhí)行頻度作為衡量一個算法好壞的主要參數(shù)。 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)。 例，計算nn兩矩陣乘積的算法如下： （1）for(i=1，i=n;+i) （2） for(j=1;j=n;+j) （3） cij=0; （4） for(k=1;k=n;+k) （5） cij+=aik*bkj; l 其中，語句(1)的循環(huán)控制變量i要增加到n+1，測試i=n+1成立時,循環(huán)才會終止，因此

34、它的頻度為n+1，但它的循環(huán)體卻只能執(zhí)行n次；語句(2)作為(1)的循環(huán)內語句應執(zhí)行n次，但語句(2)本身要執(zhí)行n+1 次，所以語句(2)的頻度為n(n+1)，同理可得語句(3)、語句(4)和語句(5)的頻度分別為n2、n2(n+1)、n3。因此，該算法中所有語句的頻度之和（即運行算法耗費的時間）為：lT(n)=(n+1)+n(n+1)+ n2 + n2 (n+1)+n3l =2n3+3n2+2n+1l耗費時間T(n)是矩陣階數(shù)n的函數(shù)。 矩陣乘積算法的時間復雜度T(n)，當n足夠大時，T(n)與n n3 3之比是一個不等零的常數(shù)，則稱T(n)和n n3 3是同階的，或者說T(n)和n n3

35、3的數(shù)量級相同，可記為T(n)=O(n3)。這時,我們稱T(n)=O(n3)是矩陣乘積算法的漸進近時間復雜度。語句頻度：是指該語句重復執(zhí)行的次數(shù)l定義：如果存在兩個正常數(shù)c和n0，對于所有的nn0，有f(n) cg(n) l 記作 f(n)=O(g(n)稱為算法的漸近時間復雜度l如前例，T(n)=f(n)= 2n3+3n2+2n+1 l取n0=1，當n n0時，f(n) 2n3+3n2+2n+nl = 2n3+3n2+3n 2n3+3n2+3n2=2n3+6n2l 8n3, 此時的此時的c=8, g(n)=n3T(n)=O(n3)l例2、for(i=1;i=n;+i) l +x;s+=x;l

36、語句頻度為：2n其時間復雜度為：O(n)l例3、for(i=1;i=n;+i)lfor(j=1;j=n;+j)l +x;s+=x;l 語句頻度為：2n2l其時間復雜度為：O(n2)，即時間復雜度為平方階。l定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一個m次多項式，則A(n)=O(nm)l 一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。l 以下六種計算算法時間的多項式是最常用的。其關系為：l O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3) )l 指數(shù)時間的關系為：l O(2n)O(n!)O(nn)l 當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取