A practical introduction to data structures and algorithm analysis / Clifford A. Shaffer.

Includes bibliographical references (p. 497-501) and index.

Preface xi
I PRELIMINARIES 1 (84)
Data Structures and Algorithms
3 (18)
A Philosophy of Data Structures
4 (4)
The Need for Data Structures
4 (2)
Costs and Benefits
6 (2)
Abstract Data Types and Data Structures
8 (4)
Problems, Algorithms, and Programs
12 (3)
Further Reading
15 (2)
Exercises
17 (4)
Mathematical Preliminaries
21 (28)
Sets and Relations
21 (4)
Miscellaneous Notation
25 (1)
Logarithms
26 (2)
Recursion
28 (2)
Summations and Recurrences
30 (4)
Mathematical Proof Techniques
34 (7)
Proof by Contradiction
34 (1)
Proof by Mathematical Induction
35 (6)
Estimating
41 (2)
Further Reading
43 (1)
Exercises
43 (6)
Algorithm Analysis
49 (36)
Introduction
49 (6)
Best, Worst, and Average Cases
55 (2)
A Faster Computer, or a Faster Algorithm?
57 (2)
Asymptotic Analysis
59 (6)
Upper Bounds
60 (2)
Lower Bounds
62 (1)
Θ Notation
63 (1)
Simplifying Rules
64 (1)
Calculating the Running Time of a Program
65 (5)
Analyzing Problems
70 (1)
Common Misunderstandings
71 (1)
Multiple Parameters
72 (1)
Space Bounds
73 (3)
Some Practical Considerations
76 (2)
Further Reading
78 (1)
Exercises
79 (4)
Projects
83 (2)
II FUNDAMENTAL DATA STRUCTURES 85 (132)
Lists, Stacks, and Queues
87 (54)
Lists
88 (25)
Array-Based List Implementation
91 (4)
Linked Lists
95 (10)
Comparison of List Implementations
105 (2)
Element Implementations
107 (1)
Doubly Linked Lists
108 (5)
The Dictionary ADT
113 (6)
Stacks
119 (9)
Array-Based Stacks
121 (1)
Linked Stacks
122 (2)
Comparison of Array-Based and Linked Stacks
124 (1)
Implementing Recursion
125 (3)
Queues
128 (5)
Array-Based Queues
129 (4)
Linked Queues
133 (1)
Comparison of Array-Based and Linked Queues
133 (1)
Further Reading
133 (1)
Exercises
133 (5)
Projects
138 (3)
Binary Trees
141 (50)
Definitions and Properties
141 (5)
The Full Binary Tree Theorem
143 (2)
A Binary Tree Node ADT
145 (1)
Binary Tree Traversals
146 (3)
Binary Tree Node Implementations
149 (10)
Pointer-Based Node Implementations
149 (5)
Space Requirements
154 (3)
Array Implementation for Complete Binary Trees
157 (2)
Binary Search Trees
159 (8)
Heaps and Priority Queues
167 (7)
Huffman Coding Trees
174 (11)
Building Huffman Coding Trees
176 (6)
Assigning and Using Huffman Codes
182 (3)
Further Reading
185 (1)
Exercises
186 (3)
Projects
189 (2)
Non-Binary Trees
191 (26)
General Tree Definitions and Terminology
191 (4)
An ADT for General Tree Nodes
192 (1)
General Tree Traversals
193 (2)
The Parent Pointer Implementation
195 (7)
General Tree Implementations
202 (5)
List of Children
202 (1)
The Left-Child/Right-Sibling Implementation
203 (2)
Dynamic Node Implementations
205 (2)
Dynamic ``Left-Child/Right-Sibling'' Implementation
207 (1)
K-ary Trees
207 (1)
Sequential Tree Implementations
208 (3)
Further Reading
211 (1)
Exercises
211 (3)
Projects
214 (3)
III Sorting and Searching 217 (140)
Internal Sorting
219 (40)
Sorting Terminology and Notation
219 (2)
Three Θ(n2) Sorting Algorithms
221 (6)
Insertion Sort
221 (2)
Bubble Sort
223 (1)
Selection Sort
224 (2)
The Cost of Exchange Sorting
226 (1)
Shellsort
227 (2)
Quicksort
229 (6)
Mergesort
235 (3)
Heapsort
238 (3)
Binsort and Radix Sort
241 (6)
An Empirical Comparison of Sorting Algorithms
247 (2)
Lower Bounds for Sorting
249 (4)
Further Reading
253 (1)
Exercises
254 (3)
Projects
257 (2)
File Processing and External Sorting
259 (34)
Primary versus Secondary Storage
259 (3)
Disk Drives
262 (8)
Disk Drive Architecture
263 (5)
Disk Access Costs
268 (2)
Buffers and Buffer Pools
270 (5)
The Programmer's View of Files
275 (1)
External Sorting
276 (3)
Simple Approaches to External Sorting
279 (2)
Replacement Selection
281 (4)
Multiway Merging
285 (3)
Further Reading
288 (1)
Exercises
288 (3)
Projects
291 (2)
Searching
293 (34)
Searching Sorted Arrays
294 (1)
Self-Organizing Lists
295 (6)
Searching in Sets
301 (1)
Hashing
302 (19)
Hash Functions
303 (4)
Open Hashing
307 (1)
Closed Hashing
308 (13)
Further Reading
321 (1)
Exercises
321 (3)
Projects
324 (3)
Indexing
327 (30)
Linear Indexing
329 (2)
ISAM
331 (3)
Tree Indexing
334 (2)
2-3 Trees
336 (7)
B-Trees
343 (9)
B+-Trees
344 (6)
B-Tree Analysis
350 (2)
Further Reading
352 (1)
Exercises
353 (2)
Projects
355 (2)
IV Applications and Advanced Topics 357 (136)
Graphs
359 (34)
Terminology and Representations
360 (4)
Graph Implementations
364 (3)
Graph Traversals
367 (10)
Depth-First Search
370 (1)
Breadth-First Search
371 (4)
Topological Sort
375 (2)
Shortest-Paths Problems
377 (5)
Single-Source Shortest Paths
377 (4)
All-Pairs Shortest Paths
381 (1)
Minimum-Cost Spanning Trees
382 (5)
Prim's Algorithm
383 (3)
Kruskal's Algorithm
386 (1)
Further Reading
387 (1)
Exercises
388 (2)
Projects
390 (3)
Lists and Arrays Revisited
393 (30)
Skip Lists
393 (6)
Multilists
399 (3)
Matrix Representations
402 (4)
Memory Management
406 (12)
Dynamic Storage Allocation
407 (7)
Failure Policies and Garbage Collection
414 (4)
Further Reading
418 (1)
Exercises
419 (1)
Projects
420 (3)
Advanced Tree Structures
423 (28)
Tries
423 (5)
Balanced Trees
428 (6)
The AVL Tree
428 (3)
The Splay Tree
431 (3)
Spatial Data Structures
434 (13)
The K-D Tree
436 (5)
The PR quadtree
441 (4)
Other Spatial Data Structures
445 (2)
Further Reading
447 (1)
Exercises
447 (1)
Projects
448 (3)
Analysis Techniques
451 (18)
Summation Techniques
452 (3)
Recurrence Relations
455 (6)
Estimating Upper and Lower Bounds
455 (1)
Expanding Recurrences
456 (1)
Divide and Conquer Recurrences
457 (2)
Average-Case Analysis of Quicksort
459 (2)
Amortized Analysis
461 (3)
Further Reading
464 (1)
Exercises
464 (4)
Projects
468 (1)
Limits to Computation
469 (24)
Reductions
470 (5)
Hard Problems
475 (7)
NP-Completeness
476 (5)
Getting Around NP-Complete Problems
481 (1)
Impossible Problems
482 (7)
Uncountability
483 (3)
The Halting Problem Is Unsolvable
486 (2)
Determining Program Behavior Is Unsolvable
488 (1)
Further Reading
489 (1)
Exercises
489 (2)
Projects
491 (2)
V APPENDIX 493 (4)
A Utility Functions
495 (2)
Bibliography 497 (6)
Index 503

eng.