Classic Data Structures in Java

Timothy Budd

Classic Data Structures in Java

買這商品的人也買了...

相關主題

商品描述


Description

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.

Back to Top


Appropriate Courses

Java Data Structures/CS2.

Back to Top


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.
Back to Top


Table Of Contents

(All chapters conclude with "Chapter Summary", "Further Information", "Study Questions", "Exercises", and "Programming Projects".)
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.


Back to Top

類似商品