目 錄
第1章 數據結構導論 1
1.1 數據結構簡介 2
1.1.1 數據結構的應用 2
1.1.2 算法 4
1.1.3 算法的描述工具 5
1.2 認識程序設計 7
1.2.1 高級程序設計語言 7
1.2.2 程序設計要領 8
1.3 程序設計的風格 8
1.3.1 自頂嚮下與模塊化設計8
1.3.2 可讀性設計 8
1.3.3 控製結構設計 9
1.3.4 麵嚮對象設計 10
1.4 麵嚮對象設計與C 12
1.4.1 C 的麵嚮對象功能12
1.4.2 類的基本概念 13
1.4.3 訪問權限關鍵詞 14
1.4.4 繼承關係 15
1.4.5 多態 16
1.5 遞歸算法 17
1.5.1 遞歸的定義 17
1.5.2 斐波拉契數列 19
1.5.3 漢諾塔問題 20
1.6 程序效率的分析 25
1.6.1 Big-oh 27
1.6.2 Ω(omega)28
1.6.3 θ(theta)28
本章習題 29
第2章 綫性錶 33
2.1 綫性錶的定義 34
2.1.1 綫性錶的用途 34
2.2 數組 35
2.2.1 一維數組 35
2.2.2 二維數組 37
2.2.3 多維數組 41
2.2.4 結構數組 45
2.2.5 C 的字符串 48
2.2.6 字符串數組 50
2.2.7 String類 51
2.2.8 指針數組 52
2.3 矩陣 54
2.3.1 矩陣的運算 54
2.3.2 稀疏矩陣 57
2.3.3 上三角形矩陣 60
2.3.4 下三角形矩陣 62
2.3.5 帶狀矩陣 66
本章習題 66
第3章 鏈錶 70
3.1 動態分配內存 71
3.1.1 C 的動態分配變量72
3.1.2 動態配置數組 73
3.2 單嚮鏈錶 74
3.2.1 單嚮鏈錶的創建與遍曆74
3.2.2 單嚮鏈錶插入新節點 76
3.2.3 單嚮鏈錶刪除節點78
3.2.4 單嚮鏈錶的反轉 80
3.3 環形鏈錶 82
3.3.1 環形鏈錶中插入新節點83
3.3.2 環形鏈錶節點的刪除84
3.3.3 環形鏈錶的連接功能86
3.4 雙嚮鏈錶 87
3.4.1 雙嚮鏈錶的建立與遍曆87
3.4.2 雙嚮鏈錶中加入新節點88
3.4.3 雙嚮鏈錶節點的刪除90
3.5 鏈錶相關應用簡介 91
3.5.1 多項式錶式法 92
3.5.2 稀疏矩陣錶示法 95
本章習題 97
第4章 堆棧與隊列 103
4.1 堆棧簡介 104
4.1.1 堆棧的基本操作105
4.1.2 用數組實現堆棧105
4.1.3 用鏈錶實現堆棧107
4.1.4 堆棧類樣闆的實現108
4.1.5 老鼠走迷宮 109
4.1.6 八皇後問題 112
4.2 算術錶達式的錶示法114
4.2.1 中序轉為前序與後序115
4.2.2 前序與後序轉為中序120
4.2.3 中序錶示法求值122
4.2.4 前序法的求值運算124
4.2.5 後序法的求值運算125
4.3 隊列 125
4.3.1 隊列的基本操作126
4.3.2 用數組實現隊列126
4.4 隊列的相關應用 129
4.4.1 環形隊列 129
4.4.2 雙嚮隊列 133
4.4.3 優先隊列 134
本章習題 135
第5章 樹狀結構 147
5.1 樹的基本概念 148
5.1.1 專有名詞介紹 149
5.2 二叉樹 150
5.2.1 二叉樹的特性 150
5.2.2 特殊二叉樹簡介152
5.3 二叉樹的存儲方式 153
5.3.1 一維數組錶示法153
5.3.2 鏈錶錶示法 155
5.4 二叉樹的遍曆 156
5.4.1 中序遍曆 157
5.4.2 後序遍曆 158
5.4.3 前序遍曆 158
5.4.4 二叉樹節點的插入與刪除 160
5.4.5 二叉運算樹 165
5.5 綫索二叉樹 167
5.5.1 二叉樹轉為綫索二叉樹167
5.6 樹的二叉樹錶示法 171
5.6.1 樹轉化為二叉樹171
5.6.2 二叉樹轉換成樹173
5.6.3 森林化為二叉樹174
5.6.4 二叉樹轉換成森林175
5.6.5 樹與森林的遍曆176
5.6.6 確定唯一二叉樹180
5.7 優化二叉查找樹 182
5.7.1 擴充二叉樹 182
5.7.2 霍夫曼樹 184
5.8 平衡樹 185
5.8.1 平衡樹的定義 185
5.9 高級樹狀結構的研究187
5.9.1 決策樹 187
5.9.2 B樹 189
5.9.3 二叉空間分割樹190
5.9.4 四叉樹與八叉樹191
本章習題 192
第6章 圖形結構 202
6.1 圖形簡介 203
6.1.1 圖的定義 204
6.1.2 無嚮圖 204
6.1.3 有嚮圖 206
6.2 圖的數據錶示法 207
6.2.1 鄰接矩陣法 207
6.2.2 鄰接錶法 210
6.2.3 鄰接復閤鏈錶法212
6.2.4 索引錶格法 214
6.3 圖的遍曆 217
6.3.1 深度優先遍曆法217
6.3.2 廣度優先遍曆法219
6.4 生成樹 221
6.4.1 DFS生成樹和BFS生成樹 222
6.4.2 最小生成樹 223
6.4.3 Kruskal算法224
6.4.4 Prim算法 227
6.5 圖的最短路徑 228
6.5.1 單點對全部頂點229
6.5.2 兩兩頂點間的最短路徑232
6.6 AOV網絡與拓樸排序235
6.6.1 拓樸排列簡介 236
6.7 AOE網絡 237
6.7.1 關鍵路徑 238
本章習題 239
第7章 排序 248
7.1 排序簡介 249
7.1.1 排序的分類 250
7.2 內部排序法 251
7.2.1 冒泡排序法 251
7.2.2 選擇排序法 254
7.2.3 插入排序法 256
7.2.4 希爾排序法 258
7.2.5 閤並排序法 260
7.2.6 快速排序法 260
7.2.7 堆積排序法 263
7.2.8 基數排序法 269
7.3 外部排序法 272
7.3.1 直接閤並排序法272
7.3.2 k路閤並法 275
7.3.3 多相閤並法 276
本章習題 276
第8章 查找 286
8.1 常見的查找方法 287
8.1.1 順序查找法 287
8.1.2 二分查找法 288
8.1.3 插值查找法 290
8.1.4 斐波那契查找法292
8.2 哈希查找法 295
8.2.1 哈希法簡介 296
8.3 常見的哈希函數 297
8.3.1 除留餘數法 297
8.3.2 平方取中法 297
8.3.3 摺疊法 298
8.3.4 數字分析法 299
8.4 碰撞與溢齣問題的處理300
8.4.1 綫性探測法 300
8.4.2 平方探測 301
8.4.3 再哈希 301
8.4.4 鏈錶 301
本章習題 303
附錄A C/C 編譯程序的介紹與安裝 309
A.1 C/C 編譯程序簡介310
A.2 Dev C 的安裝與介紹 313
附錄B C 程序設計語言簡介 319
B.1 C 語言的基本概念320
B.2 C 語言的運算符與錶達式 323
B.3 C 語言的流程控製327
B.4　C 語言的高級語法 332
B.5 C 語言與麵嚮對象概念341
附錄C 數據結構專有名詞索引 349
· · · · · · (收起)