Table of contents for Data structures via C++ : objects by evolution / A. Michael Berman.


Bibliographic record and links to related information available from the Library of Congress catalog


Information from electronic data provided by the publisher. May be incomplete or contain other coding.


Counter
Preface
1. Software Engineering and Computer Programming
1.1. Software Engineering and Computer Science
1.1.1. Data Structures and Abstract Data Types
1.2. The Software "Life Cycle"
1.2.1. The Waterfall
1.2.2. Critiques of the Waterfall
1.2.3. Documentation
1.3. Why C++?
2. Designing Software: Two Approaches
2.1. Why Design?
2.2. Top-Down Design
2.3. The Object Alternative
2.4. Which Method is Better, TDD or OOD?
3. Software Reliability
3.1. Risks of Faulty Software
3.2. Testing
3.2.1. A Taxonomy of Errors
3.2.2. Approaches to Testing
3.2.3. Two Techniques for Unit Testing
3.3. Applying Program Correctness Techniques
3.3.1. Assertions
3.3.2. Preconditions and Postconditions
3.3.3. Loop Invariants and Proving Termination
3.3.4. Insertion Sort
4. Abstract Data Types, Classes, and Objects
4.1. Problem: Computing with Time
4.2. Describing Data Types
4.2.1. What's an ADT and Why Use It?
4.2.2. A Time ADT
4.3. ADT Implementation and Code Reuse
4.3.1. Code Reuse: Don't Reinvent the Wheel
4.3.2. Implementing a Time ADT
4.4. Information Hiding, Encapsulation, and Views
4.5. Creating Encapsulated ADTs Using the C++ Class
4.5.1. Declaring the Time Class
4.5.2. Creating ADT's for C++ Classes
4.5.3. Creating Clients for C++ Classes
4.5.4. Implementation for C++ Classes
4.6. Using Standarad C++ Class Libraries
4.6.1. Using C++ Libraries for Input and Output
4.6.2. Using C++ String Library
4.7. ADTs, Objects, and Object-Oriented Programming
5. Efficiency
5.1. Selecting Good Algorithms
5.2. The Many Faces of Program Efficiency
5.3. Algorithms for Searching
5.3.1. Linear Search
5.3.2. Binary Search
5.4. Analysis of Some Simple Sorting Algorithms
5.4.1. Selection Sort
5.4.2. Bubble Sort
6. Recursion
6.1. Solving Problems with Recursion
6.1.1. A Very Simple Example
6.1.2. The Nature of Recursion
6.2. Recursive Definitions
6.3. Applying Recursion to Sorting and Searching Problems
6.3.1. Recursive Search Algorithms
6.3.2. Quicksort: A Recursive Sorting Algorithm
6.4. How is Recursion Implemented?
6.4.1. What Happens When a Function Is Called?
6.4.2. What Happens When a Recursive Function Is Called?
6.4.3. Is Recursion Inefficient?
7. Lists
7.1. Problem: A Membership Management Program
7.2. The List ADT
7.3. Implementing Lists
7.3.1. A Header File for the List ADT
7.3.2. Implementation via Arrays
7.3.3. Implementation via Linked Lists
7.3.4. Dynamic Memory Allocation
7.4. The Inorder List ADT
7.5. Variations on a Linked List
7.5.1. Dummy Head Nodes
7.5.2. Circular Linked Lists
7.5.3. Doubly Linked Lists
7.6. A Dynamic Linear List
7.7. The Membership Management Program Revisited
8. Stacks
8.1. Problem: Robot Navigation
8.2. The Stack ADT
8.3. Implementing the Stack 1: Array
8.4. Creating Generic Classes with Templates
8.5. Implementing the Stack 2: Dynamic List
8.6. Applications of the Stack ADT
8.6.1. Building a Calculator with a Stack
8.6.2. How Is Recursion Implemented? Part 2
8.7. The Robot Navigation Problem Solved
9. Queues
9.1. Problem: Computer Network Performance
9.2. The Queue ADT
9.3. Implementing a Queue 1: Array
9.4. Implementing a Queue 2: Dynamic List
9.5. Simulation:Modelling a Computer Network
10. Tables
10.1. A Data Structure to Support Retrieval by Key
10.1.1. The Routing Problem
10.1.2. Defining the Table ADT
10.2. Implemeting a Table
10.2.1. Simple Implementation That Doesn't Quite Work
10.3. Hash Table for Fast Retrievals
10.3.1. Hash Functions
10.3.2. Picking a Good Hash Function
10.3.3. Methods of Handling Collisions
10.3.4. A Complete Implementation
10.3.5. Chained Hashing
10.4. Using Tables
11. Trees
11.1. Introducing Trees
11.1.1. Talking About Trees
11.1.2. Binary Trees
11.1.3. An Application: Expression Trees
11.2. Building the Binary Tree
11.2.1. The Binary Tree ADT
11.2.2. Implementing a Binary Tree
11.2.3. A Sample Client for the Binary Tree
11.2.4. Using the Binary Tree: Expression Trees Revisited
11.3. Tree Traversal
11.3.1. Three Tree Traversal Algorithms
11.3.2. Using Tree Traversals
11.3.3. Implementing Tree Traversals
11.4. Binary Search Trees
11.4.1. An Ordered Tree ADT
11.4.2. Implementing the Binary Search Tree
11.5. Reuse Through Inheritance: A Hierarchy of Trees
11.6. Performance of Binary Trees
11.6.1. The Shapes of Binary Trees
12. Graphs
12.1. Example: Keeping Track of Course Prerequisites
12.2. Basic Graph Concepts and Terminology
12.3. Creating Graph ADTs
12.3.1. Data Structures to Model Graphs
12.3.2. Defining Graph ADTs
12.3.3. A Hierarchy of Graphs
12.4. Implementing and Using Adjacency List Graphs
12.4.1. Implementing Lists with Iterators
12.4.2. The Adjacency List Abstract Base Class
12.4.3. The Undirected and Directed Adjacency List Graphs
12.4.4. Topological Sort
12.5. Implementing and Using Adjacency Matrix Graphs
12.5.1. Implementation of the Adjacency Matrix Classes
12.5.2. Finding the Transitive Closure
Appendix A: A Brief Review of C
Appendix B: C++ for the Pascal Programmer
Appendix C: C++ for the Programmer
Bibliography
Index



Library of Congress subject headings for this publication:
C++ (Computer program language)
Data structures (Computer science)
Object-oriented programming (Computer science)