算法與數(shù)據(jù)結(jié)構(gòu)嚴蔚敏版WORD

《算法與數(shù)據(jù)結(jié)構(gòu)嚴蔚敏版WORD》由會員分享，可在線閱讀，更多相關(guān)《算法與數(shù)據(jù)結(jié)構(gòu)嚴蔚敏版WORD（152頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu)教材：數(shù)據(jù)結(jié)構(gòu)(C語言版)。嚴蔚敏，吳偉民 編著。清華大學(xué)出版社。參考文獻：1 數(shù)據(jù)結(jié)構(gòu) 。張選平，雷詠梅 編， 嚴蔚敏 審。 機械工業(yè)出版社。2 數(shù)據(jù)結(jié)構(gòu)與算法分析。Clifford A. Shaffer著， 張 銘，劉曉丹 譯。電子工業(yè)出版社。3 數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析(C語實言版)。李春葆。 清華大學(xué)出版社。4 數(shù)據(jù)結(jié)構(gòu)與算法。夏克儉 編著。國防工業(yè)出版社。說明: 除上面所介紹的外,數(shù)據(jù)結(jié)構(gòu)的參考文獻還有許多,在此就不一一列舉.另外, 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法分析這門課程時上機實驗用C語言實現(xiàn),基本的數(shù)學(xué)基礎(chǔ)來源于離散數(shù)學(xué),因此,必須熟練地掌握C語言程序設(shè)計與調(diào)試,離散數(shù)學(xué)的相關(guān)內(nèi)容

2、.第1章 緒 論目前，計算機已深入到社會生活的各個領(lǐng)域，其應(yīng)用已不再僅僅局限于科學(xué)計算，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計算領(lǐng)域。計算機是一門研究用計算機進行信息表示和處理的科學(xué)。這里面涉及到兩個問題：信息的表示，信息的處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復(fù)雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。編寫解決實際問題的程序的一般過程：如何用數(shù)據(jù)形式描述問題?即由問題抽象出一個適當?shù)臄?shù)學(xué)模型;問題所涉及的數(shù)據(jù)

3、量大小及數(shù)據(jù)之間的關(guān)系;如何在計算機中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系?處理問題時需要對數(shù)據(jù)作何種運算?所編寫的程序的性能是否良好?上面所列舉的問題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來回答。計算機求解問題的一般步驟1.1 數(shù)據(jù)結(jié)構(gòu)及其概念算法與數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)中的一門綜合性專業(yè)基礎(chǔ)課。是介于數(shù)學(xué)、計算機硬件、計算機軟件三者之間的一門核心課程，不僅是一般程序設(shè)計的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。41.1.1 數(shù)據(jù)結(jié)構(gòu)的例子姓名電話號碼陳海13612345588李四鋒13056112345。例1：電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄，它記錄了N個人的

4、名字和其相應(yīng)的電話號碼，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中ai, bi(i=1，2n) 分別表示某人的名字和電話號碼。 本問題是一種典型的表格問題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關(guān)系。表1-1 線性表結(jié)構(gòu)5要求設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。例2：磁盤目錄文件系統(tǒng)磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推：本問題是一種典型的樹型結(jié)構(gòu)問題，如圖1-1 ，數(shù)據(jù)與數(shù)據(jù)成一對

5、多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)樹形結(jié)構(gòu)。圖1-1 樹形結(jié)構(gòu)例3：交通網(wǎng)絡(luò)圖從一個地方到另外一個地方可以有多條路徑。本問題是一種典型的網(wǎng)狀結(jié)構(gòu)問題，數(shù)據(jù)與數(shù)據(jù)成多對多的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)。7其他例子：圖書館的書目檢索系統(tǒng)自動化問題教師資料檔案管理系統(tǒng)多叉路口交通燈的管理問題數(shù)據(jù)(Data) ：是客觀事物的符號表示。在計算機科學(xué)中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(Data Element) ：是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對

6、客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C=A,B,C, 。1.1.2 基本概念和術(shù)語8數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如圖1-3所示。 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關(guān)系。 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。 樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)

7、據(jù)元素之間存在多對多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義是一個二元組：Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例2：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B=（K，R）K=k1, k2, , k9R= ， 畫出這邏輯結(jié)構(gòu)的圖示，并確定那些是起點，那些是終點1.1.3 數(shù)據(jù)結(jié)構(gòu)的形式定義圖1-3 四類基本結(jié)構(gòu)圖1.1.4 數(shù)據(jù)結(jié)構(gòu)的存儲方式數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為定義的關(guān)系，這種自然或人為定義的 “關(guān)系”稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關(guān)系的表

