了得網計算機/網絡_數據結構教程（第5版）

編輯推薦

本書配套20小時的教學視頻，本教程突出上機實習內容，書中給出大量的上機實驗題（分為驗證、設計和綜合型實驗），供教師和學生選用。為了方便教師教學和學生學習，本書提供了全面而豐富的教學資源，其中包括教學PPT、源程序代碼和練習題參考答案等

內容簡介

本書在前4版的基礎上針對*新的考研大綱和大量讀者來信提出的要求進行了修訂。本書共13章，內容包括緒論、線性表、棧和隊列、串、遞歸、數組和廣義表、樹和二叉樹、圖、查找、內排序、外排序和文件等，書中給出了大量練習題和各類上機實驗題，每個知識點都配有視頻講解。
本書內容全面，知識點翔實，條理清晰，講解透徹，實例豐富，實用性強，適合高等院校計算機和相關專業的本科生及研究生使用。

目錄

第1章緒論

1.1什麼是數據結構

1.1.1數據結構的定義

1.1.2邏輯結構

1.1.3存儲結構

1.1.4數據運算

第1章緒論

1.1什麼是數據結構

1.1.1數據結構的定義

1.1.2邏輯結構

1.1.3存儲結構

1.1.4數據運算

1.1.5數據類型和抽像數據類型

1.2算法及其描述

1.2.1什麼是算法

1.2.2算法設計的目標

1.2.3算法描述

1.3算法分析

1.3.1算法分析概述

1.3.2算法時間性能分析

1.3.3算法空間性能分析

1.4數據結構算法=程序

1.4.1程序和數據結構

1.4.2算法和程序

1.4.3算法和數據結構

1.4.4數據結構的發展

本章小結

練習題1

上機實驗題1

驗證性實驗

設計性實驗

第2章線性表

2.1線性表及其邏輯結構

2.1.1線性表的定義

2.1.2線性表的抽像數據類型描述

2.2線性表的順序存儲結構

2.2.1線性表的順序存儲結構——順序表

2.2.2順序表基本運算的實現

2.3線性表的鏈式存儲結構

2.3.1線性表的鏈式存儲結構——鏈表

2.3.2單鏈表

2.3.3雙鏈表

2.3.4循環鏈表

2.4線性表的應用

2.5有序表

2.5.1有序表的抽像數據類型描述

2.5.2有序表的存儲結構及其基本運算算法

2.5.3有序表的歸並算法

2.5.4有序表的應用

本章小結

練習題2

上機實驗題2

驗證性實驗

設計性實驗

綜合性實驗

第3章棧和隊列

3.1棧

3.1.1棧的定義

3.1.2棧的順序存儲結構及其基本運算的實現

3.1.3棧的鏈式存儲結構及其基本運算的實現

3.1.4棧的應用

3.2隊列

3.2.1隊列的定義

3.2.2隊列的順序存儲結構及其基本運算的實現

3.2.3隊列的鏈式存儲結構及其基本運算的實現

3.2.4隊列的應用舉例

3.2.5雙端隊列

本章小結

練習題3

上機實驗題3

驗證性實驗

設計性實驗

綜合性實驗

第4章串

4.1串的基本概念

4.2串的存儲結構

4.2.1串的順序存儲結構——順序串

4.2.2串的鏈式存儲結構——鏈串

4.3串的模式匹配

4.3.1BruteForce算法

4.3.2KMP算法

本章小結

練習題4

上機實驗題4

驗證性實驗

設計性實驗

綜合性實驗

第5章遞歸

5.1什麼是遞歸

5.1.1遞歸的定義

5.1.2何時使用遞歸

5.1.3遞歸模型

5.1.4遞歸與數學歸納法

5.2棧和遞歸

5.2.1函數調用棧

5.2.2遞歸調用的實現

5.2.3遞歸到非遞歸的轉換

5.3遞歸算法的設計

5.3.1遞歸算法設計的步驟

5.3.2基於遞歸數據結構的遞歸算法設計

5.3.3基於遞歸求解方法的遞歸算法設計

本章小結

練習題5

上機實驗題5

驗證性實驗

設計性實驗

綜合性實驗

第6章數組和廣義表

