目　錄



第1章　緒論　1

1.1　數據結構的概念　1

1.1.1　什么是數據結構　1

1.1.2　學習數據結構的意義　3

1.2　基本概念和術語　4

1.2.1　數據與數據元素　4

1.2.2　數據的邏輯結構　4

1.2.3　數據的存儲結構　5

1.2.4　數據運算　5

1.2.5　數據類型　6

1.2.6　抽象數據類型　6

1.3　算法和算法分析　6

1.3.1　算法定義及描述　6

1.3.2　算法評價　7

1.3.3　算法性能分析與度量　10

本章小結　15

習題　15



第2章　c++程序設計基礎知識　18

2.1　c++的基本操作　18

2.1.1　c++的基本輸入與輸出　18

2.1.2　函數及其參數傳遞　21

2.2　類與對象　26

2.2.1　類定義　27

2.2.2　對象定義與聲明　28

2.2.3　類與對象的使用　28

2.2.4　對象數組　29

2.2.5　動態存儲分配　29

2.2.6　構造函數與析構函數　30

2.2.7　繼承和派生　33

2.2.8　虛函數　35

本章小結　37

習題　38



第3章　線性表　40

3.1　線性表的定義及其運算　40

3.1.1　線性表的定義　40

3.1.2　線性表的運算　41

3.1.3　線性表的抽象數據類型描述　42

3.2　線性表的順序存儲結構　42

3.2.1　順序表結構　42

3.2.2　順序表運算　43

3.2.3　順序表存儲空間的動態分配　47

3.3　線性表的鏈式存儲結構　47

3.3.1　單鏈表結構　47

3.3.2　單鏈表運算　49

3.3.3　循環鏈表結構　56

3.3.4　雙向鏈表結構　57

3.4　順序表與鏈式表的比較　58

3.5　算法應用舉例　59

本章小結　62

習題　63



第4章　棧和隊列　66

4.1　棧　66

4.1.1　棧的抽象數據類型　67

4.1.2　順序棧　67

4.1.3　鏈棧　69

4.1.4　棧的應用　71

4.2　隊列　81

4.2.1　隊列的抽象數據類型　81

4.2.2　順序隊列　81

4.2.3　鏈隊列　84

4.2.4　隊列的應用　87

4.3　遞歸　89

4.3.1　遞歸算法書寫要點及方法　90

4.3.2　遞歸過程的調用和返回　90

4.3.3　遞歸的應用　91

4.3.4　遞歸函數的非遞歸化　92

本章小結　93

習題　93



第5章　串　96

5.1　c++語言的字符和字符串　96

5.1.1　c++語言的字符和字符串　96

5.1.2　一個簡單的c++函數　97

5.2　串及其基本運算　97

5.2.1　串的基本概念　97

5.2.2　串的基本運算　98

5.3　串的順序存儲及基本運算　99

5.3.1　串的定長順序存儲　99

5.3.2　順序串的數據類型定義　100

5.3.3　定長順序串的基本運算　103

5.3.4　模式匹配　104

5.4　串的鏈式存儲結構　108

5.5　串操作應用　110

本章小結　111

習題　112



第6章　數組和廣義表　114

6.1　數組　114

6.1.1　數組的定義　114

6.1.2　數組的內存映像　115

6.2　特殊矩陣的壓縮存儲　115

6.2.1　對稱矩陣　115

6.2.2　三角矩陣　116

6.2.3　稀疏矩陣　116

6.3　廣義表　120

6.3.1　廣義表的定義　120

6.3.2　廣義表的存儲　121

6.3.3　廣義表基本操作的實現　122

本章小結　123

習題　124



第7章　樹和二叉樹　127

7.1　樹的基本概念　127

7.1.1　樹的定義及其表示　128

7.1.2　基本術語　129

7.2　二叉樹　129

7.2.1　二叉樹的定義　129

7.2.2　二叉樹的性質　130

7.2.3　二叉樹的存儲結構　132

7.2.4　二叉樹抽象數據類型　133

7.3　遍歷二叉樹　135

7.3.1　先序遍歷　135

7.3.2　中序遍歷　136

7.3.3　后序遍歷　137

7.3.4　按層次遍歷二叉樹　138

7.3.5　遍歷算法的應用舉例　139

7.4　線索二叉樹　140

7.4.1　線索的概念　140

7.4.2　線索的描述　142

7.4.3　線索的算法實現　143

7.4.4　線索二叉樹上的運算　144

7.5　樹與森林　146

7.5.1　樹的存儲結構　146

7.5.2　樹、森林和二叉樹的轉換　148

7.5.3　樹和森林的遍歷　150

7.6　哈夫曼樹　151

7.6.1　基本術語　152

7.6.2　哈夫曼樹的建立　153

7.6.3　哈夫曼樹的應用　157

本章小結　158

習題　158



第8章　圖　162

8.1　圖的基本概念　162

8.1.1　圖的定義和術語　162

8.1.2　圖的基本操作　166

8.2　圖的存儲結構　166

8.2.1　鄰接矩陣　166

8.2.2　鄰接表　169

8.2.3　十字鏈表　171

8.2.4　鄰接多重表　173

8.3　圖的遍歷　174

8.3.1　深度優先搜索　174

8.3.2　廣度優先搜索　175

8.3.3　應用圖的遍歷判定圖的連通性　177

8.3.4　圖的遍歷的其他應用　178

8.4　生成樹和*小生成樹　181

8.4.1　生成樹及生成森林　181

8.4.2　*小生成樹的概念　182

8.4.3　構造*小生成樹的prim算法　183

8.4.4　構造*小生成樹的kruskal算法　185

8.5　*短路徑　187

8.5.1　單源點的*短路徑　187

8.5.2　每對頂點之間的*短路徑　190

8.6　有向無環圖及其應用　193

8.6.1　有向無環圖的概念　193

8.6.2　aov網與拓撲排序　194

8.6.3　aoe網與關鍵路徑　198

本章小結　202

習題　203



第9章　查找　206

9.1　基本概念　206

9.2　靜態查找表　207

9.2.1　順序查找　207

9.2.2　有序表的查找　208

9.2.3　分塊查找　209

9.3　動態查找表i——樹表查找　210

9.3.1　二叉排序樹　211

9.3.2　平衡二叉樹(avl樹)　215

9.3.3　b-樹和b+樹　222

9.4　動態查找表ⅱ——哈希表查找(雜湊法)　226

9.4.1　常用的哈希方法　226

9.4.2　處理沖突的方法　228

9.4.3　哈希表的操作　230

本章小結　232

習題　232



第10章　排序　236

10.1　基本概念　236

10.2　插入排序　237

10.2.1　直接插入排序　237

10.2.2　二分插入排序　239

10.2.3　希爾排序　239

10.3　交換排序　241

10.3.1　冒泡排序　241

10.3.2　快速排序　242

10.4　選擇排序　244

10.4.1　簡單選擇排序　244

10.4.2　樹型選擇排序　245

10.4.3　堆排序　246

10.5　歸并排序　249

10.6　分配排序　251

10.6.1　多關鍵碼排序　251

10.6.2　鏈式基數排序　252

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

本章小結　256

習題　256