8、示。元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈式存儲結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer )，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。例：設(shè)有數(shù)據(jù)集合A=3.0,2.3,5.0,-8.5,11.0 ，兩種不同的存儲結(jié)構(gòu)。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；鏈式結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面，一個算法的設(shè)計取決于所選定的邏輯結(jié)構(gòu)，而算

9、法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。在C語言中，用一維數(shù)組表示順序存儲結(jié)構(gòu)；用結(jié)構(gòu)體類型表示鏈式存儲結(jié)構(gòu)。12課堂教學(xué)時畫出實際的示意圖說明兩種存儲結(jié)構(gòu)問題.數(shù)據(jù)結(jié)構(gòu)的三個組成部分：邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間邏輯關(guān)系的描述D_S=（D，S）存儲結(jié)構(gòu)： 數(shù)據(jù)元素在計算機中的存儲及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作： 對數(shù)據(jù)要進行的運算。本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲結(jié)構(gòu)如圖1-4所示。數(shù)據(jù)類型(Data Type)：指的是一個值的集合和定義在該值集上的一組操作的總稱。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。 在C語言中數(shù)據(jù)類型有：基本類型和構(gòu)造類型。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)

10、類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。1.1.5 數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)的主要運算包括： 建立(Create)一個數(shù)據(jù)結(jié)構(gòu)； 消除(Destroy)一個數(shù)據(jù)結(jié)構(gòu)； 從一個數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個數(shù)據(jù)元素； 把一個數(shù)據(jù)元素插入(Insert)到一個數(shù)據(jù)結(jié)構(gòu)中； 對一個數(shù)據(jù)結(jié)構(gòu)進行訪問(Access)； 對一個數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進行修改(Modify)； 對一個數(shù)據(jù)結(jié)構(gòu)進行排序(Sort)； 對一個數(shù)據(jù)結(jié)構(gòu)進行查找(Search)。1.1.6 數(shù)據(jù)結(jié)構(gòu)的運算抽象數(shù)據(jù)類型(Abstract Data Type ，簡稱ADT)：是指一

11、個數(shù)學(xué)模型以及定義在該模型上的一組操作。ADT的定義僅是一組邏輯特性描述， 與其在計算機內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。1.2 抽象數(shù)據(jù)類型17說明： ADT和數(shù)據(jù)類型實質(zhì)上是一個概念.其區(qū)別是： ADT的范疇更廣,它不再局限于系統(tǒng)已定義并實現(xiàn)的數(shù)據(jù)類型，還包括用戶自己定義的數(shù)據(jù)類型。 ADT的定義是由一個值域和定義在該值域上的一組操作組成。包括定義，表示和實現(xiàn)三個部分。 ADT的最重要的特點是抽象和信息隱蔽。 抽象的本質(zhì)

12、就是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細節(jié)，使所設(shè)計的結(jié)構(gòu)更具有一般性，可以解決一類問題。信息隱蔽就是對用戶隱藏數(shù)據(jù)存儲和操作實現(xiàn)的細節(jié)，使用者了解抽象操作或界面服務(wù)，通過界面中的服務(wù)來訪問這些數(shù)據(jù)。例：整數(shù)的數(shù)學(xué)概念和對整數(shù)所能進行的運算構(gòu)成一個ADT ， C語言中的變量類型int就是對這個抽象數(shù)據(jù)類型的一種物理實現(xiàn)。ADT的一般定義形式是：ADT 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作： ADT 其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述?；静僮鞯亩x是：()初始條件： 操作結(jié)果： 18說明： ADT和數(shù)據(jù)類型實質(zhì)上是一個概念.其區(qū)別是： ADT的范疇更廣,它不再局限于系統(tǒng)已定義并實現(xiàn)的數(shù)據(jù)類型

13、，還包括用戶自己定義的數(shù)據(jù)類型。 ADT的定義是由一個值域和定義在該值域上的一組操作組成。包括定義，表示和實現(xiàn)三個部分。 ADT的最重要的特點是抽象和信息隱蔽。 抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細節(jié)，使所設(shè)計的結(jié)構(gòu)更具有一般性，可以解決一類問題。信息隱蔽就是對用戶隱藏數(shù)據(jù)存儲和操作實現(xiàn)的細節(jié)，使用者了解抽象操作或界面服務(wù)，通過界面中的服務(wù)來訪問這些數(shù)據(jù)。例：整數(shù)的數(shù)學(xué)概念和對整數(shù)所能進行的運算構(gòu)成一個ADT ， C語言中的變量類型int就是對這個抽象數(shù)據(jù)類型的一種物理實現(xiàn)。初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件;若不滿足，則操作失敗，返回相應(yīng)的出錯信息。操作結(jié)果

