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 algorithmsAllows you to visualize key analytic concepts, learn about the most recent insights in the field, and do data structure designProvides clear approaches for developing programsFeatures a clear, easy-to-understand writing style that breaks down even the most difficult mathematical conceptsBuilding 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 Basic C++ Programming Elements......Page 26 14.2.1 The Memory Hierarchy......Page 0 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.1 Design......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 Goals, Principles, and Patterns......Page 90 2.1.2 Object-Oriented Design Principles......Page 91 2.1.3 Design Patterns......Page 94 2.2 Inheritance and Polymorphism......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 Templates......Page 114 2.3.2 Class Templates......Page 115 2.4 Exceptions......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 Using Arrays......Page 128 3.1.2 Sorting an Array......Page 133 3.1.3 Two-Dimensional Arrays and Positional Games......Page 135 3.2 Singly Linked Lists......Page 141 3.2.2 Insertion to the Front of a Singly Linked List......Page 143 3.2.4 Implementing a Generic Singly Linked List......Page 145 3.3 Doubly Linked Lists......Page 147 3.3.2 Removal from a Doubly Linked List......Page 148 3.3.3 A C++ Implementation......Page 149 3.4 Circularly Linked Lists and List Reversal......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 The Seven Functions Used in This Book......Page 178 4.1.3 The Linear 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 Simple Justification Techniques......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.2 The STL Stack......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 Queues......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 Double-Ended Queues......Page 241 5.3.2 The STL Deque......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 Vectors......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 Lists......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 Sequences......Page 279 6.3.3 Implementing a Sequence with an Array......Page 281 6.4 Case Study: Bubble-Sort on a Sequence......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 Tree Traversal Algorithms......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 The Priority Queue Abstract Data Type......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 Heaps......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 Hash Tables......Page 399 9.2.2 Hash Functions......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 Dictionaries......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 10.1.3 C++ 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 Splay Trees......Page 474 10.3.2 When to Splay......Page 478 10.3.3 Amortized Analysis of Splaying......Page 480 10.4 (2,4) 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 Merge-Sort......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 Studying Sorting through an Algorithmic Lens......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 Sets and Union/Find Structures......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 Selection......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 Dynamic Programming......Page 581 12.2.2 DNA and Text Sequence Alignment......Page 584 12.3 Pattern Matching Algorithms......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 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 Data Structures for Graphs......Page 624 13.2.2 The Adjacency List Structure......Page 627 13.2.3 The Adjacency Matrix Structure......Page 629 13.3 Graph Traversals......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 Shortest Paths......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 External Memory and Caching......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."-- Read more... 1. A C++ primer -- 2. Object-oriented design -- 3. Arrays, linked lists, and recursion -- 4. Analysis tools -- 5. Stacks, queues, and deques -- 6. List and iterator ADTs -- 7. Trees -- 8. Heaps and priority queues -- 9. Hash tables, maps, and skip lists -- 10. Search trees -- 11. Sorting, sets, and selection -- 12. Strings and dynamic programming -- 13. Graph algorithms -- 14. Memory management and B-trees -- A. Useful mathematical facts

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.