文档介绍：A Practical Introduction to
Data Structures and Algorithm
Analysis
Third Edition (Java Version)
Clifford A. Shaffer
Department puter Science
Virginia Tech
Blacksburg, VA 24061
January 19, 2010
Copyright
c 2009-2010 by Clifford A. Shaffer.
This document is made freely available for educational and other
mercial use.
You may make copies of this file and redistribute it 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 ******@.
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 14
15
Strategy 16
Problems, Algorithms, and Programs 17
Further Reading 19
Exercises 21
2 Mathematical Preliminaries 25
Sets and Relations 25
Miscellaneous Notation 29
Logarithms 31
Summations and Recurrences 33
iii
iv Contents
Recursion 36
Mathematical Proof Techniques 39
Direct Proof 40
Proof by Contradiction 40
Proof by Mathematical Induction 41
Estimating 47
Further Reading 49
Exercises 50
3 Algorithm Analysis 57
Introduction 57
Best, Worst, and Average Cases 63
A puter, or a Faster Algorithm? 65
Asymptotic Analysis 67
Upper Bounds 68
Lower Bounds 70
Θ Notation 71
Simplifying Rules 72
Classifying Functions 73
Calculating the Running Time for a Program 74
Analyzing Problems 79
Misunderstandings 81
Multiple Paramete