文档介绍：Data Structures and Algorithm
Analysis
Edition (Java Version)
Clifford A. Shaffer
Department puter Science
Virginia Tech
Blacksburg, VA 24061
September 15, 2011
Update
For a list of changes, see
/˜shaffer/Book/
Copyright © 2009-2011 by Clifford A. Shaffer.
This document is made freely available in PDF form for educational and
other mercial use. You may make copies of this file and
redistribute in electronic form without charge. You may extract portions of
this document provided that the front page, including the title, author, and
this notice are included. mercial use of this document requires the
written consent of the author. The author can be reached at
******@.
If you wish to have a printed version of this document, print copies are
published by Dover Publications
(see http://store./).
Further information about this text is available at
/˜shaffer/Book/.
Contents
Preface xiii
I Preliminaries 1
1 Data Structures and Algorithms 3
A Philosophy of Data Structures 4
The Need for Data Structures 4
Costs and Benefits 6
Abstract Data Types and Data Structures 8
Design Patterns 12
Flyweight 13
Visitor 13
14
Strategy 15
Problems, Algorithms, and Programs 16
Further Reading 18
Exercises 20
2 Mathematical Preliminaries 23
Sets and Relations 23
Miscellaneous Notation 27
Logarithms 29
Summations and Recurrences 30
Recursion 34
Mathematical Proof Techniques 36
iii
iv Contents
Direct Proof 37
Proof by Contradiction 37
Proof by Mathematical Induction 38
Estimation 44
Further Reading 45
Exercises 46
3 Algorithm Analysis 53
Introduction 53
Best, Worst, and Average Cases 59
A puter, or a Faster Algorithm? 60
Asymptotic Analysis 63
Upper Bounds 6