Java版数据结构与算法分析第三版

5星 · 超过95%的资源需积分: 9 145 浏览量更新于2024-07-29 5 收藏 2.37MB PDF 举报

"Data Structures and Algorithm Analysis in Java 3rd edition 是一本由Clifford A. Shaffer编著的关于数据结构与算法分析的专业书籍，适用于Java编程语言。书中涵盖了数据结构、算法设计与分析的基础知识，并且在第三版中进行了更新，版本号为3.2.0.2。作者允许教育和非商业用途的自由复制和分发，但任何商业使用需要获得作者的书面许可。此外，该书也有Dover Publications出版的纸质版本。本书的内容包括了前言和多个章节，主要讨论以下几个核心知识点： 1. 数据结构与算法的重要性：书中首先阐述了数据结构和算法在计算机科学中的哲学意义，强调它们是解决问题和优化程序性能的关键。数据结构是组织和存储数据的方式，而算法则是解决问题的步骤和方法。 2. 基本概念：书中可能涵盖了如数组、链表、栈、队列、树（二叉树、平衡树如AVL和红黑树等）、图等基本数据结构的定义、操作和特性。同时，也会讲解排序（如冒泡排序、插入排序、快速排序、归并排序等）、搜索（如线性搜索、二分搜索）等基础算法。 3. 复杂度分析：书中会深入探讨时间复杂度和空间复杂度的概念，以及如何通过它们来评估算法的效率。这包括大O符号表示法，以及如何通过分析算法运行时的操作次数来估算其复杂度。 4. 高级数据结构和算法：除了基础内容，书里可能还涉及高级数据结构，如哈希表、堆、图算法（如Dijkstra最短路径算法、Floyd-Warshall算法）和动态规划等。 5. 设计与分析技巧：书中可能教导读者如何设计有效的算法，使用分治、贪心、回溯等策略，并介绍如何分析算法的效率和优化方法。 6. 实践应用：可能会包含实际编程挑战和案例研究，帮助读者将理论知识应用到实际问题解决中。 7. 问题解决策略：书中的内容可能还会涵盖如何理解和表述问题，选择合适的数据结构，以及如何用算法来解决这些问题。通过阅读这本书，读者可以提升对数据结构和算法的理解，提高编程能力，特别是对于Java开发者，能更好地利用这些工具来编写高效、可维护的代码。同时，书中的例子和练习有助于加深理解，并培养分析和解决问题的能力。"

xvi Preface

As with any programming language, Java has both advantages and disadvan-

tages. Java is a small language. There usually is only one language feature to do

something, and this has the happy tendency of encouraging a programmer toward

clarity when used correctly. In this respect, it is superior to C or C

. Java serves

nicely for deﬁning and using most traditional data structures such as lists and trees.

On the other hand, Java is quite poor when used to do ﬁle processing, being both

cumbersome and inefﬁcient. It is also a poor language when ﬁne control of memory

is required. As an example, applications requiring memory management, such as

those discussed in Section 12.3, are difﬁcult to write in Java. Since I wish to stick

to a single language throughout the text, like any programmer I must take the bad

along with the good. The most important issue is to get the ideas across, whether

or not those ideas are natural to a particular language of discourse. Most program-

mers will use a variety of programming languages throughout their career, and the

concepts described in this book should prove useful in a variety of circumstances.

Inheritance, a key feature of object-oriented programming, is used sparingly

in the code examples. Inheritance is an important tool that helps programmers

avoid duplication, and thus minimize bugs. From a pedagogical standpoint, how-

ever, inheritance often makes code examples harder to understand since it tends to

spread the description for one logical unit among several classes. Thus, my class

deﬁnitions only use inheritance where inheritance is explicitly relevant to the point

illustrated (e.g., Section 5.3.1). This does not mean that a programmer should do

likewise. Avoiding code duplication and minimizing errors are important goals.

Treat the programming examples as illustrations of data structure principles, but do

not copy them directly into your own programs.

One painful decision I had to make was whether to use generics in the code

examples. Generics were not used in the ﬁrst edition of this book. But in the years

since then, Java has matured and its use in computer science curricula has greatly

expanded. I now assume that readers of the text will be familiar with generic syntax.

Thus, generics are now used extensively in the code examples.

My implementations are meant to provide concrete illustrations of data struc-

