《數(shù)據(jù)結(jié)構(gòu)》第4版高職全套教學課件

第1章緒論《數(shù)據(jù)結(jié)構(gòu)》（第四版）第1章緒論.pptx第2章線性表（1）.pptx第2章線性表（2）.pptx第3章棧和隊列（1）.pptx第3章棧和隊列（2）.pptx第4章串.pptx第5章數(shù)組和廣義表.pptx第6章樹（1）.pptx第6章樹（2）.pptx第7章圖（1）.pptx第7章圖（2）.pptx第8章查找.pptx第9章排序.pptx全套可編輯PPT課件目錄CONTENTS數(shù)據(jù)結(jié)構(gòu)的發(fā)展1.1邊界值分析法1.2錯誤推測法1.3學習目標Learningtarget知識目標了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展。理解數(shù)據(jù)結(jié)構(gòu)中的基本概念。理解抽象數(shù)據(jù)類型的概念、記法和用法理解算法分析的目的。掌握算法及其特性。掌握算法時間復雜度的分析方法。素質(zhì)目標理解“數(shù)據(jù)結(jié)構(gòu)”課程的意義和基本概念，構(gòu)建課程的整體知識框架，培養(yǎng)學生的全局意識和大局觀。通過學習算法復雜度分析，學習“工匠精神”，激發(fā)學生開拓創(chuàng)新，深耕科研之路，為全面建設(shè)社會主義現(xiàn)代化國家、全面推進中華民族偉大復興貢獻青春力量。技能目標能分析一般算法的時間復雜度。1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展全套可編輯PPT課件1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展

用計算機解決一個具體問題時，要先從具體問題中抽象出一個適當?shù)臄?shù)據(jù)模型，設(shè)計出一個解此數(shù)據(jù)模型的算法，然后編寫程序，形成軟件。在誕生初期，計算機主要用于完成數(shù)值計算工作。隨著計算機科學與技術(shù)的不斷進步，計算機的應(yīng)用領(lǐng)域從單一的數(shù)值計算發(fā)展到字符、圖像、表格和聲音等具有復雜結(jié)構(gòu)的非數(shù)值處理，處理的數(shù)據(jù)量也不斷增大。如何科學有效地處理這些數(shù)據(jù)，就成了程序設(shè)計的一個問題。數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計算程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科。

1968年，美國的唐納德·歐文克努特(DonaldE.Knuth)教授在他的歷史性經(jīng)典巨著《計算機程序設(shè)計藝術(shù)》(TheArtofComputerProgramming)第一卷《基本算法》中較系統(tǒng)地闡述了數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作，開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。20世紀70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程進入大學課堂。在我國，自1978年美籍華裔學者冀中田在國內(nèi)首開這門課程以來，經(jīng)過幾十年的發(fā)展，該課程已經(jīng)成為各大學計算機專業(yè)的學科主干課程，也成為非計算機專業(yè)學生學習計算機的主要選修課程之一。1.2數(shù)據(jù)結(jié)構(gòu)的意義

數(shù)據(jù)結(jié)構(gòu)是一門綜合性很強的專業(yè)基礎(chǔ)課，是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。

瑞士計算機科學家沃斯(N.Wirth)曾提出：

程序＝數(shù)據(jù)結(jié)構(gòu)+算法1.2數(shù)據(jù)結(jié)構(gòu)的意義1.3數(shù)據(jù)結(jié)構(gòu)的概述1.3.1基本概念和術(shù)語1.數(shù)據(jù)

數(shù)據(jù)(Data)是信息的載體，是指能夠輸入計算機中并能被計算機識別、存儲和加工處理的符號集合。在計算機科學中，數(shù)據(jù)的含義很廣泛，既有整數(shù)和實數(shù)等數(shù)值類型，也包括聲音、文字和圖像等非數(shù)值類型。2.數(shù)據(jù)元素

數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行處理。數(shù)據(jù)元素也稱為結(jié)點或記錄。一個數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項組成。通常，能獨立、完整地描述問題世界的一切實體都是數(shù)據(jù)元素。3.數(shù)據(jù)項

數(shù)據(jù)項(DataItem)是數(shù)據(jù)的最小單位，是對數(shù)據(jù)元素屬性的描述，也稱域或字段。4.數(shù)據(jù)對象

數(shù)據(jù)對象(DataObject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。5.數(shù)據(jù)類型

數(shù)據(jù)類型(DataType)是一組性質(zhì)相同的值的集合和定義在該值集上的一組操作的總稱。每個數(shù)據(jù)項屬于某一確定的數(shù)據(jù)類型。按“值”的特性不同，高級程序設(shè)計語言中的數(shù)據(jù)類型可以分為兩類：(1)原子類型：其值不可分解。例如，C語言中的整型、實型和字符型等。(2)結(jié)構(gòu)類型：其值通?？梢苑纸獬蔀槿舾蓚€成分。它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的，如數(shù)組類型和結(jié)構(gòu)類型等。6.數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包含三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算。算法的設(shè)計取決于選定的數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，實現(xiàn)在數(shù)據(jù)的存儲結(jié)構(gòu)上。1.3.1基本概念和術(shù)語1.3.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是獨立于計算機系統(tǒng)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。1.線性結(jié)構(gòu)

數(shù)據(jù)元素之間存在著一對一的關(guān)系。線性結(jié)構(gòu)中有且僅有一個首結(jié)點和一個尾結(jié)點，首結(jié)點只有一個直接后繼結(jié)點，尾結(jié)點只有一個直接前驅(qū)結(jié)點，其他結(jié)點有且僅有一個直接前驅(qū)結(jié)點和一個直接后繼結(jié)點。如圖1.1(a)所示。1.3.2數(shù)據(jù)的邏輯結(jié)構(gòu)2.非線性結(jié)構(gòu)

非線性結(jié)構(gòu)可細分為以下幾部分：(1)集合：數(shù)據(jù)元素之間同屬于一個集合，除此之外沒有其他關(guān)系。如圖1.1(b)所示。它是數(shù)據(jù)結(jié)構(gòu)的一個特例，本書不予討論。(2)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系。如圖1.1(c)所示。在現(xiàn)實生活中，部門的組織結(jié)構(gòu)、棋盤對弈格局、體育比賽賽制安排和家譜等問題都可以用樹形結(jié)構(gòu)來描述。(3)圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對多的關(guān)系。如圖1.1(d)所示。當數(shù)據(jù)元素間有著多對多關(guān)系時，形成圖結(jié)構(gòu)。例如，交通和網(wǎng)絡(luò)布線等許多問題模型都屬于圖結(jié)構(gòu)。1.3.2數(shù)據(jù)的邏輯結(jié)構(gòu)1.3.3數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)(StorageStructure)是指數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，是依賴于計算機的。

在存儲器中表示數(shù)據(jù)的方法通常有以下四種：(1)順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，其數(shù)據(jù)元素間的邏輯關(guān)系是通過元素的存儲位置來反映的。(2)鏈式存儲結(jié)構(gòu)：用一組任意的存儲單元存儲數(shù)據(jù)元素，其數(shù)據(jù)元素間的邏輯關(guān)系通過附加指針來表示。(3)索引存儲結(jié)構(gòu)：在存儲數(shù)據(jù)元素的同時，建立一個附加的索引表，利用索引表中索引項的值來確定結(jié)點的存儲單元地址。(4)散列存儲結(jié)構(gòu)：根據(jù)數(shù)據(jù)元素的關(guān)鍵字，通過散列函數(shù)直接計算出該數(shù)據(jù)元素的存儲地址。一種邏輯結(jié)構(gòu)可以采用不同的存儲結(jié)構(gòu)，具體選定哪種存儲結(jié)構(gòu)主要取決于算法運算的方便以及算法的時間和空間利用率。1.3.4抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是一個數(shù)據(jù)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型描述的是一組邏輯特性，與在計算機內(nèi)部的表示和實現(xiàn)無關(guān)。

