Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000004820290 | QA76.73.C153 B46 1997 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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.
Author Notes
A. Michael Berman is at Rowan College of New Jersey.
Table of Contents
| 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 |