ture principles, as an aid to the textual exposition. Code examples should not be

read or used in isolation from the associated text because the bulk of each exam-

ple’s documentation is contained in the text, not the code. The code complements

the text, not the other way around. They are not meant to be a series of commercial-

quality class implementations. If you are looking for a complete implementation

of a standard data structure for use in your own code, you would do well to do an

Internet search.

For instance, the code examples provide less parameter checking than is sound

programming practice, since including such checking would obscure rather than

illuminate the text. Some parameter checking and testing for other constraints

(e.g., whether a value is being removed from an empty container) is included in

Preface xvii

the form ofcalls to methods in class Assert. Method Assert.notFalse

takes a Boolean expression. If this expression evaluates to false, then a message

is printed and the program terminates immediately. Method Assert.notNull

takes a reference to class Object, and terminates the program if the value of

the reference is null. (To be precise, they throw an IllegalArgument-

Exception, which will terminate the program unless the programmer takes ac-

tion to handle the exception.) Terminating a program when a function receives a

bad parameter is generally considered undesirable in real programs, but is quite

adequate for understanding how a data structure is meant to operate. In real pro-

gramming applications, Java’s exception handling features should be used to deal

with input data errors. However, assertions provide a simpler mechanism for indi-

cating required conditions in a way that is both adequate for clarifying how a data

structure is meant to operate, and is easily modiﬁed into true exception handling.

I make a distinction in the text between “Java implementations” and “pseu-

docode.” Code labeled as a Java implementation has actually been compiled and

tested on one or more Java compilers. Pseudocode examples often conform closely

to Java syntax, but typically contain one or more lines of higher-level description.

Pseudocode is used where I perceived a greater pedagogical advantage to a simpler,

but less precise, description.

Exercises and Projects: Proper implementation and analysis of data structures

cannot be learned simply by reading a book. You must practice by implementing

real programs, constantly comparing different techniques to see what really works

best in a given situation.

One of the most important aspects of a course in data structures is that it is

where students really learn to program using pointers and dynamic memory al-

location, by implementing data structures such as linked lists and trees. It is often

where students truly learn recursion. In our curriculum, this is the ﬁrst course where

students do signiﬁcant design, because it often requires real data structures to mo-

tivate signiﬁcant design exercises. Finally, the fundamental differences between

memory-based and disk-based data access cannot be appreciated without practical

programming experience. For all of these reasons, a data structures course cannot

succeed without a signiﬁcant programming component. In our department, the data

structures course is one of the most difﬁcult programming course in the curriculum.

Students should also work problems to develop their analytical abilities. I pro-

vide over 450 exercises and suggestions for programming projects. I urge readers

to take advantage of them.

Contacting the Author and Supplementary Materials: A book such as this

is sure to contain errors and have room for improvement. I welcome bug reports

and constructive criticism. I can be reached by electronic mail via the Internet at

shaffer@vt.edu. Alternatively, comments can be mailed to

xviii Preface

Cliff Shaffer

Department of Computer Science

Virginia Tech

Blacksburg, VA 24061

The electronic posting of this book, along with a set of lecture notes for use in

class can be obtained at

http://www.cs.vt.edu/

shaffer/book.html.

The code examples used in the book are available at the same site. Online Web

pages for Virginia Tech’s sophomore-level data structures class can be found at

http://courses.cs.vt.edu/

cs3114.

This book was typeset by the author using L

X. The bibliography was pre-

pared using BIBT

X. The index was prepared using makeindex. The ﬁgures were

mostly drawn with Xfig. Figures 3.1 and 9.10 were partially created using Math-

ematica.

Acknowledgments: It takes a lot of help from a lot of people to make a book.

I wish to acknowledge a few of those who helped to make this book possible. I

apologize for the inevitable omissions.

Virginia Tech helped make this whole thing possible through sabbatical re-

search leave during Fall 1994, enabling me to get the project off the ground. My de-

partment heads during the time I have written the various editions of this book, Den-

nis Kafura and Jack Carroll, provided unwavering moral support for this project.

Mike Keenan, Lenny Heath, and Jeff Shaffer provided valuable input on early ver-

sions of the chapters. I also wish to thank Lenny Heath for many years of stimulat-

ing discussions about algorithms and analysis (and how to teach both to students).

Steve Edwards deserves special thanks for spending so much time helping me on

