數據結構：從概念到C++實現(第3版)（簡體書）

數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹數據結構、算法以及抽象數據類型的概念；介紹線性表、棧和隊列、字符串和多維數組、樹和二叉樹、圖等常用數據結構；討論查找和排序技術。本書合理規劃教學內容，梳理知識單元及其拓撲結構，兼顧概念層和實現層，既強調數據結構的基本概念和原理方法，又注重數據結構的程序實現和實際運用，在提煉基礎知識的同時，進行適當的擴展和提高。
本書內容豐富，層次清晰，深入淺出，結合實例，可作為高等學校計算機及相關專業數據結構課程的教材，也可供從事計算機軟件開發和應用的工程技術人員參考和閱讀。

目錄第1章緒論1
1.1問題求解與程序設計2
1.1.1程序設計的一般過程2
1.1.2數據結構在程序設計中的作用5
1.1.3算法在程序設計中的作用6
1.1.4本書討論的主要內容7
1.2數據結構的基本概念9
1.2.1數據結構9
1.2.2抽象數據類型11
1.3算法的基本概念13
1.3.1算法及算法的特性13
1.3.2算法的描述方法14
1.4算法分析16
1.4.1算法的時間複雜度16
1.4.2算法的空間複雜度18
1.4.3算法分析舉例18
1.5擴展與提高21
1.5.1從數據到大數據21
1.5.2算法分析的其他漸進符號22
思想火花――概率算法23
習題124
第2章線性表27
2.1引言28
2.2線性表的邏輯結構29
2.2.1線性表的定義29數據結構――從概念到C++實現(第3版)目錄2.2.2線性表的抽象數據類型定義30
2.3線性表的順序存儲結構及實現31
2.3.1順序表的存儲結構31
2.3.2順序表的實現32
2.3.3順序表的使用37
2.4線性表的鏈接存儲結構及實現38
2.4.1單鏈表的存儲結構38
2.4.2單鏈表的實現40
2.4.3單鏈表的使用48
2.4.4雙鏈表49
2.4.5循環鏈表50
2.5順序表和鏈表的比較51
2.6擴展與提高52
2.6.1線性表的靜態鏈表存儲52
2.6.2順序表的動態分配方式54
2.7應用實例56
2.7.1約瑟夫環問題56
2.7.2一元多項式求和59
思想火花――好算法是反復努力和重新修正的結果63
習題264
實驗題267
第3章棧和隊列69
3.1引言70
3.2棧71
3.2.1棧的邏輯結構71
3.2.2棧的順序存儲結構及實現72
3.2.3棧的鏈接存儲結構及實現75
3.2.4順序棧和鏈棧的比較77
3.3隊列78
3.3.1隊列的邏輯結構78
3.3.2隊列的順序存儲結構及實現79
3.3.3隊列的鏈接存儲結構及實現83
3.3.4循環隊列和鏈隊列的比較86
3.4擴展與提高86
3.4.1兩棧共享空間86
3.4.2雙端隊列88
3.5應用舉例89
3.5.1括號匹配問題89
3.5.2表達式求值91
思想火花――好程序要能識別和處理各種輸入94
習題395
實驗題397
第4章字符串和多維數組99
4.1引言100
4.2字符串101
4.2.1字符串的邏輯結構101
4.2.2字符串的存儲結構103
4.2.3模式匹配103
4.3多維數組107
4.3.1數組的邏輯結構107
4.3.2數組的存儲結構與尋址108
4.4矩陣的壓縮存儲109
4.4.1特殊矩陣的壓縮存儲109
4.4.2稀疏矩陣的壓縮存儲112
4.5擴展與提高114
4.5.1稀疏矩陣的轉置運算114
4.5.2廣義表116
4.6應用實例119
4.6.1發紙牌119
4.6.2八皇后問題121
思想火花――用常識性的思維去思考問題124
習題4124
實驗題4126
第5章樹和二叉樹127
5.1引言128
5.2樹的邏輯結構129
5.2.1樹的定義和基本術語129
5.2.2樹的抽象數據類型定義131
5.2.3樹的遍歷操作131
5.3樹的存儲結構132
5.3.1雙親表示法132
5.3.2孩子表示法132
5.3.3孩子兄弟表示法133
5.4二叉樹的邏輯結構134
5.4.1二叉樹的定義134
5.4.2二叉樹的基本性質136
5.4.3二叉樹的抽象數據類型定義138
5.4.4二叉樹的遍歷操作139
5.5二叉樹的存儲結構140
5.5.1順序存儲結構140
5.5.2二叉鏈表141
5.5.3三叉鏈表146
5.6森林147
5.6.1森林的邏輯結構147
5.6.2樹、森林與二叉樹的轉換147
5.7最優二叉樹149
5.7.1哈夫曼算法149
5.7.2哈夫曼編碼152
5.8擴展與提高153
5.8.1二叉樹遍歷的非遞歸算法153
5.8.2線索鏈表157
5.9應用實例161
5.9.1堆與優先隊列161
5.9.2並查集164
思想火花――調試程序與魔術表演166
習題5167
實驗題5169
第6章圖171
6.1引言172
6.2圖的邏輯結構173
6.2.1圖的定義和基本術語173
6.2.2圖的抽象數據類型定義176
6.2.3圖的遍歷操作176
6.3圖的存儲結構及實現179
6.3.1鄰接矩陣179
6.3.2鄰接表182
6.3.3鄰接矩陣和鄰接表的比較187
6.4最小生成樹188
6.4.1Prim算法189
6.4.2Kruskal算法191
6.5最短路徑195
6.5.1Dijkstra算法196
6.5.2Floyd算法199
6.6有向無環圖及其應用200
6.6.1AOV網與拓撲排序201
6.6.2AOE網與關鍵路徑203
6.7擴展與提高206
6.7.1圖的其他存儲方法206
6.7.2圖的連通性208
6.8應用實例209
6.8.1七巧板塗色問題209
6.8.2醫院選址問題211
思想火花――直覺可能是錯誤的214
習題6214
實驗題6218
第7章查找技術219
7.1概述220
7.1.1查找的基本概念220
7.1.2查找算法的性能221
7.2線性表的查找技術221
7.2.1線性表查找結構的類定義221
7.2.2順序查找222
7.2.3折半查找223
7.3樹表的查找技術226
7.3.1二叉排序樹226
7.3.2平衡二叉樹231
7.3.3B樹235
7.4散列表的查找技術239
7.4.1散列查找的基本思想239
7.4.2散列函數的設計241
7.4.3處理衝突的方法242
7.4.4散列查找的性能分析246
7.4.5開散列表與閉散列表的比較247
7.5各種查找方法的比較247
7.6擴展與提高248
7.6.1順序查找的改進――分塊查找248
7.6.2折半查找的改進――插值查找249
7.6.3B樹的改進――B+樹250
思想火花――把注意力集中於主要因素，不要糾纏於噪聲251
習題7251
實驗題7254
第8章排序技術255
8.1概述256
8.1.1排序的基本概念256
8.1.2排序算法的性能257
8.1.3排序類的定義257
8.2插入排序258
8.2.1直接插入排序258
8.2.2希爾排序260
8.3交換排序262
8.3.1起泡排序262
8.3.2快速排序264
8.4選擇排序267
8.4.1簡單選擇排序267
8.4.2堆排序269
8.5歸併排序274
8.5.1二路歸併排序的遞歸實現274
8.5.2二路歸併排序的非遞歸實現275
8.6各種排序方法的比較277
8.6.1各種排序技術的使用範例277
8.6.2各種排序方法的綜合比較278
8.7擴展與提高280
8.7.1排序問題的時間下界280
8.7.2基數排序281
思想火花――學會“盒子以外的思考”283
習題8284
實驗題8286
附錄A預備知識289
附錄BC++語言基本語法293
附錄C詞匯索引307
參考文獻311