# Estrutura de dados - livro do shaffer

Páginas: 488 (121958 palavras) Publicado: 29 de março de 2013
Data Structures and Algorithm
Analysis
Edition 3.2 (C++ Version)
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
November 19, 2012
Update 3.2.0.7
For a list of changes, see
http://people.cs.vt.edu/˜shaffer/Book/errata.html
This document is made freely available in PDF form for educational and
othernon-commercial use. You may make copies of this ﬁle 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. Any commercial use of this document requires the
written consent of the author. The author can be reached at
shaffer@cs.vt.edu.
If you wish to have a printedversion of this document, print copies are
(see http://store.doverpublications.com/048648582x.html).
http://people.cs.vt.edu/˜shaffer/Book/.

Contents

Preface

xiii

I

Preliminaries

1

1

Data Structures and Algorithms
1.1 A Philosophy of Data Structures
1.1.1 The Need for Data Structures1.1.2 Costs and Beneﬁts
1.2 Abstract Data Types and Data Structures
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
1.6 Exercises

3
4
4
6
8
12
13
13
14
15
16
18
20

2

Mathematical Preliminaries
2.1 Sets and Relations
2.2 Miscellaneous Notation
2.3 Logarithms
2.4 Summations andRecurrences
2.5 Recursion
2.6 Mathematical Proof Techniques

25
25
29
31
32
36
38
iii

iv

Contents

2.7
2.8
2.9
3

II
4

2.6.1 Direct Proof
2.6.3 Proof by Mathematical Induction
Estimation
Exercises

Algorithm Analysis
3.1 Introduction
3.2 Best, Worst, and Average Cases
3.3 A Faster Computer, or a Faster Algorithm?3.4 Asymptotic Analysis
3.4.1 Upper Bounds
3.4.2 Lower Bounds
3.4.3 Θ Notation
3.4.4 Simplifying Rules
3.4.5 Classifying Functions
3.5 Calculating the Running Time for a Program
3.6 Analyzing Problems
3.7 Common Misunderstandings
3.8 Multiple Parameters
3.9 Space Bounds
3.11 Empirical Analysis
3.13 Exercises
3.14 ProjectsFundamental Data Structures
Lists, Stacks, and Queues
4.1 Lists
4.1.1 Array-Based List Implementation
4.1.3 Comparison of List Implementations

39
39
40
46
47
48
55
55
61
62
65
65
67
68
69
70
71
76
77
79
80
82
85
86
86
90

93
95
96
100
103
112

v

Contents

4.2

4.3

4.4
4.5
4.6
4.7

4.1.4 Element Implementations
Stacks
4.2.1 Array-Based Stacks
4.2.3 Comparison of Array-Based and Linked Stacks
4.2.4 Implementing Recursion
Queues
4.3.1 Array-Based Queues
4.3.3 Comparison of Array-Based and Linked Queues
Dictionaries
Exercises
Projects

114
115
120
121
124
125
125
129
129
134
134
134
145
145
149

5

BinaryTrees
5.1 Deﬁnitions and Properties
5.1.1 The Full Binary Tree Theorem
5.1.2 A Binary Tree Node ADT
5.2 Binary Tree Traversals
5.3 Binary Tree Node Implementations
5.3.1 Pointer-Based Node Implementations
5.3.2 Space Requirements
5.3.3 Array Implementation for Complete Binary Trees
5.4 Binary Search Trees
5.5 Heaps and Priority Queues
5.6 Huffman Coding Trees
5.6.1 Building Huffman CodingTrees
5.6.2 Assigning and Using Huffman Codes
5.6.3 Search in Huffman Trees
5.8 Exercises
5.9 Projects

151
151
153
155
155
160
160
166
168
168
178
185
186
192
195
196
196
200

6

Non-Binary Trees

203

vi

Contents

6.1

General Tree Deﬁnitions and Terminology

203

6.1.1

An ADT for General Tree Nodes

204

6.1.2

General...

Por favor, assinar para o acesso.