山大《數(shù)據(jù)結(jié)構(gòu)》講義

1、第一章緒論內(nèi)容概述數(shù)據(jù)結(jié)構(gòu)研究非數(shù)值數(shù)據(jù)之間的邏輯關(guān)系，合理組織它們，存儲到計算機(jī)內(nèi)，并依此實(shí)現(xiàn)操作數(shù)據(jù)的算法。本章首先從數(shù)據(jù)結(jié)構(gòu)的實(shí)例入手，分析了數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容；然后介紹數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型等數(shù)據(jù)結(jié)構(gòu)所涉及的基本概念，并以抽象數(shù)據(jù)類型為工具結(jié)合實(shí)例描述了數(shù)據(jù)結(jié)構(gòu)的表示與實(shí)現(xiàn)；最后介紹算法和算法的評價。本章難點(diǎn)和重點(diǎn)數(shù)據(jù)結(jié)構(gòu)的理解、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法的評價。思考1你對數(shù)據(jù)結(jié)構(gòu)的概念是如何理解？2數(shù)據(jù)邏輯結(jié)構(gòu)包括哪些類型？3為什么采用抽象數(shù)據(jù)類型描述數(shù)據(jù)結(jié)構(gòu)？4算法分析的目的是什么？案例分析1物流活動中貨車的抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)。第一節(jié)數(shù)據(jù)結(jié)構(gòu)實(shí)例為了更好

2、地理解數(shù)據(jù)結(jié)構(gòu)，本節(jié)從飛機(jī)訂票系統(tǒng)、物料清單、郵遞員送信等三個實(shí)際應(yīng)用入手分析了數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。1.線性結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系例1-1飛機(jī)訂票系統(tǒng)。應(yīng)用本系統(tǒng)進(jìn)行飛機(jī)訂票的過程中，客戶首先通過查詢航班信息表，并根據(jù)自己的情況按照起始城市和起降時間查找具體航班，然后，根據(jù)票價和座位情況，確定航班號，進(jìn)而進(jìn)行訂票操作。訂票操作中，客戶輸入姓名、證件號等信息后，選擇航班、訂票數(shù)，即可完成訂票。在此類系統(tǒng)中，計算機(jī)處理的對象之間通常存在著一種最簡單的線性關(guān)系，如圖1-1所示，即各個數(shù)據(jù)元素按照一定的順序線性排列，我們把這類結(jié)構(gòu)稱為線性數(shù)據(jù)結(jié)構(gòu)。該類線性數(shù)據(jù)結(jié)構(gòu)還可應(yīng)用于其他各種訂票系統(tǒng)、學(xué)籍管理

3、、選課系統(tǒng)、網(wǎng)上購物、倉庫賬目管理等。2.樹結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系例1-2物料清單（BOM）。物料清單BOM（BillofMaterial）是一種描述配套件結(jié)構(gòu)的零件表，其中包括所有子件、零件、原材料的清單，以及制造一個配件所需要的所有物料的數(shù)量。BOM是制造業(yè)信息系統(tǒng)的一個核心部件。如果我們將產(chǎn)品的配件按照線性數(shù)據(jù)結(jié)構(gòu)羅列表示，如圖1.2（a）所示，將不利于產(chǎn)品的設(shè)計和改進(jìn)；當(dāng)把產(chǎn)品的配件按照一定的層次進(jìn)行表示時，如圖1.2（b）所示，形成的結(jié)構(gòu)圖像一棵倒長的樹，“樹根”是該產(chǎn)品，而所有的“葉子”就是產(chǎn)品對應(yīng)的零配件。這時的產(chǎn)品配件結(jié)構(gòu)鮮明，易于分析和應(yīng)用。我們把此類存儲產(chǎn)品配件資料的數(shù)據(jù)

4、結(jié)構(gòu)稱為“樹”結(jié)構(gòu)。該產(chǎn)品結(jié)構(gòu)圖不僅可以應(yīng)用于產(chǎn)品的設(shè)計和改進(jìn)，還可應(yīng)用到生產(chǎn)管理中。當(dāng)接收到客戶訂單時，查詢每個結(jié)點(diǎn)即配件是否有貨，即進(jìn)行“遍歷”操作。如果無貨，對于本廠生產(chǎn)的配件，制訂出生產(chǎn)作業(yè)計劃；對于外購的配件，向供貨商發(fā)出訂單。如果把圖1.2（b）的“樹”結(jié)構(gòu)轉(zhuǎn)換成圖1.2（c）的結(jié)構(gòu)，即每個結(jié)點(diǎn)只有不多于兩個分叉，轉(zhuǎn)換后的結(jié)構(gòu)可稱為“二叉樹”，該“樹”的結(jié)點(diǎn)的增加、刪除、修改、遍歷等操作的相應(yīng)算法將比非“二叉樹”的算法更加簡單和成熟。3.算法和算法的評價例1-3郵遞員送信問題。如圖1.3（a）所示，現(xiàn)在郵遞員從郵局出發(fā)，向以下幾個地點(diǎn)2、3、4送信。要求選擇一條路線，從郵局出發(fā)，經(jīng)

5、過每個地點(diǎn)，最終回到郵局，并且路線長度最短。該問題描述的是經(jīng)典的“中國郵路”問題，通常這類郵件發(fā)送問題的數(shù)學(xué)模型是一種稱為“圖”的數(shù)據(jù)結(jié)構(gòu)。在此例中，如圖1.3（b）所示，可以通過一個頂點(diǎn)表示一個地點(diǎn)，通過兩點(diǎn)之間的連線表示兩地之間的通路。此外，在諸如城市物流配送、建筑網(wǎng)絡(luò)布線、城市道路規(guī)劃等問題中，均會用到“圖”數(shù)據(jù)結(jié)構(gòu)。第二節(jié)基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素是更深入理解數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)概念。數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)是計算機(jī)處理非數(shù)值問題中算法設(shè)計與實(shí)現(xiàn)的依據(jù)。抽象數(shù)據(jù)類型是數(shù)據(jù)結(jié)構(gòu)的描述框架，抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)也是本節(jié)需要解決的問題。1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象數(shù)據(jù)（Data）

