Always Learning

Classic Data Structures in Java
Timothy Budd, Oregon State University

ISBN-10: 0201700026
ISBN-13:  9780201700022

Publisher:  Addison-Wesley
Copyright:  2001
Format:  Paper; 593 pp
Published:  10/19/2000
Status: Instock


Customers outside the U.S., click here.


Print this content

In this section:


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.


Features

  • An object-oriented mindset is applied throughout. Pg.___
  • The clear separation between ADT (interface) and implementation is emphasized throughout. Pg.___
  • 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. Pg.___
  • 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. Pg.___
  • Important software patterns are highlighted, and the use of patterns is emphasized from the beginning. Pg.___
  • 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. Pg.___
  • Sidebars are included throughout so that readers can then peruse additional information as they choose. Pg.___
  • 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. Pg.___
  • An appendix with an overview of Java syntax makes this book appropriate for readers without a Java background. Pg.___
  • 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.


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

Print this content

In this section:

Back to top

Print this content

In this section:

Solutions Manual
Budd
©2001  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321357310  |  ISBN-13: 9780321357311

Show Downloadable Files
 | More Info

Online Source Code
Budd
©2001  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321357094  |  ISBN-13: 9780321357090

Show Downloadable Files
 | More Info

Back to top

Log in to the Instructor Resource Center

Login name: 

  Password: 

Forgot login/password?  |  Need to redeem an access code?

        

Instructor Resource Center File Download

This work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from this site should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

Cancel     I accept, proceed with download

Print this content

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.

Back to top