6.1數組

6.1.1數組的基本概念

6.1.2數組的存儲結構

6.1.3特殊矩陣的壓縮存儲

6.2稀疏矩陣

6.2.1稀疏矩組表示

6.2.2稀疏矩陣的十字鏈表表示

6.3廣義表

6.3.1廣義表的定義

6.3.2廣義表的存儲結構

6.3.3廣義表的運算

本章小結

練習題6

上機實驗題6

驗證性實驗

設計性實驗

綜合性實驗

第7章樹和二叉樹

7.1樹的基本概念

7.1.1樹的定義

7.1.2樹的邏輯表示方法

7.1.3樹的基本術語

7.1.4樹的性質

7.1.5樹的基本運算

7.1.6樹的存儲結構

7.2二叉樹的概念和性質

7.2.1二叉樹的定義

7.2.2二叉樹的性質

7.2.3二叉樹與樹、森林之間的轉換

7.3二叉樹的存儲結構

7.3.1二叉樹的順序存儲結構

7.3.2二叉樹的鏈式存儲結構

7.4二叉樹的基本運算及其實現

7.4.1二叉樹的基本運算概述

7.4.2二叉樹的基本運算算法實現

7.5二叉樹的遍歷

7.5.1二叉樹遍歷的概念

7.5.2先序、中序和後序遍歷遞歸算法

7.5.3先序、中序和後序遍歷非遞歸算法

7.5.4層次遍歷算法

7.6二叉樹的構造

7.7線索二叉樹

7.7.1線索二叉樹的概念

7.7.2線索化二叉樹

7.7.3遍歷線索化二叉樹

7.8哈夫曼樹

7.8.1哈夫曼樹概述

7.8.2哈夫曼樹的構造算法

7.8.3哈夫曼編碼

7.9用並查集求解等價問題

7.9.1什麼叫並查集

7.9.2並查集的算法實現

本章小結

練習題7

上機實驗題7

驗證性實驗

設計性實驗

綜合性實驗

第8章圖

8.1圖的基本概念

8.1.1圖的定義

8.1.2圖的基本術語

8.2圖的存儲結構和基本運算算法

8.2.1鄰接矩陣存儲方法

8.2.2鄰接表存儲方法

8.2.3圖基本運算算法設計

8.2.4其他存儲方法

8.3圖的遍歷

8.3.1圖的遍歷的概念

8.3.2深度優先遍歷

8.3.3廣度優先遍歷

8.3.4非連通圖的遍歷

8.3.5圖遍歷算法的應用

8.4生成樹和小生成樹

8.4.1生成樹的概念

8.4.2無向圖的連通分量和生成樹

8.4.3普裡姆算法

8.4.4克魯斯卡爾算法

8.5短路徑

8.5.1路徑的概念

8.5.2從一個頂點到其餘各頂點的短路徑

8.5.3每對頂點之間的短路徑

8.6拓撲排序

8.7AOE網與關鍵路徑

8.7.1相關概念

8.7.2求AOE網的關鍵活動

本章小結

練習題8

上機實驗題8

驗證性實驗

設計性實驗

綜合性實驗

第9章查找

9.1查找的基本概念

9.2線性表的查找

9.2.1順序查找

9.2.2折半查找

9.2.3索引存儲結構和分塊查找

9.3樹表的查找

9.3.1二叉排序樹

9.3.2平衡二叉樹

9.3.3B-樹

9.3.4B 樹

9.4哈希表的查找

9.4.1哈希表的基本概念

9.4.2哈希函數的構造方法

9.4.3哈希衝突的解決方法

9.4.4哈希表的運算算法

本章小結

練習題9

上機實驗題9

驗證性實驗

設計性實驗

綜合性實驗

第10章內排序

10.1排序的基本概念

10.2插入排序

10.2.1直接插入排序

10.2.2折半插入排序

10.2.3希爾排序

10.3交換排序

10.3.1冒泡排序

10.3.2快速排序

10.4選擇排序

10.4.1簡單選擇排序

10.4.2堆排序

10.5歸並排序

10.6基數排序

10.7各種內排序方法的比較和選擇

本章小結

練習題10

上機實驗題10

驗證性實驗

設計性實驗

