配套課件-數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述(第三版)

第1章概論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2數(shù)據(jù)抽象和抽象數(shù)據(jù)類型1.3描述數(shù)據(jù)結(jié)構(gòu)1.4算法和算法分析習(xí)題11.1什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域廣泛使用的術(shù)語(yǔ)，然而，究竟什么是數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)界至今沒有標(biāo)準(zhǔn)的定義。計(jì)算機(jī)由硬件和軟件組成。硬件是軀體，軟件是靈魂。硬件通過(guò)軟件發(fā)揮效用。軟件的核心是程序。學(xué)習(xí)程序設(shè)計(jì)需要掌握一門程序設(shè)計(jì)語(yǔ)言，它是學(xué)習(xí)計(jì)算機(jī)后續(xù)課程所必需的技能。但程序設(shè)計(jì)不等于編碼，為了充分利用計(jì)算機(jī)資源，開發(fā)高效的程序，計(jì)算機(jī)技術(shù)人員還必須掌握計(jì)算機(jī)學(xué)科多方面的知識(shí)，如數(shù)據(jù)的組織、算法的設(shè)計(jì)和分析、軟件工程技術(shù)等。

現(xiàn)實(shí)世界各領(lǐng)域中的大量信息都必須轉(zhuǎn)換成數(shù)據(jù)才能在計(jì)算機(jī)中存儲(chǔ)、處理。數(shù)據(jù)是信息的載體。應(yīng)用程序可以處理各種各樣的數(shù)據(jù)。籠統(tǒng)地說(shuō)，所謂數(shù)據(jù)(data)，就是計(jì)算機(jī)加工處理的對(duì)象。數(shù)據(jù)一般分為兩類：數(shù)值數(shù)據(jù)(numericaldata)和非數(shù)值數(shù)據(jù)(non-numericaldata)。數(shù)值數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)，主要用于工程計(jì)算、科學(xué)計(jì)算、商務(wù)處理等。非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語(yǔ)音、表格等。這類數(shù)據(jù)的特點(diǎn)是量大，而且往往有著復(fù)雜的內(nèi)在聯(lián)系。如果單純依靠改進(jìn)程序設(shè)計(jì)技巧，已無(wú)法編制出高效可靠的程序，而必須對(duì)數(shù)據(jù)本身的結(jié)構(gòu)加以研究。數(shù)據(jù)的組織和表示方法直接影響使用計(jì)算機(jī)求解問(wèn)題的效率。算法設(shè)計(jì)通常建立在所處理數(shù)據(jù)的一定組織形式之上。在許多應(yīng)用中，對(duì)于相同數(shù)據(jù)的同樣的處理要求，如果選擇不同的數(shù)據(jù)結(jié)構(gòu)，會(huì)有不同的處理效率，即運(yùn)算時(shí)間和存儲(chǔ)空間都會(huì)不同。數(shù)據(jù)結(jié)構(gòu)主要是為研究和解決如何使用計(jì)算機(jī)處理這些非數(shù)值問(wèn)題而產(chǎn)生的理論、技術(shù)和方法。對(duì)計(jì)算機(jī)學(xué)科來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)與算法的概念是至關(guān)重要的，它們是計(jì)算機(jī)學(xué)科的基礎(chǔ)之一，更是軟件技術(shù)的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)與算法之間有著本質(zhì)的聯(lián)系。當(dāng)談?wù)撘环N算法時(shí)，自然要涉及算法所處理的數(shù)據(jù)問(wèn)題；而討論數(shù)據(jù)的組織或結(jié)構(gòu)，離開了對(duì)處理此類數(shù)據(jù)的運(yùn)算及其算法的研究也是無(wú)意義的。因此有人概括出一個(gè)公式，即程序?=?算法?+?數(shù)據(jù)結(jié)構(gòu)ACM和IEEE-CS的計(jì)算學(xué)科教學(xué)計(jì)劃1991將計(jì)算學(xué)科劃分為9個(gè)主領(lǐng)域，“算法與數(shù)據(jù)結(jié)構(gòu)”是其中之一。計(jì)算學(xué)科教學(xué)計(jì)劃2001調(diào)整為14個(gè)主領(lǐng)域，數(shù)據(jù)結(jié)構(gòu)和算法的基本內(nèi)容主要涵蓋在“程序設(shè)計(jì)基礎(chǔ)”和“算法與復(fù)雜性”兩個(gè)領(lǐng)域中。如前所述，計(jì)算機(jī)處理的對(duì)象稱為數(shù)據(jù)。一個(gè)數(shù)據(jù)可以由若干成分?jǐn)?shù)據(jù)構(gòu)成，并具有某種結(jié)構(gòu)。在這里，我們稱組成數(shù)據(jù)的成分?jǐn)?shù)據(jù)為數(shù)據(jù)元素(dataelement)。數(shù)據(jù)元素可以是簡(jiǎn)單類型的，如整數(shù)、實(shí)數(shù)、字符等，也可以是結(jié)構(gòu)類型的，如記錄。如果把每個(gè)學(xué)生的記錄看做一個(gè)數(shù)據(jù)元素，那么該數(shù)據(jù)元素包括學(xué)號(hào)、姓名、性別等數(shù)據(jù)項(xiàng)(dataitem)。一個(gè)班學(xué)生的記錄組成了表1－1所示的學(xué)生情況表。表1－1學(xué)生情況表從概念上講，一個(gè)數(shù)據(jù)結(jié)構(gòu)(datastructure)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的。對(duì)數(shù)據(jù)元素間的邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)(logicalstructure)。數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storagestructure)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示。此外，討論一個(gè)數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算(operation)才有意義。表是一個(gè)數(shù)據(jù)結(jié)構(gòu)。1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系的不同特征，可將其分為四類基本的邏輯結(jié)構(gòu)。圖1－1給出了它們的示意圖。圖中用小圓圈表示數(shù)據(jù)元素，用帶箭頭的線表示元素間的次序關(guān)系。兩個(gè)不同元素的連線稱為邊，邊的起點(diǎn)稱為前驅(qū)(predecessor)元素，終點(diǎn)稱為后繼(successor)元素。這四種基本邏輯結(jié)構(gòu)是：

(1)集合結(jié)構(gòu)(set)。集合結(jié)構(gòu)中，元素間的次序是隨意的。元素之間除了“屬于同一個(gè)集合”的聯(lián)系之外沒有其他關(guān)系。由于集合結(jié)構(gòu)的元素間沒有固有的關(guān)系，因此往往需要借助其他結(jié)構(gòu)才能在計(jì)算機(jī)中實(shí)際表示此結(jié)構(gòu)。

(2)線性結(jié)構(gòu)(linear)。線性結(jié)構(gòu)是數(shù)據(jù)元素的有序序列，其中，第一個(gè)元素沒有前驅(qū)只有后繼，最后一個(gè)元素只有前驅(qū)沒有后繼，其余元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。數(shù)據(jù)元素之間形成一對(duì)一的關(guān)系。

(3)樹形結(jié)構(gòu)(tree)。樹中，除一個(gè)稱為根的特殊元素沒有前驅(qū)只有后繼外，其余元素都有且僅有一個(gè)前驅(qū)，但后繼的數(shù)目不限。對(duì)于非根元素，都存在著一條從根到該元素的路徑。樹中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。樹是層次數(shù)據(jù)結(jié)構(gòu)。

(4)圖狀結(jié)構(gòu)(graph)。圖是最一般的數(shù)據(jù)結(jié)構(gòu)，圖中每個(gè)元素的前驅(qū)和后繼的數(shù)目都不限。圖中數(shù)據(jù)元素之間的關(guān)系是多對(duì)多的關(guān)系。上述四種基本結(jié)構(gòu)關(guān)系可分為兩類：線性結(jié)構(gòu)(linearstructure)和非線性結(jié)構(gòu)(non-linearstructure)。我們把除了線性結(jié)構(gòu)以外的幾種結(jié)構(gòu)關(guān)系——樹、圖和集合都?xì)w入非線性結(jié)構(gòu)一類。圖1－1四種基本結(jié)構(gòu)示意圖

