数据结构与算法分析-C++语言描述-(第四版)-英文版_PDF下载[85MB-百度云]马克.艾伦.韦斯

本书特色

[

本书是数据结构和算法分析的经典教材，书中使用主流的程序设计语言C 作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、后缀数组、后缀树、k-d树和配对堆等。本书把算法分析与C 程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

]

内容简介

[

本版特色如下：
*书中的阐述和算法均用C 新标准C 11的代码实现。
*unordered_map两个类模板的简要讨论。
*增加了基数排序和与选择相关问题下界的证明。增加了对AVL树删除算法的实现。使用新的union/find分析同时改进此前各版的较弱的O(Mlog*N)界。

]

作者简介

[

　　Mark Allen Weiss，佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Bob Sedgewick。他曾经担任全美AP(Advanced Placement)考试计算机学科委员会的主席(2000-2004)。Weiss教授在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评．已被世界500余所大学用作教材。

]

ContentsChapter 1 Programming: A General Overview 11.1 What’s This Book About? 11.2 Mathematics Review 21.2.1 Exponents 31.2.2 Logarithms 31.2.3 Series 41.2.4 Modular Arithmetic 51.2.5 The P Word 61.3 A Brief Introduction to Recursion 81.4 C Classes 121.4.1 Basic class Syntax 121.4.2 Extra Constructor Syntax and Accessors 131.4.3 Separation of Interface and Implementation 161.4.4 vector and string 191.5 C Details 211.5.1 Pointers 211.5.2 Lvalues, Rvalues, and References 231.5.3 Parameter Passing 251.5.4 Return Passing 271.5.5 std::swap and std::move 291.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, CopyAssignment operator=, Move Assignment operator= 301.5.7 C-style Arrays and Strings 351.6 Templates 361.6.1 Function Templates 371.6.2 Class Templates 381.6.3 Object, Comparable, and an Example 391.6.4 Function Objects 411.6.5 Separate Compilation of Class Templates 441.7 Using Matrices 441.7.1 The Data Members, Constructor, and Basic Accessors 441.7.2 operator[] 451.7.3 Big-Five 46Summary 46Exercises 46References 48Chapter 2 Algorithm Analysis 512.1 Mathematical Background 512.2 Model 542.3 What to Analyze 542.4 Running-Time Calculations 572.4.1 A Simple Example 582.4.2 General Rules 582.4.3 Solutions for the Maximum SubsequenceSum Problem 602.4.4 Logarithms in the Running Time 662.4.5 Limitations of Worst-Case Analysis 70Summary 70Exercises 71References 76Chapter 3 Lists, Stacks, and Queues 773.1 Abstract Data Types (ADTs) 773.2 The List ADT 783.2.1 Simple Array Implementation of Lists 783.2.2 Simple Linked Lists 793.3 vector and list in the STL 803.3.1 Iterators 823.3.2 Example: Using erase on a List 833.3.3 const_iterators 843.4 Implementation of vector 863.5 Implementation of list 913.6 The Stack ADT 1033.6.1 Stack Model 1033.6.2 Implementation of Stacks 1043.6.3 Applications 1043.7 The Queue ADT 1123.7.1 Queue Model 1133.7.2 Array Implementation of Queues 1133.7.3 Applications of Queues 115Summary 116Exercises 116Chapter 4 Trees 1214.1 Preliminaries 1214.1.1 Implementation of Trees 1224.1.2 Tree Traversals with an Application 1234.2 Binary Trees 1264.2.1 Implementation 1284.2.2 An Example: Expression Trees 1284.3 The Search Tree ADT?aBinary Search Trees 1324.3.1 contains 1344.3.2 findMin and findMax 1354.3.3 insert 1364.3.4 remove 1394.3.5 Destructor and Copy Constructor 1414.3.6 Average-Case Analysis 1414.4 AVL Trees 1444.4.1 Single Rotation 1474.4.2 Double Rotation 1494.5 Splay Trees 1584.5.1 A Simple Idea (That Does Not Work) 1584.5.2 Splaying 1604.6 Tree Traversals (Revisited) 1664.7 B-Trees 1684.8 Sets and Maps in the Standard Library 1734.8.1 Sets 1734.8.2 Maps 1744.8.3 Implementation of set and map 1754.8.4 An Example That Uses Several Maps 176Summary 181Exercises 182References 189Chapter 5 Hashing 1935.1 General Idea 1935.2 Hash Function 1945.3 Separate Chaining 1965.4 Hash Tables without Linked Lists 2015.4.1 Linear Probing 2015.4.2 Quadratic Probing 2025.4.3 Double Hashing 2075.5 Rehashing 2085.6 Hash Tables in the Standard Library 2105.7 Hash Tables with Worst-Case O(1) Access 2125.7.1 Perfect Hashing 2135.7.2 Cuckoo Hashing 2155.7.3 Hopscotch Hashing 2275.8 Universal Hashing 2305.9 Extendible Hashing 233Summary 236Exercises 237References 241Chapter 6 Priority Queues (Heaps) 2456.1 Model 2456.2 Simple Implementations 2466.3 Binary Heap 2476.3.1 Structure Property 2476.3.2 Heap-Order Property 2486.3.3 Basic Heap Operations 2496.3.4 Other Heap Operations 2526.4 Applications of Priority Queues 2576.4.1 The Selection Problem 2586.4.2 Event Simulation 2596.5 d-Heaps 2606.6 Leftist Heaps 2616.6.1 Leftist Heap Property 2616.6.2 Leftist Heap Operations 2626.7 Skew Heaps 2696.8 Binomial Queues 2716.8.1 Binomial Queue Structure 2716.8.2 Binomial Queue Operations 2716.8.3 Implementation of Binomial Queues 2766.9 Priority Queues in the Standard Library 282Summary 283Exercises 283References 288Chapter 7 Sorting 2917.1 Preliminaries 2917.2 Insertion Sort 2927.2.1 The Algorithm 2927.2.2 STL Implementation of Insertion Sort 2937.2.3 Analysis of Insertion Sort 2947.3 A Lower Bound for Simple Sorting Algorithms 2957.4 Shellsort 2967.4.1 Worst-Case Analysis of Shellsort 2977.5 Heapsort 3007.5.1 Analysis of Heapsort 3017.6 Mergesort 3047.6.1 Analysis of Mergesort 3067.7 Quicksort 3097.7.1 Picking the Pivot 3117.7.2 Partitioning Strategy 3137.7.3 Small Arrays 3157.7.4 Actual Quicksort Routines 3157.7.5 Analysis of Quicksort 3187.7.6 A Linear-Expected-Time Algorithm for Selection 3217.8 A General Lower Bound for Sorting 3237.8.1 Decision Trees 3237.9 Decision-Tree Lower Bounds for Selection Problems 3257.10 Adversary Lower Bounds 3287.11 Linear-Time Sorts: Bucket Sort and Radix Sort 3317.12 External Sorting 3367.12.1 Why We Need New Algorithms 3367.12.2 Model for External Sorting 3367.12.3 The Simple Algorithm 3377.12.4 Multiway Merge 3387.12.5 Polyphase Merge 3397.12.6 Replacement Selection 340Summary 341Exercises 341References 347Chapter 8 The Disjoint Sets Class 3518.1 Equivalence Relations 3518.2 The Dynamic Equivalence Problem 3528.3 Basic Data Structure 3538.4 Smart Union Algorithms 3578.5 Path Compression 3608.6 Worst Case for Union-by-Rank and Path Compression 3618.6.1 Slowly Growing Functions 3628.6.2 An Analysis by Recursive Decomposition 3628.6.3 An O( M log *N ) Bound 3698.6.4 An O( M |á(M, N) ) Bound 3708.7 An Application 372Summary 374Exercises 375References 376Chapter 9 Graph Algorithms 3799.1 Definitions 3799.1.1 Representation of Graphs 3809.2 Topological Sort 3829.3 Shortest-Path Algorithms 3869.3.1 Unweighted Shortest Paths 3879.3.2 Dijkstra’s Algorithm 3919.3.3 Graphs with Negative Edge Costs 4009.3.4 Acyclic Graphs 4009.3.5 All-Pairs Shortest Path 4049.3.6 Shortest Path Example 4049.4 Network Flow Problems 4069.4.1 A Simple Maximum-Flow Algorithm 4089.5 Minimum Spanning Tree 4139.5.1 Prim’s Algorithm 4149.5.2 Kruskal’s Algorithm 4179.6 Applications of Depth-First Search 4199.6.1 Undirected Graphs 4209.6.2 Biconnectivity 4219.6.3 Euler Circuits 4259.6.4 Directed Graphs 4299.6.5 Finding Strong Components 4319.7 Introduction to NP-Completeness 4329.7.1 Easy vs. Hard 4339.7.2 The Class NP 4349.7.3 NP-Complete Problems 434Summary 437Exercises 437References 445Chapter 10 Algorithm Design Techniques 44910.1 Greedy Algorithms 44910.1.1 A Simple Scheduling Problem 45010.1.2 Huffman Codes 45310.1.3 Approximate Bin Packing 45910.2 Divide and Conquer 46710.2.1 Running Time of Divide-and-Conquer Algorithms 46810.2.2 Closest-Points Problem 47010.2.3 The Selection Problem 47510.2.4 Theoretical Improvements for Arithmetic Problems 47810.3 Dynamic Programming 48210.3.1 Using a Table Instead of Recursion 48310.3.2 Ordering Matrix Multiplications 48510.3.3 Optimal Binary Search Tree 48710.3.4 All-Pairs Shortest Path 49110.4 Randomized Algorithms 49410.4.1 Random-Number Generators 49510.4.2 Skip Lists 50010.4.3 Primality Testing 50310.5 Backtracking Algorithms 50610.5.1 The Turnpike Reconstruction Problem 50610.5.2 Games 511Summary 518Exercises 5