綜合性實驗

第11章外排序

11.1外排序概述

11.2磁盤排序

11.2.1磁盤排序概述

11.2.2生成初始歸並段

11.2.3多路平衡歸並

11.2.4歸並樹

11.3磁帶排序

11.3.1多路平衡歸並排序

11.3.2多階段歸並排序

本章小結

練習題11

上機實驗題11

驗證性實驗

設計性實驗

第12章文件

12.1文件的基本概念

12.1.1什麼是文件

12.1.2文件的邏輯結構及操作

12.1.3文件的存儲結構

12.2順序文件

12.3索引文件

12.3.1ISAM文件

12.3.2VSAM文件

12.4哈希文件

12.5多關鍵字文件

12.5.1多重表文件

12.5.2倒排文件

本章小結

練習題12

上機實驗題12

驗證性實驗

設計性實驗

第13章采用面向對像的方法描述算法

13.1面向對像的概念

13.2用C 描述面向對像的程序

13.2.1類

13.2.2類對像

13.2.3構造函數和析構函數

13.2.4模板類

13.3用C 描述數據結構算法

13.3.1順序表類模板

13.3.2鏈棧類模板

13.4使用STL設計數據結構算法

附錄A實驗報告格式

一、
設計人員相關信息

二、
程序設計相關信息

三、
實驗提交內容

附錄B引用型參數和指針引用型參數的說明

附錄C算法索引

附錄D名詞索引

附錄E全國計算機專業數據結構2016年

聯考大綱

參考文獻

前言

前言
前言

數據結構是研究計算機科學和工程的基礎，數據結構課程是計算機科學與技術專業及相關專業的核心課程之一，學好該課程不僅對後續課程的學習有很大幫助，而且對開發有效利用計算機資源的程序極為有益。計算機是進行數據處理的工具，數據結構主要研究數據的各種組織形式以及建立在這些結構之上的各種運算算法的實現，它不僅為用計算機語言進行程序設計提供了方法性的理論指導，還在更高的層次上總結了程序設計的常用方法和常用技巧。本教程是作者針對數據結構課程概念多、算法靈活和抽像性強等特點，在總結長期教學經驗的基礎上編寫的。全書分為13章和5個附錄，第1章為緒論，介紹數據結構的基本概念，特別強調算法分析的方法；第2章為線性表，介紹線性表的兩種存儲結構——順序表和鏈表，以及基本運算算法的實現過程；第3章為棧和隊列，介紹這兩種特殊的線性結構的概念與應用；第4章為串，介紹串的概念與模式匹配算法；第5章為遞歸，討論計算機學科中遞歸算法的設計方法；第6章為數組和廣義表，介紹數組、稀疏矩陣和廣義表的概念與相關運算算法的實現過程；第7章為樹和二叉樹，介紹樹和二叉樹的概念與各種運算算法的實現過程，其中特別介紹二叉樹的各種遞歸算法方法；第8章為圖，介紹圖的概念和圖的各種運算算法的實現過程；第9章為查找，介紹各種查找算法的實現過程；第10章為內排序，介紹各種內排序算法的實現過程；第11章為外排序，介紹各種外排序算法的實現過程；第12章為文件，介紹各類文件的組織結構；第13章為采用面向對像的方法描述算法，介紹面向對像的概念和采用C 語言描述數據結構算法的方法。附錄A給出了實驗報告格式，附錄B是引用型參數和指針引用型參數的說明，附錄C給出了書中全部算法的索引，附錄D給出了書中相關名詞的索引，附錄E為*頒布的2016年全國計算機專業碩士研究生入學考試專業課中的數據結構部分考試大綱。數據結構是一門應用實踐性非常強的課程，學生在掌握各種數據結構（特別是存儲結構）的基礎上一定要盡可能多地上機實習，通過較多的實驗把難以理解的抽像概念轉化為實實在在的能夠在計算機上執行的程序，這樣纔能將所學知識和實際應用結合起來，吸取算法的設計思想和精髓，提高運用這些知識解決實際問題的能力。因此，本教程突出上機實習內容，書中給出了大量的上機實驗題(分為驗證性實驗、設計性實驗和綜合性實驗)供教師和學生選用。為了便於學生學習和上機實驗，我們還編寫了與本教程配套的《數據結構教程學習指導》和《數據結構教程上機實驗指導》兩書，構成一個完整的教學繫列。本繫列教程中的所有程序均在Visual C 6．0和Dev C 5環境下調試通過。本教程和配套的上機實驗指導、學習指導的編寫得到武漢大學“弘毅學堂”數據結構榮譽課程教學項目和湖北省“計算機科學與技術專業課程體繫改革”項目的支助，聚集了課程組許多教師多年來在數據結構課程教學研究和教學改革中的經驗與成果。本書在編寫過程中得到王麗娜、黃傳河和吳黎兵等多位教授、博導的大力支持，陳國良院士提供了富有建設性的指導，很多使用本書的老師和同學給予了熱心幫助，清華大學出版社的魏江江主任和王冰飛編輯給予了愉快的合作，作者在此一並表示衷心的感謝。為了方便教師教學和學生學習，本書提供了全面而豐富的教學資源，其中包括教學PPT、教學視頻、源程序代碼和練習題參考答案等，均可從清華大學出版社網站免費下載。由於水平所限，盡管作者不遺餘力，本書仍可能存在錯誤和不足之處，敬請讀者批評指正，特別希望使用本書的教師與作者探討，共同提高我國計算機專業數據結構課程的教學水平。作者
2017年1月