(a)集合結(jié)構(gòu)；(b)線性結(jié)構(gòu)；(c)樹形結(jié)構(gòu)；(d)圖狀結(jié)構(gòu)1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是面向應(yīng)用問(wèn)題的，是從用戶角度看到的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)內(nèi)的組織方式，是邏輯數(shù)據(jù)的存儲(chǔ)映像，它是面向計(jì)算機(jī)的。我們知道，計(jì)算機(jī)內(nèi)存是由有限個(gè)存儲(chǔ)單元組成的一個(gè)連續(xù)存儲(chǔ)空間，這些存儲(chǔ)單元或者是字節(jié)編址的，或者是字編址的。從存儲(chǔ)器角度看，內(nèi)存中是一堆二進(jìn)制數(shù)據(jù)，它們可以被機(jī)器指令解釋為指令、整數(shù)、字符、布爾數(shù)等，也可以被數(shù)據(jù)結(jié)構(gòu)的算法解釋為具有某種結(jié)構(gòu)的數(shù)據(jù)。為一個(gè)數(shù)據(jù)結(jié)構(gòu)找到一種有效的表示方法，使它適于計(jì)算機(jī)存儲(chǔ)和處理是十分重要的。順序(sequential)存儲(chǔ)結(jié)構(gòu)和鏈接(linked)存儲(chǔ)結(jié)構(gòu)是兩種最基本的存儲(chǔ)表示方法。順序(或稱連續(xù)(contiguous))表示方法需要一塊連續(xù)的存儲(chǔ)空間，并把邏輯上相關(guān)的數(shù)據(jù)元素依次存儲(chǔ)在該連續(xù)的存儲(chǔ)區(qū)中。例如由4個(gè)元素組成的線性數(shù)據(jù)結(jié)構(gòu)(a0，a1，a2，a3)存儲(chǔ)在某個(gè)連續(xù)的存儲(chǔ)區(qū)內(nèi)，設(shè)存儲(chǔ)區(qū)的起始地址是102，假定每個(gè)元素占2個(gè)存儲(chǔ)單元，則其順序存儲(chǔ)表示如圖1－2(a)所示。順序表示方法并不僅限于存儲(chǔ)線性數(shù)據(jù)結(jié)構(gòu)。對(duì)于非線性數(shù)據(jù)結(jié)構(gòu)，如樹形結(jié)構(gòu)，有時(shí)也可采用順序存儲(chǔ)的方法表示。另一種基本的存儲(chǔ)表示方法是鏈接存儲(chǔ)表示。在鏈接存儲(chǔ)表示下，為了在計(jì)算機(jī)中存儲(chǔ)一個(gè)元素，除了需要存放該元素本身的信息外，還需要存放與該元素相關(guān)的其他元素的位置信息。這兩部分信息組成存放一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)(node)。圖1－2(b)給出了線性結(jié)構(gòu)(a0，a1，a2，a3)的鏈接存儲(chǔ)表示。其中每個(gè)結(jié)點(diǎn)的存儲(chǔ)塊分成兩部分，一部分存放元素自身，另一部分存放包含其后繼元素的結(jié)點(diǎn)的存儲(chǔ)位置。這種關(guān)于其他結(jié)點(diǎn)的位置信息被稱為鏈(link)。圖1－2兩種基本的存儲(chǔ)表示方法

(a)順序存儲(chǔ)結(jié)構(gòu)；(b)鏈接存儲(chǔ)結(jié)構(gòu)

圖1－2中，電接地符號(hào)表示空鏈(即不表示任何具體結(jié)點(diǎn)的地址)。注意，一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置通常是指存放該結(jié)點(diǎn)的存儲(chǔ)塊的起始單元的地址。以后的討論中，在不會(huì)引起混淆的場(chǎng)合，我們混合使用結(jié)點(diǎn)和元素這兩個(gè)術(shù)語(yǔ)。但必要時(shí)，將包括位置信息在內(nèi)的存儲(chǔ)塊整體稱為結(jié)點(diǎn)，而將其中的元素信息部分稱為該結(jié)點(diǎn)的元素。除順序和鏈接表示外，還可以有其他存儲(chǔ)數(shù)據(jù)的方法，如索引(index)方法和散列(hash)方法。關(guān)于這兩種方法，請(qǐng)參看以后相關(guān)章節(jié)。這些基本的存儲(chǔ)表示方法以及它們的組合，可衍生出各種數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。1.1.4數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算是研究數(shù)據(jù)結(jié)構(gòu)不可分割的兩個(gè)方面。所以我們討論數(shù)據(jù)結(jié)構(gòu)時(shí)不但要討論數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，還要討論在數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的運(yùn)算以及實(shí)現(xiàn)這些運(yùn)算的算法(algorithm)。通過(guò)對(duì)運(yùn)算及其算法的性能分析和討論，我們?cè)谇蠼鈶?yīng)用問(wèn)題時(shí)能選擇和設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，編寫出高效的程序。數(shù)據(jù)結(jié)構(gòu)的最常見的運(yùn)算有：

(1)創(chuàng)建運(yùn)算——?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)。

(2)清除運(yùn)算——?jiǎng)h除數(shù)據(jù)結(jié)構(gòu)中的全部元素。

(3)插入運(yùn)算——在數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新元素。

(4)刪除運(yùn)算——將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)指定元素刪除。

(5)搜索運(yùn)算——在數(shù)據(jù)結(jié)構(gòu)中搜索滿足一定條件的元素。

(6)更新運(yùn)算——修改數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定元素的值。

(7)訪問(wèn)運(yùn)算——訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素。

(8)遍歷運(yùn)算——按照某種次序，系統(tǒng)地訪問(wèn)數(shù)據(jù)結(jié)構(gòu)的各元素，使得每個(gè)元素恰好被訪問(wèn)一次。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)一旦創(chuàng)建，其結(jié)構(gòu)不會(huì)發(fā)生改變，則稱為靜態(tài)數(shù)據(jù)結(jié)構(gòu)(staticdatastructure)，否則稱為動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)(dynamicdatastructure)。也就是說(shuō)，如果一個(gè)數(shù)據(jù)結(jié)構(gòu)上定義了插入和刪除運(yùn)算，則該數(shù)據(jù)結(jié)構(gòu)被認(rèn)為是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。1.2數(shù)據(jù)抽象和抽象數(shù)據(jù)類型

抽象(abstraction)可以被理解為一種機(jī)制，其實(shí)質(zhì)是抽取共同的和實(shí)質(zhì)的東西，忽略非本質(zhì)的細(xì)節(jié)。抽象可以使我們的求解問(wèn)題過(guò)程以自頂向下的方式分步進(jìn)行：首先考慮問(wèn)題的最主要方面，然后再逐步細(xì)化，進(jìn)一步考慮問(wèn)題的某些細(xì)節(jié)，并最終實(shí)現(xiàn)之。在程序設(shè)計(jì)中，抽象機(jī)制被用于兩個(gè)方面：數(shù)據(jù)和過(guò)程。數(shù)據(jù)抽象(dataabstraction)使程序設(shè)計(jì)者可以將數(shù)據(jù)元素間的邏輯關(guān)系與數(shù)據(jù)在計(jì)算機(jī)內(nèi)的具體表示分別考慮。過(guò)程抽象(procedualabstraction)可使程序設(shè)計(jì)者將在數(shù)據(jù)上定義的運(yùn)算與實(shí)現(xiàn)這些運(yùn)算的具體方法分開考慮。抽象的好處在于降低了問(wèn)題求解的難度。1.2.2封裝與信息隱蔽封裝(encapsulation)是指把數(shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算組合在一起的機(jī)制。使用者只能通過(guò)一組允許的運(yùn)算訪問(wèn)其中的數(shù)據(jù)。原則上，數(shù)據(jù)的使用者只需知道這些運(yùn)算的定義(也稱規(guī)范)便可訪問(wèn)數(shù)據(jù)，而無(wú)需了解數(shù)據(jù)是如何組織、存儲(chǔ)的，以及運(yùn)算算法如何。也就是說(shuō)，封裝對(duì)使用者隱藏了數(shù)據(jù)結(jié)構(gòu)以及程序的實(shí)現(xiàn)細(xì)節(jié)。這種設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)或程序的策略稱為信息隱蔽(informationhiding)。通?？蓪?shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算組成模塊(module)。每個(gè)模塊有一個(gè)明確定義的接口(interface)，模塊內(nèi)部信息只能經(jīng)過(guò)這一接口被外部訪問(wèn)。一個(gè)模塊的接口是實(shí)現(xiàn)運(yùn)算的一組函數(shù)(functions)。模塊應(yīng)采用封裝和信息隱蔽原則來(lái)設(shè)計(jì)，這樣的模塊被稱為黑盒子(blackbox)。一個(gè)模塊可以被其他程序或模塊調(diào)用，它們是該模塊的客戶(client)。封裝和信息隱蔽是把錯(cuò)誤局部化的有效措施，有助于降低問(wèn)題求解的復(fù)雜度，提高程序的可靠性。1.2.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中的概念，它是數(shù)據(jù)抽象的一種方式。一個(gè)數(shù)據(jù)類型(datatype)定義了一個(gè)值的集合以及作用于該值集的運(yùn)算集合。程序設(shè)計(jì)語(yǔ)言中，一個(gè)數(shù)據(jù)類型不僅規(guī)定了該類型的變量(或常量)的取值范圍，還定義了該類型允許的運(yùn)算。例如一個(gè)類型為int的變量的取值范圍是?-32768～32767，在整型數(shù)上的算術(shù)運(yùn)算有?+、-、*、/、%，關(guān)系運(yùn)算有?<、>、<=、>=、==、!=，賦值運(yùn)算有?=?等。圖1－3的上半部分規(guī)定了int的取值范圍及允許的運(yùn)算，圖的下半部分描述與該類型的實(shí)現(xiàn)有關(guān)的方面，包括數(shù)據(jù)的表示和運(yùn)算的實(shí)現(xiàn)。兩者是分離的。圖1－3C語(yǔ)言的數(shù)據(jù)類型int了解一個(gè)數(shù)據(jù)類型的對(duì)象(變量、常量)在計(jì)算機(jī)內(nèi)的表示是有用的，但往往也是危險(xiǎn)的。這使得應(yīng)用程序可以直接編寫算法操縱該類型對(duì)象，而不是嚴(yán)格使用預(yù)先定義的運(yùn)算進(jìn)行訪問(wèn)，這會(huì)滋生不可預(yù)知的錯(cuò)誤。而且一旦改變?cè)擃愋偷拇鎯?chǔ)表示，則必須改變所有使用該類型對(duì)象的應(yīng)用程序。目前普遍認(rèn)為對(duì)使用者隱藏一個(gè)數(shù)據(jù)類型的存儲(chǔ)表示是一個(gè)好的設(shè)計(jì)策略，用戶程序只能使用該類型提供的運(yùn)算(函數(shù))訪問(wèn)該類型對(duì)象，這就是抽象數(shù)據(jù)類型。一個(gè)抽象數(shù)據(jù)類型(AbstractDataType，ADT)是一個(gè)數(shù)據(jù)類型，其主要特征是數(shù)據(jù)對(duì)象及其運(yùn)算的規(guī)范獨(dú)立于它們的實(shí)現(xiàn)，實(shí)行封裝和信息隱蔽，使ADT的使用與實(shí)現(xiàn)分離。那么，在一個(gè)抽象數(shù)據(jù)類型上應(yīng)當(dāng)定義哪些運(yùn)算呢？這取決于應(yīng)用。如果我們使用的一個(gè)抽象數(shù)據(jù)類型上定義的一組運(yùn)算足以對(duì)該類型對(duì)象實(shí)施所需要的全部操作，則這組運(yùn)算可以認(rèn)為是完備的。其實(shí)，C語(yǔ)言的類型int就是一個(gè)抽象數(shù)據(jù)類型，我們只能通過(guò)類型int所規(guī)定的運(yùn)算操縱整型變量或常量。然而僅在面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言出現(xiàn)后，才提供了必要的機(jī)制，如C++語(yǔ)言的類(class)，使用戶有可能真正實(shí)現(xiàn)抽象數(shù)據(jù)類型。但這并不意味著當(dāng)我們使用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)時(shí)，不能運(yùn)用抽象數(shù)據(jù)類型的原則。1.2.4數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一方面要聲明它的邏輯結(jié)構(gòu)，同時(shí)還應(yīng)定義一組在該數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的運(yùn)算。邏輯結(jié)構(gòu)和運(yùn)算的定義組成了數(shù)據(jù)結(jié)構(gòu)的規(guī)范(specification)，而數(shù)據(jù)的存儲(chǔ)表示和運(yùn)算算法的描述構(gòu)成了數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)(implementation)。規(guī)范是實(shí)現(xiàn)的準(zhǔn)則和依據(jù)，規(guī)范指明“做什么”，而實(shí)現(xiàn)解決“怎樣做”。從規(guī)范和實(shí)現(xiàn)兩方面來(lái)討論數(shù)據(jù)結(jié)構(gòu)的方式是抽象數(shù)據(jù)類型的觀點(diǎn)。

