數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）
本書是為“數(shù)據(jù)結(jié)構(gòu)”課程編著的教材，第1章和第2章介紹數(shù)學(xué)基礎(chǔ)和算法相關(guān)預(yù)備知識(shí)，第3～第10章介紹常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、算法實(shí)現(xiàn)、性能分析及其應(yīng)用。本書注重用具體案例介紹如何運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問(wèn)題，同時(shí)穿插程序設(shè)計(jì)技巧的講解。全書采用C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言，提供了大量設(shè)計(jì)精良的代碼，且不乏對(duì)算法所蘊(yùn)含的數(shù)學(xué)原理的精彩介紹，使讀者不僅能夠開(kāi)發(fā)出高效、精致的程序，而且能夠達(dá)到“知其然，也知其所以然”的效果。
更多科學(xué)出版社服務(wù)，請(qǐng)掃碼獲取。
目錄
前言
第1章 緒論 1
1.1 幾個(gè)實(shí)際問(wèn)題 1
1.1.1 學(xué)生成績(jī)表管理 1
1.1.2 人機(jī)對(duì)弈 2
1.1.3 路徑導(dǎo)航 3
1.2 本書主要討論內(nèi)容 3
1.2.1 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容 3
1.2.2 為什么需要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 4
1.3 數(shù)學(xué)知識(shí)復(fù)習(xí) 5
1.3.1 指數(shù) 5
1.3.2 對(duì)數(shù) 5
1.3.3 級(jí)數(shù) 6
1.3.4 模運(yùn)算 8
1.3.5 證明方法 8
1.4 總結(jié) 10
第2章 算法分析 11
2.1 數(shù)學(xué)基礎(chǔ) 11
2.2 模型 13
2.3 要分析的問(wèn)題 14
2.4 算法的運(yùn)行時(shí)間計(jì)算 17
2.4.1 一個(gè)簡(jiǎn)單的例子 17
2.4.2 一般法則 18
2.4.3 最大子序列和問(wèn)題的解 21
2.4.4 運(yùn)行時(shí)間中的對(duì)數(shù) 26
2.4.5 檢驗(yàn)結(jié)果 30
2.4.6 分析結(jié)果的準(zhǔn)確性 31
2.5 算法的存儲(chǔ)空間計(jì)算 31
2.6 總結(jié) 32
第3章 線性表 33
3.1 ADT 33
3.2 線性表的邏輯特性 34
3.3 順序表及其實(shí)現(xiàn) 35
3.3.1 順序表 35
3.3.2 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn) 35
3.3.3 ArrayList的實(shí)現(xiàn) 36
3.4 鏈表及其實(shí)現(xiàn) 40
3.4.1 鏈表的思想 40
3.4.2 單向鏈表 41
3.4.3 單向鏈表 ADT 42
3.4.4 常見(jiàn)的錯(cuò)誤 48
3.4.5 模塊化設(shè)計(jì) 50
3.4.6 雙向鏈表 50
3.4.7 循環(huán)鏈表 52
3.5 鏈表應(yīng)用實(shí)例 53
3.6 總結(jié) 61
第4章 棧和隊(duì)列 62
4.1 棧 62
4.1.1 棧的定義 62
4.1.2 棧 ADT 62
4.1.3 棧的順序表示 63
4.1.4 棧的鏈接表示 65
4.2 表達(dá)式計(jì)算 67
4.2.1 表達(dá)式 67
4.2.2 計(jì)算后綴表達(dá)式的值 68
4.2.3 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 69
4.2.4 利用兩個(gè)棧計(jì)算表達(dá)式 71
4.3 遞歸 75
4.3.1 遞歸的概念 75
4.3.2 遞歸的實(shí)現(xiàn) 80
4.4 隊(duì)列 82
4.4.1 隊(duì)列ADT 82
4.4.2 隊(duì)列的數(shù)組實(shí)現(xiàn) 84
4.4.3 隊(duì)列數(shù)組實(shí)現(xiàn)的改進(jìn) 86
4.4.4 循環(huán)隊(duì)列 86
4.4.5 循環(huán)隊(duì)列的應(yīng)用 89
4.4.6 隊(duì)列的鏈接表示 89
4.4.7 舞伴問(wèn)題 91
4.5 總結(jié) 93
第5章 矩陣 94
5.1 矩陣的二維數(shù)組存儲(chǔ) 94
5.2 特殊矩陣的壓縮存儲(chǔ) 96
5.2.1 稠密矩陣和稀疏矩陣 96
5.2.2 對(duì)稱矩陣 96
5.2.3 三角矩陣 97
5.2.4 帶狀矩陣 99
5.3 稀疏矩陣的壓縮存儲(chǔ) 100
5.3.1 三元組順序表存儲(chǔ) 101
5.3.2 行邏輯鏈接的順序存儲(chǔ) 105
5.3.3 十字鏈表 109
5.3.4 稀疏矩陣的并行運(yùn)算 118
5.4 總結(jié) 119
第6章 查找和散列表 120
6.1 查找方法 120
6.1.1 順序表的查找 120
6.1.2 有序表的查找 122
6.1.3 索引順序表的查找 126
6.1.4 散列表的查找 128
6.2 什么是散列表 128
6.2.1 基本思想 129
6.2.2 構(gòu)造散列函數(shù)的原則 129
6.3 常見(jiàn)散列函數(shù) 130
6.3.1 直接定址法 130
6.3.2 數(shù)字分析法 130
6.3.3 平方取中法 130
6.3.4 折疊法 131
6.3.5 除留余數(shù)法 132
6.4 解決散列函數(shù)沖突的方法 132
6.4.1 拉鏈法 132
6.4.2 開(kāi)放地址法 133
6.4.3 裝填因子 136
6.4.4 再散列 136
6.5 散列表的查找 138
6.5.1 散列表的實(shí)現(xiàn) 138
6.5.2 性能分析 148
6.6 總結(jié) 149
第7章 排序 150
7.1 基本概念 150
7.2 插入排序 151
7.2.1 直接插入排序 151
7.2.2 對(duì)簡(jiǎn)單排序的分析 153
7.2.3 希爾排序 154
7.2.4 對(duì)希爾排序的分析 156
7.3 交換排序 156
7.3.1 冒泡排序 156
7.3.2 對(duì)冒泡排序的分析 158
7.3.3 快速排序 158
7.3.4 實(shí)際的快速排序程序 160
7.3.5 對(duì)快速排序的分析 161
7.4 選擇排序 162
7.4.1 算法實(shí)現(xiàn) 162
7.4.2 效率分析 163
7.5 歸并排序 163
7.5.1 二路歸并排序 164
7.5.2 對(duì)歸并排序的分析 166
7.6 基數(shù)排序 167
7.6.1 多關(guān)鍵字的排序 167
7.6.2 鏈?zhǔn)交鶖?shù)排序 168
7.6.3 對(duì)基數(shù)排序的分析 170
7.7 外部排序 172
7.7.1 外部排序的概念 172
7.7.2 簡(jiǎn)單算法 172
7.7.3 多路合并 173
7.7.4 多相合并 174
7.7.5 替換選擇 175
7.8 在ArrayList與SList結(jié)構(gòu)中加入排序方法 176
7.9 總結(jié) 180
第8章 樹 181
8.1 樹的基礎(chǔ)知識(shí) 181
8.1.1 基本術(shù)語(yǔ) 181
8.1.2 樹ADT 183
8.1.3 樹的表示 185
8.1.4 樹的實(shí)現(xiàn) 186
8.2 樹的遍歷 187
8.2.1 前序遍歷 187
8.2.2 后序遍歷 189
8.3 二叉樹 191
8.3.1 二叉樹基本概念 191
8.3.2 二叉樹的性質(zhì) 195
8.3.3 二叉樹的實(shí)現(xiàn) 197
8.3.4 二叉樹的遍歷方法以及非遞歸實(shí)現(xiàn) 200
8.3.5 表達(dá)式樹 208
8.3.6 哈夫曼樹 217
8.3.7 決策樹 224
8.4 二叉查找樹 227
8.4.1 二叉查找樹的概念 227
8.4.2 查找操作 229
8.4.3 插入操作 230
8.4.4 刪除操作 232
8.4.5 性能分析 234
8.5 二叉平衡樹 236
8.5.1 二叉平衡樹的概念 236
8.5.2 平衡化策略 238
8.5.3 平衡樹的實(shí)現(xiàn) 244
8.6 其他一些樹 251
8.6.1 伸展樹 251
8.6.2 B-樹 252
8.6.3 紅黑樹的概念 257
8.6.4 紅黑樹的實(shí)現(xiàn) 258
8.7 總結(jié) 267
第9章 優(yōu)先隊(duì)列(堆) 268
9.1 基本概念 268
9.2 簡(jiǎn)單實(shí)現(xiàn) 269
9.3 二叉堆 269
9.3.1 堆ADT 272
9.3.2 基本的堆操作 272
9.4 d-堆 276
9.5 左式堆 277
9.5.1 左式堆的性質(zhì) 277
9.5.2 左式堆的操作 278
9.6 斜堆 283
9.7 二項(xiàng)隊(duì)列 285
9.7.1 二項(xiàng)隊(duì)列的結(jié)構(gòu) 285
9.7.2 二項(xiàng)隊(duì)列的操作 286
9.7.3 二項(xiàng)隊(duì)列的實(shí)現(xiàn) 289
9.8 優(yōu)先隊(duì)列應(yīng)用 293
9.8.1 堆排序 293
9.8.2 選擇問(wèn)題 295
9.8.3 事件模擬 296
9.9 總結(jié) 297
第10章 圖論算法 298
10.1 圖的基本概念 298
10.1.1 定義與術(shù)語(yǔ) 298
10.1.2 圖ADT 301
10.2 圖的存儲(chǔ) 304
10.2.1 矩陣表示法 304
10.2.2 鄰接矩陣表示法的實(shí)現(xiàn) 306
10.2.3 鄰接表表示法 308
10.2.4 鄰接表表示法的實(shí)現(xiàn) 309
10.3 圖的遍歷 312
10.3.1 廣度優(yōu)先遍歷 312
10.3.2 深度優(yōu)先遍歷 315
10.3.3 圖的連通性 318
10.4 拓?fù)渑判?320
10.4.1 AOV網(wǎng)絡(luò) 320
10.4.2 拓?fù)渑判虻母拍?322
10.4.3 拓?fù)渑判蛩惴捌鋵?shí)現(xiàn) 323
10.5 關(guān)鍵路徑 327
10.5.1 AOE網(wǎng)絡(luò) 327
10.5.2 關(guān)鍵路徑的概念 327
10.5.3 關(guān)鍵路徑算法及其實(shí)現(xiàn) 330
10.6 最小生成樹 333
10.6.1 最小生成樹的概念 333
10.6.2 Prim算法 334
10.6.3 Kruskal算法 337
10.7 最短路徑問(wèn)題 341
10.7.1 問(wèn)題描述 341
10.7.2 Dijkstra算法 342
10.7.3 Floyd算法 347
10.8 總結(jié) 350
參考文獻(xiàn) 351
附錄 352
書單推薦
