數(shù)據(jù)結(jié)構(gòu)教案_中科大

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

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

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

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

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

6、圖書目錄檢索的數(shù)學(xué)模型。計算機的主要操作是按某個特定要求（如書名、作者）對書目文檔進行查詢檢索。諸如此類的問題還有各種查號系統(tǒng)、倉庫管理系統(tǒng)、帳務(wù)處理等。這類問題中的處理對象之間都是一種最簡單的線性關(guān)系，它們所對應(yīng)的數(shù)學(xué)模型稱為線性的數(shù)據(jù)結(jié)構(gòu)。l【例1.3】圖的m著色問題。l 圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使地圖的每個區(qū)域著一種顏色，且相鄰區(qū)域的顏色不同。如果把一個區(qū)域收縮為一個頂點，將相鄰兩個區(qū)域用一條邊相連接，就可以把一個區(qū)域圖抽象為一個平面圖和一個區(qū)域鄰接關(guān)系圖，如圖1.1(a)、(b)所示。 (a) 抽象的平面圖 (b) 區(qū)域鄰接關(guān)系圖 圖1.1 圖的

7、著色問題示意圖l 19世紀(jì)50年代，英國學(xué)者提出了任何地圖都可以用4種顏色來著色的4著色猜想問題。過了100多年，這個問題才由美國學(xué)者在計算機上予以證明，這就是著名的4色定理。如在圖1.1中，顏色用數(shù)字表示，字母表示區(qū)域，則圖中表示了不同區(qū)域的不同著色情況。l 再例如，家族的血統(tǒng)關(guān)系、博奕樹問題（人一機下棋）、計算機的文件系統(tǒng)等都是一種樹形結(jié)構(gòu)；而城市之間的交通網(wǎng)絡(luò)、工程管理中的活動安排以及多叉路口交通燈管理等問題是圖形結(jié)構(gòu)的。它們都是一種非線性的數(shù)據(jù)結(jié)構(gòu)。l 通過以上幾例可以直接地認為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，而且確保經(jīng)過這些

8、運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。l 1.2 基本概念和術(shù)語l數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。例如，一個代數(shù)方程的求解程序中所使用的數(shù)據(jù)是整數(shù)和實數(shù)，而對一個文本編輯程序中使用的數(shù)據(jù)是字符串。隨著計算機的發(fā)展以及計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的含義也隨之拓展了。例如，當(dāng)今計算機可以處理的圖形、圖像、聲音等，它們也都屬于數(shù)據(jù)的范疇。 l數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。l 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。l 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。如

9、前例中的目錄卡片表中的一張卡片（表格中的一行）、樹中的一個節(jié)點、圖的一個頂點等都是數(shù)據(jù)元素，有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（也稱為字段、域、屬性）組成，數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。如圖書卡片信息中的登錄號、書名、作者等。 l數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。例如，大寫字母數(shù)據(jù)對象就是集合A,B,Z。l 數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間存在一種或多種特定關(guān)系(結(jié)構(gòu))的數(shù)據(jù)元素的集合。雖然至今沒有一個關(guān)于數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)定義，但它一般包括以下三個方面的內(nèi)容：l (1) 數(shù)據(jù)元素之間的邏輯(或抽象)關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)

10、邏輯結(jié)構(gòu)。l (2) 數(shù)據(jù)元素及其關(guān)系在計算機內(nèi)的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)(物理結(jié)構(gòu)物理結(jié)構(gòu))。 (3) 數(shù)據(jù)的運算運算，即對數(shù)據(jù)元素施加的操作(行為)。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合 一個特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系 這種結(jié)構(gòu)又分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)l 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)的，它與數(shù)據(jù)元素的存儲結(jié)構(gòu)無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。l 如上一節(jié)中表1.1所表示的圖書目錄卡片，表中數(shù)據(jù)元素之間的邏輯

