Data Structures and Algorithms in C++

Data Structures and Algorithms in C++ это авторитетное руководство, которое демистифицирует даже самые сложные математические понятия, так что вы можете получить четкое понимание структуры данных и алгоритмы в C + +. Оно включает в себя объектно-ориентированное проектирование парадигмы использования C + + в качестве языка реализации, а также предоставляет анализ основных алгоритмов. Предлагает уникальный мультимедийный формат для обучения основам структур данных и алгоритмов, позволяет узнать о самых последних открытиях в этой области. Структура дизайн обеспечивает четкий подход к разработке программ, ясный, легкий для восприятия стиль письма, который делает доступными даже самые сложные математические понятия Опираясь на успех первого издания, эта новая версия предлагает вам инновационный подход к фундаментальной структуре данных и алгоритмов. Data Structures and Algorithms in C++ /by Michael T. Goodrich, Roberto Tamassia, David M. Mount. Written by an author team of experts in their fields, this authoritative guide demystifies even the most difficult mathematical concepts so that you can gain a clear understanding of data structures and algorithms in C++. The unparalleled author team incorporates the object-oriented design paradigm using C++ as the implementation language, while also providing intuition and analysis of fundamental algorithms. Offers a unique multimedia format for learning the fundamentals of data structures and algorithms Allows you to visualize key analytic concepts, learn about the most recent insights in the field, and do data structure design Provides clear approaches for developing programs Features a clear, easy-to-understand writing style that breaks down even the most difficult mathematical concepts Building on the success of the first edition, this new version offers you an innovative approach to fundamental data structures and algorithms. Cover......Page 1 Title Page......Page 5 Copyright......Page 6 Preface......Page 9 Contents......Page 17 1 A C++ Primer......Page 25 1.1.1 A Simple C++ Program......Page 26 1.1.2 Fundamental Types......Page 28 1.1.3 Pointers, Arrays, and Structures......Page 31 1.1.4 Named Constants, Scope, and Namespaces......Page 37 1.2 Expressions......Page 40 1.2.1 Changing Types through Casting......Page 44 1.3 Control Flow......Page 47 1.4 Functions......Page 50 1.4.1 Argument Passing......Page 52 1.4.2 Overloading and Inlining......Page 54 1.5 Classes......Page 56 1.5.1 Class Structure......Page 57 1.5.2 Constructors and Destructors......Page 61 1.5.3 Classes and Memory Allocation......Page 64 1.5.4 Class Friends and Class Members......Page 67 1.5.5 The Standard Template Library......Page 69 1.6 C++ Program and File Organization......Page 71 1.6.1 An Example Program......Page 72 1.7 Writing a C++ Program......Page 77 1.7.2 Pseudo-Code......Page 78 1.7.3 Coding......Page 79 1.7.4 Testing and Debugging......Page 81 1.8 Exercises......Page 84 2 Object-Oriented Design......Page 89 2.1.1 Object-Oriented Design Goals......Page 90 2.1.2 Object-Oriented Design Principles......Page 91 2.1.3 Design Patterns......Page 94 2.2.1 Inheritance in C++......Page 95 2.2.2 Polymorphism......Page 102 2.2.3 Examples of Inheritance in C++......Page 103 2.2.4 Multiple Inheritance and Class Casting......Page 108 2.2.5 Interfaces and Abstract Classes......Page 111 2.3.1 Function Templates......Page 114 2.3.2 Class Templates......Page 115 2.4.1 Exception Objects......Page 117 2.4.2 Throwing and Catching Exceptions......Page 118 2.4.3 Exception Specification......Page 120 2.5 Exercises......Page 122 3 Arrays, Linked Lists, and Recursion......Page 127 3.1.1 Storing Game Entries in an Array......Page 128 3.1.2 Sorting an Array......Page 133 3.1.3 Two-Dimensional Arrays and Positional Games......Page 135 3.2.1 Implementing a Singly Linked List......Page 141 3.2.3 Removal from the Front of a Singly Linked List......Page 143 3.2.4 Implementing a Generic Singly Linked List......Page 145 3.3.1 Insertion into a Doubly Linked List......Page 147 3.3.2 Removal from a Doubly Linked List......Page 148 3.3.3 A C++ Implementation......Page 149 3.4.1 Circularly Linked Lists......Page 153 3.4.2 Reversing a Linked List......Page 157 3.5 Recursion......Page 158 3.5.1 Linear Recursion......Page 164 3.5.2 Binary Recursion......Page 168 3.5.3 Multiple Recursion......Page 171 3.6 Exercises......Page 173 4 Analysis Tools......Page 177 4.1.2 The Logarithm Function......Page 178 4.1.5 The Quadratic Function......Page 180 4.1.6 The Cubic Function and Other Polynomials......Page 182 4.1.7 The Exponential Function......Page 183 4.1.8 Comparing Growth Rates......Page 185 4.2 Analysis of Algorithms......Page 186 4.2.1 Experimental Studies......Page 187 4.2.2 Primitive Operations......Page 188 4.2.3 Asymptotic Notation......Page 190 4.2.4 Asymptotic Analysis......Page 194 4.2.5 Using the Big-Oh Notation......Page 196 4.2.6 A Recursive Algorithm for Computing Powers......Page 200 4.2.7 Some More Examples of Algorithm Analysis......Page 201 4.3.2 The “Contra” Attack......Page 205 4.3.3 Induction and Loop Invariants......Page 206 4.4 Exercises......Page 209 5 Stacks, Queues, and Deques......Page 217 5.1 Stacks......Page 218 5.1.1 The Stack Abstract Data Type......Page 219 5.1.3 A C++ Stack Interface......Page 220 5.1.4 A Simple Array-Based Stack Implementation......Page 222 5.1.5 Implementing a Stack with a Generic Linked List......Page 226 5.1.6 Reversing a Vector Using a Stack......Page 227 5.1.7 Matching Parentheses and HTML Tags......Page 228 5.2.1 The Queue Abstract Data Type......Page 232 5.2.2 The STL Queue......Page 233 5.2.3 A C++ Queue Interface......Page 234 5.2.4 A Simple Array-Based Implementation......Page 235 5.2.5 Implementing a Queue with a Circularly Linked List......Page 237 5.3.1 The Deque Abstract Data Type......Page 241 5.3.3 Implementing a Deque with a Doubly Linked List......Page 242 5.3.4 Adapters and the Adapter Design Pattern......Page 244 5.4 Exercises......Page 247 6 List and Iterator ADTs......Page 251 6.1.1 The Vector Abstract Data Type......Page 252 6.1.2 A Simple Array-Based Implementation......Page 253 6.1.3 An Extendable Array Implementation......Page 255 6.1.4 STL Vectors......Page 260 6.2.1 Node-Based Operations and Iterators......Page 262 6.2.2 The List Abstract Data Type......Page 264 6.2.3 Doubly Linked List Implementation......Page 266 6.2.4 STL Lists......Page 271 6.2.5 STL Containers and Iterators......Page 272 6.3.2 Implementing a Sequence with a Doubly Linked List......Page 279 6.3.3 Implementing a Sequence with an Array......Page 281 6.4.1 The Bubble-Sort Algorithm......Page 283 6.4.2 A Sequence-Based Analysis of Bubble-Sort......Page 284 6.5 Exercises......Page 286 7 Trees......Page 291 7.1 General Trees......Page 292 7.1.1 Tree Definitions and Properties......Page 293 7.1.2 Tree Functions......Page 296 7.1.3 A C++ Tree Interface......Page 297 7.1.4 A Linked Structure for General Trees......Page 298 7.2.1 Depth and Height......Page 299 7.2.2 Preorder Traversal......Page 302 7.2.3 Postorder Traversal......Page 305 7.3 Binary Trees......Page 308 7.3.1 The Binary Tree ADT......Page 309 7.3.2 A C++ Binary Tree Interface......Page 310 7.3.3 Properties of Binary Trees......Page 311 7.3.4 A Linked Structure for Binary Trees......Page 313 7.3.5 A Vector-Based Structure for Binary Trees......Page 319 7.3.6 Traversals of a Binary Tree......Page 321 7.3.7 The Template Function Pattern......Page 327 7.3.8 Representing General Trees with Binary Trees......Page 333 7.4 Exercises......Page 334 8 Heaps and Priority Queues......Page 345 8.1.1 Keys, Priorities, and Total Order Relations......Page 346 8.1.2 Comparators......Page 348 8.1.3 The Priority Queue ADT......Page 351 8.1.4 A C++ Priority Queue Interface......Page 352 8.1.5 Sorting with a Priority Queue......Page 353 8.1.6 The STL priority_queue Class......Page 354 8.2 Implementing a Priority Queue with a List......Page 355 8.2.1 A C++ Priority Queue Implementation using a List......Page 357 8.2.2 Selection-Sort and Insertion-Sort......Page 359 8.3.1 The Heap Data Structure......Page 361 8.3.2 Complete Binary Trees and Their Representation......Page 364 8.3.3 Implementing a Priority Queue with a Heap......Page 368 8.3.4 C++ Implementation......Page 373 8.3.5 Heap-Sort......Page 375 8.3.6 Bottom-Up Heap Construction......Page 377 8.4 Adaptable Priority Queues......Page 381 8.4.1 A List-Based Implementation......Page 382 8.4.2 Location-Aware Entries......Page 384 8.5 Exercises......Page 385 9 Hash Tables, Maps, and Skip Lists......Page 391 9.1 Maps......Page 392 9.1.1 The Map ADT......Page 393 9.1.2 A C++ Map Interface......Page 395 9.1.3 The STL map Class......Page 396 9.1.4 A Simple List-Based Map Implementation......Page 398 9.2.1 Bucket Arrays......Page 399 9.2.3 Hash Codes......Page 400 9.2.4 Compression Functions......Page 404 9.2.5 Collision-Handling Schemes......Page 406 9.2.6 Load Factors and Rehashing......Page 410 9.2.7 A C++ Hash Table Implementation......Page 411 9.3 Ordered Maps......Page 418 9.3.1 Ordered Search Tables and Binary Search......Page 419 9.3.2 Two Applications of Ordered Maps......Page 423 9.4 Skip Lists......Page 426 9.4.1 Search and Update Operations in a Skip List......Page 428 9.4.2 A Probabilistic Analysis of Skip Lists......Page 432 9.5.1 The Dictionary ADT......Page 435 9.5.2 A C++ Dictionary Implementation......Page 437 9.5.3 Implementations with Location-Aware Entries......Page 439 9.6 Exercises......Page 441 10 Search Trees......Page 447 10.1 Binary Search Trees......Page 448 10.1.1 Searching......Page 450 10.1.2 Update Operations......Page 452 Implementation of a Binary Search Tree......Page 456 10.2 AVL Trees......Page 462 10.2.1 Update Operations......Page 464 10.2.2 C++ Implementation of an AVL Tree......Page 470 10.3.1 Splaying......Page 474 10.3.2 When to Splay......Page 478 10.3.3 Amortized Analysis of Splaying......Page 480 10.4.1 Multi-Way Search Trees......Page 485 10.4.2 Update Operations for (2,4) Tree......Page 491 10.5 Red-Black Trees......Page 497 10.5.1 Update Operations......Page 499 10.5.2 C++ Implementation of a Red-Black Tree......Page 512 10.6 Exercises......Page 516 11 Sorting, Sets, and Selection......Page 523 11.1.1 Divide-and-Conquer......Page 524 11.1.2 Merging Arrays and Lists......Page 529 11.1.3 The Running Time of Merge-Sort......Page 532 11.1.4 C++ Implementations of Merge-Sort......Page 533 11.1.5 Merge-Sort and Recurrence Equations......Page 535 11.2 Quick-Sort......Page 537 11.2.1 Randomized Quick-Sort......Page 545 11.2.2 C++Implementations and Optimizations......Page 547 11.3.1 A Lower Bound for Sorting......Page 550 11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort......Page 552 11.3.3 Comparing Sorting Algorithms......Page 555 11.4.1 The Set ADT......Page 557 11.4.2 Mergable Sets and the Template Method Pattern......Page 558 11.4.3 Partitions with Union-Find Operations......Page 562 11.5.1 Prune-and-Search......Page 566 11.5.2 Randomized Quick-Select......Page 567 11.5.3 Analyzing Randomized Quick-Select......Page 568 11.6 Exercises......Page 569 12 Strings and Dynamic Programming......Page 577 12.1 String Operations......Page 578 12.1.1 The STL String Class......Page 579 12.2.1 Matrix Chain-Product......Page 581 12.2.2 DNA and Text Sequence Alignment......Page 584 12.3.1 Brute Force......Page 588 12.3.2 The Boyer-Moore Algorithm......Page 590 12.3.3 The Knuth-Morris-Pratt Algorithm......Page 594 12.4 Text Compression and the Greedy Method......Page 599 12.4.1 The Huffman-Coding Algorithm......Page 600 12.4.2 The Greedy Method......Page 601 12.5.1 Standard Tries......Page 602 12.5.2 Compressed Tries......Page 606 12.5.3 Suffix Tries......Page 608 12.5.4 Search Engines......Page 610 12.6 Exercises......Page 611 13 Graph Algorithms......Page 617 13.1 Graphs......Page 618 13.1.1 The Graph ADT......Page 623 13.2.1 The Edge List Structure......Page 624 13.2.2 The Adjacency List Structure......Page 627 13.2.3 The Adjacency Matrix Structure......Page 629 13.3.1 Depth-First Search......Page 631 13.3.2 Implementing Depth-First Search......Page 635 13.3.3 A Generic DFS Implementation in C++......Page 637 13.3.4 Polymorphic Objects and Decorator Values......Page 645 13.3.5 Breadth-First Search......Page 647 13.4 Directed Graphs......Page 650 13.4.1 Traversing a Digraph......Page 652 13.4.2 Transitive Closure......Page 654 13.4.3 Directed Acyclic Graphs......Page 657 13.5.1 Weighted Graphs......Page 661 13.5.2 Dijkstra’s Algorithm......Page 663 13.6 Minimum Spanning Trees......Page 669 13.6.1 Kruskal’s Algorithm......Page 671 13.6.2 The Prim-Jarnik Algorithm......Page 675 13.7 Exercises......Page 678 14 Memory Management and B-Trees......Page 689 14.1 Memory Management......Page 690 14.1.1 Memory Allocation in C++......Page 693 14.1.2 Garbage Collection......Page 695 14.2.1 The Memory Hierarchy......Page 697 14.2.2 Caching Strategies......Page 698 14.3 External Searching and B-Trees......Page 703 14.3.1 (a,b) Trees......Page 704 14.3.2 B-Trees......Page 706 14.4 External-Memory Sorting......Page 707 14.4.1 Multi-Way Merging......Page 708 14.5 Exercises......Page 709 A Useful Mathematical Facts......Page 713 Bibliography......Page 721 Index......Page 726

