vi APPROACH
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 effi-
ciency and sorting (Chapter 9) any time after Chapter 5. You can intro-
duce 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 program-
ming abilities by emphasizing both the thought processes and the tech-
niques 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 recur-
sion are used to design solutions to problems throughout the book.
C++ pointers and linked list 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 aids, and loop invariants are important
Preface C++ 3e.fm Page vi Monday, July 16, 2001 1:44 PM