定義抽象數(shù)據(jù)類型時，只包含數(shù)據(jù)的邏輯結(jié)構(gòu)的定義和所允許的操作集合，不涉及它的實現(xiàn)細節(jié)。抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計中問題分解、信息隱藏和數(shù)據(jù)封裝的特性。1.4算法及其分析1.4.1算法1.算法的定義

算法(Algorithm)是指對特定問題解題方案的準確而完整的描述，是一系列解決問題的清晰指令的有限序列。也就是說，算法能夠?qū)σ欢ㄒ?guī)范的輸入在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于這個問題，執(zhí)行該算法將不會解決這個問題。

算法必須滿足以下五個特性：(1)有窮性：一個算法必須在執(zhí)行有窮步后結(jié)束，且每一步都可在有窮時間內(nèi)完成。(2)確定性：算法中的每條指令必須有確切的含義，不會產(chǎn)生二義性。(3)可行性：算法中的每條指令都是可行的，且可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。(4)輸入：一個算法可以有零個或多個輸入(算法可以沒有輸入)，這些輸入來自某個特定對象的集合。(5)輸出：一個算法應(yīng)該有一個或多個輸出(算法必須有輸出)，這些輸出是同輸入有特定關(guān)系的量。沒有輸出的算法是沒有意義的。2.算法設(shè)計的要求

一個問題可以有多種算法，一個“好”算法應(yīng)該具有以下幾個方面的基本特性：(1)正確性

正確性是設(shè)計一個算法的首要條件，所設(shè)計的算法要滿足具體問題的要求。在輸入合法的數(shù)據(jù)時，算法能在有限的時間內(nèi)得到正確的結(jié)果。

可以理解為以下四個層次：①程序不含語法錯誤。②程序?qū)捉M輸入數(shù)據(jù)能給出滿足規(guī)格說明要求的結(jié)果。③程序?qū)倪x擇的、典型的、苛刻而有刁難性的幾組輸入數(shù)據(jù)能給出滿足規(guī)格說明要求的結(jié)果。④程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能給出滿足規(guī)格說明要求的結(jié)果。1.4.1算法(2)可讀性

一個好的算法首先要便于人們閱讀、理解，其次才是計算機可以執(zhí)行。可讀性是軟件開發(fā)的一項重要原則，算法的可讀性好，則其可維護性也強。(3)健壯性

當輸入不合法的數(shù)據(jù)時，算法應(yīng)該給出相應(yīng)的處理結(jié)果，而不是產(chǎn)生錯誤動作或是陷入癱瘓。(4)高效率和低存儲量

效率是指算法的執(zhí)行時間。對于解決一個特定問題的不同算法，執(zhí)行時間短的算法效率高。存儲量是指算法執(zhí)行過程中所需要的最大存儲空間。這二者與輸入的規(guī)模和輸入數(shù)據(jù)的性質(zhì)有關(guān)。設(shè)計時應(yīng)盡量選擇高效率和低存儲量的算法。1.4.1算法1.4.1算法3.算法的描述方法(1)自然語言

用自然語言描述算法容易理解，但容易出現(xiàn)二義性。(2)流程圖

流程圖的優(yōu)點是直觀，但靈活性不如自然語言，對復雜的流程不易表達。(3)程序設(shè)計語言

用程序設(shè)計語言描述的算法能夠直接在計算機上運行，但抽象性差。4.算法與程序

程序(Program)是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn)。算法與程序非常相似，但二者是有區(qū)別的。首先，算法可以有多種表達方式，程序設(shè)計要符合程序設(shè)計語言的規(guī)則；其次，程序不一定滿足有窮性；最后，程序中的指令必須是計算機可以執(zhí)行的，而算法中的指令可以包括計算機的一個或多個操作。1.4.2算法分析

同一問題可用不同的算法解決，一個算法的質(zhì)量將影響到算法乃至程序的效率。算法分析的目的在于選擇合適的算法和改進算法。1.時間復雜度

對于解決特定問題的算法，執(zhí)行時間短的顯然比執(zhí)行時間長的效率高。衡量一個算法的執(zhí)行時間有事后統(tǒng)計和事前分析兩種方法。(1)事后統(tǒng)計

事后統(tǒng)計方法是通過使用測試用例運行已經(jīng)設(shè)計完成的程序，利用計算機計時器測定該程序的運行時間。但該方法存在一定的缺陷：一是必須事先完成程序的設(shè)計，耗時耗力；二是計算機硬件和軟件等環(huán)境因素將會影響測試的準確性，甚至會掩蓋算法本身的優(yōu)劣。(2)事前分析

事前分析方法不上機運行根據(jù)算法編制的程序，而是依據(jù)統(tǒng)計方法對算法執(zhí)行時間進行估算。

程序在計算機上運行的影響因素有：①機器執(zhí)行指令的速度。②算法本身選用的策略。③編譯產(chǎn)生的機器代碼質(zhì)量。④輸入算法的數(shù)據(jù)量，稱為問題規(guī)模，問題規(guī)模越大，耗時越多。⑤書寫程序的語言，語言越高級，耗時越多。1.4.2算法分析

當算法采用不同的編譯系統(tǒng)、不同的策略及不同的編程語言在不同的計算機上運行時，其效率均會不同。所以，不宜使用絕對時間衡量算法效率。因此，最重要的因素是問題規(guī)模。

一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，所花費的時間就多。

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)稱為語句頻度或時間頻度，它是問題規(guī)模n的某個函數(shù)，用T(n)表示。若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度(TimeComplexity)。時間復雜度不是精確的執(zhí)行次數(shù)，而是估算的數(shù)量級，著重體現(xiàn)的是隨著問題規(guī)模n的增大，算法執(zhí)行時間的變化趨勢。

1.4.2算法分析【例1.4】求以下六個算法的時間復雜度。(1)x=x+1;x=x+1是基本語句，執(zhí)行次數(shù)為1。它的語句頻度與問題規(guī)模n沒有關(guān)系，時間復雜度為O(1)，稱為常數(shù)階。(2)for(i=0;i<n;i++)x=x+1;x=x+1是基本語句，執(zhí)行次數(shù)為n。它的語句頻度隨問題規(guī)模n的增大而呈線性增大，時間復雜度為O(n)，稱為線性階。(3)for(j=0;j<n;j++)for(i=0;i<n;i++)x=x+1;x=x+1是基本語句，執(zhí)行次數(shù)為n2。時間復雜度為O(n2)，稱為平方階。1.4.2算法分析(4)for(k=0;k<n;k++)for(j=0;j<n;j++)for(i=0;i<n;i++)x=x+1;x=x+1是基本語句，執(zhí)行次數(shù)為n3。時間復雜度為O(n3)，稱為立方階。(5)i=0;

sum=0;

while(sum<n)

{i=i+1;sum=sum+i;

}sum=sum+i是基本語句，設(shè)執(zhí)行次數(shù)為T(n)，則要滿足：sum=1+2+3+…+T(n)=(1+T(n))T(n)/2≤n，即T(n)≤

。該算法的時間復雜度為O(n)。1.4.2算法分析(6)i=1;

while(i<=n)i=i*2;i=i*2是基本語句，設(shè)執(zhí)行次數(shù)為T(n)，則要滿足：2T(n)-1≤n，即T(n)≤log2n+1。該算法的時間復雜度為O(log2n)，稱為對數(shù)階。

