圖書簡介
最重要的修改包括這樣幾個方面：
（1）對本書的基本結構進行了重新設計，以使得這些內容之間的脈絡更加清晰；
（2）第3版把對面向對象概念的複習作為一個附錄以供參考；
（3）上一版給出了幾個完整的Java程式設計案例和原始碼，在第3版中進行了刪除，並把這幾個程式案例原始碼放在了網上供讀者下載。譯者認為，這不僅壓縮了不少篇幅，而且使得本書更像是一本數據結構與算法的教材，而不是Java程式設計的教材；
（4）第3版擴展了對圖的討論，把“圖”與“散列”兩章的順序進行了調換，使得脈絡更清晰。本版還添加了一章來專門討論Set與Map集合。
總之，這些修改都是建立在使用以前版本教學的基礎上，為教師提供更多的機會和更好的靈活性來使用本書。
圖書目錄
Contents
Preface
Chapter 1 Introduction 1
1 .1 Soffware Quality 2
Correctness 3
Reliability 3
Robustness 4
Usability 4
Maintainability S
Reusability S
Portability 6
Efficiency 6
Quality Issues 6
1.2 Data Structures 7
A Physical Example 7
Containers as Objects 10
Chapter 2 Analysis of Algorithms 13
2.1 Algorithm Efficiency 14
2.2 Growth Functions and Big-OH Notation 15
2.3 Comparing Growth Functions 17
2.4 Determining Time Complexity 19
Analyzing Loop Execution 19
Nested Loops 20
Method Calls 21
Chapter 3 Collections 27
3.1 Introduction to Collections 28
Abstract Data Types 29
The Java Collections API 31
xv
.
xvi CONTENTS
x o A sfack Collection 31
o.2 A Stack Collection 31
~ - ~..
x' Crucial OO Concert.c 9'
o'3 Crucial OO Concepts 33
Inheritance 34
Class Hierarchies 36
m'
foe Object Class 37
PolymorDhism 38
ymorphism 38
References and Class Hierarchies 38
Generics 40
.
o.4 A Stock ADT 41
Interfaces 41
~ -... CI.. -...
. c Usina tfacks: Evaluatina prtcfflv I
o.5 Usina Stacks: Evaluatina Posffix Exoressions 44
s stacks: Evaluating Posffix Expressions 44
-' -..
. ^ ac~eptions 51
o.6 Exceptions 51
Exception Messages 52
~,
foe try Statement S3
Exception Propagation 54
- 'f..
x. lmrilementina a Stack: With Array ''
o.7 implementing a Stack: With Arrays 55
Managing Capacity 56
- o -.
x R The Arral'q.-" Class 57
o.8 The Arraystack Class 57
FI
foe Constructors 58
al.
foe push Operation 59
FI
foe pop Operation 61
al.
foe peek Operation 62
Other Operations 63
Chapter 4 Linked Structures 71
4.1 References as Links 72
4.2 Managing Linked Lists 74
Accessing Elements 74
Inserting Nodes 7S
Deleting Nodes 76
sentinel Nodes 77
sentinel Nodes 77
4.3 Elements Without Links 78
Doublv Linked Lists 78
y Linked Lists 78
4.4 implementing a Stock: With Links 79
FI
foe LinkedStack Class 79
CONTENTS xvii
m['
f he push Operation 83
FI
f he pop Operation 85
Other Operations 86
4.5 Usina Stacks: Traversina a Maze 86
u clacks: Traversing a Maze 86
4.6 Implementing Stacks:
The java. util. stack Class 93
Unique Operations 93
Inheritance and Implementation 94
Chapter 5 Queues 99
5.1 A Queue ADT 100
5 o llcina Queues: Code Ke\'c Ink
a'2 Using Queues: Code Keys 103
s Queues: Code Keys 103
5. llcina Queues: Ticket Counter Simulation 107
a.3 Using Queues: Ticket Counter Simulation 107
u Queues: Ticket Counter Simulation 107
5 4 lmrilementina Queues: With Links 112
a.4 implementing Queues: With Links 112
FI
f he enque Operation 114
al,
f he dequeue Operation 115
Other Operations 117
5.5 Implementing Queues: With Arrays 117
FI
f he enqueue Operation 123
m,
f he dequeue Operation 124
Other Operations 125
Chapter 6 Lists 131
6.1 A List ADT 132
Iterators 134
Adding Elements to a List 135
Interfaces and PolymorDhism 137
; Inorphism 137
6'2 Using Ordered Lists: TOurnament Maker 140
d
6'3 Using indexed Lists: The Joseohus Problem 150
u indexed Lists: The Josephus Problem 150
6.4 Implementing Lists: With Arrays 152
FI
l he remove Operation ISS
FI
l he contains Operation IS7
al.
f he iterator Operation IS8
al.
f he add Operation for an Ordered List IS8
peration for an Ordered List IS8
...
xvill CO NTE NTS
Operations Particular to Unordered Lists 161
ml,,,
foe addAfter Operation for an Unordered List 162
6.5 Implementing Lists: With Links 163
FI
foe remove Operation 163
Doubly Linked Lists 165
y Linked Lists 165
al.
foe iterator Operation 168
6.6 Lists in the Java Collections API 171
Cloneable 172
c., i - =hi e 172
berializable 172
RandomAccess 172
Tova. util. Vector 173
Java. util. Vector 173
Tova. util. ArralrT' o- 1 72
Java. util. ArrayList 173
Tova. util. LinkedList 176
Java. util. LinkedList 176
Chapter 7 Recursion 185
-f, -. -I... -
7.1 Recursive Thinking 186
9 186
Infinite Recursion 186
Recursion in Math 187
7.2 Recursive Programming 188
"ramming 188
Recursion versus iteration 190
Direct versus indirect Recursion 191
-.
7.3 Using Recursion 192
. Recursion 192
m. A' 4 Q,
lraversing a Maze 192
al m r T T. 4
Of he Towers of Hanoi 197
7.4 Analyzing Recursive Algorithms 201
Chapter & Sorting and Searching 209
8.1 Searchinq 210
9 210
static Methods 211
static Methods 211
Generic Methods 211
Linear Search 212
Binary Search 213
y search 213
Comparing Search Algorithms 216
8.2 Sortina 217
9 217
Selection Sort 220
selection Sort 220
Insertion Sort 222
CO NTE NTS xlx
Bubble Sort 224
Quick sort 226
Merge Sort 229
8.3 Radix Sort 231
Chapter 9 Thees 241
9'1 Thees 242
m
free Classifications 243
9'2 Strateaies for Imolementina Thees 245
stes for Implementing Thees 245
Commutational Strategy for
putational Strategy for
Array ImDlementation of Trees 245
j implementation of Trees 245
simulated Link Strate21r for
simulated Link Strategy for
Array ImDlementation of Trees 246
, implementation of Trees 246
Analtsis of Trees 247
9.3 Thee TFaversals 248
Preorder Traversal 248
Inorder Traversal 249
Postorder Traversal 249
Level-Order Traversal 250
9.4 A Binary Thee ADT 251
9.5 Usina Binary Thees: Exoression TFees 255
s Binary Thees: Expression TFees 255
9.6 Implementing Binary Thees with Links 262
FI
foe find Method 269
ml.,
foe iteratorlnorder Method 270
9.7 implementing Binary Thees with Arrays 271
FI
foe find Method 273
ac. h' I I ry-'
foe iteratorlnorder Method 274
Chapter 10 Binary Search Thees 281
10.1 A Binary Search Thee 282
10.2 Implementing Binary Search Thees:
With Links 284
ale
foe addElement ODeration 286
peration 286
FI
foe removeElement Operation 288
u CONTENTS
FI
foe removeAlloccurrences Operation 291
peration 291
FI
foe removeMin Operation 292
10.3 implementing Binary Search Thees:
With Arrays 294
ml,,o,
foe addElement Operation 295
FI
foe removeElement Operation 296
FI
foe removeAlloccurrences Operation 302
FI
foe removeMin Operation 303
10.4 Usina Binary Search Thees:
9 Binary Search Thees:
implementing Ordered Lists 304
Analysis of the BinarySearchTreeList
.
Implementation 308
10.5 Balanced Binary Search Thees 309
Right Rotation 310
.lit Rotation 310
Left Rotation 310
Rightleft Rotation 311
.iltleft Rotation 311
Leftright Rotation 311
10.6 implementing Binary Search Thees:
AVL Thees 312
Right Rotation in an AVL Tree 313
.nt Rotation in an AVL Tree 313
Left Rotation in an AVL Tree 315
Ritthtleft Rotation in an AVL Tree 3iS
.ntleft Rotation in an AVL Tree 3iS
Leftright Rotation in an AVL Tree 315
10.7 Implementing Binary Search Thees:
Red/Black Thees 315
Insertion into a Red/Black Tree 316
Element Removal from a Red/Black Tree 319
10.8 Implementing Binary Search Thees:
The Java Collections API 321
10.9 A Philosophical Quandary 325
Chapter 11 Priority Queues and Heaps 333
11.1 A Heap 334
ml,,
foe addElement Operation 334
FI.
foe removeMin Operation 337
FI
foe findMin Operation 338
11'2 Usina Heaps: Priority Queues 339
. Heaps: Priority Queues 339
CO NTE NTS m
11.3 implementing Heaps: With Links 343
FI
foe addElement Operation 343
FI
foe removeMin Operation 346
FI
foe findMin Operation 349
11.4 Implementing Heaps: With Arrays 350
al.
foe addElement Operation 350
FI
foe removeMin Operation 352
FI
foe findMin Operation 353
11'5 Usina Heaos: Heao Sort 354
u Heaps: Heap Sort 354
Chapter 12 Multi-way Search Thees 361
12'1 Combining TFee Conceots 362
. rFee Concepts 362
12'2 2-3 Thees 362
Inserting Elements into a 2-3 Tree 362
Removing Elements from a 2-3 Tree 365
12'3 2-4 Thees 369
12.4 B-Thees 369
B*-trees 371
B+-trees 372
Analysis of B-trees 372
yals of B-trees 372
12.5 implementation Strategies for B-Thees 373
Chapter 13 Graphs 377
13.1 Undirected Graphs 378
13.2 Directed Graphs 380
13.3 Networks 381
13'4 Common Graph Algorithms 382
~'
fraversals 383
m.
festinZ for Connectivity 387
b ior Connectivity 387
Minimum Spanning Trees 388
DetermininZ the Shortest Path 391
o the Shortest Path 391
13'5 Strateqies for lmolementina Graohs 392
.ies for implementing Graphs 392
Adjacency Lists 392
jacency Lists 392
Adjacency Matrices 393
jacency Matrices 393
..
nil C O NTE NTS
13.6 implementing Undirected Graphs
... -..
With an Adiocency Motrix 395
Jacency Motrix 395
al, 'o' A' 1 1 7 OO
foe addEdge Method 399
ale .t. t A, I l' un
foe addvertex Method 400
FI
foe extendcapacity Method 401
Other Methods 401
Chapter 14 Hashing 407
14.1 Hashing 408
14.2 Hashina Functions 410
9 Functions 410
AL ri'.. h' I l', n
foe Division Method 410
al v I l' Method 411
foe Folding Method 411
al 1 r. I c A' I l' 1 1
foe Mid-Square Method 411
al n ac l' m c. h' I I' 1,
foe Radix Transformation Method 412
al ri'.' 1. Method 412
foe Digit Analysis Method 412
The Length-Dependent Method 412
Hashing Functions in the Java Language 413
14.3 Resolving Collisions 413
Chaining 413
Open Addressing 416
14.4 Deleting Elements from a Hash Table 419
Deleting from a Chained Implementation 420
Deleting from an Open Addressing
Implementation 420
14.5 Hash Tables in the Java Collections API 421
FI
foe Hashtable Class 422
FI
foe HashSet Class 424
FI
foe HashMap Class 424
FI
foe ldentityHashMap Class 424
FI
foe WeakHashMap Class 425
.
LinkedHashSet and LinkedHashMap 428
Chapter 15 Sets and Maps 435
15.1 A Set Collection 436
15.2 Using a Set: Bingo 439
CONTENTS "iii
15.3 implementing a Set: With Arrays 443
~,
foe add Operation 445
al
foe addAll Operation 447
m'
foe removeRandom Operation 448
FI
foe remove Operation 449
al.
foe union Operation 450
FI
foe contains Operation 451
FI
foe equals Operation 452
Other Operations 453
UML Description 453
15.4 implementing a Set: With Links 455
ml,, ac.
foe add Operation 456
FI
foe removeRandom Operation 457
FI
foe remove Operation 458
Other Operations 459
15.5 Maps and the Java Collections API 459
Appendix A UML 467
al T T. f' I A, I I. T fT T'
foe Unified Modeling Language (UML) 468
b Language (UML) 468
UML Class Diagrams 468
UML Relationships 469
Appendix B Object-Oriented Design 475
B.1 Overview of Object-Orientation 476
B.2 Usina Obiects 476
S Objects 476
Abstraction 477
Creating Objects 478
B.3 Class Libraries and Packages 480
al. ac 1.
foe import Declaration 480
B.4 State and Behavior 481
B.5 Classes 482
Instance Data 485
B.6 Encapsulation 486
Visibility Modifiers 486
Local Data 488
.
ulv C O N T E N TS
B.7 Constructors 488
B.8 Method Overloadina 489
s 489
B.9 References Revisited 490
FI 11 o c' on
foe null Reference 490
FI
l he this Reference 491
Aliases 493
Garbage Collection 494
Passing Objects as Parameters 495
B.10 The static Modifier 495
static Variables 49s
Jtatlc Variables 49s
static Methods 496
static Methods 496
B.11 Wrapper Classes 497
B.12 Interfaces 498
al T C' QQ
foe Comparable interface 499
FI T C adn
foe lterator interface 500
B.13 Inheritance 500
Derived Classes 501
al A' 1. c. on,
foe protected Modifier 503
al n r
foe super Reference 503
Overriding Methods 504
B.14 Class Hierarchies 504
FI
foe object Class 505
Abstract Classes 506
Interface Hierarchies 508
B.15 Polymorphism 508
References and Class Hierarchies 509
Polymorphism via inheritance 510
y morphism via inheritance 510
Polymorphism via interfaces 512
ymorphism via interfaces 512
B.16 Generic Types 514
B.17 Exceptions 515
Exception Messages 515
al c'
foe try Statement 516
Exception Propagation 517
al v.
foe Exception Class Hierarchy 517
Index 527
