目录 3
第Ⅰ部分 问题求解技术 3
第1章 编程原理与软件工程 3
1.1 问题求解与软件工程 3
1.1.1 问题求解的含义 3
1.1.2 软件的生命周期 4
1.1.3 优秀解决方案的定义 10
1.2.1 抽象与信息隐藏 11
1.2 模块化设计 11
1.2.2 面向对象的设计 13
1.2.3 自上而下的设计 14
1.2.4 一般设计原则 15
1.3 关键编程问题 15
1.3.1 模块化 15
1.3.2 可修改 16
1.3.3 易用 17
1.3.4 防故障编程 18
1.3.5 风格 22
1.3.6 调试 25
1.4 小结 27
1.5 提示 28
1.6 自我测试题 28
1.7 练习题 28
1.8 编程问题 30
第2章 递归：镜子 32
2.1 递归解决方案 32
2.1.1 递归值方法：n的阶乘 34
2.1.2 递归void方法：逆置字符串 40
2.2 计数 47
2.2.1 兔子繁殖 47
2.2.2 组织游行队伍 50
2.2.3 Spock的困惑 51
2.3 数组查找 52
2.3.1 查找数组最大项 53
2.3.2 折半查找 54
2.3.3 查找数组中第k个最小项 57
2.4 组织数据 59
2.5 递归与效率 64
2.6 小结 66
2.7 提示 67
2.8 自我测试题 67
2.9 练习题 68
2.10 编程问题 73
第3章 数据抽象：墙 74
3.1 抽象数据类型 74
3.2 指定ADT 77
3.2.1 ADT列表 78
3.2.2 ADT有序表 81
3.2.3 设计ADT 82
3.2.4 公理 85
3.3 实现ADT 87
3.3.1 Java类 88
3.3.2 Java接口 94
3.3.3 Java异常 95
3.3.4 基于数组的ADT列表实现 96
3.4 小结 102
3.6 自我测试题 103
3.5 提示 103
3.7 练习题 104
3.8 编程问题 105
第4章 链表 107
4.1 预备知识 107
4.1.1 对象引用 108
4.1.2 变长数组 111
4.1.3 基于引用的链表 112
4.2.1 显示链表内容 115
4.2 链表编程 115
4.2.2 从链表中删除指定节点 117
4.2.3 在链表特殊位置插入节点 118
4.2.4 ADT列表的基于引用的实现 123
4.2.5 比较基于数组的实现和基于引用的实现 127
4.2.6 将链表传给方法 128
4.2.7 递归地处理链表 129
4.3 链表的各种变化 133
4.3.1 尾引用 133
4.3.2 循环链表 134
4.3.3 虚拟头节点 135
4.3.4 双向链表 136
4.4 清单应用程序 138
4.5 小结 142
4.6 提示 144
4.7 自我测试题 144
4.8 练习题 145
4.9 编程问题 147
5.1 回溯 150
第5章 递归问题求解技术 150
5.2 定义语言 154
5.2.1 语法知识基础 155
5.2.2 两种简单语言 156
5.2.3 代数表达式 158
5.3 递归和数学归纳法的关系 165
5.3.1 factorial递归算法的正确性 165
5.3.2 Hanoi塔的成本 166
5.4 小结 167
5.7 练习题 168
5.6 自我测试题 168
5.5 提示 168
5.8 编程问题 171
第Ⅱ部分 使用抽象数据类型解决问题 177
第6章 栈 177
6.1 抽象数据类型 177
6.2 ADT栈的简单应用 181
6.2.1 检查括号匹配 181
6.2.2 识别语言中的字符串 184
6.3 ADT栈的实现 185
6.3.1 ADT栈的基本数组的实现 186
6.3.2 ADT栈的基于引用的实现 188
6.3.3 使用ADT列表的实现 190
6.3.4 各种实现方式的比较 191
6.4 应用：代数表达式 191
6.4.1 计算后缀表达式 192
6.4.2 中缀表达式与后缀表达式的等价转换 193
6.5 应用：查找问题 195
6.5.1 使用栈的非递归解决方案 196
6.5.2 递归解决方案 202
6.6 栈和递归的关系 204
6.7 小结 205
6.8 提示 206
6.9 自我测试题 206
6.10 练习题 207
6.11 编程问题 209
第7章 队列 214
7.1 ADT队列 214
7.2.1 读取字符串 215
7.2 ADT队列的简单应用 215
7.2.2 识别同文 216
7.3 实现ADT队列 217
7.3.1 基于引用的实现 217
7.3.2 基于数组的实现 221
7.3.3 用ADT列表的实现 225
7.3.4 实现比较 226
7.4 基于位置的ADT总览 227
7.5 模拟应用 227
7.8 自我测试题 235
7.7 提示 235
7.6 小结 235
7.9 练习题 236
7.10 编程问题 238
第8章 类关系 241
8.1 继承 241
8.1.1 Java包 245
8.1.2 Java访问修饰符 246
8.1.3 is-a和has-a关系 247
8.2 动态绑定和抽象类 248
8.2.1 抽象类 251
8.2.2 Java接口 254
8.3 ADT列表和有序表 255
8.3.1 列表迭代器的实现 256
8.3.2 使用ADT列表的ADT有序表的实现 259
8.4 面向对象方法的优势 262
8.5 小结 263
8.6 提示 263
8.7 自我测试题 263
8.8 练习题 264
8.9 编程问题 265
第9章 算法效率和排序 268
9.1 确定算法效率 268
9.1.1 算法的执行时间 269
9.1.2 算法增率 270
9.1.3 数量阶分析和大O表示法 271
9.1.4 正确分析问题 273
9.1.5 查找算法的效率 275
9.2.1 选择排序 276
9.2 排序算法及其效率 276
9.2.2 起泡排序 279
9.2.3 插入排序 280
9.2.4 归并排序 282
9.2.5 快速排序 287
9.2.6 基数排序 295
9.2.7 各种排序算法的比较 297
9.3 小结 297
9.4 提示 298
9.5 自我测试题 298
9.6 练习题 299
9.7 编程问题 301
第10章 树 303
10.1 术语 303
10.2 ADT二叉树 309
10.2.1 ADT二叉树的基本操作 309
10.2.2 ADT二叉树的一般操作 310
10.2.3 二叉树的遍历 311
10.2.4 二叉树的表示 313
10.2.5 ADT二叉树的基于引用的实现 316
10.2.6 用迭代器遍历树 320
10.3 ADT二叉查找树 326
10.3.1 ADT二叉查找树的操作算法 329
10.3.2 ADT二叉查找树的基于引用的实现 341
10.3.3 二叉查找树操作的效率 344
10.3.4 树排序 347
10.3.5 将二叉查找树保存到文件 347
1 0.4 一般树 350
10.5 小结 351
10.7 自我测试题 352
10.6 提示 352
10.8 练习题 353
10.9 编程问题 358
第11章 表和优先队列 361
11.1 ADT表 361
11.1.1 选择实现 365
11.1.2 ADT表的基于数组的有序实现 370
11.1.3 ADT表的二叉查找树实现 372
11.2 ADT优先队列：ADT表的变体 374
11.2.1 堆 376
11.2.2 ADT优先队列的堆实现 382
11.2.3 堆排序 383
11.3 小结 387
11.4 提示 387
11.5 自我测试题 387
11.6 练习题 388
11.7 编程问题 390
第12章 表的高级实现 391
12.1 平衡查找树 391
12.1.1 2-3树 392
12.1.2 2-3-4树 407
12.1.3 红-黑树 412
12.1.4 AVL树 415
12.2 散列 418
12.2.1 散列函数 421
12.2.2 解决冲突 423
12.2.3 散列效率 429
12.2.4 如何确立散列函数 431
12.3 按多种形式组织数据 433
12.2.5 表遍历：散列的低效操作 433
12.4 小结 437
12.5 提示 438
12.6 自我测试题 438
12.7 练习题 438
12.8 编程问题 440
第13章 图 442
13.1 术语 442
13.2 将图作为ADT 444
13.3 图的遍历 447
13.3.1 深度优先查找 448
13.3.2 广度优先查找 450
13.4 图的应用 451
13.4.1 拓扑排序 451
13.4.2 生成树 454
13.4.3 最小生成树 456
13.4.4 最短路径 459
13.4.5 回路 462
13.4.6 一些复杂问题 464
13.5 小结 465
13.6 提示 465
13.7 自我测试题 465
13.8 练习题 466
13.9 编程问题 468
第14章 外部方法 469
14.1 了解外部存储 469
14.2 排序外部文件的数据 471
14.3 外部表 477
14.3.1 确定外部文件的索引 478
14.3.2 外部散列 481
14.3.3 B-树 484
14.3.4 遍历 491
14.3.5 多索引 492
14.4 小结 493
14.5 提示 494
14.6 自我测试题 494
14.7 练习题 494
14.8 编程练习 496
A.1 程序结构 497
附录A Java基本原理 497
A.1.1 包 498
A.1.2 类 498
A.1.3 数据字段 499
A.1.4 方法 499
A.1.5 对象成员的访问方法 501
A.2 Java语言基础知识 501
A.2.1 注释 501
A.2.4 基本数据类型 502
A.2.3 变量 502
A.2.2 标识符和关键词 502
A.2.5 引用 503
A.2.6 字面常量 503
A.2.7 命名常量 504
A.2.8 赋值和表达式 504
A.2.9 数组 506
A.3 有用的Java类 509
A.3.1 Obiect类 509
A.3.2 字符串类 509
A.4.1 捕获异常 513
A.4 Java异常 513
A.4.2 抛出异常 517
A.5 文本输入和输出 519
A.5.1 输入 519
A.5.2 输出 519
A.6 选择语句 520
A.6.1 if语句 520
A.6.2 switch语句 521
A.7.1 while语句 522
A.7 迭代语句 522
A.7.2 for语句 523
A.7.3 do语句 525
A.8 文件输入和输出 526
A.8.1 文本文件 527
A.8.2 对象串行化 532
A.9 比较Java和C++ 533
A.10 小结 536
A.11 提示 539
附录B 统一字符代码 540
附录C Java资源 542
C.1 Java Web站点 542
C.2 使用Java 2软件开发包 542
附录D 数学归纳法 544
D.1 公理1 544
D.2 公理2 545
D.3 自我测试题 547
D.4 练习题 547
附录E Java操作符 548