常用的時間復雜度所耗費的時間從小到大依次是：O(1)(常數(shù)階)<O(log2n)(對數(shù)階)<O(n)(線性階)<O(nlog2n)(線性對數(shù)階)<O(n2)(平方階)<O(n3)(立方階)<…<O(nk)(k次方階)<O(2n)(指數(shù)階)

算法的時間復雜度越大，其執(zhí)行效率就越低。當我們在解決大規(guī)模數(shù)據(jù)問題時，需要發(fā)揚工匠精神，探索解決該問題的低時間復雜度算法。例如，我國神舟十二號飛船發(fā)射入軌后需要完成自主快速交會對接，整個過程歷時約6.5小時，自動控制過程用到了很多的算法，高效的算法縮短了交會對接時間，大大緩解了航天員的旅途疲勞，為中國載人航天事業(yè)取得了巨大進步助力。1.4.2算法分析1.4.2算法分析2.空間復雜度

空間復雜度(SpaceComplexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記作S(n)=O(f(n))。其中，n為問題規(guī)模，分析方法與算法的時間復雜度相似。感謝支持本章結(jié)束第2章線性表（一）《數(shù)據(jù)結(jié)構(gòu)》（第四版）目錄CONTENTS案例導引2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序存儲結(jié)構(gòu)2.3學習目標Learningtarget知識目標理解線性表的邏輯結(jié)構(gòu)特征。掌握順序表的含義、特點、基本運算和相關(guān)算法分析。掌握鏈表的含義、特點、基本運算和相關(guān)算法分析。理解循環(huán)鏈表和雙鏈表的邏輯結(jié)構(gòu)特征及基本運算。理解順序表和鏈表的比較。素質(zhì)目標理解針對實際問題選擇不同數(shù)據(jù)結(jié)構(gòu)解決方案的差異，引導學生運用具體問題具體分析的方法論分析問題、解決問題。軟件工程師應(yīng)具有選擇最優(yōu)方案的知識儲備，編寫出來的軟件才會得到用戶的喜歡。技能目標能應(yīng)用順序表的理論設(shè)計算法，解決實際問題。能應(yīng)用鏈表的理論設(shè)計算法，解決實際問題。2.1案例導引

編寫一個用于通信錄管理的程序，實現(xiàn)對聯(lián)系人信息的插入、刪除和查找等功能。要求記錄每位聯(lián)系人的姓名、性別、手機號碼、住宅電話和郵箱信息。案例：通信錄管理。案例探析：

對于通信錄中的聯(lián)系人需要管理其姓名、性別、電話和郵箱等信息，各位聯(lián)系人所需要存儲的信息類型是相同的，也就是說各個結(jié)點應(yīng)該具有相同的結(jié)構(gòu)。同時，各位聯(lián)系人的信息記錄之間按順序排列，形成了線性結(jié)構(gòu)。線性結(jié)構(gòu)是最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。2.2線性表的邏輯結(jié)構(gòu)2.2.1線性表的定義

線性表(LinearList)是由n個性質(zhì)相同的數(shù)據(jù)元素組成的有限序列。表中數(shù)據(jù)元素的個數(shù)n定義為線性表的長度。n=0的表稱為空表，即該線性表不包含任何數(shù)據(jù)元素；n>0時，線性表記為：L=(a1,a2,a3,…,ai,…,an)

其中，ai(1≤i≤n)稱為表中的第i個數(shù)據(jù)元素，下標i表示該元素在線性表中的位置。任意一對相鄰的數(shù)據(jù)元素ai-1和ai(2≤i≤n)存在著線性關(guān)系(ai-1，ai)，且ai-1稱為ai的直接前驅(qū)，ai稱為ai-1的直接后繼。

線性表的邏輯結(jié)構(gòu)為：(1)存在唯一的數(shù)據(jù)元素a1，或稱首結(jié)點，它沒有直接前驅(qū)，只有一個直接后繼。(2)存在唯一的數(shù)據(jù)元素an，或稱尾結(jié)點，它沒有直接后繼，只有一個直接前驅(qū)。(3)除第一個結(jié)點(首結(jié)點)之外，集合中的每個數(shù)據(jù)元素均只有一個直接前驅(qū)。(4)除最后一個結(jié)點(尾結(jié)點)之外，集合中每個數(shù)據(jù)元素均只有一個直接后繼。

線性表中的數(shù)據(jù)元素之間是一對一的關(guān)系，數(shù)據(jù)元素可以是簡單數(shù)據(jù)類型，如整型和字符型等；也可以是用戶自定義的任何類型，如記錄類型等。2.2.1線性表的定義

線性表是一種典型的線性結(jié)構(gòu)，用二元組表示為：S=(A,R)A={a1,a2，a3,…，ai,…,an}R={<a1,a2>,<a2,a3>,…,<ai-1,ai>,<ai,ai+1>,…,<an-1,an>}

線性表的邏輯結(jié)構(gòu)如圖2-1所示。圖2-1線性表的邏輯結(jié)構(gòu)2.2.1線性表的定義2.2.2線性表的抽象數(shù)據(jù)類型定義

線性表的長度可以隨著數(shù)據(jù)元素的插入和刪除等操作而增加或減少，是一種靈活的數(shù)據(jù)結(jié)構(gòu)。線性表的抽象數(shù)據(jù)類型定義如下：ADTList{數(shù)據(jù)對象：D={ai|ai為DataType類型，1≤i≤n，n≥0}/*DataType為自定義類型*/數(shù)據(jù)關(guān)系：R={<ai-1，ai>|ai-1，ai∈D，2≤i≤n}。在非空表中，除了首結(jié)點，每個結(jié)點都有且只有一個前驅(qū)結(jié)點；除了尾結(jié)點，每個結(jié)點都有且只有一個后繼結(jié)點。基本操作：InitList(&L)：構(gòu)造一個空的線性表L，即表的初始化。ListLength(L)：求線性表L中的結(jié)點個數(shù)，即求表長。GetNode(L,i)：取線性表L中的第i個結(jié)點，要求1≤i≤ListLength(L)。LocateNode(L,x)：在L中查找值為x的結(jié)點，并返回該結(jié)點在L中的位置。若L中有多個結(jié)點的值與x相同，則返回首次找到的結(jié)點位置；若L中沒有結(jié)點的值為x，則返回一個特殊值表示查找失敗。InsertList(&L,x,i)：在線性表L的第i個位置上插入一個值為x的新結(jié)點，使得原編號為i，i+1，…，n的結(jié)點變?yōu)榫幪枮閕+1，i+2，…，n+1的結(jié)點。這里1≤i≤n+1，n是原表L的長度。插入操作成功后表L的長度加1。DeleteList(&L,i)：刪除線性表L的第i個結(jié)點，使得原編號為i+1，i+2，…，n的結(jié)點變成編號為i，i+1，…，n-1的結(jié)點。這里1≤i≤n，n是原表L的長度。刪除操作成功后表L的長度減1。}ADTList2.3線性表的順序存儲結(jié)構(gòu)2.3.1順序表的結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)又稱順序表(SequentialList)。

順序表是用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素，即保持元素同構(gòu)且無缺項。

若每個數(shù)據(jù)元素占用c個存儲單元，并以所占的第一個存儲單元地址作為該數(shù)據(jù)元素的存儲位置，設(shè)表的最大長度為MaxSize，如圖2-2所示，則表中任一元素ai的存儲地址為：LOC(ai)=LOC(a1)+(i-1)*c

(1≤i≤n)