6、是人們利用各種符號對客觀事物及其活動進(jìn)行的抽象描述。從計算機(jī)程序設(shè)計的角度來講，數(shù)據(jù)則是計算機(jī)程序加工和處理的“原料”和對象。例如，一個簡單的數(shù)值計算程序所使用的數(shù)據(jù)是一些整數(shù)和實(shí)數(shù)；一個編譯程序所加工、處理的數(shù)據(jù)則是用某種高級語言編寫的源程序。就我們本教材所討論的內(nèi)容而言，我們可做如下定義：數(shù)據(jù)是描述客觀事物用到的數(shù)、字符以及所有能輸入到計算機(jī)中并能被計算機(jī)處理的符號的集合，它是計算機(jī)程序使用、加工的原料和輸出的結(jié)果。一般把數(shù)據(jù)分為數(shù)值性數(shù)據(jù)和非數(shù)值數(shù)據(jù)兩類。數(shù)值性數(shù)據(jù)常用于科學(xué)計算和商業(yè)事務(wù)處理等，包括整數(shù)、實(shí)數(shù)、復(fù)數(shù)、雙精度數(shù)；非數(shù)值數(shù)據(jù)一般是指字符、聲音、圖像、文字等數(shù)據(jù)。數(shù)據(jù)元素（D

7、ataElement）是數(shù)據(jù)整體中相對獨(dú)立的基本單位，通常作為一個整體在計算機(jī)程序中進(jìn)行處理。針對處理具體問題的不同，數(shù)據(jù)元素可以是從簡單的數(shù)、字符到復(fù)雜的對象（例如C語言中的結(jié)構(gòu)體類型），只要它們能被計算機(jī)接受并處理，包括圖形、聲音等。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)的最小單位，例如銀行儲蓄業(yè)務(wù)管理系統(tǒng)中處理的數(shù)據(jù)元素可包括如下數(shù)據(jù)項：賬號，姓名，存入，支出，余額，利息；學(xué)生檔案管理系統(tǒng)中的數(shù)據(jù)項常常是：學(xué)號，姓名，性別，年齡，籍貫，學(xué)習(xí)成績。數(shù)據(jù)對象（DataObject）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是集合N=0，1，2，字母字符數(shù)據(jù)對象

8、是集合C=A，B，Z。2.數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)現(xiàn)實(shí)世界中，客觀事物都是相互聯(lián)系的，所以數(shù)據(jù)之間也必然存在著聯(lián)系。數(shù)據(jù)結(jié)構(gòu)（DataStructure）就是指數(shù)據(jù)元素及其相互之間的關(guān)系。數(shù)據(jù)元素之間的相互聯(lián)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖結(jié)構(gòu)4類基本結(jié)構(gòu)，見圖1.4。（1）集合：數(shù)據(jù)元素間的關(guān)系同屬一個集合，除此之外，別無其它關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的元素間存在一對一的關(guān)系。（3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的元素間存在一對多的關(guān)系。（4）圖（網(wǎng)狀）結(jié)構(gòu)：結(jié)構(gòu)中的元素間存在多對多的關(guān)系。在上節(jié)中，我們已經(jīng)看到了分別

9、為線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的三個例子。為了更確切地描述數(shù)據(jù)的邏輯結(jié)構(gòu)，通常采用二元組表示數(shù)據(jù)結(jié)構(gòu)：Data_Structure=(D,S)其中：D是數(shù)據(jù)元素的有限集合，S是D上關(guān)系的有限集合。下面結(jié)合上節(jié)中的具體例子進(jìn)行說明。例1-4在例1-1的飛機(jī)訂票系統(tǒng)中，定義一種數(shù)據(jù)結(jié)構(gòu)為：Linearity=(Name,Relation)，其中Name=丁琳,張偉,李明,王強(qiáng)Relation=，這是按照航班號的大小順序排列的線性關(guān)系。對應(yīng)的圖形如圖1.5所示。例1-5在例1-2的物料清單結(jié)構(gòu)中，定義一種數(shù)據(jù)結(jié)構(gòu)為：Tree=(Accessory,Relation)，其中Accessory=a,d,f,

10、hRelation=,A，f,A，h對應(yīng)的圖形如圖1.6所示。數(shù)據(jù)邏輯結(jié)構(gòu)和數(shù)據(jù)存儲結(jié)構(gòu)我們利用計算機(jī)解決問題，就需要在計算機(jī)內(nèi)部組織存放數(shù)據(jù)。數(shù)據(jù)在計算機(jī)內(nèi)組織存放的方式就稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。在計算機(jī)中存儲數(shù)據(jù)時，不僅要存儲數(shù)據(jù)本身，還要存儲數(shù)據(jù)之間的關(guān)系（即邏輯結(jié)構(gòu)）。我們應(yīng)當(dāng)根據(jù)具體問題，對于某一給定的抽象數(shù)據(jù)結(jié)構(gòu)，選擇一種恰當(dāng)?shù)呐c其對應(yīng)的數(shù)據(jù)存儲結(jié)構(gòu)，這一過程稱為抽象數(shù)據(jù)結(jié)構(gòu)到具體存儲結(jié)構(gòu)的映象。在計算機(jī)中，表示信息的最小單位是二進(jìn)制數(shù)的一位，稱為位（bit）。一個由若干位組合而成的位串稱為元素（Element）或結(jié)點(diǎn)（Node），用它來表示數(shù)據(jù)元素，它是數(shù)據(jù)元素在計算機(jī)中的

11、映像。存儲結(jié)構(gòu)可以分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩類。順序存儲結(jié)構(gòu)是利用連續(xù)的存儲單元來依次存放邏輯上相鄰的數(shù)據(jù)元素，這樣通過元素在存儲器中的相對位置反映數(shù)據(jù)元素之間的關(guān)系。如圖1.7(a)，某個姓名集合（李帥、張偉、馬亮、劉源），“李帥”和“張偉”在邏輯上的關(guān)系是相鄰的，這兩個元素的存儲位置也是相鄰的。鏈?zhǔn)酱鎯Y(jié)構(gòu)對應(yīng)的存儲空間不必是連續(xù)的存儲單元或不必按數(shù)據(jù)元素的邏輯關(guān)系依次存儲它們，它是通過指示出數(shù)據(jù)元素存儲地址的指針反映元素之間的關(guān)系。如圖1.7(b)，數(shù)據(jù)元素“馬亮”的指針指向數(shù)據(jù)元素“劉源”的存儲位置，這意味著，在邏輯關(guān)系上“馬亮”和“劉源”是相鄰的。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)密切相

12、關(guān)，任何一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)則取決于采用的存儲結(jié)構(gòu)。1.抽象數(shù)據(jù)類型數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱，它描述了數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)及允許施加的操作。數(shù)據(jù)類型可以分為簡單類型和結(jié)構(gòu)類型兩類。簡單類型的值是不可分解的，通常只作為整體使用，如一個整數(shù)、實(shí)數(shù)、字符等。結(jié)構(gòu)類型由若干簡單類型數(shù)據(jù)或結(jié)構(gòu)類型數(shù)據(jù)按照一定的規(guī)則構(gòu)造而成，是可以分解的，它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。抽象數(shù)據(jù)類型（ADT，AbstractDataType）由具有一定關(guān)系的一組數(shù)據(jù)和定義在該組數(shù)據(jù)上的操作組成。抽象數(shù)據(jù)類型的定義一般包括數(shù)據(jù)定

