图书前言

preface

Thi, book is designed for a two-semester sequence in computer science,

beginning with what is typically known as Data Structures and continuing

with advanced data structures and algorithm analysis. It is appropriate for the

courses from both the two-course and three-course sequences in "B.l 

intfOductory Tracks:' as outlined in the final report of the Computing Curricula

y Yracks:' as outlined in the final report of the Computing Curricula

2001 project (CC2001)--a joint undertaking of the ACM and the IEEE.

The content of the Data Structures course has been evolving for some

time. Although there is some general consensus concerning topic coverage,

considerable disagreement still exists over the details. One uniformly

accented topic is principles of software development, most notably the 

conpted topic is principles of software development, most notably the 

concepts of encapsulation and information hiding. Algorithmically, all Data

Structures courses tend to include an intfoduction to running-time analysis,

.,..,.,,,, 1 x.

recursion, basic sorting algorithms, and elementary data structures. Many 

universities offer an advanced course that covers topics in data strictures, 

algopics in data strictures, 

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 purchase a second textbook.

Although the most passionate debates in Data Structures revolve around

the choice of a programming language, other fundamental choices need to be

made:

. Whether to introduce object-oriented design or object-based

design early

. The level of mathematical rigor

5

-'

Iv preface

. The appropriate balance between the implementation of data 

stmcppropriate balance between the implementation of data 

stack

tures and their use

.

. Programming details related to the language chosen (for instance,

.ramming details related to the language chosen (for instance,

,,,

should GUIs be used earlV)

J )

My goal in writing this text was to provide a practical introduction to data

y goal in writing this text was to provide a practical introduction to data

.

structures and algorithms from the viewpoint of abstract thinking and 

probe point of abstract thinking and 

problem solving. I tried to cover all the important details concerning the data

e. i tried to cover all the important details concerning the data

-. 

structures, their analyses, and their Java implementations, while staying away

from data structures that are theoretically interesting but not widely used. It is

y Interesting but not widely used. It is

..,,, 1,

impossible to cover all the different data structures, including their uses and

the analVsis, described in this text in a single course. So I designed the 

texts .is, described in this text in a single course. So I designed the 

textbook to allow instructors flexibilitV in topic coverage. The instructor will need

J in topic coverage. The instructor will need

.

to decide on an appropriate balance between practice and theory and then

'

choose the topics that best fit the course. As I discuss later in this Preface, I

.,

organized the text to minimize dependencies among the various chapters.

.anned the text to minimize dependencies among the various chapters.

summary of chanqes

y of changes

- - - - - - - - - 

in the fourth edition

1. This edition provides additional discussion on using classes (Chapter 2),

..

wntinZ classes (ChaDter 3), and interfaces (Chapter 4).

o

ry

2. Chapter 6 contains additional material discussing the running time of

lists, the use of maps, and the use of views in the Java Collections API.

3. The Scanner class is described, and code throughout the text makes use

n

of the Scanner class.

4. Chapter 9 describes and implements the 48-bit linear congruential 

gener.

ator that is part of both the Java and many C++ libraries.

5. Chapter 20 has new material on separate chaining hash tables and the

t parate chaining hash tables and the

Sin na hashCode method.

Jtri ng hashCode method.

6. There are numerous revisions to the text that improve on the prose in the

.,..

previous edition.

7. Many new exercises are provided in Parts i. 11. and tV

j flew exercises are provided in Parts i, II, and tV

~ -. ~ = - I

a unique approach

me approach

My basic Dremise is that software develoDment tools in all languages come with

j Dasic 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

e, and many data structUres are part of these libraries. I envision an

'

eventual shift in emDhasis of data structures courses from imDlementation to

phasis of data structures courses from implementation to

preface v

use. In this book I tabs a unique approach by separating the data structures into

their sDecincation and subseQuent implementation and taking advantage of an

pecification and subsequent implementation and taking advantage of an

already existing data structures library, the Java Collections API.

J existing data structures library, the Java Collections API.

A subset of the Collections API suitable for most applications is discussed

.., 1

in a single chapter (Chapter 6) in Part Two. Part TWo also covers basic 

analyble chapter (Chapter 6) in Part Two. Part TWo also covers basic 

analysis techniques, recursion, and sorting. Part Three contains a host of 

applica.'

