內容簡介
內容簡介 This classic, best selling data structures text provides a firm foundation in data abstraction that emphasizes the distinction between specifications and implementation as the basis for an object-oriented approach. Software engineering principles and concepts as well as UML diagrams are used to enhance student understanding.The sixth edition of Data Abstraction and Problem Solving with C++: Walls & Mirrors welcomes Associate Professor Timothy Henry of the University of Rhode Island as a co-author with Frank Carrano. The 6th edition is a significant revision of the previous edition with these goals:- to place greater emphasis on data abstraction as a problem solving tool;- to emphasize C++ as an implementation tool;- to reduce the interdependency of chapters to allow more flexibility for instructors;- to demonstrate safe and secure programming practices,- to add VideoNotes- to include a transition guide from Python to C++
產品目錄
產品目錄 Chapter 1 Data Abstraction: The Walls1.1 Object-Oriented Concepts1.1.1 Object-Oriented Analysis and Design1.1.2 Aspects of an Object-Oriented Solution1.2 Achieving a Better Solution1.2.1 Cohesion1.2.2 Coupling1.3 Specifications1.3.1 Operation Contracts1.3.2 Unusual Conditions1.3.3 Abstraction1.3.4 Information Hiding1.3.5 Minimal and Complete Interfaces1.4 Abstract Data Types1.4.1 Designing an ADT1.4.2 ADTs that suggest other ADTs1.5 The ADT Bag1.5.1 Identifying Behaviors1.5.2 Specifying Data and Operations1.5.3 An Interface Template for the ADT1.5.4 Using the ADT BagC++ Interlude 1 C++ ClassesC1.1 A Problem to SolveC1.1.1 Private Data FieldsC1.1.2 Constructors and DestructorC1.1.3 MethodsC1.1.4 Preventing Compiler ErrorsC1.2 Implementing a SolutionC1.3 TemplatesC1.4 InheritanceC1.4.1 Base Classes and Derived ClassesC1.4.2 Overriding Base Class MethodsC1.5 Virtual Methods and Abstract ClassesC1.5.1 Virtual MethodsC1.5.2 Abstract ClassesChapter 2 Recursion: The Mirrors2.1 Recursive Solutions2.2 Recursion That Returns a Value2.2.1 A Recursive Valued Function: The Factorial of n 2.2.2 The Box Trace2.3 Recursion That Performs an Action2.3.1 A Recursive void Function: Writing a String Backward2.4 Recursion with Arrays2.4.1 Writing an Array’s Entries in Backward Order2.4.2 The Binary Search2.4.3 Finding the Largest Value in an Array2.4.4 Finding the kth Smallest Value of an Array2.5 Organizing Data2.5.1The Towers of Hanoi2.6 More Examples2.6.1 The Fibonacci Sequence (Multiplying Rabbits)2.6.2 Organizing a Parade2.6.3 Choosing k Out of n Things2.7 Recursion and EfficiencyChapter 3 Array-Based Implementations3.1 The Approach3.1.1 Core Methods3.1.2 Using Fixed-Size Arrays3.2 An Array-Based Implementation of the ADT Bag3.2.1 The Header File3.2.2 Defining the Core Methods3.2.3 Testing the Core Methods3.2.4 Implementing More Methods3.2.5 Methods That Remove Entries3.2.6 Testing3.3 Using Recursion in the ImplementationC++ Interlude 2 Pointers, Polymorphism, and Memory AllocationC2.1 Memory Allocation for Variables and Early Binding of MethodsC2.2 A Problem to SolveC2.3 Pointers and the Program Free StoreC2.3.1 Deallocating MemoryC2.3.2 Avoiding Memory LeaksC2.3.3 Avoiding Dangling PointersC2.4 Virtual Methods and PolymorphismC2.5 Dynamic Allocation of ArraysC2.5.1 A Resizable Array-Based BagChapter 4 Link-Based Implementations4.1 Preliminaries4.1.1 The Class Node4.2 A Link-Based Implementation of the ADT Bag4.2.1 The Header File4.2.2 Defining the Core Methods 4.2.3 Implementing More Methods4.3 Using Recursion in Link-Based Implementations4.3.1 Recursive Definitions of Methods in LinkedBag4.4 Comparing Array-Based and Link-Based ImplementationsChapter 5 Recursion as a Problem-Solving Technique5.1 Defining Languages5.1.1 The Basics of Grammars5.1.2 Two Simple Languages5.3 Algebraic Expressions5.2.1 Kinds of Algebraic Expressions5.2.2 Prefix Expressions5.2.3 Postfix Expressions5.2.4 Fully Parenthesized Expressions5.3 Backtracking5.3.1 Searching for an Airline Route5.3.2 The Eight Queens Problem5.4 The Relationship Between Recursion and Mathematical Induction5.4.1 The Correctness of the Recursive Factorial Function5.4.2 The Cost of Towers of HanoiChapter 6 Stacks6.1 The Abstract Data Type Stack6.1.1 Developing an ADT During the Design of a Solution6.1.2 Specifications for the ADT Stack6.2 Simple Uses of a Stack6.2.1 Checking for Balanced Braces6.2.2 Recognizing Strings in a Language6.3 Using Stacks with Algebraic Expressions6.3.1 Evaluating Postfix Expressions6.3.2 Converting Infix Expressions to Equivalent Postfix Expressions6.4 Using a Stack to Search a Flight Map6.5 The Relationship Between Stacks and RecursionC++ Interlude 3 ExceptionsC3.1 BackgroundC3.1.1 A Problem to SolveC3.2 AssertionsC3.3 Throwing ExceptionsC3.4 Handling ExceptionsC3.1.1 Multiple catch BlocksC3.1.2 Uncaught ExceptionsC3.5 Programmer-Defined Exception ClassesChapter 7 Stack Implementations7.1 An Array-Based Implementation7.2 A Linked Implementation7.3 Comparing ImplementationsChapter 8 Lists8.1 Specifying the Abstract Data Type List8.2 Using the List Operations8.3 Specifications of the ADT List Using Exceptions Chapter 9 List Implementations9.1 An Array-Based Implementation of the ADT List9.1.1 The Header File9.1.2 The Implementation File9.2 A Linked Implementation of the ADT List9.2.1 The Header File9.2.2 The Implementation File9.2.3 Using Recursion To Process a Linked Chain9.3 Comparing ImplementationsChapter 10 Algorithm Efficiency10.1 What Is a Good Solution?10.2 Measuring the Efficiency of Algorithms10.2.1 The Execution Time of Algorithms10.2.2 Algorithm Growth Rates10.2.3 Order-of-Magnitude Analysis and Big O Notation10.2.4 Keeping Your Perspective10.2.5 The Efficiency of Searching AlgorithmsChapter 11 Sorting Algorithms and Their Efficiency11.1 Basic Sorting Algorithms11.1.1 Selection Sort11.1.2 Bubble Sort11.1.3 Insertion Sort11.2 Faster Sorting Algorithms11.2.1 Merge Sort11.2.2 Quick Sort11.2.3 Radix Sort11.3 A Comparison of Sorting Algorithms11.4 The Standard Template Library: Sorting AlgorithmsC++ Interlude 4 Class Relationships and ReuseC4.1 Inheritance RevisitedC4.1.1 Public, Private, and Protected Sections of a ClassC4.1.2 Public, Private, and Protected InheritanceC4.1.3 Is-a and As-a RelationshipsC4.2 Containment: Has-a RelationshipsC4.3 Abstract Base Classes RevisitedChapter 12 Sorted Lists and Their Implementations12.1 Specifying the ADT Sorted List12.1.1 An Interface Template for the ADT Sorted List12.1.2 Using the Sorted List Operations12.2 A Link-Based Implementation12.2.1 The Header File12.2.3 The Implementation File12.2.3 The Efficiency of the Link-Based Implementation12.3 Implementations That Use the ADT List12.3.1 Composition12.3.2 Public Inheritance12.3.3 Private InheritanceChapter 13 Queues and Priority Queues13.1 The ADT Queue13.2 Simple Applications of a Queue13.2.1 Reading a String of Characters13.2.2 Recognizing Palindromes13.3 The ADT Priority Queue13.4.1 Tracking Your Assignments13.4 Application: Simulation13.5 Position-Oriented and Value-Oriented ADTsChapter 14 Queue Implementations14.1 Implementations of the ADT Queue14.1.1 An Implementation That Uses the ADT List14.1.2 A Link-Based Implementation14.1.3 An Array-Based Implementation14.1.4 Comparing Implementations14.2 An Implementation of the ADT Priority QueueC++ Interlude 5 Overloaded Operators and Friend ClassesOverloading OperatorsOverloading the Stream Operators << and >>Friend Classes and Data Member AccessChapter 15 Trees15.1 Terminology15.1.1 Kinds of Trees15.1.2 The Height of Trees15.1.3 Full, Complete, and Balanced Binary Trees15.1.4 The Maximum and Minimum Heights of a Binary Tree15.2 The ADT Binary Tree15.2.1 Binary Tree Operations15.2.2 An Interface Template for the ADT Binary Tree15.2.3 Traversals of a Binary Tree15.3 The ADT Binary Search Tree15.3.1 Binary Search Tree Operations15.3.2 An Interface Template for the ADT Binary Tree15.3.3 Searching a Binary Search Tree15.3.4 Creating a Binary Search Tree15.3.5 Traversals of a Binary Search TreeChapter 16 Tree Implementations16.1 Implementations of the ADT Binary Tree16.1.1 A Link-Based Implementation16.1.2 An Array-Based Implementation16.1.3 Efficiency of Implementations16.2 An Implementation of the ADT Binary Search Tree16.2.1 Algorithms for Insertion, Deletion, and Traversal16.2.2 A Link-Based Implementation16.2.3 Efficiency of the Implementation16.2.4 Saving a Binary Search Tree in a FileC++ Interlude 6 IteratorsIterator IntroductionA List Iterator and Its UseA BST Tree Iterator and Its UseChapter 17 HeapsAn Array-Based ImplementationA Heap as a Priority QueueThe Heap SortChapter 18 Dictionaries and Their ImplementationsDictionaries and Key-Value PairsLinear (Array and Linked) and Hierarchical (Tree) ImplementationsHash FunctionsResolving CollisionsA Hashing ImplementationThe Efficiency of HashingChapter 19 Balanced Search TreesAVL Trees2-3 Trees2-3-4 TreesRed-Black TreesChapter 20 Graphs20.1 Terminology20.2 Graphs as ADTs20.2.1 Implementing Graphs20.3 Graph Traversals 20.3.1 Depth-First Search20.3.2 Breadth-First Search20.4 Applications of Graphs20.4.1 Topological Sorting20.4.2 Spanning Trees20.4.3 Minimum Spanning Trees20.4.4 Shortest Paths20.4.5 Circuits20.4.6 Some Difficult ProblemsChapter 21 Processing Data in External Storage21.1 A Look at External Storage21.2 A Sorting Data in an External File21.3 External Searches21.3.1 Indexing an External File21.3.2 External Hashing21.3.3 B-Trees21.3.4 Traversals21.3.5 Multiple IndexingC++ Interlude 7 The Standard Template LibraryIntroduction to Templates and the STLGeneralizing the ADT Node and ListAppendix A Review of C++ FundamentalsAppendix B Important Themes in Programming (currently Section 1.3)Appendix C The Unified Modeling Language (currently in section 1.1)Appendix D The Software Life Cycle (currently section 1.1)Appendix E Mathematical Induction (currently Appendix D)Appendix F Algorithm Verification (currently in section 1.2)Appendix G FilesAppendix H C++ Header Files and Standard Functions (currently Appendix C)Appendix I C++ Standard Template Library (currently Appendix E)Appendix J C++ Documentation Systems (currently Appendix F) Appendix K ASCII Character Codes (currently Appendix B)Appendix L A Comparison of C++ and Java Appendix M A Comparison of C++ and Python