文档介绍：Data Structures and Algorithm
Analysis
Edition (C++ 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 25
Sets and Relations 25
Miscellaneous Notation 29
Logarithms 31
Summations and Recurrences 32
Recursion 36
Mathematical Proof Techniques 38
iii
iv Contents
Direct Proof 39
Proof by Contradiction 39
Proof by Mathematical Induction 40
Estimation 46
Further Reading 47
Exercises 48
3 Algorithm Analysis 55
Introduction 55
Best, Worst, and Average Cases 61
A puter, or a Faster Algorithm? 62
Asymptotic Analysis 65
Upper Bounds 65