數(shù)據(jù)結(jié)構(gòu)與算法分析：C++語言描述（英文版 第4版）

Chapter 1　Programming： A General Overview / 第 1章　程序設(shè)計(jì)：概述　　　　1
1．1　What’s This Book About / 本書討論的內(nèi)容　　　　1
1．2　Mathematics Review / 數(shù)學(xué)知識(shí)復(fù)習(xí)　　　　2
1．2．1　Exponents / 指數(shù)　　　　3
1．2．2　Logarithms / 對數(shù)　　　　3
1．2．3　Series / 級(jí)數(shù)　　　　4
1．2．4　Modular Arithmetic / 模運(yùn)算　　　　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 / 接口與實(shí)現(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ù)、移動(dòng)構(gòu)造函數(shù)、拷貝賦值operator=和移動(dòng)賦值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和一個(gè)例子　　　　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 / 運(yùn)行時(shí)間計(jì)算　　　　57
2．4．1　A Simple Example / 一個(gè)簡單的例子　　　　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 / 運(yùn)行時(shí)間中的對數(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章　表、棧和隊(duì)列\(zhòng)t77
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ù)組實(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的實(shí)現(xiàn)　　　　86
3．5　Implementation of list / list的實(shí)現(xiàn)　　　　91
3．6　The Stack ADT / 棧的抽象數(shù)據(jù)類型　　　　103
3．6．1　Stack Model / 棧模型　　　　103
3．6．2　Implementation of Stacks / 棧的實(shí)現(xiàn)　　　　104
3．6．3　Applications / 應(yīng)用　　　　104
3．7　The Queue ADT / 隊(duì)列的抽象數(shù)據(jù)類型　　　　112
3．7．1　Queue Model / 隊(duì)列模型　　　　113
3．7．2　Array Implementation of Queues / 隊(duì)列的數(shù)組實(shí)現(xiàn)　　　　113
3．7．3　Applications of Queues / 隊(duì)列的應(yīng)用　　　　115
Summary / 小結(jié)　　　　116
Exercises / 練習(xí)　　　　116
Chapter 4 Trees / 第4章　樹　　　　121
4．1　Preliminaries / 預(yù)備知識(shí)　　　　121
4．1．1　Implementation of Trees / 樹的實(shí)現(xiàn)　　　　122
4．1．2　Tree Traversals with an Application / 樹的遍歷及應(yīng)用　　　　123
4．2　Binary Trees / 二叉樹　　　　126
4．2．1　Implementation / 實(shí)現(xiàn)　　　　128
4．2．2　An Example： Expression Trees / 一個(gè)例子——表達(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) / 一個(gè)簡單的想法（不能直接使用）　　　　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的實(shí)現(xiàn)　　　　175
4．8．4　An Example That Uses Several Maps / 使用多個(gè)映射的示例　　　　176
Summary / 小結(jié)　　　　181
Exercises / 練習(xí)　　　　182
References / 參考文獻(xiàn)　　　　189
Chapter 5 Hashing / 第5章　哈?！　　　?93
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 / 雙哈?！　　　?07
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 / 完美哈?！　　　?13
5．7．2　Cuckoo Hashing / 杜鵑哈?！　　　?15
5．7．3　Hopscotch Hashing / 跳房子哈?！　　　?27
5．8　Universal Hashing / 通用哈?！　　　?30
5．9　Extendible Hashing / 可擴(kuò)哈希　　　　233
Summary / 小結(jié)　　　　236
Exercises / 練習(xí)　　　　237
References / 參考文獻(xiàn)　　　　241
Chapter 6 Priority Queues (Heaps) / 第6章　優(yōu)先隊(duì)列（堆）\t245
6．1　Model / 模型　　　　245
6．2　Simple Implementations / 一些簡單的實(shí)現(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)先隊(duì)列的應(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 / 二項(xiàng)隊(duì)列　　　　271
6．8．1　Binomial Queue Structure / 二項(xiàng)隊(duì)列構(gòu)建　　　　271
6．8．2　Binomial Queue Operations / 二項(xiàng)隊(duì)列操作　　　　271
6．8．3　Implementation of Binomial Queues / 二項(xiàng)隊(duì)列的實(shí)現(xiàn)　　　　276
6．9　Priority Queues in the Standard Library / 標(biāo)準(zhǔn)庫中的優(yōu)先隊(duì)列　　　　282
Summary / 小結(jié)　　　　283
Exercises / 練習(xí)　　　　283
References / 參考文獻(xiàn)　　　　288
Chapter 7 Sorting / 第7章　排序　　　　291
7．1　Preliminaries / 預(yù)備知識(shí)　　　　291
7．2　Insertion Sort / 插入排序　　　　292
7．2．1　The Algorithm / 算法　　　　292
7．2．2　STL Implementation of Insertion Sort / 插入排序的STL實(shí)現(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 / 實(shí)際的快速排序例程　　　　315
7．7．5　Analysis of Quicksort / 快速排序的分析　　　　318
7．7．6　A Linear-Expected-Time Algorithm for Selection / 選擇問題的線性期望時(shí)間算法　　　　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í)間排序：桶式排序和基數(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章　不相交集算法\t351
8．1　Equivalence Relations / 等價(jià)關(guān)系　　　　351
8．2　The Dynamic Equivalence Problem / 動(dòng)態(tài)等價(jià)性問題　　　　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 / 一個(gè)O (M log*N)界　　　　369
8．6．4　An O (Mα(M， N)) Bound / 一個(gè)O (Mα(M， N))界　　　　370
8．7　An Application / 一個(gè)應(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 / 所有頂點(diǎn)對間的最短路徑　　　　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 / 一個(gè)簡單的最大流算法　　　　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 / 查找強(qiáng)分支　　　　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è)計(jì)技巧　　449
10．1　Greedy Algorithms / 貪婪算法　　　　449
10．1．1　A Simple Scheduling Problem / 一個(gè)簡單的調(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 / 分治算法的運(yùn)行時(shí)間　　　　468
10．2．2　Closest-Points Problem / 最近點(diǎn)問題　　　　470
10．2．3　The Selection Problem / 選擇問題　　　　475
10．2．4　Theoretical Improvements for Arithmetic Problems / 一些算術(shù)問題的理論改進(jìn)　　　　478
10．3　Dynamic Programming / 動(dòng)態(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 / 所有點(diǎn)對最短路徑　　　　491
10．4　Randomized Algorithms / 隨機(jī)化算法　　　　494
10．4．1　Random-Number Generators / 隨機(jī)數(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 / 收費(fèi)公路重建問題　　　　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 / 一個(gè)無關(guān)的智力問題　　　　534
11．2　Binomial Queues / 二項(xiàng)隊(duì)列　　　　534
11．3　Skew Heaps / 斜堆　　　　539
11．4　Fibonacci Heaps / 斐波那契堆　　　　541
11．4．1　Cutting Nodes in Leftist Heaps / 切除左式堆中的節(jié)點(diǎn)　　　　542
11．4．2　Lazy Merging for Binomial Queues / 二項(xiàng)隊(duì)列的懶惰合并　　　　544
11．4．3　The Fibonacci Heap Operations / 斐波那契堆操作　　　　548
11．4．4　Proof of the Time Bound / 時(shí)間界的證明　　　　549
11．5　Splay Trees / 伸展樹　　　　551
Summary / 小結(jié)　　　　555
Exercises / 練習(xí)　　　　556
References / 參考文獻(xiàn)　　　　557
Chapter 12 Advanced Data Structures and Implementation / 第 12章　高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(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 / 顯示實(shí)例化　　　　616