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.

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. 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 Bibliography Index

A. Michael BermanVice President for Instructional and Information Technology, California State Polytechnic University, Pomona

"This new book on elementary data structures is designed for the standard second course in computer science. The first six chapters cover software engineering, algorithm design and analysis, and program correctness arguments, in addition to the standard data structures material presented later in the book. . . . The book is well written and easy to understand. Both programming exercises and those requiring written answers are built into the body of the text. In addition, most chapters end with programming laboratory problems. Students who attempt a significant number of the exercises should be able to master most of the material. I like this textbook and would recommend it to anyone teaching Computer Science 2 using C++."--Computing Reviews