順序表為相鄰的元素ai和ai+1賦予相鄰的存儲位置LOC(ai)和LOC(ai+1)，即在線性表中邏輯關(guān)系相鄰的數(shù)據(jù)元素在內(nèi)存中的物理位置也是相鄰的。對于這種存儲方式，只要確定表頭結(jié)點的首地址，線性表中任一數(shù)據(jù)元素都可以隨機存取，所以順序表是一種隨機的存儲結(jié)構(gòu)。2.3.1順序表的結(jié)構(gòu)2.3.2順序表上實現(xiàn)的基本運算

在C語言中，可以采用結(jié)構(gòu)體類型來定義順序表類型，算法如下：/*順序表的定義*/#defineMaxSize80

/*表空間大小應(yīng)根據(jù)實際需要設(shè)定，這里假設(shè)為80*/typedefintDataType;/*DataType為數(shù)據(jù)元素的類型，可以是任何類型*/typedefstruct{

DataTypedata[MaxSize];/*data[]用于存放表結(jié)點*/

intlength;/*當前的表長度*/}SeqList;順序表的存儲結(jié)構(gòu)如圖2-3所示。1.建表

輸入給定的數(shù)組元素作為線性表的數(shù)據(jù)元素，將其傳入順序表中，并將傳入的元素個數(shù)作為順序表的長度建立順序表?！舅惴?-1】：voidCreateList(SeqList*L,DataTypea[],intn)/*建立順序表*/{

inti;

if(n>MaxSize)

{

printf("overflow");

/*如果n大于MaxSize，出現(xiàn)上溢*/

exit(0);

}

for(i=0;i<n;i++)/*為線性表的元素賦值*/

L->data[i]=a[i];

L->length=n;/*設(shè)置表中元素的個數(shù)*/}2.3.2順序表上實現(xiàn)的基本運算該算法的問題規(guī)模是表的長度n，基本語句是for循環(huán)中執(zhí)行元素賦值的語句，故時間復雜度為O(n)。

在日常工作中，根據(jù)實際情況可以設(shè)計多種建表方式，如通過鍵盤輸入數(shù)據(jù)或通過文件讀取數(shù)據(jù)等。下面為讀者提供從鍵盤輸入數(shù)據(jù)建立順序表的算法。【算法2-2】：voidCreateListB(SeqList*L)/*從鍵盤輸入數(shù)據(jù)，建立順序表*/{

inti,value;

i=0;

printf("請輸入數(shù)據(jù)，輸入9999時結(jié)束：\\n");

scanf("value=%d",&value);while(value!=9999)

{

if(i>MaxSize-1)

{

/*如果i大于MaxSize-1，出現(xiàn)上溢*/ printf("overflow");

exit(0);

}

L->data[i]=value;/*為線性表的元素賦值*/

i++;

scanf("value=%d",&value);

}

L->length=i;/*設(shè)置表中元素個數(shù)*/}2.3.2順序表上實現(xiàn)的基本運算2.插入

線性表的插入運算是指在線性表的第i個(1≤i≤n+1)位置上插入一個新元素x，使長度為n的線性表(a1,a2，…，ai,…,an)變成長度為n+1的線性表(a1,a2，…，ai-1，x，ai,…,an)。

在C語言中，數(shù)組下標從0開始依次存放數(shù)據(jù)元素，其完整插入過程如圖2-4所示。2.3.2順序表上實現(xiàn)的基本運算【算法2-3】：voidInsertList(SeqList*L,DataTypex,inti)/*將新結(jié)點x插入L所指順序表的第i個結(jié)點的位置上*/{

intj;

if(L->length==MaxSize)

/*表空間已滿，不能插入元素，退出運行*/

{

printf("表空間已滿，不能插入元素，退出運行。");

exit(0);

}

if(i<1||i>L->length+1)

/*插入位置錯誤，退出運行*/

{

printf("插入位置非法");

exit(0);

}

for(j=L->length-1;j>=i-1;j--)/*從表尾結(jié)點至第i個結(jié)點依次后移*/

L->data[j+1]=L->data[j];

L->data[i-1]=x;/*新元素賦值*/

L->length++;/*表長加1*/}該算法的問題規(guī)模是表的長度n，基本語句是for循環(huán)中執(zhí)行元素后移的語句。算法的平均時間復雜度為O(n)。2.3.2順序表上實現(xiàn)的基本運算3.刪除

線性表的刪除運算是指將線性表的第i個(1≤i≤n)位置上的元素刪除，使長度為n的線性表(a1,a2，…，ai,…,an)變成長度為n-1的線性表(a1,a2，…，ai-1，ai+1,…,an)。其刪除過程如圖2-5所示。2.3.2順序表上實現(xiàn)的基本運算【算法2-4】：voidDeleteList(SeqList*L,inti)/*從L所指的順序表中刪除第i個結(jié)點*/{

intj;

if(L->length==0)

{

printf("線性表為空，退出運行\(zhòng)\n");

exit(0);

}

if(i<1||i>L->length)

{

printf("刪除位置非法\\n");

exit(0);

}

for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j];

/*將自第i個元素之后的所有元素前移*/

L->length--;/*表長減1*/}該算法的問題規(guī)模是表長n，基本語句為for循環(huán)中元素前移的語句。在順序表上實現(xiàn)刪除操作，等概率情況下，平均要移動表中大約一半的數(shù)據(jù)元素，算法的平均時間復雜度為O(n)。2.3.2順序表上實現(xiàn)的基本運算4.查找

查找運算分為按值查找和按位查找。(1)按值查找

在順序表中實現(xiàn)按值查找操作，需要對順序表中的元素按照順序依次進行比較，如果查找成功，則返回元素的序號(注意：不是元素的下標)；否則，返回0。2.3.2順序表上實現(xiàn)的基本運算【算法2-5】：intLocateList(SeqListL,DataTypex)/*順序表按值查找*/{

inti=0;

while(i<L.length&&L.data[i]!=x)

++i;

/*如果查找成功，下標為i的元素等于x*/

if(i<L.length)

returni+1;/*返回找到元素的序號i+1*/

else

return0;/*找不到返回0*/}該算法的問題規(guī)模是表長n，基本語句為while循環(huán)中元素比較的語句。等概率情況下，平均要比較n/2個元素，該算法的平均時間復雜度為O(n)。2.3.2順序表上實現(xiàn)的基本運算(2)按位查找

根據(jù)順序表的隨機查找的特性，按位查找只需返回相應(yīng)位置的數(shù)據(jù)元素即可?！舅惴?-6】：DataTypeGetNode(SeqListL,inti)/*順序表按位查找*/{

if(i<1||i>L.length)

{

printf("查找位置非法");

exit(0);

}

else

returnL.data[i-1];

/*返回找到的值*/}按位查找算法的時間復雜度為O(1)。2.3.2順序表上實現(xiàn)的基本運算感謝支持本節(jié)結(jié)束第2章線性表（二）《數(shù)據(jù)結(jié)構(gòu)》（第四版）目錄CONTENTS線性表的鏈式存儲結(jié)構(gòu)2.4順序表與鏈表的比較2.5學習目標Learningtarget知識目標理解線性表的邏輯結(jié)構(gòu)特征。掌握順序表的含義、特點、基本運算和相關(guān)算法分析。掌握鏈表的含義、特點、基本運算和相關(guān)算法分析。理解循環(huán)鏈表和雙鏈表的邏輯結(jié)構(gòu)特征及基本運算。理解順序表和鏈表的比較。素質(zhì)目標理解針對實際問題選擇不同數(shù)據(jù)結(jié)構(gòu)解決方案的差異，引導學生運用具體問題具體分析的方法論分析問題、解決問題。軟件工程師應(yīng)具有選擇最優(yōu)方案的知識儲備，編寫出來的軟件才會得到用戶的喜歡。技能目標能應(yīng)用順序表的理論設(shè)計算法，解決實際問題。能應(yīng)用鏈表的理論設(shè)計算法，解決實際問題。2.4線性表的鏈式存儲結(jié)構(gòu)