11、關(guān)系就是一種相鄰關(guān)系：對表中任一個結(jié)點，與它相鄰且在它前面的結(jié)點稱為直直接前趨，接前趨，這種直接前驅(qū)最多只有一個；與表中任一結(jié)點相鄰且在其后面的結(jié)點稱為直接后繼，直接后繼，也最多只有一個。表中只有第一個結(jié)點沒有直接前趨，稱之為開始結(jié)點開始結(jié)點；也只有最后一個結(jié)點沒有直接后繼，稱之為終端結(jié)點終端結(jié)點。例如，表中的“操作系統(tǒng)”所在結(jié)點的直接前趨結(jié)點和直接后繼結(jié)點分別是“數(shù)據(jù)結(jié)構(gòu)”和“數(shù)據(jù)庫原理”所在的結(jié)點，這種結(jié)點之間的關(guān)系就構(gòu)成了圖書目錄卡片表的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)又可分為兩大類：l(1)線性結(jié)構(gòu) 線性結(jié)構(gòu)的特征是：數(shù)據(jù)元素(結(jié)點)之間存在著一對一的關(guān)系，且結(jié)構(gòu)中有僅有一個開始結(jié)點和一個終端

12、結(jié)點，其余結(jié)點都是有僅有一個直接前趨和一個直接后繼。因此，上述圖書目錄卡片表就是一個典型的線性結(jié)構(gòu)。l(2)非線性結(jié)構(gòu)l 非線性結(jié)構(gòu)的特征是：數(shù)據(jù)元素之間存在著一對多或多對多的關(guān)系，即一個結(jié)點可能有多個直接前趨和多個直接后繼。該結(jié)構(gòu)包括樹形結(jié)構(gòu)、圖形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)等。l 數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)常又細分為以下四類基本結(jié)構(gòu)：l 一、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。l 二、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。l 三、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。l 四、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。l 后三種都屬于非線性結(jié)構(gòu)從關(guān)系關(guān)系或

13、結(jié)構(gòu)結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類四類: :l 數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：l Data-Structure=(D，S)l 其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。l 例 復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：l Complex=(C，R)l 其中：C是含兩個實數(shù)的集合C1，C2，分別表示復(fù)數(shù)的實部和虛部。R=P，P是定義在集合上的一種關(guān)系C1，C2。 例如，當(dāng)用三個三個 4 位的十進制數(shù)位的十進制數(shù)表示一個含 12 位數(shù)的十進制數(shù)時，位數(shù)的十進制數(shù)時，3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3

14、之間存在著“次序次序”關(guān)系關(guān)系 a1, a2 、 a2, a3 3214，6587，9345 6587，3214，9345a1 a2 a3a2 a1 a3又例，在 2 行 3 列的二維數(shù)組中六個元素a1, a2, a3, a4, a5, a6之間存在兩個關(guān)系:行的次序關(guān)系行的次序關(guān)系:row = ,col = , a1 a2 a3 a4 a5 a6列的次序關(guān)系列的次序關(guān)系: : 若在 6 個數(shù)據(jù)元素a1, a2, a3, a4, a5, a6 之間存在如下的次序關(guān)系次序關(guān)系:| i=1, 2, 3, 4, 5 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合輯關(guān)

15、系的數(shù)據(jù)元素的集合?？梢?，不同的“關(guān)系關(guān)系”構(gòu)成不同的“結(jié)構(gòu)結(jié)構(gòu)” 則構(gòu)成一維數(shù)組一維數(shù)組的定義。 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機中的存儲表示（映象），亦稱為數(shù)據(jù)的物理結(jié)構(gòu)。它包括數(shù)據(jù)元素和關(guān)系的表示，是依賴于計算機語言的。數(shù)據(jù)的存儲結(jié)構(gòu)可以用以下四種基本的存儲方法實現(xiàn)：l(1) 順序存儲方法l 該方法是把邏輯上相鄰的結(jié)點存儲在物理位置上也相鄰的連續(xù)存儲單元里，由此得到的存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)。它通常是借助于程序設(shè)計語言的數(shù)組來描述的。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)，但非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法來實現(xiàn)順序存儲。 l(2) 鏈接存儲方法 l 該方法是用一組

