本書在簡要回顧基本C++程序設計概念的基礎上，全面繫統地介紹了隊列、堆棧、樹、圖等基本數據結構。本書將C++語言作為數據結構的算法描述語言。一方面對傳統的數據結構內容進行了C++語言實現，另一方面將數據結構與面向對像技術結合起來，圍繞抽像數據類型的概念來討論每一種數據結構及算法。書中大量C++語言的程序實例既是數據結構的具體實現，又是面向對像技術的算法基礎。本書理論與實踐並重，每章都有大量的習題，強調數據結構的應用價值。
本書可作為計算機類及信息類相關專業的核心教材，也可供廣大研究開發人員自學參考使用。

• 
• 
• 
• 
• 

目錄

第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．1C++的基本操作18
2．1．1C++的基本輸入與輸出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．1C++語言的字符和字符串96
5．1．1C++語言的字符和字符串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．2AOV網與拓撲排序194
8．6．3AOE網與關鍵路徑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．3B-樹和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