本書是數(shù)據(jù)結(jié)構(gòu)和算法分析領(lǐng)域的教材。全書以 C++作為具體的實現(xiàn)語言，介紹了表、棧、隊列、樹、哈希表、優(yōu)先隊列、排序、不相交集算法、圖論算法、算法分析、算法設(shè)計、攤還分析、查找樹算法、后綴數(shù)組、后綴樹、k-d 樹、配對堆等內(nèi)容。本書把算法分析和 C++程序的開發(fā)有機結(jié)合起來，深入剖析每種算法，內(nèi)容縝密嚴(yán)謹(jǐn)，還詳細(xì)講解了精心構(gòu)建程序的方法。
本書可作為高等院校計算機相關(guān)專業(yè)的教學(xué)用書或參考用書，也可供計算機領(lǐng)域的工程技術(shù)人員參考
1. 用C++新標(biāo)準(zhǔn)C++11的代碼講數(shù)據(jù)結(jié)構(gòu)和算法分析；
2. 作者所寫的數(shù)據(jù)結(jié)構(gòu)和算法分析書籍銷量好，好評多，已被世界上很多大學(xué)用作教材。
Mark Allen Weiss，佛羅里達(dá)國際大學(xué)計算與信息科學(xué)學(xué)院教授、副院長，本科教育主任和研究生教育主任。他于1987年獲得普林斯頓大學(xué)計算機科學(xué)博士學(xué)位，師從Bob Sedgewick。他曾經(jīng)擔(dān)任全美AP(Advanced Placement)考試計算機學(xué)科委員會的主席(2000-2004)。Weiss教授在數(shù)據(jù)結(jié)構(gòu)和算法分析方面卓有建樹，他的數(shù)據(jù)結(jié)構(gòu)和算法分析的書籍，受到廣泛好評．已被世界500余所大學(xué)用作教材。
Chapter 1 Programming: A General Overview / 第 1章 程序設(shè)計：概述 1
1.1 What’s This Book About / 本書討論的內(nèi)容 1
1.2 Mathematics Review / 數(shù)學(xué)知識復(fù)習(xí) 2
1.2.1 Exponents / 指數(shù) 3
1.2.2 Logarithms / 對數(shù) 3
1.2.3 Series / 級數(shù) 4
1.2.4 Modular Arithmetic / 模運算 5
1.2.5 The P Word / 證明方法 6
1.3 A Brief Introduction to Recursion / 遞歸簡論 8
1.4 C++ Classes / C類 12
1.4.1 Basic class Syntax / 基本的class語法 12
1.4.2 Extra Constructor Syntax and Accessors / 構(gòu)造函數(shù)的附加語法和訪問函數(shù) 13
1.4.3 Separation of Interface and Implementation / 接口與實現(xiàn)的分離 16
1.4.4 vector and string / vector類和string類 19
1.5 C++Details / C細(xì)節(jié) 21
1.5.1 Pointers / 指針 21
1.5.2 Lvalues, Rvalues, and References / 左值、右值和引用 23
1.5.3 Parameter Passing / 參數(shù)傳遞 25
1.5.4 Return Passing / 返回值傳遞 27
1.5.5 std::swap and std::move / std::swap和std::move 29
1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= / 五大函數(shù)：析構(gòu)函數(shù)、拷貝構(gòu)造函數(shù)、移動構(gòu)造函數(shù)、拷貝賦值operator=和移動賦值operator= 30
1.5.7 C-style Arrays and Strings / C風(fēng)格數(shù)組和字符串 35
1.6 Templates / 模板 36
1.6.1 Function Templates / 函數(shù)模板 37
1.6.2 Class Templates / 類模板 38
1.6.3 Object, Comparable, and an Example / Object、Comparable和一個例子 39
1.6.4 Function Objects / 函數(shù)對象 41
1.6.5 Separate Compilation of Class Templates / 類模板的分離式編譯 44
1.7 Using Matrices / 使用矩陣 44
1.7.1 The Data Members, Constructor, and Basic Accessors / 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本訪問函數(shù) 44
1.7.2 operator[] / operator[] 45
1.7.3 Big-Five / 五大函數(shù) 46
Summary / 小結(jié) 46
Exercises / 練習(xí) 46
References / 參考文獻(xiàn) 48
Chapter 2 Algorithm Analysis / 第 2章 算法分析 51
2.1 Mathematical Background / 數(shù)學(xué)基礎(chǔ) 51
2.2 Model / 模型 54
2.3 What to Analyze / 要分析的問題 54
2.4 Running-Time Calculations / 運行時間計算 57
2.4.1 A Simple Example / 一個簡單的例子 58
2.4.2 General Rules / 一般法則 58
2.4.3 Solutions for the Maximum Subsequence Sum Problem / 最大子序列和問題的求解 60
2.4.4 Logarithms in the Running Time / 運行時間中的對數(shù) 66
2.4.5 Limitations of Worst-Case Analysis / 最壞情形分析的局限性 70
Summary / 小結(jié) 70
Exercises / 練習(xí) 71
References / 參考文獻(xiàn)
76
Chapter 3 Lists, Stacks, and Queues / 第3章 表、棧和隊列 77
3.1 Abstract Data Types (ADTs) / 抽象數(shù)據(jù)類型 77
3.2 The List ADT / 表的抽象數(shù)據(jù)類型 78
3.2.1 Simple Array Implementation of Lists / 表的簡單數(shù)組實現(xiàn) 78
3.2.2 Simple Linked Lists / 簡單鏈表 79
3.3 vector and list in the STL / STL中的vector和list 80
3.3.1 Iterators / 迭代器 82
3.3.2 Example: Using erase on a List / 例子：對表使用erase 83
3.3.3 const_iterators / const_iterators 84
3.4 Implementation of vector / vector的實現(xiàn) 86
3.5 Implementation of list / list的實現(xiàn) 91
3.6 The Stack ADT / 棧的抽象數(shù)據(jù)類型 103
3.6.1 Stack Model / 棧模型 103
3.6.2 Implementation of Stacks / 棧的實現(xiàn) 104
3.6.3 Applications / 應(yīng)用 104
3.7 The Queue ADT / 隊列的抽象數(shù)據(jù)類型 112
3.7.1 Queue Model / 隊列模型 113
3.7.2 Array Implementation of Queues / 隊列的數(shù)組實現(xiàn) 113
3.7.3 Applications of Queues / 隊列的應(yīng)用 115
Summary / 小結(jié) 116
Exercises / 練習(xí) 116
Chapter 4 Trees / 第4章 樹 121
4.1 Preliminaries / 預(yù)備知識 121
4.1.1 Implementation of Trees / 樹的實現(xiàn) 122
4.1.2 Tree Traversals with an Application / 樹的遍歷及應(yīng)用 123
4.2 Binary Trees / 二叉樹 126
4.2.1 Implementation / 實現(xiàn) 128
4.2.2 An Example: Expression Trees / 一個例子——表達(dá)式樹 128
4.3 The Search Tree ADT—Binary Search Trees / 查找樹的抽象數(shù)據(jù)類型——二叉查找樹 132
4.3.1 contains / contains 134
4.3.2 findMin and findMax / findMin和findMax 135
4.3.3 insert / insert 136
4.3.4 remove / remove 139
4.3.5 Destructor and Copy Constructor / 析構(gòu)函數(shù)和拷貝構(gòu)造函數(shù) 141
4.3.6 Average-Case Analysis / 平均情況分析 141
4.4 AVL Trees / AVL樹 144
4.4.1 Single Rotation / 單旋轉(zhuǎn) 147
4.4.2 Double Rotation / 雙旋轉(zhuǎn) 149
4.5 Splay Trees / 伸展樹 158
4.5.1 A Simple Idea (That Does Not Work) / 一個簡單的想法（不能直接使用） 158
4.5.2 Splaying / 展開 160
4.6 Tree Traversals (Revisited) / 樹的遍歷（再次討論） 166
4.7 B-Trees / B樹 168
4.8 Sets and Maps in the Standard Library / 標(biāo)準(zhǔn)庫中的集合與映射 173
4.8.1 Sets / 集合 173
4.8.2 Maps / 映射 174
4.8.3 Implementation of set and map / set和map的實現(xiàn) 175
4.8.4 An Example That Uses Several Maps / 使用多個映射的示例 176
Summary / 小結(jié) 181
Exercises / 練習(xí) 182
References / 參考文獻(xiàn) 189
Chapter 5 Hashing / 第5章 哈希 193
5.1 General Idea / 一般想法 193
5.2 Hash Function / 哈希函數(shù) 194
5.3 Separate Chaining / 分離鏈接法 196
5.4 Hash Tables without Linked Lists / 不用鏈表的哈希表 201
5.4.1 Linear Probing / 線性探測法 201
5.4.2 Quadratic Probing / 平方探測法 202
5.4.3 Double Hashing / 雙哈希 207
5.5 Rehashing / 再哈希 208
5.6 Hash Tables in the Standard Library / 標(biāo)準(zhǔn)庫中的哈希表 210
5.7 Hash Tables with Worst-Case O(1) Access / 以最壞情形O(1)訪問的哈希表 212
5.7.1 Perfect Hashing / 完美哈希 213
5.7.2 Cuckoo Hashing / 杜鵑哈希 215
5.7.3 Hopscotch Hashing / 跳房子哈希 227
5.8 Universal Hashing / 通用哈希 230
5.9 Extendible Hashing / 可擴哈希 233
Summary / 小結(jié) 236
Exercises / 練習(xí) 237
References / 參考文獻(xiàn) 241
Chapter 6 Priority Queues (Heaps) / 第6章 優(yōu)先隊列（堆） 245
6.1 Model / 模型 245
6.2 Simple Implementations / 一些簡單的實現(xiàn) 246
6.3 Binary Heap / 二叉堆 247
6.3.1 Structure Property / 結(jié)構(gòu)性質(zhì) 247
6.3.2 Heap-Order Property / 堆序性質(zhì) 248
6.3.3 Basic Heap Operations / 基本的堆操作 249
6.3.4 Other Heap Operations / 其他的堆操作 252
6.4 Applications of Priority Queues / 優(yōu)先隊列的應(yīng)用 257
6.4.1 The Selection Problem / 選擇問題 258
6.4.2 Event Simulation / 事件模擬 259
6.5 d-Heaps / d堆 260
6.6 Leftist Heaps / 左式堆 261
6.6.1 Leftist Heap Property / 左式堆的性質(zhì) 261
6.6.2 Leftist Heap Operations / 左式堆操作 262
6.7 Skew Heaps / 斜堆 269
6.8 Binomial Queues / 二項隊列 271
6.8.1 Binomial Queue Structure / 二項隊列構(gòu)建 271
6.8.2 Binomial Queue Operations / 二項隊列操作 271
6.8.3 Implementation of Binomial Queues / 二項隊列的實現(xiàn) 276
6.9 Priority Queues in the Standard Library / 標(biāo)準(zhǔn)庫中的優(yōu)先隊列 282
Summary / 小結(jié) 283
Exercises / 練習(xí) 283
References / 參考文獻(xiàn) 288
Chapter 7 Sorting / 第7章 排序 291
7.1 Preliminaries / 預(yù)備知識 291
7.2 Insertion Sort / 插入排序 292
7.2.1 The Algorithm / 算法 292
7.2.2 STL Implementation of Insertion Sort / 插入排序的STL實現(xiàn) 293
7.2.3 Analysis of Insertion Sort / 插入排序的分析 294
7.3 A Lower Bound for Simple Sorting Algorithms / 一些簡單排序算法的下界 295
7.4 Shellsort / 希爾排序 296
7.4.1 Worst-Case Analysis of Shellsort / 希爾排序的最壞情形分析 297
7.5 Heapsort / 堆排序 300
7.5.1 Analysis of Heapsort / 堆排序的分析 301
7.6 Mergesort / 歸并排序 304
7.6.1 Analysis of Mergesort / 歸并排序的分析 306
7.7 Quicksort / 快速排序 309
7.7.1 Picking the Pivot / 選取樞紐元 311
7.7.2 Partitioning Strategy / 分割策略 313
7.7.3 Small Arrays / 小數(shù)組 315
7.7.4 Actual Quicksort Routines / 實際的快速排序例程 315
7.7.5 Analysis of Quicksort / 快速排序的分析 318
7.7.6 A Linear-Expected-Time Algorithm for Selection / 選擇問題的線性期望時間算法 321
7.8 A General Lower Bound for Sorting / 排序算法的一般下界 323
7.8.1 Decision Trees / 決策樹 323
7.9 Decision-Tree Lower Bounds for Selection Problems / 選擇問題的決策樹下界 325
7.10 Adversary Lower Bounds / 對手下界 328
7.11 Linear-Time Sorts: Bucket Sort and Radix Sort / 線性時間排序：桶式排序和基數(shù)排序 331
7.12 External Sorting / 外部排序 336
7.12.1 Why We Need New Algorithms / 為什么需要一些新的算法 336
7.12.2 Model for External Sorting / 外部排序模型 336
7.12.3 The Simple Algorithm / 簡單算法 337
7.12.4 Multiway Merge / 多路合并 338
7.12.5 Polyphase Merge / 多相合并 339
7.12.6 Replacement Selection / 替換選擇 340
Summary / 小結(jié) 341
Exercises / 練習(xí) 341
References / 參考文獻(xiàn) 347
Chapter 8 The Disjoint Sets Class / 第8章 不相交集算法 351
8.1 Equivalence Relations / 等價關(guān)系 351
8.2 The Dynamic Equivalence Problem / 動態(tài)等價性問題 352
8.3 Basic Data Structure / 基本數(shù)據(jù)結(jié)構(gòu) 353
8.4 Smart Union Algorithms / 靈巧求并算法 357
8.5 Path Compression / 路徑壓縮 360
8.6 Worst Case for Union-by-Rank and Path Compression / 按秩求并和路徑壓縮的最壞情形 361
8.6.1 Slowly Growing Functions / 緩慢增長的函數(shù) 362
8.6.2 An Analysis by Recursive Decomposition / 通過遞歸分解進(jìn)行的分析 362
8.6.3 An O (M log*N) Bound / 一個O (M log*N)界 369
8.6.4 An O (Mα(M, N)) Bound / 一個O (Mα(M, N))界 370
8.7 An Application / 一個應(yīng)用 372
Summary / 小結(jié) 374
Exercises / 練習(xí) 375
References / 參考文獻(xiàn) 376
Chapter 9 Graph Algorithms / 第9章 圖論算法 379
9.1 Definitions / 若干定義 379
9.1.1 Representation of Graphs / 圖的表示 380
9.2 Topological Sort / 拓?fù)渑判颉 ?82
9.3 Shortest-Path Algorithms / 最短路徑算法 386
9.3.1 Unweighted Shortest Paths / 無權(quán)最短路徑 387
9.3.2 Dijkstra’s Algorithm / Dijkstra算法 391
9.3.3 Graphs with Negative Edge Costs / 具有負(fù)邊值的圖 400
9.3.4 Acyclic Graphs / 無圈圖 400
9.3.5 All-Pairs Shortest Path / 所有頂點對間的最短路徑 404
9.3.6 Shortest Path Example / 最短路徑的例 404
9.4 Network Flow Problems / 網(wǎng)絡(luò)流問題 406
9.4.1 A Simple Maximum-Flow Algorithm / 一個簡單的最大流算法 408
9.5 Minimum Spanning Tree / 最小生成樹 413
9.5.1 Prim’s Algorithm / Prim算法 414
9.5.2 Kruskal’s Algorithm / Kruskal算法 417
9.6 Applications of Depth-First Search / 深度優(yōu)先搜索的應(yīng)用 419
9.6.1 Undirected Graphs / 無向圖 420
9.6.2 Biconnectivity / 雙連通性 421
9.6.3 Euler Circuits / 歐拉回路 425
9.6.4 Directed Graphs / 有向圖 429
9.6.5 Finding Strong Components / 查找強分支 431
9.7 Introduction to NP-Completeness / NP完全性介紹 432
9.7.1 Easy vs. Hard / 難與易 433
9.7.2 The Class NP / NP類 434
9.7.3 NP-Complete Problems / NP完全問題 434
Summary / 小結(jié) 437
Exercises / 練習(xí) 437
References / 參考文獻(xiàn) 445
Chapter 10 Algorithm Design Techniques / 第 10章 算法設(shè)計技巧 449
10.1 Greedy Algorithms / 貪婪算法 449
10.1.1 A Simple Scheduling Problem / 一個簡單的調(diào)度問題 450
10.1.2 Huffman Codes / 哈夫曼編碼 453
10.1.3 Approximate Bin Packing / 近似裝箱問題 459
10.2 Divide and Conquer / 分治算法 467
10.2.1 Running Time of Divide-and-Conquer Algorithms / 分治算法的運行時間 468
10.2.2 Closest-Points Problem / 最近點問題 470
10.2.3 The Selection Problem / 選擇問題 475
10.2.4 Theoretical Improvements for Arithmetic Problems / 一些算術(shù)問題的理論改進(jìn) 478
10.3 Dynamic Programming / 動態(tài)規(guī)劃 482
10.3.1 Using a Table Instead of Recursion / 用表代替遞歸 483
10.3.2 Ordering Matrix Multiplications / 矩陣乘法的順序安排 485
10.3.3 Optimal Binary Search Tree / 二叉查找樹 487
10.3.4 All-Pairs Shortest Path / 所有點對最短路徑 491
10.4 Randomized Algorithms / 隨機化算法 494
10.4.1 Random-Number Generators / 隨機數(shù)發(fā)生器 495
10.4.2 Skip Lists / 跳躍表 500
10.4.3 Primality Testing / 素性測試 503
10.5 Backtracking Algorithms / 回溯算法 506
10.5.1 The Turnpike Reconstruction Problem / 收費公路重建問題 506
10.5.2 Games / 游戲 511
Summary / 小結(jié) 518
Exercises / 練習(xí) 518
References / 參考文獻(xiàn) 527
Chapter 11 Amortized Analysis / 第 11章 攤還分析 533
11.1 An Unrelated Puzzle / 一個無關(guān)的智力問題 534
11.2 Binomial Queues / 二項隊列 534
11.3 Skew Heaps / 斜堆 539
11.4 Fibonacci Heaps / 斐波那契堆 541
11.4.1 Cutting Nodes in Leftist Heaps / 切除左式堆中的節(jié)點 542
11.4.2 Lazy Merging for Binomial Queues / 二項隊列的懶惰合并 544
11.4.3 The Fibonacci Heap Operations / 斐波那契堆操作 548
11.4.4 Proof of the Time Bound / 時間界的證明 549
11.5 Splay Trees / 伸展樹 551
Summary / 小結(jié) 555
Exercises / 練習(xí) 556
References / 參考文獻(xiàn) 557
Chapter 12 Advanced Data Structures and Implementation / 第 12章 高級數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn) 559
12.1 Top-Down Splay Trees / 自頂向下伸展樹 559
12.2 Red-Black Trees / 紅黑樹 566
12.2.1 Bottom-Up Insertion / 自底向上的插入 567
12.2.2 Top-Down Red-Black Trees / 自頂向下紅黑樹 568
12.2.3 Top-Down Deletion / 自頂向下刪除 570
12.3 Treaps / treap 樹 576
12.4 Suffix Arrays and Suffix Trees / 后綴數(shù)組和后綴樹 579
12.4.1 Suffix Arrays / 后綴數(shù)組 580
12.4.2 Suffix Trees / 后綴樹 583
12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees / 后綴數(shù)組和后綴樹的線性 586
12.5 k -d Trees / k-d 樹 596
12.6 Pairing Heaps / 配對堆 602
Summary / 小結(jié) 606
Exercises / 練習(xí) 608
References / 參考文獻(xiàn) 612
Appendix A Separate Compilation of Class Templates / 附錄A 類模板的分離式編譯 615
A.1 Everything in the Header / 頭文件中的內(nèi)容 616
A.2 Explicit Instantiation / 顯示實例化 616
新書資訊