16、不一定連續(xù)的存儲單元存儲邏輯上相鄰的元素，元素間的邏輯關(guān)系是由附加的指針域表示的。由此得到的存儲結(jié)構(gòu)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)。它通常是借助于程序設(shè)計語言中的指針來描述的l(3) 索引存儲方法l 該方法通常是在存儲元素信息的同時，還建立附加的索引表。表中的索引項一般形式是：(關(guān)鍵字，地址)，關(guān)鍵字是能唯一標(biāo)識一個元素的一個數(shù)據(jù)項或多個數(shù)據(jù)項的組合。l(4) 散列存儲方法l 該方法的基本思想是根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。 l 無論怎樣定義數(shù)據(jù)結(jié)構(gòu)，都應(yīng)該將數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面看成一個整體。因此，存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面。l 同一種邏輯結(jié)

17、構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，要視具體的應(yīng)用系統(tǒng)要求而定，而主要考慮的還是運算方便及算法的時間和空間上的要求。l 數(shù)據(jù)的運算數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每種邏輯結(jié)構(gòu)都有一個運算的集合，最常用的運算有：檢索、插入、刪除、更新、排序等。數(shù)據(jù)運算是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面，在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運算集合及其運算性質(zhì)的不同，可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。例如，若對線性表的插入、刪除運算限制在表的一端進行，則該線性表稱為棧；若對線性表的插入運算限制在表的一端，而刪除運算限制在表的另一端，則該線性表稱為隊列。 l 數(shù)據(jù)

18、類型：(data type)是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。所謂數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。在使用高級程序設(shè)計語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的數(shù)據(jù)類型。類型規(guī)定了在程序執(zhí)行期間變量或表達式可能的取值范圍以及在這些值上所允許的操作運算。l 例如： 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實型、和復(fù)數(shù)型 ；在C語言中有：l數(shù)據(jù)類型：基本類型和構(gòu)造類型l基本類型：整型、浮點型、字符型l構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義類型 l C語言中的整數(shù)類型，就給出了一個整型量的取值范圍(依賴于不同的機器或編譯系統(tǒng))，定義了對整型量可施加

19、的加、減、乘、除和取模等算術(shù)運算。l 在高級程序設(shè)計語言中，按“值”的不同特性，可將數(shù)據(jù)類型分為兩類：一類是其值不可分解的稱為原子類型原子類型(或非結(jié)構(gòu)類型)。例如C語言中的基本類型(整型、實型、字符型和枚舉類型)以及指針類型和空類型等簡單類型；另一類則是結(jié)構(gòu)類型，結(jié)構(gòu)類型，其值可由若干個分量(或成分)按某種結(jié)構(gòu)組成，它的分量可以是非結(jié)構(gòu)型的，也可以是結(jié)構(gòu)型的。l 例如，C語言中數(shù)組、結(jié)構(gòu)等類型。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。l 1.3 抽象數(shù)據(jù)類型l 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type,簡稱簡稱ADT)是20世紀(jì)70年代提出的一種新概念，它

20、是抽象數(shù)據(jù)的組織和與之相關(guān)的操作。一個ADT可以看作是定義了相關(guān)操作運算的一個數(shù)學(xué)模型。例如，集合與集合的并、交、差運算就可以定義為一個抽象數(shù)據(jù)類型。l 抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立與具體實現(xiàn)。它的特點是將數(shù)據(jù)定義和數(shù)據(jù)操作封裝在一起，使得用戶程序只能通過在ADT中定義的某種操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了信息的隱藏性。這種抽象數(shù)據(jù)類型類似于C+中的類定義。ADT的一般定義形式是：的一般定義形式是：ADT 數(shù)據(jù)對象：數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： 基本操作：基本操作： ADT 其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述。其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述。 基本操作的定義是：