媒體評論

評論

在線試讀

第3章棧和隊列

素的邏輯關繫看，棧和隊列都屬於線性結構。棧和隊列與線性表的不同之處在於它們的相關運算具有一些特殊性。更準確地說，一般線性表上的插入、刪除運算不受限制，而棧和隊列上的插入、刪除運算均受某種特殊限制，因此棧和隊列也稱為操作受限的線性表。本章介紹棧和隊列的基本概念、存儲結構、基本運算算法設計和應用實例。

3.1棧棧是一種常用而且重要的數據結構之一，如用於保存函數調用時所需要的信息，通常在將遞歸算法轉換成非遞歸算法時需要使用到棧。本節主要討論棧及其應用。3.1.1棧的定義棧(stack)是一種隻能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂(top)，表的另一端稱為棧底(bottom)，如圖3.1所示。棧頂的當前位置是動態的，棧頂的當前位置由一個被稱為棧頂指針的位置指示器來指示。當棧中沒素時稱為空棧。棧的插入操作通常稱為進棧或入棧(push)，

圖3.1棧示意圖
棧的刪除操作通常稱為出棧或退棧(pop)。棧的主要特點是“後進先出”(Last In First Out，LIFO)，即後素先出棧。每次進棧素都放在原素之前成為新素，每次出棧素都是當素。棧也稱為後進先出表。例如，若干個人走進一個死胡同，假設該死胡同的寬度恰好隻夠一個人進出，那麼走出死胡同的順序和走進的順序正好相反。這個死胡同就是一個棧。棧抽像數據類型的定義如下：