13、義和操作定義兩個部分。一個含抽象數(shù)據(jù)類型的模塊通常包含定義、表示和實(shí)現(xiàn)3個部分。抽象數(shù)據(jù)類型為我們提供了一個描述數(shù)據(jù)結(jié)構(gòu)的架構(gòu)，在本書以后各章的內(nèi)容中，我們均采用抽象數(shù)據(jù)類型對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行描述。抽象數(shù)據(jù)類型不僅包含一般數(shù)據(jù)類型的概念，還包括用戶自定義的數(shù)據(jù)類型。正如近代程序設(shè)計方法學(xué)中指出的，為了提高軟件的復(fù)用率，一個軟件系統(tǒng)的框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。也就是說，在構(gòu)成軟件系統(tǒng)的每個相對獨(dú)立的模塊上，定義一組數(shù)據(jù)和在該組數(shù)據(jù)上的操作，并在模塊內(nèi)部給出這些數(shù)據(jù)的表示及其操作的細(xì)節(jié)，同時在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。定義的數(shù)據(jù)類型的抽象層次越高，含有該抽象數(shù)據(jù)類

14、型的軟件模塊的復(fù)用程度也就越高。和數(shù)據(jù)結(jié)構(gòu)的形式定義相對應(yīng)，抽象數(shù)據(jù)類型的形式表示為：（D,S,O）其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集合，O是D上的基本操作集合。在本書中我們一般按如下格式定義抽象數(shù)據(jù)類型：ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：基本操作：ADT抽象數(shù)據(jù)類型名其中，用偽碼（PseudoCode，它是用介于自然語言和計算機(jī)語言之間的文字或符號來描述算法）描述數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義，用下列格式定義基本操作：基本操作名（參數(shù)表）初始條件：操作結(jié)果：基本操作的參數(shù)有賦值參數(shù)和引用參數(shù)這兩種參數(shù)。其中，賦值參數(shù)為操作提供輸入值；引用參數(shù)以&開頭，除提供輸入值之外，還將返回操作結(jié)果?！?/p>

15、初始條件”描述了操作執(zhí)行前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不能滿足初始條件，則操作失敗，返回相應(yīng)的出錯信息?！安僮鹘Y(jié)果”說明了操作正常完成后數(shù)據(jù)結(jié)構(gòu)的變化情況和應(yīng)返回的結(jié)果。2.抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)我們可以通過固有數(shù)據(jù)類型表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。由于我們是在高級程序設(shè)計語言的層次上來討論抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)，所以采用介于C語言和偽碼之間的類C語言作為數(shù)據(jù)結(jié)構(gòu)的描述工具，或用偽碼來描述一些只含抽象操作的抽象算法。這樣可以使數(shù)據(jù)結(jié)構(gòu)和算法的描述相對簡單和清晰，不必嚴(yán)格按照C語言的語法細(xì)節(jié)來描

16、述，但易于轉(zhuǎn)換成C或C+程序。本書所采用的類C語言是在精選C語言的核心集的基礎(chǔ)上作了修改和擴(kuò)充而成的，它增強(qiáng)了語言的描述功能。以下對其作簡要說明。（1）預(yù)定義常量和類型/函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE1#defineOVERFLOW2/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲結(jié)構(gòu)）用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。（3）基本操作的算法都用以下形

17、式的函數(shù)描述：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）/算法說明語句序列/函數(shù)名除了函數(shù)的參數(shù)需要說明類型，算法中使用的輔助變量可以不作變量說明，必要時對其作用給予注釋。一般而言，用a，b，c等表示數(shù)據(jù)元素，i，j，k等表示整型變量，p，q等表示指針變量。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時，函數(shù)定義為Status類型。除值調(diào)用方式以外，增加了C+語言的引用調(diào)用的參數(shù)傳遞方式，以便于算法的描述。注意在形式參數(shù)表中，以&打頭的參數(shù)即為引用參數(shù)。（4）賦值語句簡單賦值變量名=表達(dá)式；串聯(lián)賦值變量名1=變量名2=變量名k=表達(dá)式；成組賦值（變量名1,變量名k）=（表達(dá)式1,表達(dá)式k）；結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1

18、，值k）；變量名=表達(dá)式；變量名起始下標(biāo).終止下標(biāo)=變量名起始下標(biāo).終止下標(biāo)；交換賦值變量名變量名條件賦值變量名=條件表達(dá)式？表達(dá)式1：表達(dá)式2；（5）選擇語句條件語句1if（表達(dá)式）語句；條件語句2if（表達(dá)式）語句1；else語句2；開關(guān)語句1switch（表達(dá)式）case值1：語句序列1；break；case值n：語句序列n；break；default：語句序列n+1；開關(guān)語句2switchcase條件1：語句序列1；break；case條件n：語句序列n；break；default：語句序列n+1；（6）循環(huán)語句for語句for（賦初值表達(dá)式；條件表達(dá)式；修改表達(dá)式）語句；while語

19、句while（條件表達(dá)式）語句；do-while語句do語句序列；while（條件表達(dá)式）；（7）結(jié)束語句函數(shù)結(jié)束語句return表達(dá)式；return；case結(jié)束語句break；異常結(jié)束語句exit（異常代碼）；（8）輸入和輸出語句輸入語句scanf（格式串，變量1，變量n）；輸出語句printf（格式串，表達(dá)式1，表達(dá)式n）；通常省略格式串。（9）注釋單行注釋/文字序列（10）邏輯運(yùn)算約定與運(yùn)算&：對于A&B，當(dāng)A的值為零時，不再對B求值。或運(yùn)算|：對于A|B，當(dāng)A的值為非零時，不再對B求值。下面看一個簡單的例子。例1-6在物流活動中，經(jīng)常應(yīng)用到貨車進(jìn)行運(yùn)輸。一般貨車每次運(yùn)輸不止一種貨物，