21、基本操作的定義是：()初始條件：初始條件： 操作結(jié)果：操作結(jié)果： 初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件足的條件;若不滿足，則操作失敗，返回相應(yīng)的出錯若不滿足，則操作失敗，返回相應(yīng)的出錯信息。信息。 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和變化狀況和 應(yīng)返回的結(jié)果。應(yīng)返回的結(jié)果。 l 作為一個例子，看一個“圓”數(shù)據(jù)類型的描述。我們知道，要表示一個圓一般應(yīng)包括圓心的位置和半徑的大小。如果只關(guān)心圓的面積，那么這個抽象數(shù)據(jù)類型中就只需要有表示半徑的數(shù)據(jù)。假設(shè)要設(shè)計一個圓(Circle)抽象

22、數(shù)據(jù)類型，它包括計算面積(area)、周長（circumference）的操作，Circle的抽象數(shù)據(jù)類型描述如下：ADT Circle /圓的抽象數(shù)據(jù)類型描述 Data 非負實數(shù)表示圓的半徑 Operations Constructor 輸入的初值：非負實數(shù) 處理： 給半徑賦初值 Area 輸入：無 處理：計算圓面積 輸出：圓的面積 Circumference 輸入：無 處理：計算圓周長 輸出：圓周長 ADT CircleC+ C+ 類和對象類和對象#include iostream.hclass Circleprivate: double x,y,r; public: void print

23、() 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(); 引例引例: :圓類定義圓類定義類定義類定義數(shù)據(jù)成員數(shù)據(jù)成員成員函數(shù)成員函數(shù)定義類對象定義類對象對對象調(diào)用對對象調(diào)用成員函數(shù)成員函數(shù)CircleCircle類將圓的屬性類將圓的屬性（圓心坐標(biāo)和半徑）（圓心坐標(biāo)和半徑）和操作（和操作（printprint、setset）封裝在一起封裝在一起l 由于我們是以C語言為基礎(chǔ)

24、來描述算法的，而C語言中沒有提供“類”這一數(shù)據(jù)類型，所以無法實現(xiàn)抽象數(shù)據(jù)類型，因此，我們將不采用ADT的形式來描述數(shù)據(jù)結(jié)構(gòu)。但讀者只需要記住，ADT實際上等價于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作。l 1.4 算法和算法分析l算法：是對特定問題求解步驟的一種描述,l 算法是操作指令的有限序列，其中每一條指令表示一個或多個操作。l 例如，我們要用計算機求解一個已知3個坐標(biāo)點a(x1,y1)、b(x2,y2)、c(x3,y3)所構(gòu)成的三角形的面積。首先要根據(jù)實際問題，找出求解三角形面積的相關(guān)計算公式(抽象出數(shù)學(xué)模型)，然后再逐步求解計算。比如要計算面積，就必須先求邊長，求邊長的公

25、式為：l求三角形面積的公式為：l 在有了上述公式(模型)之后，就要給出求解問題的過程（又叫解題的方法或步驟），這就是所謂的算法。該問題的算法描述如下：l（1）輸入三角形的3個坐標(biāo)點a、b和c；l（2）計算三條邊長及邊長和的一半；l（3）計算三角形的面積area;l（4）輸出三角形的邊長和面積。l 然后再根據(jù)算法的描述，編寫相應(yīng)的程序代碼上機調(diào)試運行直至得出正確結(jié)果。 l#include /包含輸入/輸出流l#include /包含數(shù)學(xué)函數(shù)的頭文件ldouble edge(double x1,double x2,double y1,double y2)l /求三角形的邊長l double len

