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

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

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

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

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

瑞士計(jì)算機(jī)科學(xué)家沃斯(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ù)語(yǔ)1.數(shù)據(jù)

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

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

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

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

數(shù)據(jù)類型(DataType)是一組性質(zhì)相同的值的集合和定義在該值集上的一組操作的總稱。每個(gè)數(shù)據(jù)項(xiàng)屬于某一確定的數(shù)據(jù)類型。按“值”的特性不同，高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型可以分為兩類：(1)原子類型：其值不可分解。例如，C語(yǔ)言中的整型、實(shí)型和字符型等。(2)結(jié)構(gòu)類型：其值通?？梢苑纸獬蔀槿舾蓚€(gè)成分。它的成分可以是非結(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ù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。算法的設(shè)計(jì)取決于選定的數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，實(shí)現(xiàn)在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上。1.3.1基本概念和術(shù)語(yǔ)1.3.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是獨(dú)立于計(jì)算機(jī)系統(tǒng)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。1.線性結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

一個(gè)好的算法首先要便于人們閱讀、理解，其次才是計(jì)算機(jī)可以執(zhí)行?？勺x性是軟件開(kāi)發(fā)的一項(xiàng)重要原則，算法的可讀性好，則其可維護(hù)性也強(qiáng)。(3)健壯性

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

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

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

流程圖的優(yōu)點(diǎn)是直觀，但靈活性不如自然語(yǔ)言，對(duì)復(fù)雜的流程不易表達(dá)。(3)程序設(shè)計(jì)語(yǔ)言

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

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

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

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

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

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

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

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

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

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

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

sum=0;

while(sum<n)

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

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

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

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

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

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

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

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

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

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

其中，ai(1≤i≤n)稱為表中的第i個(gè)數(shù)據(jù)元素，下標(biāo)i表示該元素在線性表中的位置。任意一對(duì)相鄰的數(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é)點(diǎn)，它沒(méi)有直接前驅(qū)，只有一個(gè)直接后繼。(2)存在唯一的數(shù)據(jù)元素an，或稱尾結(jié)點(diǎn)，它沒(méi)有直接后繼，只有一個(gè)直接前驅(qū)。(3)除第一個(gè)結(jié)點(diǎn)(首結(jié)點(diǎn))之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)。(4)除最后一個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn))之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼。

線性表中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，數(shù)據(jù)元素可以是簡(jiǎn)單數(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ù)類型定義

線性表的長(zhǎng)度可以隨著數(shù)據(jù)元素的插入和刪除等操作而增加或減少，是一種靈活的數(shù)據(jù)結(jié)構(gòu)。線性表的抽象數(shù)據(jù)類型定義如下：ADTList{數(shù)據(jù)對(duì)象：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é)點(diǎn)，每個(gè)結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；除了尾結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都有且只有一個(gè)后繼結(jié)點(diǎn)?；静僮鳎篒nitList(&L)：構(gòu)造一個(gè)空的線性表L，即表的初始化。ListLength(L)：求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。GetNode(L,i)：取線性表L中的第i個(gè)結(jié)點(diǎn)，要求1≤i≤ListLength(L)。LocateNode(L,x)：在L中查找值為x的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在L中的位置。若L中有多個(gè)結(jié)點(diǎn)的值與x相同，則返回首次找到的結(jié)點(diǎn)位置；若L中沒(méi)有結(jié)點(diǎn)的值為x，則返回一個(gè)特殊值表示查找失敗。InsertList(&L,x,i)：在線性表L的第i個(gè)位置上插入一個(gè)值為x的新結(jié)點(diǎn)，使得原編號(hào)為i，i+1，…，n的結(jié)點(diǎn)變?yōu)榫幪?hào)為i+1，i+2，…，n+1的結(jié)點(diǎn)。這里1≤i≤n+1，n是原表L的長(zhǎng)度。插入操作成功后表L的長(zhǎng)度加1。DeleteList(&L,i)：刪除線性表L的第i個(gè)結(jié)點(diǎn)，使得原編號(hào)為i+1，i+2，…，n的結(jié)點(diǎn)變成編號(hào)為i，i+1，…，n-1的結(jié)點(diǎn)。這里1≤i≤n，n是原表L的長(zhǎng)度。刪除操作成功后表L的長(zhǎng)度減1。}ADTList2.3線性表的順序存儲(chǔ)結(jié)構(gòu)2.3.1順序表的結(jié)構(gòu)

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

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

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

