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

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

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

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

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

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

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

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

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

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

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

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

12、結(jié)點(diǎn)，其余結(jié)點(diǎn)都是有僅有一個(gè)直接前趨和一個(gè)直接后繼。因此，上述圖書目錄卡片表就是一個(gè)典型的線性結(jié)構(gòu)。l(2)非線性結(jié)構(gòu)l 非線性結(jié)構(gòu)的特征是：數(shù)據(jù)元素之間存在著一對(duì)多或多對(duì)多的關(guān)系，即一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和多個(gè)直接后繼。該結(jié)構(gòu)包括樹形結(jié)構(gòu)、圖形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)等。l 數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)常又細(xì)分為以下四類基本結(jié)構(gòu)：l 一、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。l 二、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。l 三、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。l 四、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其它關(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)是一個(gè)二元組：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是含兩個(gè)實(shí)數(shù)的集合C1，C2，分別表示復(fù)數(shù)的實(shí)部和虛部。R=P，P是定義在集合上的一種關(guān)系C1，C2。 例如，當(dāng)用三個(gè)三個(gè) 4 位的十進(jìn)制數(shù)位的十進(jìn)制數(shù)表示一個(gè)含 12 位數(shù)的十進(jìn)制數(shù)時(shí)，位數(shù)的十進(jìn)制數(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ù)組中六個(gè)元素a1, a2, a3, a4, a5, a6之間存在兩個(gè)關(guān)系:行的次序關(guān)系行的次序關(guān)系:row = ,col = , a1 a2 a3 a4 a5 a6列的次序關(guān)系列的次序關(guān)系: : 若在 6 個(gè)數(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ù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示（映象），亦稱為數(shù)據(jù)的物理結(jié)構(gòu)。它包括數(shù)據(jù)元素和關(guān)系的表示，是依賴于計(jì)算機(jī)語(yǔ)言的。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可以用以下四種基本的存儲(chǔ)方法實(shí)現(xiàn)：l(1) 順序存儲(chǔ)方法l 該方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上也相鄰的連續(xù)存儲(chǔ)單元里，由此得到的存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)。它通常是借助于程序設(shè)計(jì)語(yǔ)言的數(shù)組來(lái)描述的。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)，但非線性的數(shù)據(jù)結(jié)構(gòu)也可通過(guò)某種線性化的方法來(lái)實(shí)現(xiàn)順序存儲(chǔ)。 l(2) 鏈接存儲(chǔ)方法 l 該方法是用一組

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

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

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

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

20、是抽象數(shù)據(jù)的組織和與之相關(guān)的操作。一個(gè)ADT可以看作是定義了相關(guān)操作運(yùn)算的一個(gè)數(shù)學(xué)模型。例如，集合與集合的并、交、差運(yùn)算就可以定義為一個(gè)抽象數(shù)據(jù)類型。l 抽象數(shù)據(jù)類型可以看作是描述問(wèn)題的模型，它獨(dú)立與具體實(shí)現(xiàn)。它的特點(diǎn)是將數(shù)據(jù)定義和數(shù)據(jù)操作封裝在一起，使得用戶程序只能通過(guò)在ADT中定義的某種操作來(lái)訪問(wèn)其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息的隱藏性。這種抽象數(shù)據(jù)類型類似于C+中的類定義。ADT的一般定義形式是：的一般定義形式是：ADT 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： 基本操作：基本操作： ADT 其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述。其中數(shù)據(jù)對(duì)象和數(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)的出錯(cuò)若不滿足，則操作失敗，返回相應(yīng)的出錯(cuò)信息。信息。 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和變化狀況和 應(yīng)返回的結(jié)果。應(yīng)返回的結(jié)果。 l 作為一個(gè)例子，看一個(gè)“圓”數(shù)據(jù)類型的描述。我們知道，要表示一個(gè)圓一般應(yīng)包括圓心的位置和半徑的大小。如果只關(guān)心圓的面積，那么這個(gè)抽象數(shù)據(jù)類型中就只需要有表示半徑的數(shù)據(jù)。假設(shè)要設(shè)計(jì)一個(gè)圓(Circle)抽象