ADT Stack
{數據對像：第3章棧和隊列

素的邏輯關繫看，棧和隊列都屬於線性結構。棧和隊列與線性表的不同之處在於它們的相關運算具有一些特殊性。更準確地說，一般線性表上的插入、刪除運算不受限制，而棧和隊列上的插入、刪除運算均受某種特殊限制，因此棧和隊列也稱為操作受限的線性表。本章介紹棧和隊列的基本概念、存儲結構、基本運算算法設計和應用實例。

3.1棧棧是一種常用而且重要的數據結構之一，如用於保存函數調用時所需要的信息，通常在將遞歸算法轉換成非遞歸算法時需要使用到棧。本節主要討論棧及其應用。3.1.1棧的定義棧(stack)是一種隻能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂(top)，表的另一端稱為棧底(bottom)，如圖3.1所示。棧頂的當前位置是動態的，棧頂的當前位置由一個被稱為棧頂指針的位置指示器來指示。當棧中沒素時稱為空棧。棧的插入操作通常稱為進棧或入棧(push)，

圖3.1棧示意圖
棧的刪除操作通常稱為出棧或退棧(pop)。棧的主要特點是“後進先出”(Last In First Out，LIFO)，即後素先出棧。每次進棧素都放在原素之前成為新素，每次出棧素都是當素。棧也稱為後進先出表。例如，若干個人走進一個死胡同，假設該死胡同的寬度恰好隻夠一個人進出，那麼走出死胡同的順序和走進的順序正好相反。這個死胡同就是一個棧。棧抽像數據類型的定義如下：

ADT Stack
{數據對像：
D={ ai | 1≤i≤n，n≥0，ai為ElemType類型}//ElemType是自定義類型標識符
數據關繫：
R={ai，ai 1 | ai、ai 1∈ D，i=1，…，n-1}
基本運算：
InitStack(&s)：初始化棧，構造一個空棧s。
DestroyStack(&s)：銷毀棧，釋放棧s占用的存儲空間。
StackEmpty(s)：判斷棧是否為空，若棧s為空，則返回真；否則返回假。
Push(&s，e)：進素e插入到棧s中作素。
Pop(&s，&e)：出棧，從棧s中刪素，並將其值賦給e。
GetTop(s，&e)：素，返回當前素，並將其值賦給e。
}

【例3.素的進棧序列為1234，能否得到3142的出棧序列？解為了讓3作為素，1、2先進棧，此時要麼2出棧，要麼4進棧後出棧，出棧的素不可能是1，所以得不到3142的出棧序列。【例3.2】用S表示進棧操作、X表示出棧操素的進棧順序為1234，為了得到1342的出棧序列，給出相應的S和X操作串。解為了得到1342的出棧序列，其操作過程是1進棧，1出棧，2進棧，3進棧，3出棧，4進棧，4出棧，2出棧。因此相應的S和X操作串為SXSSXSXX。說明： n個素通過一個棧產生的出棧序列的個數為1n 1Cn2n。例如n=4時，出棧序列的個數等於14。

圖3.2棧操作的一個時刻
【例3.3】一個棧的進棧序列為1，2，…，n，通過一個棧得到出棧序列p1，p2，…，pn(p1，p2，…，pn是1，2，…，n的一種排列)。若p1=3，則p2可能取值的個數是多少？解為了讓3作為素，將1、2、3依次進棧，3出棧，此時如圖3.2所示。之後可以讓2出棧，p2=2，也可以讓4進棧再出棧，p2=4，也可以讓4、5進棧再出棧，p2=5，…，所以p2可以是2，4，5，…，n，不可能是1和3，即p2可能取值的個數是n-2。3.1.2棧的順序存儲結構及其基本運算的實現棧素的邏輯關繫呈線性關繫，所以棧可以像線性表一樣采用順序存儲結構進行存儲，即分配一塊連續的存儲空間來存素，並用一個變量（如top）指向當前素以反素的變化。采用順序存儲結構的棧稱為順序棧(sequential stack)。假素個數不超過正整數MaxSize，素都具有同一數據類型，即ElemType，可用下列方式來聲明順序棧的類型SqStack：

typedef struct
{ElemType data［MaxSize］;//存放棧中素
int top;//棧頂指針，即存素在data數組中的下標
} SqStack;//順序棧類型

棧到順序棧的映射過程如圖3.3所示。本節采用棧指針s(不同於棧頂指針top)的方式創建和使用順序棧，如圖3.4所示。

圖3.3棧到順序棧的映射

圖3.4順序棧指針s

圖3.5是一個順序棧操作示意圖。圖3.5(a)是初始情況，它是一個空棧；圖3.5(b素a進棧以後的狀態；圖3.5(c素b、c、d進棧以後的狀態；圖3.5(d素d出棧以後的狀態。綜上所述，對於s所指的順序棧(即順序棧s)，初始時設置s->top=-1，可以歸納出對後面算法設計來說非常重要的4個要素。

圖3.5棧操作示意圖

 棧空的條件： s-top==-1。 棧滿的條件： s-top==MaxSize-1(data數組的下標)素e的進棧操作：先將棧頂指針top增1，素e放在棧頂指針處。 出棧操作：先將棧頂指針to素取出放在e中，然後將棧頂指針減1。在順序棧上對應棧的基本運算算法設計如下。1) 初始化棧initStack(&s)該運算創建一個空棧，由s指向它。實際上就是分配一個順序棧空間，並將棧頂指針設置為-1。算法如下：

void InitStack(SqStack *&s)
{s=(SqStack *)malloc(sizeof(SqStack));//分配一個順序棧空間，首地址存放在s中
stop=-1;//棧頂指針置為-1
}

2) 銷毀棧DestroyStack(&s)該運算釋放順序棧s占用的存儲空間。算法如下：

void DestroyStack(SqStack *&s)
{
free(s);
}

3) 判斷棧是否為空StackEmpty(s)該運算實際上用於判斷條件s->top==-1是否成立。算法如下：

bool StackEmpty(SqStack *s)
{
return(stop==-1);
}

4) 進棧Push(&s，e)該運算的執行過程是，在棧不滿的條件下先將棧頂指針增1，然後在該位置素e，並返回真；否則返回假。算法如下：

