About the Book
Using Java 1.1, this book teaches
the fundamentals of data structures and algorithms. With this exciting
new language, Tim Standish takes a fresh look at the subject matter. New
challenges arise any time a new language is used, and the author meets
these challenges. For example, although Java is a language without explicit
pointers, this book offers pointer diagrams to help students visualize,
reason about, and understand this major Data Structures topic. Standish's
clear presentation helps readers tie the many concepts of data structures
together with recurring themes. Central ideas-such as modularity, levels
of abstraction, efficiency, and tradeoffs-serve as integrators in the book
in order to tie the material together conceptually and to reveal its underlying
unity and interrelationships.
Features
-
Starts with introduction to OO Programming,
allowing any language or programming paradigm to be used in CS1.
-
Covers Software Engineering in a 70-page appendix,
and accompanying lab manual. Basic principles are introduced early.
-
Assumes less sophisticated math background
of students but offers sophisticated math ideas in Appendix B.
Related
Books
Data Structures - Programming
Courses (Data Structures)
Table of Contents
1. Preparing for the Journey.
Where Are We Going?
Blending Mathematics, Science, and
Engineering.
The Search for Enduring Principles
in Computer Science.
Principles of Software System Structure.
Efficiency and Tradeoffs.
Software Engineering Principles.
Our Approach to Mathematics.
Some Notes on Programming Notation.
Preview of Coming Attractions.
2. Introduction to Object-Oriented
Programming.
A Rectangle Drawing Applet.
The DrawShapes Applet.
Drawing Some Conclusions.
3. Linked Data Representations.
What are Pointers? The Basic Intuition.
Using Java’s Implicit Pointers — The
Rudiments.
Pointer Diagramming Notation.
Linear Linked Lists.
Other Linked Data Structures.
4. Introduction to Recursion.
Thinking Recursively.
Common Pitfall — Infinite Regresses.
A Recursive Algorithm with Exponential
Running Time.
5. Modularity and Data Abstraction.
Priority Queues — An Abstract Data
Type.
Two Implementations for Priority Queues.
Plugging in New Kinds of Objects into
Priority Queues.
Modularity and Information Hiding
in Program Design.
6. Linear Data Structures — Stacks
and Queues.
Some Background on Stacks.
ADTs for Stacks and Queues.
Using the Stack ADT to Check for Balanced
Parentheses.
Using the Stack ADT to Evaluate Postfix
Expressions.
Implementing the Stack ADT.
How Java Implements Recursive Method
Calls Using Stacks.
Implementations of the Queue ADT.
More Queue Applications.
7. Lists, Strings, and Dynamic Memory
Allocation.
Lists.
Generalized Lists.
Applications of Generalized Lists.
Strings.
Dynamic Memory Allocation.
8. Trees and Graphs.
Trees — Basic Concepts and Terminology.
Binary Trees.
A Sequential Binary Tree Representation.
An Application — Heaps and Priority
Queues.
Traversing Binary Trees.
Binary Search Trees.
AVL Trees and Their Performance.
Two-Three Trees.
Tries.
An Application — Huffman Codes.
Graphs — Basic Concepts and Terminology.
Graph Representations.
Graph Searching.
Topological Ordering.
9. Hashing and the Table ADT.
The Table ADT.
Introduction to Hashing by Simple
Examples.
Collisions, Load Factors, and Clusters.
Algorithms for Hashing by Open Addressing.
Choosing a Hash Function.
Comparison of Searching Methods Using
the Table ADT.
10. Sorting.
Laying Some Groundwork.
Priority Queue Sorting Methods.
Divide-and-Conquer Methods.
Methods That Insert Keys and Keep
Them Sorted.
O(n) Methods — Address Calculation
Sorting.
Other Methods.
Comparison and Perspective.
Appendix A - A Review of Some Basic
Java Features.
Appendix B - The Language of Efficiency.
Appendix C - Software Engineering
Concepts. |