nons that use the Collections API's data structures. Implementation of the

Collections API is not shown until Paft Four, once the data structures have

already been used. Because the Collections API is Dart of Java, students can

j paft of Java, students can

design large projects early on, using existing software components.

Despite the central use of the Collections API in this text, it is neither a book

pite the central use of the Collections API in this text, it is neither a book

on the Collections API nor a primer on implementing the Collections API 

specificallV; it remains a book that emphasizes data structures and basic 

problems, it remains a book that emphasizes data structures and basic 

problemsolving techniques. Of course, the general techniques used in the design of data

-. -,'. -.

structures are applicable to the implementation of the Collections API, so 

several chapters in Part FOur include Collections API implementations. Howevef,

instructors can choose the simpler implementations in Part Four that do not 

discuss the Collections API protocol. Chapter 6, which presents the Collections

API, is essential to understanding the code in Pat Three. I attempted to use only

the basic parts of the Collections API.

Many instructors will Drefer a more traditional approach in which each

y 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 Three and Four, a traditional course can

easily be taught from this book.

j .nt from this book.

- - 

prerequisites

Students using this book should have knowledge of either an object-oriented

or procedural programming language. Knowledge of basic features, including

... 

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

four chapters "light" reading in some places. Howevef, other parts are definitely

"heavV" with Java details that may not have been covered in intfoductory courses.

J with Java details that may not have been covered in introductory courses.

Students who have had a first course in another language should begin at

Chapter 1 and proceed slowly. If a student would like to use a Java reference

book as well, some recommendations are given in Chapter 1.

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 7 and 19--24 require

-'

yi preface

t t.

some degree of mathematical sophistication. The instructor may easily elect

arse of mathematical sophistication. The instructor may easily elect

to skip mathematical aspects of the proofs by presenting only the results.

p 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.

java

ac.

fbis textbook presents material using the Java programming language. Java

.,

is a language that is often examined in comparison with C++. Java offers

auage that is often examined in comparison with C++. Java offers

,

manV benents. and Drogrammers often view Java as a safef, more portable,

J, and programmers often view Java as a safer, more portable,

,.,

and easiento-use language than C++.

guage than C++.

ac r T', 'q wory,,iwos

Yhe use of Java requires that some decisions be made when writing a 

textbook. Some of the decisions made are as follows:

1. The minimum required comDiler is Java S. Please make sure Von are

4mred compiler is Java S. Please make sure you are

..,

using a compiler that is Java 5-compatible.

a a compiler that is Java 5-compatible.

ry

2. GUIs are not emphasized. Although GUIs are a nice feature in Java,

phasized. Although GUIs are a nice feature in Java,

.

theV seem to be an implementation detail rather than a core Data

J deem to be an implementation detail rather than a core Data

Rtmctures toDic. We do not use Swing in the text, but because man\'

strictures topic. We do not use Swing in the text, but because many

.

instructors maV Prefer to do so, a brief introduction to Swing is 

proy prefer to do so, a brief introduction to Swing is 

pro.,,.',. n

vided in Appendix B. 

ppendix B.

3. APPlets are not emphasized. Applets use GUIs. Furthef, the focus of

the course is on data stttictllres, rather than language features. 

Instruc.

tors who would like to discuss applets will need to supplement this

.'

text with a Java reference.

4. Inner classes are used. Inner classes are used primarily in the 

imple.

mentation of the Collections API, and can be avoided by instructors

, aam

who prefer to do so.

prefer to do so.

5. The conceDt of a pointer is discussed when reference variables are

pt Of a pointer is discussed when reference variables are

.', T'

introduced. Java does not have a pointer type. Instead, it has a 

reference tVPe. However, Dointers have traditionallV been an imDortant

ype. However, pointers have traditionally been an important

Data Structures topic that needs to be introduced. I illustrate the

concept of pointers in other languages when discussing reference

pt of pointers in other languages when discussing reference

.,,

vanables.

6. Threads are not discussed. Some members of the CS community

argue that multithreaded computing should become a core topic in the

. I

introductorV programming sequence. Although it is possible that this

y programming sequence. Although it is possible that this

., 1,., ac

will happen in the future, few introductory programming courses 

dis-. -.

cuss this difficult topic.

pie.

preface vii

7. Some Java 5 features are not used. Including f

