数据结构与算法分析（Java版）3.1章实战指南

需积分: 9 3 浏览量更新于2024-07-31 收藏 2.03MB PDF 举报

"A Practical Introduction to Data Structures and Algorithm Analysis (3.1)" 是一本由Clifford A. Shaffer编写的经典数据结构与算法分析教材，适用于Java编程语言。这本教材是2010年版，由Shaffer博士授权在教育机构中分享。作者是弗吉尼亚理工学院计算机科学系的教授，该书于2011年1月3日发布。此书的版权归属于Clifford A. Shaffer，并允许非商业性的自由复制和分发，但需保留标题、作者和版权声明。书中涵盖了数据结构和算法分析的基本概念，旨在为读者提供实用的指导。以下是对书中的关键知识点的详细说明： 1. **数据结构和算法的重要性** - **哲学**：1.1章节讨论了数据结构和算法的重要性，强调它们在解决问题时的关键作用。数据结构是组织和存储数据的方式，而算法则是解决问题的步骤或方法。 - **需求**：1.1.1小节指出，数据结构的使用是为了更有效地管理和操作数据，解决复杂的问题。 - **成本与收益**：1.1.2小节探讨了使用合适的数据结构和算法在时间和空间效率上的权衡。 2. **抽象数据类型与数据结构** - 1.2章节介绍了抽象数据类型（ADT）的概念，它是一种逻辑上的数据类型，只关注其操作而不关注其实现细节。数据结构是实现ADT的具体方式。 3. **设计模式** - 1.3章节中，Shaffer教授讲解了几种常见的设计模式，如： - **Flyweight模式**：用于减少内存消耗，通过共享大量相似对象来节省资源。 - **Visitor模式**：使对象结构独立于对其操作的代码，提供了一种在运行时增加新行为的方式。 - **Composite模式**：将对象组合成树形结构，使用户可以统一处理单个对象和对象集合。 - **Strategy模式**：定义一系列算法，将每个算法封装起来，让它们可以互相替换，使算法的变化独立于使用它的客户端。 4. **问题、算法与程序** - 1.4章节讨论了问题、算法和程序之间的关系，阐述了如何从问题出发，通过算法设计，最终实现为程序。这本教材不仅适合大学课堂，也适合自学者，它深入浅出地讲解了数据结构和算法分析的基础，帮助读者理解并掌握这些核心技术，为解决实际问题和编写高效软件打下坚实基础。书中的练习题和例子将有助于读者巩固所学知识，提升编程能力。读者可以通过访问作者提供的在线资源获取更多相关信息。

Preface xvii

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 il-

luminate 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 the form

of calls to methods in class Assert. These methods are modeled after the C stan-

dard library function 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 ref-

erence to class Object, and terminates the program if the value of the refer-

ence is null. (To be precise, these functions throw an IllegalArgument-

Exception, which typically results in terminating the program unless the pro-

grammer takes action 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 programming applications, Java’s

exception handling features should be used to deal with input data errors. However,

assertions provide a simpler mechanism for indicating 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.

xviii Preface

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 alloca-

tion, by implementing data structures such as linked lists and trees. Its also 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 arguably the most difﬁcult programming course in the curricu-

lum.

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

vide over 400 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

Cliff Shaffer

Department of Computer Science

Virginia Tech

Blacksburg, VA 24061

A set of lecture notes for use in conjunction with this book can be obtained

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

shaffer/book.html. All code examples

used in the book are also available at this site. Online Web pages for Virginia

Tech’s sophomore-level data structures class can be found at URL

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

cs3114

This book was originally typeset by the author with L

X. The bibliography

was prepared using BIBT

X. The index was prepared using makeindex. The

ﬁgures were mostly drawn with Xfig. Figures 3.1 and 9.8 were partially created

using Mathematica.

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.

Preface xix

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.

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.

Without the hard work of many people at Prentice Hall, none of this would be

possible. Authors 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, Kath-

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

剩余627页未读，继续阅读

zt_bull

粉丝: 0
资源: 2

数据结构与算法分析（Java版）3.1章实战指南

《A Practical Introduction to Data Structures and Algorithm Analysis》

A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (C++ Version)

unordered_map and Algorithm Complexity Analysis: Search, Insertion, Deletion

[Practical Exercise] Gaussian Belief Propagation Algorithm for DC State Estimation Model in MATLAB

C Language Image Pixel Data Loading and Analysis [Image Processing Library] NImage: A C Language-...

C Language Image Pixel Data Input and Analysis [Pixel Data Processing] Acquisition of Pixel RGB ...

C Language Image Pixel Data Reading and Analysis [Image Processing Library] CImg Library: A Powerful...

【Project Practicality】: New Horizons in Image Transformation: A Practical Guide to the Application...

MATLAB Genetic Algorithm Coding and Operations: In-depth Analysis of Crossover and Mutation

Optimization of Medical Data Analysis with MATLAB: Practical Applications of Optimization Algorithms

最新资源