本書內容包括概論、線性表、棧和隊列、串、數組和稀疏矩陣、樹和二叉樹、圖、查找和排序，附錄中給出書中部分算法清單、全國計算機專業數據結構聯考大綱、部分練習題的參考答案

李春葆，武漢大學計算機學院教授，主要研究方向為數據挖掘和算法設計。先後主持和參加多項國家自然科學基金項目和應用開發項目。在清華大學出版社、人民郵電出版社和機械工業出版社等出版社出版教材和論著30餘本。

C O N T E N T S
目錄

源碼下載

第1章緒論

1．1知識點1：  數據結構的基本概念

1．1．1要點歸納

1．1．2例題解析

1．2知識點2：  算法和算法分析

1．2．1要點歸納

1．2．2例題解析

第2章線性表

2．1知識點1：  線性表的基本概念

2．1．1要點歸納

2．1．2例題解析

2．2知識點2：  順序表的算法

2．2．1要點歸納

2．2．2例題解析

2．3知識點3：  單鏈表的算法

2．3．1要點歸納

2．3．2例題解析

2．4知識點4：  雙鏈表的算法

2．4．1要點歸納

2．4．2例題解析

2．5知識點5：  循環鏈表的算法

2．5．1要點歸納

2．5．2例題解析

第3章棧和遞歸

3.1知識點1：  棧的基本概念

3.1.1要點歸納

3.1.2例題解析

3.2知識點2：  順序棧的算法

3.2.1要點歸納

3.2.2例題解析

3.3知識點3：  鏈棧的算法

3.3.1要點歸納

3.3.2例題解析

3.4知識點4：  遞歸

3.4.1要點歸納

3.4.2例題解析

第4章隊列

4.1知識點1：  隊列的基本概念

4.1.1要點歸納

4.1.2例題解析

4.2知識點2：  順序隊的算法

4.2.1要點歸納

4.2.2例題解析

4.3知識點3：  鏈隊的算法

4.3.1要點歸納

4.3.2例題解析

第5章串

5．1知識點1：  串的基本概念

5．1．1要點歸納

5．1．2例題解析

5．2知識點2：  順序串的算法

5．2．1要點歸納

5．2．2例題解析

5．3知識點3：  鏈串的算法

5．3．1要點歸納

5．3．2例題解析

5．4知識點4：  模式匹配的算法

5．4．1要點歸納

5．4．2例題解析

第6章數組和稀疏矩陣

6．1知識點1：  數組和特殊矩陣

6．1．1要點歸納

6．1．2例題解析

6．2知識點2：  稀疏矩陣

6．2．1要點歸納

6．2．2例題解析

第7章樹和二叉樹

7．1知識點1：  樹的基本概念

7．1．1要點歸納

7．1．2例題解析

7．2知識點2：  二叉樹的基本概念

7．2．1要點歸納

7．2．2例題解析

7．3知識點3：  二叉樹的算法

7．3．1要點歸納

7．3．2例題解析

7．4知識點4：  線索二叉樹

7．4．1要點歸納

7．4．2例題解析

7．5知識點5：  哈夫曼樹

7．5．1要點歸納

7．5．2例題解析

7．6知識點6：  樹算法設計

7．6．1要點歸納

7．6．2例題解析

第8章廣義表

8.1知識點1：  廣義表的基本概念

8.1.1要點歸納

8.1.2例題解析

8.2知識點2：  廣義表的算法設計

8.2.1要點歸納

8.2.2例題解析

第9章圖

9.1知識點1：  圖的基本概念

9.1.1要點歸納

9.1.2例題解析

9.2知識點2：  圖的遍歷算法

9.2.1要點歸納

9.2.2例題解析

9.3知識點3：  小生成樹

9.3.1要點歸納

9.3.2例題解析

9.4知識點4：  短路徑

9.4.1要點歸納

9.4.2例題解析

9.5知識點5：  AOV網和拓撲排序

9.5.1要點歸納

9.5.2例題解析

9.6知識點6：  AOE網與關鍵路徑

9.6.1要點歸納

9.6.2例題解析

第10章查找

10．1知識點1：  線性表的查找

10．1．1要點歸納

10．1．2例題解析

10．2知識點2：  樹表的查找

10．2．1要點歸納

10．2．2例題解析

10．3知識點3：  哈希表的查找

10．3．1要點歸納

10．3．2例題解析

第11章內排序

11.1知識點1：  插入排序算法

11.1.1要點歸納

11.1.2例題解析

11.2知識點2：  選擇排序算法

11.2.1要點歸納

11.2.2例題解析

11.3知識點3：  交換排序算法

11.3.1要點歸納

11.3.2例題解析

11.4知識點4：  歸並排序算法

11.4.1要點歸納

11.4.2例題解析

11.5知識點5：  基數排序算法

11.5.1要點歸納

11.5.2例題解析

第12章外排序和文件

12.1知識點1：  外排序

12.1.1要點歸納

12.1.2例題解析

12.2知識點2：  文件

12.2.1要點歸納

12.2.2例題解析

附錄A四份重點大學本科“數據結構”科目考試試題

試題1

試題1參考答案

試題2

試題2參考答案

試題3

試題3參考答案

試題4

試題4參考答案

附錄B2012—2018年全國計算機專業碩士學位研究生入學考試數據結構
部分試題視頻講解

附錄C書中視頻對應二維碼彙總表

F O R E W O R D
前言

