Data Abstraction and Problem Solving with C++: Walls and Mirrors, 3rd Edition

About

Features

• NEW! Introduces the Unified Modeling Language (UML) as a tool for designing classes.

• NEW! Provides coverage of the Standard Template Library (STL).

• NEW! Updated coverage of C++, including an introduction to C++ exceptions, and discussion of C++ namespaces.

• NEW! Includes many new and revised exercises and programming projects.

• The challenging topic of Recursion (mirrors) is taught in Chapter 2 and used throughout so students master this important concept.

• Data abstraction (walls) is taught in Chapter 3 and also carried throughout.

• Focuses on coverage of data structures instead of language syntax. However, all C++ code has been updated.



Description

• Copyright 2002
• Dimensions: 7 15/16 x 10
• Pages: 944
• Edition: 3rd

• Book
• ISBN-10: 0-201-74119-9
• ISBN-13: 978-0-201-74119-3

The classic Data Abstraction and Problem Solving with C++: Walls and Mirrors been revised to further enhance its focus on data abstraction and data structures using C++. It provides a firm foundation in data abstraction, emphasizing the distinction between specification and implementation as the foundation for an object-oriented approach. Professors Frank Carrano and Janet Prichard cover key object-oriented concepts, including encapsulation, inheritance and polymorphism. However, the focus remains on data abstraction instead of simply C++ syntax.

The authors also illustrate the role of classes and ADTs in the problem-solving process and include major applications of ADTs, such as searching a flight map and event-driven simulation. The book offers early, extensive coverage of recursion and uses this technique in many examples and exercises. It also introduces analysis of algorithms and the Big "0" notation. New to this edition is an introduction to the Standard Template Library and the Unified Modeling Language. Features

• Includes a lucid writing style, wide-spread use of examples, and flexible coverage of topics
• Provides a strong introduction to, and a continuous use of, data abstraction
• Presents the best coverage of recursion available in any textbook, starting in Chapter 2
• Focuses on coverage of data structures instead of language syntax-still, all C++ code has been updated to conform with ANSI Standard C++
• Contains coverage of the Standard Template Library (STL)
• Introduces the Unified Modeling Language (UML) as a tool for designing classes
• Provides an appendix on basic C++ syntax for those who are making the transition to C++ from another language



Sample Content

Table of Contents

Preface.


Chapter Dependency Chart.

I. PROBLEM-SOLVING TECHNIQUES.

1. Principles of Programming and Software Engineering.

Problem Solving and Software Engineering.

Achieving A Modular Design.

A Summary of Key Issues in Programming.

2. Recursion: The Mirrors.

Recursive Solutions.

Counting Things.

Searching An Array.

Organizing Data.

Recursion And Efficiency.

3. Data Abstraction: The Walls.

Abstract Data Types.

Specifying ADTs.

Implementing ADTs.

4. Linked Lists.

Preliminaries.

Programming with Linked Lists.

Variations of the Linked List 206.

Application: Maintaining an Inventory.

The C++ Standard Template Library.

5. Recursion as a Problem-Solving Technique.

Backtracking.

Defining Languages.

The Relationship between Recursion and Mathematical Induction.

II. PROBLEM SOLVING WITH ABSTRACT DATA TYPES.

6. Stacks.

The Abstract Data Type Stack.

Simple Applications Of The ADT Stack.

Implementations Of The ADT Stack.

Application: Algebraic Expressions.

Application: A Search Problem.

The Relationship between Stacks and Recursion.

7. Queues.

The Abstract Data Type Queue.

Simple Applications of the ADT Queue.

Implementations of the ADT Queue.

A Summary Of Position-Oriented ADTs.

Application: Simulation.

8. Advanced C++ Topics.

Inheritance Revisited.

Virtual Functions and Late Binding.

Friends.

The ADTs List and Sorted List Revisited.

Class Templates.

Overloaded Operators.

Iterators.

9. Algorithm Efficiency and Sorting.

Measuring the Efficiency of Algorithms.

Sorting Algorithms and Their Efficiency.

10. Trees.

Terminology.

The ADT Binary Tree.

The ADT Binary Search Tree.

General Trees.

11. Tables and Priority Queues.

The ADT Table.

The ADT Priority Queue: A Variation of the ADT Table.

12. Advanced Implementations of Tables.

Balanced Search Trees.

