About the Book
With this book, Tim Budd looks at
data structures by providing a solid foundation on the ADT, and uses the
graphical elements found in Java when possible.
The beginning chapters provide the
foundation on which everything else will be built. These chapters define
the essential concept of the abstract data type (ADT), and describe the
tools used in the evaluation and analysis of data structures. The book
moves on to provide a detailed description of the two most important fundamental
data abstractions, the vector and the linked list, providing an explanation
of some of the more common variations on these fundamental ideas.
Next, the material considers data structures
applicable to problems in which the order that values are added to a collection
is important, followed by a consideration of the various different ways
in which binary trees are used in the creation of data structures. The
last few chapters consider a sequence of more advanced data structures.
Most are constructed as adaptors built on top of earlier abstractions.
Hash tables are introduced first as a technique for implementing simple
collections, and later as a tool for developing efficient maps. Lastly,
the graph data type is considered. Here there are several alternative data
structures presentations in common use, and the emphasis in this chapter
is more on the development and analysis of useful algorithms than on any
particular data structure.
Features
-
An object-oriented mindset is applied throughout.
-
The clear separation between ADT (interface)
and implementation is emphasized throughout.
-
A rigorous approach to development in encouraged,
with techniques for developing formal proofs of programs being presented,
and proofs of programs appearing throughout the text.
-
An explorational and visual approach is encouraged
by providing tools that make it easy to create a visual record of execution
time, and Experiments that will help see aspects of execution that may
not be obvious from the code.
-
Important software patterns are highlighted,
and the use of patterns is emphasized from the beginning.
-
Graphical elements, chosen to minimize the
unnecessary detail and emphasize the important lessons of Java, are used
to motivate the student's interest in the material.
-
Sidebars are included throughout so that readers
can then peruse additional information as they choose.
-
End of Chapter material is designed to aid
students comprehension of the material just presented, including: a chapter
summary, glossary of key terms, numerous basic study questions, a collection
of thought-provoking exercises, and a series of programming projects.
-
An appendix with an overview of Java syntax
makes this book appropriate for readers without a Java background.
-
Written by Tim Budd, author of numerous other
successful texts, including Classic Data Structures in C++, Data Structures
in C++ with the STL, Introduction to Object Oriented Programming, and C++
for Java Programmers.
Related
Books
Data Structures - Programming
Courses (Data Structures)
Table of Contents
1. The Management of Complexity.
The Control of Complexity.
Abstraction, Information Hiding, and
Layering.
Division into Parts.
Encapsulation and Interchangeability.
Interface and Implementation.
The Service View.
Repetition and Recursion.
Composition.
Layers of Specialization.
Multiple Views.
Patterns.
2. Abstract Data Types.
What is a Type?
Classes.
Interfaces and Polymorphism.
Abstract Data Types.
The Fundamental ADTs.
Collection.
Bag.
Set.
Sorted, Comparator and Comparable.
Stack, Queue and Deque.
FindMin and FindNth.
Indexed Collections and Sorting Algorithms.
Map.
Matrix.
3. Algorithms.
Characteristics of Algorithms.
Recipes as Algorithms.
Analyzing Computer Algorithms.
Specification of the Input.
Description of the Result.
Instruction Precision.
Time to Execute.
Space Utilization.
Recursive Algorithms.
4. Execution-Time Measurement.
Algorithmic Analysis and Big-Oh Notation.
Execution Time of Programming Constructs.
Constant Time.
Simple Loops.
Nested Loops.
While Loops.
Function Calls.
Summing Algorithmic Execution Times.
The Importance of Fast Algorithms.
Benchmarking and Actual Execution
Times.
5. Increasing Confidence in Correctness.
Program Proofs.
Invariants.
Analyzing Loops.
Asserting That the Outcome is Correct.
Progress Toward an Objective.
Manipulating Unnamed Quantities.
Function Calls.
Recursive Algorithms.
Program Testing.
6. Vectors.
The Vector Data Structure.
Enumeration.
Application—Silly Sentences.
Application—Memory Game.
Application—Shell Sort.
A Visual Vector.
7. Sorting Vectors.
Divide and Conquer.
Binary Search.
Sorted Vectors.
Merge Sort.
Partitioning.
The Pivot Algorithm.
Finding the nth Element.
Quick Sort.
8. Linked Lists.
Varieties of Linked Lists.
LISP-Style Lists.
The LinkedList Abstraction.
Application—Asteroids Game.
Application—Infinite-Precision Integers.
9. List Variations.
Sorted Lists.
Fast Merge.
Execution Timings for Merge Operations.
Self-Organizing Lists.
Skip Lists.
10. Stacks.
The Stack ADT.
Checking for Balanced Parentheses.
Towers of Hanoi, Revisited.
A Four-Function Calculator.
A Solitaire Program.
Implementation of the Stack Abstraction.
11. Deques.
A Fractal Snowflake.
Depth- and Breadth-First Search.
An Implementation: The IndexedDeque.
12. Queues.
The Queue ADT.
The Caterpillar Game.
A Pastry Factory Simulation.
Implementation of the Queue Abstraction.
A Vector-Based Queue.
The Ring Buffer Queue.
Piped Input/Output Streams.
13. Trees.
Binary Trees.
Vector Implementation.
Dynamic Memory Implementation.
Application—Guess the Animal Game.
Tree Traversals.
Postorder Tree Traversal.
Preorder Tree Traversal.
In-Order Tree Traversal.
Level-Order Tree Traversal.
Euler Tours.
Binary Tree Representation of General
Trees.
14. Binary Search Trees.
The Importance of Balance.
AVL Trees.
Application—Tree Sort.
15. Priority Queues.
The Priority Queue ADT.
Heaps.
Skew Heaps.
Application—Discrete Event-Driven
Simulation.
A Framework for Simulations.
Ice Cream Store Simulation.
16. Hash Tables.
Hash Functions.
Hash Functions.
Hash Functions in the Java Standard
Library.
Collision Resolution.
Hash Table Sorting Algorithms.
Counting Sort.
Radix Sorting.
Open-Address Hashing.
The Hashtable Data Type.
Application—Ranking Poker Hands.
17. Maps.
Example Programs.
Silly Sentence Generation, Revisited.
An Address Database.
A Concordance.
An Implementation.
Searching Problems and Maps.
18. Sets.
Changing a Bag into a Set.
Set Union, Intersection, and Differences.
Sorted List Sets.
Application—A Spelling Checker.
The Union-Find Problem.
The BitSet Abstraction.
Application—Prime Number Sieve.
19. Matrices.
Java Matrices.
Application—Rain Game.
Binary Matrices.
Application—The Game of Life.
Sparse Vectors.
An Application—(Almost) Infinitely
Large Hash Tables.
Sparse Matrices.
Noninteger Keys.
20. Graphs.
Adjacency-Matrix Representation.
Edge-List Representation.
Weighted-Graph Representation.
Weighted-Adjacency Matrix.
Floyd's Algorithm.
Weighted-Edge List Representation.
Dijkstra's Algorithm.
Other Graph Problems.
Topological Sorting.
Depth-First Search Spanning Tree.
Problem-The Traveling Salesman.
Appendix A. Java Syntax.
Program Structure.
Packages.
Import Declarations.
Class Declaration.
Interface Declaration.
Method Declaration.
Constructors.
Data Field Declaration.
Statements.
Declaration Statement.
Assignment Statement.
Procedure Calls.
If Statement.
Switch Statement.
While Statement.
For Statement.
Return Statement.
Throw Statement.
Try Statement.
Expressions.
Literal.
Variable.
Data Field and Method Access.
Operators.
Object Creation.
Arrays.
Files.
Appendix B. Import Libraries.
Appendix C. Data Structures in
the Java Standard Library.
Collection.
Enumerators and Iterators.
Vectors.
Lists.
Stack, Queue, and Deque.
Priority Queue.
Binary Search Tree.
Hash Tables.
Set.
Map.
Bibliography.
Index. |
