具體描述
産品名稱：算法導論 ISBN編號: 9787111407010
産品名稱：數據結構、算法與應用：C++語言描述原書第2版 ISBN編號: 9787111496007
算法導論
《算法導論(原書第3版)》
齣版者的話
譯者序
前言
第一部分 基礎知識
第1章 算法在計算中的作用3
1.1 算法3
1.2 作為一種技術的算法6
思考題8
本章注記8
第2章 算法基礎9
2.1 插入排序9
2.2 分析算法13
2.3 設計算法16
2.3.1 分治法16
2.3.2 分析分治算法20
思考題22
本章注記24
第3章 函數的增長25
3.1 漸近記號25
3.2 標準記號與常用函數30
思考題35
本章注記36
第4章 分治策略37
4.1 最大子數組問題38
4.2 矩陣乘法的Strassen算法43
4.3 用代入法求解遞歸式47
4.4 用遞歸樹方法求解遞歸式50
4.5 用主方法求解遞歸式53
4.6 證明主定理55
4.6.1 對b的冪證明主定理56
4.6.2 嚮下取整和嚮上取整58
思考題60
本章注記62
第5章 概率分析和隨機算法65
5.1 雇用問題65
5.2 指示器隨機變量67
5.3 隨機算法69
��5.4 概率分析和指示器隨機變量的進一步使用73
5.4.1 生日悖論73
5.4.2 球與箱子75
5.4.3 特徵序列76
5.4.4 在綫雇用問題78
思考題79
本章注記80
第二部分 排序和順序統計量
第6章 堆排序84
6.1 堆84
6.2 維護堆的性質85
6.3 建堆87
6.4 堆排序算法89
6.5 優先隊列90
思考題93
本章注記94
第7章 快速排序95
7.1 快速排序的描述95
7.2 快速排序的性能97
7.3 快速排序的隨機化版本100
7.4 快速排序分析101
7.4.1 最壞情況分析101
7.4.2 期望運行時間101
思考題103
本章注記106
第8章 綫性時間排序107
8.1 排序算法的下界107
8.2 計數排序108
8.3 基數排序110
8.4 桶排序112
思考題114
本章注記118
第9章 中位數和順序統計量119
9.1 最小值和最大值119
9.2 期望為綫性時間的選擇算法120
9.3 最壞情況為綫性時間的選擇算法123
思考題125
本章注記126
第三部分 數據結構
第10章 基本數據結構129
10.1 棧和隊列129
10.2 鏈錶131
10.3 指針和對象的實現134
10.4 有根樹的錶示137
思考題139
本章注記141
第11章 散列錶142
11.1 直接尋址錶142
11.2 散列錶143
11.3 散列函數147
11.3.1 除法散列法147
11.3.2 乘法散列法148
11.3.3 全域散列法148
11.4 開放尋址法151
11.5 完全散列156
思考題158
本章注記160
第12章 二叉搜索樹161
12.1 什麼是二叉搜索樹161
12.2 查詢二叉搜索樹163
12.3 插入和刪除165
12.4 隨機構建二叉搜索樹169
思考題171
本章注記173
第13章 紅黑樹174
13.1 紅黑樹的性質174
13.2 鏇轉176
13.3 插入178
13.4 刪除183
思考題187
本章注記191
第14章 數據結構的擴張193
14.1 動態順序統計193
14.2 如何擴張數據結構196
14.3 區間樹198
思考題202
本章注記202
第四部分 高級設計和分析技術
第15章 動態規劃204
15.1 鋼條切割204
15.2 矩陣鏈乘法210
15.3 動態規劃原理215
15.4 最長公共子序列222
15.5 最優二叉搜索樹226
思考題231
本章注記236
第16章 貪心算法237
16.1 活動選擇問題237
16.2 貪心算法原理242
16.3 赫夫曼編碼245
16.4 擬陣和貪心算法250
16.5 用擬陣求解任務調度問題253
思考題255
本章注記257
第17章 攤還分析258
17.1 聚閤分析258
17.2 核算法261
17.3 勢能法262
17.4 動態錶264
17.4.1 錶擴張265
17.4.2 錶擴張和收縮267
思考題270
本章注記273
第五部分 高級數據結構
第18章 B樹277
18.1 B樹的定義279
18.2 B樹上的基本操作281
18.3 從B樹中刪除關鍵字286
思考題288
本章注記289
第19章 斐波那契堆290
19.1 斐波那契堆結構291
19.2 可閤並堆操作292
19.3 關鍵字減值和刪除一個結點298
19.4 最大度數的界300
思考題302
本章注記305
第20章 van Emde Boas樹306
20.1 基本方法306
20.2 遞歸結構308
20.2.1 原型van Emde Boas結構310
20.2.2 原型van Emde Boas結構上的操作311
20.3 van Emde Boas樹及其操作314
20.3.1 van Emde Boas樹315
20.3.2 van Emde Boas樹的操作317
思考題322
本章注記323
第21章 用於不相交集閤的數據結構324
21.1 不相交集閤的操作324
21.2 不相交集閤的鏈錶錶示326
21.3 不相交集閤森林328
*21.4 帶路徑壓縮的按秩閤並的分析331
思考題336
本章注記337
第六部分 圖算法
第22章 基本的圖算法341
22.1 圖的錶示341
22.2 廣度優先搜索343
22.3 深度優先搜索349
22.4 拓撲排序355
22.5 強連通分量357
思考題360
本章注記361
第23章 最小生成樹362
23.1 最小生成樹的形成362
23.2 Kruskal算法和Prim算法366
思考題370
本章注記373
第24章 單源最短路徑374
24.1 Bellman�睩ord算法379
24.2 有嚮無環圖中的單源最短路徑問題381
24.3 Dijkstra算法383
24.4 差分約束和最短路徑387
24.5 最短路徑性質的證明391
思考題395
本章注記398
第25章 所有結點對的最短路徑問題399
25.1 最短路徑和矩陣乘法400
25.2 Floyd�瞁arshall算法404
25.3 用於稀疏圖的Johnson算法409
思考題412
本章注記412
第26章 最大流414
26.1 流網絡414
26.2 Ford�睩ulkerson方法418
26.3 最大二分匹配428
26.4 推送重貼標簽算法431
26.5 前置重貼標簽算法438
思考題446
本章注記449
第七部分 算法問題選編
第27章 多綫程算法453
27.1 動態多綫程基礎454
27.2 多綫程矩陣乘法465
27.3 多綫程歸並排序468
思考題472
本章注記476
第28章 矩陣運算478
28.1 求解綫性方程組478
28.2 矩陣求逆486
28.3 對稱正定矩陣和最小二乘逼近489
思考題493
本章注記494
第29章 綫性規劃495
29.1 標準型和鬆弛型499
29.2 將問題錶達為綫性規劃504
29.3 單純形算法507
29.4 對偶性516
29.5 初始基本可行解520
思考題525
本章注記526
第30章 多項式與快速傅裏葉變換527
30.1 多項式的錶示528
30.2 DFT與FFT531
30.3 高效FFT實現536
思考題539
本章注記541
第31章 數論算法543
31.1 基礎數論概念543
31.2 最大公約數547
31.3 模運算550
31.4 求解模綫性方程554
31.5 中國餘數定理556
31.6 元素的冪558
31.7 RSA公鑰加密係統561
31.8 素數的測試565
31.9 整數的因子分解571
思考題574
本章注記576
第32章 字符串匹配577
32.1 樸素字符串匹配算法578
32.2 Rabin�睰arp算法580
32.3 利用有限自動機進行字符串匹配583
32.4 Knuth�睲orris�睵ratt算法588
思考題594
本章注記594
第33章 計算幾何學595
33.1 綫段的性質595
33.2 確定任意一對綫段是否相交599
33.3 尋找凸包604
33.4 尋找最近點對610
思考題613
本章注記615
第34章 NP完全性616
34.1 多項式時間619
34.2 多項式時間的驗證623
34.3 NP完全性與可歸約性626
34.4 NP完全性的證明633
34.5 NP完全問題638
34.5.1 團問題638
34.5.2 頂點覆蓋問題640
34.5.3 哈密頓迴路問題641
34.5.4 旅行商問題644
34.5.5 子集和問題645
思考題647
本章注記649
第35章 近似算法651
35.1 頂點覆蓋問題652
35.2 旅行商問題654
35.2.1 滿足三角不等式的旅行商問題654
35.2.2 一般旅行商問題656
35.3 集閤覆蓋問題658
35.4 隨機化和綫性規劃661
35.5 子集和問題663
思考題667
本章注記669
第八部分 附錄：數學基礎知識
附錄A 求和672
A.1 求和公式及其性質672
A.2 確定求和時間的界674
思考題678
附錄注記678
附錄B 集閤等離散數學內容679
B.1 集閤679
B.2 關係682
B.3 函數683
B.4 圖685
B.5 樹687
B.5.1 自由樹688
B.5.2 有根樹和有序樹689
B.5.3 二叉樹和位置樹690
思考題691
附錄注記692
附錄C 計數與概率693
C.1 計數693
C.2 概率696
C.3 離散隨機變量700
C.4 幾何分布與二項分布702
*C.5 二項分布的尾部705
思考題708
附錄注記708
附錄D 矩陣709
D.1 矩陣與矩陣運算709
D.2 矩陣基本性質712
思考題714
附錄注記715
參考文獻716
索引732
數據結構、算法與應用：C++語言描述原書第2版
Data Structures, Algorithms, and Applications in C++, Second Edition
齣版者的話
譯者序
前言
第一部分 預備知識
第1章 C++迴顧 2
1.1 引言 2
1.2 函數與參數 3
1.2.1 傳值參數 3
1.2.2 模闆函數 4
1.2.3 引用參數 4
1.2.4 常量引用參數 5
1.2.5 返迴值 5
1.2.6 重載函數 6
1.3 異常 7
1.3.1 拋齣異常 7
1.3.2 處理異常 7
1.4 動態存儲空間分配 9
1.4.1 操作符new 9
1.4.2 一維數組 9
1.4.3 異常處理 9
1.4.4 操作符delete 10
1.4.5 二維數組 10
1.5 自有數據類型 12
1.5.1 類currency 12
1.5.2 一種不同的描述方法 18
1.5.3 操作符重載 20
1.5.4 友元和保護性類成員 22
1.5.5 增加#ifndef、#define和#endif語句 23
1.6 異常類illegalParameterValue 24
1.7 遞歸函數 25
1.7.1 遞歸的數學函數 25
1.7.2 歸納 25
1.7.3 C++遞歸函數 26
1.8 標準模闆庫 30
1.9 測試與調試 32
1.9.1 什麼是測試 32
1.9.2 測試數據的設計 34
1.9.3 調試 36
1.10 參考及推薦讀物 37
第2章 程序性能分析 38
2.1 什麼是程序性能 38
2.2 空間復雜度 39
2.2.1 空間復雜度的組成 39
2.2.2 舉例 42
2.3 時間復雜度 44
2.3.1 時間復雜度的組成 44
2.3.2 操作計數 45
2.3.3 最好、最壞和平均操作計數 48
2.3.4 步數 53
第3章 漸近記法 64
3.1 引言 64
3.2 漸近記法 65
3.2.1 大Ο記法 65
3.2.2 漸近記法Ω和Θ 67
3.3 漸近數學（可選） 69
3.3.1 大O記法 69
3.3.2 Ω記法 71
3.3.3 Θ記法 72
3.3.4 小ο記法 73
3.3.5 特性 73
3.4 復雜度分析舉例 75
3.5 實際復雜度 78
3.6 參考及推薦讀物 80
第4章 性能測量 81
4.1 引言 81
4.2 選擇實例的大小 82
4.3 設計測試數據 82
4.4 實驗設計 82
4.5 高速緩存 87
4.5.1 簡單計算機模型 87
4.5.2 緩存未命中對運行時間的影響 87
4.5.3 矩陣乘法 88
4.6 參考及推薦讀物 90
第二部分 數據結構
第5章 綫性錶——數組描述 92
5.1 數據對象和數據結構 92
5.2 綫性錶數據結構 93
5.2.1 抽象數據類型linearList 94
5.2.2 抽象類linearList 94
5.3 數組描述 95
5.3.1 描述 95
5.3.2 變長一維數組 96
5.3.3 類arrayList 97
5.3.4 C++迭代器 102
5.3.5 arrayList的一個迭代器 103
5.4 vector的描述 107
5.5 在一個數組中實現的多重錶 109
5.6 性能測量 111
5.7 參考及推薦讀物 112
第6章 綫性錶——鏈式描述 113
6.1 單嚮鏈錶 113
6.1.1 描述 113
6.1.2 結構chainNode 114
6.1.3 類chain 115
6.1.4 抽象數據類型linearList的擴充 121
6.1.5 類extendedChain 121
6.1.6 性能測量 122
6.2 循環鏈錶和頭節點 126
6.3 雙嚮鏈錶 128
6.4 鏈錶用到的詞匯錶 129
6.5 應用 130
6.5.1 箱子排序 130
6.5.2 基數排序 134
6.5.3 凸包 135
6.5.4 並查集 137
第7章 數組和矩陣 146
7.1 數組 146
7.1.1 抽象數據類型 146
7.1.2 C++數組的索引 147
7.1.3 行主映射和列主映射 147
7.1.4 用數組的數組來描述 148
7.1.5 行主描述和列主描述 149
7.1.6 不規則二維數組 149
7.2 矩陣 151
7.2.1 定義和操作 151
7.2.2 類matrix 152
7.3 特殊矩陣 157
7.3.1 定義和應用 157
7.3.2 對角矩陣 158
7.3.3 三對角矩陣 159
7.3.4 三角矩陣 160
7.3.5 對稱矩陣 161
7.4 稀疏矩陣 164
7.4.1 基本概念 164
7.4.2 用單個綫性錶描述 165
7.4.3 用多個綫性錶描述 170
7.4.4 性能測量 172
第8章 棧 175
8.1 定義和應用 175
8.2 抽象數據類型 177
8.3 數組描述 178
8.3.1 作為一個派生類實現 178
8.3.2 類arrayStack 179
8.3.3 性能測量 181
8.4 鏈錶描述 182
8.4.1 類derivedLinkedStack 182
8.4.2 類linkedStack 183
8.4.3 性能測量 184
8.5 應用 184
8.5.1 括號匹配 184
8.5.2 漢諾塔 185
8.5.3 列車車廂重排 187
8.5.4 開關盒布綫 191
8.5.5 離綫等價類問題 193
8.5.6 迷宮老鼠 196
8.6 參考及推薦讀物 204
第9章 隊列 205
9.1 定義和應用 205
9.2 抽象數據類型 206
9.3 數組描述 207
9.3.1 描述 207
9.3.2 類arrayQueue 209
9.4 鏈錶描述 212
9.5 應用 214
9.5.1 列車車廂重排 214
9.5.2 電路布綫 217
9.5.3 圖元識彆 219
9.5.4 工廠仿真 222
9.6 參考及推薦讀物 234
第10章 跳錶和散列 235
10.1 字典 235
10.2 抽象數據類型 236
10.3 綫性錶描述 237
10.4 跳錶錶示（可選） 239
10.4.1 理想情況 239
10.4.2 插入和刪除 241
10.4.3 級的分配 241
10.4.4 結構skipNode 242
10.4.5 類skipList 242
10.4.6 skipList方法的復雜度 246
10.5 散列錶描述 246
10.5.1 理想散列 246
10.5.2 散列函數和散列錶 248
10.5.3 綫性探查 250
10.5.4 鏈式散列 255
10.6 一個應用——文本壓縮 260
10.6.1 LZW壓縮 260
10.6.2 LZW壓縮的實現 261
10.6.3 LZW解壓縮 264
10.6.4 LZW解壓縮的實現 265
10.6.5 性能評價 268
10.7 參考及推薦讀物 269
第11章 二叉樹和其他樹 270
11.1 樹 270
11.2 二叉樹 273
11.3 二叉樹的特性 274
11.4 二叉樹的描述 275
11.4.1 數組描述 275
11.4.2 鏈錶描述 276
11.5 二叉樹常用操作 277
11.6 二叉樹遍曆 277
11.7 抽象數據類型BinaryTree 281
11.8 類linkedBinaryTree 282
11.9 應用 285
11.9.1 設置信號放大器 285
11.9.2 並查集 288
11.10 參考及推薦讀物 296
第12章 優先級隊列 297
12.1 定義和應用 297
12.2 抽象數據類型 298
12.3 綫性錶 299
12.4 堆 299
12.4.1 定義 299
12.4.2 大根堆的插入 300
12.4.3 大根堆的刪除 301
12.4.4 大根堆的初始化 301
12.4.5 類maxHeap 302
12.4.6 堆和STL 305
12.5 左高樹 306
12.5.1 高度優先與寬度優先的最大及最小左高樹 306
12.5.2 最大HBLT的插入 308
12.5.3 最大HBLT的刪除 308
12.5.4 兩棵最大HBLT的閤並 308
12.5.5 初始化 309
12.5.6 類maxHblt 310
12.6 應用 313
12.6.1 堆排序 313
12.6.2 機器調度 314
12.6.3 霍夫曼編碼 317
12.7 參考及推薦讀物 322
第13章 競賽樹 323
13.1 贏者樹和應用 323
13.2 抽象數據類型WinnerTree 326
13.3 贏者樹的實現 327
13.3.1 錶示 327
13.3.2 贏者樹的初始化 328
13.3.3 重新組織比賽 328
13.3.4 類completeWinnerTree 328
13.4 輸者樹 329
13.5 應用 331
13.5.1 用最先適配法求解箱子裝載問題 331
13.5.2 用相鄰適配法求解箱子裝載問題 335
13.6 參考及推薦讀物 337
第14章 搜索樹 338
14.1 定義 338
14.1.1 二叉搜索樹 338
14.1.2 索引二叉搜索樹 340
14.2 抽象數據類型 340
14.3 二叉搜索樹的操作和實現 341
14.3.1 類binarySearchTree 341
14.3.2 搜索 342
14.3.3 插入 342
14.3.4 刪除 343
14.3.5 二叉搜索樹的高度 346
14.4 帶有相同關鍵字元素的二叉搜索樹 347
14.5 索引二叉搜索樹 348
14.6 應用 349
14.6.1 直方圖 349
14.6.2 箱子裝載問題的最優匹配法 351
14.6.3 交叉分布 353
第15章 平衡搜索樹 359
15.1 AVL樹 360
15.1.1 定義 360
15.1.2 AVL樹的高度 361
15.1.3 AVL樹的描述 361
15.1.4 AVL搜索樹的搜索 361
15.1.5 AVL搜索樹的插入 361
15.1.6 AVL搜索樹的刪除 364
15.2 紅-黑樹 367
15.2.1 基本概念 367
15.2.2 紅-黑樹的描述 368
15.2.3 紅-黑樹的搜索 368
15.2.4 紅-黑樹的插入 368
15.2.5 紅-黑樹的刪除 371
15.2.6 實現細節的考慮及復雜性分析 374
15.3 分裂樹 376
15.3.1 介紹 376
15.3.2 分裂樹的操作 376
15.3.3 摺算復雜性 378
15.4 B-樹 379
15.4.1 索引順序訪問方法 379
15.4.2 m叉搜索樹 380
15.4.3 m階B-樹 381
15.4.4 B-樹的高度 382
15.4.5 B-樹的搜索 382
15.4.6 B-樹的插入 382
15.4.7 B-樹的刪除 384
15.4.8 節點結構 387
15.5 參考及推薦讀物 389
第16章 圖 390
16.1 基本概念 390
16.2 應用和更多的概念 391
16.3 特性 394
16.4 抽象數據類型graph 395
16.5 無權圖的描述 396
16.5.1 鄰接矩陣 396
16.5.2 鄰接鏈錶 397
16.5.3 鄰接數組 398
16.6 加權圖的描述 400
16.7 類實現 400
16.7.1 不同的類 400
16.7.2 鄰接矩陣類 401
16.7.3 擴充chain類 405
16.7.4 鏈錶類 405
16.8 圖的遍曆 407
16.8.1 廣度優先搜索 407
16.8.2 廣度優先搜索的實現 408
16.8.3 方法graph::bfs的復雜性分析 409
16.8.4 深度優先搜索 410
16.8.5 深度優先搜索的實現 411
16.8.6 方法graph::dfs的復雜性分析 412
16.9 應用 412
16.9.1 尋找一條路徑 412
16.9.2 連通圖及其構成 414
16.9.3 生成樹 415
第三部分 算法設計方法
第17章 貪婪算法 420
17.1 最優化問題 420
17.2 貪婪算法思想 421
17.3 應用 424
17.3.1 貨箱裝載 424
17.3.2 0/1背包問題 425
17.3.3 拓撲排序 427
17.3.4 二分覆蓋 430
17.3.5 單源最短路徑 433
17.3.6 最小成本生成樹 436
17.4 參考及推薦讀物 445
第18章 分而治之 446
18.1 算法思想 446
18.2 應用 453
18.2.1 殘缺棋盤 453
18.2.2 歸並排序 455
18.2.3 快速排序 459
18.2.4 選擇 464
18.2.5 相距最近的點對 466
18.3 解遞歸方程 474
18.4 復雜度的下限 475
18.4.1 最小最大問題的下限 476
18.4.2 排序算法的下限 477
第19章 動態規劃 479
19.1 算法思想 479
19.2 應用 481
19.2.1 0/1背包問題 481
19.2.2 矩陣乘法鏈 484
19.2.3 所有頂點對之間的最短路徑 489
19.2.4 帶有負值的單源最短路徑 492
19.2.5 網組的無交叉子集 496
19.3 參考及推薦讀物 501
第20章 迴溯法 502
20.1 算法思想 502
20.2 應用 506
20.2.1 貨箱裝載 506
20.2.2 0/1背包問題 512
20.2.3 最大完備子圖 515
20.2.4 旅行商問題 517
20.2.5 電路闆排列 519
第21章 分支定界 525
21.1 算法思想 525
21.2 應用 528
21.2.1 貨箱裝載 528
21.2.2 0/1背包問題 535
21.2.3 最大完備子圖 536
21.2.4 旅行商問題 538
21.2.5 電路闆排列 541
算法導論
在有關算法的書中，有一些敘述非常嚴謹，但不夠全麵；另一些涉及瞭大量的題材，但又缺乏嚴謹性。本書將嚴謹性和全麵性融為一體，深入討論各類算法，並著力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體係，可以作為獨立的學習單元；算法以英語和僞代碼的形式描述，具備初步程序設計經驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數學嚴謹性。
《算法導論(原書第3版)》選材經典、內容豐富、結構閤理、邏輯清晰，對本科生的數據結構課程和研究生的算法課程都是非常實用的教材，在IT專業人員的職業生涯中，本書也是一本案頭必備的參考書或工程實踐手冊。
第3版的主要變化：
新增瞭van Emde Boas樹和多綫程算法，並且將矩陣基礎移至附錄。
修訂瞭遞歸式（現在稱為“分治策略”）那一章的內容，更廣泛地覆蓋分治法。
移除兩章很少講授的內容：二項堆和排序網絡。
修訂瞭動態規劃和貪心算法相關內容。
流網絡相關材料現在基於邊上的全部流。
由於關於矩陣基礎和Strassen算法的材料移到瞭其他章，矩陣運算這一章的內容所占篇幅更小。
修改瞭對Knuth-Morris-Pratt字符串匹配算法的討論。
新增100道練習和28道思考題，還更新並補充瞭參考文獻。
數據結構、算法與應用：C++語言描述原書第2版
全書共分三個部分。第一部分從第1章到第4章，旨在復習C++程序設計的概念以及程序性能的分析和測量方法。第二部分從第5章到第16章，研究數據結構，包括綫性錶的數組描述和鏈式描述，以及用這兩種描述方法描述的數組和矩陣、棧、隊列、字典、二叉樹、優先級隊列、競賽樹和圖等數據結構。第三部分從第17章到第21章，研究常用算法，包括貪婪算法、分而治之算法、動態規劃、迴溯算法和分支定界算法。
本書內容廣博、組織閤理、論述清晰、循序漸進，每章包含豐富的習題，對程序性能的分析和測量係統且細緻，不僅是數據結構和算法的經典教材，而且是計算機科學與工程領域的理想參考書。
用戶評價
評分
評分
評分
評分
評分
評分
評分
評分
相關圖書
本站所有內容均為互聯網搜尋引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 book.cndgn.com All Rights Reserved. 新城书站 版權所有