26、; 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 %lf”,&x1,&x2,&x3);l scanf(%lf %lf %lf”,&y1,&y2,&y3); /輸入坐標(biāo)值l ab=edge(x1,x2,y1,y2)； /求邊長l ac=edge(x1,x3,y1,y3)； l bc=edge(x2,x3,y2,y3)；l s

27、=(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 SetPoint(float a,float b)x=a;y=b; /設(shè)置X、Y值l void Print() cout”(”x”,”y”)”endl; l void Move(float a,float b) x=x+a; y=y+b; /移動坐標(biāo)點l private:l float x,y;l; lvoid main

28、( )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點坐標(biāo)的X、Y值l B.Print( ); C.Print( ); B.Move(2,-3); l C.Move(-3,5); /移動C點坐標(biāo)的X-3,Y+5l B.Print( ); C.Print( ); /輸出C點坐標(biāo)的X、Y值ll 從上述的實例可以看出，算法是對問題求解步驟的一種描述。通俗地說：一個算法就是一種解題的方法。算法必須滿足以下五個準(zhǔn)則： l（1）有窮性 一個算法必須總是在執(zhí)行有

29、窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。l（2）確定性 算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。l（3）可行性 一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。l（4）輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。l（5）輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。l 因此，一個程序如果對任何輸入都不會陷入無限循環(huán)，則它就是一個算法。算法的含義與程序十分相似，但二者是有區(qū)別的，程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數(shù)學(xué)語言或約定的符號語言來描

30、述。l 例如上述求解三角形面積的算法就是中文語言描述的。目前最常用的描述算法的語言有兩種，一種是用類PASCAL，另一種是類C，類似于C語言，而又不完全同C語言。類C語言借助于C語言的語法結(jié)構(gòu)，輔之以自然語言的敘述，使得用它編寫的算法既具有良好的結(jié)構(gòu)，又不拘泥于具體程序語言的某些細節(jié)。因此，類C語言使得算法易讀易寫。l1.4.2 算法設(shè)計要求l評價一個好的算法有以下幾個標(biāo)準(zhǔn):l (1) 正確性(Correctness ) 算法應(yīng)滿足具體問題的需求。l (2)可讀性(Readability) 算法應(yīng)該好讀。以有利于閱讀者對程序的理解。 (3)健狀性(Robustness) 算法應(yīng)具有容錯處理。當(dāng)

31、輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。 (4) 效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。l1.4.3 算法分析（效率的度量）l 求解一個問題可能有多種不同的算法，而算法的好壞直接影響程序的執(zhí)行效率，且不同的算法之間的運行效率相差巨大。那么，又如何來評價算法的優(yōu)劣而從中選擇好的算法呢？顯然，算法的“正確性”是首先要考慮的。所謂一個算法的正確性，是指對于一切合法的輸入數(shù)據(jù)，該算法經(jīng)過有限時間的執(zhí)行都能得到正確的結(jié)果，此外，應(yīng)主要考慮如下幾點：l（1） 執(zhí)行算法所耗費的時間，即時間復(fù)雜性；l

32、 （2）執(zhí)行算法所耗費的存儲空間，主要是輔助空間，即空間復(fù)雜性；l （3）算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。 l 在以上幾點當(dāng)中，最主要的還是時間復(fù)雜性。一個算法所耗費的時間，應(yīng)是該算法中每條語句的執(zhí)行時間之和。每條語句的執(zhí)行次數(shù)又稱為頻度，頻度，所以每條語句的執(zhí)行時間就是該語句的執(zhí)行次數(shù)（頻度頻度）與該語句執(zhí)行一次所需時間的乘積。l 由于計算機之間的性能千差萬別，不能以一個統(tǒng)一的標(biāo)準(zhǔn)來度量，因此，通常就將每條語句的執(zhí)行時間忽略，而以語句的執(zhí)行頻度作為衡量一個算法好壞的主要參數(shù)。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)。 例，計算nn兩矩陣乘積的

