中圖網(wǎng)小程序
一鍵登錄
更方便
本類五星書更多>
-
>
全國計算機(jī)等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應(yīng)用
-
>
決戰(zhàn)行測5000題(言語理解與表達(dá))
-
>
軟件性能測試.分析與調(diào)優(yōu)實踐之路
-
>
第一行代碼Android
-
>
JAVA持續(xù)交付
-
>
EXCEL最強(qiáng)教科書(完全版)(全彩印刷)
-
>
深度學(xué)習(xí)
數(shù)據(jù)結(jié)構(gòu)(JavaScript語言版) 版權(quán)信息
- ISBN：9787030698612
- 條形碼：9787030698612 ; 978-7-03-069861-2
- 裝幀：一般膠版紙
- 冊數(shù)：暫無
- 重量：暫無
- 所屬分類：>
數(shù)據(jù)結(jié)構(gòu)(JavaScript語言版) 本書特色
全書采用了JavaScript語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言，提供了大量設(shè)計精良的代碼，且不乏對算法背后所蘊(yùn)含數(shù)學(xué)原理的精彩介紹，使讀者不僅能夠開發(fā)出高效、精致的程序，而且達(dá)到“知其然，也知其所以然”的效果。
數(shù)據(jù)結(jié)構(gòu)(JavaScript語言版) 內(nèi)容簡介
本書是為“數(shù)據(jù)結(jié)構(gòu)課程編寫的教材，第1,2章介紹數(shù)學(xué)基礎(chǔ)和算法相關(guān)預(yù)備知識，第3章至第10章介紹常見數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、算法實現(xiàn)、性能分析及其應(yīng)用。本書注重全面運用數(shù)據(jù)結(jié)構(gòu)知識解決案例中的實際問題，也穿插了程序設(shè)計的技巧。全書采用JavaScript語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言，介紹了常見的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)原理，如ArrayList、LinkedList、HashMap等，對于高效使用這些對象、提高程序性能有指導(dǎo)意義，特別適合JavaScript語言的進(jìn)階學(xué)習(xí)者。本書提供了大量設(shè)計精良的代碼，且不乏對算法背后所蘊(yùn)含的數(shù)學(xué)原理的精彩解析，使讀者不僅能夠開發(fā)出高效、精致的程序，而且達(dá)到“知其然，也知其所以然”的效果。 本書適合作為高等院校計算機(jī)專業(yè)或信息類相關(guān)專業(yè)的本科或?qū)？平滩模策m合作為信息技術(shù)和工程應(yīng)用行業(yè)工作者的自學(xué)參考書。
數(shù)據(jù)結(jié)構(gòu)(JavaScript語言版) 目錄
目錄
前言
第1章 緒論 1
1.1 幾個實際問題 1
1.1.1 學(xué)生成績表管理 1
1.1.2 人機(jī)對弈 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é)知識復(fù)習(xí) 5
1.3.1 指數(shù) 5
1.3.2 對數(shù) 5
1.3.3 級數(shù) 6
1.3.4 模運算 8
1.3.5 證明方法 8
1.4 總結(jié) 11
第2章 算法分析 12
2.1 數(shù)學(xué)基礎(chǔ) 12
2.2 模型 15
2.3 要分析的問題 15
2.4 算法的運行時間計算 19
2.4.1 一個簡單的例子 19
2.4.2 一般法則 20
2.4.3 *大子序列和問題的解 23
2.4.4 運行時間中的對數(shù) 28
2.4.5 檢驗結(jié)果 32
2.4.6 分析結(jié)果的準(zhǔn)確性 33
2.4.7 算法的存儲空間計算 34
2.5 總結(jié) 34
第3章 線性表 35
3.1 抽象數(shù)據(jù)類型 35
3.2 線性表的邏輯特性 36
3.2.1 定義 36
3.2.2 特征 36
3.2.3 運算 36
3.3 順序表及其實現(xiàn) 37
3.3.1 順序表 37
3.3.2 表的簡單數(shù)組實現(xiàn) 38
3.3.3 ArrayList的實現(xiàn) 38
3.4 鏈表及其實現(xiàn) 42
3.4.1 鏈表的思想 42
3.4.2 單向鏈表 43
3.4.3 單向鏈表ADT 44
3.4.4 常見的錯誤 48
3.4.5 模塊化設(shè)計 48
3.4.6 雙向鏈表 49
3.4.7 循環(huán)鏈表 51
3.5 鏈表應(yīng)用實例 54
3.5.1 一元多項式 54
3.5.2 音樂播放列表排序 59
3.5.3 多重表 62
3.6 總結(jié) 63
第4章 棧和隊列 64
4.1 棧 64
4.1.1 棧的定義 64
4.1.2 棧ADT 65
4.1.3 棧的順序表示 65
4.1.4 棧的鏈接表示 67
4.2 表達(dá)式計算 68
4.2.1 表達(dá)式 68
4.2.2 計算后綴表達(dá)式的值 69
4.2.3 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 71
4.2.4 利用兩個棧計算表達(dá)式 72
4.3 遞歸 76
4.3.1 遞歸的概念 76
4.3.2 遞歸的實現(xiàn) 81
4.4 隊列 83
4.4.1 隊列ADT 83
4.4.2 隊列的數(shù)組實現(xiàn) 84
4.4.3 隊列數(shù)組實現(xiàn)的改進(jìn) 86
4.4.4 循環(huán)隊列 87
4.4.5 循環(huán)隊列的應(yīng)用 90
4.4.6 隊列的鏈接表示 90
4.4.7 舞伴問題 92
4.5 總結(jié) 93
第5章 矩陣 95
5.1 矩陣的二維數(shù)組存儲 95
5.2 特殊矩陣的壓縮存儲 97
5.2.1 稠密矩陣和稀疏矩陣 97
5.2.2 對稱矩陣 97
5.2.3 三角矩陣 98
5.2.4 帶狀矩陣 100
5.3 稀疏矩陣的壓縮存儲 101
5.3.1 三元組順序表存儲 102
5.3.2 行邏輯鏈接的順序存儲 107
5.3.3 十字鏈表 112
5.3.4 稀疏矩陣的并行運算 120
5.4 總結(jié) 121
第6章 查找和散列表 122
6.1 查找方法 122
6.1.1 順序表的查找 122
6.1.2 有序表的查找 125
6.1.3 索引順序表的查找 129
6.1.4 散列表的查找 130
6.2 散列表 131
6.2.1 基本思想 131
6.2.2 構(gòu)造散列函數(shù)的原則 131
6.3 常見散列函數(shù) 132
6.3.1 直接定址法 132
6.3.2 數(shù)字分析法 132
6.3.3 平方取中法 133
6.3.4 折疊法 133
6.3.5 除留余數(shù)法 134
6.4 解決散列函數(shù)沖突的方法 134
6.4.1 拉鏈法 135
6.4.2 開放地址法 135
6.4.3 裝填因子 139
6.4.4 再散列 139
6.5 散列表的查找 141
6.5.1 散列表的實現(xiàn) 141
6.5.2 性能分析 146
6.6 總結(jié) 147
第7章 排序 148
7.1 基本概念 148
7.2 插入排序 149
7.2.1 直接插入排序 149
7.2.2 對直接插入排序的分析 151
7.2.3 希爾排序 152
7.2.4 對希爾排序的分析 154
7.3 交換排序 154
7.3.1 冒泡排序 154
7.3.2 對冒泡排序的分析 156
7.3.3 快速排序 156
7.3.4 實際的快速排序程序 158
7.3.5 對快速排序的分析 160
7.4 選擇排序 160
7.4.1 算法實現(xiàn) 161
7.4.2 效率分析 161
7.5 歸并排序 162
7.5.1 二路歸并排序 162
7.5.2 對歸并排序的分析 164
7.6 基數(shù)排序 165
7.6.1 多關(guān)鍵字的排序 165
7.6.2 鏈?zhǔn)交鶖?shù)排序 166
7.6.3 對基數(shù)排序的分析 168
7.7 外部排序 171
7.7.1 外部排序的概念 171
7.7.2 簡單算法 171
7.7.3 多路合并 172
7.7.4 多相合并 173
7.7.5 替換選擇 175
7.8 ArrayList與LinkedList中的排序方法 176
7.8.1 ArrayList中的排序方法 176
7.8.2 LinkedList中的排序方法 176
7.9 總結(jié) 178
第8章 樹 180
8.1 樹的基礎(chǔ)知識 180
8.1.1 基本術(shù)語 180
8.1.2 樹的ADT 182
8.1.3 樹的表示 184
8.1.4 樹的實現(xiàn) 184
8.2 樹的遍歷 185
8.2.1 前序遍歷 186
8.2.2 后序遍歷 188
8.3 二叉樹 190
8.3.1 二叉樹基本概念 190
8.3.2 二叉樹的性質(zhì) 194
8.3.3 二叉樹的實現(xiàn) 196
8.3.4 二叉樹的遍歷方法以及非遞歸實現(xiàn) 198
8.3.5 表達(dá)式樹 205
8.3.6 哈夫曼樹 212
8.3.7 決策樹 220
8.4 二叉查找樹 223
8.4.1 二叉查找樹的概念 223
8.4.2 查找操作 225
8.4.3 插入操作 227
8.4.4 刪除操作 228
8.4.5 性能分析 231
8.5 二叉平衡樹 233
8.5.1 二叉平衡樹的概念 233
8.5.2 平衡化策略 235
8.5.3 平衡樹的實現(xiàn) 242
8.6 其他一些樹 248
8.6.1 伸展樹 248
8.6.2 B-樹 249
8.6.3 紅黑樹的概念 254
8.6.4 紅黑樹的實現(xiàn) 256
8.7 總結(jié) 263
第9章 優(yōu)先隊列（堆） 265
9.1 基本概念和簡單實現(xiàn) 265
9.2 二叉堆 266
9.2.1 堆ADT 268
9.2.2 基本的堆操作 268
9.3 d-堆 273
9.4 左式堆 274
9.4.1 左式堆的性質(zhì) 274
9.4.2 左式堆的操作 275
9.5 斜堆 280
9.6 二項隊列 282
9.6.1 二項隊列的結(jié)構(gòu) 282
9.6.2 二項隊列的操作 283
9.6.3 二項隊列的實現(xiàn) 286
9.7 優(yōu)先隊列的應(yīng)用 291
9.7.1 堆排序 291
9.7.2 選擇問題 293
9.7.3 事件模擬 294
9.8 總結(jié) 295
第10章 圖論算法 296
10.1 圖的基本概念 296
10.1.1 定義與術(shù)語 297
10.1.2 圖ADT 300
10.2 圖的存儲 300
10.2.1 矩陣表示法 300
10.2.2 鄰接矩陣表示法的實現(xiàn) 303
10.2.3 鄰接表表示法 305
10.2.4 鄰接表表示法的實現(xiàn) 306
10.3 圖的遍歷 308
10.3.1 廣度優(yōu)先遍歷 308
10.3.2 深度優(yōu)先遍歷 311
10.3.3 圖的連通性 314
10.4 拓?fù)渑判?316
10.4.1 AOV網(wǎng)絡(luò) 316
10.4.2 拓?fù)渑判虻母拍?317
10.4.3 拓?fù)渑判蛩惴捌鋵崿F(xiàn) 318
10.5 關(guān)鍵路徑 320
10.5.1 AOE網(wǎng)絡(luò) 320
10.5.2 關(guān)鍵路徑的概念 321
10.5.3 關(guān)鍵路徑算法及其實現(xiàn) 323
10.6 *小代價生成樹 325
10.6.1 *小代價生成樹的概念 325
10.6.2 Prim算法 326
10.6.3 Kruskal算法 329
10.7 *短路徑問題 333
10.7.1 問題描述 333
10.7.2 Dijkstra算法 334
10.7.3 Floyd算法 338
10.8 總結(jié) 341
參考文獻(xiàn) 342
附錄 343
前言
第1章 緒論 1
1.1 幾個實際問題 1
1.1.1 學(xué)生成績表管理 1
1.1.2 人機(jī)對弈 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é)知識復(fù)習(xí) 5
1.3.1 指數(shù) 5
1.3.2 對數(shù) 5
1.3.3 級數(shù) 6
1.3.4 模運算 8
1.3.5 證明方法 8
1.4 總結(jié) 11
第2章 算法分析 12
2.1 數(shù)學(xué)基礎(chǔ) 12
2.2 模型 15
2.3 要分析的問題 15
2.4 算法的運行時間計算 19
2.4.1 一個簡單的例子 19
2.4.2 一般法則 20
2.4.3 *大子序列和問題的解 23
2.4.4 運行時間中的對數(shù) 28
2.4.5 檢驗結(jié)果 32
2.4.6 分析結(jié)果的準(zhǔn)確性 33
2.4.7 算法的存儲空間計算 34
2.5 總結(jié) 34
第3章 線性表 35
3.1 抽象數(shù)據(jù)類型 35
3.2 線性表的邏輯特性 36
3.2.1 定義 36
3.2.2 特征 36
3.2.3 運算 36
3.3 順序表及其實現(xiàn) 37
3.3.1 順序表 37
3.3.2 表的簡單數(shù)組實現(xiàn) 38
3.3.3 ArrayList的實現(xiàn) 38
3.4 鏈表及其實現(xiàn) 42
3.4.1 鏈表的思想 42
3.4.2 單向鏈表 43
3.4.3 單向鏈表ADT 44
3.4.4 常見的錯誤 48
3.4.5 模塊化設(shè)計 48
3.4.6 雙向鏈表 49
3.4.7 循環(huán)鏈表 51
3.5 鏈表應(yīng)用實例 54
3.5.1 一元多項式 54
3.5.2 音樂播放列表排序 59
3.5.3 多重表 62
3.6 總結(jié) 63
第4章 棧和隊列 64
4.1 棧 64
4.1.1 棧的定義 64
4.1.2 棧ADT 65
4.1.3 棧的順序表示 65
4.1.4 棧的鏈接表示 67
4.2 表達(dá)式計算 68
4.2.1 表達(dá)式 68
4.2.2 計算后綴表達(dá)式的值 69
4.2.3 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 71
4.2.4 利用兩個棧計算表達(dá)式 72
4.3 遞歸 76
4.3.1 遞歸的概念 76
4.3.2 遞歸的實現(xiàn) 81
4.4 隊列 83
4.4.1 隊列ADT 83
4.4.2 隊列的數(shù)組實現(xiàn) 84
4.4.3 隊列數(shù)組實現(xiàn)的改進(jìn) 86
4.4.4 循環(huán)隊列 87
4.4.5 循環(huán)隊列的應(yīng)用 90
4.4.6 隊列的鏈接表示 90
4.4.7 舞伴問題 92
4.5 總結(jié) 93
第5章 矩陣 95
5.1 矩陣的二維數(shù)組存儲 95
5.2 特殊矩陣的壓縮存儲 97
5.2.1 稠密矩陣和稀疏矩陣 97
5.2.2 對稱矩陣 97
5.2.3 三角矩陣 98
5.2.4 帶狀矩陣 100
5.3 稀疏矩陣的壓縮存儲 101
5.3.1 三元組順序表存儲 102
5.3.2 行邏輯鏈接的順序存儲 107
5.3.3 十字鏈表 112
5.3.4 稀疏矩陣的并行運算 120
5.4 總結(jié) 121
第6章 查找和散列表 122
6.1 查找方法 122
6.1.1 順序表的查找 122
6.1.2 有序表的查找 125
6.1.3 索引順序表的查找 129
6.1.4 散列表的查找 130
6.2 散列表 131
6.2.1 基本思想 131
6.2.2 構(gòu)造散列函數(shù)的原則 131
6.3 常見散列函數(shù) 132
6.3.1 直接定址法 132
6.3.2 數(shù)字分析法 132
6.3.3 平方取中法 133
6.3.4 折疊法 133
6.3.5 除留余數(shù)法 134
6.4 解決散列函數(shù)沖突的方法 134
6.4.1 拉鏈法 135
6.4.2 開放地址法 135
6.4.3 裝填因子 139
6.4.4 再散列 139
6.5 散列表的查找 141
6.5.1 散列表的實現(xiàn) 141
6.5.2 性能分析 146
6.6 總結(jié) 147
第7章 排序 148
7.1 基本概念 148
7.2 插入排序 149
7.2.1 直接插入排序 149
7.2.2 對直接插入排序的分析 151
7.2.3 希爾排序 152
7.2.4 對希爾排序的分析 154
7.3 交換排序 154
7.3.1 冒泡排序 154
7.3.2 對冒泡排序的分析 156
7.3.3 快速排序 156
7.3.4 實際的快速排序程序 158
7.3.5 對快速排序的分析 160
7.4 選擇排序 160
7.4.1 算法實現(xiàn) 161
7.4.2 效率分析 161
7.5 歸并排序 162
7.5.1 二路歸并排序 162
7.5.2 對歸并排序的分析 164
7.6 基數(shù)排序 165
7.6.1 多關(guān)鍵字的排序 165
7.6.2 鏈?zhǔn)交鶖?shù)排序 166
7.6.3 對基數(shù)排序的分析 168
7.7 外部排序 171
7.7.1 外部排序的概念 171
7.7.2 簡單算法 171
7.7.3 多路合并 172
7.7.4 多相合并 173
7.7.5 替換選擇 175
7.8 ArrayList與LinkedList中的排序方法 176
7.8.1 ArrayList中的排序方法 176
7.8.2 LinkedList中的排序方法 176
7.9 總結(jié) 178
第8章 樹 180
8.1 樹的基礎(chǔ)知識 180
8.1.1 基本術(shù)語 180
8.1.2 樹的ADT 182
8.1.3 樹的表示 184
8.1.4 樹的實現(xiàn) 184
8.2 樹的遍歷 185
8.2.1 前序遍歷 186
8.2.2 后序遍歷 188
8.3 二叉樹 190
8.3.1 二叉樹基本概念 190
8.3.2 二叉樹的性質(zhì) 194
8.3.3 二叉樹的實現(xiàn) 196
8.3.4 二叉樹的遍歷方法以及非遞歸實現(xiàn) 198
8.3.5 表達(dá)式樹 205
8.3.6 哈夫曼樹 212
8.3.7 決策樹 220
8.4 二叉查找樹 223
8.4.1 二叉查找樹的概念 223
8.4.2 查找操作 225
8.4.3 插入操作 227
8.4.4 刪除操作 228
8.4.5 性能分析 231
8.5 二叉平衡樹 233
8.5.1 二叉平衡樹的概念 233
8.5.2 平衡化策略 235
8.5.3 平衡樹的實現(xiàn) 242
8.6 其他一些樹 248
8.6.1 伸展樹 248
8.6.2 B-樹 249
8.6.3 紅黑樹的概念 254
8.6.4 紅黑樹的實現(xiàn) 256
8.7 總結(jié) 263
第9章 優(yōu)先隊列（堆） 265
9.1 基本概念和簡單實現(xiàn) 265
9.2 二叉堆 266
9.2.1 堆ADT 268
9.2.2 基本的堆操作 268
9.3 d-堆 273
9.4 左式堆 274
9.4.1 左式堆的性質(zhì) 274
9.4.2 左式堆的操作 275
9.5 斜堆 280
9.6 二項隊列 282
9.6.1 二項隊列的結(jié)構(gòu) 282
9.6.2 二項隊列的操作 283
9.6.3 二項隊列的實現(xiàn) 286
9.7 優(yōu)先隊列的應(yīng)用 291
9.7.1 堆排序 291
9.7.2 選擇問題 293
9.7.3 事件模擬 294
9.8 總結(jié) 295
第10章 圖論算法 296
10.1 圖的基本概念 296
10.1.1 定義與術(shù)語 297
10.1.2 圖ADT 300
10.2 圖的存儲 300
10.2.1 矩陣表示法 300
10.2.2 鄰接矩陣表示法的實現(xiàn) 303
10.2.3 鄰接表表示法 305
10.2.4 鄰接表表示法的實現(xiàn) 306
10.3 圖的遍歷 308
10.3.1 廣度優(yōu)先遍歷 308
10.3.2 深度優(yōu)先遍歷 311
10.3.3 圖的連通性 314
10.4 拓?fù)渑判?316
10.4.1 AOV網(wǎng)絡(luò) 316
10.4.2 拓?fù)渑判虻母拍?317
10.4.3 拓?fù)渑判蛩惴捌鋵崿F(xiàn) 318
10.5 關(guān)鍵路徑 320
10.5.1 AOE網(wǎng)絡(luò) 320
10.5.2 關(guān)鍵路徑的概念 321
10.5.3 關(guān)鍵路徑算法及其實現(xiàn) 323
10.6 *小代價生成樹 325
10.6.1 *小代價生成樹的概念 325
10.6.2 Prim算法 326
10.6.3 Kruskal算法 329
10.7 *短路徑問題 333
10.7.1 問題描述 333
10.7.2 Dijkstra算法 334
10.7.3 Floyd算法 338
10.8 總結(jié) 341
參考文獻(xiàn) 342
附錄 343
展開全部
數(shù)據(jù)結(jié)構(gòu)(JavaScript語言版) 節(jié)選
第1章 緒論 本章闡述本書的目的和目標(biāo)，并簡要介紹學(xué)習(xí)本書所需要的數(shù)學(xué)知識，我們將要學(xué)習(xí)到： 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 本書其余部分所需要的基本的數(shù)學(xué)知識 1.1 幾個實際問題 1.1.1 學(xué)生成績表管理 學(xué)生的成績數(shù)據(jù)如表1.1所示。 表1.1 學(xué)生成績表(單位：分) 我們把表1.1稱為一個數(shù)據(jù)結(jié)構(gòu)（線性表），表中的每一行是一個節(jié)點（或記錄），它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項組成。 接下來的問題是如何快速根據(jù)成績確定其中第 k 名是誰。我們將之稱為選擇問題(selection problem)。大多數(shù)學(xué)習(xí)過一兩門程序設(shè)計課程的學(xué)生寫一個解決這種問題的程序不會有什么困難，因為顯而易見的解決方法就有很多。 該問題的一種解法就是將這 n 個元素讀進(jìn)一個數(shù)組中，通過某種簡單的算法，如冒泡排序法，以遞減順序?qū)?shù)組排序，然后返回位置 k 上的元素。 稍好一點的算法可以先把前 k 個元素讀入數(shù)組（以遞減的順序）并對其進(jìn)行排序。然后，將剩下的元素再逐個讀入，當(dāng)新元素被讀到時，如果它小于數(shù)組中的第 k 個元素則忽略，否則將其放到數(shù)組中正確的位置上，同時將數(shù)組中的一個元素擠出數(shù)組。當(dāng)算法終止時，位于第 k 個位置上的元素作為答案返回。 這兩種算法編碼都很簡單，建議讀者進(jìn)行嘗試。此時自然要問：哪種算法更好？哪種算法更重要？還是兩種算法都足夠好？使用含有100萬個元素的隨機(jī)文件，在 k =50000的條件下進(jìn)行模擬，可以發(fā)現(xiàn)，兩種算法都不能在合理的時間內(nèi)結(jié)束；兩種算法都需要計算機(jī)處理若干天才能算出（雖然*后還是給出了正確的答案）。在第7章中將討論另外一種算法，該算法將在1s 左右給出問題的解。因此，雖然前面提到的兩種算法都能計算出結(jié)果，但是不能認(rèn)為它們是好的算法，要想在合理的時間內(nèi)完成大量輸入數(shù)據(jù)的處理，用這兩種算法是不切實際的。 1.1.2 人機(jī)對弈 計算機(jī)之所以能和人對弈是因為有人事先已將對弈的策略存入計算機(jī)。由于對弈的過程是在一定規(guī)則下隨機(jī)進(jìn)行的，所以為使計算機(jī)能靈活對弈，必須將對弈過程中所有可能發(fā)生的情況以及相應(yīng)的對策都考慮周全，并且一個好的棋手，在對弈時不僅要看棋盤當(dāng)時的狀態(tài)，還要能預(yù)測棋局發(fā)展的趨勢，甚至是*后的結(jié)局。在對弈問題中，計算機(jī)的操作對象是對弈過程中可能出現(xiàn)的棋盤狀態(tài)——格局，格局之間的關(guān)系是由對弈規(guī)則決定的。 以井字棋(tic-tac-toe)為例，井字棋是一種在3×3格子上進(jìn)行的連珠游戲，和五子棋類似，由于棋盤一般不畫邊框，格線排成井字故得名。游戲規(guī)則是：由分別代表 O 和×的兩個游戲者輪流在格子里留下標(biāo)記（一般來說先手者為×），任意三個相同標(biāo)記形成一條直線，則為獲勝。圖1.1是井字棋的一個格局，從當(dāng)前格局可以派生出五個格局，這種格局之間的關(guān)系可以用樹的數(shù)據(jù)結(jié)構(gòu)來描述。如果將對弈開始到結(jié)束的過程中可能出現(xiàn)的格局都畫在一張圖上，則可得到一棵倒長的樹。樹根是對弈開始之前的棋盤格局，而所有的葉子就是可能出現(xiàn)的結(jié)局，對弈的過程就是從樹根沿樹杈到某個葉子的過程。樹可以是某些非數(shù)值計算問題的數(shù)學(xué)模型，它也是一種數(shù)據(jù)結(jié)構(gòu)。 圖1.1 一個井字棋游戲中的格局 1.1.3 路徑導(dǎo)航 在交通網(wǎng)絡(luò)中經(jīng)常會遇到這樣的問題：兩地之間是否有公路可通？在有多條公路可通的情況下，哪一條路徑是*短的？ 圖1.2是廣州城市的簡化圖，假如某人從新城東出發(fā)，前往機(jī)場，如果各點之間的距離已知，找到一條*短的路徑顯然是*佳策略。要做到這一點，就需要用到圖的數(shù)據(jù)結(jié)構(gòu)和*短路徑算法。除了路徑導(dǎo)航問題，在供暖、供氣、供電、供水管道的設(shè)計和公路建設(shè)中，為了節(jié)省費用也需要用到這種算法。 圖1.2 廣州城市的簡化圖 在許多問題當(dāng)中，一個重要的觀念是：寫出一個可以工作的程序并不夠，如果這個程序在巨大的數(shù)據(jù)集上運行，那么運行效率就變成了重要的問題。讀者將在本書中看到對于大量的輸入如何估計程序的運行時間，尤其是如何在尚未具體編碼的情況下比較兩個程序的運行時間。讀者還將學(xué)到提升程序速度以及確定程序瓶頸的方法。這些方法將使讀者能夠找到需要大力優(yōu)化的代碼段。 1.2 本書主要討論內(nèi)容 1.2.1 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容 數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率，因此，數(shù)據(jù)結(jié)構(gòu)往往與高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)界至今沒有標(biāo)準(zhǔn)的定義，個人根據(jù)各自的理解的不同而有不同的表述方法。 Sahni 在他的《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用——C++語言描述》一書中稱：數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象，以及存在于該對象的實例和組成實例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出。Shaffer 在《數(shù)據(jù)結(jié)構(gòu)與算法分析（C++版）》一書中的定義是：數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型（abstract data type，ADT）的物理實現(xiàn)。 1.2.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 有人說：如果對編程思想不理解，哪怕會一千種語言，也寫不出好的程序。數(shù)據(jù)結(jié)構(gòu)和算法講授的是編程的思想，學(xué)習(xí)它的意義可以從兩個方面來講。 1.技術(shù)層面 數(shù)據(jù)結(jié)構(gòu)是編程*重要的基本功之一。“數(shù)據(jù)結(jié)構(gòu)”課程并不涵蓋編程的語法，而是提供解決問題的思路，這些思路是眾多科學(xué)家智慧的結(jié)晶，適用于所有編程語言，在編程遇到運行效率上的瓶頸時，或是在接到一個任務(wù)，需要評估這個任務(wù)能否實現(xiàn)時，這些前人的方案就可以提供參考。例如，擰螺母時，可以用扳手，也可以用鉗子，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)可以了解已有哪些工具、這些工具各有什么利弊、應(yīng)用于什么場景，知道究竟該用扳手還是鉗子。 例如，涉及后進(jìn)先出的問題有很多，函數(shù)遞歸就是個棧模型，Android 的屏幕跳轉(zhuǎn)就用到棧。對于很多類似的問題，學(xué)了棧之后，就會**時間想到可以用棧實現(xiàn)這些功能。 例如，有多個網(wǎng)絡(luò)下載任務(wù)，該怎么去調(diào)度它們?nèi)カ@得網(wǎng)絡(luò)資源呢？再如，對于操作系統(tǒng)的進(jìn)程（線程）調(diào)度，該怎么去分配資源[如中央處理器（centralprocessing unit，CPU）]給多個任務(wù)呢？肯定不能全部同時擁有，資源只有一個，那就要排隊。對于先進(jìn)先出要排隊的問題，學(xué)了隊列之后，就會想到要用隊列。那么怎么排隊呢？對于那些優(yōu)先級高的線程怎么辦？這時就會想到優(yōu)先隊列。 以后實踐的過程中會發(fā)現(xiàn)這些基礎(chǔ)的工具也存在一些缺陷，在不滿足于這些工具后，就會開始在這些數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上加以改造，這就稱為自定義數(shù)據(jù)結(jié)構(gòu)，以后還可以造出很多其他應(yīng)用于實際場景的數(shù)據(jù)結(jié)構(gòu)。 2.抽象層面 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法會擴(kuò)展視野，比如，平時編程中用到數(shù)組，如果不懂?dāng)?shù)據(jù)結(jié)構(gòu)和算法，就只能認(rèn)識到數(shù)組只是存儲一系列有序元素的集合，但是學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)就會對數(shù)組的認(rèn)識更加深刻。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法能夠指導(dǎo)如何將數(shù)據(jù)組織起來。例如，若想把家譜管理起來，就需要對家譜數(shù)據(jù)進(jìn)行抽象，將數(shù)據(jù)分解成樹狀結(jié)構(gòu)的節(jié)點，但是計算機(jī)無法理解人的抽象，計算機(jī)中只有0和1，某個節(jié)點和其他節(jié)點的關(guān)系如何互相得到，這是程序員要做的，也是數(shù)據(jù)結(jié)構(gòu)要介紹的。因此，了解數(shù)據(jù)結(jié)構(gòu)，對選擇程序結(jié)構(gòu)、選擇方案、提出解決方法都有很大幫助。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能夠幫助提高解決問題的能力。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是學(xué)習(xí)如何將物理世界里的信息變成計算機(jī)世界里的數(shù)據(jù)，并且是高效存儲、快速檢索數(shù)據(jù)的過程，是一個樹立計算思維的過程。計算思維是指運用計算機(jī)科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類的行為。當(dāng)必須求解一個特定的問題時，首先會問：解決這個問題有多困難？怎樣才是*佳的解決方法？數(shù)據(jù)結(jié)構(gòu)就是準(zhǔn)確地回答這些問題的理論基礎(chǔ)。 1.3 數(shù)學(xué)知識復(fù)習(xí) 本節(jié)列出一些需要記住或者能夠推導(dǎo)出的基本公式，復(fù)習(xí)基本的證明方法。 1.3.1 指數(shù) 具體公式如下： 1.3.2 對數(shù) 在計算機(jī)科學(xué)中，除非有特別的聲明，所有的對數(shù)都是以2為底的。 定義1.1 XA = B，當(dāng)且僅當(dāng) logX B = A。 由該定義可以得到幾個方便的等式。 定理1.1 證明： 令，以及。此時由對數(shù)的定義得：CX = B，CY = A 以及 AZ = B。聯(lián)合這三個等式則產(chǎn)生(CY )Z = B = CX。此時 X = Y Z，這意味著 Z =XY，定理1.1得證。 定理1.2 logAB = logA + logB 證明：令 X = log A， Y = logB，以及 Z = logAB。此時由于假設(shè)默認(rèn)的底數(shù)為2，2X = A，2Y = B 及2Z = AB。聯(lián)合后面的三個等式則有。因此 X + Y = Z，這就證明了該定理。 其他一些有用的公式如下，它們都能夠用類似的方法推導(dǎo)： 1.3.3 級數(shù) *容易記憶的公式是 在第二個公式中，如果0< A <1，則
書友推薦
- >
【精裝繪本】畫給孩子的中國神話
- >
隨園食單
- >
推拿
- >
唐代進(jìn)士錄
- >
二體千字文
- >
伊索寓言-世界文學(xué)名著典藏-全譯本
- >
姑媽的寶刀
- >
山海經(jīng)
本類暢銷
