Data Structures and Other Objects Using C++

For example, the graphics program that generated the cover of this book uses a collection of three-dimensional objects--and a programmer must use the knowledge of data structures to make decisions on how to represent such collections. As a programmer, you must also possess an unshakable understanding of fundamental programming techniques and algorithms to manipulate the data structures. The graphics program is again a good example, using recursion to generate beautiful fractal patterns, and using efficient sorting algorithms in the process of removing hidden objects.

With many accessible examples, this book provides the knowledge of data representations and algorithms in a way that will be immediately useful to you with C++. This book also focuses on foundational material that will continue to be useful to you over the next ten years and beyond.

Data Structures and Other Objects Using C++ provides:

• a balanced approach to data structures and object-oriented programming
• early, self-contained coverage of key C++ and object-oriented programming topics
• a solid foundation in specifying, designing, implementing, and using simple container classes, lists, stacks, queues, trees, and more
• accessible coverage of fundamental topics such as container classes, pointers and linked lists, time analysis, testing, recursion, searching and sorting
• extensive appendices that will make this book a valuable resource for years to come

TABLE OF CONTENTS

1. PROGRAM SPECIFICATION, DESIGN, AND ANALYSIS

1. Specification and Design
2. Running Time Analysis
3. Testing and Debugging
4. Chapter Summary
5. Solutions to Self-Test Exercises

2. ABSTRACT DATA TYPES AND C++ CLASSES

1. Classes and Members
2. Constructors
3. Providing Your ADT to Other Programmers
4. Classes and Parameters
5. Operator Overloading
6. Chapter Summary
7. Solutions to Self-Test Exercises

3. CONTAINER CLASSES

1. The Bag ADT
2. Programming Project: The List ADT
3. Interactive Test Programs
4. Chapter Summary
5. Solutions to Self-Test Exercises
6. Programming Project

4. POINTERS AND DYNAMIC ARRAYS

1. Pointers and Dynamic Memory
2. Pointers and Arrays as Parameters
3. The Bag ADT with Dynamic Array
4. Prescription for a Dynamic Class
5. PROGRAMMING PROJECT: THE STRING ADT
6. Chapter Summary
7. Solutions to Self-Test Exercises

5. LINKED LISTS

1. Fundamentals of Linked Lists
2. A Linked List Toolkit
3. The Bag ADT with a Linked List
4. Programming Project: The Lit ADT with a Linked List
5. Dynamic Arrays vs. Linked Lists vs. doubly linked lists
6. Chapter Summary
7. Solutions to Self-Test Exercises
8. Programming Projects

6. SOFTWARE REUSE WITH TEMPLATES

1. Template Functions
2. Template Functions in a Toolkit
3. Template Classes
4. Using Templates in the Linked List Toolkit
5. The Bag Template Class with a Linked List
6. Chapter Summary
7. Solutions to Self-Test Exercises

7. STACKS

1. Introduction o Stacks
2. Stack Applications
3. Implementations Of The Stack ADT
4. More Complex Stack Applications
5. Chapter Summary
6. Solutions to Self-Test Exercises

8. QUEUES

1. Introduction to Queues
2. Queue Applications
3. Implementations of the Queue
4. Priority Queues
5. Chapter Summary
6. Solutions to Self-Test Exercises
7. Programming Project

9. RECURSIVE THINKING

1. Recursive Functions
2. Fractals and Mazes
3. Chapter Summary
4. Solutions to Self-Test Exercises
5. The Toolkit of UsefOL Functions

10. TREES

1. Introduction to Trees
2. Tree Implementations
3. A Toolkit for Binary Tree Nodes
4. Tree Traversals
5. Binary Search Trees
6. Chapter Summary
7. Solutions to Self-Test Exercises
8. Programming Project

11. TREES PROJECTS

1. Heaps
2. B-Trees
3. Trees, Logs, and Time Analysis
4. Chapter Summary
5. Solutions to Self-Test Exercises
6. Programming Project

12. SEARCHING

1. Open Address Hashing
2. Chained hashing
3. Chapter Summary
4. Solutions to Self-Test Exercises

13. SORTING

1. Quadratic Sorting Algorithms
2. Recursive Sorting Algorithms
3. Chapter Summary
4. Solutions to Self-Test Exercises

14. SOFTWARE REUSE WITH DERIVED CLASSES

1. Derived Classes
2. SimOLation of an Ecosystem
3. Using Derived Classes for ADTs
4. Chapter Summary
5. Solutions to Self-Test Exercises

15. GRAPHS

1. Graph Definitions
2. Graph Implementations
3. Graph Traversals
4. Path Algorithms
5. Chapter Summary
6. Solutions to Self-Test Exercises