Chapter 1　Programming: A General Overview / 第 1章　程序設(shè)計(jì)：概述　　　　1 1.1　What’s This Book About / 本書(shū)討論的內(nèi)容　　　　1 1.2　Mathematics Review / 數(shù)學(xué)知識(shí)復(fù)習(xí)　　　　2 1.2.1　Exponents / 指數(shù)　　　　3 1.2.2　Logarithms / 對(duì)數(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 / 遞歸簡(jiǎn)論　　　　8 1.4　C++ Classes / C類(lèi)　　　　12 1.4.1　Basic class Syntax / 基本的class語(yǔ)法　　　　12 1.4.2　Extra Constructor Syntax and Accessors / 構(gòu)造函數(shù)的附加語(yǔ)法和訪問(wèn)函數(shù)　　　　13 1.4.3　Separation of Interface and Implementation / 接口與實(shí)現(xiàn)的分離　　　　16 1.4.4　vector and string / vector類(lèi)和string類(lèi)　　　　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 / 類(lèi)模板　　　　38 1.6.3　Object, Comparable, and an Example / Object、Comparable和一個(gè)例子　　　　39 1.6.4　Function Objects / 函數(shù)對(duì)象　　　　41 1.6.5　Separate Compilation of Class Templates / 類(lèi)模板的分離式編譯　　 44 1.7　Using Matrices / 使用矩陣　　　　44 1.7.1　The Data Members, Constructor, and Basic Accessors / 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本訪問(wèn)函數(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 / 要分析的問(wèn)題　　　　54 2.4　Running-Time Calculations / 運(yùn)行時(shí)間計(jì)算　　　　57 2.4.1　A Simple Example / 一個(gè)簡(jiǎn)單的例子　　　　58 2.4.2　General Rules / 一般法則　　　　58 2.4.3　Solutions for the Maximum Subsequence Sum Problem / 最大子序列和問(wèn)題的求解　　　　60 2.4.4　Logarithms in the Running Time / 運(yùn)行時(shí)間中的對(duì)數(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ì)列 77 3.1　Abstract Data Types (ADTs) / 抽象數(shù)據(jù)類(lèi)型　　　　77 3.2　The List ADT / 表的抽象數(shù)據(jù)類(lèi)型　　　　78 3.2.1　Simple Array Implementation of Lists / 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)　　　　78 3.2.2　Simple Linked Lists / 簡(jiǎn)單鏈表　　　　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 / 例子：對(duì)表使用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ù)類(lèi)型　　　　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ù)類(lèi)型　　　　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章　樹(shù)　　　　121 4.1　Preliminaries / 預(yù)備知識(shí)　　　　121 4.1.1　Implementation of Trees / 樹(shù)的實(shí)現(xiàn)　　　　122 4.1.2　Tree Traversals with an Application / 樹(shù)的遍歷及應(yīng)用　　　　123 4.2　Binary Trees / 二叉樹(shù)　　　　126 4.2.1　Implementation / 實(shí)現(xiàn)　　　　128 4.2.2　An Example: Expression Trees / 一個(gè)例子——表達(dá)式樹(shù)　　　　128 4.3　The Search Tree ADT—Binary Search Trees / 查找樹(shù)的抽象數(shù)據(jù)類(lèi)型——二叉查找樹(shù)　　　　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樹(shù)　　　　144 4.4.1　Single Rotation / 單旋轉(zhuǎn)　　　　147 4.4.2　Double Rotation / 雙旋轉(zhuǎn)　　　　149 4.5　Splay Trees / 伸展樹(shù)　　　　158 4.5.1　A Simple Idea (That Does Not Work) / 一個(gè)簡(jiǎn)單的想法（不能直接使用）　　　　158 4.5.2　Splaying / 展開(kāi)　　　　160 4.6　Tree Traversals (Revisited) / 樹(shù)的遍歷（再次討論）　　　　166 4.7　B-Trees / B樹(shù)　　　　168 4.8　Sets and Maps in the Standard Library / 標(biāo)準(zhǔn)庫(kù)中的集合與映射　　　　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章　哈�！　　　�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 / 線性探測(cè)法　　　　201 5.4.2　Quadratic Probing / 平方探測(cè)法　　　　202 5.4.3　Double Hashing / 雙哈�！　　　�207 5.5　Rehashing / 再哈�！　　　�208 5.6　Hash Tables in the Standard Library / 標(biāo)準(zhǔn)庫(kù)中的哈希表　　　　210 5.7　Hash Tables with Worst-Case O(1) Access / 以最壞情形O(1)訪問(wèn)的哈希表　　　　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 / 可擴(kuò)哈�！　　　�233 Summary / 小結(jié)　　　　236 Exercises / 練習(xí)　　　　237 References / 參考文獻(xiàn)　　　　241 Chapter 6 Priority Queues (Heaps) / 第6章　優(yōu)先隊(duì)列（堆） 245 6.1　Model / 模型　　　　245 6.2　Simple Implementations / 一些簡(jiǎn)單的實(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 / 選擇問(wèn)題　　　　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)庫(kù)中的優(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 / 一些簡(jiǎn)單排序算法的下界　　　　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 / 選擇問(wèn)題的線性期望時(shí)間算法　　　　321 7.8　A General Lower Bound for Sorting / 排序算法的一般下界　　　　323 7.8.1　Decision Trees / 決策樹(shù)　　　　323 7.9　Decision-Tree Lower Bounds for Selection Problems / 選擇問(wèn)題的決策樹(shù)下界　　　　325 7.10　Adversary Lower Bounds / 對(duì)手下界　　　　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 / 簡(jiǎn)單算法　　　　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 / 等價(jià)關(guān)系　　　　351 8.2　The Dynamic Equivalence Problem / 動(dòng)態(tài)等價(jià)性問(wèn)題　　　　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 / 緩慢增長(zhǎng)的函數(shù)　　　　362 8.6.2　An Analysis by Recursive Decomposition / 通過(guò)遞歸分解進(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 / 無(wú)權(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 / 無(wú)圈圖　　　　400 9.3.5　All-Pairs Shortest Path / 所有頂點(diǎn)對(duì)間的最短路徑　　　　404 9.3.6　Shortest Path Example / 最短路徑的例　　　　404 9.4　Network Flow Problems / 網(wǎng)絡(luò)流問(wèn)題　　　　406 9.4.1　A Simple Maximum-Flow Algorithm / 一個(gè)簡(jiǎn)單的最大流算法　　　　408 9.5　Minimum Spanning Tree / 最小生成樹(shù)　　　　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 / 無(wú)向圖　　　　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類(lèi)　　　　434 9.7.3　NP-Complete Problems / NP完全問(wèn)題　　　　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è)簡(jiǎn)單的調(diào)度問(wèn)題　　　　450 10.1.2　Huffman Codes / 哈夫曼編碼　　　　453 10.1.3　Approximate Bin Packing / 近似裝箱問(wèn)題　　　　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)問(wèn)題　　　　470 10.2.3　The Selection Problem / 選擇問(wèn)題　　　　475 10.2.4　Theoretical Improvements for Arithmetic Problems / 一些算術(shù)問(wèn)題的理論改進(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 / 二叉查找樹(shù)　　　　487 10.3.4　All-Pairs Shortest Path / 所有點(diǎn)對(duì)最短路徑　　　　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 / 素性測(cè)試　　　　503 10.5　Backtracking Algorithms / 回溯算法　　　　506 10.5.1　The Turnpike Reconstruction Problem / 收費(fèi)公路重建問(wèn)題　　　　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è)無(wú)關(guān)的智力問(wè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 / 伸展樹(shù)　　　　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 / 自頂向下伸展樹(shù)　　　　559 12.2　Red-Black Trees / 紅黑樹(shù)　　　　566 12.2.1　Bottom-Up Insertion / 自底向上的插入　　　　567 12.2.2　Top-Down Red-Black Trees / 自頂向下紅黑樹(shù)　　　　568 12.2.3　Top-Down Deletion / 自頂向下刪除　　　　570 12.3　Treaps / treap 樹(shù)　　　　576 12.4　Suffix Arrays and Suffix Trees / 后綴數(shù)組和后綴樹(shù)　　　　579 12.4.1　Suffix Arrays / 后綴數(shù)組　　　　580 12.4.2　Suffix Trees / 后綴樹(shù)　　　　583 12.4.3　Linear-Time Construction of Suffix Arrays and Suffix Trees / 后綴數(shù)組和后綴樹(shù)的線性　　　　586 12.5　k -d Trees / k-d 樹(shù)　　　　596 12.6　Pairing Heaps / 配對(duì)堆　　　　602 Summary / 小結(jié)　　　　606 Exercises / 練習(xí)　　　　608 References / 參考文獻(xiàn)　　　　612 Appendix A Separate Compilation of Class Templates / 附錄A　類(lèi)模板的分離式編譯　　　　615 A.1 Everything in the Header / 頭文件中的內(nèi)容　　　　616 A.2 Explicit Instantiation / 顯示實(shí)例化　　　　616