順序表的特點是利用數(shù)據(jù)元素在物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這樣順序表就無須為表示結(jié)點間的邏輯關(guān)系而增加額外的空間，同時也可以直接存取表中的任一元素。

但它也有相應(yīng)的缺點：(1)插入和刪除操作需要移動大量的結(jié)點。(2)表的容量難以預(yù)先確定。在為長度變化較大的線性表預(yù)先分配空間時，只能按照最大空間需求分配，造成空間利用率低。(3)造成存儲空間的“碎片”。因為順序表存儲要求占用連續(xù)的存儲空間，即使空閑單元總數(shù)超過了表的容量，如果不連續(xù)，也無法使用。

鑒于順序表的這些不足，我們考慮線性表的鏈式存儲結(jié)構(gòu)。2.4.1鏈表的結(jié)構(gòu)

線性表的鏈式存儲結(jié)構(gòu)簡稱鏈表(LinkedList)，是用一組任意的存儲單元存儲該線性表中的各個數(shù)據(jù)元素，存儲單元可以連續(xù)，也可以不連續(xù)。因此，鏈表中數(shù)據(jù)元素的邏輯次序和物理次序不一定相同。

為了能體現(xiàn)元素間的邏輯順序，每個結(jié)點除了存儲數(shù)據(jù)元素的信息外，還要存儲其后繼元素所在的地址信息。因此，一個鏈表結(jié)點由兩個域構(gòu)成：存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域(data)；存儲直接后繼存儲位置的域稱為指針域(next)。

鏈表通過每個結(jié)點中的指針域?qū)⒕€性表的各個結(jié)點按邏輯順序鏈接在一起。若鏈表的每個結(jié)點中只有一個指針域，這種鏈表稱為單鏈表(SingleLinkedList)，結(jié)點結(jié)構(gòu)如圖2-6所示。

線性表(a1,a2，a3,a4)的鏈式存儲結(jié)構(gòu)如圖2-7(a)所示，但用這種方法表示單鏈表很不方便，而且用戶也沒必要關(guān)心線性表中每個數(shù)據(jù)元素的實際內(nèi)存地址，因此通常采用如圖2-7(b)所示的形式表示單鏈表的邏輯關(guān)系。2.4.1鏈表的結(jié)構(gòu)

鏈表的存取要從頭指針head開始，頭指針指示鏈表中第一個結(jié)點(稱為首結(jié)點)的存儲位置；鏈表的最后一個結(jié)點稱為尾結(jié)點，由于其沒有直接后繼，尾結(jié)點的指針域為空(NULL)，用“∧”表示。線性表(a1,a2，…，ai,…,an)的單鏈表如圖2-8所示。2.4.1鏈表的結(jié)構(gòu)

為了方便操作，在單鏈表第一個結(jié)點之前附加一個同結(jié)構(gòu)的結(jié)點，稱為頭結(jié)點(front)或表頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以空閑，也可以用來存儲如線性表長度等附加信息，但實際使用時要考慮結(jié)點數(shù)據(jù)域的數(shù)據(jù)類型設(shè)置。增加了頭結(jié)點的單鏈表，鏈表頭指針在空表和非空表中的處理便統(tǒng)一了，鏈表的首結(jié)點也不必再進行特殊處理。帶頭結(jié)點的單鏈表如圖2-9所示。2.4.1鏈表的結(jié)構(gòu)2.4.2單鏈表上實現(xiàn)的基本運算

在C語言中，單鏈表可以定義如下：/*單鏈表的定義*/typedefintDataType;/*DataType為數(shù)據(jù)元素的類型，可以是任何類型*/typedefstructnode

/*結(jié)點類型定義*/{DataTypedata;

/*結(jié)點的數(shù)據(jù)域*/structnode*next;

/*結(jié)點的指針域*/}ListNode;typedefListNode*LinkList;1.建表

鏈表的建立有頭插法建表和尾插法建表兩種方式。(1)頭插法建表

頭插法建立鏈表是將新生成的結(jié)點插入現(xiàn)有鏈表首結(jié)點之前，無頭結(jié)點的單鏈表和帶頭結(jié)點的單鏈表頭插法建表算法如下：【算法2-7】：LinkListCreateListF1(void)/*用頭插法建無頭結(jié)點的單鏈表*/{

intvalue;

LinkListhead=NULL;

/*設(shè)置頭指針*/

ListNode*p;/*p用于指向新結(jié)點*/

printf("輸入9999，結(jié)束輸入！\\n");

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);/*輸入數(shù)據(jù)值*/while(value!=9999)

{

p=(ListNode*)malloc(sizeof(ListNode));/*生成新結(jié)點*/

if(!p)/*如果新結(jié)點申請空間不成功，退出*/

exit(-1);

p->data=value;/*為新結(jié)點賦值*/

/*新結(jié)點的指針指向原有鏈表首結(jié)點*/p->next=head;

head=p;/*頭指針指向新結(jié)點*/

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);

}

returnhead;/*返回頭指針*/}2.4.2單鏈表上實現(xiàn)的基本運算【算法2-8】：LinkListCreateListF2(void)/*用頭插法建帶頭結(jié)點的單鏈表*/{

intvalue;

LinkListhead;

/*設(shè)置頭指針*/

ListNode*p;/*p用于指向新結(jié)點*/

head=(ListNode*)malloc(sizeof(ListNode));/*初始化一個空鏈表*/

head->next=NULL;

printf("輸入9999，結(jié)束輸入！\\n");

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);/*輸入數(shù)據(jù)值*/

while(value!=9999)

{

p=(ListNode*)malloc(sizeof(ListNode));/*生成新結(jié)點*/

if(!p)/*如果新結(jié)點申請空間不成功，退出*/

exit(-1);

p->data=value;/*為新結(jié)點賦值*/

p->next=head->next;/*新結(jié)點的指針指向原有鏈表首結(jié)點*/

head->next=p;/*頭結(jié)點的指針指向新結(jié)點*/

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);

}

returnhead;/*返回頭指針*/}2.4.2單鏈表上實現(xiàn)的基本運算以帶頭結(jié)點單鏈表的頭插法為例，具體操作過程如圖2-10所示。2.4.2單鏈表上實現(xiàn)的基本運算(2)尾插法建表

尾插法建立鏈表是將新生成的結(jié)點鏈接到現(xiàn)有表的尾結(jié)點之后。無頭結(jié)點的單鏈表和帶頭結(jié)點的單鏈表尾插法建表算法如下：【算法2-9】：LinkListCreateListR1(void)/*用尾插法建無頭結(jié)點的單鏈表*/{

intvalue;

LinkListhead=NULL;

/*設(shè)置頭指針*/

ListNode*p,*r;/*p用于指向新結(jié)點，r用于指向表尾結(jié)點*/

r=NULL;

printf("輸入9999，結(jié)束輸入！\\n");

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);/*輸入數(shù)據(jù)值*/

while(value!=9999)

{

p=(ListNode*)malloc(sizeof(ListNode));/*生成新結(jié)點*/

if(!p)/*如果新結(jié)點申請空間不成功，退出*/

exit(-1);

p->data=value;

/*為新結(jié)點賦值*/

if(head==NULL)

head=p;/*新結(jié)點插入空表*/

else

r->next=p;/*新結(jié)點接在表尾*/

r=p;/*r指向新結(jié)點*/

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);

}