22、數(shù)據(jù)類型，它包括計(jì)算面積(area)、周長(zhǎng)（circumference）的操作，Circle的抽象數(shù)據(jù)類型描述如下：ADT Circle /圓的抽象數(shù)據(jù)類型描述 Data 非負(fù)實(shí)數(shù)表示圓的半徑 Operations Constructor 輸入的初值：非負(fù)實(shí)數(shù) 處理： 給半徑賦初值 Area 輸入：無(wú) 處理：計(jì)算圓面積 輸出：圓的面積 Circumference 輸入：無(wú) 處理：計(jì)算圓周長(zhǎng) 輸出：圓周長(zhǎng) ADT CircleC+ C+ 類和對(duì)象類和對(duì)象#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ù)定義類對(duì)象定義類對(duì)象對(duì)對(duì)象調(diào)用對(duì)對(duì)象調(diào)用成員函數(shù)成員函數(shù)CircleCircle類將圓的屬性類將圓的屬性（圓心坐標(biāo)和半徑）（圓心坐標(biāo)和半徑）和操作（和操作（printprint、setset）封裝在一起封裝在一起l 由于我們是以C語(yǔ)言為基礎(chǔ)

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

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

26、; l len=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)；/求邊長(zhǎng)l return len;llvoid main( )l double x1,x2,x3,y1,y2,y3,s,area,ab,ac,bc；/說(shuō)明變量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)； /求邊長(zhǎng)l ac=edge(x1,x3,y1,y3)； l bc=edge(x2,x3,y2,y3)；l s

27、=(ab+ac+bc)/2； /求邊長(zhǎng)和的一半l area=sqrt(s*(s-ab)*(s-ac)*(s-bc)； /計(jì)算面積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; /移動(dòng)坐標(biāo)點(diǎn)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點(diǎn)坐標(biāo)的X、Y值l B.Print( ); C.Print( ); B.Move(2,-3); l C.Move(-3,5); /移動(dòng)C點(diǎn)坐標(biāo)的X-3,Y+5l B.Print( ); C.Print( ); /輸出C點(diǎn)坐標(biāo)的X、Y值ll 從上述的實(shí)例可以看出，算法是對(duì)問(wèn)題求解步驟的一種描述。通俗地說(shuō)：一個(gè)算法就是一種解題的方法。算法必須滿足以下五個(gè)準(zhǔn)則： l（1）有窮性 一個(gè)算法必須總是在執(zhí)行有

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

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

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

32、 （2）執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性；l （3）算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。 l 在以上幾點(diǎn)當(dāng)中，最主要的還是時(shí)間復(fù)雜性。一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)是該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和。每條語(yǔ)句的執(zhí)行次數(shù)又稱為頻度，頻度，所以每條語(yǔ)句的執(zhí)行時(shí)間就是該語(yǔ)句的執(zhí)行次數(shù)（頻度頻度）與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。l 由于計(jì)算機(jī)之間的性能千差萬(wàn)別，不能以一個(gè)統(tǒng)一的標(biāo)準(zhǔn)來(lái)度量，因此，通常就將每條語(yǔ)句的執(zhí)行時(shí)間忽略，而以語(yǔ)句的執(zhí)行頻度作為衡量一個(gè)算法好壞的主要參數(shù)。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)。 例，計(jì)算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 其中，語(yǔ)句(1)的循環(huán)控制變量i要增加到n+1，測(cè)試i=n+1成立時(shí),循環(huán)才會(huì)終止，因此它的頻度為n+1，但它的循環(huán)體卻只能執(zhí)行n次；語(yǔ)句(2)作為(1)的循環(huán)內(nèi)語(yǔ)句應(yīng)執(zhí)行n次，但語(yǔ)句(2)本身要執(zhí)行n+1 次，所以語(yǔ)句(2)的頻度為n(n+1)，同理可得語(yǔ)句(3)、語(yǔ)句(4)和語(yǔ)句(5)的頻度分別為n2、n2(n+1)、n3。因此，該算法中所有語(yǔ)句的頻度之和（即運(yùn)行算法耗費(fèi)的時(shí)間）為：lT(n)=(n+

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

35、n2+2n+1 l取n0=1，當(dāng)n n0時(shí)，f(n) 2n3+3n2+2n+nl = 2n3+3n2+3n 2n3+3n2+3n2=2n3+6n2l 8n3, 此時(shí)的此時(shí)的c=8, g(n)=n3T(n)=O(n3)l例2、for(i=1;i=n;+i) l +x;s+=x;l 語(yǔ)句頻度為：2n其時(shí)間復(fù)雜度為：O(n)l例3、for(i=1;i=n;+i)lfor(j=1;j=n;+j)l +x;s+=x;l 語(yǔ)句頻度為：2n2l其時(shí)間復(fù)雜度為：O(n2)，即時(shí)間復(fù)雜度為平方階。l定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)l 一個(gè)算法

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