33、算法如下： （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)才會終止，因此它的頻度為n+1，但它的循環(huán)體卻只能執(zhí)行n次；語句(2)作為(1)的循環(huán)內(nèi)語句應(yīng)執(zhí)行n次，但語句(2)本身要執(zhí)行n+1 次，所以語句(2)的頻度為n(n+1)，同理可得語句(3)、語句(4)和語句(5)的頻度分別為n2、n2(n+1)、n3。因此，該算法中所有語句的頻度之和（即運行算法耗費的時間）為：lT(n)=(n+

34、1)+n(n+1)+ n2 + n2 (n+1)+n3l =2n3+3n2+2n+1l耗費時間T(n)是矩陣階數(shù)n的函數(shù)。 矩陣乘積算法的時間復(fù)雜度T(n)，當(dāng)n足夠大時，T(n)與n n3 3之比是一個不等零的常數(shù)，則稱T(n)和n n3 3是同階的，或者說T(n)和n n3 3的數(shù)量級相同，可記為T(n)=O(n3)。這時,我們稱T(n)=O(n3)是矩陣乘積算法的漸進近時間復(fù)雜度。語句頻度：是指該語句重復(fù)執(zhí)行的次數(shù)l定義：如果存在兩個正常數(shù)c和n0，對于所有的nn0，有f(n) cg(n) l 記作 f(n)=O(g(n)稱為算法的漸近時間復(fù)雜度l如前例，T(n)=f(n)= 2n3+3

35、n2+2n+1 l取n0=1，當(dāng)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 語句頻度為：2n其時間復(fù)雜度為：O(n)l例3、for(i=1;i=n;+i)lfor(j=1;j=n;+j)l +x;s+=x;l 語句頻度為：2n2l其時間復(fù)雜度為：O(n2)，即時間復(fù)雜度為平方階。l定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一個m次多項式，則A(n)=O(nm)l 一個算法

36、時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。l 以下六種計算算法時間的多項式是最常用的。其關(guān)系為：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ù)時間的關(guān)系為：l O(2n)O(n!)O(nn)l 當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。 【例5】百錢買百雞問題。l公元5世紀(jì)末，我國古代數(shù)學(xué)家張丘建在他撰寫的算經(jīng)中提出了這樣一個問題：“雞

37、翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？”l分析分析：設(shè)公雞數(shù)為a，母雞數(shù)為b，小雞為c，根據(jù)題意，可得如下的方程式： 根據(jù)以上得出的數(shù)學(xué)模型，如果使用通常的解析法很難求解，但使用窮舉法很容易實現(xiàn) 。lint chicken_question(int g, int m, int s)l int a,b,c,k=0;l for(a=0;a=100;a+)l for(b=0;b=100;b+)l for(c=0;c=100;c+)l if(a+b+c=100) & (5*a+3*b+c/3=100) & (c%3=0) l gk=a;mk

38、=b;sk=c; l k=k+1;l l return k;l /窮舉法l 上述算法是三重循環(huán)，主要執(zhí)行時間取決于第三重循環(huán)的循環(huán)體的執(zhí)行次數(shù)，外循環(huán)每執(zhí)行一次，內(nèi)循環(huán)就需要執(zhí)行101次，所以，整個算法需要執(zhí)行101101101約100多萬次。對于計算機來說，解決這樣的一個簡單問題，執(zhí)行的時間是不能容忍的。因此，這個算法不是一個好的算法。l 其實，對上述算法是完全可以改進的，比如，公雞5元一只，百元錢全買公雞最多也只能夠買20只，同樣，全買母雞也只能買33只，而小雞只能是買公雞母雞剩余的錢來買。所以，上述算法可改進成如下算法： lint chicken_question(int g,int m

39、,int s)l int a,b,c,k=0;l for(a=0;a=20;a+)l for(b=0;b1 & change;-i)l l change=false;l for(j=0;jaj+1) l aj aj+1;l change=TURE;l l l/ 最好情況：0次 l最壞情況：1+2+3+n-1l =n(n-1)/2l 平均時間復(fù)雜度為:O(n2)l1.4.4算法的存儲空間需求l 空間復(fù)雜度空間復(fù)雜度(Space complexity) : 是是指算法編寫成程序后，在計算機中運行指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。時所需存儲空間大小的度量。 記作：記