if(r!=NULL)

r->next=NULL;/*表尾結(jié)點指針置空*/

returnhead;/*返回頭指針*/}2.4.2單鏈表上實現(xiàn)的基本運算【算法2-10】：LinkListCreateListR2(void)/*用尾插法建帶頭結(jié)點的單鏈表*/{

intvalue;

LinkListhead;

/*設(shè)置頭指針*/

ListNode*p,*r;/*p用于指向新結(jié)點，r用于指向表尾結(jié)點*/

head=(ListNode*)malloc(sizeof(ListNode));/*生成頭結(jié)點*/

r=head;

printf("輸入9999，結(jié)束輸入！\\n");

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);/*輸入數(shù)據(jù)值*/

while(value!=9999)

{

p=(ListNode*)malloc(sizeof(ListNode));/*生成新結(jié)點*/

if(!p)/*如果新結(jié)點申請空間不成功，退出*/

exit(-1);p->data=value;/*為新結(jié)點賦值*/

r->next=p;/*新結(jié)點接在表尾*/

r=p;/*r指向新結(jié)點*/

printf("請輸入數(shù)據(jù)值：\\n");

scanf("%d",&value);

}

r->next=NULL;/*表尾結(jié)點指針置空*/

returnhead;/*返回頭指針*/}2.4.2單鏈表上實現(xiàn)的基本運算以帶頭結(jié)點單鏈表的尾插法為例，具體操作過程如圖2-11所示。

以上四種建表算法中，問題規(guī)模都取決于表長n，基本語句為while循環(huán)中新結(jié)點插入的語句。因此，算法的平均時間復雜度均為O(n)。2.4.2單鏈表上實現(xiàn)的基本運算2.插入

將新元素x插入鏈表中的數(shù)據(jù)元素ai-1

和ai之間，實現(xiàn)鏈表的插入運算。

具體步驟如圖2-12所示。2.4.2單鏈表上實現(xiàn)的基本運算【算法2-11】：voidInsertList(LinkListhead,DataTypex,inti)/*將值為x的新結(jié)點插入帶頭結(jié)點的單鏈表head的第i個結(jié)點的位置上*/{

intj;

/*j用于記錄當前結(jié)點位置*/

ListNode*p,*r;

r=head;

j=0;

while(r->next&&j<i-1)/*尋找第i-1個結(jié)點*/

{

r=r->next;

j++;

}if(j!=i-1)

{

printf("插入位置非法\\n");

exit(0);

}

p=(ListNode*)malloc(sizeof(ListNode));

/*生成新結(jié)點*/

if(!p)/*如果新結(jié)點申請空間不成功，退出*/

exit(-1);

p->data=x;/*為新結(jié)點p賦值x*/

p->next=r->next;/*插入結(jié)點p*/

r->next=p;/*修改r的指針*/}本算法的問題規(guī)模是表長n，基本語句為while循環(huán)中用于尋找第i-1個結(jié)點的語句。因此，算法的平均時間復雜度為O(n)。2.4.2單鏈表上實現(xiàn)的基本運算3.刪除

如果要刪除單鏈表中的數(shù)據(jù)元素ai，需要找到指向待刪除元素的指針p及指向其直接前驅(qū)結(jié)點的指針r，再將r的next指針指向p的后繼，最后釋放結(jié)點p。操作步驟如圖2-13所示。2.4.2單鏈表上實現(xiàn)的基本運算【算法2-12】：voidDeleteList(LinkListhead,DataTypex)/*刪除帶頭結(jié)點的單鏈表中值等于x的結(jié)點*/{

ListNode*p,*r;

/*p指向查找的結(jié)點，r指向p的前驅(qū)結(jié)點*/

r=head;

p=head->next;

while(p&&p->data!=x)/*查找值等于x的結(jié)點*/

{

p=p->next;

r=r->next;

}

if(p==NULL)/*如果p為空，查找失敗*/

{

printf("待刪除結(jié)點不存在！\\n");

exit(0);

}

r->next=p->next;/*r的next指針指向p的后繼*/

free(p);/*釋放結(jié)點p*/}本算法的問題規(guī)模是表長n，基本語句為while循環(huán)中用于查找值等于x的結(jié)點的語句。算法的平均時間復雜度為O(n)。2.4.2單鏈表上實現(xiàn)的基本運算4.查找

單鏈表上的查找與順序表的查找不同，不能實現(xiàn)隨機查找。若要找到某個元素，只能從表頭開始查找，屬于順序查找。(1)按值查找【算法2-13】：LinkListLocNode(LinkListhead,DataTypex)/*在帶頭結(jié)點的單鏈表head中查找其值為x的結(jié)點*/{

/*設(shè)置比較的指針r從鏈表首結(jié)點開始*/

ListNode*r=head->next;

while(r&&r->data!=x)/*直到r為NULL或r->data等于x為止*/

r=r->next;

returnr;}2.4.2單鏈表上實現(xiàn)的基本運算（2）按位查找LinkListGetNode(LinkListhead,inti)/*在帶頭結(jié)點的單鏈表head中查找第i個結(jié)點*/{

if(i<1)

/*如果i小于1，查找位置不合理，返回NULL*/

{

printf("查找位置不合理！\\n");

returnNULL;

}

intj=0;

/*設(shè)置計數(shù)器j，賦初值為0*/

ListNode*r=head;

while(r->next&&j<i)/*直到r->next為NULL或j等于i為止*/

{

r=r->next;

j++;

}

if(j==i)

returnr;

else

returnNULL;}兩種查找都需要從表頭結(jié)點依次向后比較，因此問題規(guī)模均為表長n，時間復雜度均為O(n)。2.4.2單鏈表上實現(xiàn)的基本運算2.4.3循環(huán)鏈表

將單鏈表中的最后一個結(jié)點的指針指向鏈表中的第一個結(jié)點，使整個鏈表構(gòu)成一個環(huán)形，這種鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表(CircularLinkedList)。從循環(huán)鏈表中的任意一個結(jié)點出發(fā)都可以找到表中的其他結(jié)點。為了使空表與非空表的處理統(tǒng)一，通常循環(huán)鏈表也附設(shè)一個頭結(jié)點，如圖2-14所示。

在循環(huán)鏈表中，從表中任一結(jié)點p出發(fā)，均可以找到其直接前驅(qū)結(jié)點。算法如下：【算法2-15】：LinkListprior(ListNode*p)/*求循環(huán)鏈表中任意一個結(jié)點的前驅(qū)結(jié)點*/{

ListNode*s;

s=p->next;

/*初始化s為p的直接后繼*/

while(s->next!=p)/*當s的直接后繼為p時，s是p的直接前驅(qū)*/

s=s->next;

returns;}

本算法的時間復雜度為O(n)。2.4.3循環(huán)鏈表2.4.4雙鏈表

在單鏈表和循環(huán)鏈表中，數(shù)據(jù)元素的結(jié)點除數(shù)據(jù)域外，只有一個指向其直接后繼的指針域，若要查找其前驅(qū)結(jié)點就需要遍歷鏈表。為了解決這種單向性的問題，可以在單鏈表的結(jié)點中增加一個指向其直接前驅(qū)結(jié)點的指針域，這樣有兩種不同方向鏈的鏈表就稱為雙(向)鏈表(DoubleLinkedList)，其結(jié)點結(jié)構(gòu)如圖2-15(a)所示。

給雙鏈表添加一個表頭結(jié)點成為帶表頭結(jié)點的雙鏈表，如圖2-15(b)所示。如果每條鏈都構(gòu)成循環(huán)鏈表，就形成了雙循環(huán)鏈表，如圖2-15(c)所示。

