1.1 本书内容 1
1.1.1 动态数组 1
第1章 类与对象 1
1.1.2 链表 2
1.1.3 关联数组 3
1.1.5 适配器结构 4
1.1.4 图 4
1.2 面向对象编程 5
1.1.7 数据结构与算法 5
1.1.6 数据结构与面向对象编程 5
1.3 理解类的概念 7
1.4.1 设计Time24类 8
1.4 Time24类 8
1.4.2 构造函数 9
1.4.3 toString方法 10
1.4.4 Accessor和mutator方法 11
1.5 对象的声明和使用 12
1.4.5 静态方法 12
1.5.1 对象方法的使用 13
1.5.2 引用与别名 14
1.6 一个使用Time24对象的应用程序 15
1.7 类的表示 16
1.8 类的实现 18
1.8.1 Time24类声明 19
1.8.2 私有的工具方法 20
1.8.3 accessor与mutator方法 21
1.8.4 构造函数 22
1.8.7 时间间隔 23
1.8.6 增加时间 23
1.8.5 格式化的对象描述 23
1.9 类的构造 24
1.10 String类 26
1.10.2 串合并 27
1.10.1 串索引 27
1.10.3 串比较 28
1.11 枚举类 29
1.12 总结 32
书面练习 33
编程练习 34
编程项目 36
第2章 类之间的关系 39
2.1.1 Integer对象的比较 40
2.1 wrapper类 40
2.1.2 静态wrapper类成员 41
2.1.3 字符处理 42
2.2 自动装箱与自动拆箱 43
2.3 对象组合 44
2.3.1 TimeCard类 45
2.3.2 TimeCard类的实现 46
2.4 Java中的继承 47
2.3.3 TimeCard类的UML图 47
2.4.1 一个雇员层次结构 48
2.4.2 继承层次结构中成员的可见性 49
2.4.3 Employee类的声明 50
2.4.4 SalaryEmployee子类 51
2.4.5 继承层次结构中的关键字super 52
2.4.6 HourlyEmployee子类 53
2.5 多态性 55
2.6 抽象类 59
2.7.1 throw语句 60
2.7 运行时错误的处理 60
2.7.2 处理异常的try/catch代码块 61
2.7.3 finally子句 62
2.7.5 Java异常的层次结构 63
2.7.4 异常传播 63
2.8 输入与输出 65
2.7.6 标准的异常 65
2.8.1 控制台I/O 66
2.8.3 使用Reader流的文本输入 67
2.8.2 文件I/O 67
2.8.4 输入串的分析 69
2.8.5 使用Writer流的文本输出 71
2.8.6 输出流的控制 72
2.9.2 输入流的读取 73
2.9.1 声明Scanner对象 73
2.9 Scanner类 73
2.9.4 Scanner类API 75
2.9.3 文件输入 75
2.9.5 应用程序：Scanner类的使用 76
2.10 总结 79
书面练习 80
编程练习 83
编程项目 87
3.1 Java接口 89
第3章 类的设计 89
3.2 作为模板的接口 91
3.2.1 使用接口类型 92
3.2.2 接口与继承 94
3.3 使用iavadoc创建API 96
3.4 设计模式 99
3.5 GUI应用程序设计 100
3.5.1 图形组件 101
3.5.2 GUI应用程序设计模式 102
3.5.3 事件侦听器与事件处理程序 105
3.5.4 骰子投掷动作事件 106
3.6 总结 107
编程练习 108
书面练习 108
编程项目 112
4.1 选择排序 115
第4章 算法介绍 115
4.2.1 顺序搜索 119
4.2 简单的搜索算法 119
4.2.2 二叉搜索 121
4.3.2 算法性能：运行时间分析 126
4.3.1 系统／内存性能标准 126
4.3 算法的分析 126
4.3.3 Big-O符号 129
4.3.4 通用数量级 131
4.4 搜索算法的比较 133
书面练习 136
4.5 总结 136
编程练习 138
编程项目 141
第5章 泛型类与方法 143
5.1 Obiect超类 144
5.1.1 对象数组方法 145
5.1.2 通用的顺序搜索 146
5.2 Java泛型介绍 147
5.2.1 基于Object的Store类 148
5.2.2 泛型集合 149
5.2.3 泛型Store类 150
5.3 泛型接口 151
5.4.1 基本的泛型方法 155
5.4 泛型方法 155
5.4.2 为泛型类型使用绑定 156
5.5 泛型与继承 157
5.5.1 被绑定的泛型类型 158
5.5.2 泛型与通配符 160
5.6 泛型搜索／排序算法 161
5.7 总结 164
书面练习 165
编程练习 166
编程项目 168
6.1 递归的概念 171
第6章 递归 171
6.1.2 递归方法的实现 173
6.1.1 描述一个递归算法 173
6.1.3 递归的工作方式 175
6.1.4 多种基数表示法 176
6.2.1 构建一个刻度尺 179
6.2 递归的应用 179
6.2.2 Hanoi塔 181
6.3 递归的评价 185
6.3.1 Fibonacci方法 186
6.4 总结 189
6.3.2 使用递归的标准 189
书面练习 190
编程练习 192
编程项目 194
7.1 插入排序 195
第7章 排序算法 195
7.2.1 归并排序 198
7.2 分治排序算法 198
7.2.2 通用的排序方法 201
7.2.3 msort（）方法 202
7.2.4 归并排序的效率 205
7.3.1 使用基准值分割列表 206
7.3 快速排序 206
7.3.2 快速排序递归下降 209
7.3.3 pivotIndex（）方法 211
7.3.4 quicksort（）方法 213
7.3.5 快速排序的运行时间 215
7.3.6 排序算法的比较 216
7.4 第k大元素的查找 219
7.5 总结 221
书面练习 222
编程练习 223
编程项目 225
8.1 集合介绍 227
第8章 集合类型 227
8.2 集合的概述 229
8.2.1 List集合 230
8.2.2 Set集合 232
8.2.3 Map集合 233
8.2.4 适配器集合 234
8.2.5 Graph集合 235
8.2.6 Java Collections Framework 236
8.3 Bag集合 237
8.3.1 创建和使用一个Bag集合 238
8.3.2 应用：Eratosthenes筛选法 240
8.4 Bag类的实现 243
8.4.1 私有的remove（）方法 244
8.4.2 插入和访问方法 245
8.5 总结 246
8.4.3 集合的toString（）方法 246
书面练习 247
编程练习 248
编程项目 249
9.1 列表集合 251
第9章 基于数组的列表集合 251
9.2 ArrayList类 255
9.2.1 调整ArrayList的大小 257
9.3.1 ArrayList的连接 259
9.3 ArrayList应用程序 259
9.2.2 ArrayList API 259
9.3.2 closest-pair问题 262
9.4.1 ArrayList类的设计 266
9.4 实现ArrayList类 266
9.4.2 准备更大的容量 267
9.4.3 添加和删除元素 268
9.4.4 实现索引访问 272
9.5 Cloneable对象 273
9.5.1 克隆Time24对象 274
9.5.2 克隆引用变量 275
9.5.3 克隆ArrayList对象 277
9.6 ArrayList集合的评价 279
9.5.4 克隆数组 279
书面练习 280
9.7 总结 280
编程练习 282
编程项目 285
第10章 链表 287
10.1.1 创建链表 289
10.1 单链表 289
10.1.3 定位列表位置 291
10.1.2 扫描链表 291
10.1.5 通用的插入和删除操作 292
10.1.4 更新列表头 292
10.1.6 删除目标节点 294
10.2 双链表 298
10.3 LinkedList集合 299
10.3.1 LinkedList类 300
10.3.2 基于索引的LinkedList方法 301
10.3.3 访问列表尾 302
10.4.1 应用程序：选拔列表 304
10.4 使用LinkedList集合的应用程序 304
10.4.2 应用程序：回文列表 307
10.5 总结 309
书面练习 310
编程练习 313
编程项目 318
11.1 双链表 321
第11章 实现LinkedList类 321
11.1.1 DNode对象 322
11.1.2 使用DNode对象 323
11.2 循环双链表 325
11.2.1 声明双链表 326
11.2.2 更新双链表 327
11.2.3 应用程序：词汇杂乱 330
11.3.1 LinkedList类的私有成员 333
11.3 实现LinkedList类 333
11.3.3 列表中基于索引的访问 335
11.3.2 LinkedList类的构造函数 335
11.3.4 搜索列表 336
11.3.5 修改列表 337
书面练习 339
11.4 总结 339
编程练习 340
编程项目 342
12.1 迭代器的概念 345
第12章 迭代器 345
12.2 集合迭代器 346
12.2.1 迭代器扫描方法 347
12.2.2 通用的迭代器方法 350
12.2.3 使用增强的for语句进行迭代 351
12.3 列表迭代器 352
12.3.1 ListIterator方法set（） 353
12.3.2 列表的后向扫描 354
12.3.3 ListIterator方法add（） 356
12.3.4 迭代器设计模式 357
12.4.1 有序列表 358
12.4 迭代器的应用 358
12.4.2 删除有序列表中的重复值 360
12.5 OrderedList集合 361
12.5.1 OrderedList类方法 362
12.5.2 应用程序：确定字频 363
12.6 顺序集合的选择 367
12.5.3 适配器设计模式 367
12.7 总结 368
书面练习 369
编程练习 371
编程项目 373
13.1 迭代器实现设计 375
第13章 迭代器的实现 375
13.1.1 迭代器变量 376
13.1.2 迭代器接口方法 377
13.2 LinkedList迭代器 378
13.3.1 列表迭代器构造函数 381
13.3 列表迭代器的实现 381
13.3.2 列表迭代器的公共方法 382
13.4 快速失效迭代器 385
13.5 总结 386
书面练习 387
编程练习 388
编程项目 390
第14章 堆栈 391
14.1 堆栈集合 392
14.2 堆栈的应用 396
14.2.1 多种基数 397
14.2.2 符号对的平衡 400
14.3 递归与运行时堆栈 403
14.4 后缀表达式 405
14.4.1 后缀表达式的求解 406
14.4.2 PostfixEval类 408
14.4.3 evaluate（）方法 410
14.5.1 中缀表达式属性 412
14.5 中缀表达式的求解 412
14.5.2 中缀－后缀转换 413
14.6 总结 416
书面练习 417
编程练习 419
编程项目 422
第15章 队列与优先队列 425
15.1 Queue接口 426
15.1.1 创建一个队列集合类 427
15.1.2 应用：队列的调度 428
15.2 基数排序 430
15.3 有界队列 436
15.3.1 BQueue类的设计实现 438
15.3.2 BQueue类的声明 440
15.4 优先队列 441
15.4.1 优先队列接口 442
15.4.2 应用程序：支持服务库 444
15.5.1 对银行的仿真 447
15.5 事件驱动的仿真 447
15.5.2 仿真设计模式 449
15.5.3 BankSimulation类 451
书面练习 457
15.6 总结 457
编程练习 460
编程项目 463
16.1 树结构 465
第16章 二叉树 465
16.1.1 树的相关术语 466
16.1.2 二叉树 468
16.2 二叉树节点 473
16.3.1 递归树遍历 477
16.3 二叉树扫描算法 477
16.3.2 中序扫描算法 478
16.3.3 扫描方法的设计 480
16.3.4 迭代的层序扫描 482
16.3.5 Visitor设计模式 484
16.3.6 Visitor设计模式的使用 486
16.4.1 树高度的计算 489
16.4 树扫描算法的使用 489
16.4.2 复制二叉树 491
16.4.3 清除树 494
16.4.4 显示二叉树 495
16.5 排序的下界（选读） 497
16.6 总结 499
书面练习 500
编程练习 503
编程项目 505
17.1 表达式树 507
第17章 二叉树的应用 507
17.2 迭代的树遍历 512
17.2.1 中序迭代遍历 513
17.2.2 InorderIterator类的实现 515
17.3 Euler回路遍历 518
17.4.1 影像树的构建 521
17.4 绘制二叉树 521
17.4.2 影像树的显示 523
17.5 总结 525
编程练习 526
书面练习 526
编程项目 529
18.1 二叉搜索树 531
第18章 二叉搜索树 531
18.1.1 构建二叉搜索树 532
18.1.2 在二叉搜索树中定位对象 533
18.1.3 删除二叉搜索树节点 535
18.2 STree：一种二叉搜索树类 536
18.3 STree类的实现 540
18.3.1 STree类的私有成员与构造函数 541
18.3.2 插入和定位节点 542
18.3.3 删除节点 544
18.3.4 其他操作 550
18.4 STree迭代器 551
18.3.5 二叉搜索树操作的复杂度 551
书面练习 556
18.5 总结 556
编程练习 558
编程项目 559
第19章 集与映射 561
19.1.1 TreeSet集合 563
19.1 集 563
19.1.2 简单的拼写检查器 565
19.2 集运算符 568
19.2.1 集运算符的实现 569
19.2.2 应用程序：计算机账号的更新 572
19.2.3 使用有序集的操作 574
19.3.1 Map接口 577
19.3 映射 577
19.3.2 有序映射TreeMap 579
19.3.3 应用程序：一个学生时间记录映射 581
19.3.4 应用程序：计算机软件产品 583
19.4.1 键集集合视图 586
19.4 映射集合视图 586
19.4.2 条目集集合视图 588
19.4.3 应用程序：构建词汇索引 591
书面练习 596
19.5 总结 596
编程练习 598
编程项目 602
20.1 TreeSet类的实现 603
第20章 有序集与映射的实现 603
20.2 TreeMap类的实现 604
20.2.1 TreeMap类的设计 607
20.2.2 使用键对条目进行访问 608
20.2.3 更新条目 609
20.3 集合视图的实现 611
20.2.5 TreeSet和TreeMap类中插入和删除操作的复杂度 611
20.2.4 删除条目 611
20.3.1 查看视图 612
20.3.2 实现视图 614
20.3.3 keySet集合视图 615
书面练习 617
20.4 总结 617
编程练习 618
编程项目 621
21.1 散列法 625
第21章 实现映射的散列法 625
21.2.1 Java方法hashCode（） 627
21.2 散列函数的设计 627
21.2.2 自定义的散列函数 629
21.3.1 线性探查法 631
21.3 散列表的设计 631
21.3.2 具有不同列表的拉链法 633
21.3.3 再散列 635
21.4 作为集合的散列表 636
21.5 Hash类的实现 637
21.5.1 Hash类的add（）和rehash（）方法 639
21.5.2 Hash类的remove（）方法 641
21.5.3 Hash类迭代器的实现 642
21.6 无序映射集合 645
21.6.1 访问HashMap类中的条目 646
21.6.2 更新HashMap类中的条目 647
21.7 无序集集合 649
21.8 散列表的性能 650
21.9 总结 652
书面练习 653
编程练习 655
编程项目 657
22.1 基于数组的二叉树 661
第22章 堆 661
22.2 Comparator接口 663
22.2.1 通用比较对象 664
22.2.2 通用的数组排序 665
22.3 堆 667
22.3.1 堆的插入操作 668
22.3.2 堆的删除操作 670
22.3.3 堆的显示 674
22.4.1 堆的产生 676
22.4 使用堆进行排序 676
22.4.2 堆排序 679
22.4.3 静态堆方法概述 680
22.5 优先队列的实现 681
书面练习 684
22.6 总结 684
编程练习 687
编程项目 689
23.1 位数组 691
第23章 位数组与文件压缩 691
23.1.1 BitArray类 694
23.1.2 BitArray类的实现 696
23.2 二进制文件 699
23.3 Huffman压缩 703
23.3.1 Huffman树的构建 707
23.3.2 Huffman压缩的实现 708
23.3.3 Huffman解压的实现 714
23.4 序列化 716
23.4.1 对象的序列化 717
23.4.4 应用程序：对象的序列化 718
23.4.3 反序列化对象 718
23.4.2 使类可序列化 718
23.4.5 定制序列化 721
23.5 总结 723
书面练习 724
编程练习 728
编程项目 729
24.1 图的相关术语 731
第24章 图与路径 731
24.1.1 有向图 733
24.1.2 带权图 734
24.2.1 Graph接口 735
24.2 图的创建和使用 735
24.2.2 DiGraph类 737
24.3.1 广度优先搜索算法 741
24.3 图遍历算法 741
24.3.2 深度优先访问算法 746
24.3.3 深度优先搜索算法 751
24.3.4 无环图 753
书面练习 755
24.4 总结 755
编程练习 758
编程项目 761
25.1 拓扑排序 763
第25章 图算法 763
25.1.1 拓扑排序的目的 764
25.1.2 topologicalSort（）方法的实现 765
25.2 强连通组件 766
25.2.1 强连通组件算法的工作原理 768
25.2.2 strongComponents（）方法的实现 769
25.3 图最优化算法 771
25.4 最短路径算法 772
shortestPath（）方法的实现 774
25.5 Dijkstra最小路径算法 777
25.5.1 Dijkstra算法的设计 778
25.5.3 minimumPath（）方法的实现 781
25.5.2 Dijkstra算法的工作原理 781
25.5.4 无环图中的最小路径 784
25.6 最小生成树 787
25.6.1 Prim算法 788
25.6.2 minSpanTree（）方法的实现 790
书面练习 794
25.7 总结 794
编程练习 796
编程项目 798
26.1 图的表示 799
第26章 图的实现 799
26.2 DiGraph类的组件 800
26.2.1 顶点信息的表示 801
26.2.2 顶点映射与VertexInfo数组列表 803
26.3 DiGraph类设计 806
26.4 DiGraph类方法 807
26.4.2 邻接顶点的标识 808
26.4.1 ArrayList的访问 808
26.4.4 添加边 809
26.4.3 入度和出度的求解 809
26.4.5 删除顶点 810
26.4.6 图算法支持方法 813
26.4.7 图集合视图 814
26.5 总结 815
书面练习 816
编程练习 817
编程项目 819
第27章 平衡的搜索树 821
27.1 AVL树 822
27.2 AVLTree类的实现 824
27.2.1 AVLTree类的add（）方法 825
27.2.2 私有的addNode（）方法 831
27.2.3 add（）方法 832
27.3 2-3-4树 835
27.3.2 2-3-4树中的插入操作 836
27.3.1 2-3-4树的搜索 836
27.4 红－黑树 839
27.4.1 2-3-4树节点的表示 840
27.4.2 2-3-4树的红－黑树表示 841
27.4.4 4－节点的分割 844
27.4.3 在红－黑树中插入节点 844
27.4.5 红－黑树底部的插入操作 848
27.4.6 红－黑树的构建 849
27.4.7 红－黑树的搜索运行时间 850
27.4.8 在红－黑树中删除节点 851
27.5 RBTree类 852
书面练习 855
27.6 总结 855
编程练习 858
编程项目 859
28.1 基本的数论概念 861
第28章 数论与加密 861
28.1.1 Euclid GCD算法 862
28.1.2 模运算 863
28.1.3 Euler φ函数 865
28.2 安全的消息传输 866
28.2.2 使用用于RSA加密的密钥 867
28.2.1 创建用于RSA加密的密钥 867
28.3 大整数的使用 868
28.2.3 如何保护RSA通信 868
28.4 RSA的客户－服务器模式 872
28.5.1 Euclid GCD算法的实现 873
28.5 RSA算法（选读） 873
28.5.2 RSA定理 876
28.6 总结 877
书面练习 878
编程练习 879
编程项目 880
29.1 组合学 881
第29章 杂类算法 881
29.1.1 组合的构建 882
29.1.2 查找所有子集 883
29.1.3 列出置换 885
29.1.4 旅行推销员问题 888
29.2 动态编程 889
29.1.5 置换与TSP 889
29.2.1 由顶向下动态编程 890
29.2.2 使用动态编程的组合 893
29.2.3 由底向上动态编程 894
29.2.4 背包问题 896
29.2.5 Knapsack类 899
29.3 回溯：八皇后问题 903
29.3.1 问题分析 905
29.3.2 程序设计 907
29.3.3 显示棋盘 911
29.4 总结 913
书面练习 914
编程练习 915
编程项目 920
A.1 Java程序的结构 923
附录A Java入门 923
A.1.1 注释 924
A.1.4 控制台输出 925
A.1.3 变量的声明和使用 925
A.1.2 关键字与标识符 925
A.2 Java编程环境 926
A.3.1 数值类型 927
A.3 原始数据类型 927
A.3.2 Java的char类型 929
A.4.1 算术运算符 930
A.4 运算符 930
A.3.3 命名常量的声明 930
A.4.3 复合赋值运算符 931
A.4.2 赋值运算符 931
A.4.5 运算符的优先顺序 932
A.4.4 增量运算符 932
A.5 类型之间的转换 933
A.6 选择语句 935
A.6.1 if语句 937
A.6.2 嵌套的if语句 938
A.6.4 条件表达式运算符 939
A.6.3 多路if/else语句 939
A.6.5 switch语句 940
A.6.6 boolean类型 941
A.7.1 while语句 942
A.7 循环语句 942
A.7.2 do/while语句 943
A.7.3 for语句 944
A.7.4 break语句 945
A.8 数组 946
A.8.2 使用增强的for语句扫描数组 947
A.8.1 数组的初始化 947
A.8.3 二维数组 948
A.9.1 预定义的方法 949
A.9 Java的方法 949
A.9.2 自定义的方法 951
A.9.3 作为方法参数的数组 953
附录B Java关键字 957
附录C ASCII字符编码 959
附录D Java操作符的优先顺序 961
E.1 安装EZJava 963
附录E EZJava集成开发环境 963
E.2 启动EZJava 964
E.2.1 创建新文档 965
E.3 程序的编译和运行 966
E.2.2 菜单选项 966
E.4 项目的使用 968