Hashing.

Data with Multiple Organizations.

13. Graphs.

Terminology.

Graphs as ADTs.

Graph Traversals.

Applications of Graphs.

14. External Methods.

A Look at External Storage.

Sorting Data in an External File.

External Tables.

Appendices.
A. Review Of C++ Fundamentals.

Language Basics.

Input and Output Using iostream.

Functions.

Selection Statements.

Iteration Statements.

Arrays.

Strings.

Structures.

C++ Exceptions.

File Input and Output.

Libraries.

A Comparison to Java.

B. Ascii Character.
C. Codes (Ascii Subset).
D. C++ Header Files And Standard Functions.
E. Mathematical Induction.
Glossary.
Answers to Self-Test Exercises.
Index.

Preface

Welcome to the third edition of Data Abstraction and Problem Solving with C++: Walls and Mirrors. Since the publication of the second edition, we all have gained experience with teaching data abstraction in an object-oriented way using C++. This edition reflects that experience and the evolution that C++ has taken.

This book is based on the original Intermediate Problem Solving and Data Structures: Walls and Mirrors by Paul Helman and Robert Veroff (© 986 by The Benjamin/Cummings Publishing Company, Inc.). This work builds on their organizational framework and overall perspective and includes technical and textual content, examples, figures, and exercises derived from the original work. Professors Helman and Veroff introduced two powerful analogies, walls and mirrors, that have made it easier for us to teach—and to learn—computer science.

With its focus on data abstraction and other problem-solving tools, this book is designed for a second course in computer science. In recognition of the dynamic nature of the discipline and the great diversity in undergraduate computer science curricula, this book includes comprehensive coverage of enough topics to make it appropriate for other courses as well. For example, you can use this book in courses such as introductory data structures or advanced programming and problem solving. The goal remains to give students a superior foundation in data abstraction, object-oriented programming, and other modern problem-solving techniques.

TO THE STUDENT

Thousands of students before you have read and learned from Walls and Mirrors. The walls and mirrors in the title represent two fundamental problem-solving techniques that appear throughout the presentation. Data abstraction isolates and hides the implementation details of a module from the rest of the program, much as a wall can isolate and hide you from your neighbor. Recursion is a repetitive technique that solves a problem by solving smaller problems of exactly the same type, much as mirror images grow smaller with each reflection.

This book was written with you in mind. As former college students, and as educators who are constantly learning, we appreciate the importance of a clear presentation. Our goal is to make this book as understandable as possible. To help you learn and to review for exams, we have included such learning aids as margin notes, chapter summaries, self-test exercises with answers, and a glossary. As a help during programming, you will find C++ reference material in the appendixes and inside the covers. You should review the list of this book's features given later in this preface in the section "Pedagogical Features."

The presentation makes some basic assumptions about your knowledge of C++. Some of you may need to review this language or learn it for the first time by consulting Appendix A of this book. You will need to know about the selection statements if and switch; the iteration statements for, while, and do; functions and argument passing; arrays; strings; structures; and files. This book covers C++ classes in Chapters 1, 3, and 8 and does not assume that you already know this topic. We assume no experience with recursive functions, which are included in Chapters 2 and 5.

All of the C++ source code that appears in this book is available for your use. Later in this preface, the description of supplementary materials tells you how to obtain these files. Note, however, that your instructor may already have obtained them for you.

APPROACH

This edition of Walls and Mirrors uses C++ to enhance its emphasis on data abstraction and data structures. The book carefully accounts for the strengths and weaknesses of the C++ language and remains committed to a pedagogical approach that makes the material accessible to students at the introductory level.

Prerequisites

We assume that readers either know the fundamentals of C++ or know another language and have an instructor who will help them make the transition to C++ by using the provided appendix. The book formally introduces C++ classes, and so does not assume prior knowledge of them. Included are the basic concepts of object-oriented programming, inheritance, virtual functions, and class templates, all in C++. Although the book provides an introduction to these topics in connection with the implementations of abstract data types (ADTs) as classes, the emphasis remains on the ADTs, not on C++. The material is presented in the context of object-based programming, but it assumes that future courses will cover object-oriented design and software engineering in detail, so that the focus can remain orb data abstraction. We do, however, introduce the Unified Modeling Language (UML) as a design tool.

Flexibility