由于雙鏈表的對稱結(jié)構(gòu)，其插入和刪除操作都很容易。雙鏈表有一個重要的特點，若p是指向表中任一結(jié)點的指針，則有：(p->next)->prior==(p->prior)->next==p在C語言中，雙鏈表可以定義如下：/*雙鏈表的定義：*/typedefintDataType;

/*DataType為數(shù)據(jù)元素的類型，可以是任何類型*/typedefstructDnode/*結(jié)點類型定義*/{

DataTypedata;/*結(jié)點的數(shù)據(jù)域*/

structDnode*prior;/*結(jié)點的前驅(qū)指針域*/

structDnode*next;/*結(jié)點的后繼指針域*/}DulListNode;typedefDulListNode*DulLinkList;2.4.4雙鏈表1.插入在雙鏈表中結(jié)點s的后面插入新結(jié)點p，需要修改四個指針：①p->prior=s;②p->next=s->next;③s->next->prior=p;④s->next=p;第②和③步的操作順序可以互換。操作步驟如圖2-16所示。2.4.4雙鏈表2.刪除在雙鏈表中刪除結(jié)點s，可以采用如下語句完成：①s->next->prior=s->prior;②s->prior->next=s->next;③free(s);第①和②步可以互換，如圖2-17所示。2.4.4雙鏈表2.5順序表與鏈表的比較考慮時間因素考慮空間因素考慮程序設(shè)計語言順序表查找運算是隨機操作，對表中任一結(jié)點都可以直接存取。存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確定義其存儲規(guī)模。從計算機程序語言看，絕大多數(shù)高級語言都提供數(shù)組類型，因此順序表的實現(xiàn)相對簡單一些。鏈表鏈表中的結(jié)點需要從頭指針起沿著鏈表遍歷才能找到。鏈表的存儲空間是動態(tài)分配的，只要系統(tǒng)內(nèi)存尚有空閑，就不會產(chǎn)生溢出。若無指針類型，則可以采用靜態(tài)鏈表的方法來模擬動態(tài)存儲結(jié)構(gòu)。選擇場景當線性表的操作主要是進行查找，很少做插入和刪除操作時，宜采用順序表作為存儲結(jié)構(gòu)；對于頻繁進行插入和刪除的線性表，宜采用鏈表作為存儲結(jié)構(gòu)；若表的插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表作為存儲結(jié)構(gòu)。當線性表的長度變化較大，難以估計其存儲規(guī)模時，宜采用動態(tài)鏈表作為存儲結(jié)構(gòu)；當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。根據(jù)具體實現(xiàn)的語言進行選擇。感謝支持本章結(jié)束第3章棧和隊列（一）《數(shù)據(jù)結(jié)構(gòu)》（第四版）目錄CONTENTS案例導引3.1棧3.2學習目標Learningtarget知識目標理解棧的邏輯結(jié)構(gòu)特征以及棧與線性表的異同。理解隊列的邏輯結(jié)構(gòu)特征以及隊列與線性表的異同。掌握順序棧及鏈棧的進棧、出棧等基本算法和相關(guān)分析。掌握順序隊列及鏈隊列的入隊、出隊等基本算法和相關(guān)分析。素質(zhì)目標學習棧和隊列的邏輯結(jié)構(gòu)，理解規(guī)則的重要性，幫助學生樹立正確的世界觀和價值觀。技能目標能夠應(yīng)用棧的理論設(shè)計算法，解決實際問題。能夠應(yīng)用隊列的理論設(shè)計算法，解決實際問題。3.1案例導引案例1：漢諾塔問題。

傳說所羅門廟里有一個塔臺，臺上有三根用鉆石做成的標號分別為A、B和C的柱子，在A柱上放著64個金盤，每一個金盤都比下面的略小一點。把A柱上的金盤全部移到C柱上的那一天就是世界末日。移動的條件是，一次只能移動一個金盤，移動過程中大金盤不能放在小金盤上面。編寫程序求出n個金盤移動的次數(shù)。案例探析：

設(shè)移動次數(shù)為H(n)。分析題目要求，首先我們要把A柱上面的n-1個金盤移動到B柱上，然后把最大的一塊放在C柱上，最后把B柱上的所有金盤移動到C柱上，由此得出表達式：H(1)=1H(n)=2*H(n-1)+1(n>1)那么我們就能得到H(n)的一般式：H(n)=2n-1(n>0)

這是一個后進先出的過程，可以采用棧結(jié)構(gòu)來實現(xiàn)。案例2：機器翻譯。

某機器翻譯軟件的實現(xiàn)原理為：從頭到尾依次將文中每個英文單詞用對應(yīng)的中文含義來替換。對于文中的每個英文單詞，該軟件先在內(nèi)存中進行查找，如果內(nèi)存中有，就使用對應(yīng)的中文含義替換；如果內(nèi)存中沒有，軟件就會到外存的詞典內(nèi)查找該單詞，然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。3.2棧的邏輯結(jié)構(gòu)3.2.1棧的邏輯結(jié)構(gòu)1.棧的定義

棧(Stack)是運算受限的線性表，只允許在表的一端進行插入和刪除操作。允許插入和刪除的一端稱為棧頂(Top)，棧頂將隨著棧中數(shù)據(jù)元素的插入和刪除而動態(tài)變化，通過棧頂指針表示當前數(shù)據(jù)元素的位置。另一端稱為棧底(Bottom)，棧底是固定的。當表中沒有數(shù)據(jù)元素時，稱為空棧。棧如圖3-1所示。

在棧S=(a1,a2,…,an)中，a1稱為棧底元素，an稱為棧頂元素。在棧頂插入元素稱為入棧(或進棧、壓棧)，刪除棧頂元素稱為出棧(或退棧、彈棧)。棧中的數(shù)據(jù)元素按后進先出的原則操作。因此，棧又稱為“后進先出”(LastInFirstOut)表，簡稱LIFO表。在軟件應(yīng)用中，棧的使用非常普遍。例如，瀏覽器中的“后退”按鈕，用戶單擊該按鈕后就可以按照訪問順序的逆序加載瀏覽過的網(wǎng)頁。3.2.1棧的邏輯結(jié)構(gòu)2.棧的抽象數(shù)據(jù)類型定義

棧的抽象數(shù)據(jù)類型表示了棧中的數(shù)據(jù)對象、數(shù)據(jù)關(guān)系以及基本操作，定義如下：ADTStack{數(shù)據(jù)對象：S={ai|ai為DataType類型，1≤i≤n，n≥0}/*DataType為自定義類型*/數(shù)據(jù)關(guān)系：R={<ai-1，ai>|ai-1，ai∈D，2≤i≤n}。在非空表中，除了首結(jié)點，每個結(jié)點都有且只有一個前驅(qū)結(jié)點；除了尾結(jié)點外，每個結(jié)點都有且只有一個后繼結(jié)點。棧中的數(shù)據(jù)元素只能在棧頂一端進行插入和刪除操作?；静僮鳎篒nitStack(&S)：構(gòu)造一個空棧，即棧的初始化。StackEmpty(&S)：判?？?。若棧為空，返回1；否則，返回0。StackFull(&S)：判棧滿。若棧滿，返回1；否則，返回0。Push(&S,x)：入棧。將元素x插入為新的棧頂元素。Pop(&S,&x)：出棧。刪除棧S的棧頂元素，用x返回棧頂元素值。GetTop(&S,&x)：取棧頂元素。用x返回棧頂元素值。}ADTStack3.2.1棧的邏輯結(jié)構(gòu)3.2.2順序棧1.順序棧