1.3描述數(shù)據(jù)結(jié)構(gòu)1.3.1數(shù)據(jù)結(jié)構(gòu)的規(guī)范一個(gè)運(yùn)算的規(guī)范是在概念層次上或從用戶角度對(duì)運(yùn)算的精確定義，它既能精確描述運(yùn)算又不涉及運(yùn)算的實(shí)現(xiàn)細(xì)節(jié)。本書中，我們從語(yǔ)法和語(yǔ)義兩方面描述一個(gè)運(yùn)算。一方面使用C語(yǔ)言的函數(shù)原型(functionprototype)規(guī)定該運(yùn)算的使用格式，包括運(yùn)算名稱、運(yùn)算的輸入?yún)?shù)、輸出參數(shù)和返回值，另一方面規(guī)定了使用一個(gè)運(yùn)算應(yīng)當(dāng)滿足的先決條件和運(yùn)算執(zhí)行后應(yīng)有的結(jié)果，即運(yùn)算的功能。這里需說(shuō)明一點(diǎn)，數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是較抽象層次上的概念，當(dāng)我們實(shí)際用C語(yǔ)言函數(shù)實(shí)現(xiàn)一個(gè)運(yùn)算時(shí)，有時(shí)還需要輔助函數(shù)，也就是說(shuō)實(shí)現(xiàn)一個(gè)運(yùn)算可能需要設(shè)計(jì)不止一個(gè)C語(yǔ)言函數(shù)。下面以復(fù)數(shù)數(shù)據(jù)結(jié)構(gòu)為例，說(shuō)明本書所采用的數(shù)據(jù)結(jié)構(gòu)的描述方法。在ADT1－1中，復(fù)數(shù)被定義為一個(gè)抽象數(shù)據(jù)類型Complex。一個(gè)復(fù)數(shù)由一對(duì)實(shí)數(shù)(x，y)構(gòu)成，x為實(shí)部，y為虛部。在復(fù)數(shù)ADTComplex上定義了構(gòu)造函數(shù)(CreateComp)及加(Add)、減(Sub)、乘(Mul)和除(Div)四個(gè)運(yùn)算。

ADT1-1Complex{

數(shù)據(jù)：

由一對(duì)實(shí)數(shù)(x,y)構(gòu)成，x為實(shí)部，y為虛部。

運(yùn)算：設(shè)兩個(gè)復(fù)數(shù)分別為a=(a1,a2)和b=(b1,b2)。

ComplexCreateComp(floatx,floaty)

構(gòu)造函數(shù)，函數(shù)返回復(fù)數(shù)(x,y)。

ComplexAdd(Complexa,Complexb)

設(shè)和的實(shí)部和虛部分別不超過(guò)實(shí)型值的允許范圍，返回復(fù)數(shù)(a1+b1,a2+b2)。

ComplexSub(Complexa,Complexb)

設(shè)差的實(shí)部和虛部分別不超過(guò)實(shí)型值的允許范圍，返回復(fù)數(shù)(a1-b1,a2-b2)。

ComplexMul(Complexa,Complexb)設(shè)積的實(shí)部和虛部分別不超過(guò)實(shí)型值的允許范圍，返回復(fù)數(shù)(a1b1-a2b2，a1b1+a2b2)。

ComplexDiv(Complexa,Complexb)設(shè)除數(shù)b不為0，且商的實(shí)部和虛部分別不超過(guò)實(shí)型值的允許范圍，返回復(fù)數(shù)((a1b1+a2b2)/(b12+b22)，(a2b1-a1b2)/(b12+b22))。

}1.3.2實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)必須首先確定數(shù)據(jù)的存儲(chǔ)表示，然后在給定的存儲(chǔ)方式下實(shí)現(xiàn)相應(yīng)的運(yùn)算。本書中，C語(yǔ)言的結(jié)構(gòu)、數(shù)組、指針等被用于描述數(shù)據(jù)的存儲(chǔ)表示。這里，不妨假定C語(yǔ)言的數(shù)組和結(jié)構(gòu)都是順序存儲(chǔ)的：認(rèn)為數(shù)組元素具有相同的數(shù)據(jù)類型，按照下標(biāo)的次序存儲(chǔ)在連續(xù)的存儲(chǔ)區(qū)；結(jié)構(gòu)可以由不同類型的域(成分)組成，按照域表的次序順序存放。借助于C語(yǔ)言的數(shù)組、結(jié)構(gòu)和指針可以描述和實(shí)現(xiàn)本書討論的數(shù)據(jù)結(jié)構(gòu)的各種不同的存儲(chǔ)表示。

C語(yǔ)言也被用于描述運(yùn)算的算法。當(dāng)一個(gè)算法采用程序設(shè)計(jì)語(yǔ)言描述時(shí)，需要了解算法足夠多的實(shí)現(xiàn)細(xì)節(jié)，這有些麻煩。所幸的是書中算法的C程序都較短，不至掩蓋算法實(shí)質(zhì)，由此帶來(lái)的好處是有助于提高學(xué)生C語(yǔ)言程序設(shè)計(jì)的能力。程序1－1是復(fù)數(shù)ADT的C語(yǔ)言實(shí)現(xiàn)。代碼可分為兩部分：復(fù)數(shù)結(jié)構(gòu)類型和實(shí)現(xiàn)復(fù)數(shù)運(yùn)算的C函數(shù)。注意區(qū)分Complex和complex。此處complex是結(jié)構(gòu)名，不是類型名，它只是一個(gè)結(jié)構(gòu)標(biāo)記。程序1－1首先采用typedef將復(fù)數(shù)ADTComplex的存儲(chǔ)表示描述為一個(gè)C語(yǔ)言的結(jié)構(gòu)，然后給出實(shí)現(xiàn)各個(gè)運(yùn)算的算法。程序1－1中，運(yùn)算Add由一個(gè)C函數(shù)實(shí)現(xiàn)。用同樣的方法可以寫出其他運(yùn)算的實(shí)現(xiàn)代碼。

【程序1－1】Complex的實(shí)現(xiàn)。

#include<stdio.h>

#include<stdlib.h>

typedefstructcomplex

{

floatx,y;

}Complex;

ComplexCreateComp(floatx,floaty)

{

Complexc;

c.x=x;c.y=y;

returnc;

}

ComplexAdd(Complexa,Complexb)

{

Complexc;

c.x=a.x+b.x;

c.y=a.y+b.y;

returnc;

}…一旦實(shí)現(xiàn)Complex的全部運(yùn)算，我們便可在主函數(shù)或其他應(yīng)用程序中使用Complex的運(yùn)算進(jìn)行復(fù)數(shù)計(jì)算。一個(gè)簡(jiǎn)單的測(cè)試程序見程序1－2。程序1－2中還需要使用函數(shù)voidPrintComplex(Complexa)。從封裝和信息隱蔽的角度看，也應(yīng)將這一運(yùn)算添加到ADT1－1中，并在程序1－1中實(shí)現(xiàn)之。

【程序1－2】

測(cè)試復(fù)數(shù)加法運(yùn)算。

voidPrintComplex(Complexa)

