PART ONE INTRODUCTION

1 PRELIMINARIES

1.1 ADTs:ABSTRACTION AND ENCAPSULATION

Abstraction

Reuse and Encapsulation

ADTs,OOP,and Things to Come

1.2 ADT:INTEGERARRAY

1.3 IMPLEMENTATION

Defining Integer Arrays

1.4 COMPUTER SCIENCE INTERLUDE:ASSERTIONS AND VERIFICATION

Assertions

Verification

1.5 APPLICATION:MULTIPRECISION ARITHMETIC

Declaring the Number Class

Defining the Number Class

1.6 SUMMARY

1.7 EXERCISES

1.8 EXPLORATIONS

Representation of Integers

Bit Vectors

PART TWO LINEAR STRUCTURES

2 LISTS

2.1 ADT:LIST

Parametrized Classes

2.2 IMPLEMENTATIONS

Arrays

Linked Lists

2.3 COMPARING IMPLEMENTATIONS

Space

Time

Comprehensibility

Trade-Offs

2.4 COMPUTER SCIENCE INTERLUDE:MEASURES OF EFFICIENCY

Algorithms

Big-O

Order Arichmetic

Timing Functions

2.5 APPLICATION:MEMORY MANAGEMENT

Allocation

Deallocation

Compaction

2.6 SUMMARY

2.7 EXERCISES

2.8 EXPLORATIONS

Sorted Lists

Self-Organizing Lists

3 STRINGS

3.1 ADT:STRING

(S)trings,(s)trings,and Arrays

Lexicographic Order

Declaring Strings

3.2 IMPLEMENTATION

Efficiency

3.3 APPLICATION:STRING MATCHING

3.4 SUMMARY

3.5 EXERCISES

3.6 EXPLORATIONS

Advanced Pattern Matching

4 OTHER LINEAR STRUCTURES

4.1 ADT:STACK

4.2 IMPLEMENTATIONS OF STACK

Efficiency Issues

Sacks as a Derived Class

Sacks from Scratch

4.3 APPLICATION:POSTFIX ARITHMETIC

4.4 ADT:QUEUE

4.5 IMPLEMENTATIONS OF QUEUE

Queues as Linked Lists

Circular Arrays and Queues

4.6 APPLICATION(CONTINUED):INFIX TO POSTFIX CONVERSION

Verification

4.7 SUMMARY

4.8 EXERCISES

4.9 EXPLORATIONS

The Electronic Labyrintn

Operating System Simulation

PART THREE NONLINEAR STRUCTURES

5 RECURSION

5.1 RECURSIVE ALGORITHMS

Induction and Recursion

5.2 TIMING RECURSIVE ALGORITHMS

5.3 COMPUTER SCIENCE INTERLUDE:DESIGN OF ALGORITHMS

5.4 RECURSIVE DATA STRUCTURES

General Lists and LISP

5.5 SUMMARY

5.6 EXERCISES

5.7 EXPLORATIONS

Quicksort

6 TREES

6.1 THE STRUCTURE OF TREES

6.2 ADT:BINARYTREE

6.3 BINARY TREE TRAVERSALS

6.4 IMPLEMENTATION OF BINARYTREE

6.5 COMPUTER SCIENCE INTERLUDE:PARSE TREES

6.6 DATA-ORDERED BINARY TREES

Binary Search Trees

Application:Treesort

6.7 SUMMARY

6.8 EXERCISES

6.9 EXPLORATIONS

Threaded Trees

Preamble:Tree Applications

Huffman Codes

Tries

7 SPECIALIZED TREES

7.1 BALANCED TREES

AVL Trees

Efficiency and Verification

7.2 B-TREES

k-ary Trees,Again

B-Trees Explained

Application:External Storage

7.3 SUMMARY

7.4 EXERCISES

8 GRAPHS AND DIGRAPHS

8.1 ADT:GRAPH

8.2 IMPLEMENTATIONS OF GRAPH

Adjacency Matrices

Adjacency Lists and Edge Lists

8.3 GRAPH TRAVERSALS

Depth-First Traversals

Breadth-First Traversals

Spanning Trees

8.4 APPLICATION:MINIMUM SPANNING TREES

8.5 DIRECTED GRAPHS

Application:Cheapest Paths

8.6 COMPUTER SCIENCE INTERLUDE:COMPUTATIONAL COMPLEXITY

8.7 SUMMARY

8.8 EXERCISES

8.9 EXPLORATIONS

Topological Sorting

Counting Paths

9 UNORDERED COLLECTION

9.1 ADT:SET

9.2 IMPLEMENTATIONS OF SET

Bit Vectors

Sets Represented by Lists

9.3 ADT:DICTIONARY

Associations

9.4 HASHING

Open Hashing

Time and Space Estimates

9.5 APPLICATION:A PROBABILISTIC SPELLING CHECKER

9.6 ADT:PRIORITYQUEUE

Application:Heapsort

9.7 SUMMARY

9.8 EXERCISES

9.9 EXPLORATIONS

Hashing,Coninued

The Disjoint Set ADT

Tree Representations of Disjoint Set

Application:Minimum Spanning Trees,Revisited

10 TRAVESTY:PUTTING IT ALL TOGETHER

10.1 THE PROBLEM

10.2 THE SOLUTIONS

Arrays

Hashing

Tries

A Guest Author

10.3 APPLICATIONS

Reactive Keyboards

Coding,Once Again

10.4 SUMMARY

10.5 EXERCISES

10.6 EXPLORATIONS

Long Strings

APPENDIX A:A Pascal-C++ Dictionary

A.1 Information

A.2 Program Structure

A.3 Statements

A.4 Compound Data Types

A.5 Pointers and References

A.6 Two Sample Programs

APPENDIX B:Topics in Mathematics

B.1 Exponential and Logarithmic Functions

B.2 Induction

B.3 Counting Techniques

B.4 Exercises

APPENDIX C:Random Numbers and Simulation

C.1 RandomNumbers

C.2 Probability Distributions

C.3 Selection Algorithms

C.4 Exercises

APPENDIX D:Specifications of the ADTs Used in the Text

Index