棧的順序存儲結(jié)構(gòu)稱為順序棧(SequentialStack)，利用一組地址連續(xù)的存儲空間依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素。與順序表類似，順序棧采用一維數(shù)組實現(xiàn)?？梢圆捎脭?shù)組的任意一端作為棧底，通常設(shè)定數(shù)組中下標為0的一端作為棧底，同時設(shè)定指針top用于指示當前棧頂?shù)奈恢谩ｍ樞驐５念愋投x如下：#defineStackSize100

/*設(shè)定棧的長度，可根據(jù)實際問題具體定義*/typedefintDataType;typedefstruct{

DataTypeStack[StackSize];

inttop;/*設(shè)定棧頂指針*/}SeqStack;

當棧中沒有元素時為空棧，top==-1；當棧中放滿數(shù)據(jù)元素時，top==StackSize-1，表示棧滿。入棧時，先使棧頂指針top加1，再放入數(shù)據(jù)元素；出棧時，先讀取棧頂元素，再將棧頂指針top減1。棧的操作如圖3-2所示。

在棧的操作過程中，棧滿時做進棧操作會出現(xiàn)空間溢出，稱為上溢，這是一種出錯狀態(tài)，應(yīng)該避免。在棧空時做出棧操作產(chǎn)生的溢出稱為下溢，這是正?，F(xiàn)象，是程序控制轉(zhuǎn)移的條件。3.2.2順序棧2.順序棧的實現(xiàn)(1)棧的初始化

棧的初始化就是置空棧，只需把top指針置為-1即可?！舅惴?-1】：voidInitStack(SeqStack*S)/*棧的初始化*/{

S->top=-1;}(2)判?？?/p>

判斷棧是否為空，就是要判斷top指針是否為-1?！舅惴?-2】：intStackEmpty(SeqStack*S)/*判棧空*/{

returnS->top==-1;

/*當棧為空時，返回1；否則，返回0*/}(3)判棧滿

判斷棧是否已滿，需要判斷top指針是否達到了數(shù)組上限?！舅惴?-3】：intStackFull(SeqStack*S)/*判棧滿*/{

returnS->top==StackSize-1;

/*當棧滿時，返回1；否則，返回0*/}3.2.2順序棧(4)入棧

先將棧頂指針加1，再將元素x插入為新的棧頂元素，完成入棧操作。【算法3-4】：voidPush(SeqStack*S,DataTypex)/*入棧*/{

if(StackFull(s))

/*棧滿時，不能再做入棧操作*/

{

printf("棧已滿，不能入棧！");

exit(0);

}

S->top++;/*棧頂指針加1*/

S->Stack[S->top]=x;/*輸入新的棧頂元素*/}(5)出棧

刪除棧S的棧頂元素，用x返回其值，棧頂指針減1?！舅惴?-5】：voidPop(SeqStack*S,DataType*x)/*出棧*/{

if(StackEmpty(S))/*?？諘r，不能再做出棧操作*/

{

printf("棧已空，不能出棧！");

exit(0);

}

*x=S->Stack[S->top];/*將棧頂元素取出*/

S->top--;/*棧頂指針減1*/}3.2.2順序棧(6)取棧頂元素(讀棧)

用x返回棧S的棧頂元素。【算法3-6】：voidGetTop(SeqStack*S,DataType*x)/*取棧頂元素*/{

if(StackEmpty(S))/*?？諘r，無棧頂元素*/

{

printf("棧為空！");

exit(0);

}

*x=S->Stack[S->top];/*將棧頂元素取出*/}3.2.2順序棧1.鏈棧定義

棧的鏈式存儲結(jié)構(gòu)稱為鏈棧(LinkedStack)。鏈棧是運算受限的單鏈表，其插入和刪除操作都限定在表頭位置上進行。棧頂指針就是鏈表的頭指針，用來唯一確定一個鏈棧。

鏈?？梢杂蓄^結(jié)點，也可以沒有頭結(jié)點。因為以單鏈表的頭部做棧頂是最方便的，所以通常選用無頭結(jié)點的單鏈表表示鏈棧，如圖3-4所示。3.2.3鏈棧鏈棧的類型定義如下：typedefstructStackNode{DataTypedata;structStackNode*next;}StackNode,*LinkStack;2.鏈棧的實現(xiàn)(1)鏈棧的初始化【算法3-11】：voidLInitStack(LinkStack*top)/*鏈棧初始化*/{

*top=NULL;}(2)判斷鏈棧是否為空【算法3-12】：intLStackEmpty(LinkStacktop)/*判斷鏈棧是否為空*/{if(top==NULL)/*?？辗祷?；否則，返回0*/return1;elsereturn0;}(3)入?！舅惴?-13】：intLPush(LinkStack*top,DataTypex)/*鏈棧的入棧操作*/{

StackNode*p;

p=(StackNode*)malloc(sizeof(StackNode));

/*生成新結(jié)點*/

if(!p)

{

printf("入棧操作出錯!\\n");

exit(-1);

}

p->data=x;

p->next=*top;

*top=p;

return1;}3.2.3鏈棧(4)出棧【算法3-14】：intLPop(LinkStack*top,DataType*x)/*鏈棧的出棧操作*/{

StackNode*p;

if(!(*top))

{

printf("棧已空!\\n");

exit(0);

}

p=*top;

/*p指向棧頂元素*/

*top=p->next;/*將棧頂結(jié)點從鏈上取下，即出棧*/

*x=p->data;

/*將棧頂元素值賦給指針x所指的變量x*/

free(p);/*釋放p指向的結(jié)點*/

return1;}(5)取棧頂元素(讀棧)【算法3-15】：intLGetPop(LinkStacktop,DataType*x)/*鏈棧的讀棧操作*/{

if(!top)

{

printf("棧已空!\\n");

exit(0);

}

*x=top->data;

/*將棧頂元素值賦給指針x所指的變量x*/

return1;}3.2.3鏈棧(1)時間性能：因為棧的所有操作都在棧頂進行，所以順序棧和鏈棧的基本操作的算法都只需要常數(shù)階的時間。(2)空間性能：順序棧初始化時需要設(shè)定一個固定的長度，當數(shù)據(jù)元素過多時可能出現(xiàn)上溢現(xiàn)象，數(shù)據(jù)元素較少時又存在空間浪費的現(xiàn)象。鏈棧只有在內(nèi)存空間不足時才會出現(xiàn)棧滿的問題，但因為每個元素結(jié)點都需要指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。

因此，棧的使用過程中如果元素個數(shù)變化較大宜選用鏈棧；反之，宜選用順序棧。3.2.4順序棧和鏈棧的比較3.2.5棧的應(yīng)用1.遞歸——階乘問題

棧的一個重要應(yīng)用就是在程序設(shè)計語言中實現(xiàn)遞歸。棧是嵌套調(diào)用機制的實現(xiàn)基礎(chǔ)。

遞歸就是子程序(或函數(shù))直接或間接調(diào)用自己的算法。也就是說，遞歸函數(shù)的調(diào)用是函數(shù)在執(zhí)行過程中進行多次的自我嵌套調(diào)用。遞歸算法是程序設(shè)計中的常用算法之一，可以使程序設(shè)計簡單精練、結(jié)構(gòu)清晰、容易實現(xiàn)。

遞歸通常用于解決結(jié)構(gòu)自相似的問題。遞歸有兩個組成部分：一是遞歸終止條件；二是遞歸模式。

過程調(diào)用的執(zhí)行步驟為：(1)記錄調(diào)用過程結(jié)束時的返回地址以及前一次調(diào)用過程中的數(shù)據(jù)