PART ONE INTRODUCTION 3
1 PRELIMINARIES 3
1.1 ADTs:ABSTRACTION AND ENCAPSULATION 4
Abstraction 5
Reuse and Encapsulation 7
ADTs,OOP,and Things to Come 7
1.2 ADT:INTEGERARRAY 8
1.3 IMPLEMENTATION 13
Defining Integer Arrays 13
1.4 COMPUTER SCIENCE INTERLUDE:ASSERTIONS AND VERIFICATION 18
Assertions 18
Verification 19
1.5 APPLICATION:MULTIPRECISION ARITHMETIC 23
Declaring the Number Class 25
Defining the Number Class 27
1.6 SUMMARY 36
1.7 EXERCISES 36
1.8 EXPLORATIONS 44
Representation of Integers 44
Bit Vectors 45
PART TWO LINEAR STRUCTURES 45
2 LISTS 49
2.1 ADT:LIST 50
Parametrized Classes 53
2.2 IMPLEMENTATIONS 55
Arrays 55
Linked Lists 63
2.3 COMPARING IMPLEMENTATIONS 75
Space 75
Time 76
Comprehensibility 77
Trade-Offs 78
2.4 COMPUTER SCIENCE INTERLUDE:MEASURES OF EFFICIENCY 78
Algorithms 79
Big-O 81
Order Arichmetic 83
Timing Functions 85
2.5 APPLICATION:MEMORY MANAGEMENT 89
Allocation 92
Deallocation 94
Compaction 98
2.6 SUMMARY 100
2.7 EXERCISES 100
2.8 EXPLORATIONS 111
Sorted Lists 111
Self-Organizing Lists 115
3 STRINGS 117
3.1 ADT:STRING 117
(S)trings,(s)trings,and Arrays 118
Lexicographic Order 121
Declaring Strings 122
3.2 IMPLEMENTATION 124
Efficiency 130
3.3 APPLICATION:STRING MATCHING 132
3.4 SUMMARY 139
3.5 EXERCISES 140
3.6 EXPLORATIONS 144
Advanced Pattern Matching 144
4 OTHER LINEAR STRUCTURES 146
4.1 ADT:STACK 146
4.2 IMPLEMENTATIONS OF STACK 151
Efficiency Issues 151
Sacks as a Derived Class 152
Sacks from Scratch 153
4.3 APPLICATION:POSTFIX ARITHMETIC 154
4.4 ADT:QUEUE 157
4.5 IMPLEMENTATIONS OF QUEUE 158
Queues as Linked Lists 159
Circular Arrays and Queues 160
4.6 APPLICATION(CONTINUED):INFIX TO POSTFIX CONVERSION 163
Verification 166
4.7 SUMMARY 166
4.8 EXERCISES 167
4.9 EXPLORATIONS 173
The Electronic Labyrintn 173
Operating System Simulation 178
PART THREE NONLINEAR STRUCTURES 178
5 RECURSION 183
5.1 RECURSIVE ALGORITHMS 183
Induction and Recursion 190
5.2 TIMING RECURSIVE ALGORITHMS 191
5.3 COMPUTER SCIENCE INTERLUDE:DESIGN OF ALGORITHMS 196
5.4 RECURSIVE DATA STRUCTURES 202
General Lists and LISP 204
5.5 SUMMARY 211
5.6 EXERCISES 212
5.7 EXPLORATIONS 219
Quicksort 219
6 TREES 223
6.1 THE STRUCTURE OF TREES 224
6.2 ADT:BINARYTREE 228
6.3 BINARY TREE TRAVERSALS 231
6.4 IMPLEMENTATION OF BINARYTREE 236
6.5 COMPUTER SCIENCE INTERLUDE:PARSE TREES 240
6.6 DATA-ORDERED BINARY TREES 242
Binary Search Trees 244
Application:Treesort 251
6.7 SUMMARY 252
6.8 EXERCISES 253
6.9 EXPLORATIONS 257
Threaded Trees 257
Preamble:Tree Applications 259
Huffman Codes 261
Tries 265
7 SPECIALIZED TREES 268
7.1 BALANCED TREES 269
AVL Trees 270
Efficiency and Verification 277
7.2 B-TREES 277
k-ary Trees,Again 278
B-Trees Explained 279
Application:External Storage 289
7.3 SUMMARY 293
7.4 EXERCISES 294
8 GRAPHS AND DIGRAPHS 297
8.1 ADT:GRAPH 298
8.2 IMPLEMENTATIONS OF GRAPH 302
Adjacency Matrices 302
Adjacency Lists and Edge Lists 305
8.3 GRAPH TRAVERSALS 311
Depth-First Traversals 311
Breadth-First Traversals 312
Spanning Trees 314
8.4 APPLICATION:MINIMUM SPANNING TREES 317
8.5 DIRECTED GRAPHS 319
Application:Cheapest Paths 320
8.6 COMPUTER SCIENCE INTERLUDE:COMPUTATIONAL COMPLEXITY 326
8.7 SUMMARY 330
8.8 EXERCISES 331
8.9 EXPLORATIONS 336
Topological Sorting 336
Counting Paths 338
9 UNORDERED COLLECTION 342
9.1 ADT:SET 342
9.2 IMPLEMENTATIONS OF SET 345
Bit Vectors 345
Sets Represented by Lists 348
9.3 ADT:DICTIONARY 352
Associations 352
9.4 HASHING 356
Open Hashing 362
Time and Space Estimates 363
9.5 APPLICATION:A PROBABILISTIC SPELLING CHECKER 366
9.6 ADT:PRIORITYQUEUE 369
Application:Heapsort 375
9.7 SUMMARY 376
9.8 EXERCISES 377
9.9 EXPLORATIONS 380
Hashing,Coninued 380
The Disjoint Set ADT 383
Tree Representations of Disjoint Set 384
Application:Minimum Spanning Trees,Revisited 389
10 TRAVESTY:PUTTING IT ALL TOGETHER 391
10.1 THE PROBLEM 391
10.2 THE SOLUTIONS 396
Arrays 397
Hashing 401
Tries 408
A Guest Author 416
10.3 APPLICATIONS 416
Reactive Keyboards 417
Coding,Once Again 418
10.4 SUMMARY 419
10.5 EXERCISES 420
10.6 EXPLORATIONS 422
Long Strings 422
APPENDIX A:A Pascal-C++ Dictionary 425
A.1 Information 426
A.2 Program Structure 428
A.3 Statements 430
A.4 Compound Data Types 434
A.5 Pointers and References 435
A.6 Two Sample Programs 437
APPENDIX B:Topics in Mathematics 444
B.1 Exponential and Logarithmic Functions 444
B.2 Induction 449
B.3 Counting Techniques 451
B.4 Exercises 455
APPENDIX C:Random Numbers and Simulation 459
C.1 RandomNumbers 460
C.2 Probability Distributions 462
C.3 Selection Algorithms 469
C.4 Exercises 473
APPENDIX D:Specifications of the ADTs Used in the Text 475
Index 487