第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
附錄B C 語言基本語法293
附錄C 詞彙索引307
參考文獻311
