數據結構（C語言版）

本書是為“數據結構”課程編寫的教材，對常用的數據結構做了系統的介紹，主要的內容包括：數據結構的基本概念；算法描述和算法分析初步；線性表、棧、隊列、串、數組、廣義表、樹和圖等結構；查找和排序的各種算法。 作者在多年教學經驗的基礎上，根據學生的認知規律精心組織了本教材內容，並通過大量有現實意義的例題，循序漸進地介紹了數據結構的有關概念、各種基本的數據結構和算法。

書中例題都經過了仔細的調試，另外還配有一定數量的上機實訓題和課後習題。 本書概念清晰、內容豐富、深入淺出、知識結構及深度合理，可作為高等職業和高等專科學校的教材，也可作為計算機培訓班的教材及自學者的參考書。 ^[1] 

第1章緒論 1

1.1數據結構的概念 1

1.1.1為什麼要學習數據結構 1

1.1.2有關概念和術語 4

1.1.3數據結構課程的內容 6

1.2抽象數據類型 7

1.2.1數據類型 7

1.2.2抽象數據類型 7

1.3算法和算法分析 8

1.3.1算法特性 8

1.3.2算法描述 9

1.3.3算法性能分析與度量 9

第2章線性表 11

2.1線性表的邏輯結構 11

2.1.1線性表的定義 11

2.1.2線性表的基本操作 11

2.2線性表的順序存儲及運算實現 12

2.2.1順序表 12

2.2.2順序表上基本運算的實現 14

2.2.3順序表應用舉例 18

2.3線性表的鏈式存儲和運算實現 20

2.3.1單鏈表 20

2.3.2單鏈表上基本運算的實現 22

2.3.3循環鏈表 28

2.3.4雙向鏈表 29

2.3.5靜態鏈表 30

2.3.6單鏈表應用舉例 32

2.4順序表和鏈表的比較 34

2.5上機實訓 35

2.6本章習題 36

第3章棧和隊列 39

3.1棧 39

3.1.1棧的定義及基本運算 39

3.1.2棧的存儲結構和運算實現 40

3.2棧的應用舉例 44

3.3隊列 48

3.3.1隊列的定義及基本運算 48

3.3.2隊列的存儲結構及運算

實現 49

3.4隊列應用舉例 56

3.5上機實訓 58

3.6本章習題 60

第4章串 63

4.1串類型的定義 63

4.2串的存儲結構 65

4.2.1定長順序存儲結構 66

4.2.2堆分配存儲表示 67

4.2.3串的塊鏈存儲表示 70

4.3串操作應用舉例 71

4.4上機實訓 71

4.5本章習題 72

第5章數組和廣義表 73

5.1數組的定義及其基本操作 73

5.1.1數組的定義 73

5.1.2數組的基本操作 74

5.2數組的順序存儲結構 74

5.3矩陣的壓縮存儲 76

5.3.1特殊矩陣的壓縮存儲 76

5.3.2稀疏矩陣的壓縮存儲 78

5.4廣義表的概念 87

5.5上機實訓 88

5.6本章習題 89

第6章樹和二叉樹 90

6.1樹的定義 90

6.1.1樹的定義 90

6.1.2樹的表示形式 91

6.1.3樹的常用術語 92

6.1.4樹的基本操作 92

6.2二叉樹 93

6.2.1二叉樹的定義 93

6.2.2二叉樹的性質 95

6.2.3二叉樹的存儲結構 97

6.3遍歷二叉樹和線索二叉樹 100

6.3.1遍歷二叉樹 100

6.3.2線索二叉樹 102

6.4樹、森林和二叉樹的關係 105

6.4.1樹的存儲結構 105

6.4.2森林與二叉樹的轉換 109

6.4.3樹和森林的遍歷 112

6.5哈夫曼樹及其應用 113

6.5.1哈夫曼樹的定義 113

6.5.2哈夫曼編碼 115

6.6上機實訓 116

6.7本章習題 117

第7章圖 119

7.1圖的基本概念 119

7.1.1圖的定義 119

7.1.2圖的基本術語 120

7.2圖的存儲結構 122

7.2.1鄰接矩陣 122

7.2.2鄰接表 124

7.2.3邊集數組 126

7.3圖的遍歷 127

7.3.1深度優先搜索 127

7.3.2廣度優先搜索 128

7.4圖的生成樹和最小生成樹 130

7.4.1概念 130

7.4.2普里姆算法 130

7.4.3克魯斯卡爾算法 133

7.5最短路徑 135

7.5.1求某個源點到其他頂點

的最短路徑 135

7.5.2求每對頂點之間

的最短路徑 137

7.6拓撲排序 138

7.6.1頂點活動網(AOV網) 138

7.6.2拓撲排序 139

7.7上機實訓 142

7.8本章習題 143 ^[1-2]