基本介紹
- 中文名：數據結構——C 語言描述
- 作者：張淑芬、劉麗
- 出版社：清華大學出版社
- ISBN：9787302574941
內容簡介,目錄,
內容簡介
本書採用C++語言介紹數據結構和算法，主要內容包括數據結構的概念和術語、線性表、棧和佇列、串、數組與廣義表、樹與二叉樹、圖及套用。每章之後配有多種類型的習題，方便讀者加深對所學知識的理解。教材力求語言通俗、算法表達精煉、注重套用實踐。本書可供本科計算機及相關專業的教材，也可供自學人員學習參考
目錄
第1章緒論1
1.1數據結構的研究內容1
1.2數據結構的基本概念3
1.2.1數據、數據元素、數據項和數據對象3
1.2.2數據結構4
1.3抽象數據類型及其實現6
1.3.1數據類型6
1.3.2抽象數據類型6
1.3.3C++的類和對象7
1.3.4C++的動態存儲分配11
1.3.5C++的模板11
1.4算法和算法分析15
1.4.1算法15
1.4.2算法分析16
本章小結20
習題121
第2章線性表23
2.1線性表的邏輯結構23
2.2線性表的順序表示和實現25
2.2.1線性表的順序存儲結構——順序表25
2.2.2順序表的實現26
2.3線性表的鏈式表示和實現33
2.3.1線性表的鏈式存儲結構——鍊表33
2.3.2單鍊表的定義和表示33
2.3.3單鍊表的實現34
2.3.4雙鍊表42
2.3.5循環鍊表44
2.4順序表和鍊表的比較45
2.5線性表的套用46
本章小結52
習題252第3章棧和佇列56
3.1棧56
3.1.1棧的定義56
3.1.2順序棧的表示和實現58
3.1.3鏈棧的表示和實現62
3.1.4棧的套用67
3.2佇列69
3.2.1佇列的定義69
3.2.2循環佇列——佇列的順序表示和實現71
3.2.3鏈隊——佇列的鏈式表示和實現75
3.2.4佇列的套用80
本章小結83
習題384
第4章串88
4.1串的定義88
4.2串的存儲結構90
4.3串的模式匹配91
本章小結96
習題496
第5章數組和廣義表98
5.1數組98
5.1.1數組的基本概念98
5.1.2數組的存儲結構99
5.2矩陣100
5.2.1特殊矩陣的壓縮存儲100
5.2.2稀疏矩陣的壓縮存儲104
5.3廣義表109
5.3.1廣義表的定義109
5.3.2廣義表的存儲結構111
本章小結112
習題5112
第6章樹和二叉樹116
6.1樹116
6.1.1樹的定義116
6.1.2樹的基本術語116
6.1.3樹的抽象數據類型定義118
6.2二叉樹119
6.2.1二叉樹的定義119
6.2.2二叉樹的抽象數據類型定義121
6.2.3二叉樹的性質123
6.2.4二叉樹的存儲結構124
6.2.5二叉鍊表的實現127
6.3二叉樹的遍歷133
6.3.1遍歷的概念133
6.3.2遍歷算法136
6.4線索二叉樹144
6.4.1線索二叉樹的概念144
6.4.2構造線索二叉樹145
6.4.3線索二叉樹的遍歷148
6.5樹和森林149
6.5.1樹的存儲結構149
6.5.2樹和森林與二叉樹的轉換151
6.5.3樹和森林的遍歷154
6.6哈夫曼樹及其套用155
6.6.1哈夫曼樹的基本概念155
6.6.2哈夫曼樹的構造算法156
6.6.3哈夫曼編碼158
本章小結160
習題6161
第7章圖165
7.1圖的基本概念165
7.1.1圖的定義165
7.1.2基本術語166
7.1.3圖的抽象類型定義168
7.2圖的存儲結構169
7.2.1鄰接矩陣169
7.2.2鄰接表176
7.2.3十字鍊表185
7.2.4鄰接多重表185
7.3圖的遍歷186
7.3.1深度優先遍歷187
7.3.2廣度優先遍歷188
7.4圖的套用191
7.4.1最小生成樹191
7.4.2最短路徑197
7.4.3拓撲排序204
7.4.4關鍵路徑208
本章小結213
習題7214
第8章查找219
8.1查找的基本概念219
8.1.1查找的定義219
8.1.2查找算法的性能分析220
8.2基於靜態表的查找221
8.2.1順序查找221
8.2.2折半查找221
8.3二叉排序樹223
8.3.1二叉排序樹的概念224
8.3.2二叉排序樹結點的定義224
8.3.3二叉排序樹類的定義和實現225
8.4二叉平衡樹231
8.4.1二叉平衡樹的概念231
8.4.2二叉平衡樹的平衡處理235
8.4.3二叉平衡樹的插入操作239
8.5B樹和B+樹240
8.5.1B樹241
8.5.2B+樹244
8.6散列表245
8.6.1散列表的概念245
8.6.2常見的散列函式246
8.6.3處理衝突的方法246
本章小結249
習題8249
第9章排序251
9.1排序的基本概念251
9.1.1排序的定義251
9.1.2內排序和外排序251
9.1.3排序用到的類定義251
9.2插入排序252
9.2.1直接插入排序252
9.2.2希爾排序253
9.3交換排序255
9.3.1冒泡排序255
9.3.2快速排序257
9.4選擇排序259
9.4.1簡單選擇排序259
9.4.2堆排序261
9.5歸併排序266
9.6各種內部排序算法的分析和比較268
本章小結269
習題9269
第10章實驗271
實驗1一元多項式求和271
實驗2求解約瑟夫問題277
實驗3表達式求值280
實驗4字元串的加解密285
實驗5利用二叉樹求解簡單算術表達式289
實驗6醫院選址問題294
附錄C++程式設計簡述299
A.1C++程式的基本結構299
A.2C++的數據類型300
A.3順序結構306
A.4選擇結構308
A.5循環結構309
A.6數組311
A.7指針和引用315
A.8函式317
A.9結構體319
參考文獻322