{

printf("%3.2f+%3.2fi\n",a.x,a.y);

}

voidmain()

{

Complexa,b,c;

a=CreateComp(1.0f,2.0f);/*構(gòu)造復(fù)數(shù)a=(1+2i)*/

b=CreateComp(3.0f,4.0f); /*構(gòu)造復(fù)數(shù)b=(3+4i)*/

c=Add(a,b); /*復(fù)數(shù)c=a+b*/

PrintComplex(a);PrintComplex(b);

PrintComplex(c);

} 1.4算法和算法分析1.4.1算法及其性能標(biāo)準(zhǔn)什么是算法？籠統(tǒng)地說(shuō)，算法是求解一類問(wèn)題的任意一種特殊的方法。較嚴(yán)格的說(shuō)法是：一個(gè)算法(algorithm)是對(duì)特定問(wèn)題的求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列五個(gè)特征：

(1)輸入(input)：算法有零個(gè)或多個(gè)輸入。

(2)輸出(output)：算法至少產(chǎn)生一個(gè)輸出。

(3)確定性(definite)：算法的每一條指令都有確切的定義，沒有二義性。

(4)能行性(effective)：算法的每一條指令都足夠基本，它們可以通過(guò)執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的基本運(yùn)算來(lái)實(shí)現(xiàn)。

(5)有窮性(terminative)：算法總能在執(zhí)行有限步之后終止。凡是算法，都必須滿足以上五條特征。對(duì)于書中討論的數(shù)據(jù)結(jié)構(gòu)上定義的運(yùn)算，我們將討論實(shí)現(xiàn)它們的相應(yīng)算法。描述一個(gè)算法有多種方法，它可以用自然語(yǔ)言、流程圖或程序設(shè)計(jì)語(yǔ)言來(lái)描述。當(dāng)一個(gè)算法直接使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述時(shí)，該算法便成為程序。算法必須可終止，但計(jì)算機(jī)程序并沒有這一限制，比如操作系統(tǒng)是一個(gè)程序，但不是一個(gè)算法。本書中，我們使用C語(yǔ)言描述算法，當(dāng)然只有當(dāng)了解了算法的足夠多的實(shí)現(xiàn)細(xì)節(jié)后，才能寫成程序，同時(shí)，這也使得對(duì)算法的性能分析往往成為對(duì)相應(yīng)程序的性能分析。衡量一個(gè)算法的性能，主要有以下幾個(gè)標(biāo)準(zhǔn)：

(1)正確性(correctness)：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。

(2)簡(jiǎn)明性(simplicity)：一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂。

(3)健壯性(robustness)：當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至于引起嚴(yán)重后果。

(4)效率(effeciency)：有效使用存儲(chǔ)空間，并有高的時(shí)間效率。算法的正確性是指在合法的輸入下，算法應(yīng)實(shí)現(xiàn)預(yù)先規(guī)定的功能和計(jì)算精度要求。對(duì)于大型程序，我們無(wú)法奢望它是“完全正確”的，而且這一點(diǎn)也往往無(wú)法證實(shí)，但我們要求它是健壯的，其含義是當(dāng)程序萬(wàn)一遇到意外時(shí)，能按某種預(yù)定的方式作出適當(dāng)?shù)奶幚?。正確性和健壯性是相互補(bǔ)充的。正確的程序并不一定是健壯的，而健壯的程序并不一定絕對(duì)正確。一個(gè)可靠的程序應(yīng)當(dāng)能在正常情況下正確地工作，而在異常情況下亦能作出適當(dāng)?shù)奶幚?，這就是程序的可靠性。1.4.2算法的時(shí)間復(fù)雜度一個(gè)程序的時(shí)間復(fù)雜度(timecomplexity)是程序運(yùn)行從開始到結(jié)束所需的時(shí)間。程序的一次運(yùn)行是針對(duì)所求解的問(wèn)題的某一特定實(shí)例(instance)而言的。例如，求解排序問(wèn)題的排序算法的每次執(zhí)行是對(duì)一組特定個(gè)數(shù)的元素進(jìn)行排序。對(duì)該組元素的排序是排序問(wèn)題的一個(gè)實(shí)例。元素個(gè)數(shù)可視為該實(shí)例的特征(characteristics)，它直接影響排序算法的執(zhí)行時(shí)間和所需的存儲(chǔ)空間。因此，判斷算法性能要考慮的一個(gè)基本特征是問(wèn)題實(shí)例的規(guī)模(size)。規(guī)模一般是指輸入量(有時(shí)也涉及輸出量)。程序的運(yùn)行時(shí)間與實(shí)例的特征有關(guān)。使用相同的排序算法對(duì)100個(gè)元素進(jìn)行排序與對(duì)10?000個(gè)元素進(jìn)行排序所需的時(shí)間顯然是不同的。當(dāng)然，算法自身的好壞直接影響程序所需的運(yùn)行時(shí)間。不同的排序算法對(duì)同一組元素(即相同的實(shí)例)進(jìn)行排序，程序運(yùn)行的時(shí)間一般是不相同的。程序的運(yùn)行時(shí)間不僅與問(wèn)題實(shí)例的特征和算法自身的優(yōu)劣有關(guān)，還與運(yùn)行程序的計(jì)算機(jī)軟、硬件環(huán)境相關(guān)。它依賴于編譯程序所產(chǎn)生的目標(biāo)代碼的效率，以及運(yùn)行程序的計(jì)算機(jī)的速度及其運(yùn)行環(huán)境。一般來(lái)說(shuō)，我們希望能對(duì)算法(程序)作事前分析(priorianalysis)，在排除程序運(yùn)行環(huán)境的因素后再來(lái)討論算法的時(shí)間效率。當(dāng)然這不是程序運(yùn)行時(shí)間的實(shí)際值，而是算法運(yùn)行時(shí)間的一種事前估計(jì)。算法的事后測(cè)試(posteroritesting)是測(cè)試一個(gè)程序在所選擇的輸入數(shù)據(jù)下運(yùn)行時(shí)實(shí)際需要的時(shí)間。為了實(shí)施算法的事前分析，通常使用程序步的概念。一個(gè)程序步(programstep)是指在語(yǔ)法上或語(yǔ)義上有意義的程序段，該程序段的執(zhí)行時(shí)間與問(wèn)題實(shí)例的特征無(wú)關(guān)。下面我們以求一個(gè)數(shù)組元素的累加之和的程序(見程序1－3)為例，來(lái)說(shuō)明如何計(jì)算一個(gè)程序的程序步數(shù)。其中，n個(gè)元素存放在數(shù)組list中，count是全局變量，用來(lái)計(jì)算程序步數(shù)。程序中，語(yǔ)句count++;?與數(shù)組求和的算法無(wú)關(guān)，只是為了計(jì)算程序步數(shù)而添加的。去掉所有此語(yǔ)句，便是數(shù)組求和程序?？梢钥吹?，這里被計(jì)算的每一程序步均與問(wèn)題實(shí)例的規(guī)模n(數(shù)組元素的個(gè)數(shù))無(wú)關(guān)。該程序的程序步數(shù)為2n+3。【程序1－3】求一個(gè)數(shù)組元素的累加之和的迭代程序。floatSum(floatlist[]，intn){

floattempsum=0.0;

count++; /*針對(duì)賦值語(yǔ)句*/

for(inti=0;i<n;i++){

count++；/*針對(duì)for循環(huán)語(yǔ)句*/

tempsum+=list[i];

count++; /*針對(duì)賦值語(yǔ)句*/

}

count++; /*針對(duì)for的最后一次執(zhí)行*/

count++; /*針對(duì)return語(yǔ)句*/

returntempsum;

}【程序1－4】求一個(gè)數(shù)組元素的累加之和的遞歸程序。

floatRSum(floatlist[]，intn)

{

count++; /*針對(duì)if條件*/

if(n){

count?++; /*針對(duì)RSum調(diào)用和return語(yǔ)句*/

returnRSum(list,n-1)+list[n-1];

}

count++; /*針對(duì)return語(yǔ)句*/

return0；

}為了確定這一遞歸程序的程序步，首先考慮當(dāng)n=0時(shí)的情況。很明顯，當(dāng)n=0時(shí)，執(zhí)行if條件語(yǔ)句和第二句return語(yǔ)句，所需的程序步數(shù)為2。當(dāng)n>0時(shí)，執(zhí)行if條件語(yǔ)句和第一句return語(yǔ)句。設(shè)程序RSum的程序步數(shù)為T(n)，則有(1－2)這是一個(gè)遞推公式，可以通過(guò)下面的方式計(jì)算：

T(n)?=2+T(n－1)

=2+2+T(n－2)

=2+2+2+T(n－3)

=2*n+T(0)

=2*n+2…同樣，移去程序1－4中的所有count++;?語(yǔ)句，便是數(shù)組求和的遞歸程序。雖然計(jì)算所得到的程序1－4的程序步數(shù)為2n+2，少于程序1－3的程序步數(shù)2n+3，但這并不意味著前者比后者快。請(qǐng)注意兩者使用的程序步是不同的。語(yǔ)句returntempsum;與語(yǔ)句returnRSum(list,n－1)?+?list[n－1];的時(shí)間開銷顯然是不同的。

