We use cookies to enhance your experience on our website. By continuing to use our website, you are agreeing to our use of cookies. You can change your cookie settings at any time. Find out more

Data Structures via C++

Objects by Evolution

A. Michael Berman

Publication Date - March 1997

ISBN: 9780195108439

496 pages
7-1/2 x 9-1/4 inches

Retail Price to Students: $244.99


Bringing together the fundamental topics of a traditional introductory data structures course and the current world of C++ and object-oriented programming,Data Structures via C++: Objects by Evolution offers an evolutionary approach to the subject. It combines a sound pedagogy for teaching data structures at the introductory (CS2) level with modern ideas in software engineering and object-oriented programming. The book introduces students (and instructors) to C++ and object-oriented programming using a "just-in-time" approach which leads readers from traditional techniques to more current ideas.
This text emphasizes abstraction by introducing each new data structure first as an abstract data type (ADT), then discussing the external interface, and following with implementation. The primary data structures included are lists, stacks, queues, tables, trees, and graphs. All examples are developed using C++, and advanced features are introduced as needed or just-in-time. Berman's real-world examples, such as simulation of an Ethernet, robot navigation, and expression processing, help to illustrate use of data structures in concrete terms. C++ language features and object-oriented concepts, both very useful in solving problems encountered in the course, are also covered. Techniques of object-oriented programming are introduced, with a strong emphasis on encapsulation and detailed coverage of inheritance. An overview of software engineering is presented, including discussion of the software life-cycle, design, testing, assertions and loop invariants, and abstract data types. All supporting materials will be available to faculty and students via the World Wide Web at: http://www.rowan.edu/evolve.

Table of Contents

    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. Implementing 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

Related Title

An Introduction to C++ and Numerical Methods

An Introduction to C++ and Numerical Methods

James M. Ortega and Andrew S. Grimshaw