40、作： S(n)=O(f(n) l其中：其中： n為問題的規(guī)模為問題的規(guī)模(或大小或大小)l該存儲空間一般包括三個方面：該存儲空間一般包括三個方面： 指令常數(shù)、變量所占用的存儲空間指令常數(shù)、變量所占用的存儲空間; 輸入數(shù)據(jù)所占用的存儲空間輸入數(shù)據(jù)所占用的存儲空間; 輔助輔助(存儲存儲)空間?？臻g。l 一般地，算法的一般地，算法的空間復(fù)雜度空間復(fù)雜度指的是輔助指的是輔助空間?？臻g。 一維數(shù)組一維數(shù)組an： 空間復(fù)雜度空間復(fù)雜度 O(n) 二維數(shù)組二維數(shù)組anm： 空間復(fù)雜度空間復(fù)雜度 O(n*m)l2.1 線性表的類型定義l2.2 線性表的順序表示和實現(xiàn)l2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)l 2.3.

41、1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加l2.1 線性表的邏輯結(jié)構(gòu)l線性表線性表(Linear List) ：由n(n0)個數(shù)據(jù)元素(結(jié)點)a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n0)記作：l (a1，a2，an) l這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。l例1、26個英文字母組成的字母表l （A，B，C、Z）l例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。l （6，17，28，50，92，188）l例4、一副

42、撲克的點數(shù)l （2，3，4，J，Q，K，A） 從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨a n-1；其余的內(nèi)部結(jié)點ai(2in-1)都有且僅有一個直接前趨a i-1和一個直接后繼a i+1。 線性表是一種典型的線性結(jié)構(gòu)。l數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。l抽象數(shù)據(jù)類型的定義為：P19 算法2.1l例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。 void union(List &am

43、p;La，List Lb) La_len=listlength(La); Lb_len=listlength(Lb); for(i=1;i=Lb-len;i+) getelem(Lb，i，e); if(!locateelem(La，e，equal) listinsert(La，+La_len，e)； l l 算法2.2l例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。l 此問題的算法如下： void mergelist(List la，List lb，List &lc) initlist

44、(lc); i=j=1;k=0; la_len=listlength(la); lb_len=listlength(lb); while(i=la_len)&(j=lb_len)l getelem(la，i，ai);getelem(lb，j，bj);l if(ai=bj)listinsert(lc，+k，ai);+i; elselistinsert(lc，+k，bj);+j; l while(i=la_len) getelem(la，i+，ai); listinsert(lc， +k，ai); while(j=lb_len) getelem(lb，j+，bj); listinsert(

45、lc，+k，bi); l 2.2 線性表的順序存儲結(jié)構(gòu)l2.2.1 順序表 把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 假設(shè)線性表的每個元素需占用c個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a i )之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+c 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(ai)=LOC(a1)+(i-1)*c l 由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表

46、。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。l # define ListSize 100l typedef int DataType;l typedef structl DataType dataListSize;l int length;l Sqlist;l2.2.2 順序表上實現(xiàn)的基本操作 在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.datai-1。 以下主要討論線性表的插

47、入和刪除兩種運算。 1、插入: 線性表的插入運算是指在表的第i(1in+1個位置上，插入一個新結(jié)點x，使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，an) 算法2.3lvoid InsertList(Sqlist &L，DataType x，int i)l l int j;l if(iL.length+1) l printf(“Position error”);l return ERROR; l l if(L.length=ListSize)l printf(“overflow”);l exit(overflow);l l