定義：設(shè)f(n)和g(n)是定義在正整數(shù)上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≤cg(n)，則記作f(n)?=?O(g(n))，被稱為大O記號(hào)(big-Ohnotation)。大O記號(hào)用以表達(dá)一個(gè)算法運(yùn)行時(shí)間的上界。當(dāng)我們說(shuō)一個(gè)算法具有O(g(n))的運(yùn)行時(shí)間時(shí)，是指該算法在計(jì)算機(jī)上的實(shí)際運(yùn)行時(shí)間不會(huì)超過(guò)g(n)的一個(gè)常數(shù)倍。1.4.3漸近時(shí)間復(fù)雜度例如，設(shè)一個(gè)程序的實(shí)際執(zhí)行時(shí)間T(n)?=?3.6n3?+?2.5?n2?+?2.8，下面的定理表明T(n)=O(n3)。這就是說(shuō)，如果我們只能夠知道T(n)=O(n3)，并不能得到T(n)?=?3.6n3?+?2.5n2?+2.8的計(jì)算公式，從算法事前分析的角度，我們認(rèn)為已經(jīng)有了滿意的對(duì)算法時(shí)間復(fù)雜度的估計(jì)結(jié)果。使用大O記號(hào)表示的算法的時(shí)間復(fù)雜度，稱為算法的漸近時(shí)間復(fù)雜度(asymptoticcomplexity)。漸近時(shí)間復(fù)雜度也常簡(jiǎn)稱為時(shí)間復(fù)雜度。通常用O(1)表示常數(shù)計(jì)算時(shí)間，即算法只需執(zhí)行有限個(gè)程序步。

定理：如果f(n)?=?amnm?+?am－1nm－1?+?

?+?a1n?+?a0是m次多項(xiàng)式，則f(n)?=?O(nm)。證明：取n0=1，當(dāng)n≥n0時(shí)，有

f(n)?=?amnm?+?am－1nm－1?+?

?+?a1n?+?a0

?≤|am|nm?+?|am－1|nm－1?+?

?+?|a1|n?+?|a0|

????≤(|am|?+?|am－1|/n?+?

?+?|a1|/nm－1?+?|a0|/nm)nm

????≤(|am|?+?|am－1|?+?

?+?|a1|?+?|a0|)nm

可取c?=?|am|?+?|am－1|?+?

?+?|a1|+|a0|。定理得證。常見的漸近時(shí)間復(fù)雜度按從小到大順序排列為：O(1)<O(lbn)?<O(n)?<O(nlbn)<O(n2)<O(n3)。我們可用大O記號(hào)表示的程序步來(lái)估計(jì)算法的時(shí)間復(fù)雜度，即得到算法的漸近時(shí)間復(fù)雜度。程序1－3和程序1－4的漸近時(shí)間復(fù)雜度均為O(n)，即O(2n+3)=O(n)和O(2n+2)=O(n)。很多情況下，我們可以通過(guò)考察一個(gè)程序中的關(guān)鍵操作(關(guān)鍵操作被認(rèn)為是一個(gè)程序步)的執(zhí)行次數(shù)來(lái)計(jì)算算法的漸近時(shí)間復(fù)雜度，有時(shí)也需要同時(shí)考慮幾個(gè)關(guān)鍵操作，以反映算法的執(zhí)行時(shí)間。例如程序1－3中，語(yǔ)句tempsum+=list[i];可認(rèn)為是關(guān)鍵操作，它的執(zhí)行次數(shù)為n，由此得到算法的漸近時(shí)間復(fù)雜度也是O(n)。T(n)=2n3+3n2+2n+1程序1－5是實(shí)現(xiàn)兩個(gè)n

n矩陣相乘的程序段，每行的最右邊表明該行語(yǔ)句執(zhí)行的次數(shù)，我們將它們視為程序步。整個(gè)程序中所有語(yǔ)句的執(zhí)行次數(shù)為(1－3)語(yǔ)句c[i][j]+=a[i][k]*b[k][j];可看成關(guān)鍵操作，它的執(zhí)行次數(shù)是n3。所以，算法的漸近時(shí)間復(fù)雜度為O(n3)。

【程序1－5】矩陣乘法。

for(i=0;i<n;i++) /*n+1*/

for(j=0;j<n;j++){ /*n(n+1)*/

c[i][j]=0; /*n2*/

for(k=0;k<n;k++) /*n2(n+1)*/

c[i][j]+=a[i][k]*b[k][j]; /*n3*/

}1.4.4最壞、最好和平均情況時(shí)間復(fù)雜度對(duì)于某些算法，即使問(wèn)題實(shí)例的規(guī)模相同，如果輸入數(shù)據(jù)不同，算法所需的時(shí)間開銷也會(huì)不同。例如，在一個(gè)有n個(gè)元素的數(shù)組中找一個(gè)給定的元素，從第一個(gè)元素開始依次檢查數(shù)組元素。如果我們要找的元素是第一個(gè)元素，所需的查找時(shí)間最短，這就是所謂的算法的最好情況(bestcase)。如果待查的元素是最后一個(gè)元素，則是算法的最壞情況(worstcase)。如果我們多次在數(shù)組中查找元素，并且假定以某種概率查找每個(gè)數(shù)組元素，最典型的是以相等的概率查找每個(gè)數(shù)組元素，這種情況下，就會(huì)發(fā)現(xiàn)程序需平均檢索n/2個(gè)元素，我們稱之為算法時(shí)間代價(jià)的平均情況(averagecase)。對(duì)應(yīng)于三種不同的情況，我們有關(guān)于算法的三種時(shí)間復(fù)雜度：最好情況、最壞情況和平均情況時(shí)間復(fù)雜度。在三種情況下，我們都可以得到它們的漸近時(shí)間復(fù)雜度表示。程序1－5的例子對(duì)于三種情況的時(shí)間復(fù)雜度都是一樣的，三種情況下有不相同的時(shí)間復(fù)雜度的例子我們將在后面的章節(jié)中給出。1.4.5算法的空間復(fù)雜度一個(gè)程序的空間復(fù)雜度(spacecomplexity)是程序運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。程序運(yùn)行所需的存儲(chǔ)空間包括兩部分：

(1)固定部分(fixedspacerequirement)。這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無(wú)關(guān)，或者說(shuō)與問(wèn)題的實(shí)例的特征無(wú)關(guān)。它主要包括程序代碼、常量、簡(jiǎn)單變量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。

(2)可變部分(variablespacerequirement)。這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如，將有100個(gè)元素的兩個(gè)數(shù)組相加，與將有10個(gè)元素的兩個(gè)數(shù)組相加，所需的存儲(chǔ)空間顯然是不同的。這部分存儲(chǔ)空間包括數(shù)據(jù)元素所占的空間，以及算法執(zhí)行所需的額外空間，如遞歸棧所用的空間。對(duì)算法的空間復(fù)雜度的討論類似于對(duì)時(shí)間復(fù)雜度的討論，并且一般來(lái)說(shuō)，空間復(fù)雜度的計(jì)算比起時(shí)間復(fù)雜度的計(jì)算來(lái)得容易。此外，應(yīng)當(dāng)注意的是空間復(fù)雜度一般按最壞情況來(lái)分析。第2章數(shù)?組?和?鏈?表

2.1結(jié)構(gòu)與聯(lián)合2.2數(shù)組2.3鏈表習(xí)題22.1結(jié)構(gòu)與聯(lián)合2.1.1結(jié)構(gòu)結(jié)構(gòu)(structure)是C語(yǔ)言提供的聚合數(shù)據(jù)的機(jī)制。使用結(jié)構(gòu)可以將不同類型的數(shù)據(jù)組合成一個(gè)整體，便于使用。一個(gè)結(jié)構(gòu)(在許多其他程序設(shè)計(jì)語(yǔ)言中稱為記錄record)是數(shù)據(jù)項(xiàng)的聚集(collection)。每個(gè)數(shù)據(jù)項(xiàng)有名稱和類型，它們可以是不同的數(shù)據(jù)類型。例如：structstudent{charname[20];charsex;intage;}

該語(yǔ)句定義了一個(gè)結(jié)構(gòu)類型structstudent，可以使用它作為定義結(jié)構(gòu)變量的類型，如structstudentstudA;，這里，變量studA是一個(gè)結(jié)構(gòu)。可以使用成員運(yùn)算符“.”對(duì)結(jié)構(gòu)變量的成員賦值。如:strcpy(studA.name,"Wang"); /*字符串賦值函數(shù)*/studA.age=19;studA.sex='M';

對(duì)成員變量可以像對(duì)普通變量一樣進(jìn)行其類型所允許的各種運(yùn)算。

ANSIC允許將一個(gè)結(jié)構(gòu)變量整體賦值給另一個(gè)具有相同結(jié)構(gòu)的結(jié)構(gòu)變量，但不能將一個(gè)結(jié)構(gòu)變量作為一個(gè)整體進(jìn)行輸入和輸出，也不能直接判定兩個(gè)結(jié)構(gòu)是否相同。