14、：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和 應(yīng)返回的結(jié)果。191.3.1 算法算法(Algorithm)：是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性 有窮性： 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。 確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。 可行性： 一個算法是能行的。即算法描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。1.3 算法分析初步20 輸入： 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。 輸出： 一個算法有一個或多

15、個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。一個算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計算機程序設(shè)計語言描述。算法和程序是兩個不同的概念。一個計算機程序是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn)。算法必須可終止意味著不是所有的計算機程序都是算法。在本門課程的學(xué)習(xí)、作業(yè)練習(xí)、上機實踐等環(huán)節(jié)，算法都用C語言來描述。在上機實踐時，為了檢查算法是否正確，應(yīng)編寫成完整的C語言程序。21評價一個好的算法有以下幾個標準 正確性(Correctness )： 算法應(yīng)滿足具體問題的需求。 可讀性(Readability)： 算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對算法

16、的理解和修改。 健壯性(Robustness)： 算法應(yīng)具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法應(yīng)能適當?shù)刈鞒龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。 通用性(Generality)： 算法應(yīng)具有一般性 ，即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立。1.3.2 算法設(shè)計的要求算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量。其方法通常有兩種：事后統(tǒng)計：計算機內(nèi)部進行執(zhí)行時間和實際占用空間的統(tǒng)計。問題：必須先運行依據(jù)算法編制的程序；依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。事前分析：求出該算法的一個時間界限函數(shù)。1.3.3 算法效率的度量 效率與存儲量需求