(1≤i≤n)

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

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

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

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

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

輸入給定的數(shù)組元素作為線性表的數(shù)據(jù)元素，將其傳入順序表中，并將傳入的元素個(gè)數(shù)作為順序表的長(zhǎng)度建立順序表?！舅惴?-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è)置表中元素的個(gè)數(shù)*/}2.3.2順序表上實(shí)現(xiàn)的基本運(yùn)算該算法的問(wèn)題規(guī)模是表的長(zhǎng)度n，基本語(yǔ)句是for循環(huán)中執(zhí)行元素賦值的語(yǔ)句，故時(shí)間復(fù)雜度為O(n)。

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

inti,value;

i=0;

printf("請(qǐng)輸入數(shù)據(jù)，輸入9999時(shí)結(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è)置表中元素個(gè)數(shù)*/}2.3.2順序表上實(shí)現(xiàn)的基本運(yùn)算2.插入

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

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

intj;

if(L->length==MaxSize)

/*表空間已滿，不能插入元素，退出運(yùn)行*/

{

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

exit(0);

}

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

/*插入位置錯(cuò)誤，退出運(yùn)行*/

{

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

exit(0);

}

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

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

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

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

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

intj;

if(L->length==0)

{

printf("線性表為空，退出運(yùn)行\(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個(gè)元素之后的所有元素前移*/

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

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

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

inti=0;

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

++i;

/*如果查找成功，下標(biāo)為i的元素等于x*/

if(i<L.length)

returni+1;/*返回找到元素的序號(hào)i+1*/

else

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

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

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

{

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

exit(0);

}

else

returnL.data[i-1];

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

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

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

鑒于順序表的這些不足，我們考慮線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2.4.1鏈表的結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

intvalue;

LinkListhead=NULL;

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

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

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

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

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

{

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

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

exit(-1);

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

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

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

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

scanf("%d",&value);

}

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

intvalue;

LinkListhead;

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

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

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

head->next=NULL;

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

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

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

while(value!=9999)

{

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

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

exit(-1);

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

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

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

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

scanf("%d",&value);

}

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

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

intvalue;

LinkListhead=NULL;

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

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

r=NULL;

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

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

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

while(value!=9999)

{

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

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

exit(-1);

p->data=value;

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

if(head==NULL)

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

else

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

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

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

scanf("%d",&value);

}

if(r!=NULL)

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

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

intvalue;

LinkListhead;

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

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

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

r=head;

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

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

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

while(value!=9999)

{

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

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

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

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

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

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

scanf("%d",&value);

}

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

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

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

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

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

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

intj;

/*j用于記錄當(dāng)前結(jié)點(diǎn)位置*/

ListNode*p,*r;

r=head;

j=0;

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

{

r=r->next;

j++;

}if(j!=i-1)

{

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

exit(0);

}

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

/*生成新結(jié)點(diǎn)*/

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

exit(-1);

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

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

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

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

ListNode*p,*r;

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

r=head;

p=head->next;

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

{

p=p->next;

r=r->next;

}

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

{

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

exit(0);

}

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

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

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

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

ListNode*r=head->next;

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

r=r->next;

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

if(i<1)

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

{

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

returnNULL;

}

intj=0;

/*設(shè)置計(jì)數(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é)點(diǎn)依次向后比較，因此問(wèn)題規(guī)模均為表長(zhǎng)n，時(shí)間復(fù)雜度均為O(n)。2.4.2單鏈表上實(shí)現(xiàn)的基本運(yùn)算2.4.3循環(huán)鏈表

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

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

ListNode*s;

s=p->next;

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

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

s=s->next;

returns;}

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

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

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

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

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

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

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

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

傳說(shuō)所羅門(mén)廟里有一個(gè)塔臺(tái)，臺(tái)上有三根用鉆石做成的標(biāo)號(hào)分別為A、B和C的柱子，在A柱上放著64個(gè)金盤(pán)，每一個(gè)金盤(pán)都比下面的略小一點(diǎn)。把A柱上的金盤(pán)全部移到C柱上的那一天就是世界末日。移動(dòng)的條件是，一次只能移動(dòng)一個(gè)金盤(pán)，移動(dòng)過(guò)程中大金盤(pán)不能放在小金盤(pán)上面。編寫(xiě)程序求出n個(gè)金盤(pán)移動(dòng)的次數(shù)。案例探析：

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

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

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

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

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

棧的抽象數(shù)據(jù)類型表示了棧中的數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系以及基本操作，定義如下：ADTStack{數(shù)據(jù)對(duì)象：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é)點(diǎn)，每個(gè)結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；除了尾結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有且只有一個(gè)后繼結(jié)點(diǎn)。棧中的數(shù)據(jù)元素只能在棧頂一端進(jìn)行插入和刪除操作?；静僮鳎篒nitStack(&S)：構(gòu)造一個(gè)空棧，即棧的初始化。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.順序棧

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

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

DataTypeStack[StackSize];

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

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

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

棧的初始化就是置空棧，只需把top指針置為-1即可。【算法3-1】：voidInitStack(SeqStack*S)/*棧的初始化*/{

S->top=-1;}(2)判棧空

判斷棧是否為空，就是要判斷top指針是否為-1。【算法3-2】：intStackEmpty(SeqStack*S)/*判棧空*/{

returnS->top==-1;

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

判斷棧是否已滿，需要判斷top指針是否達(dá)到了數(shù)組上限。【算法3-3】：intStackFull(SeqStack*S)/*判棧滿*/{

returnS->top==StackSize-1;

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

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

if(StackFull(s))

/*棧滿時(shí)，不能再做入棧操作*/

{

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(shí)，不能再做出棧操作*/

{

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

exit(0);

}

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

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

用x返回棧S的棧頂元素?！舅惴?-6】：voidGetTop(SeqStack*S,DataType*x)/*取棧頂元素*/{

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

{

printf("棧為空！");

exit(0);

}

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

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧(LinkedStack)。鏈棧是運(yùn)算受限的單鏈表，其插入和刪除操作都限定在表頭位置上進(jìn)行。棧頂指針就是鏈表的頭指針，用來(lái)唯一確定一個(gè)鏈棧。

鏈?？梢杂蓄^結(jié)點(diǎn)，也可以沒(méi)有頭結(jié)點(diǎn)。因?yàn)橐詥捂湵淼念^部做棧頂是最方便的，所以通常選用無(wú)頭結(jié)點(diǎn)的單鏈表表示鏈棧，如圖3-4所示。3.2.3鏈棧鏈棧的類型定義如下：typedefstructStackNode{DataTypedata;structStackNode*next;}StackNode,*LinkStack;2.鏈棧的實(shí)現(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é)點(diǎn)*/

if(!p)

{

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

exit(-1);

}

p->data=x;

p->next=*top;

*top=p;

return1;}3.2.3鏈棧(4)出?！舅惴?-14】：intLPop(LinkStack*top,DataType*x)/*鏈棧的出棧操作*/{

StackNode*p;

if(!(*top))

{

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

exit(0);

}

p=*top;

/*p指向棧頂元素*/

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

*x=p->data;

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

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

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í)間性能：因?yàn)闂５乃胁僮鞫荚跅ｍ斶M(jìn)行，所以順序棧和鏈棧的基本操作的算法都只需要常數(shù)階的時(shí)間。(2)空間性能：順序棧初始化時(shí)需要設(shè)定一個(gè)固定的長(zhǎng)度，當(dāng)數(shù)據(jù)元素過(guò)多時(shí)可能出現(xiàn)上溢現(xiàn)象，數(shù)據(jù)元素較少時(shí)又存在空間浪費(fèi)的現(xiàn)象。鏈棧只有在內(nèi)存空間不足時(shí)才會(huì)出現(xiàn)棧滿的問(wèn)題，但因?yàn)槊總€(gè)元素結(jié)點(diǎn)都需要指針域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷。

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

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

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

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

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