20、每種貨物都有對應(yīng)的數(shù)量。在進(jìn)行裝貨、卸貨等操作的時候，需要根據(jù)各種貨物的變化情況修改其種類和數(shù)量。因此，我們可以把貨車定義為一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分包括貨車車廂里的貨物種類和數(shù)量，操作部分包括初始化貨車、裝貨、卸貨等。假設(shè)給定一個三廂貨車用SET表示，車廂用g1，g2和g3表示，每個車廂只能裝載一種貨物，貨物種類由小寫字母a，b，c標(biāo)記，并注明每種貨物的數(shù)量，如圖1.8所示。抽象數(shù)據(jù)類型ADTTruck的定義ADTTruck數(shù)據(jù)對象：D=g1,g2,g3|g1,g2,g3SET數(shù)據(jù)關(guān)系：R=,基本操作：InitTruck(&T,v1,v2,v3)操作結(jié)果：創(chuàng)建貨車T，車廂g1、g2和g3分

21、別裝上數(shù)據(jù)為v1、v2和v3的貨物。DestroyTruck(&T)操作結(jié)果：貨車T被銷毀。GoodsGet(T,i,&e)初始條件：貨車T存在，1i3。操作結(jié)果：用e返回第i個車廂的貨物數(shù)據(jù)。GoodsChange(&T,i,e,&f)初始條件：貨車T存在，1i3。操作結(jié)果：卸下貨車T中第i個車廂的貨物，用f返回，并裝上數(shù)據(jù)為e的貨物。GoodsSort(&T)初始條件：貨車T存在。操作結(jié)果：貨車T中貨物放入車廂g1g3的順序按貨物種類的字母順序排列。Max(T,&e)初始條件：貨車T存在。操作結(jié)果：用e返回貨車T的3個車廂中數(shù)量最大的貨物數(shù)據(jù)。Min(T,&e)初始條件：貨車T存在。操作結(jié)

22、果：用e返回貨車T的3個車廂中數(shù)量最小的貨物數(shù)據(jù)。ADTTruck/抽象數(shù)據(jù)類型ADTTruck的表示和實(shí)現(xiàn)typedefstruct/貨物數(shù)據(jù)，作為Truck的數(shù)據(jù)元素charkind;/產(chǎn)品種類intnum;/產(chǎn)品數(shù)量ElemType;typedefElemType*Truck;StatusInitTruck(Truck&T,ElemTypev1,ElemTypev2,ElemTypev3)/創(chuàng)建貨車T，依次設(shè)置T的三個車廂的初值為v1,v2和v3。T=(ElemType*)malloc(3*sizeof(ElemType);if(!T)exit(OVERFLOW);T0=v1;T1=v2

23、;T2=v3;/為每個元素賦值，即為每個車廂裝貨returnOK;/InitTruckStatusDestroyTruck(Truck&T)/銷毀貨車free(T);T=NULL;returnOK;/DestroyTruckStatusGoodsGet(TruckT,inti,ElemType&e)/得到第i個車廂的貨物數(shù)據(jù)if(i3)returnERROR;e=Ti1;returnOK;/GoodsGetStatusGoodsChange(Truck&T,inti,ElemTypee,ElemType&f)/卸下貨車T中第i個車廂的貨物并返回其數(shù)據(jù)，裝上數(shù)據(jù)為e的貨物。if(i3)retur

24、nERROR;f=Ti1;Ti1=e;returnOK;/GoodsChangeStatusGoodsSort(Truck&T)/貨車T中貨物放入車廂g1g3的順序按貨物種類由a到c排列if(T0.kindT1.kind)T0T1;if(T0.kindT2.kind)T0T2;if(T1.kindT2.kind)T1T2;returnOK;/GoodsSortStatusMax(TruckT,ElemType&e)/用e返回貨車T的3個車廂中數(shù)量最大的貨物數(shù)據(jù)。e=(T0.num=T1.num)?(T0.num=T2.num)?T0:T2):(T1.num=T2.num)?T1:T2);ret

25、urnOK;/MaxStatusMin(TruckT,ElemType&e)/用e返回貨車T的3個車廂中數(shù)量最小的貨物數(shù)據(jù)。e=(T0.num=T1.num)?(T0.num=T2.num)?T0:T2):(T1.num=T2.num)?T1:T2);returnOK;/Min第三節(jié)算法和算法的評價算法是解決特定問題的有限運(yùn)算序列。本節(jié)介紹算法具有的特性以及算法設(shè)計的優(yōu)劣評價指標(biāo)。1.算法的特性算法（Algorithm）是指完成一個任務(wù)所需要的具體步驟和方法的描述。一個算法可以采用文字?jǐn)⑹?，或用傳統(tǒng)的流程圖、NS圖等描述。一個算法應(yīng)具備以下五個特性：（1）有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)

26、束，每一步都在有窮時間內(nèi)完成。（2）確定性：算法中的每一步都必須有確切的含義，沒有二義性，對于相同的輸入只能得出相同的輸出。（3）可行性：算法中的每一步都能夠通過有限次的基本運(yùn)算在有限時間內(nèi)實(shí)現(xiàn)。（4）輸入：一個算法可以有零個或多個取自于某個特定對象集合的輸入量。（5）輸出：一個算法執(zhí)行結(jié)束后至少有一個輸出量。2.時間復(fù)雜性及其計算時間復(fù)雜度（TimeComplexity）。指一個算法運(yùn)行時間的相對量度。一個算法在計算機(jī)上從開始運(yùn)行到運(yùn)行結(jié)束花費(fèi)的時間約等于計算機(jī)執(zhí)行一種簡單操作的時間和算法中進(jìn)行簡單操作的次數(shù)的乘積。其中計算機(jī)執(zhí)行一種簡單操作的時間由計算機(jī)本身的硬、軟件環(huán)境決定，所以通常把算

27、法中包含簡單操作的次數(shù)作為算法的時間復(fù)雜度，用來衡量一個算法的運(yùn)行時間。算法中基本操作重復(fù)執(zhí)行的次數(shù)一般是問題規(guī)模的一個函數(shù)f(n)。我們在本書中不要求對時間復(fù)雜度進(jìn)行精確計算，只要大致計算出相應(yīng)的數(shù)量級即可。所以我們把算法的時間復(fù)雜度記作T(n)=O(f(n)。多數(shù)情況下最深層次循環(huán)內(nèi)的語句中的原操作，其重復(fù)執(zhí)行的次數(shù)和算法的執(zhí)行時間成正比，和包含它的語句的頻度相同。語句的頻度（FrequencyCount）是指該語句重復(fù)執(zhí)行的次數(shù)。例如，在下列程序段中：a)a=0;b=1;s=a+b;b)for(i=0;iN;c)for(i=0;iN;for(j=0;jN;cij=aij+bij;三個例子

28、都包含求和這個基本操作。其中，第一個例子含基本操作“s=a+b”的語句的頻度是1；第二個例子含基本操作“s+=bi”的語句的頻度是n；第三個例子含基本操作“cij=aij+bij”的語句的頻度是n2。以上三個例子的時間復(fù)雜度分別是O(1)，O(n)，O(n2)。其中，O(1)是常量階，表示算法的運(yùn)行時間不隨數(shù)據(jù)量n的改變而改變；O(n)是線性階，表示算法的運(yùn)行時間與n成正比；O(n2)是平方階，當(dāng)n加倍時算法的運(yùn)行時間將增長4倍。常見的算法的時間復(fù)雜度有O(1)，O(n)，O(n2)，O(lnn)，O(log2n)，O(2n)等形式。對于一個算法而言，最好情況的時間復(fù)雜度最容易求出，但通常實(shí)際

29、意義不大；最壞情況下的時間復(fù)雜度是估算算法執(zhí)行時間的一個上界，通過它可以估計算法運(yùn)行所需要的最長時間，并使用戶盡量避免出現(xiàn)這種情況；一般計算平均情況下的時間復(fù)雜度，需要概率統(tǒng)計和推導(dǎo)，但最具實(shí)際意義，可以確切的反映出運(yùn)行一個算法的平均快慢程度。第二章 線性表內(nèi)容概述線性結(jié)構(gòu)是每一個有意義的程序基本都使用的一種數(shù)據(jù)結(jié)構(gòu)，也是最簡單的數(shù)據(jù)結(jié)構(gòu)。那么，線性結(jié)構(gòu)如何表示與實(shí)現(xiàn)？本章從線性表的抽象數(shù)據(jù)類型定義、線性表的順序存儲及實(shí)現(xiàn)算法、線性表的鏈?zhǔn)酱鎯八惴▽?shí)現(xiàn)等三個方面闡述該問題。重點(diǎn)與難點(diǎn)重點(diǎn)為順序表和單鏈表的描述和插入、刪除運(yùn)算以及算法的效率分析。難點(diǎn)為單鏈表的插入、刪除運(yùn)算和鏈表的應(yīng)用。思考1

30、線性結(jié)構(gòu)與非線性結(jié)構(gòu)的根本區(qū)別是什么？2線性表有哪兩種存儲結(jié)構(gòu)，各有哪些優(yōu)缺點(diǎn)？3在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問任一結(jié)點(diǎn)？4當(dāng)對一個線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時，則采用何種存儲結(jié)構(gòu)為宜？當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則應(yīng)采用存儲結(jié)構(gòu)為宜？5在單鏈表中設(shè)置頭結(jié)點(diǎn)有何作用？6有一個單鏈表L（至少有1個結(jié)點(diǎn)），編寫一個算法將L逆置，即最后一個結(jié)點(diǎn)變成第一個結(jié)點(diǎn)，原來倒數(shù)第二個結(jié)點(diǎn)變成第二個結(jié)點(diǎn)，如此等等。7有一個單鏈表，其結(jié)點(diǎn)的元素值以非遞減有序排列，其結(jié)點(diǎn)的元素值有可能相同，編寫一個算法刪除單鏈表中多余的元素值相同的結(jié)點(diǎn)。第一節(jié)線性表的類型定義線性表示最常

31、用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。了解線性表的結(jié)構(gòu)特點(diǎn)、掌握線性表抽象類型定義是運(yùn)用線性結(jié)構(gòu)解決具體應(yīng)用問題的基礎(chǔ)。1.線性表定義、線性表的結(jié)構(gòu)特點(diǎn)所謂線性表（Linear_List），就是n（n0）個數(shù)據(jù)元素的集合a1,a2,an，這些數(shù)據(jù)元素之間有邏輯上的線性關(guān)系。線性表結(jié)構(gòu)的特點(diǎn)是：當(dāng)數(shù)據(jù)元素集合為非空時（即n0），則（1）有且僅有一個元素作為該結(jié)構(gòu)的第一個元素，即a1；（2）有且僅有一個元素作為該結(jié)構(gòu)的最后一個元素，即an；（3）當(dāng)1KN時，第k個元素ak有且僅有一個直接前驅(qū)，即ak-1，有且僅有一個直接后繼，即ak+1；另外，a1的后繼為a2，a1無前驅(qū)，an的前驅(qū)為an-1，an無后繼。具

32、有n個元素的線性表，n稱為線性表的長度。當(dāng)長度n為0時，線性表稱為空表。當(dāng)n0時，線性表中每個數(shù)據(jù)元素ai的位置稱為ai在線性表中的位序。線性表中每個數(shù)據(jù)元素在不同的情況下，可以是一個數(shù)或一個符號，也可以是一篇文章，甚至是圖片等其他更復(fù)雜的信息。例如，2到20的所有質(zhì)數(shù)：（2，3，5，7，11，13，17，19）是一個線性表，表中的數(shù)據(jù)元素是單個的整數(shù)。又如，一個班級的學(xué)生姓名集合：（李帥，張偉，王明）表中的數(shù)據(jù)元素是字符串。在第一章所舉的例子中，航班信息表為稍復(fù)雜的線性表，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（Item）組成。該線性表中的元素，常稱為數(shù)據(jù)記錄（DataRecord），簡稱記錄，它是

33、數(shù)據(jù)處理領(lǐng)域組織數(shù)據(jù)的基本單位。在日常生活中，學(xué)生學(xué)籍表、職工檔案表、圖書館書目表、醫(yī)院病歷表、庫存賬目表等都可稱為線性表。對于線性表，我們可以按照需求來增加或縮減它的長度，即進(jìn)行插入或刪除操作，也可以對表中的元素進(jìn)行查找或訪問等操作。2.線性表抽象類型定義線性表的抽象數(shù)據(jù)類型定義如下：ADTList數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n基本操作：CreatList(&L)操作結(jié)果：生成一個空的線性表L。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。ListInsert(&L,i,e)初始

34、條件：線性表L已存在，1iListLength(L)+1。操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1iListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。GetElem(L,i,&e)初始條件：線性表L已存在，1iListLength(L)。操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。LocateElem(L,e,compare()初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)。操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序

35、。若這樣的數(shù)據(jù)元素不存在，則返回值為0。ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。ADTList對于以上定義的抽象數(shù)據(jù)類型線性表，除了對其進(jìn)行的基本操作外，還可進(jìn)行一些更復(fù)雜的操作。如：對線性表進(jìn)行排序；在一個有序的線性表中插入元素；將兩個或兩個以上有序的線性表歸并成為一個有序的線性表等。這些復(fù)雜的操作可建立在基本操作的基礎(chǔ)上完成，即它們可通過調(diào)用基本操作來實(shí)現(xiàn)。若操作環(huán)境

36、或操作要求發(fā)生變化（例如，存儲結(jié)構(gòu)的變化），只需要修改基本操作的實(shí)現(xiàn)算法，而通過調(diào)用基本操作實(shí)現(xiàn)的其它算法則不必修改或只做很少的修改，這在一定程度上可以達(dá)到軟件模塊復(fù)用的目的。第二節(jié)線性表的順序表示和實(shí)現(xiàn)順序存儲結(jié)構(gòu)是線性表存儲結(jié)構(gòu)的選擇之一。當(dāng)線性表很少涉及插入和刪除操作時，優(yōu)先選擇順序結(jié)構(gòu)表示線性表。1、順序表數(shù)據(jù)類型定義順序表數(shù)據(jù)類型定義線性表的順序表示是利用一組地址連續(xù)的內(nèi)存空間依次存儲線性表的各個數(shù)據(jù)元素，即以元素在計算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。因為順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，所以通常利用C語言中動態(tài)分配的一組連續(xù)的存儲單元作為順序存儲結(jié)構(gòu)所

37、需要的存儲空間。首先定義一個指針表示存儲空間的基地址，為了保存線性表的長度需要定義一個整型變量，此外為了指示順序表當(dāng)前分配的存儲空間大小還需要定義一個整型變量，即當(dāng)前線性表的最大容量。所需要的具體數(shù)據(jù)類型描述如下：#defineMAXLEN100#defineLIST_INCREASE10/線性表存儲空間的動態(tài)分配增量typedefstructElemType*list;/線性表的存儲空間的基地址intlength;/線性表的當(dāng)前長度intmaxsize;/線性表當(dāng)前分配的存儲容量List_Sq;結(jié)構(gòu)體類型List_Sq用于實(shí)現(xiàn)線性表的動態(tài)分配順序存儲結(jié)構(gòu)。由于存儲空間為動態(tài)分配，在對線性表進(jìn)

38、行插入等操作時，若原有的存儲空間已滿而不能滿足進(jìn)一步操作，可進(jìn)行空間再分配，存儲空間的增加量用LIST_INCREASE表示。下面我們將給出各種典型的線性表操作的算法。2、順序表的生成算法生成線性表線性表的生成算法主要是為其準(zhǔn)備所需要的存儲空間（這可通過malloc函數(shù)動態(tài)申請空間實(shí)現(xiàn)），同時為參數(shù)L的成員L.list、L.length、L.maxsize賦以相應(yīng)的值。StatusCreatList_S(List_Sq&L)/構(gòu)造一個空的線性表LL.list=(ElemType*)malloc(MAXLEN*sizeof(ElemType);if(!L.list)exit(OVERFLOW);

39、/若存儲空間分配失敗，則退出程序L.length=0;/初始化表的長度為0L.maxsize=MAXLEN;/初始化表的存儲容量returnOK;/初始化成功/CreatList_S算法2-1線性表的生成算法3、返回線性表中第i個元素值的算法返回線性表中第i個元素值的算法在順序存儲線性表的連續(xù)單元中，第i個元素位于地址從L.list向后偏移i1的位置上（或處于L.list為基地址的連續(xù)單元中，下標(biāo)為i1的位置上），我們可直接通過下標(biāo)返回該元素的值。本算法的時間復(fù)雜度為O(1)。StatusGetElem_S(List_SqL,inti,ElemType&e)if(iL.length)retur

40、nERROR;/若i為無效值，返回錯誤e=L.listi1;/通過參數(shù)e返回第i個元素值returnOK;/GetElem_S算法2-2返回線性表中第i個元素的值4、線性表的插入算法在線性表的第i個位置插入元素該操作是指在線性表的第i個位置之前插入新的數(shù)據(jù)元素，插入后線性表的長度增加1個單位，插入的元素分別與原線性表的第i1個元素、第i個元素在邏輯上是相鄰的關(guān)系。由于順序存儲結(jié)構(gòu)是通過元素之間存儲位置的關(guān)系來反映邏輯關(guān)系，為了完成插入操作，滿足插入元素與其前驅(qū)元素、后繼元素之間的相鄰關(guān)系，我們需要把原線性表第i個到第n個元素依次向后移動一個單位。如圖2.2所示，在第4個和第5個元素之間插入元素

41、，需要將第5個到第7個元素依次向后移動一個單位。StatusListInsert_S(List_Sq&L,inti,ElemTypee)if(iL.length+1)returnERROR;/若i為無效值，返回錯誤if(L.length=L.maxsize)/若存儲容量已滿，則增加分配空間newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/若增加分配空間失敗，退出程序L.list=newbase;/新基址L.maxsize+=LIST_I

42、NCREASE;/存儲容量增加/ifq=&(L.listi1);/插入位置。q=L.list+i1;也可。for(p=&(L.listL.length1);p=q;p)/p=L.list+L.Length1;也可。*(p+1)=*p;/將插入元素位置之后的元素依次后移一個位置*q=e;/插入元素e+L.length;/線性表長度增加1returnOK;/插入操作成功/ListInsert_S算法2-3線性表的插入算法該算法的主要操作和影響算法效率的步驟為：將插入位置其后的元素依次向后移一個位置。執(zhí)行此算法時，假定線性表的長度為n，當(dāng)向第i個位置（1in+1）插入元素時，需要后移ni+1個元素，

43、所以進(jìn)行每次插入平均需要移動元素的次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。5、線性表的刪除算法刪除線性表中的第i個元素和插入操作的原理相同，當(dāng)刪除第i個元素之后，為了滿足原線性表第i+1個和第i1個元素之間的相鄰關(guān)系，我們需要將原第i+1個到第n個元素依次向前移動一個單位。如圖2.3所示，刪除第4個元素后，需要將第5個到第7個元素依次向前移動一個單位。StatusListDelete_S(List_Sq&L,inti,ElemType&e)if(iL.length)returnERROR;/若i為無效值，返回錯誤p=&(L.listi1);/被刪元素的位置，p=L.list+i1;也

44、可e=*p;/通過e返回被刪除的元素的值q=L.list+L.length1;/線性表的最后一個元素的位置for(+p;p=q;+p)*(p1)=*p;/被刪除元素之后的元素依次前移L.length;/線性表長度減少1returnOK;/刪除操作成功/ListDelete_S算法2-4線性表的刪除算法該算法的主要操作和影響算法效率的步驟是將所刪除元素位置后的數(shù)據(jù)元素依次向前移一個位置。執(zhí)行此算法時，假定線性表的長度為n，當(dāng)刪除第i個位置（1in）上的元素時，需要前移ni個元素，所以進(jìn)行每次刪除平均需要移動元素的次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。6、線性表中查找元素的算法在線性表

45、中查找滿足條件的元素本算法從線性表的第一個數(shù)據(jù)元素開始，依次和給定元素進(jìn)行比較，直至找到滿足條件的元素為止，若未找到，則函數(shù)返回0。intLocateElem_S(List_SqL,ElemTypee,Status(*compare)(ElemType,ElemType)i=1;p=L.list;/線性表的第一個元素while(iL.lengthif(i=L.maxsize)/若存儲容量已滿，則增加分配空間newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType);if(!newbase)exit(O

46、VERFLOW);/若增加分配空間失敗，退出程序L.list=newbase;/新基址L.maxsize+=LIST_INCREASE;/存儲容量增加/ifq=L.list;/起始位置while(q=*q)q+;/找到元素的適當(dāng)?shù)牟迦胛恢胒or(p=&(L.listL.length1);p=q;p)*(p+1)=*p;/將插入元素位置之后的元素依次后移一個位置*q=e;/插入元素e+L.length;/線性表長度增加1returnOK;/插入操作成功/List_Sorted_Insert_S算法2-6有序表的插入算法該算法的主要操作和影響算法效率的步驟為查找到新元素的插入位置，并將其后的元素依

47、次向后移一個位置。執(zhí)行此算法時，假定線性表的長度為n，則進(jìn)行查找元素插入位置時平均需要比較元素次數(shù)的數(shù)量級為n，當(dāng)插入元素時，需要后移ni+1個元素（若記插入位置為i），故此算法的時間復(fù)雜度為O(n)。8、有序表的合并算法有序表的合并在有序線性表的合并中，通過對兩個線性表的元素比較大小，選擇較小的元素插入。當(dāng)其中一個線性表的元素插入完成后，將另一個線性表的剩余元素直接插入即可。本算法適用于非遞減排列的線性表的合并。voidMergeList_S(List_SqLa,List_SqLb,List_Sq&Lc)/非遞減排列的有序線性表的合并pa=La.list;pb=Lb.list;Lc.maxs

48、ize=Lc.length=La.length+Lb.length;/新表的存儲容量為兩個表的長度之和pc=Lc.list=(ElemType*)malloc(Lc.maxsize*sizeof(ElemType);/為新表申請空間if(!Lc.list)exit(OVERFLOW);/若申請空間失敗，則退出程序pa_last=La.list+La.length1;pb_last=Lb.list+Lb.length1;/以表尾元素為標(biāo)記進(jìn)行合并while(pa=pa_last&pb=pb_last)/在未到達(dá)兩表的表尾時，按照元素大小順序進(jìn)行合并if(*pa=*pb)*pc+=*pa+;els

49、e*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;/插入剩余元素/MergeList_S算法2-7有序線性表的合并算法該算法的主要操作和影響算法效率的步驟為依次比較兩個線性表的元素，選擇符合條件的元素進(jìn)行插入，然后插入剩余元素。執(zhí)行此算法時，假定兩個線性表的長度分別為n和m，則進(jìn)行比較后插入元素平均需要執(zhí)行的次數(shù)的數(shù)量級為n+m，當(dāng)插入剩余元素時，需要執(zhí)行插入操作的數(shù)量級為n或m，故此算法的時間復(fù)雜度為O(n+m)。9、線性表排序算法線性表的排序本算法采用“起泡法”對線性表的數(shù)據(jù)元素進(jìn)行排序，排序方式同數(shù)組排序方式

50、類似。voidSortList_S(List_Sq&L)/排序成非遞減線性表，使用“起泡法”a=L.listfor(j=0;jL.LENGTH1;J+)for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;/SortList_S算法2-8線性表的排序算法該算法的主要操作和影響算法效率的步驟為起泡法的使用。執(zhí)行此算法時，假定線性表的長度為n，則通過兩層循環(huán)比較元素并且完成元素交換操作的數(shù)量級為n2，故此算法的時間復(fù)雜度為O(n2)。第三節(jié)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)具有邏輯上相鄰的元素在物理結(jié)構(gòu)上可不相鄰，靈活、簡單地插入或刪除結(jié)點(diǎn)而不必移動大量元素等特點(diǎn)。因此，當(dāng)線性表經(jīng)常

51、進(jìn)行插入和刪除操作時，應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示線性表。1、線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的數(shù)據(jù)類型定義線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的數(shù)據(jù)類型定義鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下特點(diǎn)：不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰；允許迅速簡單地插入或刪除結(jié)點(diǎn)，而不必移動大量元素；但只能順序存取而不能隨機(jī)存取線性表中任一元素。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可通過單鏈表來實(shí)現(xiàn)。此時，線性表中的每個元素對應(yīng)單鏈表中的一個結(jié)點(diǎn)，每個結(jié)點(diǎn)的數(shù)據(jù)域存儲線性表的數(shù)據(jù)元素，每個結(jié)點(diǎn)的指針域存儲其后繼元素所在結(jié)點(diǎn)的地址，可以通過每個結(jié)點(diǎn)的指針域訪問到其后繼結(jié)點(diǎn)，如圖2.4所示因此，單鏈表中每個結(jié)點(diǎn)都是由包含這個數(shù)據(jù)元素的信息和一個指示其直接后繼的指針組成的一個結(jié)

52、構(gòu)體類型，具體描述如下：typedefstructLNodeElemTypedata;structLNode*next;LNode,*List_Link;每個單鏈表的頭指針L是List_Link型的變量，指向鏈表中第一個結(jié)點(diǎn)。由表頭指針出發(fā)可以依次訪問到每個結(jié)點(diǎn)，存取相應(yīng)的數(shù)據(jù)元素值。線性表中數(shù)據(jù)元素間的線性關(guān)系都可以通過單鏈表中結(jié)點(diǎn)指針域的鏈接關(guān)系反映出來。當(dāng)L=NULL時，意味著所表示的線性表為“空”表，其長度n為“零”。2、單鏈表設(shè)置頭結(jié)點(diǎn)的作用為操作方便，在單鏈表的第一個結(jié)點(diǎn)之前，我們可附設(shè)一個結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息，頭

53、結(jié)點(diǎn)的指針域存儲指向第一個結(jié)點(diǎn)的指針（即第一個結(jié)點(diǎn)的存儲位置），如圖2.5所示。帶有頭結(jié)點(diǎn)的單鏈表將給我們提供操作上的方便。因為若無頭結(jié)點(diǎn)，則線性表中第一個結(jié)點(diǎn)的刪除、在第一個結(jié)點(diǎn)之前插入元素等操作將和其他結(jié)點(diǎn)相應(yīng)的操作有所不同。因此，為了操作的方便，以下介紹的單鏈表均為帶有頭結(jié)點(diǎn)的單鏈表。與順序存儲結(jié)構(gòu)不同，當(dāng)我們使用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表時，不需要考慮線性表的存儲容量，插入、刪除元素時，只需要申請或釋放線性表中結(jié)點(diǎn)的空間即可。下面我們將給出各種典型的線性表操作的算法。3、鏈?zhǔn)酱鎯Φ木€性表的生成算法生成線性表StatusCreatList_L(List_Link&L)L=(List_Link)

54、malloc(sizeof(LNode);/為頭結(jié)點(diǎn)申請空間if(!L)exit(OVERFLOW);/若申請空間失敗，則退出程序Lnext=NULL;returnOK;/CreatList_L算法2-9鏈?zhǔn)酱鎯Φ木€性表的生成算法4、鏈?zhǔn)酱鎯Y(jié)構(gòu)下返回線性表中第i個元素值的算法返回線性表中第i個元素的值在單鏈表中返回指定元素的值，和順序表不同，不能按下標(biāo)值來隨機(jī)存取其中的元素，只能順序存取，即要從頭結(jié)點(diǎn)開始，通過每個結(jié)點(diǎn)的指針域依次訪問其后繼結(jié)點(diǎn)，直到訪問到第i個結(jié)點(diǎn)為止。StatusGetElem_L(List_LinkL,inti,ElemType&e)p=Lnext;j=1;/p指向第一

55、個結(jié)點(diǎn)，j為計數(shù)器while(p&j/通過指針依次查找后繼結(jié)點(diǎn)，直到第i個元素或遍歷完線性表為止p=pnext;+j;if(!p|ji)returnERROR;/無第i個元素，即i線性表長度或idata;returnOK;/GetElem_L算法2-10返回線性表中第i個元素的值的算法該算法的主要操作和影響算法效率的步驟為通過順序訪問的方式查找到第i個元素的位置。進(jìn)行順序訪問元素的平均次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。5、鏈?zhǔn)酱鎯Φ木€性表的插入算法在線性表的第i個位置插入元素同返回第i個元素算法類似，都需要通過順序訪問結(jié)點(diǎn)的方式找到插入元素的前驅(qū)的位置，而后申請空間，插入結(jié)點(diǎn)。

56、如圖2.6，在數(shù)據(jù)元素a和數(shù)據(jù)元素b之間插入數(shù)據(jù)元素e，插入后e所在結(jié)點(diǎn)*s的指針域為其前驅(qū)結(jié)點(diǎn)*p的原來指針域的值，以實(shí)現(xiàn)*s結(jié)點(diǎn)的后繼為*p結(jié)點(diǎn)原來的后繼，同時*p的指針域指向結(jié)點(diǎn)*s。StatusListInsert_L(List_Link&L,inti,ElemTypee)p=L;j=0;/p指向頭結(jié)點(diǎn)，j為計數(shù)器while(p&jnext;+j;/到第i1個結(jié)點(diǎn)if(!p|ji1)returnERROR;s=(List_Link)malloc(sizeof(LNode);/為插入元素申請空間sdata=e;/插入元素snext=pnext;pnext=s;returnOK;/List

57、Insert_L算法2-11鏈?zhǔn)酱鎯Φ木€性表的插入算法該算法的主要操作和影響算法效率的步驟同返回第i個元素的算法相同，為查找到第i1個元素的位置，進(jìn)行順序訪問元素的平均次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。6、鏈?zhǔn)酱鎯Φ木€性表的刪除算法刪除線性表中的第i個元素刪除元素的操作是將要刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針值設(shè)置為其后繼結(jié)點(diǎn)的位置，然后釋放刪除結(jié)點(diǎn)的空間。如圖2.7所示，刪除結(jié)點(diǎn)a和結(jié)點(diǎn)c之間的結(jié)點(diǎn)b，則將結(jié)點(diǎn)a的指針指向結(jié)點(diǎn)b的后繼即結(jié)點(diǎn)c的位置，然后釋放結(jié)點(diǎn)b的空間。StatusListDelete_L(List_Link&L,inti,ElemType&e)p=L;j=0;/p指

58、向頭結(jié)點(diǎn)，j為計數(shù)器while(pnext&jnext;+j;/到第i1個結(jié)點(diǎn)if(!(pnext)|ji1)returnERROR;q=pnext;/完成刪除元素操作pnext=qnext;e=qdata;free(q);returnOK;/ListDelete_L算法2-12鏈?zhǔn)酱鎯Φ木€性表的刪除算法該算法的主要操作和影響算法效率的步驟同返回第i個元素的算法相同，為查找到第i1個元素的位置，進(jìn)行順序訪問元素的平均次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。7、在鏈?zhǔn)酱鎯Φ木€性表中查找元素的算法在線性表中查找滿足條件的元素同返回第i個元素算法類似，也需要通過順序訪問結(jié)點(diǎn)的方式找到滿足條

59、件的元素并返回該元素的位置。若直到線性表尾還未找到滿足條件的元素，則返回空。intLocateElem_L(List_LinkL,ElemTypee,Status(*compare)(ElemType,ElemType)p=Lnext;j=1;/p指向第一個結(jié)點(diǎn)，j為計數(shù)器while(p&(*compare)(pdata,e)p=pnext;+j;/若p-data、e滿足關(guān)系則compare為0/查找相匹配的結(jié)點(diǎn)if(!p)return0;elsereturnj;/LocateElem_L算法2-13在鏈?zhǔn)酱鎯Φ木€性表中查找元素的算法該算法的主要操作和影響算法效率的步驟同返回第i個元素的算法類

60、似，為查找到滿足條件的元素的位置，進(jìn)行順序訪問元素的平均次數(shù)的數(shù)量級為n，故此算法的時間復(fù)雜度為O(n)。8、鏈?zhǔn)酱鎯Φ挠行蚓€性表的插入算法有序表的插入有序表的插入也是通過順序訪問結(jié)點(diǎn)的方式找到滿足條件的插入位置，然后插入元素即可，插入過程中進(jìn)行的操作同普通插入操作相同。StatusList_Sorted_Insert_L(List_Link&L,ElemTypee)/非遞減排列的有序線性表的插入p=L;/p指向頭結(jié)點(diǎn)while(pnext&e=pnextdata)p=pnext;/或者找到表尾（此時pnext為0）/或者找到第一個比e的值大的數(shù)據(jù)元素結(jié)點(diǎn)：*（pnext）/對上述兩種情況，都