About the Book

Written by renowned author and educator Nell Dale, C++ Plus Data Structures, Fifth Edition explores the specifications, applications, and implementations of abstract data types with unmatched accessibility. Updated with new case studies and exercises throughout, 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 Fifth Edition provides an increased emphasis on object-oriented design and an early introduction of object/oriented concepts.

New and Key Features of the Fifth Edition:
• Object-oriented terminology now dominates computing vocabulary. Dale was careful to update all ADT names to reflect this terminology.
• Additional exercises have been added to most chapters.
• The Fifth Edition features the trademark Dale pedagogy and highlights numerous real-world, updated 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 40 engaging exercises that span varying levels of difficulty. These exercises test students’ understanding of key concepts through various means, including programming problems and analysis of algorithm problems.

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, traveling, tennis, and bridge -- and her family of course.

Table of Contents:
Preface Chapter 1: Software Engineering Principles • The Software Process • Program Design • Design Approaches • Verification of Software Correctness • Case Study: Fraction Class • Summary • Exercises Chapter 2: 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 • Case Study: User-Defined Date ADT • Summary • Exercises Chapter 3: ADT Unsorted List • Lists • Abstract Data Type Unsorted List • Pointer Types • Implementing Class UnsortedType as a Linked Structure • Comparing Unsorted List Implementations • Case Study: Creating a Deck of Playing Cards • Summary • Exercises Chapter 4: 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 • Case Study: Evaluating Card Hands • Summary • Exercises Chapter 5: ADTs Stack and Queue • Stacks • Implementing a Stack as a Linked Structure • Queues • Implementing a Queue as a Linked Structure • Case Study: Simulating a Solitaire Game • Summary • Exercises Chapter 6: 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 • Case Study: Implementing a Large Integer ADT • Summary • Exercises Chapter 7: 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 PutItem and DeleteItem • How Recursion Works • Tracing the Execution of Recursive Function Insert • Debugging Recursive Routines • Removing Recursion • Deciding Whether to Use a Recursive Solution • Case Study: Escaping from a Maze • Summary • Exercises Chapter 8: 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 • Case Study: Building an Index • Summary • Exercises Chapter 9: Priority Queues, Heaps, Graphs, and Sets • ADT Priority Queue • Heaps • Graphs • Sets • Summary • Exercises Chapter 10: 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