第1页 / 共714页
第2页 / 共714页
第3页 / 共714页
第4页 / 共714页
第5页 / 共714页
第6页 / 共714页
第7页 / 共714页
第8页 / 共714页
Object-Oriented+Data+Structures+Using+Java,+4th+Edition-(2016).pdf
www.ebook3000.com
Object-Oriented
Data Structures
Java™
Javausing
Fourth Edition
Nell Dale
University of Texas, Austin
Daniel T. Joyce
Villanova University
Chip Weems
University of Massachusetts,
Amherst
World Headquarters
Jones & Bartlett Learning
5 Wall Street
Burlington, MA 01803
978-443-5000
info@jblearning.com
www.jblearning.com
Jones & Bartlett Learning books and products are available through most bookstores and online booksellers. To contact Jones & Bartlett
Learning directly, call 800-832-0034, fax 978-443-8000, or visit our website, www.jblearning.com.
Substantial discounts on bulk quantities of Jones & Bartlett Learning publications are available to corporations, professional associa-
tions, and other qualified organizations. For details and specific discount information, contact the special sales department at Jones &
Bartlett Learning via the above contact information or send an email to specialsales@jblearning.com.
Copyright © 2018 by Jones & Bartlett Learning, LLC, an Ascend Learning Company
All rights reserved. No part of the material protected by this copyright may be reproduced or utilized in any form, electronic or mechani-
cal, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright
owner.
The content, statements, views, and opinions herein are the sole expression of the respective authors and not that of Jones & Bartlett Learn-
ing, LLC. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise
does not constitute or imply its endorsement or recommendation by Jones & Bartlett Learning, LLC and such reference shall not be used for
advertising or product endorsement purposes. All trademarks displayed are the trademarks of the parties noted herein. Object-Oriented Data
Structures Using Java, Fourth Edition is an independent publication and has not been authorized, sponsored, or otherwise approved by the
owners of the trademarks or service marks referenced in this product.
09820-4
Production Credits
VP, Executive Publisher: David D. Cella
Cover Design: Kristin E. Parker
Acquisitions Editor: Laura Pagluica
Text Design: Scott Moden
Editorial Assistant: Taylor Ferracane
Rights & Media Specialist: Merideth Tumasz
Director of Vendor Management: Amy Rose
Media Development Editor: Shannon Sheehan
Marketing Manager: Amy Langlais
Cover Image: © Ake13bk/Shutterstock
VP, Manufacturing and Inventory Control: Therese Connell
Printing and Binding: Edwards Brothers Malloy
Composition and Project Management: S4Carlisle Publishing Services
Cover Printing: Edwards Brothers Malloy
Library of Congress Cataloging-in-Publication Data
Names: Dale, Nell (Nell B.), author. | Joyce, Daniel T., author. | Weems,
Chip., author.
Title: Object-oriented data structures using Java / Nell Dale, Daniel T.
Joyce, Chip Weems.
Description: Fourth edition. | Burlington, MA : Jones & Bartlett Learning,
[2017]
Identifiers: LCCN 2016025145 | ISBN 9781284089097 (casebound)
Subjects: LCSH: Object-oriented programming (Computer science) | Data
structures (Computer science) | Java (Computer program language)
Classification: LCC QA76.64 .D35 2017 | DDC 005.13/3--dc23 LC record available at
https://lccn.loc.gov/2016025145
6048
Printed in the United States of America
20 19 18 17 16 10 9 8 7 6 5 4 3 2 1
www.ebook3000.com
To Alfred G. Dale
ND
To Kathy, Tom, and Julie, thanks for the love and support
DJ
To Lisa, Charlie, and Abby, thank you . . .
CW
©
A
k
e
1
3
b
k
/
S
h
u
t
t
e
r
s
t
o
c
k
Preface
Welcome to the fourth edition of Object-Oriented Data Structures Using Java™. This book pres-
ents the algorithmic, programming, and structuring techniques of a traditional data structures
course in an object-oriented context. You’ll find the familiar topics of linked lists, recursion,
stacks, queues, collections, indexed lists, trees, maps, priority queues, graphs, sorting, searching,
and complexity analysis, all covered from an object-oriented point of view using Java. We stress
software engineering principles throughout, including modularization, information hiding, data
abstraction, stepwise refinement, the use of visual aids, the analysis of algorithms, and software
verification methods.
To the Student
You know that an algorithm is a sequence of unambiguous instructions for solving a problem.
You can take a problem of moderate complexity, design a small set of classes/objects that work
together to solve the problem, code the method algorithms needed to make the objects work, and
demonstrate the correctness of your solution.
Algorithms describe actions. These actions manipulate data. For most interesting problems
that are solved using computers, the structure of the data is just as important as the structure
of the algorithms used to manipulate the data. Using this text you will discover that the way
you structure data affects how efficiently you can use the data; you will see how the nature of
the problem you are attempting to solve dictates your structuring decisions; and you will learn
about the data structures that computer scientists have developed over the years to help solve
problems.
Object-Oriented Programming with Java
Our primary goal is to present both the traditional and modern data structure topics with an
emphasis on problem solving and software design. Using the Java programming language as a
vehicle for problem solutions, however, presents an opportunity for students to expand their
www.ebook3000.com
Preface
v
familiarity with a modern programming language and the object-oriented paradigm. As our data
structure coverage unfolds, we introduce and use the appropriate Java constructs that support our
primary goal. Starting early and continuing throughout the text, we introduce and expand on the
use of many Java features such as classes, objects, generics, polymorphism, packages, interfaces,
library classes, inheritance, exceptions, and threads. We also use Universal Modeling Language
(UML) class diagrams throughout to help model and visualize our objects, classes, interfaces,
applications, and their interrelationships.
Features
Data Abstraction
In this text we view our data structures from three different perspectives:
their specification, their application, and their implementation. The specification describes the
logical or abstract level—what the logical relationships among the data elements are and what
operations can be performed on the structure. The application level, sometimes called the client
level, is concerned with how the data structure is used to solve a problem—why the operations
do what they do. The implementation level involves the coding details—how the structures
and operations are implemented. In other words we treat our data structures as abstract data
types (ADTs).
Efficiency Analysis
In Chapter 1 we introduce order of growth efficiency analysis using a unique
approach involving the interaction of two students playing a game. Time and space analysis is
consistently applied throughout the text, allowing us to compare and contrast data structure
implementations and the applications that use them.
Recursion Treatment Recursion is introduced early (Chapter 3) and used throughout the re-
mainder of the text. We present a design and analysis approach to recursion based on answering
three simple questions. Answering the questions, which are based on formal inductive reasoning,
leads the programmer to a solid recursive design and program.
Interesting Applications Eight primary data structures (stacks, queues, collections, indexed
lists, trees, maps, priority queues, and graphs) are treated in separate chapters that include their
definition, several implementations, and one or more interesting applications based on their use.
Applications involve, for example, balanced expressions, postfix expressions, image generation
(new!), fractals (new!), queue simulation, card decks and games (new!), text analysis (new!), tree
and graph traversals, and big integers.
Robust Exercises We average more than 40 exercises per chapter. The exercises are organized by
chapter sections to make them easier for you to manage. They vary in level of difficulty, including
short and long programming problems (marked with “programming-required” icons—one icon
to indicate short exercises and two icons for projects), the analysis of algorithms, and problems
to test students’ understanding of abstract concepts. In this edition we have streamlined the
previous exercises, allowing us to add even more options for you to choose from. In particular
we have added several larger programming exercises to many of the chapters.
Input/Output Options
It is difficult to know what background the students using a data struc-
tures text will have in Java I/O. To allow all the students using our text to concentrate on the
vi
Preface
primary topic of data structures, we use the simplest I/O approach we can, namely a command
line interface. However, to support those teachers and students who prefer to work with graphi-
cal user interfaces (GUIs), we provide GUIs for many of our applications. Our modular approach
to program design supports this approach—our applications separate the user interface code,
problem solution code, and ADT implementation code into separate classes.
Concurrency Coverage We are pleased to be one of the only data structures texts to address the
topics of concurrency and synchronization, which are growing in importance as computer systems
move to using more cores and threads to obtain additional performance with each new generation.
We introduce this topic in Section 4.9, “Concurrency, Interference, and Synchronization,” where
we start with the basics of Java threads, continue through examples of thread interference and
synchronization, and culminate in a discussion of efficiency concerns.
New to the Fourth Edition
This edition represents a major revision of the text’s material, although the philosophy and style
that our loyal adopters have grown to appreciate remain unchanged. We removed material we
felt was redundant or of lesser/outdated importance to the core topic of data structures, added
new key material, and reworked much of the material that we kept. Although the length of the
textbook was reduced by about 10%, the coverage of data structures has been expanded. We
believe this new edition is a great improvement over previous editions and hope you do, too.
Major changes include:
• Simplified Architecture: We continue to use the Java interface construct to
define the abstract view of our ADTs, but we have reduced the number of levels
of inheritance, simplifying the architecture and making it easier to understand
and use.
• New Chapters: Chapter 5, “The Collection ADT,” and Chapter 8, “The Map ADT,” are
brand new. The Collection ADT material introduces the idea of a data structure as
a repository and concentrates on storage and retrieval of data based on key attri-
butes. The Map ADT has become increasingly important with the rise in popularity
of scripting languages with built-in associative arrays.
• New Section: Section 1.6, “Comparing Algorithms: Order of Growth Analysis,” was
completely rewritten and features an introduction to efficiency analysis driven by
a game played between two students, plus analysis of sequential search, binary
search, and sequential sort algorithms.
• New Sections: In response to reader’s suggestions, Chapter 3, “Recursion,” features
two new sections: Section 3.3, “Recursive Processing of Arrays,” is devoted to recur-
sive processing of arrays and Section 3.4, “Recursive Processing of Linked Lists,” is
devoted to recursive processing of linked lists. These new sections provide practical
examples of the use of recursion, before the reader moves on to the less practical
but nevertheless popular Towers of Hanoi example covered in Section 3.5, “Towers.”
• New Section: Fractals! A fun section related to recursively generating fractal-based
images now wraps up the examples of Chapter 3, “Recursion.”
www.ebook3000.com
Preface
vii
• New Sections: We added “Variations” sections to the Stack, Queue, Collection, List,
Tree, and Map chapters. In the primary exposition of each of these ADTs we record
design decisions and specify the operations to be supported by the ADT. We also
develop or at least discuss various implementation approaches, in most cases high-
lighting one array-based approach and one reference/linked-list-based approach.
The “Variations” section discusses alternate approaches to defining/implementing
the ADT and in most cases reviews the ADT counterparts available in the standard
Java Library. Some of these sections also introduce related ADTs, for example, in the
“Variations” section of the Collection chapter we define and discuss both the Set
and Bag ADTs.
• Glossary: The text’s glossary has always been available online. With this edition we
make it available as Appendix E. Throughout the text we highlight important terms
that might be unfamiliar to the student in green, the first time they are featured, to
indicate that their definition can be found in the glossary.
Prerequisite Assumptions
In this book, we assume that readers are familiar with the following Java constructs:
• Built-in simple data types and the array type
• Control structures while, do, for, if, and switch
• Creating and instantiating objects
• Basic user-defined classes:
variables and methods
constructors, method parameters, and the return statement
visibility modifiers
• Commonly used Java Library Classes: Integer, Math, Random, Scanner, String,
and System
Chapter Content
Chapter 1 is all about Getting Organized. An overview of object orientation stresses mecha-
nisms for organizing objects and classes. The Java exception handling mechanisms, used to
organize response to unusual situations, are introduced. Data structures are previewed and the
two fundamental language constructs that are used to implement those structures, the array
and the reference (link/pointer), are discussed. The chapter concludes with a look at efficiency
analysis—how we evaluate and compare algorithms.
Chapter 2 presents The Stack ADT. The concept of abstract data type (ADT) is introduced.
The stack is viewed from three different levels: the abstract, application, and implementation
levels. The Java interface mechanism is used to support this three-tiered view. We also investigate
using generics to support generally usable ADTs. The Stack ADT is implemented using both arrays
and references. To support the reference-based approach we introduce the linked list structure.
Sample applications include determining if a set of grouping symbols is well formed and the
evaluation of postfix expressions.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