計算機是進行數據處理的工具，數據結構課程主要討論數據組織和處理方法，具有概念多、抽像和算法設計靈活等特點。全國聯考大綱對本課程有較高的要求，不僅要求掌握數據結構的基本概念、基本原理和基本方法，還要求可以運用數據結構原理和方法進行問題的分析和求解，並具備實現算法和算法分析的能力。

要學好數據結構課程，首先要從宏觀上理解本課程的目的和地位。該課程是在學完C、C 或者Java等程序設計語言相關課程後開設的，程序設計語言課程教會學生用計算機處理簡單數據的方法，相當於小學階段的識字，認識數百個漢字但不一定能寫出好的作文，這是因為寫作文有自身的規律和方法，同樣的道理，熟悉程序設計語言卻不一定能編寫出“好程序”。

從數據結構角度看，編寫程序的過程分為邏輯層面和實現層面。邏輯層面是理解求解問題是什麼，即從求解的問題中提煉出數據邏輯結構和運算(前者素之間的相鄰關繫的整體，主要分為線性結構、樹形結構和圖形結構類型； 後者指程序功能的描述)。實現層面是將處理的數據存放到計算機內（映射），稱為數據存儲結構，再在存儲結構之上實現對應的運算，即算法。一種數據邏輯結構可以映射成多種存儲結構，不同的運算對應不同的算法，同一運算也可以有多種算法，通過算法時間和空間分析可以確定算法的好壞。數據結構課程的精髓就是設計求解問題的“好算法”。

數據結構課程總結和歸納了軟件開發中常用的一些數據結構，從數據邏輯結構、存儲結構和運算算法設計等各方面綜合討論這些數據結構，可以提高學生基本的數據組織和處理能力，為後續學習操作繫統、數據庫原理和編譯原理等課程打下基礎。

本書在總結作者多年的程序設計語言、數據結構和算法設計與分析課程的教學經驗的基礎上編寫而成。全書分為12章： 第1章為緒論，討論數據結構和算法的基本概念； 第2章為線性表，歸納了線性表的概念以及順序表、單鏈表、雙鏈表和循環鏈表的算法設計方法； 第3章為棧和遞歸，歸納了棧的概念以及順序棧、鏈棧的算法設計方法，較深入地討論了計算機學科中遞歸的算法設計方法； 第4章為隊列，歸納了隊列的概念以及順序隊、鏈隊的算法設計方法； 第5章為串，歸納了串的概念以及順序串、鏈串和模式匹配的算法設計方法； 第6章為數組和稀疏矩陣，歸納了數組、特殊矩陣和稀疏矩陣的概念與相關運算設計方法； 第7章為樹和二叉樹，歸納了樹、二叉樹、線索二叉樹、哈夫曼樹的概念以及二叉樹算法設計方法和樹算法設計方法； 第8章為廣義表，歸納了廣義表的概念和廣義表算法設計方法； 第9章為圖，歸納了圖的概念、圖遍歷算法、圖應用的各種算法設計方法； 第10章為查找，歸納了線性表、樹表和哈希表等各種查找算法設計方法； 第11章為內排序，歸納了各種內排序算法設計方法； 第12章為外排序和文件，歸納了外排序過程和各類文件的組織結構。書中算法設計題中每道例題後面的數字表示該題目的難度，數字從①到⑤代表難度依次遞增。

書中對部分重要知識點和示例提供了共計30小時的視頻講解，掃描書中的二維碼，可以在線觀看。附錄A給出四份重點大學本科“數據結構”科目考試試題和參考答案； 附錄B給出2012—2018年全國計算機專業碩士學位研究生入學考試數據結構部分試題的真題下載和視頻講解； 附錄C給出書中視頻對應二維碼的彙總表。

本書以知識點歸納為引導，以求解方法總結為延伸，以典型示例講解為擴展，以提高能力為目標，主要特色如下所述。

 強調數據結構求解問題的整體觀，即數據邏輯結構、存儲結構和算法設計的層次化思想。例如棧和隊列屬於邏輯結構的概念，順序棧和鏈隊屬於存儲結構的概念，後者是前者的存儲實現，二者不能混同。

 總結知識難點的求解方法。例如求樹中結點個數等，隻要按照書中列出的方法套用公式，求解過程就會變得十分簡單。

 力求歸納各類算法設計的規律，例如單鏈表算法很多是基於建表算法的，二叉樹算法很多是基於遍歷算法的，圖算法很多是基於深度優先遍歷和廣度優先遍歷算法的，如果讀者掌握了建表算法、二叉樹的遍歷算法和圖遍歷算法，那麼設計相關算法就會駕輕就熟了。

 深入討論遞歸算法設計方法。遞歸算法設計是數據結構課程中的難點之一，編者從遞歸模型入手，介紹了從求解問題中提取遞歸模型的通用方法，講解了從遞歸模型到遞歸算法設計的基本規律。

 提供了大量示例。全書超過1000道例題，絕大部分題目都給出了詳解和分析過程，每道算法設計題都在VC 6.0中調試通過（注意程序文件擴展名為.cpp而不是.c）。讀者可以從中體會求解問題的方法。

求解問題需要的是“能力”，從書本中可以獲取“知識”，但知識不等於能力，能力是獨有的，是自己通過學習知識提煉出解決問題的個性化方法。但願本書能夠幫助讀者提高數據結構問題的解決能力。

自2013年本書出版以來，得到了廣大讀者的厚愛和支持，很多讀者來信探討學習方法和改進意見，成為這次改版的動力，作者衷心感謝。由於水平所限，盡管作者不遺餘力，仍可能存在不足之處，敬請讀者批評指正。

編者2019年9月