為了能像使用C語(yǔ)言類型int一樣使用一個(gè)結(jié)構(gòu)類型，我們可以用typedef創(chuàng)建自己的結(jié)構(gòu)類型Student如下：typedefstructstudent{charname[20];charsex;intage;}Student；這里，student是結(jié)構(gòu)名，Student是結(jié)構(gòu)類型名，我們可以像使用類型int一樣用Student定義結(jié)構(gòu)變量。定義變量的語(yǔ)句為StudentstudA;，無(wú)須加保留字struct。事實(shí)上，結(jié)構(gòu)名稱與結(jié)構(gòu)類型的名稱可以相同。2.1.2聯(lián)合聯(lián)合(union)是一個(gè)變量，它可以存放不同類型的數(shù)據(jù)對(duì)象。例如在編譯程序的符號(hào)表管理中，假定常量可以是int、float或char類型。一種最簡(jiǎn)單的管理方法是不考慮它們的類型，分配相同大小的空間存放各種常量。聯(lián)合的目的是使用單一變量，存放多個(gè)類型的值。顯然任何時(shí)候只能存放其中之一。定義一個(gè)聯(lián)合的方法類似于結(jié)構(gòu)，見下面的例子。unionu_tag{intival;floatfval;charchval;}；這里，unionu_tag是一個(gè)聯(lián)合類型，可以用來(lái)定義聯(lián)合變量，如unionu_taga，b;。分配給聯(lián)合變量使用的存儲(chǔ)塊的大小是它的最大變量所需的存儲(chǔ)塊的大小。

聯(lián)合可以放在結(jié)構(gòu)或數(shù)組中，反之亦然。訪問(wèn)一個(gè)結(jié)構(gòu)中的聯(lián)合的成員等同于訪問(wèn)嵌套的結(jié)構(gòu)變量。例如，struct{charname[20];intflags;intutype;union{intival;floatfval;charchval;}u;}symtab[maxsize];

引用聯(lián)合的成員ival的方式是：symtab[i].u.ival。我們也可以像創(chuàng)建結(jié)構(gòu)類型一樣用typedef創(chuàng)建自己的聯(lián)合類型，如下面的定義：typedefunionu_tag{intival;floatfval;charchval;}Constval；2.2數(shù)組

數(shù)組(array)是大家熟悉的一種數(shù)據(jù)類型，幾乎所有的程序設(shè)計(jì)語(yǔ)言都包含數(shù)組類型。C語(yǔ)言的數(shù)組是連續(xù)存儲(chǔ)的，因此很自然地，我們可以使用C語(yǔ)言數(shù)組描述數(shù)據(jù)的順序存儲(chǔ)結(jié)構(gòu)。數(shù)組與結(jié)構(gòu)不同的是，數(shù)組的元素具有相同的數(shù)據(jù)類型，而結(jié)構(gòu)的元素(域)可以是不同類型。所以，數(shù)組元素用下標(biāo)(index)標(biāo)識(shí)，而結(jié)構(gòu)的域由域名(fieldname)引用。2.2.1一維數(shù)組一維數(shù)組(one-dimensionalarray)常用于順序存儲(chǔ)的線性數(shù)據(jù)結(jié)構(gòu)中。讓我們先來(lái)看C語(yǔ)言中的一維數(shù)組。例如，intone[5];定義了5個(gè)整數(shù)組成的一個(gè)數(shù)組，下標(biāo)從0到4。數(shù)組元素可以在定義時(shí)賦值，也可以通過(guò)引用數(shù)組元素對(duì)元素賦值。例如，

intone[5]={0,1,2,3,4};或

for(i=0;i<5;i++)one[i]=i;

數(shù)組通常采用順序表示，即數(shù)組中的元素按一定順序存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)域。一個(gè)一維數(shù)組可以直接映射到一維的存儲(chǔ)空間。由于數(shù)組元素具有相同類型，每個(gè)元素占有相同數(shù)量的存儲(chǔ)單元，因此根據(jù)數(shù)組元素的下標(biāo)可以方便地計(jì)算元素的存放地址。設(shè)給長(zhǎng)度為n的一維數(shù)組a所分配的存儲(chǔ)塊的起始地址是Loc(a[0])，若已知a的每個(gè)元素占k個(gè)存儲(chǔ)單元，則下標(biāo)為i的數(shù)組元素a[i]的存放地址Loc(a[i])是

Loc(a[i])=Loc(a[0])+i*k0≤i＜n(2－1)2.2.2二維數(shù)組二維數(shù)組(two-dimensionalarray)的下標(biāo)是二維的。可以認(rèn)為二維數(shù)組是每個(gè)元素都是一維數(shù)組的一維數(shù)組。將一個(gè)二維數(shù)組映射到一維的存儲(chǔ)空間一般有兩種順序：行優(yōu)先順序(rowmajororder)和列優(yōu)先順序(columnmajororder)。大多數(shù)語(yǔ)言如Pascal、Basic、C和C++等都是按行優(yōu)先順序存儲(chǔ)的，F(xiàn)ortran語(yǔ)言是按列優(yōu)先順序存儲(chǔ)二維數(shù)組元素的?，F(xiàn)考察采用行優(yōu)先順序存放二維數(shù)組時(shí)，數(shù)組元素的地址計(jì)算公式。

設(shè)有m行n列的二維數(shù)組a[m][n]，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)數(shù)組元素a[0][0]的存儲(chǔ)地址是Loc(a[0][0])，則數(shù)組元素a[i][j]的存儲(chǔ)地址Loc(a[i][j])為L(zhǎng)oc(a[i][j])=Loc(a[0][0])+(i*n+j)*k0≤i＜m;0≤j＜n(2－2)其中，Loc(a[0][0])被稱為基地址(baseaddress)，它是存儲(chǔ)數(shù)組的存儲(chǔ)塊的起始地址。由此我們可以看到，對(duì)于數(shù)組，一旦規(guī)定了它的維數(shù)和各維的長(zhǎng)度，便可為它分配存儲(chǔ)空間，并且只要給出數(shù)組元素下標(biāo)，就可根據(jù)相應(yīng)的地址計(jì)算公式求得數(shù)組元素的存儲(chǔ)位置來(lái)存取元素。這種方式下，存取數(shù)組中任何一個(gè)元素所需的時(shí)間是相同的，我們稱具有這一存取特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)(randomaccessstoragestructure)。圖2－1二維數(shù)組的順序存儲(chǔ)(a)行優(yōu)先順序存儲(chǔ)；(b)列優(yōu)先順序存儲(chǔ)

下列語(yǔ)句定義了一個(gè)靜態(tài)二維數(shù)組a，并對(duì)其初始化，兩維的長(zhǎng)度分別為3和4。

staticinta[3][4]={{1},{0,6},{0,0,11}};

每一行中不足的元素自動(dòng)為0，這樣，初始化后的數(shù)組a的元素為：

此處，數(shù)組a被定義成靜態(tài)存儲(chǔ)變量。靜態(tài)存儲(chǔ)變量存放在靜態(tài)存儲(chǔ)區(qū)中，在程序執(zhí)行期間，它們占據(jù)固定的存儲(chǔ)單元。

此處，數(shù)組a被定義成靜態(tài)存儲(chǔ)變量。靜態(tài)存儲(chǔ)變量存放在靜態(tài)存儲(chǔ)區(qū)中，在程序執(zhí)行期間，它們占據(jù)固定的存儲(chǔ)單元。下面是定義一個(gè)二維數(shù)組類型的兩種方法，后者將一個(gè)二維數(shù)組定義為其成員類型是一維數(shù)組的一維數(shù)組類型。兩者是等價(jià)的。

typedefintatype[3][4];或

typedefintat[4]; typedefatatype[3];使用類型atype定義二維數(shù)組a的語(yǔ)句為：

atypea={{1},{0,6},{0,0,11}};2.2.3多維數(shù)組可以將二維數(shù)組的地址計(jì)算方法推廣到多維數(shù)組的情況。多維數(shù)組的地址映射方式也可以有類似于二維數(shù)組的行優(yōu)先和列優(yōu)先兩種做法。設(shè)有n維數(shù)組a，各維的長(zhǎng)度分別為：m1，m2，...，mn，每個(gè)元素占k個(gè)單元，則在行優(yōu)先方式(亦稱字典編排順序)下，數(shù)組元素a[i1][i2]…[in]的存儲(chǔ)地址的計(jì)算公式為：Loc(a[i1][i2]…[in])=Loc(a[0]…[0])+(i1*m2*m3*…*mn-+i2*m3*m4*…*mn-+…+in-1*mn+in)*k

＝Loc(a[0]…[0])+((+in)*k(2-3)

容易看出，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。通過(guò)計(jì)算地址便可實(shí)現(xiàn)對(duì)數(shù)組元素的隨機(jī)存取。注意，C語(yǔ)言中數(shù)組是不允許整體賦值的。另外，對(duì)數(shù)組下標(biāo)超出正常范圍的訪問(wèn)并不限制，例如對(duì)長(zhǎng)度為5的一維數(shù)組a，對(duì)不合法的訪問(wèn)a[－3]，a[7]，系統(tǒng)并不給予警告，提請(qǐng)讀者在使用時(shí)注意。順序存儲(chǔ)表示是實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的重要存儲(chǔ)方式，它一般借助數(shù)組來(lái)描述。數(shù)組是靜態(tài)數(shù)據(jù)結(jié)構(gòu)，其存儲(chǔ)空間的大小需具體確定，并預(yù)先分配，一旦分配則難以擴(kuò)充。對(duì)于事先無(wú)法預(yù)知所需空間大小的應(yīng)用，采用鏈接存儲(chǔ)方式存儲(chǔ)數(shù)據(jù)通常更適合。2.3鏈表2.3.1指針

1．指針

C語(yǔ)言中，指針(pointer)也稱為鏈(link)或引用(reference)。C語(yǔ)言使用下列語(yǔ)句定義一個(gè)整型變量i和一個(gè)指向整型變量的指針變量pi：

inti,*pi;

事實(shí)上，對(duì)任意類型T，都可定義指向該類型的指針類型。指針類型變量的值是一個(gè)存儲(chǔ)地址。C語(yǔ)言中有兩個(gè)十分重要的與指針類型相關(guān)的運(yùn)算符：取地址運(yùn)算符(addressoperator)&和間接引用運(yùn)算符(dereferencingoperator)*。間接引用運(yùn)算符用來(lái)對(duì)指針變量所指示的變量進(jìn)行操作?？聪旅娴某绦蚨危?/p>

inti,*pi; /*定義整型變量i和指向整型的指針變量pi*/pi=&i; /*將變量i的地址賦給指針(變量)pi*/i=5; /*對(duì)變量i賦整數(shù)值5*/printf("%d，"，i); /*輸出i的值5和逗號(hào)*/*pi=10;/*對(duì)指針pi所指示的存儲(chǔ)位置(變量i)賦值10*/printf("%d"，*pi); /*輸出i的當(dāng)前值10*/運(yùn)行上面的程序段將顯示：5，10。C語(yǔ)言有一個(gè)特殊的指針值NULL，它不指向任何數(shù)據(jù)對(duì)象和函數(shù)。一般地，NULL由整數(shù)0表示。上述程序段的執(zhí)行過(guò)程可以對(duì)照?qǐng)D2－2來(lái)理解。應(yīng)注意的是：指針變量pi的值是整型變量i的地址，這里假定分配給變量i的地址是254。圖2－2指針定義和運(yùn)算

