Using Java(TM) 1.1, Professor Thomas A. Standish teaches the fundamentals of data structures and algorithms. With this exciting new language, 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. Highlights Reviews the fundamentals of object-oriented programming and Java in Chapter 2 and Appendix A, allowing students with no prior knowledge of Java to get up and running quickly. Creates a Java applet with a simple GUI in Chapter 2. Covers recursion early and carefully in Chapter 4 to help students grasp this challenging concept. Includes an introduction to modularity and data abstraction concepts in Chapter 5, and coverage of key software engineering concepts and skills in Appendix C. Contains common pitfall sections at the end of each chapter to help students recognize and avoid potential dangers.
Author(s): Thomas A. Standish
Publisher: Addison-Wesley
Year: 1998
Language: English
Pages: 555
City: Reading, MA
Front Cover
Preface
Prerequisites for the Java Programming Language
The Approach to Mathematical Foundations and Software Engineering
Supplements
Acknowledgments
Contents
1 Preparing for the Journey
1.1 Where Are We Going?
Plan for the Chapter
1.2 Blending Mathematics, Science, and Engineering
1.3 The Search for Enduring Principles in Computer Science
1.4 Principles of Software System Structure
1.5 Efficiency and Tradeoffs
1.6 Software Engineering Principles
1.7 Our Approach to Mathematics
1.8 Some Notes on Programming Notation
1.8 Exercises
1.9 Preview of Coming Attractions
Chapter Summary
2 Introduction to Object-Oriented Programming
2.1 Introduction and Motivation
Plan for the Chapter
2.2 A Rectangle Drawing Applet
2.2 Review Questions
2.2 Exercises
2.3 The DrawShapes Applet
2.3 Review Questions
2.3 Exercise
2.4 Drawing Some Conclusions
2.4 Review Questions
2.4 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
3 Linked Data Representations
3.1 Introduction and Motivation
Plan for the Chapter
3.2 What are Pointers? The Basic Intuition
Two Examples of Linked Representations
3.3 Using Java's Implicit Pointers - The Rudiments
3.3 Review Questions
3.3 Exercise
3.4 Pointer Diagramming Notation
3.4 Review Questions
3.4 Exercises
3.5 Linear Linked Lists
Inserting a New Second Node on a List
Declaring Java Classes for Linked Lists
Searching for an Item on a List
Deleting the Last Node of a List
Inserting a New Last Node on a List
How to Print a List
Getting Our Act Together
Where to Go From Here?
3.5 Review Questions
3.5 Exercises
3.6 Other Linked Data Structures
3.6 Review Questions
3.6 Exercise
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
4 Introduction to Recursion
4.1 Introduction and Motivation
Plan for the Chapter
4.2 Thinking Recursively
How to Make Things Add Up Recursively
Call Trees and Traces
Multiplying Things Recursively
Reversing Lists and Arrays
Reversing Arrays
The General Idea
4.2 Review Questions
4.2 Exercises
4.3 Common Pitfall - Infinite Regresses
4.3 Review Questions
4.3 Exercise
4.4 A Recursive Algorithm with Exponential Running Time
Towers of Hanoi
4.4 Review Questions
4.4 Exercise
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
5 Modularity and Data Abstraction
5.1 Introduction and Motivation
Plan for the Chapter
5.2 Priority Queues - An Abstract Data Type
A Priority Queue ADT Interface
5.2 Review Questions
5.2 Exercise
5.3 Two Implementations for Priority Queues
Implementing Priority Queues Using Sorted Linked Lists
Implementing Priority Queues Using Unsorted Arrays
5.3 Review Questions
5.3 Exercise
5.4 Plugging In New Kinds of Objects into Priority Queues
5.4 Review Questions
5.4 Exercise
5.5 Modularity and Information Hiding in Program Design
5.5 Review Questions
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
6 Linear Data Structures - Stacks and Queues
6.1 Introduction and Motivation
Plan for the Chapter
6.2 Some Background on Stacks
6.2 Review Questions
6.2 Exercises
6.3 ADTs for Stacks and Queues
Interfaces for Stack and Queue Classes
6.3 Review Questions
6.3 Exercises
6.4 Using the Stack ADT to Check for Balanced Parentheses
6.4 Review Questions
6.4 Exercises
6.5 Using the Stack ADT to Evaluate Postfix Expressions
6.5 Review Questions
6.5 Exercises
6.6 Implementing the Stack ADT
The Sequential Stack Representation
The Linked Stack Representation
6.6 Review Questions
6.6 Exercises
6.7 How Java Implements Recursive Method Calls Using Stacks
6.7 Review Question
6.7 Exercise
6.8 Implementations of the Queue ADT
Sequential Queue Representations
Linked Queue Representations
Comparing Linked and Sequential Queue Representations
6.8 Review Questions
6.8 Exercises
6.9 More Queue Applications
Queues in Operating Systems
Using Queues in Simulation Experiments
6.9 Review Questions
6.9 Exercise
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
7 Lists, Strings, and Dynamic Memory Allocation
7.1 Introduction and Motivation
Plan for the Chapter
7.2 Lists
A List ADT
Sequential List Representations
The One-Way Linked List Representation
Comparing Sequential and Linked List Representations
Other Linked List Representations
Circular Linked Lists
Two-Way Linked Lists
Linked Lists with Header Nodes
7.2 Review Questions
7.2 Exercises
7.3 Generalized Lists
7.3 Review Questions
7.3 Exercises
7.4 Applications of Generalized Lists
7.4 Review Questions
7.4 Exercises
7.5 Strings
Read-Only Strings in Java
String Buffers in Java
String Representations in Text Files and Word Processors
7.5 Review Questions
7.5 Exercises
7.6 Dynamic Memory Allocation
Available Space Lists and Garbage Collection
Heaps and Dynamic Memory Allocation
First-Fit
Best-Fit
Fragmentation and Coalescing
Compacting to Deal with Allocation Failures
Comparing Uses of Heaps in Applications
Reference Counts
7.6 Review Questions
7.6 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
8 Trees and Graphs
8.1 Introduction and Motivation
Plan for the Chapter
8.2 Trees - Basic Concepts and Terminology
8.2 Review Questions
8.2 Exercises
8.3 Binary Trees
8.3 Review Questions
8.3 Exercises
8.4 A Sequential Binary Tree Representation
8.4 Review Questions
8.4 Exercises
8.5 An Application - Heaps and Priority Queues
Converting to the Sequential Representation
Some Facts About the Performance of Heap Operations
8.5 Review Questions
8.5 Exercises
8.6 Traversing Binary Trees
Traversals Using the Linked Representation of Binary Trees
8.6 Review Questions
8.6 Exercises
8.7 Binary Search Trees
Some Known Performance Advantages of Binary Search Trees
8.7 Review Questions
8.7 Exercises
8.8 AVL Trees and Their Performance
Building an AVL Tree Using Insertions and Rotations
Balance Factors and Comments on Rotation Algorithms
Known Performance Results for AVL Trees
8.8 Review Questions
8.8 Exercises
8.9 Two-Three Trees
B-Trees - A Generalization of 2-3 Trees
8.9 Review Questions
8.9 Exercises
8.10 Tries
8.10 Review Questions
8.10 Exercises
8.11 An Application - Huffman Codes
8.11 Review Questions
8.11 Exercises
8.12 Graphs - Basic Concepts and Terminology
Some Formal Definitions
Paths, Cycles, and Adjacency
Connectivity and Components
Adjacency Sets and Degrees
8.12 Review Questions
8.12 Exercises
8.13 Graph Representations
8.13 Review Questions
8.13 Exercises
8.14 Graph Searching
8.14 Review Questions
8.14 Exercises
8.15 Topological Ordering
8.15 Review Questions
8.15 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
9 Hashing and the Table ADT
9.1 Introduction and Motivation
Plan for the Chapter
9.2 The Table ADT
9.2 Review Questions
9.2 Exercises
9.3 Introduction to Hashing by Simple Examples
9.3 Review Questions
9.3 Exercises
9.4 Collisions, Load Factors, and Clusters
Collisions
The von Mises Probability Argument
Load Factors and Clustering
9.4 Review Questions
9.4 Exercises
9.5 Algorithms for Hashing by Open Addressing
Two Examples of Primary Clustering and Its Absence
Ensuring That Probe Sequences Cover the Table
Performance Formulas
Comparing Theoretical and Empirical Results
9.5 Review Questions
9.5 Exercises
9.6 Choosing a Hash Function
The Division Method
Other Hash Function Methods
9.6 Review Questions
9.6 Exercises
9.7 Comparison of Searching Methods Using the Table ADT
9.7 Review Questions
9.7 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
10 Sorting
10.1 Introduction and Motivation
Plan for the Chapter
10.2 Laying Some Groundwork
10.2 Review Questions
10.2 Exercise
10.3 Priority Queue Sorting Methods
Some Preliminary Assumptions
Priority Queue Sorting
SelectionSort
HeapSort
10.3 Review Questions
10.3 Exercise
10.4 Divide-and-Conquer Methods
MergeSort
QuickSort
10.4 Review Questions
10.4 Exercises
10.5 Methods That Insert Keys and Keep Them Sorted
lnsertionSort
TreeSort
10.5 Review Questions
10.5 Exercises
10.6 O(n) Methods - Address Calculation Sorting
ProxmapSort
RadixSort
10.6 Review Questions
10.6 Exercises
10.7 Other Methods
ShellSort
BubbleSort
10.7 Review Questions
10.7 Exercises
10.8 Comparison and Perspective
Some Simple Wisdom
10.8 Review Questions
10.8 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Chapter Summary
Appendices
Appendix A: A Review of Some Java Basics
A.1 Getting Oriented Toward Java
Plan for the Appendix
A.2 Identifiers, Reserved Words, Names, and Variables
A.2 Review Questions
A.2 Exercises
A.3 Data Types in Java
Reference Data Types in Java
A.3 Review Questions
A.3 Exercises
A.4 Java Operators and Expressions
Operator Precedence and Associativity in Java
A.4 Review Questions
A.4 Exercises
A.5 Control Flow in Java
Selection Statements
Repetition-Statements
Break-, Continue-, and Return-Statements
A.5 Review Questions
A.5 Exercises
A.6 Classes, Methods, and Objects in Java
A.6 Review Questions
A.6 Exercise
A.7 Importing Packages in Java
A.7 Review Questions
A.7 Exercise
A.8 Comments in Java
A.8 Review Questions
A.8 Exercise
References for Further Study
Appendix B: The Language of Efficiency
B.1 Introduction and Motivation
Plan for the Appendix
B.2 What Do We Use for a Yardstick?
B.2 Review Questions
B.2 Exercise
B.3 The Intuition Behind O-Notation
What Is Covered Elsewhere
B.3 Review Questions
B.3 Exercises
B.4 O-Notation - Definition and Manipulation
An Example of a Formal Proof of O-Notation
Practical Shortcuts for Manipulating O-Notation
B.4 Review Questions
B.4 Exercises
B.5 What O-Notation Doesn't Tell You
B.5 Review Questions
B.5 Exercises
References for Further Study
Appendix Summary
Appendix C: Software Engineering Concepts
C.1 Introduction and Motivation
Plan for the Appendix
C.2 Object-Oriented Design and Top-Down Programming
Do You Have a Winning Ticket?
Choosing a Data Representation for the Table
A Second Refinement
C.2 Review Questions
C.2 Exercises
C.3 Proving Programs Correct
A Subtle Bug
A Bit of Formal Logic
C.3 Review Questions
C.3 Exercises
C.4 Transforming and Optimizing Programs
C.4 Review Questions
C.4 Exercise
C.5 Testing Programs
Bottom-Up Testing
Unit Testing, Formatted Debugging Aids, and Test Drivers
Integration Testing
Acceptance Testing and Regression Testing
Top-Down Testing and Stubs
Test Plans
Comparing the Roles of Testing and Verification
C.5 Review Questions
C.5 Exercises
C.6 The Philosophy of Measurement and Tuning
Comparing Some Methods for Binary Searching
C.6 Review Questions
C.6 Exercises
C.7 Software Reuse and Bottom-Up Programming
C.7 Review Questions
C.7 Exercise
C.8 Program Structuring and Documentation
Programming Style Disciplines
Documentation
C.8 Review Questions
C.8 Exercises
Pitfalls
Tips and Techniques
References for Further Study
Appendix Summary
Index
Back Cover
