PREFACE XV
THE MANAGEMENT OF COMPLEXITY 1
1.1 The Control of Complexity 2
1.2 Abstraction, Information Hiding, and Layering 3
1.3 Division into Parts 6
1.3.1 Encapsulation and Interchangeability 6
1.3.2 Interface and Implementation 7
1.3.3 The Service View 8
1.3.4 Repetition and Recursion 9
1.4 Composition 11
1.5 Layers of Specialization 14
1.6 Multiple Views 16
1.7 Patterns 16
1.8 Chapter Summary 18
Further Information 19
Study Questions 20
Exercises 21
Programming Projects 21
2 ABSTRACT DATA TYPES 23
2.1 What Is a Type? 24
2.1.1 Classes 25
2.1.2 Interfaces and Polymorphism 27
2.2 Abstract Data Types 30
2.3 The Fundamental ADTs 34
2.3.1 Collection 34
2.3.2 Bag 36
2.3.3 Set 37
2.3.4 Sorted, Comparator, and Comparable 38
2.3.5 Stack, Queue, and Deque 39
2.3.6 FindMin and FindNth 41
2.3.7 Indexed Collections and Sorting Algorithms 42
2.3.8 Map 43
2.3.9 Matrix 44
2.4 Chapter Summary 45
Further Information 46
Study Questions 46
Exercises 46
Programming Projects 47
ALGORITHMS 49
3.1 Characteristics of Algorithms 50
3.2 Recipes as Algorithms 52
3.3 Analyzing Computer Algorithms 53
3.3.1 Specification of the Input 54
3.3.2 Description of the Result 56
3.3.3 Instruction Precision 57
3.3.4 Time to Execute 57
3.3.5 Space Utilization 60
3.4 Recursive Algorithms 60
3.5 Chapter Summary 64
Further Information 64
Study Questions 65
Exercises 65
Programming Projects 66
4 EXECUTION-TIME MEASUREMENT 69
4.1 Algorithmic Analysis and Big-Oh Notation 70
4.2 Execution Time of Programming Constructs 71
4.2.1 Constant Time 71
4.2.2 Simple Loops 72
4.2.3 Nested Loops 75
4.2.4 While Loops 77
4.2.5 Function Calls 79
4.3 Summing Algorithmic Execution Times 80
4.4 The Importance of Fast Algorithms 84
4.5 Benchmarking Execution Times 86
4.6 Chapter Summary 90
Further Information 91
Study Questions 91
Exercises 91
Programming Projects 94
INCREASING CONFIDENCE IN CORRECTNESS 97
5.1 Program Proofs 97
5.1.1 Invariants 98
5.1.2 Analyzing Loops 100
5.1.3 Asserting That the Outcome Is Correct 103
5.1.4 Progress toward an Objective 104
5.1.5 Manipulating Unnamed Quantities 105
5.1.6 Function Calls 106
5.1.7 Recursive Algorithms 107
5.2 Program Testing 109
5.3 Chapter Summary 111
Further Information 111
Study Questions 111
Exercises 112
Programming Projects 114
VECTORS 117
6.1 The Vector Data Structure 117
6.2 Enumeration 127
6.3 Application-Silly Sentences 128
6.4 Application-Memory Game 131
6.5 Application-Shell Sort 136
6.6 A Visual Vector 140
6.7 Chapter Summary 144
Further Information 144
Study Questions 144
Exercises 145
Programming Projects 149
SORTING VECTORS | 53
7.1 Divide and Conquer 153
7.1.1 Binary Search 155
7.2 SortedVectors 158
7.3 Merge Sort 161
7.4 Partitioning 165
7.4.1 The Pivot Algorithm 166
7.4.2 Finding the nth Element 168
?.4.3 Quick Sort 171
7.5 Chapter Summary 175
Further Information 175
Study Questions 176
Exercises 176
Programming Projects 179
8 LINKED LISTS 181
8.1 Varieties of Linked Lists 185
8.2 LISP-Style Lists 187
8.3 The LinkedList Abstraction 189
8.4 Application-Asteroids Game 197
8.5 Application-Infinite-Precision Integers 207
8.6 Chapter Summary 211
Further Information 212
Study Questions 212
Exercises 212
Programming Projects 214
LIST VARIATIONS 217
9.1 Sorted Lists 217
9.1.1 Fast Merge 219
9.1.2 Execution Timings for Merge Operations 220
9.2 Self-Organizing Lists 221
9.3 Skip Lists 223
9.4 Chapter Summary 232
Further Information 232
Study Questions 233
Exercises 234
Programming Projects 235
10 STACKS 237
10.1 The Stack ADT 239
10.2 Checking for Balanced Parentheses 240
10.3 Towers of Hanoi, Revisited 242
10.4 A Four-Function Calculator 244
10.5 A Solitaire Program 250
10.6 Implementation of the Stack Abstraction 257
10.7 Chapter Summary 260
Further Information 260
Study Questions 260
Exercises 261
Programming Projects 264
11 DEQUES 267
11.1 A Fractal Snowflake 269
11.2 Depth- and Breadth-First Search 273
11.3 An Implementation: The IndexedDeque 281
11.4 Chapter Summary 287
Further Information 287
Study Questions 287
Exercises 288
Programming Projects 291
17. QuEuEs ?.93
12.1 The Queue ADT 294
12.2 The Caterpillar Game 295
12.3 A Pastry Factory Simulation 302
12.4 Implementation of the Queue Abstraction 308
12.4.1 A Vector-Based Queue 312
I2.4.2 The Ring Buffer Queue 313
12.4.3 Piped Input/Output Streams 317
12.5 Chapter Summary 318
Further Information 318
Study Questions 318
Exercises 319
Programming Projects 321
13 TREES 325
13.1 Binary Trees 330
13.2 Vector Implementation 333
13.3 Dynamic Memory Implementation 334
13.3.1 Application--Guess the AnimaI Game 335
13.4 Tree Traversals 338
13.4.1 Postorder Tree Traversal 340
13.4.2 Preorder Tree Traversal 343
13.4.3 In-Order Tree Traversal 344
13.4.4 Level-Order Tree Traversal 345
13.5 Euler Tours 346
13.6 Binary Tree Representation of General Trees 351
13.7 Chapter Summary 353
Further Information 354
Study Questions 354
Exercises 354
Programming Projects 355
14 BINARY SEARCH TREES 357
14.1 The Importance of Balance 365
14.2 AVL Trees 369
14.3 Application-Tree Sort 374
14.4 Chapter Summary 376
Further Information 377
Study Questions 377
Exercises 378
Programming Projects 380
15 PRIORITY QUEUES 383
15.1 The Priority Queue ADT 384
15.2 Heaps 386
15.3 Skew Heaps 397
15.4 Application-Discrete Event-Driven Simulation 403
15.4.1 A Framework for Simulations 405
15.4.2 Ice Cream Store Simulation 408
15.5 Chapter Summary 409
Further Information 410
Study Questions 410
Exercises 411
Programming Projects 413
16 HASH TABLES 417
16.1 Hash Functions 418
16.1.1 Hash Functions 421
16.1.2 Hash Functions in the Java Standard Library 423
16.2 Collision Resolution 424
16.3 Hash Table Sorting Algorithms 427
16.3.1 Counting Sort 428
16.3.2 Radix Sorting 430
16.4 Open-Address Hashing 433
16.5 The Hashtable Data Type 437
16.6 Application-Ranking Poker Hands 440
16.7 Chapter Summary 442
Further Information 443
Study Questions 444
Exercises 445
Programming Projects 447
17 MAPS 451
17.1 Example Programs 453
17.1.1 Silly-Sentence Generation, Revisited 453
17.1.2 An Address Database 458
17.1.3 A Concordance 461
17,2 An Implementation 463
17.3 Searching Problems and Maps 469
17.4 Chapter Summary 471
Further Information 471
Study Questions 472
Exercises 473
Programming Projects 474
18 SETS 479
18.1 Changing a Bag into a Set 480
18.2 Set Union, Intersection, and Differences 482
18.3 Sorted List Sets 485
18.4 Application-A Spelling Checker 490
18.5 The Union-Find Problem 491
18.6 The BitSet Abstraction 495
18.7 Application-Prime Number Sieve 498
18.8 Chapter Summary 500
Further Inf6rmation 501
Study Questions 501
Exercises 501
Programming Projects 503
19 MATRICES 507
19.1 Java Matrices 507
19.2 Application-Rain Game 510
19.3 Binary Matrices 514
19.4 Application--The Game of Life 515
19.5 Sparse Vectors 519
19.6 An Application-(Almost) Infinitely Large Hash Tables 521
19.7 Sparse Matrices 523
19.8 Noninteger Keys 524
19.9 Chapter Summary 526
Further Information 526
Study Questions 527
Exercises 527
Programming Projects 528
20 GRAPHS 531
20.1 Adjacency-MatrixRepresentation 533
20.2 Edge-List Representation 537
20.3 Weighted-Graph Representation 541
20.3.1 Weighted-Adjacey Matrix 542
20.3.2 Floyd's Algorithm 542
20.3.3 Weighted-Edge-List Representation 543
20.3.4 Dijkstra's Algorithm 544
20.4 Other Graph Problems 549
20.4.1 Topological Sorting 549
20.4.2 Depth-First Search Spanning Tree 550
20.4.3 Problem-The Traveling Salesman 551
20.5 Chapter Summary 553
Further Information 553
Study Questions 553
Exercises 554
Programming Projects 556
APPENDIX A JAVA SYNTAX 559
A.1 Program Structure 559
A.1.1 Packages 559
A.1.2 Import Declaration 560
A.1.3 Class Declaration 560
A.1.4 Interface Declaration 561
A.1.5 Method Declaration 561
A.1.6 Constructors 563
A.1.7 Data Field Declaration 563
A.2 Statements 564
A.2.I Declaration Statement 564
A.2.2 Assignment Statement 564
A.2.3 Procedure Calls 564
A.2.4 ff Statement 565
A.2.5 switch Statement 565
A.2.6 while Statement 566
A.2 7 for Statement 566
A.2.8 return Statement 566
A.2.9 throw Statement 567
A.2.10 try Statement 567
A.3 Expressions 567
A.3.1 Literal 568
A.3.2 Variables 568
A.3.3 Data Field and Method Access 569
A.3.4 Operators 570
A.3.5 Object Creation 570
A.3.6 Arrays 571
A.4 Files 571
APPENDIX B IMPORT LIBRARIES 573
APPENDIX C DATA STRUCTURES IN THE JAVA STANDARD LIBRARY 577
C.1 Collection 577
C.2 Enumerators and lterators 578
C.3 Vectors 578
C.4 Lists 579
C.5 Stack, Queue, and Deque 580
C.6 Priority Queue 580
C.7 Binary SearchTree 580
C.8 Hash Tables 581
C.9 Set 581
C.10 Map 582
BIBLIOGRAPHY 583
INDEX 589
鄂公网安备 42010302001612号 