48、 for(j=L.length-1;j=i-1;j-)l L.dataj+1=L.dataj;l L.datai-1=x;l L.length+;l l 現(xiàn)在分析算法的時間復(fù)雜度。l 這里的問題規(guī)模是表的長度，設(shè)它的值為n。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是n-i+1。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。l當(dāng)i=n+1時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復(fù)雜度O（1）；l當(dāng)i=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，l其時間復(fù)雜度為O（n）。l

49、由于插入可能在表中任何位置上進行，因此需分析算法的平均復(fù)雜度 在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故 Eis(n)= pi(n-i+1) 不失一般性，假設(shè)在表中任何位置(1in+1)上插入結(jié)點的機會是均等的，則 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情況下， Eis(n)= (n-i+1)/(n+1)=n/2 也就是說，在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長 n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，

50、它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。 2、刪除 線性表的刪除運算是指將表的第i(1in)結(jié)點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1，an) void deleteList(Sqlist &L，int i) int j; if(iL.length) printf(“Position error”); return ERROR ; for(j=i;jdata=ch; pnext=head; head=p; ch=getchar( ); return (head); ListLink

51、 createlist(int n) int data; LinkList head; ListNode *p; head=NULL; for(i=n;i0;-i) p=(ListNode*)malloc(sizeof(ListNode); scanf(%d，&pdata); pnext=head; head=p; return(head); 2、尾插法建表 頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例： LinkList c

52、reater( ) char ch; LinkList head; ListNode *p，*r ; head=NULL; r=NULL; while(ch=getchar( )!= n) p=(ListNode *)malloc(sizeof(ListNode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，

53、原因是開始結(jié)點的位置是存放在頭指針（指針變量）中，而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。 如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，那么會帶來以下兩個優(yōu)點： a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進行特殊處理；

54、 b、無論鏈表是否為空，其頭指針是指向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。其算法如下： LinkList createlistr1( ) char ch; LinkList head=(LinkList)malloc(sizeof(ListNode); ListNode *p，*r=head; while(ch=getchar( )!= n p=(ListNode*)malloc(sizeof(ListNode); pdata=ch; rnext=p; r=p; rnext=NULL; return(head); 上述算法里動態(tài)申請新結(jié)點空間時未加

55、錯誤處理，可作下列處理： p=(ListNode*)malloc(sizeof(ListNode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的時間復(fù)雜度均為O(n)。二、查找運算 1、按序號查找 在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。 設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1in時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭

56、結(jié)點看做是第0 個結(jié)點，其算法如下：ListNode * getnode(LinkList head ， int i) int j; ListNode * p; p=head; j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 2、按值查找 按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下： ListNode * locatenode(Lin

57、kList head，int key) LlistNode * p=headnext; while( p & pdata!=key) p=pnext; return p; 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。三、插入運算 插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點*q，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：具體算法如

58、下： LinkList insertnode(LinkList head，DateType x，int i) LlistNode * p，*q; p=GetNode(head，i-1); if(p=NULL) error(position error); q=(ListNode *)malloc(sizeof(ListNode); qdata=x; qnext=pnext; pnext=q; return head; 設(shè)鏈表的長度為n，合法的插入位置是1in+1。注意當(dāng)i=1時，getnode找到的是頭結(jié)點，當(dāng) i=n+1時，getnode找到的是結(jié)點an。因此，用i-1做實參調(diào)用getnod

59、e時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復(fù)雜度亦為O(n)。四、刪除運算 刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點a a i-1的指針域next中，所以我們必須首先找到a i-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。此過程為： 具體算法如下： void deletelist(LinkList head， int i) LlistNode * p， *r; p=GetNode(head，i-1); if(p= =NULL | pn

60、ext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1in時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點 （即pnext!=NULL）時，才能確定被刪結(jié)點存在。 顯然，此算法的時間復(fù)雜度也是O(n)。 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。2.3.2 循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)