Clifford Shaffer的《数据结构与算法分析》英文第三版简介

需积分: 10 136 浏览量更新于2024-07-26 收藏 2.03MB PDF 举报

"《数据结构与算法描述》英文第三版，作者Clifford A. Shaffer，是一部关于数据结构和算法分析的专业书籍，适合教育和非商业使用。" 该书是数据结构与算法领域的一本实践性入门教程，由Clifford A. Shaffer撰写，他来自美国弗吉尼亚理工学院计算机科学系。书中内容涵盖了从基础知识到高级概念的广泛话题，旨在帮助读者理解和应用数据结构和算法。在" Preface "（序言）部分，作者阐述了编写本书的哲学和目的，强调了数据结构在软件工程中的重要性，并讨论了教育和非商业使用本书的自由权限。第一部分"I Preliminaries"（预备知识）介绍了数据结构和算法的基础概念。第1章"Data Structures and Algorithms"探讨了为何需要数据结构，以及它们的成本和益处。1.1.1节"The Need for Data Structures"解释了在解决复杂问题时数据结构的重要性，1.1.2节"Custs and Benefits"则讨论了使用数据结构的代价和好处。接着，1.2节"Abstract Data Types and Data Structures"介绍了抽象数据类型（ADT）和数据结构的区别和联系，这是理解算法设计的关键。1.3节"Design Patterns"探讨了软件设计模式，包括1.3.1节"Flyweight"用于减少内存消耗，1.3.2节"Visitor"允许在不修改类结构的情况下添加新操作，1.3.3节"Composite"用于构建部分-整体层次结构，以及1.3.4节"Strategy"用于定义算法族并使它们互换。 1.4节"Problems, Algorithms, and Programs"讨论了问题、算法和程序之间的关系，为后续章节中对具体算法的深入分析奠定了基础。通过这些内容，读者将能够更好地理解如何利用数据结构和算法来解决问题。整本书还包含多个章节，涵盖了如链表、栈、队列、树、图、排序和搜索算法等核心数据结构和算法。此外，书中可能还包括了复杂度分析、动态规划、贪心算法以及递归等高级主题。这本书对于计算机科学的学生和专业人士来说是一份宝贵的资源，它提供了深入的理论知识和实际应用示例，有助于提升在数据结构和算法方面的专业技能。

Preface xvii

is contained in the text, not the code. The code complements the text, not the other

way around.

The code examples provide less parameter checking than is sound program-

ming practice for professional programmers. Some parameter checking and testing

for other constraints (such as whether a value is being removed from an empty con-

tainer) is included in the form of a call to Assert. Assert is a modiﬁed version

of the C library function assert. The inputs to Assert are a Boolean expres-

sion and a character string. If this expression evaluates to false, then the string

is printed and the program terminates immediately. This behavior is generally con-

sidered undesirable in real programs. CPP provides a good alternative mechanism

through exception handling. However, Assert provides 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 han-

dling. See the Appendix for the implementation of Assert.

I make a distinction in the text between “C

implementations” and “pseu-

docode.” Code labeled as a C

implementation has actually been compiled and

tested on one or more C

compilers. Pseudocode examples often conform closely

to C

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

Pseudocode is used where I perceived a greater pedagogical advantage to a simpli-

ﬁed, but less precise, description.

Exercises and Projects: Proper implementation and anaysis 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 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.

xviii Preface

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 transparency masters for use in conjunction with this book can be

obtained via the WWW at either of the following URLs:

http://www.prenhall.com/shaffer

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

shaffer/book.html

The C

code examples are also available from these sites. Online Web pages for

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

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

cs2604

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.

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

the redesign of the C

code for the second edition, 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 McQuain, Mark Abrams and Dennis

Kafura for answering lots of silly questions about C

and Java.

Preface xix

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.

Others at Prentice Hall who helped me along the way include Truly Donovan, Linda

Behrens, and Phyllis Bregman. 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 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.

Clifford A. Shaffer

Blacksburg, Virginia

剩余637页未读，继续阅读

Coding4fun_

粉丝: 0
资源: 2

Clifford Shaffer的《数据结构与算法分析》英文第三版简介

C++数据结构与算法分析第三版英文版课后习题解答

C++版数据结构与算法分析第3版习题解答

《数据结构与算法分析C++版》第三版英文解答

数据结构与算法描述c++版本

数据结构与算法C语言描述（英文版）

数据结构与算法分析：C语言描述.rar_donescc_engine6fo_数据结构和算法分析C语言版_数据结构算法

数据结构与算法分析--C语言描述_数据结构与算法_

数据结构与算法分析C++描述（第三版）_数据开发_数据结构与算法分析第三版C++_

数据结构C++算法描述

数据结构与算法C语言描述

最新资源