C++ Plus Data Structures

Key features

• New to this Edition! The text has conformed to ISO/ANSI standard C++.
• New to this Edition! Inclusion of the Standard Template Library (STL).
• Trademark Dale pedagogy including seven large case studies.
• A complete Instructor's Guide, available for each section of the book, or an Instructor's ToolKit that provides PowerPoint presentations, computerized test bank, and all the program files included in the text.

Preface

Chapter 1. Software Engineering Principles
1.1Software Design Process
1.2 Verification of Software Correctness
Summary
Exercises
Chapter 2. Data Design and Implementation
2.1 Different Views of Data
2.2 Abstraction and Built-in Types
2.3 Higher-Level Abstraction and the C++ Class Type
2.4 C++ Constructs for Program Verification
Case Study: User-Defined String I/O Class
Summary
Exercises
Chapter 3. ADT's Unordered List and Sorted Lists
3.1 Lists
3.2 Abstract Data Type Unsorted List
3.3 Abstract Data Type Sorted List
3.4 Comparison of Algorithms
3.5 Comparison of Unsorted and Sorted List ADT Algorithms
3.6 Class Constructors, Class Destructors, and Overloading Operators
Case Study: Real Estate Listings, and Object-Oriented Design
Summary
Exercises
Chapter 4. ADT's Stack and Queue
4.1 Stacks
4.2 More about Generics: C++ Templates
4.3 Pointer Types
4.4 Dynamically Allocated Arrays
Case Study: Postfix Expression Evaluation
4.5 Queues
Case Study: Simulation
Summary
Exercises
Chapter 5. Linked Structures
5.1 Implementing a Stack as a Linked Structure
5.2 Implementing a Queue as a Linked Structure
5.3 Implementing the Unsorted List as a Linked Structure
5.4 Implementing the Sorted List as a Linked Structure
Summary
Exercises
Chapter 6. Lists Plus
6.1 Circular Linked Lists
6.2 Doubly Linked Lists
6.3 Linked Lists with Headers and Trailers
6.4 Copy Structures
6.5 A Specialized List ADT
6.6 A Linked List as an Array of Records
6.7 Object-Oriented Design: Composition and Inheritance
Case Study: Implementing a Large Integer ADT
Summary
Exercises
Chapter 7. Programming with Recursion
7.1 What is Recursion?
7.2 The Classic Example of Recursion
7.3 Programming Recursively
7.4 Verifying Recursive Functions
7.5 Writing Recursive Functions
7.6 Using Recursion to Simplify Solutions
7.7 Recursive Linked-List Processing
7.8 A Recursive Version of Binary Search
7.9 Recursive Version of InsertItem and DeleteItem
7.10 How Recursion Works
7.11 Tracing the Execution of Recursive Function Insert
7.12 Debugging Recursive Routines
7.13 Removing Recursion
7.14 Deciding Whether to Use a Recursive Solution
Case Study: Quick Sort
Summary
Exercises
Chapter 8. Binary Search Trees
8.1 The Logical Level
8.2 Binary Search Tree ADT
8.3 Application Level
8.4 Implementation Level
8.5 Recursive Binary Search Tree Operations
8.6 Iterative Insertion and Deletion}
8.7 Comparing Binary Search Trees to Linear Lists
Case Study: Building an Index
Summary
Exercises
Chapter 9. Trees Plus
9.1 Binary Expression Trees
9.2 A Nonlinked Representation of Binary Trees
9.3 Heaps
9.4 ADT Priority Queue
9.5 Graphs
Summary
Exercises
Chapter 10. Sorting and Searching Algorithms
10.1 Sorting
10.2 Searching
10.3 Radix Sort
Summary
Exercises

Programming Assignments
Answers to Selected Exercises
Appendices
A: Reserved Words
B: Operator Precedents
C: A Selection of Standard Library Routines
D: Character Sets
E: The Standard Template Library
Glossary
Index