The extensive coverage of this book should provide you with the material that you want for your course. You can select the topics you desire and present them in an order that fits your course. The chapter dependency chart shows which chapters should be covered before a given chapter can be taught. 0 In Part I, you can choose among topics according to your students' background. Three of the chapters in this part provide an extensive `introduction to data abstraction and recursion. Both topics are important, and there are various opinions about which should be taught first. Although in this book a chapter on recursion both precedes and follows the chapter on data abstraction, you can simply rearrange this order.

Part II treats topics that you can also cover in a flexible order. For example, you can cover all or parts of Chapter 8 on advanced C++ either before or after you cover stacks (Chapter 6). You can cover algorithm efficiency and sorting (Chapter 9) any time after Chapter 5. You can introduce trees before queues or graphs before tables, or cover hashing, balanced search trees, or priority queues any time after tables and in any order. You also can cover external methods (Chapter 14) earlier in the course. For example, you can cover external sorting after you cover mergesort in Chapter 9.

Data Abstraction

The design and use of abstract data types permeate this book's problem-solving approach. Several examples demonstrate how to design an ADT as part of the overall design of a solution. All ADTs are first specified-in both English and pseudocode-and then used in simple applications before implementation issues are considered. The distinction between an ADT and the data structure that implements it remains in the forefront throughout the discussion. The book explains both encapsulation and C++ classes early. Students see how C++ classes hide an implementation's data structure from the client of the ADT. Abstract data types such as lists, stacks, queues, trees, tables, heaps, and priority queues form the basis of our discussions.

Problem Solving

This book helps students learn to integrate problem-solving and programming abilities by emphasizing both the thought processes and the techniques that computer scientists use. Learning how a computer scientist develops, analyzes, and implements a solution is just as important as learning the mechanics of the algorithm; a cookbook approach to the material is insufficient.

The presentation includes analytical techniques for the development of solutions within the context of example problems. Abstraction, the successive refinement of both algorithms and data structures, and recursion are used to design solutions to problems throughout the book.

C++ pointers and linked lift processing are introduced early and used in building data structures. The book also introduces at an elementary level the order-of-magnitude analysis of algorithms. This approach allows the consideration—first at an informal level, then more quantitatively—of the advantages and disadvantages of array-based and pointer-based data structures. An emphasis on the trade-offs among potential solutions and implementations is a central problem-solving theme.

Finally, programming style, documentation including preconditions and postconditions, debugging ails, and loop invariants are important parts of the problem-solving methodology used to implement and verify solutions. These topics are covered throughout the book.

Applications