2．指針和數(shù)組

C語(yǔ)言中，指針和數(shù)組密切相關(guān)，任何在數(shù)組上執(zhí)行的運(yùn)算都可以使用指針實(shí)現(xiàn)。C語(yǔ)言規(guī)定數(shù)組名代表數(shù)組的首地址(起始地址)，那么如果我們定義了數(shù)組a：inta[5];，則語(yǔ)句int*p＝a;和int*p=&a[0];是等價(jià)的。如圖2－3所示，我們看到一個(gè)指向數(shù)組的指針實(shí)際上是指向數(shù)組元素a[0]的指針。

圖2－3指針和數(shù)組

引用一個(gè)數(shù)組元素可以使用以下的方法：

(1)下標(biāo)法，如a[3]=7;。

(2)指針?lè)?，?(a+3)=7;或*(p+3)=7;。由于數(shù)組名僅代表數(shù)組的首地址，所以當(dāng)指針作為函數(shù)的參數(shù)傳遞時(shí)，實(shí)際上是將數(shù)組的首地址傳給了形式參數(shù)(并不是把數(shù)組的值傳給了形式參數(shù))。這樣，實(shí)參數(shù)組和形參數(shù)組占有同一段內(nèi)存空間，改變形參數(shù)組元素的值也將使實(shí)參數(shù)組元素發(fā)生變化。

程序2－1定義了5個(gè)元素的一維整型數(shù)組，main函數(shù)調(diào)用函數(shù)f，函數(shù)f輸出每個(gè)數(shù)組元素，并對(duì)每個(gè)數(shù)組元素加2。由于參數(shù)p是指向整數(shù)的指針，main函數(shù)中以數(shù)組one和數(shù)組長(zhǎng)度5為實(shí)參調(diào)用之，其運(yùn)行結(jié)果為：*(p+i)：01234*(one+i)：23456

可以看到，在函數(shù)f中對(duì)數(shù)組元素都作了加2的修改，使實(shí)參數(shù)組one也隨之改變?！境绦?－1】數(shù)組和指針。intone[5]={0,1,2,3,4};voidf(int*p,intn){inti;printf("\n*(p+i)：");for(i=0;i<n;i++){printf("%d",*(p+i));*(p+i)+=2;}}voidmain(){inti;f(one,5);printf("\n*(one+i)：\n");for(i=0;i<5;i++) printf("%d",*(one+i));}

3.指向結(jié)構(gòu)的指針上面提到了指向數(shù)組的指針。指向數(shù)組的指針類型實(shí)際上是指向數(shù)組元素類型的指針類型，同樣我們也可以定義指向結(jié)構(gòu)的指針類型。前面介紹了結(jié)構(gòu)和結(jié)構(gòu)類型。一個(gè)結(jié)構(gòu)的成員可以是多種類型的，也可以是指針類型的。這個(gè)指針可以指向其他結(jié)構(gòu)類型，也可以指向它所在的結(jié)構(gòu)類型。例如，

structnode{ intData; structnode*Link;};Link是結(jié)構(gòu)的成員名，它是指向structnode類型的指針。當(dāng)一個(gè)結(jié)構(gòu)中有一個(gè)或多個(gè)成員是指向它自身的指針時(shí)，稱這種結(jié)構(gòu)為自引用結(jié)構(gòu)(self-referentialstructure)。定義一個(gè)指向結(jié)構(gòu)的指針可以使用定義語(yǔ)句：structnode*p；。使用typedef定義指向結(jié)構(gòu)的指針類型的方法更靈活。例如：

typedefstructnode*Nodeptr;typedefstructnode{ intData; NodeptrLink;}Node;

4.動(dòng)態(tài)存儲(chǔ)分配

C語(yǔ)言中的變量可分為兩類：靜態(tài)變量(staticvariable)和動(dòng)態(tài)變量(dynamicvariable)。我們這里所說(shuō)的靜態(tài)變量，與C語(yǔ)言中由關(guān)鍵字static定義的靜態(tài)存儲(chǔ)類變量是兩個(gè)不同的概念。靜態(tài)變量是指在書寫程序時(shí)定義和命名的變量，它的存儲(chǔ)空間在它所在的程序一開始運(yùn)行時(shí)便存在。C語(yǔ)言的存儲(chǔ)類為static的變量是在定義該變量的函數(shù)中使用的，在程序整個(gè)運(yùn)行期間都不釋放。動(dòng)態(tài)變量在程序編譯時(shí)并不存在，只在程序運(yùn)行時(shí)才創(chuàng)建，所以在程序書寫時(shí)無(wú)法事先對(duì)其命名，因而，動(dòng)態(tài)變量只能通過(guò)指針訪問(wèn)。

如同其他變量一樣，動(dòng)態(tài)變量是具有類型的。動(dòng)態(tài)存儲(chǔ)分配(dynamicmemoryallocation)是指在運(yùn)行時(shí)根據(jù)程序要求為變量等對(duì)象分配存儲(chǔ)空間的方法。C語(yǔ)言使用一種稱為堆(heap)的數(shù)據(jù)結(jié)構(gòu)，在運(yùn)行時(shí)為動(dòng)態(tài)變量分配存儲(chǔ)空間。我們可以使用C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc和free動(dòng)態(tài)地創(chuàng)建和撤銷一個(gè)動(dòng)態(tài)變量。如下面的語(yǔ)句：

p=(Node*)malloc(sizeof(Node));if(IS_FULL(p)){fprintf(stderr,"Thememenyisfull\n");exit(1);}其中，IS_FULL(p)可由宏定義#defineIS_FULL(ptr)(!(ptr))來(lái)定義，stderr是出錯(cuò)信息輸出流文件，語(yǔ)句exit(1);終止程序執(zhí)行。上述程序段創(chuàng)建一個(gè)Node類型動(dòng)態(tài)變量，并將它的地址賦給指針變量p。換句話說(shuō)，p指向所創(chuàng)建的動(dòng)態(tài)變量。其中，sizeof運(yùn)算符計(jì)算Node類型的結(jié)構(gòu)所需的存儲(chǔ)空間的大小，從而確定應(yīng)當(dāng)分配給新變量的存儲(chǔ)空間的大小。如果內(nèi)存耗盡，則malloc函數(shù)返回NULL，表示內(nèi)存已不足，程序終止運(yùn)行。當(dāng)一個(gè)動(dòng)態(tài)變量不再需要時(shí)，可以使用函數(shù)調(diào)用free(p)回收該變量所占用的空間。注意，執(zhí)行free函數(shù)后，指針變量p的值是無(wú)定義的?！境绦?－2】靜態(tài)變量和動(dòng)態(tài)變量。voidmain(){charc='a';char*p=&c;int*y;y=(int*)malloc(sizeof(int));*y=10;printf("\n%d,%c",*y,*p);free(y);}圖2－4靜態(tài)變量和動(dòng)態(tài)變量

使用指針使C語(yǔ)言程序設(shè)計(jì)十分靈活和高效，但如果使用不當(dāng)會(huì)帶來(lái)很大的程序隱患。空指針NULL不指向任何實(shí)際的對(duì)象，間接引用一個(gè)空指針，常會(huì)帶來(lái)不可預(yù)期的結(jié)果。另外一種值得注意的情況是，如圖2－4例子所示，y指向一個(gè)動(dòng)態(tài)變量，在使用free(y)語(yǔ)句釋放了它所指向的動(dòng)態(tài)變量后，y成為不確定的指針，那么在再次對(duì)y賦適當(dāng)值之前不應(yīng)使用y的值。2.3.2單鏈表上面我們回顧了與C語(yǔ)言的指針有關(guān)的規(guī)則。指針類型是構(gòu)造鏈接存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，在基于指針的鏈接結(jié)構(gòu)中，單鏈表(singlylinkedlist)是最基本的。在單鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：存放元素的域Element和存放指向后繼結(jié)點(diǎn)的指針域Link，如圖2－5(a)所示。圖2－5(c)是一個(gè)包含n個(gè)元素(a0,a1,…,an-1)的單鏈表結(jié)構(gòu)。我們稱單鏈表的第一個(gè)結(jié)點(diǎn)為起始結(jié)點(diǎn)，指向起始結(jié)點(diǎn)的指針為頭指針。圖中指針變量first為頭指針。頭指針為NULL的單鏈表稱為空表，這里我們使用電路的接地符號(hào)表示空指針值，如圖2－5(b)所示。尾結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，其指針域?yàn)镹ULL。圖2－5中，我們用一個(gè)圓表示指針變量，其實(shí)，它與Link域具有完全相同的數(shù)據(jù)類型。圖2－5單鏈表結(jié)構(gòu)

