|
Preface |
|
| 1 |
Introduction |
|
1.1 |
Historical background |
|
1.2 |
Algorithms and programs |
|
1.3 |
Abstract data types and data structures |
|
|
Summary |
|
|
Exercises |
|
| 2 |
Algorithms |
|
2.1 |
Principles of algorithms |
|
2.2 |
Efficiency of algorithms |
|
2.3 |
Complexity of algorithms |
|
2.4 |
Recursive algorithms |
|
|
Summary |
|
|
Exercises |
|
| 3 |
The Array Data Structure |
|
3.1 |
Arrays |
|
3.2 |
Insertion |
|
3.3 |
Deletion |
|
3.4 |
Searching |
|
3.5
|
Merging
|
|
3.6
|
Sorting
|
|
|
Summary
|
|
|
Exercises |
|
| 4 |
Linked-List Data Structures |
|
4.1 |
Linked lists |
|
4.2 |
Insertion |
|
4.3 |
Deletion |
|
4.4 |
Searching |
|
4.5 |
Merging |
|
4.6 |
Sorting |
|
|
Summary
|
|
|
Exercises |
|
| 5 |
Abstract Data Types |
|
5.1 |
Data types |
|
5.2
|
Abstract data types
|
|
5.3 |
Abstract data type design |
|
5.4 |
String abstract data types |
|
5.5 |
Collection abstract data types |
|
5.6
|
Abstract data types in the
Java class library
|
|
|
Summary |
|
|
Exercises |
|
| 6 |
Stack Abstract Data Types |
|
6.1 |
The concept of a stack |
|
6.2 |
Applications of stacks |
|
6.3 |
A stack abstract data type |
|
6.4 |
Implementation of bounded stacks using arrays |
|
6.5 |
Implementation of unbounded stacks using linked lists |
|
6.6 |
Case study: solving and generating mazes |
|
6.7 |
Run-time organization for object-oriented languages |
|
6.8 |
Case study: the abstract machine TAM |
|
6.9 |
Further reading |
|
|
Exercises |
|
| 7 |
Queue Abstract Data Types |
|
7.1 |
The concept of a queue |
|
7.2 |
Applications of queues |
|
7.3 |
A queue abstract data type |
|
7.4 |
Implementation of bounded queues using arrays |
|
7.5 |
Implementation of unbounded queues using linked lists |
|
7.6 |
Case study: a traffic simulator |
|
|
Summary
|
|
|
Exercises |
|
| 8 |
List Abstract Data Types |
|
8.1 |
The concept of a list |
|
8.2 |
Applications of liststion |
|
8.3 |
A list abstract data type |
|
8.4 |
Iterators |
|
8.5
|
Implementation of bounded lists using arrays
|
|
8.6
|
Implementation of unbounded lists using linked lists
|
|
8.7
|
Lists in the Java class library
|
|
8.8
|
Case study: a videotape manager
|
|
|
Summary
|
|
|
Exercises |
|
| 9 |
Set Abstract Data Types |
|
9.1 |
The concept of a set |
|
9.2 |
Applications of sets |
|
9.3 |
A set abstract data type |
|
9.4 |
Implementation of bounded sets using arrays |
|
9.5
|
Implementation of unbounded sets using linked lists
|
|
9.6
|
Implementation of small-integer sets using boolean
arrays
|
|
9.7
|
Sets in the Java class library
|
|
9.8
|
Case study: an interactive spell-checker
|
|
|
Summary |
|
|
Exercises |
|
|
|
10
|
Binary Tree Data Structures
|
|
10.1
|
Binary trees
|
|
10.2
|
Searching
|
|
10.3
|
Insertion
|
|
10.4
|
Deletion
|
|
10.5
|
Traversal
|
|
10.6
|
Merging
|
|
10.7
|
Implementation of unbounded sets using binary search
trees
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
11
|
Map Abstract Data Types
|
|
11.1
|
The concept of a map
|
|
11.2
|
Applications of maps
|
|
11.3
|
A map abstract data type
|
|
11.4
|
Implementation of small-integer-key maps using key-indexed
arrays
|
|
11.5
|
Implementation of bounded maps using arrays
|
|
11.6
|
Implementation of unbounded maps using linked lists
|
|
11.7
|
Implementation of unbounded maps using binary search
trees
|
|
11.8
|
Maps in the Java class library
|
|
11.9
|
Case study: a student record system
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
12
|
Hash-Table Data Structures
|
|
12.1
|
Hash tables
|
|
12.2
|
Closed-bucket hash tables
|
|
12.3
|
Open-bucket hash tables
|
|
12.4
|
Implementations of sets using hash tables
|
|
12.5
|
Implementations of maps using hash tables
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
13
|
Priority-Queue Abstract
Data Types
|
|
13.1
|
The concept of a priority queue
|
|
13.2
|
Applications of priority queues
|
|
13.3
|
A priority-queue abstract data type
|
|
13.4
|
Implementations of priority queues using linked lists
|
|
13.5
|
The heap data structure
|
|
13.6
|
Implementation of priority queues using heaps
|
|
13.7
|
Case study: an improved traffic simulator
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
14
|
Tree Abstract Data Types
|
|
14.1
|
The concept of a tree
|
|
14.2
|
Applications of trees
|
|
14.3
|
A tree abstract data type
|
|
14.4
|
A linked implementation of trees
|
|
14.5
|
Specialized tree abstract data types
|
|
14.6
|
Case study: game playing
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
15
|
Graph Abstract Data Types
|
|
15.1
|
The concept of a graph
|
|
15.2
|
Applications of graphs
|
|
15.3
|
Graph abstract data types
|
|
15.4
|
Edge-set representation of graphs
|
|
15.5
|
Adjacency-set representation of graphs
|
|
15.6
|
Adjacency-matrix representation of graphs
|
|
15.7
|
Graph traversal
|
|
15.8
|
Topological sort
|
|
15.9
|
Case study: material requirements planning
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
16
|
Balanced Search Tree Data
Structures
|
|
16.1
|
AVL-trees
|
|
16.2
|
B-trees
|
|
|
Summary
|
|
|
Exercises
|
|
|
|
17
|
Conclusion
|
|
17.1
|
Abstract data types and object-oriented design
|
|
17.2
|
Abstract data types as reusable software components
|
|
17.3
|
Homogeneous and heterogeneous collections
|
|
17.4
|
Extending Java with parameterized classes
|
|
17.5
|
Case study: a student record system revisited
|
|
|
Summary
|
|
|
Exercises
|
|
| Appendices |
|
| A |
Summary of Mathematics for Algorithm Analysis |
|
A.1
|
Powers
|
|
A.2
|
Logarithms
|
|
A.3
|
Series summations
|
|
A.4
|
Recurrences
|
|
A.5
|
O-notation
|
|
| B |
Summary of Java |
|
B.1 |
Basics
|
|
B.2 |
Classes
|
|
B.3 |
Interfaces
|
|
B.4 |
Packages
|
|
B.5 |
Exceptions
|
|
B.6 |
Inner classes and inner interfaces
|
|
| C |
Summary of the Java Collections Framework |
|
C.1 |
Collections
|
|
C.2 |
Lists
|
|
C.3 |
Sets
|
|
C.4
|
Maps
|
|
C.5
|
Orderings
|
|
C.6
|
Iterators
|
|
|
Further Reading |
|
|
Bibliographc Notes
|
|
|
Bibliography
|
|
|
Index |