bool Push(SqStack *&s,ElemType e)
{if (stop==MaxSize-1)//棧滿的情況，即棧上溢出
return false;

stop ;//棧頂指針增1
sdata［stop］=e;素e放在棧頂指針處
return true;
}

5) 出棧Pop(&s，&e)該運算的執行過程是，在棧不為空的條件下先素賦給e，然後將棧頂指針減1，並返回真；否則返回假。算法如下：

bool Pop(SqStack *&s,ElemType &e)
{if (stop==-1)//棧為空的情況，即棧下溢出
return false;
e=sdata［stop］;//素
stop--;//棧頂指針減1
return true;
}

6) 素GetTop(s，&e)該運算在棧不為空的條件下素賦給e並返回真；否則返回假。算法如下：

bool GetTop(SqStack *s,ElemType &e)
{if (stop==-1)//棧為空的情況，即棧下溢出
return false;
e=sdata［stop］;//素
return true;
}

和出棧運算相比，本算法隻是沒有移動棧頂指針。上述6個基本運算算法的時間復雜度均為O(1)，說明這是一種非常高效的設計。【例3.4】設計一個算法利用順序棧判斷一個字符串是否為對稱串。所謂對稱串指從左向右讀和從右向左讀的序列相同。

素連續進棧，產生的連續出棧序列和輸入序列正好相反，本算法就是利用這個特點設計的。對於字符串str，從頭到尾將素連續進棧，如素連續出棧產生的序列和str從頭到尾的字符依次相同，表示str是一個對稱串，返回真；否則表示str不是對稱串，返回假。算法如下：

bool symmetry(ElemType str［］)//判斷str是否為對稱串
{int i; ElemType e;
SqStack *st;//定義順序棧指針
InitStack(st);//初始化棧
for (i=0;str［i］!='＼0';i )//將str素進棧
Push(st,str［i］);
for (i=0;str［i］!='＼0';i )//處理str的所有字符
{Pop(st,e);/素e
if (str［i］!=e)//若e與當前串字符不同表示不是對稱串

{DestroyStack(st);//銷毀棧
return false;//返回假
}
}
DestroyStack(st);//銷毀棧
return true;//返回真
}

順序棧采用一個數組存放素。如果需要用到兩個相同類型的棧，這時若為它們各自開闢一個數組空間，極有可能出現這樣的情況：個棧已滿，再進棧就溢出了，而另一個棧還有很多空閑存儲空間。解決這個問題的方法是將兩個棧合起來，如圖3.6所示，用一個數組來實現這兩個棧，這稱為共享棧(share stack)。

圖3.6共享棧

在設計共享棧時，由於一個數組(大小為MaxSize)有兩個端點，兩個棧有兩個棧底，讓一個棧的棧底為數組的始端，即下標為0處，另一個棧的棧底為數組的末端，即下標為MaxSize-1，這樣在兩個棧素時棧頂向中間伸展。共享棧的4個要素如下。 棧空條件：棧1空為top1==-1；棧2空為top2==MaxSize。 棧滿條件： top1==top2-1素x進棧操作：進棧1操作為top1 ;data［top1］=x；進棧2操作為top2--;data［top2］=x。 出棧x操作：出棧1操作為x=data［top1］;top1--；出棧2操作為x=data［top2］;top2 。在上述設置中，data數組表示共享棧的存儲空間，top1和top2分別為兩個棧的棧頂指針，這樣該共享棧通過data、top1和top2來標識，也可以將它們設計為一個結構體類型：

