第1部分 Java教程
第1章 Java基础知识
第2章 引用类型
第3章 对象与类
第4章 继承
第2部分 算法与构件块
第5章 算法分析
第6章 集合类api
第7章 递归
第8章 排序算法
第9章 随机化
第3部分 应用
第10章 娱乐与游戏
第11章 栈与编译器
第12章 实用程序
第13章 模拟
第14章 图与路径
第4部分 实现
第15章 内部类和ArrayList的实现
第16章 栈和队列
第17章 链表
第18章 树
第19章 二叉查找树
第20章 散列表
第21章 优先级队列: 二叉堆
第5部分 高级数据结构
第22章 伸展树
第23章 归并优先级队列
第24章 不相交集类
附录
contends
I ~ -.
part one TOur Of Java
1., the general environment 4
,.2 the first program 5
.
1'2.1 comments 5
.
1.2.2 mal n 6
.. l..
1.2.3 terminal output 6
1.3 primitive types 6
. l..
1.3.1 the primitive types 6
.
1.3'2 constants 7
1'3.3 declaration and initialization of primitive types 7
.. I.
1.3.4 terminal input and output 8
,.4 basic operators 8
...
1.4.1 assignment operators 9
I.
1'4'2 binary arithmetic operators ic
.
.
1.4.3 unary operators tO
I.
1.4.4 type conversions tO
1.S conditional sautementS 11
l.. I I I. 1.
1.5.1 relational and equality operators 11
1.
1'5.2 logical operators 12
I 1. - 1. I
l.5.3 the if statement 13
I l..,...
1.5.4 the whi ie statement 14
I I
1.5.5 the for statement 14
1.5.6 the do statement 15
-..
XVI contents
.' 1.
l.5.7 break and continue 16
1.5.8 the switch statement 17
' I I. I. I I
1.5.9 the conditional operator 17
1.6 methods 18
l.6.1 overloadina of method names la
d 9
1.6.2 storaQe classes ZO
d
summary ZO
key concepts ZO
common errors 22
- - - -
on the internet 23
exercises 23
references 25
o.',-. i- ~
.2., what is a rdsrence? 27
- o k -. --' .- ~.
2.2 basics Of oh j~ and rdsrences 3o
I I 1. I
rs o, +H Im+ m + (\ CO
2.2.1 the dot operator (.) 3O
perator (. ) 3O
I
rs ac rs Horrlrt~rt+im m f rnhi,
z.2.2 declaration of objects 3o
l I I I.
o O ? rvrtrHrt 11 f;mm rs'
z.2.3 garbage collection 31
. I. r
o o fi. F cO
z.2.4 the meaning of = 32
I.
ac o F m ac ~ac m o+or aam c c i r
2.2.5 parameter passing 33
rs o 6 the meaninQ m' aam
z.2.6 the meaninq of == 33
d Of == 33
I I I. r 1. I
ac o r7 m f lrirtHim Fair anti
z.2.7 no operator overloading for objects 34
~ ~ .,'
2.3 StringS 35
I. r'.. I 1.
ac O, krtcirrc m+ c+rirnm m ac
2.3.1 basics of string manipulation 35
.. I I.
ac rs ac c+rim f fib
2.3.2 string concatenation 35
. 1.
ac o Q comoor;m friar
z.3.3 comparing strings 36
. I
ac O fair qfri un m fi Ic
z.3.4 other String methods 36
I. I I I I 1.
rs o F fial fi f\lrnoc + frinC
2.3.5 converfing other types to strings 37
2.4 arrays 37
l I I.. I I l.I I
n I lrtrrt+i. f on I ma+~ ic O.
2.4.1 declaration, assignment, and methods 38
l..
o 11 Im rt..
2.4.2 dynamic array expansion 4O
rs
2.4.3 ArrayList 42
l.. I.. I
ac I+; tim. I orrrt) IC
z.4.4 multidimensional arrays 45
I I. I
o I tim fo
z.4.5 command-line arguments 45
o
z.4.6 enhanced for loop 46
contents XVii
o c .: k
..=2.S exception handling 47
...
o F, rvrocessina o\ f;
z.5.1 processing exceptions 48
. I ~. -, I
o F ac +H Fi n-fill aflal lab
z.5.2 the fi naily clause 48
..
o F o common excel+;
2.5.3 common exceptions 49
o F fad uk -n I +k rn'. l'
z.5.4 the throw and throws clauses 51
o - -. ~. .-' r-'
2.6 input and output 51
o 6.1 basic stream of aide
z'6.1 basic stream operations 52
o 6.2 the Scanner ti
z.6.2 the Scanner tyDe 53
ype 53
n6.3 sequential files 56
z.6.3 sequential files 56
summary 59
key conceptS 6o
common errors 61
on the internet 62
exercises 62
references 68
,' what is obl-~-orient6d -rol
3.1 what is object-orient6d programming? 69
., - -im-l'
3'2 a simple example 71
~ - B'
. q i-~ds'
3.3 iayadoc 73
o
.
3.4 basic methods 76
..
ac Frl I fm
7 tructors 76
o'4.1 constructors 76
.. I
ac Lrt+m I ac
> tators and accessors 76
o'4.2 mutators and accessors 76
I. I
ac aam F ~ I +ac q+ po' -ry aam
> tDut and toStrino 78
o'4.3 output and toString 78
aam c = Q
7 Is 78
O'4.4 equals 78
. ac
o. q
2. 8
o'4.5 main 78
O -. -. I D;
, - ---m-..
3.S example: using java. math. Bi glnteger 78
o ~. .---...
. R -ddt.i'
3.6 additional conStruct 79
o R' +H k. F Q'
a 6.1 the this reference 81
o'o.1 the this reference 81
rs R Fi k.. k Fkrtm J' fr. I I
> 6.2 the this shorfhand for constructors 82
o'O.2 the this shorfhand for constructors 82
rs R ac +H.
> 6.q the instanceof oDerator 82
o'o.3 the instanceof operator 82
rs R. 'rtri k Fad+; k aam
> 6.d instance members versus static members sa
o'o.4 Instance members versus static members 83
rs R r- o+rt+: F: I Ic o~ I m fi J
> 6.R static fields and methods 8?
o'o.5 static fields and methods 83
ac R R Frt+:.. F:rt l:v oR
>6.6 static initialliers 86
o'o.6 static initialliers 86
O -. -. .- D; n -.,.
. 7 -w-m-.'
3'7 example: implementing a BigRational class 86
- - -..
XVIII contents
o o..
. R --~k--es
3.8 packages go
ac Q' +H. 1. f;l
> 8.1 the imDort directive QI
o'8.1 the import directive 91
rs Q ac +k I Frt+'
> 8.2 the Dackaae statement qq
o'8.2 the package statement 93
rs Q ac +H
> 8,3 the CLASSPATH environment variable 94
o'8,3 the CLASSPATH environment variable 94
ac q i. 'H;I;+\I rl Iloc Q"
> 8.4 Dackaae visibilitv rules qR
o'8'4 package visibility rules 95
o q. - - -.
. q a desia- --item: corn-
3'9 a design pattern: composite (pair) 95
summary 96
key conceptS 97
common errors IOO
- - -
on the internet IOO
exercISes IOI
references IO7
4., what is inheritance? 11o
1. I
4.1,1 creating new classes 11o
. I. 1. 1. I
4.1,2 type compatibility 115
1. I.
4.1.3 dynamic dispatch and polymorphism 116
. I. I 1. I.
4.1.4 Inheritance hierarchies 117
.. I. 1. I I
4.1.5 vislbility rules 117
4.1,6 the constructor and super 118
~. - I I I I I
4.1.7 final methods and classes 119
4.1.8 overriding a method 121
. I. I. 1. I..
4.1.9 type compatibility revisited 121
I. I. 1. I r I
4.1.IO compatibility of array types 124
. I I I
4.1.11 covarlant return types 124
4.2 designing hierarchies 125
4.2.1 abstract methods and classes 126
I.. r I I r I
4.2.2 designing for the future 13O
4.3 multiple inheritance 131
4.4 the interface 134
. r..
4.4.1 specifying an interface 134
. I I... r
4.4.2 implementing an interface 135
l 1. I. I r
4.4.3 multiple interfaces 135
. I r I I I I
4.4.4 Interfaces are abstract classes 136
contents XIX
4.5 fundamental inheritance in java 136
I I
4.5.1 the object class 136
I I 1. I r
4.5.2 the hierarchy of exceptions 137
.
4.5.3 l/o: the decorator pattern 138
4.6 implementing generic componentS using inheritance 142
4.6.1 using object for genericity 142
4.6.2 wrappers for primitive types 143
4,6.3 autoboxing/unboxing 145
4,6.4 adapters: changing an interface 146
4.6.5 using interface types for genericity 147
4.7 implementing generic componentS using java 5 generics 15o
. I. I 1. I r
4.7.1 sfmple generic classes and interfaces 15O
. I I I' I I I I
4.7.2 wlldcards with bounds 151
..'. I I I
4.7.3 generic static methods 152
I I I
4.7.4 type bounds 153
I
4.7.5 type erasure 154
4.7.6 restrictions on generics 154
4.8 the funotor (function object) 157
4.8.1 nested classes 161
4.8.2 local classes 161
4,8,3 anonymous classes 163
4.8.4 nested classes and generics 164
4.9 dynamic disoatch details 16A
ynamic dispatch details 164
Summary 168
key concepts 168
common errors 171
- - - -
on the internet 171
exercises 173
references 183
I I -. -...
part two Algorithms and
Building BlOckS
c, wb-. i-
o. I what is algorithm analySis? 188
R o exam-I--. -l'
o'2 examples of algorithm running times 192
XX contents
q' .he maximum contio..ous subseouence sum
a.3 the maximum contiguous subsequence sum problem 193
I I 1.
R?.1 the obvious O(M) alqorithm lq4
o.3.1 the obvious O(M) algorithm 194
. I
R Q.2 an imDroved O(N2) aloorithm lq7
u.3.2 an Improved O(N2) algorithm 197
R a Q a linear aIQorithm lq7
o.3.3 a linear algorithm 197
q
a'4 general big-oh rules 2of
R c the loo-rithm Zoo
a.5 the logarithm 2o5
R 6 septic searchina -roblem 2o7
o'6 septic searching problem 2o7
R.6.1 seouential search 2O7
o.o.1 sequential search 2O7
R.6.2 binary search 2o8
u.O.2 binary search 2o8
R.6,3 interpolation search 211
o.o,3 Interpolation search 211
q. -h-Ckino --
o'7 checking an algorithm analysis 212
q R limitations of bia-oh analv.
o.8 limitations of big-oh analysis 213
summary 214
key concepts 214
common errors 215
-.
on the internet 216
exercISes 216
reterences 227
6.1 introduction 23o
6.2 the iterator pattern 231
6.2.1 basic iterator desiQn 222
an 232
6,2.2 inheritance-based iterators and factories 234
6'3 collections apt: conjoiners and iterators 236
6.3.1 the collection interface 237
6.3.2 Iterator interface 24O
6'4 generic algorithms 242
6,4.1 Comparator function objects 243
6.4.2 the coil ections class 243
6.4.3 binary search 246
6.4.4 Sorting 246
6'5 the List interface 248
6.5.1 the Li stlterator interface 249
6.5.2 Li nkedLj st class 251
contents XXi
6.5.3 running time for Li sts 253
6.5.4 removing from and adding to the middle of a Li st 256
6'6 stocks and queues 258
6'6'1 stacks 258
6'6'2 stacks and computer languages 259
6'6.3 queues 26o
6'6.4 stacks and queues in the collections apt 261
6'7 sac 261
6'7.1 the TreeSet class 263
6.7.2 the HashSet class 264
6.8 maps 268
6.9 priority queues 274
6'IO views in the collections apt 277
6.ic.1 the subList method for Lists 277
6.ic.2 the headSet, subSet, and tat 1 Set methods for SortedSets 277
summary 278
key conceptS 279
common errors 28O
on the internet 281
exercISes 281
re,erences 292
7.1 what is recursion? 294
- -...
7'2 background: proofS by mathematical induction 295
- ~. -
7'3 basic recursion 297
..... I
ry O, m r; m+; cry ac I I m k. H
7.3.1 printing numbers in any base 299
I. I I
r7 H)I;+ ) I
7.3.2 why it works 3of
I.. I
m H. F ). I
7.3.3 how it works 3o2
l I.. I
ac O L k. k J. m
7.3.4 too much recursion can be dangerous 3O4
. r.
ry o R m. F +roes q
7.3.5 preview of trees 3O5
ry o 6 additional examal
7'3.6 additional examples 3O6
7'4 numerical applications 311
l I.. I..
ry I I I I ac w ac r: +H ~ F:
7.4.1 modular arithmetic 311
I I
ry I I I I ac r ac \ +: ac +:
7.4.2 modular exponentiation 312
XXll contents
l I I.. I I4. I. '!.
ry Foe+ errnmmon divisor and multirviicative inverses 314
7.4.3 greatest common divisor and multiplicative inverses 314
. I I I
ry fi + fern ?fry
7.4.4 the rsa cryptosystem 317
- ~ .- -...
..T.5 divide-and-conquer algorithms 319
l 1. 1. I I I
ry F' +ho mo\. fial ious subseauence sum nroblem
7.5.1 the maximum contiguous subsequence sum problem 32O
1.
ac G n omol\ICic aam o hoqir I
7.5.2 analysis of a basic divide-and-conquer recurrence 323
l I I' I.. I I. f:
ry F rs o openeral "rumer bound for divide-and-conquer runnina times boa
7.5.3 a general upper bound for divide-and-conquer running times 327
-f -' -
7.6 dynamic programming 329
- -f.. -.
1.7 backtracking 333
summary 336
key concepts 338
common errors 339
- - - -
on the internet 339
exercises 34O
references 348
8.1 why is sorting impotents 352
8.2 preliminaries 353
8.3 analySis Of the insertion sort and other simple sods 353
8.4 shellsort 357
8.4.1 performance of shellsorf 358
8.5 mergesort 361
8.5.1 linear-time merging of sorted arrays 361
8.5.2 the mergesort algorithm 363
8.6 quicksort 364
8.6.1 the quicksort algorithm 367
8.6.2 analysis of quicksorf 369
8.6.3 picking the pivot 372
8.6.4 a parfitioning strategy 374
8.6.5 keys equal to the pivot 376
8.6.6 median-of-three parfitioning 376
8.6.7 small arrays 377
8.6.8 lava quicksort routine 378
Java qulcksort routine 378
8.7 quickSeleot 38o
8.8 a lower bound for sorting 381
contents XXiii
summary 383
key conceptS 384
common errors 385
on the internet 385
exercises 385
references 391
q' why do we need random numbers? CQds
9., why do we need random numbers? CQd
y do we need random numbers? 393
9 9,--aam
9.2 random number generators 394
o. ---uniform random numbers doZ
9.3 nonuniform random numbers 4o2
o 4
9'4 generating a random permutotion 4o4
9.5 randomized algorithms 4o6
q 6 f&ndomized -rim-I.
9'6 randomized primality teSting 4o9
summary 412
key conceptS 412
common errors 413
on the internet 414
exercises 414
references 417
part three Applications
'O'1 word search punies 421
..
ic.1.1 theory A22
y 422
......
IO.l.2 Java Implementation 423
,O.2 the game Of tie-tee-toe 427
. I I.
ic.2.1 alpha--beta pruning 428
....
ic.2.2 transposition tables 431
..
IO.2'3 computer chess 435
summary 438
key concepts 438
-..
XXIV contents
common errors 438
- -
on the internet 438
exercises 439
references 441
1 1.1 balanced-symbol checker 443
1. I. I I
11.1.1 basic alqorithm 444
d f44
. I I 1.
11.1.2 implementation 445
1 1.2 a simple calculator 454
I r. I.
11.2.1 postfix machines 456
.'.
11.2.2 infix to postfix conversion 457
postfix conversion 457
. I I 1.
11.2.3 implementation 459
. I
11.2.4 expression trees 468
summary 469
key conceptS 47O
common errors 47O
- - - -
on the internet 471
exercises 471
reterences 472
12.1 fil. compression 474
r. I
12.1.1 prefix codes 475
l r r
fi.l.z huffman's alaorithm 477
d F77
. I l..
12.l.3 implementation 479
12.2 a cross-rderence generator 495
I.. I
12.2.1 basic ideas 495
.. I I 1.
12.2.2 lava implementation 495
J plementation 495
summary 499
key conceptS soO
common errors SOO
on the internet SOO
exercISes SOO
references 5O6
contents XXV
,3.1 the josephus problem 5o7
. I....
13.1,1 the simple solution 5O9
r'..
13.1.2 a more efficient algorithm 5O9
'3'2 event-driven simulation 513
13.2.1 basic ideas 513
I' I....
13.2.2 example: a call bank simulation 514
summary 522
key concepts 522
common errors 523
- -
on the internet 523
exercises 523
14'1 d6finitions 528
14.1.1 representation 53O
,4'2 unweighted shorteSt-path problem 539
..
14.2.1 theory 539
......
14.2.2 Java Implementation 545
,4'3 positive-Weighted, shodeSt-path problem 545
. I... I. I 1. I.
14.3.1 theory: dijkstra's algorithm 546
.. I...
14.3.2 Java Implementation 55O
,4.4 negativ.-weighted, shorteSt-path problem 552
I
14.4.1 theory 552
.. I...
14.4.2 java Implementation 553
,4'5 path problems in acyclic graphs 555
. I....
14.5.1 topological sorfing 555
. I r. I
14.5.2 theory of the acyclic shorfest-path algorithm 557
......
14.5.3 Java implementation 557
1.
14.5.4 an application: critical-path analysis 56O
summary 562
key conceptS 563
common errors 564
on the internet 565
-. I
XXVI contents
exercises 565
references 569
I r.. - -,
part four Implementations
15., iterators and neSted classes 574
,5.2 iterators and inner classes 576
15.3 the AbstractCollection class 58o
15.4 StringBuilder 584
,5.5 implementation of ArrayList with an iterator 585
summary 59O
key conceptS 591
common errors 591
on the internet 591
exercises 591
16.1 dynamic array implementations 595
16.1.1 stacks 596
16.1.2 queues 600
16.2 linked list implementations 6o5
16.2.1 stacks 6o6
16.2.2 queues 6o9
,6.3 comparison Of the tWo methods 613
, 6.4 the lava. util. Stack class 613
,6.5 double-ended queues 615
summary 615
key concepts 615
common errors 615
on the internet 616
- ac
exercises 616
contents XXVii
17'1 basic ideas 619
. I.
17.l.l header nodes 621
....
17'1'2 .terator classes 622
'7'2 lava imolementotion 624
java implementation 624
17'3 doubly linked listS and circularly linked listS 63o
,7'4 sorted linked listS 633
1 7'5 implementing the collections apt LinkedList class 635
summary 646
key conceptS 646
common errors 647
-
on the internet 647
exercises 647
,8', general trees 651
18'1'1 definitions 652
18.1.2 imolementation 653
plementation 653
18'1'3 an application: file systems 654
,8'2 binary trees 658
18'3 recursion and trees 665
'8'4 tree traversal: it6rator classes 667
18'4'1 postorder traversal 671
18.4.2 inorder traversal 675
18.4.3 preorder traversal 675
18'4'4 level-order traversals 678
summary 679
key conceptS 68o
common errors 681
-
on the internet 682
exercises 682
- - - I I
XXVIII contents
19.1 basic ideas 687
l I 1.
19.1,1 the operations 688
.. I I I.
19.1.2 java implementation 69o
19.2 order statistics 697
.. I I 1.
19.2.1 ]ava implementation 698
19.3 analysis Of binary search tree operations 7o2
19.4 avi trees 7o6
I.
19.4.1 properties 7o7
. I I 1.
19.4.2 Single rotation 7o9
l I I I 1.
19.4.3 double rotation 712
19.4.4 Summary of avi insertion 714
19.5 red-black trees 715
l l..l. 1.
ig.5.1 bottom-up insertion 716
d.5.1 bottom-up insertion 716
I I I I I I t aam Q
19.5.2 top-down red--black trees 718
.. I I I.
19.5.3 ]ava Implementation 719
l I I I 1.
19.5.4 top-down deletion 726
19.6 aa-trees 728
19.6.1 insertion 73O
19.6.2 deletion 732
19.6.3 java implementation 733
19.7 implementing the collections apt TreeSet and
TreeMap classes 738
19.8 b-trees 756
summary 762
key concepts 763
common errors 764
on the internet 764
exercises 765
references 769
on. k - -.
2O.1 basic ideas 774
2O.2 hash function 775
I
co.a.l headCode in j 'va. 1 ana sari na ry77
ic.2.1 headCode in java. 1 aug. Sin ng 777
contents XXiX
on o .=- k'
2O.3 linear probing 779
. I. r 1. 1.
aam o, anti\ l\IC;c F tim H'
2o.3.1 naive analysis of linear probing 78O
l I I I 1. I 1.
rsrn rs o what reallll aam. l' Ic+.
ic.3.2 what really happens: primary clustering 781
I.
ac O Q Qrnrtl\loic al +H Fi n I I
ic.3.3 analysis of the +md operation 782
aam
2O.4 quadratic probing 784
.. I I 1.
rsO.d,;rt) Ti;m loin 'rt+;
ic.4.1 java implementation 788
I.
nO.4 o Qmrtl\ Ic;c~ I~rt+; him
2O.4.2 analysis of quadratic probing 797
on q. - - - - -'
2O.5 separate chaining hashing 797
aam - - - .-k..
2O'6 hash ambles versus binary search trees 798
aam - - -. .= .:
2O'7 hashing applications soo
rs
summary soO
key concepts 8of
rs
common errors 8O2
on the internet 8o2
- ac,
exercISes 8O2
references 8O5
o.. - - -.
2, '1 basic ideas 8o8
I
o,,, c+ructure apron f)' iraQ
21.1.1 structure property 8o8
I I I
ry,, O aam m I f\, Q'rn
21.1.2 heap-order property 81o
o,, ac IIml I ac fib Q',
if.1.3 allowed operations 811
-' ~ -. .~.=. .- I
21 .2 implementation of the basic operations 814
. 1.
o' o,;mc f;rnm q'
if.2.1 Insertion 814
l I l,
o, rs o the deleteMi n cry fi Q'6
if.2.2 the deleteMin operation 816
ac, o .- k '1 IU .=.
21 .3 the bull dHeap operation: linear-time heap construction 818
-'
21.4 advanced operations: decreaseKey and merge 823
ac' q -..
21 .5 internal sorting: heapsort 823
ac. ~ ... .=-.
21 '6 external sorting 826
o, A' 16IH)I IBId mooH m I .I
if.6.1 why we need new aIQorithms 826
y we need new algorithms 826
O' R ac mad lol T +ormol c f;r
if.6.2 model tor external sortinq 827
d 827
o, R o +h. I I 'f am qory
if.6.3 the simple algorithm 827
O, R I+;)6lo\ I m ghQ
if.6.4 multiway merge 829
O' R r- ac i\ lmHrtoo m qorn
if.6.5 polyphase merge 83o
n, R R 1. f o I f; Roc
if.6.6 replacement selection 832
XXX contents
ac
summary 833
key concepts 834
ac o
common errors 834
-. - - - rs ac
on the internet 835
- rs ac
exercises 835
references 839
l r. -.. -'
part five Advanced Oata
-.,. .n.I
structures
-o. ...- .'--
.22'1 self-adjustment and amortized analysis 844
I. I I. I I m
no,, rimrnrfi7od time bounds sa R
22.1.1 amorfized time bounds 845
. I I r i. I. I I / I I I I I I \
nO, rs ac c;mml i+ ac iii Ic+ir
22.1,2 a simple self-adjusting strategy (that does not work) 845
-- o .- - - k
22.2 the basic bottom-up splay tree 847
-o 9 - - .~ .,~ .=
22.3 basic splay tree operations 85o
-o
22'4 analysis of bottom-up splaying 851
r r. I 1. I I
ado F m+ +H lab\. h J aam
z2.4.1 proof of the splaying bound 854
~o q.. .-
.22.5 top-down splay trees 857
22.6 implementation Of top-down splay trees 86o
-- - -. .- .~ .-
22.7 comparison of the splay tree with other search trees 865
rs n ac
summary 866
key concepts 866
o ac
common errors 867
on the internet 867
- rs ac
exercises 867
references 868
ig. .-.
23.1 the skew heap 871
.. r
nO,, m.. fi lmHrt m aam I cry
z3.1.1 merging is fundamental 872
. I. I..
no, o c;m l;c+i. f h I I +roes 87o
z3.1.2 Simplistic merging of heap--ordered trees 872
contents XXXi
l I I 1. I 1. r'
nO, O +Ho of.m)hl h. ic m III;'
z3,1.3 the skew heap: a simple modification 873
l' r' I I I
no' l)loio ac +h I Hortm ac
z3.1,4 analysis of the skew heap 874
ig - .- - -
23.2 the pairing heap 876
.. I I.
aam O, rnrt;rim H F; Qryry
z3.2.1 pairing heap operations 877
. I I'. r I l.. I
ac o o imal ro+imm ac +H.. boor
z3,2.2 implementation of the pairing heap 878
1.
cry o q l;rtrt+: h;l fpertlo oh Fad+ \A.
23.2,3 application: dijkstra's shortest weighted path algorithm 884
QQR
summary 888
key concepts 888
Q Q Q
common errors 888
- - -
on the internet 889
- O Q
exercises 889
references 89O
24'1 equivalence relations 894
24.2 dynamic equivalence and applications 894
I.
O I; f; f;mry ma-
Qrnrz4.2.1 application: generating mazes 895
I'
o l; fi...
z4.2,2 application: minimum spanning trees 898
1.
o l; f; Fad far mrrnhl
z4.2.3 application: the nearest common ancestor problem 9of
o
24.3 the quick-find algorithm 9o4
ac
24.4 the quick-union algorithm 9o5
I.
O f I I m; ac ac ac I ry. Fi m
24.4.1 smart union algorithms 9o7
l 1.
o fi.
24.4.2 path compression 9o9
o
24.5 lava imolementation Qlo
java implementation 91o
24.6 worst case for union-by-rank and path compression 913
o
z4.6.1 analysis of the union/find algorithm 914
summary 921
key conceptS 921
common errors 922
on the internet 922
exercises 923
references 925
- -.
XXXII contents
B., the abstract window toolkit and swing 93o
B.2 basic object in swing 931
B.2,1 Component 932
B.2.2 Contai ner 933
B,2.3 top-level containers 933
B.2.4 JPanel 934
B,2.5 imporfant i/o components 936
B.3 basic principles 94o
B.3.1 layout managers 941
B.3.2 graphics 945
B.3.3 events 947
B.3.4 event handling: adapters and anonymous inner classes 949
B.3.5 Summary: putting the pieces together 951
B.3.6 is this everything i need to know about swing? 952
summary 953
key conceptS 953
common errors 955
- -
on the internet 956
exercises 956
references 957