17、： 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關(guān)。與此相關(guān)的因素有：依據(jù)算法選用何種策略；問題的規(guī)模；程序設(shè)計的語言；編譯程序所產(chǎn)生的機器代碼的質(zhì)量；機器執(zhí)行指令的速度；撇開軟硬件等有關(guān)部門因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模（通常用n表示），或者說，它是問題規(guī)模的函數(shù)。算法分析應(yīng)用舉例算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間量度記作 T(n)=O(f(n)，稱作算法的漸近時間復(fù)雜度(Asymptotic Time complexity)，簡稱時間復(fù)雜度。一般地，常用最深層循環(huán)內(nèi)的語句中

18、的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示?！癘”的定義： 若f(n)是正整數(shù)n的一個函數(shù)，則 O(f(n)表示$ M0 ，使得當n n0時，| f(n) | M | f(n0) | 。表示時間復(fù)雜度的階有：O(1) ：常量時間階 O (n)：線性時間階O(n) ：對數(shù)時間階 O(nn) ：線性對數(shù)時間階O (nk)： k2 ，k次方時間階例 兩個n階方陣的乘法for(i=1，i=n; +i)for(j=1; j=n; +j) cij=0 ;for(k=1; k=n; +k)cij+=aik*bkj ; 由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為： nnn=n3時間復(fù)雜度為T(n)=O(

19、n3)例 +x; s=0 ;將x自增看成是基本操作，則語句頻度為，即時間復(fù)雜度為(1) 。如果將s=0也看成是基本操作，則語句頻度為，其時間復(fù)雜度仍為(1)，即常量階。例 for(i=1; i=n; +i) +x; s+=x ; 語句頻度為：2n，其時間復(fù)雜度為：O(n) ，即為線性階。例 for(i=1; i=n; +i)for(j=1; j=n; +j) +x; s+=x ; 語句頻度為：2n2 ，其時間復(fù)雜度為：O(n2) ，即為平方階。定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一個m次多項式，則A(n)=O(n m)例 for(i=2;i=n;+i)f

20、or(j=2;j=i-1;+j)+x; ai,j=x; 語句頻度為： 1+2+3+n-2=(1+n-2) (n-2)/2=(n-1)(n-2)/2 =n2-3n+2時間復(fù)雜度為O(n2)，即此算法的時間復(fù)雜度為平方階。一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：O(1)O(n)O(n)O(nn)O(n2)O(n3)指數(shù)時間的關(guān)系為：O(2n)O(n!)O(nn)當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。

21、因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例1：素數(shù)的判斷算法。Void prime( int n)/* n是一個正整數(shù) */ int i=2 ;while ( (n% i)!=0 & i*1.0sqrt(n) )printf(“&d 是一個素數(shù)n” , n) ;elseprintf(“&d 不是一個素數(shù)n” , n) ;嵌套的最深層語句是i+；其頻度由條件( (n% i)!=0 & i*1.0 sqrt(n) ) 決定，顯然i*1.01 & change; -i)f

22、or (j=0; jaj+1) aj aj+1 ; change=TURE ; 最好情況：0次最壞情況：1+2+3+n-1=n(n-1)/2平均時間復(fù)雜度為： O(n2)1.3.4 算法的空間分析空間復(fù)雜度(Space complexity) ：是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。記作： S(n)=O(f(n)其中： n為問題的規(guī)模(或大小)該存儲空間一般包括三個方面：指令常數(shù)變量所占用的存儲空間;輸入數(shù)據(jù)所占用的存儲空間;輔助(存儲)空間。一般地，算法的空間復(fù)雜度指的是輔助空間。一維數(shù)組an： 空間復(fù)雜度 O(n)二維數(shù)組anm： 空間復(fù)雜度 O(n*m)習(xí) 題 一

23、1 簡要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型。2 數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？3 數(shù)據(jù)結(jié)構(gòu)的主要運算包括哪些？4 算法分析的目的是什么？算法分析的主要方面是什么？5 分析以下程序段的時間復(fù)雜度，請說明分析的理由或原因。第2章 線性表線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中： 存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素； 存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素； 除第一個元素外，每個元素均有唯一一個直接前驅(qū)； 除最后一個元素外，每個元素均有唯一一個直接后繼

24、。2.1 線性表的邏輯結(jié)構(gòu)線性表(Linear List) ：是由n(n0)個數(shù)據(jù)元素(結(jié)點)a1，a2， an組成的有限序列。該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時，稱為空表。當n0時，將非空的線性表記作： (a1，a2，an)a1稱為線性表的第一個(首)結(jié)點，an稱為線性表的最后一個(尾)結(jié)點。2.1.1 線性表的定義a1，a2，ai-1都是ai(2in)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，an都是ai(1i n-1)的后繼，其中ai+1是ai的直接后繼。2.1.2 線性表的邏輯結(jié)構(gòu)線性表中的數(shù)據(jù)元素ai所代表的具體含義

25、隨具體應(yīng)用的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號。 線性表中的結(jié)點可以是單值元素(每個元素只有一個數(shù)據(jù)項) 。例1: 26個英文字母組成的字母表： (A，B，C、Z）例2 ： 某校從1978年到1983年各種型號的計算機擁有量的變化情況：(6，17，28，50，92，188）例3 ： 一副撲克的點數(shù) (2，3，4，J，Q，K，A) 線性表中的結(jié)點可以是記錄型元素，每個元素含有多個數(shù)據(jù)項 ，每個項稱為結(jié)點的一個域 。每個元素有一個可以唯一標識每個結(jié)點的數(shù)據(jù)項組，稱為關(guān)鍵字。例4 ： 某校2001級同學(xué)的基本情況：(2001414101，張里戶，男，06/24/1983)， (

26、2001414102，張化司，男，08/12/1984) ， (2001414102，李利辣，女，08/12/1984) 若線性表中的結(jié)點是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。2.1.3 線性表的抽象數(shù)據(jù)類型定義ADT List數(shù)據(jù)對象：D = ai | aiElemSet, i=1,2,n, n0 數(shù)據(jù)關(guān)系：R = | ai-1, aiD, i=2,3,n 基本操作：InitList( &L )操作結(jié)果：構(gòu)造一個空的線性表L； 線性表是一種相當靈活的數(shù)據(jù)結(jié)構(gòu)，其長度可根據(jù)需要增長或縮短。 對線性表的數(shù)據(jù)元素可以訪問、插入和刪除。ListLength( L )初

27、始條件：線性表L已存在；操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE；.GetElem( L, i, &e )初始條件：線性表L已存在，1iListLength(L)；操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值；ListInsert ( L, i, &e )初始條件：線性表L已存在，1iListLength(L) ；操作結(jié)果：在線性表L中的第i個位置插入元素e； ADT List2.2 線性表的順序存儲順序存儲 ：把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。順序存儲的線性表的特點： 線性表的邏輯順序與物理順序一致; 數(shù)據(jù)元素之間的關(guān)系

28、是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)。設(shè)有非空的線性表：(a1，a2，an) 。順序存儲如圖2-1所示。2.2.1 線性表的順序存儲結(jié)構(gòu)在具體的機器環(huán)境下：設(shè)線性表的每個元素需占用l個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：LOC(ai+1)=LOC(ai)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*l在高級語言(如C語言)環(huán)境下：數(shù)組具有隨機存取的特性，因此，借助數(shù)組來描述順序表。除了用數(shù)組來存儲線性表的元素之

29、外，順序表還應(yīng)該有表示線性表的長度屬性，所以用結(jié)構(gòu)類型來定義順序表類型。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status ;typedef int ElemType ;typedef struct sqlist ElemType Elem_arrayMAX_SIZE ;int length ; SqList ;注意：C語言中數(shù)組的下標值是從0開始，第i個元素的下標值是i - 1 。2.2.2 順序表的基本操作順序存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。以下將對幾種

30、主要的操作進行討論。1 順序線性表初始化Status Init_SqList( SqList *L ) L-elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ;if ( !L - elem_array ) return ERROR ;else L-length= 0 ; return OK ; 2 順序線性表的插入在線性表 L= (a1，a i-1，ai， ai+1，an) 中的第i(1in)個位置上插入一個新結(jié)點e，使其成為線性表：L=(a1，a i-1，e，ai，ai+1，an)實現(xiàn)步驟(1) 將線性表L中的第i個至

31、第n個結(jié)點后移一個位置。(2) 將結(jié)點e插入到結(jié)點ai-1之后。(3) 線性表長度加1。算法描述Status Insert_SqList(Sqlist *L，int i ，ElemType e) int j ;if ( iL-length-1) return ERROR ;if (L-length=MAX_SIZE) printf(“線性表溢出!n”); return ERROR ; for ( j=L-length1; j=i-1; -j )L-Elem_arrayj+1=L-Elem_arrayj;/* i-1位置以后的所有結(jié)點后移 */L-Elem_arrayi-1=e; /* 在i-1

32、位置插入結(jié)點 */L-length+ ;return OK ;時間復(fù)雜度分析在線性表L中的第i個元素之前插入新結(jié)點，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復(fù)雜度。設(shè)在線性表L中的第i個元素之前插入結(jié)點的概率為Pi，不失一般性，設(shè)各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動結(jié)點的次數(shù)為n-i+1?？偟钠骄苿哟螖?shù)： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。即在順序表上做插入運算，平均要移動表上一半結(jié)點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復(fù)雜度為O(n)。3 順序線性表的刪除在線性表 L=(a1

33、，a i-1，ai， ai+1，an) 中刪除結(jié)點ai(1in)，使其成為線性表：L= (a1，ai-1，ai+1，an)實現(xiàn)步驟(1) 將線性表L中的第i+1個至第n個結(jié)點依此向前移動一個位置。(2) 線性表長度減1。算法描述ElemType Delete_SqList(Sqlist *L，int i) int k ; ElemType x ;if (L-length=0) printf(“線性表L為空!n”); return ERROR; else if ( iL-length ) printf(“要刪除的數(shù)據(jù)元素不存在!n”) ;return ERROR ; else x=L-Elem_

34、arrayi-1 ; /*保存結(jié)點的值*/for ( k=i ; klength ; k+)L-Elem_arrayk-1=L-Elem_arrayk;/* i位置以后的所有結(jié)點前移 */L-length-; return (x);時間復(fù)雜度分析刪除線性表L中的第i個元素，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復(fù)雜度。設(shè)在線性表L中刪除第i個元素的概率為Pi，不失一般性，設(shè)刪除各個位置是等概率，則Pi=1/n，而刪除時移動結(jié)點的次數(shù)為n-i。則總的平均移動次數(shù)： Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。即在順序表上做刪

35、除運算，平均要移動表上一半結(jié)點。當表長n較大時，算法的效率相當?shù)汀Ｒ虼怂惴ǖ钠骄鶗r間復(fù)雜度為O(n)。4 順序線性表的查找定位刪除在線性表 L= (a1，a2，an) 中刪除值為x的第一個結(jié)點。實現(xiàn)步驟(1) 在線性表L查找值為x的第一個數(shù)據(jù)元素。(2) 將從找到的位置至最后一個結(jié)點依次向前移動一個位置。(3) 線性表長度減1。算法描述Status Locate_Delete_SqList(Sqlist *L，ElemType x)/* 刪除線性表L中值為x的第一個結(jié)點 */ int i=0 , k ;while (ilength) /*查找值為x的第一個結(jié)點*/ if (L-Elem_arr

36、ayi!=x ) i+ ;else for ( k=i+1; klength; k+)L-Elem_arrayk-1=L-Elem_arrayk;L-length-; break ;if (iL-length) printf(“要刪除的數(shù)據(jù)元素不存在!n”) ;return ERROR ; return OK;時間復(fù)雜度分析時間主要耗費在數(shù)據(jù)元素的比較和移動操作上。首先，在線性表L中查找值為x的結(jié)點是否存在;其次，若值為x的結(jié)點存在，且在線性表L中的位置為i ，則在線性表L中刪除第i個元素。設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個位置是等概率，則Pi=1/n。 比較的平均次數(shù)：

37、Ecompare=pi*i (1in) Ecompare=(n+1)/2 。 刪除時平均移動次數(shù)：Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 平均時間復(fù)雜度：Ecompare+Edelete=n ，即為O(n)順序存儲的線性表的特點:優(yōu)點：表中任一結(jié)點的存取很方便，也能進行插入和刪除操作。缺點：(1) 插入和刪除不方便。為保持連續(xù)存放，操作中需要移動大量元素。(2) 會造成空間的浪費以及不易擴充。數(shù)組大小固定，對于處理長度變化較大的線性表時，分配數(shù)組大小不夠，會造成溢出;分配大小太大，會造成空間浪費。2.3 線性表的鏈式存儲2.3.1 線性表的鏈式存儲結(jié)構(gòu)

38、鏈式存儲 ：用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。存儲鏈表中結(jié)點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點的邏輯順序和物理順序不一定相同。為了正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其直接后繼結(jié)點的地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)，如圖2-2所示。鏈表是通過每個結(jié)點的指針域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。每一個結(jié)只包含一個指針域的鏈表，稱為單鏈表。為操作方便，總是在鏈表的第一個結(jié)點之前附設(shè)一個頭結(jié)點(頭

39、指針)head指向第一個結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息(或鏈表長度等信息)。單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結(jié)點的單鏈表的邏輯狀態(tài)和物理存儲方式如圖2-3所示。1 結(jié)點的描述與實現(xiàn)C語言中用帶指針的結(jié)構(gòu)體類型來描述typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結(jié)點的值 */struct Lnode *next; /*指針域*/LNode; /*結(jié)點的類型 */2 結(jié)點的實現(xiàn)結(jié)點是通過動態(tài)分配和釋放來的實現(xiàn)，即需要時分配，不需要時釋放。實現(xiàn)時是分別使用C語

40、言提供的標準函數(shù)：malloc() ，realloc()，sizeof() ，free() 。動態(tài)分配 p=(LNode*)malloc(sizeof(LNode);函數(shù)malloc分配了一個類型為LNode的結(jié)點變量的空間，并將其首地址放入指針變量p中。動態(tài)釋放 free(p) ;系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用malloc函數(shù)時的返回值。3 最常用的基本操作及其示意圖 結(jié)點的賦值LNode *p;p=(LNode*)malloc(sizeof(LNode);p-data=20; p-next=NULL ;講課時板書教案上的幾種常見的指針操作。 常見的指針操作講課時板

41、書教案上的幾種常見的指針操作。講課時板書教案上的幾種常見的指針操作。2.3.2 單線性鏈式的基本操作1 建立單鏈表假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是整型，以32767作為結(jié)束標志。動態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。 頭插入法建表從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當前鏈表的表頭上，直到讀入結(jié)束標志為止。即每次插入的結(jié)點都作為鏈表的第一個結(jié)點。算法描述LNode *create_LinkList(void)/* 頭插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點head作為返回值 */ int data ;LNode *head, *p;

42、head= (LNode *) malloc( sizeof(LNode);head-next=NULL; /* 創(chuàng)建鏈表的表頭結(jié)點head */while (1) scanf(“%d”, &data) ;if (data=32767) break ;p= (LNode *)malloc(sizeof(LNode);pdata=data; /* 數(shù)據(jù)域賦值 */pnext=headnext ; headnext=p ;/* 鉤鏈，新創(chuàng)建的結(jié)點總是作為第一個結(jié)點 */return (head);(2) 尾插入法建表頭插入法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者

43、次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當前鏈表的表尾，使其成為當前鏈表的尾結(jié)點。算法描述LNode *create_LinkList(void)/* 尾插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點head作為返回值 */ int data ;LNode *head, *p, *q;head=p=(LNode *)malloc(sizeof(LNode);p-next=NULL; /* 創(chuàng)建單鏈表的表頭結(jié)點head */while (1) scanf(“%d”,& data);if (data=32767) break ;q= (LNode *)malloc(sizeof(LNode);qdata

44、=data; /* 數(shù)據(jù)域賦值 */qnext=pnext; pnext=q; p=q ;/*鉤鏈，新創(chuàng)建的結(jié)點總是作為最后一個結(jié)點*/return (head);無論是哪種插入方法，如果要插入建立的單線性鏈表的結(jié)點是n個，算法的時間復(fù)雜度均為O(n)。對于單鏈表，無論是哪種操作，只要涉及到鉤鏈(或重新鉤鏈)，如果沒有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。2 單鏈表的查找(1) 按序號查找 取單鏈表中的第i個元素。對于單鏈表，不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭結(jié)點出發(fā)，沿鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取

45、結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當1in時，i的值是合法的。算法描述ElemType Get_Elem(LNode *L ， int i) int j ; LNode *p;p=L-next; j=1; /* 使p指向第一個結(jié)點 */while (p!=NULL & jnext; j+; /* 移動指針p , j計數(shù) */if (j!=i) return(-32768) ;else return(p-data);/* p為NULL 表示i太大; ji表示i為0 */移動指針p的頻度：in：n次。時間復(fù)雜度: O(n)。(2) 按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給

46、定值key的結(jié)點? 若有，則返回首次找到的值為key的結(jié)點的存儲位置；否則返回NULL。查找時從開始結(jié)點出發(fā)，沿鏈表逐個將結(jié)點的值和給定值key作比較。算法描述LNode *Locate_Node(LNode *L，int key)/* 在以L為頭結(jié)點的單鏈表中查找值為key的第一個結(jié)點 */ LNode *p=Lnext;while ( p!=NULL& pdata!=key) p=pnext;if (pdata=key) return p;else printf(“所要查找的結(jié)點不存在!n”);retutn(NULL);算法的執(zhí)行與形參key有關(guān)，平均時間復(fù)雜度為O(n)。3 單鏈表的插入

47、插入運算是將值為e的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點p，然后生成一個數(shù)據(jù)域為e的新結(jié)點q，q結(jié)點作為p的直接后繼結(jié)點。算法描述void Insert_LNode(LNode *L，int i，ElemType e)/* 在以L為頭結(jié)點的單鏈表的第i個位置插入值為e的結(jié)點 */ int j=0; LNode *p，*q;p=Lnext ;while ( p!=NULL& jnext; j+; if (j!=i-1) printf(“i太大或i為0!n ”);else q=(LNode *)malloc(sizeof(LNode)

48、;qdata=e; qnext=pnext;pnext=q;設(shè)鏈表的長度為n，合法的插入位置是1in。算法的時間主要耗費移動指針p上，故時間復(fù)雜度亦為O(n)。4 單鏈表的刪除 按序號刪除刪除單鏈表中的第i個結(jié)點。為了刪除第i個結(jié)點ai，必須找到結(jié)點的存儲地址。該存儲地址是在其直接前趨結(jié)點ai-1的next域中，因此，必須首先找到ai-1的存儲位置p，然后令pnext指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。設(shè)單鏈表長度為n，則刪去第i個結(jié)點僅當1in時是合法的。則當i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，是終端結(jié)點。故判斷條件之一

49、是pnext!=NULL。顯然此算法的時間復(fù)雜度也是O(n)。算法描述void Delete_LinkList(LNode *L， int i)/* 刪除以L為頭結(jié)點的單鏈表中的第i個結(jié)點 */ int j=1; LNode *p，*q;p=L; q=L-next;while ( p-next!=NULL& jnext; j+; if (j!=i) printf(“i太大或i為0!n ”);else pnext=qnext; free(q); 按值刪除刪除單鏈表中值為key的第一個結(jié)點。與按值查找相類似，首先要查找值為key的結(jié)點是否存在? 若存在，則刪除；否則返回NULL。算法描述void

50、Delete_LinkList(LNode *L，int key)/* 刪除以L為頭結(jié)點的單鏈表中值為key的第一個結(jié)點 */ LNode *p=L, *q=Lnext;while ( q!=NULL& qdata!=key) p=q; q=qnext; if (qdata=key) p-next=q-next; free(q); elseprintf(“所要刪除的結(jié)點不存在!n”);算法的執(zhí)行與形參key有關(guān)，平均時間復(fù)雜度為O(n)。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無需移動結(jié)點，僅需修改指針。解決了順序表的插入或刪除操作需要移動大量元素的問題。變形之一：刪除單鏈表中值為ke

51、y的所有結(jié)點。與按值查找相類似，但比前面的算法更簡單?；舅枷耄簭膯捂湵淼牡谝粋€結(jié)點開始，對每個結(jié)點進行檢查，若結(jié)點的值為key，則刪除之，然后檢查下一個結(jié)點，直到所有的結(jié)點都檢查。算法描述void Delete_LinkList_Node(LNode *L，int key)/* 刪除以L為頭結(jié)點的單鏈表中值為key的第一個結(jié)點 */ LNode *p=L, *q=Lnext;while ( q!=NULL) if (qdata=key) p-next=q-next; free(q); q=p-next; else p=q; q=qnext; 變形之二：刪除單鏈表中所有值重復(fù)的結(jié)點，使得所有結(jié)

52、點的值都不相同。與按值查找相類似，但比前面的算法更復(fù)雜?；舅枷耄簭膯捂湵淼牡谝粋€結(jié)點開始，對每個結(jié)點進行檢查：檢查鏈表中該結(jié)點的所有后繼結(jié)點，只要有值和該結(jié)點的值相同，則刪除之；然后檢查下一個結(jié)點，直到所有的結(jié)點都檢查。算法描述void Delete_Node_value(LNode *L)/* 刪除以L為頭結(jié)點的單鏈表中所有值相同的結(jié)點 */ LNode *p=L-next, *q, *ptr;while ( p!=NULL) /* 檢查鏈表中所有結(jié)點 */ *q=p, *ptr=pnext;/* 檢查結(jié)點p的所有后繼結(jié)點ptr */while (ptr!=NULL) if (ptrdat

53、a=p-data) q-next=ptr-next; free(ptr);ptr=q-next; else q=ptr; ptr=ptrnext; p=p-next ;5 單鏈表的合并設(shè)有兩個有序的單鏈表，它們的頭指針分別是La 、 Lb，將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。合并了值為-7，-2的結(jié)點后示意圖如圖2-5所示。算法說明算法中pa ，pb分別是待考察的兩個鏈表的當前結(jié)點，pc是合并過程中合并的鏈表的最后一個結(jié)點。算法描述LNode *Merge_LinkList(LNode *La， LNode *Lb)/* 合并以La, Lb為頭結(jié)點的兩個有序單鏈

54、表 */ LNode *Lc, *pa , *pb , *pc, *ptr ;Lc=La ; pc=La ; pa=La-next ; pb=Lb-next ;while (pa!=NULL& pb!=NULL) if (pa-datadata) pc-next=pa ; pc=pa ; pa=pa-next ; /* 將pa所指的結(jié)點合并，pa指向下一個結(jié)點 */if (pa-datapb-data) pc-next=pb ; pc=pb ; pb=pb-next ; /* 將pa所指的結(jié)點合并，pa指向下一個結(jié)點 */if (pa-data=pb-data) pc-next=pa ; pc

55、=pa ; pa=pa-next ;ptr=pb ; pb=pb-next ; free(ptr) ; /* 將pa所指的結(jié)點合并，pb所指結(jié)點刪除 */if (pa!=NULL) pc-next=pa ;else pc-next=pb ; /*將剩余的結(jié)點鏈上*/free(Lb) ;return(Lc) ;算法分析若La ，Lb兩個鏈表的長度分別是m，n，則鏈表合并的時間復(fù)雜度為O(m+n) 。2.3.3 循環(huán)鏈表循環(huán)鏈表(Circular Linked List)：是一種頭尾相接的鏈表。其特點是最后一個結(jié)點的指針域指向鏈表的頭結(jié)點，整個鏈表的指針域鏈接成一個環(huán)。從循環(huán)鏈表的任意一個結(jié)點出發(fā)

56、都可以找到鏈表中的其它結(jié)點，使得表處理更加方便靈活。圖2-6是帶頭結(jié)點的單循環(huán)鏈表的示意圖?？毡硌h(huán)鏈表的操作對于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡單修改： 判斷是否是空鏈表：head-next=head ; 判斷是否是表尾結(jié)點：p-next=head ;2.4 雙向鏈表雙向鏈表(Double Linked List) :指的是構(gòu)成鏈表的每個結(jié)點中設(shè)立兩個指針域：一個指向其直接前趨的指針域prior，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也

57、能使雙鏈表上的某些運算變得方便。將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。1 雙向鏈表的結(jié)點及其類型定義雙向鏈表的結(jié)點的類型定義如下。其結(jié)點形式如圖2-7所示，帶頭結(jié)點的雙向鏈表的形式如圖2-8所示。typedef struct Dulnode ElemType data ;struct Dulnode *prior , *next ;DulNode ;雙向鏈表結(jié)構(gòu)具有對稱性，設(shè)p指向雙向鏈表中的某一結(jié)點，則其對稱性可用下式描述：(p-prior)-next=p=(p-next)-prior ;結(jié)點p的存儲位置存放在其直接前趨結(jié)點p-pr