關(guān)于我們
書單推薦
新書推薦
|
數(shù)據(jù)結(jié)構(gòu)與算法分析 C++語言描述(英文版第4版)
本書是數(shù)據(jù)結(jié)構(gòu)和算法分析領(lǐng)域的教材。全書以 C++作為具體的實(shí)現(xiàn)語言,介紹了表、棧、隊(duì)列、樹、哈希表、優(yōu)先隊(duì)列、排序、不相交集算法、圖論算法、算法分析、算法設(shè)計(jì)、攤還分析、查找樹算法、后綴數(shù)組、后綴樹、k-d 樹、配對(duì)堆等內(nèi)容。本書把算法分析和 C++程序的開發(fā)有機(jī)結(jié)合起來,深入剖析每種算法,內(nèi)容縝密嚴(yán)謹(jǐn),還詳細(xì)講解了精心構(gòu)建程序的方法。
本書可作為高等院校計(jì)算機(jī)相關(guān)專業(yè)的教學(xué)用書或參考用書,也可供計(jì)算機(jī)領(lǐng)域的工程技術(shù)人員參考
1. 用C++新標(biāo)準(zhǔn)C++11的代碼講數(shù)據(jù)結(jié)構(gòu)和算法分析;
2. 作者所寫的數(shù)據(jù)結(jié)構(gòu)和算法分析書籍銷量好,好評(píng)多,已被世界上很多大學(xué)用作教材。
Mark Allen Weiss,佛羅里達(dá)國際大學(xué)計(jì)算與信息科學(xué)學(xué)院教授、副院長(zhǎng),本科教育主任和研究生教育主任。他于1987年獲得普林斯頓大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位,師從Bob Sedgewick。他曾經(jīng)擔(dān)任全美AP(Advanced Placement)考試計(jì)算機(jī)學(xué)科委員會(huì)的主席(2000-2004)。Weiss教授在數(shù)據(jù)結(jié)構(gòu)和算法分析方面卓有建樹,他的數(shù)據(jù)結(jié)構(gòu)和算法分析的書籍,受到廣泛好評(píng).已被世界500余所大學(xué)用作教材。
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 / 對(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類 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ù)對(duì)象 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è)簡(jiǎn)單的例子 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í)間中的對(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ù)類型 77 3.2 The List ADT / 表的抽象數(shù)據(jù)類型 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ù)類型 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è)簡(jiǎn)單的想法(不能直接使用) 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章 哈希 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)庫中的哈希表 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 / 可擴(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 / 選擇問題 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 / 一些簡(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 / 選擇問題的線性期望時(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 / 對(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à)性問題 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 / 通過遞歸分解進(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)對(duì)間的最短路徑 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è)簡(jiǎn)單的最大流算法 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è)簡(jiǎn)單的調(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)對(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)公路重建問題 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 / 配對(duì)堆 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
你還可能感興趣
我要評(píng)論
|