Chapter 1 Programming： A General Overview 1 1．1 What’s This Book About? 1 1．2 Mathematics Review 2 1．2．1 Exponents 3 1．2．2 Logarithms 3 1．2．3 Series 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 12 1．4．1 Basic class Syntax 12 1．4．2 Extra Constructor Syntax and Accessors 13 1．4．3 Separation of Interface and Implementation 16 1．4．4 vector and string 19 1．5 C++ Details 21 1．5．1 Pointers 21 1．5．2 Lvalues， Rvalues， and References 23 1．5．3 Parameter Passing 25 1．5．4 Return Passing 27 1．5．5 std：：swap and std：：move 29 1．5．6 The Big-Five： Destructor， Copy Constructor， Move Constructor， Copy Assignment operator=， Move Assignment operator= 30 1．5．7 C-style Arrays and Strings 35 1．6 Templates 36 1．6．1 Function Templates 37 1．6．2 Class Templates 38 1．6．3 Object， Comparable， and an Example 39 1．6．4 Function Objects 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 44 1．7．2 operator[] 45 1．7．3 Big-Five 46 Summary 46 Exercises 46 References 48 Chapter 2 Algorithm Analysis 51 2．1 Mathematical Background 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 66 2．4．5 Limitations of Worst-Case Analysis 70 Summary 70 Exercises 71 References 76 Chapter 3 Lists， Stacks， and Queues 77 3．1 Abstract Data Types (ADTs) 77 3．2 The List ADT 78 3．2．1 Simple Array Implementation of Lists 78 3．2．2 Simple Linked Lists 79 3．3 vector and list in the STL 80 3．3．1 Iterators 82 3．3．2 Example： Using erase on a List 83 3．3．3 const_iterators 84 3．4 Implementation of vector 86 3．5 Implementation of list 91 3．6 The Stack ADT 103 3．6．1 Stack Model 103 3．6．2 Implementation of Stacks 104 3．6．3 Applications 104 3．7 The Queue ADT 112 3．7．1 Queue Model 113 3．7．2 Array Implementation of Queues 113 3．7．3 Applications of Queues 115 Summary 116 Exercises 116 Chapter 4 Trees 121 4．1 Preliminaries 121 4．1．1 Implementation of Trees 122 4．1．2 Tree Traversals with an Application 123 4．2 Binary Trees 126 4．2．1 Implementation 128 4．2．2 An Example： Expression Trees 128 4．3 The Search Tree ADT?aBinary Search Trees 132 4．3．1 contains 134 4．3．2 findMin and findMax 135 4．3．3 insert 136 4．3．4 remove 139 4．3．5 Destructor and Copy Constructor 141 4．3．6 Average-Case Analysis 141 4．4 AVL Trees 144 4．4．1 Single Rotation 147 4．4．2 Double Rotation 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 168 4．8 Sets and Maps in the Standard Library 173 4．8．1 Sets 173 4．8．2 Maps 174 4．8．3 Implementation of set and map 175 4．8．4 An Example That Uses Several Maps 176 Summary 181 Exercises 182 References 189 Chapter 5 Hashing 193 5．1 General Idea 193 5．2 Hash Function 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 210 5．7 Hash Tables with Worst-Case O(1) Access 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 236 Exercises 237 References 241 Chapter 6 Priority Queues (Heaps) 245 6．1 Model 245 6．2 Simple Implementations 246 6．3 Binary Heap 247 6．3．1 Structure Property 247 6．3．2 Heap-Order Property 248
占位居中
直播中，去观看