various redesigns of the C

and Java code versions for the second and third edi-

tions, and many hours of discussion on the principles of program design. Thanks

to Layne Watson for his help with Mathematica, and to Bo Begole, Philip Isenhour,

Jeff Nielsen, and Craig Struble for much technical assistance. Thanks to Bill Mc-

Quain, Mark Abrams and Dennis Kafura for answering lots of silly questions about

and Java.

I am truly indebted to the many reviewers of the various editions of this manu-

script. For the ﬁrst edition these reviewers included J. David Bezek (University of

Evansville), Douglas Campbell (Brigham Young University), Karen Davis (Univer-

sity of Cincinnati), Vijay Kumar Garg (University of Texas – Austin), Jim Miller

(University of Kansas), Bruce Maxim (University of Michigan – Dearborn), Jeff

Parker (Agile Networks/Harvard), Dana Richards (George Mason University), Jack

Tan (University of Houston), and Lixin Tao (Concordia University). Without their

help, this book would contain many more technical errors and many fewer insights.

Preface xix

For the second edition, I wish to thank these reviewers: Gurdip Singh (Kansas

State University), Peter Allen (Columbia University), Robin Hill (University of

Wyoming), Norman Jacobson (University of California – Irvine), Ben Keller (East-

ern Michigan University), and Ken Bosworth (Idaho State University). In addition,

I wish to thank Neil Stewart and Frank J. Thesen for their comments and ideas for

improvement.

Third edition reviewers included Randall Lechlitner (University of Houstin,

Clear Lake) and Brian C. Hipp (York Technical College). I thank them for their

comments.

Prentice Hall was the original print publisher for the ﬁrst and second editions.

Without the hard work of many people there, none of this would be possible. Au-

thors simply do not create printer-ready books on their own. Foremost thanks go to

Kate Hargett, Petra Rector, Laura Steele, and Alan Apt, my editors over the years.

My production editors, Irwin Zucker for the second edition, Kathleen Caren for

the original C

version, and Ed DeFelippis for the Java version, kept everything

moving smoothly during that horrible rush at the end. Thanks to Bill Zobrist and

Bruce Gregory (I think) for getting me into this in the ﬁrst place. Others at Prentice

Hall who helped me along the way include Truly Donovan, Linda Behrens, and

Phyllis Bregman. Thanks to Tracy Dunkelberger for her help in returning the copy-

right to me, thus enabling the electronic future of this work. I am sure I owe thanks

to many others at Prentice Hall for their help in ways that I am not even aware of.

I am thankful to Shelley Kronzek at Dover publications for her faith in taking

on the print publication of this third edition. Much expanded, with both Java and

versions, and many inconsistencies corrected, I am conﬁdent that this is the

best edition yet. But none of us really knows whether students will prefer a free

online textbook or a low-cost, printed bound version. In the end, we believe that

the two formats will be mutually supporting by offering more choices. Production

editor James Miller and design manager Marie Zaczkiewicz have worked hard to

ensure that the production is of the highest quality.

I wish to express my appreciation to Hanan Samet for teaching me about data

structures. I learned much of the philosophy presented here from him as well,

though he is not responsible for any problems with the result. Thanks to my wife

Terry, for her love and support, and to my daughters Irena and Kate for pleasant

diversions from working too hard. Finally, and most importantly, to all of the data

structures students over the years who have taught me what is important and what

should be skipped in a data structures course, and the many new insights they have

provided. This book is dedicated to them.

Cliff Shaffer

Blacksburg, Virginia

剩余601页未读，继续阅读

Lactoferrin

粉丝: 585
资源: 52

Java版数据结构与算法分析第三版

Clifford Shaffer's Data Structures and Algorithm Analysis in C++

SpringBoot入门与Data Structures and Algorithm Analysis解析

SpringBoot入门与Data Structures and Algorithm Analysis教程

Data Structures and Algorithm Analysis in C++ 3rd edition

Data Structures and Algorithm Analysis in C++, Third Edition.pdf

Addison.Wesley.Data.Structures.and.Algorithm.Analysis.in.Java.3rd.Edition.2011

Introduction to Algorithms Third Edition

Java数据结构与算法分析第三版

《Java数据结构与算法分析》第三版 - Mark Allen Weiss

C++版数据结构与算法分析第三版——Clifford A. Shaffer著

最新资源