(a)結(jié)點(diǎn)結(jié)構(gòu)；(b)空表；(c)非空表

1.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)單鏈表的每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)具有如下定義的結(jié)構(gòu)類型：

typedefstructnode{TElement;structnode*Link;}Node;這里，我們定義了單鏈表的結(jié)點(diǎn)類型Node(結(jié)構(gòu)名為node)，它包括兩個(gè)域：元素域Element和指針域Link。這是一個(gè)自引用的結(jié)構(gòu)。

值得注意的是，我們使用了由用戶自定義的元素類型T。前面提到，在大多數(shù)情況下，本書中討論的一個(gè)抽象數(shù)據(jù)類型ADT代表一類具有相同結(jié)構(gòu)和相同運(yùn)算集的數(shù)據(jù)結(jié)構(gòu)，它的元素類型通常并不重要，即所謂類屬ADT。在C++、Ada等語(yǔ)言中提供了相應(yīng)的語(yǔ)言機(jī)制處理這一問(wèn)題，但C語(yǔ)言不允許在用戶自定義的數(shù)據(jù)類型中包含類型未確定的數(shù)據(jù)成分。在C語(yǔ)言環(huán)境中，我們這里使用的元素類型T必須由用戶在應(yīng)用時(shí)，用typedef語(yǔ)句定義為具體的類型。例如，我們可以將T定義成int類型，也可將其定義為如下的Entry類型。typedefstructentry{intKey;charData;}Entry;typedefTEntry;

為了對(duì)元素執(zhí)行輸入輸出操作，下面兩個(gè)運(yùn)算是有用的。這兩個(gè)運(yùn)算應(yīng)由用戶根據(jù)實(shí)際使用的元素類型實(shí)現(xiàn)，它們的作用由如下的運(yùn)算規(guī)范定義。(1)T*InputElement();。后置條件：已構(gòu)造一個(gè)類型為T的新元素對(duì)象，并賦以所需的元素值，返回新元素對(duì)象的地址。例如，可以從數(shù)據(jù)文件輸入新元素值，或從標(biāo)準(zhǔn)輸入設(shè)備鍵盤輸入新元素的值。(2)voidPrintElement(Te)。后置條件：輸出元素e。例如，可以將元素e輸出到指定磁盤文件，或由標(biāo)準(zhǔn)輸出設(shè)備顯示器輸出。程序2－3給出從鍵盤輸入元素，在屏幕顯示元素的函數(shù)實(shí)現(xiàn)。該程序是當(dāng)T為整型時(shí)，函數(shù)InputElement和PrintElement的一種可能的實(shí)現(xiàn)方法。【程序2－3】創(chuàng)建和顯示元素。

typedefintT;T*InputElement(){staticTa;scanf("%d",&a);return&a;}voidPrintElement(Tx){ printf("%d",x);}

借助InputElement，我們來(lái)實(shí)現(xiàn)構(gòu)造單鏈表的新結(jié)點(diǎn)的函數(shù)NewNode。在應(yīng)用程序中，可能需要以多種方式構(gòu)造新結(jié)點(diǎn)。程序2－4給出了三個(gè)構(gòu)造新結(jié)點(diǎn)的函數(shù)，其中：函數(shù)NewNode僅僅構(gòu)造一個(gè)新結(jié)點(diǎn)；函數(shù)NewNode1調(diào)用函數(shù)InputElement，允許用戶從鍵盤輸入元素值構(gòu)造新結(jié)點(diǎn)；函數(shù)NewNode2使用由用戶提供的元素值x來(lái)構(gòu)造新結(jié)點(diǎn)。函數(shù)NewNode、NewNode1和NewNode2均返回指向新結(jié)點(diǎn)的指針。這里，我們假定元素類型T是可以整體賦值的類型?！境绦?－4】構(gòu)造新結(jié)點(diǎn)。#defineIS_FULL(ptr)(!(ptr))Node*NewNode(){Node*p=(Node*)malloc(sizeof(Node));if(IS_FULL(p)){ fprintf(stderr,"Thememeryisfull\n");exit(1);}p->Link=NULL;returnp;}Node*NewNode1(){Node*p=(Node*)malloc(sizeof(Node));if(IS_FULL(p)){fprintf(stderr,"Thememeryisfull\n");exit(1);}p->Element=*InputElement();p->Link=NULL;returnp;}Node*NewNode2(Tx){Node*p=(Node*)malloc(sizeof(Node));if(IS_FULL(p)){fprintf(stderr,"Thememeryisfull\n");exit(1);}p->Element=x;p->Link=NULL;returnp;}

2.單鏈表類型我們可以簡(jiǎn)單地將單鏈表類型List定義為

typedefNode*List;

這里，類型List是指向Node類型變量的指針類型。我們可以將圖2－5(c)中的first定義為L(zhǎng)ist類型，即Node*類型。

3.單鏈表的插入和刪除在單鏈表的指定結(jié)點(diǎn)(設(shè)由指針變量p指示)后面插入新結(jié)點(diǎn)(由q指示)的方法很簡(jiǎn)單，只需使用指針賦值語(yǔ)句q->Link=p->Link;和p->Link=q;，即修改兩個(gè)結(jié)點(diǎn)的指針域的值就可以了，如圖2－6所示。圖2－6單鏈表的插入

(a)插入前；(b)插入后

刪除操作如圖2－7所示。刪除p所指示的結(jié)點(diǎn)時(shí)，只需修改一個(gè)指針：q->Link=p->Link，但還需使用free(p)語(yǔ)句回收結(jié)點(diǎn)占用的空間。這里，結(jié)點(diǎn)*q是結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)(predecessor)。由此可見，在單鏈表中，為了刪除一個(gè)結(jié)點(diǎn)，我們必須知道它的前驅(qū)結(jié)點(diǎn)。圖2－7單鏈表的刪除

(a)刪除前；(b)刪除后

4.建立單鏈表定義了單鏈表的結(jié)點(diǎn)類型后，我們來(lái)設(shè)計(jì)創(chuàng)建單鏈表的函數(shù)。程序2－5是建立單鏈表的函數(shù)。由于元素類型是由用戶根據(jù)實(shí)際需要定義的，所以建立單鏈表需要使用NewNode2獲取元素值，構(gòu)造新結(jié)點(diǎn)。BuildList函數(shù)在while循環(huán)每一次迭代時(shí)詢問(wèn)是否還需輸入下一個(gè)元素，在得到用戶的肯定后調(diào)用NewNode1函數(shù)建立一個(gè)新結(jié)點(diǎn)，由p指示。新結(jié)點(diǎn)被加到表的已建成部分的尾部。指針r始終指向當(dāng)前表的最后一個(gè)結(jié)點(diǎn)。圖2－8顯示了建表過(guò)程中在已建表的尾部(由指針r指示)添加一個(gè)新結(jié)點(diǎn)*p的操作。函數(shù)tolower將字母轉(zhuǎn)換成小寫字母，其函數(shù)原型在頭文件ctype.h中?！境绦?－5】建立單鏈表。ListBuildList(){Node*p,*r=NULL,*first=NULL;charc;printf("Anotherelement?y/n");while((c=getchar())=='\n');while(tolower(c)!='n'){p=NewNode1();if(first!=NULL)r->Link=p;elsefirst=p;r=p;printf("Anotherelement?y/n");while((c=getchar())=='\n');}returnfirst;}圖2－8建立單鏈表(a)插入前；(b)新結(jié)點(diǎn)*p；(c)插入后

5．輸出單鏈表輸出單鏈表中元素的運(yùn)算實(shí)現(xiàn)起來(lái)相對(duì)容易一些。程序2－6調(diào)用函數(shù)PrintElement顯示單鏈表。對(duì)于不同的元素類型用戶可以設(shè)計(jì)不同的PrintElement函數(shù)，實(shí)現(xiàn)元素輸出。【程序2－6】輸出單鏈表。voidPrintList(Listfirst){printf("\nThelistcontains:\n");for(;first;first=first->Link)PrintElement(first->Element);printf("\n\n");}

6.清空單鏈表單鏈表是由動(dòng)態(tài)變量構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，當(dāng)需要?jiǎng)h除單鏈表中全部元素而清空單鏈表時(shí)，必須使用free語(yǔ)句逐一釋放每個(gè)結(jié)點(diǎn)占用的空間，回收后備用。如果我們只是簡(jiǎn)單地將單鏈表的頭指針置成NULL，單鏈表的結(jié)點(diǎn)占用的空間并沒有回收，然而此時(shí)已無(wú)法再訪問(wèn)這些結(jié)點(diǎn)，這些結(jié)點(diǎn)便成為垃圾(garbage)。這是對(duì)內(nèi)存的浪費(fèi)，嚴(yán)重時(shí)會(huì)影響程序的正常運(yùn)行。所以動(dòng)態(tài)變量不用時(shí)應(yīng)注意回收。程序