英文第二版
Preface
This book is designed for a two-semester sequence in computer science,
beginning with what is typically known as Data Structures (CS-2) and con-
tinuing with advanced data structures and algorithm analysis.
The content of the CS-2 course has been evolving for some time.
Although there is some general con
sensus concerning topic coverage, con-
siderable disagreement still exists over the details. One uniformly accepted
topic is principles of software development, most notably the concepts of
encapsulation and information hiding. Algorithmically, all CS-2 courses
tend to include an introduction to running-time analysis, recursion, basic
sorting algorithms, and elementary data structures. An advanced course is
offered at many universities that covers topics in data structures, algorithms,
and running-time analysis at a higher level. The material in this text has been
designed for use in both levels of courses, thus eliminating the need to pur-
chase a second textbook.
Although the most passionate debates in CS-2 revolve around the choice
of a programming language, other fundamental choices need to be made,
including
whether to introduce object-oriented design or object-based design
early,
the level of mathematical rigor,
the appropriate balance between the implementation of data struc-
tures and their use, and
programming details related to the language chosen.
My goal in writing this text was to provide a practical introduction to
data structures and algorithms from the viewpoint of abstract thinking and
problem solving. I tried to cover all of the important details concerning the
data structures, their analyses, and their C++ implementations, while staying away from data structures that are theoretically interesting but not widely
used. It is impossible to cover in a single course all the different data struc-
tures, including their uses and the analysis, described in this text. So, I
designed the textbook to allow instructors flexibility in topic coverage. The
instructor will need to decide on an appropriate balance between practice
and theory and then choose those topics that best fit the course. As I discuss
later in this Preface, I organized the text to minimize dependencies among
the various chapters.
A Unique Approach
My basic premise is that software development tools in all languages come
with large libraries, and many data structures are part of these libraries. I
envision an eventual shift in emphasis of data structures courses from imple-
mentation to use. In this book I take a unique approach by separating the
data structures into their specification and subsequent implementation and
take advantage of an already existing data structures library, the Standard
Template Library (STL).
A subset of the STL suitable for most applications is discussed in a sin-
gle chapter (Chapter 7) in Part 11. Part 11 also covers basic analysis tech-
niques, recursion, and sorting. Part I11 contains a host of applications that
use the STL's data structures. Implementation of the STL is not shown until
Part IV, once the data structures have already been used. Because the STL is
part of C++ (older compilers can use the textbook's STL code instead-see
Code Availability, xxix), students can design large projects early on, using
existing software components.
Despite the central use of the STL in this text, it is neither a book on the
STL nor a primer on implementing the STL specifically; it remains a book
that emphasizes data structures and basic problem-solving techniques. Of
course, the general techniques used in the design of data structures are appli-
cable to the implementation of the STL, so several chapters in Part IV
include STL implementations. However, instructors can choose the simpler
implementations in Part IV that do not discuss the STL protocol. Chapter 7,
which presents the STL, is essential to understanding the code in Part 111. I
attempted to use only the basic parts of the STL.
Many instructors will prefer a more traditional approach in which each
data structure is defined, implemented, and then used. Because there is no
dependency between material in Parts I11 and IV, a traditional course can
easily be taught from this book. Prerequisites
Students using this book should have knowledge of either an object-oriented
or procedural programming language. Knowledge of basic features, includ-
ing primitive data types, operators, control structures, functions (methods),
and input and output (but not necessarily arrays and classes) is assumed.
Students who have taken a first course using C++ or Java may find the
first two chapters "light" reading in some places. However, other parts are
definitely "heavy" with C++ details that may not have been covered in intro-
ductory courses.
Students who have had a first course in another language should begin at
Chapter 1 and proceed slowly. They also should consult Appendix A which
discusses some language issues that are somewhat C++ specific. If a student
would like also to use a C++ reference book, some recommendations are
given in Chapter 1, pages 38-39.
Knowledge of discrete math is helpful but is not an absolute prerequi-
site. Several mathematical proofs are presented, but the more complex
proofs are preceded by a brief math review. Chapters 8 and 19-24 require
some degree of mathematical sophistication. The instructor may easily elect
to skip mathematical aspects of the proofs by presenting only the results. All
proofs in the text are clearly marked and are separate from the body of the
text.
Summary of Changes in the Second Edition
1. Much of Part I was rewritten. In Chapter 1, primitive arrays are no
longer presented (a discussion of them was moved to Appendix D);
vectors are used instead, and push-back is introduced. Pointers
appear later in this edition than in the first edition. In Chapter 2,
material was significantly rearranged and simplified. Chapter 3 has
additional material on templates. In Chapter 4, the discussion on
inheritance was rewritten to simplify the initial presentation. The
end of the chapter contains the more esoteric C++ details that are
important for advanced uses.
2. An additional chapter on design patterns was added in Part I. Sev-
eral object-based patterns, including Functor, Wrapper, and Iterator,
are described, and patterns that make use of inheritance. including
Observer, are discussed.
3. The Data Structures chapter in Part I1 was rewritten with the STL in
mind. Both generic interfaces (as in the first edition) and STL inter-
faces are illustrated in the revised Chapter 7. 4. The code in Part I11 is based on the STL. In several places, the code
is more object-oriented than before. The Huffman coding example
is completely coded.
5. In Part IV, generic data structures were rewritten to be much sim-
pler and cleaner. Additionally, as appropriate, a simplified STL
implementation is illustrated at the end of the chapters in Part IV.
lmplemented components include vector, 1 is t, stack, queue,
set, map, priority-queue, and various function objects and
algorithms.
Using C++ presents both advantages and disadvantages. The C++ class
allows the separation of interface and implementation, as well as the hid-
ing of internal details of the implementation. It cleanly supports the notion
of abstraction. The advantage of C++ is that it is widely used in industry.
Students perceive that the material they are learning is practical and will
help them find employment, which provides motivation to persevere
through the course. One disadvantage of C++ is that it is far from a perfect
language pedagogically, especially in a second course, and thus additional
care needs to be expended to avoid bad programming practices. A second
disadvantage is that C++ is still not a stable language, so the various com-
pilers behave differently.
It might have been preferable to write the book in a language-indepen-
dent fashion, concentrating only on general principles such as the theory of
the data structures and referring to C++ code only in passing, but that is
impossible. C++ code is complex, and students will need to see complete
examples to understand some of its finer points. As mentioned earlier, a brief
review of parts of C++ is provided in Appendix A. Part I of the book
describes some of C++'s more advanced features relevant to data structures.
Several parts of the language stand out as requiring special consider-
ation: templates, inheritance, exceptions, namespaces and other recent C++
additions, and the Standard Library. 1 approached this material in the follow-
ing manner.
Templates: Templates are used extensively. Some instructors may
have reservations with this approach because it complicates the code,
but I included them because they are fundamental concepts in any
sophisticated C++ program.
I~zheritance: I use inheritance relatively sparingly because it adds
complications, and data structures are not a strong application area -- --
Preface
for it, This edition contains less use of inheritance than in the previ-
ous edition. However, there is a chapter on inheritance, and part of the
design patterns chapter touches on inheritance-based patterns. For the
most part, instructors who are eager to avoid inheritance can do so,
and those who want to discuss inheritance will find sufficient material
in the text.
Exceptions: Exception semantics have been standardized and
exceptions seem to work on many compilers. However, exceptions
in C++ involve ugly code, significant complications (e.g., if used in
conjunction with templates), and probably require discussing inher-
itance. So I use them sparingly in this text. A brief discussion of
exceptions is provided, and in some places exceptions are thrown in
code when warranted. However, I generally do not attempt to catch
exceptions in any Part I11 code (most of the Standard Library does
not attempt to throw exceptions).
Namespaces: Namespaces, which are a recent addition to C++, do not
work correctly on a large variety of compilers. I do not attempt to use
namespaces and I import the entire std namespace when necessary
(even though not great style, it works on the largest number of com-
pilers). Appendix A discusses the namespace issues.
Recent language additions: The boo1 data type is used throughout.
The new static-cas t operator is used in preference to the old-style
cast. Finally, I use explicit when appropriate. For the most part,
other additions are not used (e.g., I generally avoid using typename).
Standard Library: As previously mentioned, the STL is used through-
out, and a safe version (that does extra bounds checking) is available
online (and implemented in Part IV). We also use the string class
and the newer istringstream class that are part of the standard
library.
Text Organization
In this text I introduce C++ and object-oriented programming (particularly
abstraction) in Part I. I discuss arrays, pointers and some other C++ topics
and then go on to discuss the syntax and use of classes, templates, and inher-
itance. The material in these chapters was substantially rewritten. New to
this edition is an entire chapter on design patterns.
In Part I1 I discuss Big-Oh and algorithmic paradigms, including recur-
sion and randomization. An entire chapter is devoted to sorting, and a sepa-
rate chapter contains a description of basic data structures. I use the STL in
presenting the interfaces and running times of the data structures. At this Preface
point in the text, the instructor may take several approaches to present the
remaining material, including the following two.
I. Discuss the corresponding implementations (either the STL ver-
sions or the simpler versions) in Part IV as each data structure is
described. The instructor can ask students to extend the classes in
various ways, as suggested in the exercises.
2. Show how the STL class is used and cover implementation at a later
point in the course. The case studies in Part 111 can be used to sup-
port this approach. As complete implementations are available on
every modern C++ compiler (or on the Internet for older compil-
ers). the instructor can use the STL in programming projects.
Details on using this approach are given shortly.
Part V describes advanced data structures such as splay trees, pairing
heaps, and the disjoint set data structure, which can be covered if time per-
mits or, more likely, in a follow-up course.
Chapter-by-Chapter Text Organization
Part I consists of ti ve chapters that describe some advanced features of C++
used throughout the text. Chapter I describes arrays, strings, pointers, refer-
ences, and structures. Chapter 2 begins the discussion of object-oriented pro-
gramming by describing the class mechanism in C++. Chapter 3 continues
this discussion by examining templates, and Chapter 4 illustrates the use of
inheritance. Several components, including strings and vectors, are written
in these chapters. Chapter 5 discusses some basic design patterns, focusing
mostly on object-based patterns such as function objects, wrappers and
adapters, iterators, and pairs. Some of these patterns (most notably the wrap-
per pattern) are used later in the text.
Part IT focuses on the basic algorithms and building blocks. In Chapter 6
a complete discussion of time complexity and Big-Oh notation is provided,
and binary search is also discussed and analyzed. Chapter 7 is crucial
because it covers the STL and argues intuitively what the running time of the
supported operations should be for each data structure. (The implementation
of these data structures. in both STL-style and a simplified version, is not
provided until Part IV. The STL is available on recent compilers.) Chapter 8
describes recursion by ti rst introducing the notion of proof by induction. It
also discusses divide-and-conquer, dynamic programming, and backtrack-
ing. A section describes several recursive numerical algorithms that are used
to implement the RSA cryptosystem. For many students, the material in the second half of Chapter 8 is more suitable for a follow-up course. Chapter 9
describes. codes, and analyzes several basic sorting algorithms, including
the insertion sort, Shellsort, mergesort, and quicksort, as well as indirect
sorting. It also proves the classic lower bound for sorting and discusses the
related problems of selection. Finally, Chapter 10 is a short chapter that dis-
cusses random numbers, including their generation and use in randomized
algorithms.
Part 111 provides several case studies, and each chapter is organized
around a general theme. Chapter I I illustrates several important techniques
by examining games. Chapter 12 discusses the use of stacks in computer
languages by examining an algorithm to check for balanced symbols and the
classic operator precedence parsing algorithm. Complete implementations
with code are provided for both algorithms. Chapter 13 discusses the basic
utilities of file compression and cross-reference generation, and provides a
complete implementation of both. Chapter 14 broadly examines simulation
by looking at one problem that can be viewed as a simulation and then at the
more classic event-driven simulation. Finally, Chapter 15 illustrates how
data structures are used to implement several shortest path algorithms effi-
ciently for graphs.
Part IV presents the data structure implementations. Implementations
that use simple protocols (insert, find, remove variations) are provided.
In some cases, STL implementations that tend to use more complicated C++
syntax are presented. Some mathematics is used in this part, especially in
Chapters 19-2 1, and can be skipped at the discretion of the instructor. Chap-
ter 16 provides implementations for both stacks and queues. First these data
structures are implemented using an expanding array; then they are imple-
mented using linked lists. The STL versions are discussed at the end of the
chapter. General linked lists are described in Chapter 17. Singly linked lists
are illustrated with a simple protocol, and the more complex STL version
that uses doubly linked lists is provided at the end of the chapter. Chapter 18
describes trees and illustrates the basic traversal schemes. Chapter 19 is a
detailed chapter that provides several implementations of binary search
trees. Initially, the basic binary search tree is shown, and then a binary
search tree that supports order statistics is derived. AVL trees are discussed
but not implemented; however, the more practical red-black trees and AA-
trees are implemented. Then the STL set and map are implemented.
Finally, the B-tree is examined. Chapter 20 discusses hash tables and imple-
ments the quadratic probing scheme, after examination of a simpler alterna-
tive. Chapter 21 describes the binary heap and examines heapsort and
external sorting. The STL pr iority-queue is implemented in this chapter.
Part Chapter V contains material suitable for use in a more advanced
course or for general reference. The algorithms are accessible even at the first-year level; however, for completeness sophisticated mathematical anal-
yses were included that are almost certainly beyond the reach of a first-year
student. Chapter 22 describes the splay tree, which is a binary search tree
that seems to perform extremely well in practice and is also competitive with
the binary heap in some applications that require priority queues. Chapter 23
describes priority queues that support merging operations and provides an
implementation of the pairing heap. Finally, Chapter 24 examines the classic
disjoint set data structure.
The appendices contain additional C++ reference material. Appendix A
describes tricky C++ issues, including some unusual operators, 110, and
recent language changes. Appendix B lists the operators and their prece-
dence. Appendix C summarizes some C++ libraries. Appendix D describes
primitive arrays and strings for those who want details of what is going on
under the hood of the vector and string classes.
Chapter Dependencies
Generally speaking, most chapters are independent of each other. However,
the following are some of the notable dependencies.
Part I: The first three chapters should be covered in their entirety first. I
recommend a brief discussion of inheritance in Chapter 4. Some instruc-
tors will want to cover all of inheritance, but it is possible to get by with
just the basics of inheritance and avoid some of the more difficult C++
issues that inheritance involves. Some of the object-based patterns (e.g.,
wrappers and function objects) in Chapter 5 can be discussed shortly
after templates, or later in the course as the need arises. Some of these
patterns are used in the chapter on sorting and in Part IV.
Chapter 6 (Algorithm Analysis): This chapter should be covered prior
to Chapters 7 and 9. Recursion (Chapter 8) can be covered prior to
this chapter, but the instructor will have to gloss over some details
about avoiding inefficient recursion.
Chapter 7 (STL): This chapter can be covered prior to, or in conjunc-
tion with, material in Part 111 or IV.
Chapter 8 (Recursion): The material in Sections 8.1-8.3 should be
covered prior to discussing recursive sorting algorithms, trees, the tic-
tac-toe case study, and shortest-path algorithms. Material such as the
RSA cryptosystem, dynamic programming, and backtracking (unless
tic-tac-toe is discussed) is otherwise optional.
Chapter 9 (Sorting): This chapter should follow Chapters 6 and 8.
However, it is possible to cover Shellsort without Chapters 6 and 8. Shellsort is not recursive (hence there is no need for Chapter 8), and a
rigorous analysis of its running time is too complex and is not cov-
ered in the book (hence there is little need for Chapter 6).
Chapters 16 and 17 (Stacks/Queues/Lists): These chapters may be
covered in either order. However, I prefer to cover Chapter 16 first,
because I believe that it presents a simpler example of linked lists.
Chapters 18 and 19 (TreesBearch trees): These chapters can be cov-
ered in either order or simultaneously.
Separate Entities
The other chapters have little or no dependencies:
Chapter 10 (Randomization): The material on random numbers can
be covered at any point as needed.
Part III (Case Studies): Chapters 11-15 can be covered in conjunction
with, or after, the STL (in Chapter 7), and in roughly any order. There
are a few references to earlier chapters. These include Section 1 1.2 (tic-
tac-toe), which references a discussion in Section 8.7, and Section 13.2
(cross-reference generation), which references similar lexical analysis
code in Section 12.1 (balanced symbol checking).
CIzapters 20 and 21 (Hashing/Priority Queues): These chapters can
be covered at any point.
Part V (Advanced Data Structures): The material in Chapters 22-24
is self-contained and is typically covered in a follow-up course.
Mathematics
I have attempted to provide mathematical rigor for use in CS-2 courses that
emphasize theory and for follow-up courses that require more analysis.
However, this material stands out from the main text in the form of separate
theorems and, in some cases, separate sections (or subsections). Thus it can
be skipped by instructors in courses that deemphasize theory.
In all cases, the proof of a theorem is not necessary to the understanding
of the theorem's meaning. This is another illustration of the separation of an
interface (the theorem statement) from its implementation (the proof). Some
inherently mathematical material, such as Section 8.4 (Numerical Applica-
tions of Recursion), can be skipped without affecting comprehension of the
rest of the chapter.
...展开详情收缩