typedef struct
{ElemType data［MaxSize］;//存放共享素
int top1,top2;//兩個棧的棧頂指針
} DStack;//共享棧的類型

在實現共享棧的基本運算算法時需要增加一個形參i，指出是對哪個棧進行操作，如i=1表示對棧1進行操作，i=2表示對棧2進行操作。3.1.3棧的鏈式存儲結構及其基本運算的實現棧素的邏輯關繫呈線性關繫，所以棧可以像線性表一樣采用鏈式存儲結構。采用鏈式存儲結構的棧稱為鏈棧(linked stack)。鏈表有多種，這裡采用帶頭結點的單鏈表來實現鏈棧。鏈棧的優點是不存在棧滿上溢出的情況。規定棧的所有操作都是在單鏈表的表頭進行的(因為給定鏈棧後，已知頭結點地址，在其後面插入一個新結點和刪除首結點都十分方便，對應算法的時間復雜度均為O(1))。圖3.7所示為頭結點指針為s的鏈棧，首結點是棧頂結點，尾結點是棧底結點素自棧底到棧頂依次是a1，a2，…，an。

圖3.7棧到鏈棧的映射

鏈棧中結點類型LinkStNode的聲明如下：

typedef struct linknode
{ElemType data;//數據域
struct linknode *next;//指針域
} LinkStNode;//鏈棧結點類型

在以s為頭結點指針的鏈棧(簡稱鏈棧s)中，可以歸納出對後面算法設計來說非常重要的4個要素。 棧空的條件： s->next==NULL。 棧滿的條件：由於隻有內存溢出時纔出現棧滿，通常不考慮這樣的情況，所以在鏈棧中可以看成不存在棧滿素e的進棧操作：新建一個結素e(由p指向它)，將結點p插入到頭結點之後。 出棧操作：取出首結點的data值並將其刪除。

圖3.8創建一個空棧

在鏈棧上對應棧的基本運算算法設計如下。1) 初始化棧initStack(&s)該運算創建一個空鏈棧s，如圖3.8所示。實際上是創建鏈棧的頭結點，並將其next域置為NULL。算法如下：

void InitStack(LinkStNode *&s)
{s=(LinkStNode *)malloc(sizeof(LinkStNode));
snext=NULL;
}

本算法的時間復雜度為O(1)。2) 銷毀棧DestroyStack(&s)該運算釋放鏈棧s占用的全部結點空間，和單鏈表的銷毀算法完全相同。算法如下：

void DestroyStack(LinkStNode *&s)
{LinkStNode *pre=s,*p=snext;//pre指向頭結點，p指向首結點
while (p!=NULL)//循環到p為空
{free(pre);//釋放pre結點
pre=p;//pre、p同步後移
p=prenext;
}
free(pre);//此時pre指向尾結點,釋放其空間
}

本算法的時間復雜度為O(n)，其中n為鏈棧中的數據結點個數。3) 判斷棧是否為空StackEmpty(s)該運算判斷s->next=NULL的條件是否成立。算法如下：

bool StackEmpty(LinkStNode *s)
{
return(snext==NULL);
}

本算法的時間復雜度為O(1)。4) 進棧Push(&s，e)該運算新建一個結點，用素e(由p指向它)，然後將其插入到頭結點之後作為新的首結點。算法如下：

void Push(LinkStNode *&s,ElemType e)
{LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));//新建結點p
pdata=e;/素e
pnext=snext;//將p結點插入作為首結點
snext=p;
}

本算法的時間復雜度為O(1)。5) 出棧Pop(&s，&e)該運算在棧不為空的條件下提取首結點的數據域賦給引用型參數e，然後將其刪除。算法如下：

bool Pop(LinkStNode *&s,ElemType &e)
{LinkStNode *p;
if (snext==NULL)//棧空的情況
return false;//返回假
p=snext;//p指向首結點
e=pdata;//提取首結點值
snext=pnext;//刪除首結點

書摘插畫

商品搜索

商品分类

【醫學】

【各大出版社】