an Updated, Innovative Approach To Data Structures And Algorithms

written By An Author Team Of Experts In Their Fields, This Authoritative Guide Demystifies Even The Most Difficult Mathematical Concepts So That You Can Gain A Clear Understanding Of Data Structures And Algorithms In C++.

the Unparalleled Author Team Incorporates The Object-oriented Design Paradigm Using C++ As The Implementation Language, While Also Providing Intuition And Analysis Of Fundamental Algorithms.

• offers A Unique Multimedia Format For Learning The Fundamentals Of Data Structures And Algorithms
• allows You To Visualize Key Analytic Concepts, Learn About The Most Recent Insights In The Field, And do Data Structure Design
• provides Clear Approaches For Developing Programs
• features A Clear, Easy-to-understand Writing Style That Breaks Down Even The Most Difficult Mathematical Concepts

building On The Success Of The First Edition, This New Version Offers You An Innovative Approach To Fundamental Data Structures And Algorithms.

"An updated, innovative approach to data structures and algorithms Written by an author team of experts in their fields, this authoritative guide demystifies even the most difficult mathematical concepts so that you can gain a clear understanding of data structures and algorithms in C++. The unparalleled author team incorporates the object-oriented design paradigm using C++ as the implementation language, while also providing intuition and analysis of fundamental algorithms. Offers a unique multimedia format for learning the fundamentals of data structures and algorithms Allows you to visualize key analytic concepts, learn about the most recent insights in the field, and do data structure design Provides clear approaches for developing programs Features a clear, easy-to-understand writing style that breaks down even the most difficult mathematical concepts Building on the success of the first edition, this new version offers you an innovative approach to fundamental data structures and algorithms."-- This second edition of Data Structures and Algorithms in C++ is designed to provide an introduction to data structures and algorithms, including their design, analysis, and implementation. The authors offer an introduction to object-oriented design with C++ and design patterns, including the use of class inheritance and generic programming through class and function templates, and retain a consistent object-oriented viewpoint throughout the book. This is a sister book to Goodrich & Tamassias Data Structures and Algorithms in Java, but uses C++ as the basis language instead of Java. This C++ version retains the same pedagogical approach and general structure as the Java version so schools that teach data structures in both C++ and Java can share the same core syllabus. In terms of curricula based on the IEEE/ACM 2001 Computing Curriculum, this book is appropriate for use in the courses CS102 (I/O/B versions), CS103 (I/O/B versions), CS111 (A version), and CS112 (A/I/O/F/H versions). Building on the success of Data Structures and Algorithms in Java, Goodrich/Tamassia/Mount Data Structures and Algorithms In C++ 2e offers an innovative approach to fundamental data structures and algorithms. The text incorporates the object-oriented design paradigm using C++ as the implementation language, while also providing intuition and analysis of fundamental algorithms. The authors'highly visual approach and extensive suite of web-based learning and teaching tools give students the opportunity visualize key analytic concepts, learn about the most recent insights in the field, and do data structure design. Machine generated contents note: Chapter 1 - Basic C++ Programming. Chapter 2 - Object-Oriented Design. Chapter 3 - Analysis Tools. Chapter 4 - Stacks, Queues, and Recursion. Chapter 5 - Vectors, Lists, and Sequences. Chapter 6 - Trees. Chapter 7 - Priority Queues. Chapter 8 - Dictionaries. Chapter 9 - Search Trees. Chapter 10 - Sorting, Sets, and Selection. Chapter 11 - Text Processing. Chapter 12 - Graphs. Appendix: Useful Mathematical Facts. Teach Like a Champion 2.0 is a complete update to the international bestseller. This teaching guide is a must-have for new and experienced teachers alike. Over 700,000 teachers around the world already know how the techniques in this book turn educators into classroom champions. With ideas for everything from classroom management to inspiring student engagement, you will be able to perfect your teaching practice right away. * The 2/e offers an innovative approach to data structures and algorithms by incorporating the object-oriented design paradigm using C++. * Takes highly visual approach and extensive suite of Web-based learning giving students the opportunity to see visual justifications of key analytic concepts.