Classic application areas arise in the context of the major topics of this book. For example, the binary search, quicksort, and mergesort algorithms provide important applications of recursion and introduce order-of-magnitude analysis. Such topics as balanced search trees, hashing, and file indexing continue the discussion of searching. Searching and sorting are considered `again in the context of external files.

Algorithms for recognizing and evaluating algebraic expressions are first introduced in the context of recursion and are considered again later as an application of stacks. Other applications include, for example, the Eight Queens problem as an example of backtracking, event-driven simulation as an application of queues, and graph searching and Maversals as other important applications of stacks and queues.

NEW AND REVISED MATERIAL

This edition retains the underlying approach and philosophy of the second edition. We present data abstraction and programming both as general concepts and in the context of C++. No sentence, example, margin note, or figure escaped scrutiny during the preparation of this edition. Many changes, additions, and deletions to the text, figures, and margin notes were made to update and clarify the presentation. All C++ programs were revised to reflect recent changes to the language.

Although we revised all chapters and appendixes, here is a list of the major changes to the book.

• The specifications of all ADT operations now use UML notation to clarify the purpose and data type of their parameters.
• Chapter 1 enhances its coverage of object-oriented design and introduces the Unified Modeling Language (UML). We have revised our naming conventions for C++ identifiers to be consistent with common practice. This change will help students who either know Java or will learn Java later.
• Chapter 3 briefly introduces inheritance after its presentation of C++ classes. Also covered are the C++ namespace and exceptions. Although the ADTs in this chapter return boolean flags to indicate error conditions, subsequent chapters use exceptions.
• Chapter 4 includes a new section about the C++ Standard Template Library (STL). Class templates, containers, and iterators are introduced. More extensive coverage of these topics is deferred until Chapter 8. Chapter 4 also considers the STL class list. Other classes in the STL are presented throughout the book, and you can either skip or postpone covering them, as desired.
• Chapter 6 includes the STL class stack.
• Chapter 7 includes the STL class queue.
• Chapter 8 provides a deeper discussion of inheritance and class templates than was given earlier. Also covered are C++ friends and iterators.
• Appendix A is an updated review of C++ that now includes coverage of exceptions. Appendix C is an updated list of C++ headers. Appendix E is new and contains the STL classes list, stack, and queue.

OVERVIEW

The pedagogical features and organization of this book were carefully designed to facilitate learning and to allow instructors to tailor the material easily to a particular course.

Pedagogical Features

This book contains the following features that help students not only during their first reading of the material, but also during subsequent review:

• Chapter outlines and previews.
• Boxes listing key concepts in the material.
• Margin notes.
• Chapter summaries.
• Cautionary warnings about common errors and misconceptions.
• Self-test exercises with answers.
• Chapter exercises and programming problems. The most challenging exercises are labeled with asterisks. Answers to the exercises appear in the Instructor's Resource Manual.
• Specifications for all major ADTs in both English and pseudocode, as well as in UML notation.
• C++ class definitions for all major ADTs.
• Examples that illustrate the role of classes and ADTs in the problem-solving process.
• Appendixes, including a review of C++. Glossary of terms.

Organization

The chapters in this book are organized into two parts. In most cases, Chapters 1 through 11 will form the core of a one-semester course. Chapters,.. or 2 might be review material for your students. The coverage given to Chapters 11 through 14 will depend on the role the course plays in your curriculum. More detailed suggestions for using this book with different courses appear in the Instructor's Resource Manual.

Part I: Problem-Solving Techniques. The first chapter in Part I emphasizes the major issues in programming and software engineering. A new introduction to the Unified Modeling Language (UML) is given here. The next chapter discusses recursion for those students who have had little exposure to this important topic. The ability to think recursively is one of the most useful skills that a computer scientist can possess and is often of great value in helping one to better understand the nature of a pr6blem. Recursion is discussed extensively in this chapter and again in Chapter 5 and is used throughout the book. Included examples range from simple recursive definitions to recursive algorithms for language recognition, searching, and sorting.

Chapter 3 covers data abstraction and abstract data types (ADTs) in detail. After a discussion of the specification and use of an ADT, the chapter presents C++ classes and uses them to implement ADTs. This chapter includes a brief introduction to inheritance, the C++ namespace, and exceptions. Chapter 4 presents additional implementation tools in its discussion of C++ pointer variables and linked lists. This chapter also introduces class templates, the C++ Standard Template Library (STL), containers, and iterators.

You can choose among the topics in Part I according to the background of your students and cover these topics in several orders.

Part II: Problem Solving with Abstract Data Types. Part II continues to explore data abstraction as a problem-solving technique. Basic abstract data types such as the stack, queue, binary tree, binary search tree, table, heap, and priority queue are first specified and then implemented as classes. The ADTs are used in examples and their implementations are compared.

Chapter 8 extends the coverage of C++ classes by further developing inheritance, class templates, and iterators. The chapter then introduces virtual functions and friends. Chapter 9 formalizes the earlier discussions of an algorithm's efficiency by introducing order-of-magnitude analysis and Big O notation. The chapter examines the efficiency of several searching and sorting algorithms, including the recursive in mergesort and quicksort.

Part II also includes advanced topics—such as balanced search trees (2-3, 2-3-4, red-black, and AVL trees) and hashing—that are examined as table implementations. These implementations are analyzed to determine the table operations that each supports best.

Finally, data storage in external direct access files is considered. Mergesort is modified to sort such data, and external hashing and B-tree indexes are used to search it. These searching algorithms are generalizations of the internal hashing schemes and 2-3 trees already developed.

SUPPLEMENTARY MATERIALS

The following supplementary materials are available online to assist instructors and students.

• Source code. All of the C++ classes, functions, and programs that appear in the book are available to readers.
• Errata. We have tried not to make mistakes, but mistakes are inevitable. A list of detected errors is available and updated as necessary. You are invited to contribute your finds.
• The source code and errata list are available at the URL www.aw.com/cssupport
• Instructor's Resource Manual. Solutions to the exercises at the end of the chapters as well as teaching notes and suggestions are available only to instructors through your Addison-Wesley sales representative.



Updates

Submit Errata

