引言 组织数据 1
序言 设计类 3
P.1 封装 3
P.2 说明方法 5
P.2.1 注释 5
P.2.2 前置条件和后置条件 5
P.2.3 断言 6
P.3 Java接口 7
P.3.1 写一个接口 8
P.3.2 实现一个接口 9
P.3.3 接口作为数据类型 11
P.3.4 派生一个接口 12
P.3.5 接口内命名常量 13
P.4 选择类 14
P.4.1 标识类 15
P.4.2 CRC卡 15
P.4.3 统一建模语言 16
P.5 重用类 17
第1章 包 22
1.1 什么是包 22
1.2 说明一个包 23
1.3 使用ADT包 30
1.4 像使用自动贩卖机一样使用ADT 33
1.5 ADT集合 34
1.6 Java类库：接口Set 35
Java插曲1 泛型 39
第2章 使用数组实现包 43
2.1 使用固定大小的数组实现ADT包 43
2.1.1 类比 43
2.1.2 一组核心方法 44
2.1.3 实现核心方法 45
2.1.4 让实现安全 51
2.1.5 测试核心方法 54
2.1.6 实现更多的方法 56
2.1.7 删除项的方法 58
2.2 使用可变大小的数组实现ADT包 65
2.2.1 可变大小数组 65
2.2.2 包的新实现 68
2.3 使用数组实现ADT包的优缺点 70
Java插曲2 异常 75
第3章 使用链式数据实现包 82
3.1 链式数据 82
3.2 ADT包的链式实现 84
3.2.1 私有类Node 84
3.2.2 类LinkedBag的框架 85
3.2.3 定义一些核心方法 86
3.2.4 测试核心方法 89
3.2.5 方法getFrequencyOf 90
3.2.6 方法contains 91
3.3 从链中删除一项 92
3.4 有设置和获取方法的类Node 96
3.5 使用链实现ADT包的优缺点 98
第4章 算法的效率 102
4.1 动机 102
4.2 测量算法的效率 103
4.2.1 计数基本操作 105
4.2.2 最优、最差和平均情形 106
4.3 大O表示 107
4.4 描述效率 110
4.5 实现ADT包的效率 113
4.5.1 基于数组的实现 113
4.5.2 链式实现 114
4.5.3 两种实现的比较 115
第5章 栈 121
5.1 ADT栈的规格说明 121
5.2 使用栈来处理代数表达式 125
5.2.1 问题求解：检查中缀代数表达式中平衡的分隔符 125
5.2.2 问题求解：将中缀代数表达式转换为后缀表达式 129
5.2.3 问题求解：计算后缀表达式的值 133
5.2.4 问题求解：计算中缀表达式的值 134
5.3 程序栈 136
5.4 Java类库：类Stack 137
第6章 栈的实现 142
6.1 链式实现 142
6.2 基于数组的实现 144
6.3 基于向量的实现 148
6.3.1 Java类库：类Vector 148
6.3.2 使用向量实现ADT栈 149
第7章 递归 154
7.1 什么是递归 154
7.2 跟踪递归方法 158
7.3 返回一个值的递归方法 160
7.4 递归处理数组 162
7.5 递归处理链 165
7.6 递归方法的时间效率 166
7.6.1 countDown的时间效率 166
7.6.2 计算xn的时间效率 167
7.7 困难问题的简单求解方案 168
7.8 简单问题的低劣求解方案 172
7.9 尾递归 174
7.10 间接递归 176
7.11 使用栈来替代递归 177
Java插曲3 再谈泛型 185
第8章 排序简介 194
8.1 对数组进行排序的Java方法的组织 194
8.2 选择排序 195
8.2.1 迭代选择排序 196
8.2.2 递归选择排序 198
8.2.3 选择排序的效率 198
8.3 插入排序 199
8.3.1 迭代插入排序 199
8.3.2 递归插入排序 201
8.3.3 插入排序的效率 202
8.3.4 链式结点链的插入排序 203
8.4 希尔排序 205
8.4.1 算法 206
8.4.2 希尔排序的效率 207
8.5 算法比较 208
第9章 更快的排序方法 213
9.1 归并排序 213
9.1.1 归并数组 213
9.1.2 递归归并排序 214
9.1.3 归并排序的效率 216
9.1.4 迭代归并排序 217
9.1.5 Java类库中的归并排序 218
9.2 快速排序 218
9.2.1 快速排序的效率 219
9.2.2 创建划分 219
9.2.3 实现快速排序 221
9.2.4 Java类库中的快速排序 223
9.3 基数排序 223
9.3.1 基数排序的伪代码 225
9.3.2 基数排序的效率 225
9.4 算法比较 226
Java插曲4 再谈异常 231
第10章 队列、双端队列和优先队列 238
10.1 ADT队列 238
10.1.1 问题求解：模拟排队 241
10.1.2 问题求解：计算出售股票的资本收益 246
10.1.3 Java类库：接口Queue 248
10.2 ADT双端队列 249
10.2.1 问题求解：计算出售股票的资本收益 251
10.2.2 Java类库：接口Deque 252
10.2.3 Java类库：类ArrayDeque 253
10.3 ADT优先队列 254
10.3.1 问题求解：跟踪任务分配 255
10.3.2 Java类库：类PriorityQueue 257
第11章 队列、双端队列和优先队列的实现 262
11.1 队列的链式实现 262
11.2 基于数组实现队列 265
11.2.1 循环数组 266
11.2.2 带一个不用位置的循环数组 267
11.3 队列的循环链式实现 272
11.4 Java类库：类AbstractQueue 277
11.5 双端队列的双向链式实现 277
11.6 优先队列的可能实现方案 281
第12章 线性表 285
12.1 ADT线性表的规格说明 285
12.2 使用ADT线性表 291
12.3 Java类库：接口List 294
12.4 Java类库：类ArrayList 294
第13章 使用数组实现线性表 299
13.1 使用数组实现ADT线性表 299
13.1.1 类比 299
13.1.2 Java实现 301
13.1.3 使用数组实现ADT线性表的效率 308
第14章 使用链式数据实现线性表 313
14.1 链式结点链上的操作 313
14.1.1 在不同的位置添加结点 313
14.1.2 从不同的位置删除结点 316
14.1.3 私有方法getNodeAt 317
14.2 开始实现 318
14.2.1 数据域和构造方法 319
14.2.2 添加到线性表的表尾 320
14.2.3 在线性表的给定位置添加 321
14.2.4 方法isEmpty和toArray 322
14.2.5 测试核心方法 324
14.3 继续实现 325
14.4 细化实现 328
14.5 使用链实现ADT线性表的效率 331
14.6 Java类库：类LinkedList 333
Java插曲5 迭代器 338
第15章 ADT线性表的迭代器 351
15.1 实现迭代器的方法 351
15.2 独立类迭代器 351
15.3 内层类迭代器 354
15.3.1 链式实现 355
15.3.2 基于数组的实现 358
15.4 为什么迭代器方法在它自己的类中 360
15.5 基于数组实现接口ListIterator 362
Java插曲6 可变及不可变对象 372
第16章 有序表 378
16.1 ADT有序表的规格说明 378
16.2 链式实现 382
16.2.1 方法add 383
16.2.2 链式实现的效率 388
16.3 使用ADT线性表实现 388
Java插曲7 继承和多态 396
第17章 继承和线性表 405
17.1 使用继承实现有序表 405
17.2 设计一个基类 407
17.3 有序表的高效实现 413
第18章 查找 417
18.1 问题 417
18.2 在无序数组中查找 417
18.2.1 无序数组上的迭代顺序查找 418
18.2.2 无序数组上的递归顺序查找 418
18.2.3 顺序查找数组的效率 420
18.3 有序数组上的查找 420
18.3.1 有序数组上的顺序查找 420
18.3.2 有序数组上的二分查找 421
18.3.3 Java类库：方法binarySearch 424
18.3.4 数组上的二分查找的效率 425
18.4 无序链上的查找 426
18.4.1 无序链上的迭代顺序查找 426
18.4.2 无序链上的递归顺序查找 427
18.4.3 链上查找的效率 427
18.5 有序链上的查找 428
18.5.1 有序链上的顺序查找 428
18.5.2 有序链上的二分查找 428
18.6 查找方法的选择 429
Java插曲8 再论泛型 434
第19章 字典 436
19.1 ADT字典的规格说明 436
19.1.1 Java接口 439
19.1.2 迭代器 440
19.2 使用ADT字典 441
19.2.1 问题求解：电话号码簿 441
19.2.2 问题求解：字的频度 445
19.2.3 问题求解：字的词汇索引 448
19.3 Java类库：接口Map 451
第20章 字典的实现 455
20.1 基于数组的实现 455
20.1.1 基于数组的无序字典 455
20.1.2 基于数组的有序字典 459
20.2 链式实现 463
20.2.1 无序链式字典 464
20.2.2 有序链式字典 464
第21章 散列简介 470
21.1 什么是散列 470
21.2 散列函数 472
21.2.1 计算散列码 473
21.2.2 将散列码压缩为散列表的下标 475
21.3 解决冲突 476
21.3.1 开放地址的线性探查 476
21.3.2 开放地址的二次探查 480
21.3.3 开放地址的双散列 480
21.3.4 开放地址的潜在问题 482
21.3.5 拉链法 482
第22章 使用散列实现字典 488
22.1 散列的效率 488
22.1.1 装填因子 488
22.1.2 开放地址法的代价 489
22.1.3 拉链法的代价 490
22.2 再散列 491
22.3 冲突解决方案的比较 492
22.4 字典的散列实现 492
22.4.1 散列表中的项 492
22.4.2 数据域和构造方法 493
22.4.3 方法getValue/remove和add 495
22.4.4 迭代器 500
22.5 Java类库：类HashMap 501
22.6 Java类库：类HashSet 501
第23章 树 504
23.1 树的概念 504
23.1.1 层次结构 504
23.1.2 树的术语 505
23.2 树的遍历 509
23.2.1 二叉树的遍历 510
23.2.2 一般树的遍历 511
23.3 树的Java接口 512
23.3.1 所有树的接口 512
23.3.2 二叉树的接口 512
23.4 二叉树的示例 514
23.4.1 表达式树 514
23.4.2 决策树 515
23.4.3 二叉查找树 518
23.4.4 堆 520
23.5 一般树的示例 522
23.5.1 语法树 522
23.5.2 游戏树 523
第24章 树的实现 530
24.1 二叉树中的结点 530
24.2 ADT二叉树的实现 532
24.2.1 创建基本二叉树 532
24.2.2 方法privateSetTree 534
24.2.3 访问方法和赋值方法 536
24.2.4 计算高度和结点个数 536
24.2.5 遍历 537
24.3 表达式树的实现 541
24.4 一般树 543
24.5 使用二叉树表示一般树 543
Java插曲9 克隆 549
第25章 二叉查找树的实现 562
25.1 开始 562
25.1.1 二叉查找树的接口 563
25.1.2 重复项 564
25.1.3 开始定义类 565
25.2 查找和获取 566
25.3 遍历 567
25.4 添加一项 567
25.4.1 递归实现 568
25.4.2 迭代实现 571
25.5 删除一项 572
25.5.1 删除叶子结点中的项 573
25.5.2 删除仅有一个孩子的结点中的项 573
25.5.3 删除有两个孩子的结点中的项 574
25.5.4 删除根中的项 576
25.5.5 递归实现 576
25.5.6 迭代实现 579
25.6 操作效率 582
25.6.1 平衡的重要性 583
25.6.2 结点按什么次序添加 583
25.7 ADT字典的实现 584
第26章 堆的实现 594
26.1 再论：ADT堆 594
26.2 使用数组表示堆 594
26.3 添加项 597
26.4 删除根 599
26.5 创建堆 602
26.6 堆排序 603
第27章 平衡查找树 611
27.1 AVL树 611
27.1.1 单旋转 612
27.1.2 双旋转 614
27.1.3 实现细节 617
27.2 2-3树 620
27.2.1 在2-3树中进行查找 621
27.2.2 向2-3树中添加项 621
27.2.3 添加过程中分裂结点 623
27.3 2-4树 624
27.3.1 向2-4树中添加项 624
27.3.2 AVL树、2-3树和2-4树的比较 626
27.4 红黑树 626
27.4.1 红黑树的特性 627
27.4.2 向红黑树中添加项 628
27.4.3 Java类库：类TreeMap 632
27.5 B树 632
第28章 图 639
28.1 一些示例及术语 639
28.1.1 公路图 639
28.1.2 航空公司的航线 641
28.1.3 迷宫 642
28.1.4 先修课程 642
28.1.5 树 642
28.2 遍历 643
28.2.1 广度优先遍历 643
28.2.2 深度优先遍历 644
28.3 拓扑序 646
28.4 路径 648
28.4.1 寻找路径 648
28.4.2 无权图中的最短路径 648
28.4.3 带权图中的最短路径 651
28.5 ADT图的Java接口 654
第29章 图的实现 662
29.1 两个实现概述 662
29.1.1 邻接矩阵 662
29.1.2 邻接表 663
29.2 顶点和边 663
29.2.1 说明类Vertex 664
29.2.2 内部类Edge 666
29.2.3 类Vertex的实现 666
29.3 ADT图的实现 669
29.3.1 基本操作 669
29.3.2 图算法 672
附录A 文档和程序设计风格 678
附录B Java基础（在线） 682
附录C Java类（在线） 684
附录D 从其他类创建类 685
附录E 文件输入和输出（在线） 701
索引 702