. Static imports, not used because in my opinion it actually makes

ports, not used because in my opinion it actually makes

the code harder to read.

. Enumefated tVves. not used because there were few "laces to

ypes, not used because there were few places to

declare public enumerated types that would be usable by clients. In

the few possible places, it did not seem to help the code's readability.

teXt organization

In this text I introduce Java and object-oriented programming (particularly

,ect-onented programming (particularly

abstraction) in Part One. I discuss primitive types, reference types, and some

of the predefined classes and exceptions before proceeding to the design of

classes and inheritance.

In Part Two, I discuss Big-Oh and algorithmic paradigms, including

.,,..'.,.,

recursion and randomization. An entire chapter is devoted to sorting, and a

separate chapter contains a description of basic data stmctures. I use the 

Collections API to present the interfaces and running times of the data structures.

At this point in the text, the instrUctor may take several approaches to present

t' Lhe instrUctor may take several approaches to present

the remaining material, including the following two.

1. Discuss the corresponding implementations (either the Collections

API versions or the simpler versions) in Part Four as each data 

strucpler versions) in Part Four as each data 

structure is described. The instructor can ask students to extend the classes

.. -.

in various waVs, as suggested in the exercises.

J a, as suggested in the exercises.

2. Show how each Collections API class is used and cover 

implementation at a later point in the course. The case studies in Part Three can

point in the course. The case studies in Part Three can

be used to support this approach. As complete implementations are

available on every modem Java compilef, the instructor can use the

Collections API in programming projects. Details on using this

,.,,

approach are given shortly.

Part Five describes advanced data structures such as splay trees, pairing

heaps, and the disjoint set data structure, which can be covered if time permits

,. 1,. n 1 1

or, more likely, in a follow-up course.

chapter-by-chapter teXt organization

Part One consists of four chapters that describe the basics of Java used

throughout the text. Chapter I describes primitive types and illustrates how to

write basic programs in Java. Chapter 2 discusses reference types and illustrates

- - -'

vill preface

the general concept of a pointer-yen though Java does not have pointers--so

that students learn this important Data Structures topic. Several of the basic

reference tVves (strings, arrays, files, and Scanners) are illustrated, and the use

J pos (strings, arrays, files, and Scanners) are illustrated, and the use

of exceptions is discussed. Chapter 3 continues this discussion by describing

how a class is implemented. Chapter 4 illustrates the use of inheritance in

designing hierarchies (including exception classes and I/O) and generic 

components. Material on design patterns, including the wrappef, adapter, and 

decI

orator Dattems can be found in Pat One.

patterns can be found in Pat One.

Part Two focuses on the basic algorithms and building blocks. In

Chapter 5 a complete discussion of time complexity and Big-Oh notation

.., 1 n.,.,,., 1,,

is provided. Binary search is also discussed and analyzed. Chapter 6 is

.',.,

crucial because it covers the Collections API and argues intuitively what

the running time of the supported operations should be for each data 

struck Lime of the supported operations should be for each data 

structure. (The implementation of these data structures, in both Collections

API-stVle and a simDlined version. is not Drovided until Part Four). This

ale and a simplified version, is not provided until Part Four). This

, 1.'

chapter also introduces the iterator pattern as well as nested, local, and

, r, 1 n,. 1 o.

anonVmous classes. Inner classes are deferred until Part Four, where theV

Jmous classes. Inner classes are deferred until Part Four, where they

,.,. 1. 1.

are discussed as an implementation technique. Chapter 7 describes 

recur.,

sion bV first introducing the notion of proof by induction. It also discusses

Y nrst introducing the notion of proof by induction. It also discusses

divide-and-conquer, dynamic programming, and backtracking. A section

describes several recursive numerical algorithms that are used to 

impleI

ment the RSA crvptosvstem. For many students, the material in the second

Jptosystem. For many students, the material in the second

half of Chapter 7 is more suitable for a follow-up course. Chapter 8

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

b. It also proves the classic lower bound for sorting and discusses the

1 1', rt,. ~. 11

related problems of selection. Finally, Chapter 9 is a short chapter that 

dis,,.,,.,..,. 1. 1

cusses random numbers, including their generation and use in randomized

,.,

algorithms.

aorithms.

Part Three provides several case studies, and each chapter is organized

