第1章 OOP基础 3
第一部分 基础 3
1.1 数据抽象 4
1.2 封装 5
1.3 对象 5
1.4 消息 5
1.5 方法 6
1.6 类 6
1.7 继承 8
1.8 后绑定多态 11
1.9 抽象类 11
1.10 接口 14
1.11 委托 16
1.13 本章小结 17
1.12 一般类和接口 17
1.14 习题 18
第2章 对象 19
2.1 引用的语义和创建对象 19
2.2 对象的赋值、别名和克隆 20
2.3 相等性测试 26
2.4 标量类型与引用类型 27
2.5 标量类型和它们的包装对象类 28
2.6 包装与解包——对象和标量之间的转换 29
2.7 字符串 29
2.8 字符串缓冲区 31
2.9 数组 32
2.10 向量 35
2.11 枚举 38
2.13 习题 42
2.12 本章小结 42
第3章 类的构造 44
3.1 类和类的使用者之间的责任——契约式设计 44
3.2 类的组织 46
3.3 类包 48
3.4 访问修饰符 51
3.5 命名习惯 51
3.6 本章小结 52
3.7 习题 52
第4章 类之间的关系 54
4.1 继承 54
4.2 聚合 55
4.3.1 规则说明 56
4.3 行为中的类关系——实例分析 56
4.3.2 分析和设计 57
4.3.3 实现 58
4.4 本章小结 63
4.5 习题 64
第5章 GUI的基本概念 65
5.1 GUI应用的图形部分 65
5.2 事件 69
5.2.1 由事件驱动的应用的特征 70
5.2.2 Java语言中的事件委托模型 72
5.3 MVC设计模式 76
5.3.1 M-VC中的继承方法 77
5.3.2 M-VC中的委托方法 78
5.4 本章小结 79
6.1 创建一个GUI的容器和基本组件 80
6.1.1 顶层窗口——基础 80
第6章 在Java中实现简单的GUI 80
6.1.2 简单的组件 81
6.1.3 在窗口中组织和放置组件 82
6.2 在Java语言中实现事件处理 84
6.2.1 实现一个EventListener接口的多种选择方式 84
6.2.2 处理一个点击按钮事件的步骤 85
6.2.3 在Java2平台上事件处理方式的例子 87
6.3 在Java中实现MVC 92
6.3.1 使用继承方法实现MVC计数器的例子 93
6.3.2 使用Beans方法实现MVC计数器的例子 95
6.5 习题 98
6.4 本章小结 98
第7章 错误和例外 102
7.1 例外和错误的分类 103
7.2 声明例外 104
7.3 抛出一个例外 107
7.4 创建例外类 107
7.5 处理例外 108
7.6 finally语句 109
7.7 对前面内容的综合——一个例子 109
7.8 捕捉运行时期的例外——一个例子 113
7.9 本章小结 114
7.10 习题 115
8.1 常规递归的属性 116
8.1.1 重要的属性和术语 116
第8章 递归 116
8.1.2 执行递归的步骤 118
8.2 迭代和递归 119
8.2.1 递归问题的迭代算法 119
8.2.2 迭代问题的递归算法 121
8.3递归 的相对复杂性 122
8.4 单递归和双递归实例 124
8.5 本章小结 130
8.6 习题 130
第二部分 数据结构 135
第9章 抽象数据类型 135
9.1 抽象数据类型Counter 135
9.2 抽象数据类型Fraction的一般属性 137
9.3 类Fraction的需求 138
9.4 类Fraction中部分方法的实现细节 141
9.5 创建一个Fraction实验程序来测试类Fraction 143
9.6 Fraction的说明文档——由javadoc产生 145
9.7 本章小结 145
9.8 习题 146
第10章 抽象数据类型容器 147
10.1 容器类的层次结构——顶层 148
10.2 最简单的容器——堆栈和队列 149
10.3 辅助性接口和类 151
10.4 容器类的层次结构 153
10.4.1 List接口及其后代 155
10.4.2 BinaryTree接口 159
10.4.3 SearchTable接口及其后代 160
10.4.4 接口Dictionary 163
10.4.5 接口Set 165
10.4.6 接口Heap 166
10.5 容器类层次结构的UML描述 168
10.6 本章小结 168
10.7 习题 169
第11章 堆栈和队列 170
11.1 堆栈 170
11.2 ArrayStack 171
11.3 LinkedStack 174
11.4 ArrayStack和LinkedStack的效率比较 178
11.5 队列 179
11.6 LinkedQueue 180
11.7 Stack/Queue实验程序 183
11.9 习题 184
11.8 本章小结 184
第12章 堆栈的应用 186
12.1 代数表达式的运算 186
12.2 变中缀表达式为后缀表达式的算法 188
12.3 代数函数运算的实现 190
12.3.1 中缀表达式到后缀表达式的转换 190
12.3.2 后缀表达式的运算 194
12.4 函数运算实验程序 196
12.5 本章小结 196
12.6 习题 197
第13章 列表 198
13.1 Dequeue——列表的一种实现 198
13.1.1 单链Dequeue 200
13.1.2 双链Dequeue 205
13.2.1 单链表 209
13.2 可定位的列表 209
13.2.2 双链表 214
13.3向量 列表 217
13.4 顺序列表 220
13.5 列表实验程序 224
13.6 复习栈和队列 225
13.7 本章小结 226
13.8 习题 227
第14章 树、堆和优先队列 229
14.1 树 229
14.1.1 抽象数据类型BinaryTree 230
14.1.2 表达式二叉树 239
14.1.3 表达式二叉树实验程序 246
14.2.1 抽象数据类型堆 247
14.2 堆 247
14.2.2 接口Heap的实现 250
14.2.3 堆实验程序 262
14.3 优先队列 263
14.3.1 优先队列的抽象数据类型 263
14.3.2 用队列向量来实现接口PriorityQueue 264
14.3.3 用堆来实现优先队列 270
14.3.4 优先队列实验程序 273
14.4 本章小结 274
14.5 习题 275
第15章 搜索树 277
15.1 对搜索表的回顾 277
15.2 二叉搜索树 278
15.3 在一棵二叉搜索树中查找一个节点 279
15.4 搜索树的平衡性 280
15.5 向一棵二叉搜索树中添加一个节点 282
15.6 从一棵二叉搜索树中删除一个节点 282
15.7 二叉搜索树的add方法 283
15.8 二叉搜索树的remove方法 284
15.9 二叉搜索树的性能 291
15.10 AVL树 291
15.11 树的旋转 293
15.12 AVL的add方法 295
15.13 AVL的删除 301
15.14 伸展树 302
15.15 SplayTree类的实现 304
15.16 跳跃表 308
15.17 跳跃表的实现 309
15.18 对上述内容的综合 316
15.19 可重用类DrawTree 320
15.20 本章小结 323
15.21 习题 324
第16章 散列表和集合 325
16.1 散列法和冲突处理 325
16.2 位操作 326
16.3 完美的散列函数 329
16.4 冲突 330
16.5 Hashtable类 332
16.6 冲突解决 336
16.6.1 线性链法 336
16.6.2 结合链法 339
16.7 集合 343
16.8 本章小结 348
16.9 习题 349
第17章 关联和字典 351
17.1 关联抽象数据类型 352
17.2 Dictionary接口 354
17.3 实现Dictionary接口 357
17.3.1 使用Hashtable实现Dictionary接口 358
17.3.2 使用Vector实现Dictionary接口 363
17.4 字典实验程序 367
17.5 OrderedDictionary接口 369
17.6 实现OrderedDictionary接口 371
17.7 排序字典实验程序 376
17.8 本章小结 377
17.9 习题 378
18.1.1 选择排序 380
第18章 排序 380
18.1 简单低效的排序法则 380
18.1.2 冒泡排序 381
18.2 高效的排序算法 382
18.2.1 快速排序 382
18.2.2 沟排序 385
18.3 二分检索 386
18.4 排序实验程序 387
18.5 本章小结 387
18.6 习题 387
附录 391
附录A 统一建模语言的概念 391
附录B 算法复杂度 398
附录C 安装和使用Foundations类库 402