37、翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問(wèn)雞翁、雞母、雞雛各幾何？”l分析分析：設(shè)公雞數(shù)為a，母雞數(shù)為b，小雞為c，根據(jù)題意，可得如下的方程式： 根據(jù)以上得出的數(shù)學(xué)模型，如果使用通常的解析法很難求解，但使用窮舉法很容易實(shí)現(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í)行時(shí)間取決于第三重循環(huán)的循環(huán)體的執(zhí)行次數(shù)，外循環(huán)每執(zhí)行一次，內(nèi)循環(huán)就需要執(zhí)行101次，所以，整個(gè)算法需要執(zhí)行101101101約100多萬(wàn)次。對(duì)于計(jì)算機(jī)來(lái)說(shuō)，解決這樣的一個(gè)簡(jiǎn)單問(wèn)題，執(zhí)行的時(shí)間是不能容忍的。因此，這個(gè)算法不是一個(gè)好的算法。l 其實(shí)，對(duì)上述算法是完全可以改進(jìn)的，比如，公雞5元一只，百元錢全買公雞最多也只能夠買20只，同樣，全買母雞也只能買33只，而小雞只能是買公雞母雞剩余的錢來(lái)買。所以，上述算法可改進(jìn)成如下算法： 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 平均時(shí)間復(fù)雜度為:O(n2)l1.4.4算法的存儲(chǔ)空間需求l 空間復(fù)雜度空間復(fù)雜度(Space complexity) : 是是指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。時(shí)所需存儲(chǔ)空間大小的度量。 記作：記

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

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

42、撲克的點(diǎn)數(shù)l （2，3，4，J，Q，K，A） 從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a2；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨a n-1；其余的內(nèi)部結(jié)點(diǎn)ai(2in-1)都有且僅有一個(gè)直接前趨a i-1和一個(gè)直接后繼a i+1。 線性表是一種典型的線性結(jié)構(gòu)。l數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。l抽象數(shù)據(jù)類型的定義為：P19 算法2.1l例2-1 利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合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歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。l 此問(wèn)題的算法如下： 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 線性表的順序存儲(chǔ)結(jié)構(gòu)l2.2.1 順序表 把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。 假設(shè)線性表的每個(gè)元素需占用c個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC( a i+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(a i )之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+c 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： LOC(ai)=LOC(a1)+(i-1)*c l 由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表

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

47、入和刪除兩種運(yùn)算。 1、插入: 線性表的插入運(yùn)算是指在表的第i(1in+1個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表 (a1，a i-1，ai，an) 變成長(zhǎng)度為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)在分析算法的時(shí)間復(fù)雜度。l 這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為n。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是n-i+1。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。l當(dāng)i=n+1時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O（1）；l當(dāng)i=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，l其時(shí)間復(fù)雜度為O（n）。l

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

50、它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。 2、刪除 線性表的刪除運(yùn)算是指將表的第i(1in)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長(zhǎng)度為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ǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例： 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); 說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開始結(jié)點(diǎn)，將開始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，

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

54、 b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?，因此空表和非空表的處理也就統(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); 上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加

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

56、結(jié)點(diǎn)看做是第0 個(gè)結(jié)點(diǎn)，其算法如下：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é)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下： ListNode * locatenode(Lin

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

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è)鏈表的長(zhǎng)度為n，合法的插入位置是1in+1。注意當(dāng)i=1時(shí)，getnode找到的是頭結(jié)點(diǎn)，當(dāng) i=n+1時(shí)，getnode找到的是結(jié)點(diǎn)an。因此，用i-1做實(shí)參調(diào)用getnod

59、e時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作getnode上，故時(shí)間復(fù)雜度亦為O(n)。四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)a a i-1的指針域next中，所以我們必須首先找到a i-1的存儲(chǔ)位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過(guò)程為： 具體算法如下： 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è)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1in時(shí)是合法的。注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點(diǎn) （即pnext!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)存在。 顯然，此算法的時(shí)間復(fù)雜度也是O(n)。 從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。2.3.2 循環(huán)鏈表 循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)的或開始結(jié)