Data Structures & Algorithm Analysis in Java (3rd ed.) [Shaffer 2011-09-14].pdf

(2714 KB) Pobierz
Data Structures and Algorithm
Analysis
Edition 3.2 (Java Version)
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
September 15, 2011
Update 3.2.0.2
For a list of changes, see
http://people.cs.vt.edu/˜shaffer/Book/errata.html
Copyright © 2009-2011 by Clifford A. Shaffer.
This document is made freely available in PDF form for educational and
other non-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 printed version of this document, print copies are
published by Dover Publications
(see
http://store.doverpublications.com/0486485811.html
).
Further information about this text is available at
http://people.cs.vt.edu/˜shaffer/Book/.
Contents
Preface
xiii
I Preliminaries
1
Data Structures and Algorithms
1.1 A Philosophy of Data Structures
1.1.1 The Need for Data Structures
1.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
Mathematical Preliminaries
2.1 Sets and Relations
2.2 Miscellaneous Notation
2.3 Logarithms
2.4 Summations and Recurrences
2.5 Recursion
2.6 Mathematical Proof Techniques
1
3
4
4
6
8
12
13
13
14
15
16
18
20
23
23
27
29
30
34
36
iii
2
iv
2.6.1 Direct Proof
2.6.2 Proof by Contradiction
2.6.3 Proof by Mathematical Induction
Estimation
Further Reading
Exercises
Contents
2.7
2.8
2.9
3
37
37
38
44
45
46
53
53
59
60
63
63
65
66
67
68
69
74
75
77
78
80
83
84
85
89
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 Projects
II Fundamental Data Structures
4
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
91
93
94
97
100
108
Contents
v
4.1.4 Element Implementations
4.1.5 Doubly Linked 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
111
112
117
117
120
121
121
125
125
128
131
131
138
138
141
145
145
147
149
149
154
154
160
161
163
170
178
179
185
188
188
189
192
195
4.2
4.3
4.4
4.5
4.6
4.7
5
Binary Trees
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 Coding Trees
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
Non-Binary Trees
6
vi
6.1
General Tree Definitions and Terminology
6.1.1
6.1.2
6.2
6.3
An ADT for General Tree Nodes
General Tree Traversals
Contents
195
196
197
199
206
206
206
207
210
210
212
215
215
218
The Parent Pointer Implementation
General Tree Implementations
6.3.1
6.3.2
6.3.3
6.3.4
List of Children
The Left-Child/Right-Sibling Implementation
Dynamic Node Implementations
Dynamic “Left-Child/Right-Sibling” Implementation
6.4
6.5
6.6
6.7
6.8
K-ary
Trees
Sequential Tree Implementations
Further Reading
Exercises
Projects
III Sorting and Searching
7
Internal Sorting
7.1
7.2
Sorting Terminology and Notation
Three
Θ(n
2
)
Sorting Algorithms
7.2.1
7.2.2
7.2.3
7.2.4
7.3
7.4
7.5
7.6
7.7
7.8
7.9
Insertion Sort
Bubble Sort
Selection Sort
The Cost of Exchange Sorting
221
223
224
225
225
227
229
230
231
233
236
243
244
251
253
257
257
261
Shellsort
Mergesort
Quicksort
Heapsort
Binsort and Radix Sort
An Empirical Comparison of Sorting Algorithms
Lower Bounds for Sorting
7.10 Further Reading
7.11 Exercises
7.12 Projects

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin