Estrutura de dados - livro do shaffer

Disponível somente no TrabalhosFeitos
  • Páginas : 488 (121958 palavras )
  • Download(s) : 0
  • Publicado : 29 de março de 2013
Ler documento completo
Amostra do texto
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
Copyright © 2009-2012 by Clifford A. Shaffer.
This document is made freely available in PDF form for educational and
othernon-commercial 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. 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
published by Dover Publications
(see http://store.doverpublications.com/048648582x.html).
Further information about this text is available at
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 Benefits
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.5 Further Reading
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.2 Proof by Contradiction
2.6.3 Proof by Mathematical Induction
Estimation
Further Reading
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.10 Speeding Up Your Programs
3.11 Empirical Analysis
3.12 Further Reading
3.13 Exercises
3.14 ProjectsFundamental Data Structures
Lists, Stacks, and Queues
4.1 Lists
4.1.1 Array-Based List Implementation
4.1.2 Linked Lists
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
4.1.5 DoublyLinked Lists
Stacks
4.2.1 Array-Based Stacks
4.2.2 Linked 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.2 Linked Queues
4.3.3 Comparison of Array-Based and Linked Queues
Dictionaries
Further Reading
Exercises
Projects

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

5

BinaryTrees
5.1 Definitions 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.7 Further Reading
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 Definitions and Terminology

203

6.1.1

An ADT for General Tree Nodes

204

6.1.2

General...
tracking img