, 1,

around a general theme. Chapter 10 illustrates several important techniques

e pier 10 illustrates several important techniques

by examining games. Chapter I I discusses the use of stacks in computer 

fan; e games. Chapter I I discusses the use of stacks in computer 

fan,..,.',, r,,,',,,

guages by examining an algorithm to check for balanced symbols and the

,.,.,. 1

classic oDerator Drecedence marsing algorithm. Complete implementations

perator precedence parsing algorithm. Complete implementations

. I

with code are provided for both algorithms. Chapter 12 discusses the basic

provided for both algorithms. Chapter 12 discusses the basic

..

utilities of file compression and cross-reference generation, and provides a

,.,.

complete implementation of both. Chapter 13 broadly examines simulation by

looking at one problem that can be viewed as a simulation and then at the

,.,..,. ~., 1

more classic event-driven simulation. FinallV, Chapter 14 illustrates how data

J, pier 14 illustrates how data

preface ix

-. 

structures are used to implement several shortest path algorithms efficiently

for graphs.

.raphs.

Paft Four presents the data structure implementations. Chapter 15 

dispresents the data structure implementations. Chapter 15 

dis.,.,.'.,., 1

cusses inner classes as an implementation technique and illustrates their use

in the ArrayList implementation. In the remaining chapters of Part Four,

. 1.,.,,

implementations that use simple protocols (insert, find, remove variations)

are provided. In some cases, Collections API implementations that tend to

'.

