C++ Plus Data Structures

0.0

C++ Plus Data Structures, Fourth Edition explores the specifications, applications, and implementations of abstract data types with unmatched accessibility. Updated and reorganized, this edition provides intuitive explanations that clarify abstract concepts and approaches the study of data structures with emphasis on computer science theory and software engineering principles. Topics such as modularization, data encapsulation, information hiding, object-oriented decomposition, algorithm analysis, life-cycle software verification models, and data abstraction are carefully presented to foster solid software engineering techniques. In addition to real-world exercises and case studies that define Nell Dale’s teaching philosophy, this Fourth Edition provides an increased emphasis on object-oriented design and an early introduction of object-oriented concepts. Key Feature Features the trademark Dale pedagogy and highlights numerous real-world case studies. Each broad case study includes a description of the problem, an analysis of the problem’s input and required output, and a discussion of the appropriate data types to use. Each chapter contains an average of 35 engaging exercises that span varying levels of difficulty. These exercises test students’ understanding of key concepts, including programming problems and analysis of algorithm problems through various means. New reorganization places ADT Stacks and Queues together within the same chapter for added accessibility. About The Author Nell Dale, PhD - University of Texas, Austin Nell Dale received a B.S. in Mathematics and Psychology from the University of Houston, a M.A. in Mathematics, from the University of Texas at Austin, and a Ph. D. in Computer Sciences from the University of Texas at Austin. Nell Dale has been on the faculty at the University of Texas, Austin since 1975. She teaches occasionally but concentrates on computer science education & writing. Table of Contents Software Engineering Principles The Software Process Program Design Design Approaches Verification of Software Correctness Summary Exercises Data Design and Implementation Different Views of Data Abstraction and Built-In Types Higher-Level Abstraction and the C++ Class Type Object-Oriented Programming Constructs for Program Verification Comparison of Algorithms Summary Exercises ADT Unsorted List Lists Abstract Data Type Unsorted List Pointer Types Implementing Class Unsorted Type as a Linked Structure Comparing Unsorted List Implementations Summary Exercises ADT Sorted list Abstract Data Type Sorted List Dynamically Allocated Arrays Implementing the Sorted List as a Linked Structure Comparison of Unsorted and Sorted List ADT Algorithms Bounded and Unbounded ADTs Object-Oriented Design Methodology Summary Exercises ADTs Stack and Queue Stacks Implementing a Stack as a Linked Structure Queues Implementing a Queue as a Linked Structure Summary Exercises Lists Plus More about Generics: C++ Templates Circular Linked Lists Doubly Linked Lists Linked Lists with Headers and Trailers Copy Structures A Linked List as an Array of Records Polymorphism with Virtual Functions A Specialized List ADT Summary Exercises Programming with Recursion What Is Recursion? The Classic Example of Recursion Programming Recursively Verifying Recursive Functions Writing Recursive Functions Using Recursion to Simplify Solutions Recursive Linked List Processing A Recursive Version of Binary Search Recursive Versions of InsertItem and DeleteItem How Recursion Works Tracing the Execution of Recursive Function Insert Debugging Recursive Routines Removing Recursion Deciding Whether to Use a Recursive Solution Summary Exercises Binary Search Trees Trees Logical Level Application Level Implementation Level Recursive Binary Search Tree Operations Iterative Insertion and Deletion Comparing Binary Search Trees and Linear Lists A Nonlinked Representation of Binary Trees Summary Exercises Priority Queues, Heaps, Graphs, and Sets ADT Priority Queue Heaps Graphs Sets Summary Exercises Sorting and Searching Algorithms Sorting Searching Hashing Radix Sort Summary Exercises Appendix A Reserved Words Appendix B Operator Precedence Appendix C A Selection of Standard Library Routines Appendix D Character Sets Appendix E The Standard Template Library Glossary Index.