use more complicated Java sVntax (in addition to being complex because of

plicated Java syntax (in addition to being complex because of

their large set of required operations) are presented. Some mathematics is

used in this part, esneciallV in Chapters 19--21, and can be skipped at the 

dispart, especially in Chapters 19--21, and can be skipped at the 

discretion of the instructor. Chapter 16 provides implementations for both

stacks and queues. First these data structures are implemented using an

expanding array, then they are implemented using linked lists. The 

Collections API 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 Collections API 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 binarV search tree is shown, and then a binary search tree that supports

y .earch tree is shown, and then a binary search tree that suppofts

order statistics is derived. AVL trees are discussed but not implemented, but

the more practical red--black trees and AA-trees are implemented. Then the

Collections API TreeSet and TreeMap are implemented. Finally, the B-tree is

.'

examined. Chapter 20 discusses hash tables and implements the quadratic

probing scheme as part of HashSet and HashMap, after examination of a simpler

alternative. Chapter ZI describes the binary heap and examines heapsort and

external softing.

Part Five contains material suitable for use in a more advanced course or for

general reference. The algorithms are accessible even at the first-year level.

Howevef, for completeness, sophisticated mathematical analyses that are almost

certainly beyond the reach of a first-year student were included. Chapter 22

describes the snlaV tree, which is a binary search tree that seems to perform

play tree, which is a binary search tree that seems to perform

extremelV well in practice and is competitive with the binary heap in some

J bell in practice and is 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 Java reference material. Appendix A

lists the operators and their precedence. Appendix B has material on Swing,

and Appendix C describes the bitwise operators used in Chapter 12.

x preface

- - - - 

chapter dependencies

Generally sDedeng, most chapters are independent of each other However

y apecing, most chapters are independent of each other Howevef,

the following are some of the notable dependencies.

e are some of the notable dependencies.

. Part One (Tour of java): The first four chapters should be covered in their

..

entAnty in seouence first, boor tO continuing on to the rest of the tCXt.

y in sequence first, Prior tO continuing on to the rest of the tCXt.

. ChaDter 5 (Algorithm Analysis): This chapter should be covered prior

pier 5 (Algorithm Analysis): This chapter should be covered prior

to Chapters 6 and 8. Recursion (Chapter 7) can be covered prior to

I

-.

this chaptef, but the instructor will have to gloss over some details

.

,.'..

about avoiding inefficient recursion.

b Inefficient recursion.

. ChaDter 6 (The Collections APe: This chapter can be covered prior to

pier 6 (The Collections APe: This chapter can be covered prior to

.....

or in conlunction with material in Part Three or FouL

J

. ChaDter 7 (Recursion): The material in Sections 7.l--7.3 should be

pier 7 (Recursion): The material in Sections 7.l--7.3 should be

1.

covered prior to discussing recursive sorting algorithms, trees, the

.

ac ac m

nc-Tao-TOe case study, and shortest-path algorithms. Material such

J, and shortest-path algorithms. Material such

as the RSA crVDtosVstem, dVnamic Drogramming, and backtracking

Jptosystem, dynamic programming, and backtracking

(unless Tie-Tao-TOe is discussed) is otherwise optional.

. ChaDter 8 (Sorting Algorithms): This chapter should follow Chapters

pier 8 (Sorting Algorithms): This chapter should follow Chapters

5 and 7. Howevef, it is possible to cover Shellsort without Chapters 5

'

1 - R' '1..

and 7. Shellsort is not recursive (hence there is no need for Chapter 7),

and a rigorous analysis of its running time is too complex and is not

borons analysis of its running time is too complex and is not

,.,,,

covered in the book (hence there is little need for Chapter 5).

. ChaDter 15 (Inner Classes and Implementations of ArraVLists):

pier 15 (Inner Classes and Implementations of ArrayLists):

This material should precede the discussion of the Collections API

.,.

implementations.

. ChaDters 16 and 17 (Stacks and Oueues/Linked Lists): These chanters

piers 16 and 17 (Stacks and Queues/Linked Lists): These chapters

,,..' 1 T T x ac

may be covered in either order However, I prefer to cover Chanter 16

y be covered in either order However, I prefer to cover Chapter 16

nrst because I believe that it presents a similer examDle of linked lists.

presents a simpler example of linked lists.

. ChaDters 18 and 19 (Trees/Binary Search Trees): These chapters can

piers 18 and 19 (Trees/Binary Search Trees): These chapters can

be covered in either order or simultaneouslV'

J.

- - - - 

separate entities

ac,

she other chapters have little or no dependencies:

.

. ChaDter 9 (Randomization): The material on random numbers can be

pier 9 (Randomization): The material on random numbers can be

1.,,

covered at anV joint as needed.

J point as needed.

preface xi

. Part Three (APPlications): Chapters 10--14 can be covered in 

con... t ac

Junction with or after the Collections API (in Chapter 6) and in

roughly any order. There are a few references to earlier chapters.

These include Section 10.2 (Tie-Tao-Toe), which refers to a 

discus..

sion in Section 7.7, and Section 12.2 (cross-reference generation),

which refers to similar lexical analysis code in Section 1 1. 1 (balanced

symbol checking).

. ChaDters 20 and 21 (Hash Tables/A Priority Queue): These chapters

piers 20 and 21 (Hash Tables/A Priority Queue): These chapters

can be covered at any point.

J point.

. Part Five (Advanced Data Structures): The material in Chapters

22--24 is self-contained and is tVDicallv covered in a follow-uD course.

yplcally covered in a follow-up course.

mathematiI have attempted to provide mathematical rigor for use in Data Structures

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

yDls. Howevef, 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 instmctors 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 7.4 (Numerical 

APPlicaJ mathematical material, such as Section 7.4 (Numerical 

APPlications of Recursion), can be skipped without affecting comprehension of the

rest of the chapteL

t

- - 

course organization

A crucial issue in teaching the course is deciding how the materials in Parts

Twedour are to be used. The material in Part One should be covered in

depth, and the student should write one or two programs that illustrate the

design, implementation, testing of classes and generic classes, and perhaps

object-oriented design, using inheritance. Chapter 5 discusses Big-Oh 

notation. An exercise in which the student writes a short program and compares

the running time with an analysis can be given to test comprehension.

In the separation approach, the key concept of Chapter 6 is that different

data structures support different access schemes with different efficiency. Any

case studV (exceDt the Tie-Tao-Toe examDle that uses recursion) can be used

y (except the Tie-Tao-Toe example that uses recursion) can be used

- -'

Xll preface

.,

to illustrate the applications of the data structures. In this way, the student can

see the data structure and how it is used but not how it is efficiently 

imDleJ 

impleI

mented. This is trulV a separation. Viewing things this way will greatly

J a separation. Viewing things this way will greatly

'',.,.

enhance the ability of students to think abstractlV' Students can also provide

j J. students can also provide

.,.,.

simple implementations of some of the Collections API components (some

...

suggestions are given in the exercises in Chapter 6) and see the difference

.gestions are given in the exercises in Chapter 6) and see the difference

between efficient data structure implementations in the existing Collections

API and inefficient data structure imDlementations that theV will write. 

Stuplementations that they will write. 

Students can also be asked to extend the case studV, but again, they are not

J, DUt again, they are not

.', n.

required to know any of the details of the data structures.

Efficient implementation of the data structures can be discussed afted

',. 1.

ward, and recursion can be introduced whenever the instructor feels it is

..,,...

appropnate, provided it is prior to binary search trees. The details of sorting

,,.,.

can be discussed at anV time after recursion. At this joint, the course can 

cone time after recursion. At this point, the course can 

con. -. 

tinue bV using the same case studies and experimenting with modincations to

j b penmenting with modifications to

the implementations of the data structures. For instance, the student can

plementations of the data structures. For instance, the student can

..,

experiment with various forms of balanced binarV search trees.

penment with various forms of balanced binary search trees.

Instructors who opt for a more traditional approach can simply discuss a

case study in Part Three after discussing a data structure implementation in

J in Part Three after discussing a data structure implementation in

Part FouL Again, the book's chapters are designed to be as independent of

&am, the book's chapters are designed to be as independent of

'

each other as possible.

exercISes

~...

-exercises come in vanous navors; i nave provided tour varieties. me basic in

Short exercise asks a simple question or requires hand-drawn simulations of an

,..

algorithm described in the text. The in Theory section asks questions that either

a y section asks questions that either

..

require mathematical analVsis or asks for theoretically interesting solutions to

quire mathematical analysis or asks for theoretically interesting solutions to

,, al x n....,..

problems. The in Practice section contains simple programming questions,

.',..,.',., 1.

including questions about syntax or particularly tricky lines of code. Finally,

e questions about syntax or particularly tricky lines of code. Finally,

.

the Progmmming Projects section contains ideas for extended assignments.

- - - - 

pedagogical features

. Margin notes are used to highlight important topics.

.in notes are used to highlight important topics.

k. The Key COncepts section lists important terms along with definitions

and page references.

preface xiii

. The Common Errors section at the end of each chapter provides a list the

aam

of commonlV made errors. @

J made errors. @

. References for further reading are provided at the end of most chapters. k

W

supplementS

A variety of supplemental materials are available for this text. The following

y of supplemental materials are available for this text. The following

., 1 1

resources are available at http: //www. aw. corn/cssupport for all readers of this

textbooks

. Source code mes from the book. (The On the internet section at the ac

J' .aam

end of each chapter lists the filenames for the chapter's code.) j u

In addition, the following supplements are available to qualified instructors.

TO access them, visit http: //www. pearsonhi ghered. corn/cs and search our 

catalog by title for Data Structures and Problem SOlving Using Java. Once on the 

catalog page for this book, select the link to instructor Resources.

. POwerpoint slides of all figures in the book.

gures in the book.

. Instructor's Guide that illustrates several approaches to the material.

pproaches to the material.

It includes samples of test questions, assignments, and syllabi.

Answers to select exercises are also provided.

acknowledgmentS

Many, many people have helped me in the preparation of this book. Many

y, many people have helped me in the preparation of this book. Many

have alreadV been acknowledged in the prior edition and the related C++ 

verb .cd in the prior edition and the related C++ 

ver.

sion. Others, too numerous to list, have sent e-mail messages and pointed out

.... -.' 

errors or inconsistencies in explanations that I have tried to fix in this edition.

planations that I have tried to fix in this edition.

For this edition I would like to thank my editor Michael Hirsch, editorial

assistant Stephanie Sellinger, senior production supervisor Marilyn Lloyd,

phanie Sellinger, senior production supervisor Marilyn Lloyd,

and project manager Rebecca Lazure and her team at Laserwords. Thanks

also go to Allison Michael and Erin Davis in marketing and Elena Sidorova

and Suzanne Heiser of Night & Day Design for a terrific cover.

Some of the material in this text is adapted from my textbook Effcient C

Programming: A Practical APPmach (Prentice Hall, 1995) and is used with

-'

xlv preface

..

penmssion of the published I have included end-of-chapter references where

appropriate.

My WOrld Wide Web page, http: //www. cs. fi u. edu/~wei ss, will contain

updated source code, an errata list, and a link for receiving bug reports.

M. A. W

Miami, Florida