1.1我们要去哪儿 1
本章计划 1
第1章 准备旅行 1
1.2数学、科学和工程学合而为一 2
1.3寻找计算机科学中的持久原则 5
1.4软件系统结构的原则 6
1.5效率与权衡 9
1.6软件工程原则 9
1.7数学方法 10
1.8关于编程符号的一些注释 11
练习 13
1.9后续内容简介 14
1.10本章小结 16
2.1介绍 18
第2章 面向对象编程导论 18
本章计划 20
2.2绘制矩形Applet 21
2.2.1学习内容 21
2.2.2复习题 32
2.2.3练习 32
2.3Draw Shapes Applet 32
2.3.1学习内容 32
2.3.2复习题 47
2.3.3练习 47
2.4结论 48
2.4.1学习内容 48
2.4.2复习题 49
2.6提示和技巧 50
2.5陷阱 50
2.4.3练习 50
2.7参考资料 51
2.8本章小结 51
第3章 链式数据表示 53
3.1介绍 53
本章计划 54
3.2什么是指针 55
3.2.1学习内容 55
3.2.2链式表示的两个实例 55
3.3使用Java的隐式指针 57
3.3.1学习内容 57
3.4指针图例表示法 61
3.4.1学习内容 61
3.3.3练习 61
3.3.2复习题 61
3.4.2复习题 64
3.4.3练习 64
3.5线性链表 65
3.5.1学习内容 65
3.5.2在链表中插入新的次节点 65
3.5.3声明Java链表类 68
3.5.4在链表中搜索某节点项 71
3.5.5删除链表的末端节点 73
3.5.6在链表中插入新的末端节点 75
3.5.7如何打印链表 77
3.5.8把所有东西合在一起 77
3.5.9现在还要做什么 78
3.5.10复习题 79
3.5.11练习 79
3.6.1学习内容 80
3.6其他链式数据结构 80
3.6.2复习题 82
3.6.3练习 82
3.7陷阱 82
3.8提示与技巧 82
3.9参考资料 84
3.10本章小结 84
第4章 递归 86
4.1介绍 86
本章计划 86
4.2递归地思考 87
4.2.1学习内容 87
4.2.2如何递归累加 87
4.2.3调用树与调用轨迹 91
4.2.4递归连乘 93
4.2.5逆转链表与数组 95
4.2.6逆转数组 98
4.2.7归纳思想 99
4.2.8复习题 100
4.2.9练习 101
4.3常见陷阱——无穷回归 103
4.3.1学习内容 103
4.3.2复习题 104
4.3.3练习 104
4.4一个指数级运行时间的递归算法 105
4.4.1学习内容 105
4.4.2汉诺塔 105
4.4.4练习 108
4.5陷阱 108
4.4.3复习题 108
4.6提示与技巧 109
4.7参考资料 109
4.8本章小结 109
第5章 模块化与数据抽象 111
5.1介绍 111
本章计划 113
5.2优先队列——一种抽象数据类型 114
5.2.1学习内容 114
5.2.2优先队列ADT接口 114
5.2.3复习题 117
5.2.4练习 118
5.3优先队列的两种实现 118
5.3.1学习内容 118
5.3.2利用已排序链表实现优先队列 119
5.3.3利用未排序数组实现优先队列 121
5.3.4复习题 123
5.3.5练习 124
5.4在优先队列中填入新型对象 124
5.4.1学习内容 124
5.4.2复习题 129
5.4.3练习 129
5.5程序设计中的模块化与信息隐藏 129
5.5.1学习内容 129
5.5.2复习题 131
5.6陷阱 131
5.7提示与技巧 132
5.8参考资料 132
5.9本章小结 132
第6章 线性数据结构——堆栈与队列 135
6.1介绍 135
本章计划 136
6.2堆栈的一些背景知识 137
6.2.1学习内容 137
6.2.2复习题 139
6.2.3练习 140
6.3堆栈与队列的ADT 140
6.3.1学习内容 140
6.3.2堆栈类与队列类的接口 142
6.3.3复习题 143
6.3.4练习 143
6.4使用堆栈ADT检查括号对称性 143
6.4.1学习内容 143
6.4.3练习 148
6.4.2复习题 148
6.5利用堆栈ADT计算后缀表达式 149
6.5.1学习内容 149
6.5.2复习题 153
6.5.3练习 153
6.6实现堆栈ADT 153
6.6.1学习内容 153
6.6.2顺序堆栈表示 154
6.6.3链式堆栈表示 155
6.6.4复习题 157
6.6.5练习 157
6.7Java如何利用堆栈实现递归方法调用 157
6.7.1学习内容 157
6.8.1学习内容 162
6.8队列ADT的实现 162
6.8.2顺序队列表示 162
6.7.3练习 162
6.7.2复习题 162
6.8.3链式队列表示 165
6.8.4比较链式队列表示与顺序队列表示 167
6.8.5复习题 168
6.8.6练习 168
6.9其他队列应用 169
6.9.1学习内容 169
6.9.2操作系统中的队列 169
6.9.3在模拟试验中使用队列 171
6.9.4复习题 173
6.9.5练习 173
6.10陷阱 173
6.11提示与技巧 173
6.13本章小结 174
6.12参考资料 174
第7章 链表、字符串和动态内存分配 176
7.1引言和动机 176
本章计划 176
7.2表 177
7.2.1学习内容 177
7.2.2表的ADT 177
7.2.3顺序表表示 178
7.2.4单向链表表示 179
7.2.5比较顺序和链式表示 180
7.2.6其他链表表示 182
7.2.7循环链表 182
7.2.8双向链表 182
7.2.9带有头节点的链表 183
7.2.10复习题 183
7.2.11练习 183
7.3.1学习内容 184
7.3广义表 184
7.3.2复习题 187
7.3.3练习 187
7.4广义表的应用 188
7.4.1学习内容 188
7.4.2复习题 190
7.4.3练习 190
7.5字符串 191
7.5.1学习内容 191
7.5.2Java中的只读字符串 191
7.5.3Java中的String Buffer 192
7.5.4在文本文件和字处理程序中的字符串表示方法 196
7.6.1学习内容 198
7.6动态内存分配 198
7.5.6练习 198
7.5.5复习题 198
7.6.2可用空间列表和垃圾收集 200
7.6.3堆和动态内存分配 203
7.6.4最先适配 204
7.6.5最佳适配 205
7.6.6分段存储与合并 205
7.6.7压缩以对应分配失败 206
7.6.8比较各种应用中堆的使用 208
7.6.9引用计数 209
7.6.10复习题 210
7.6.11练习 210
7.7陷阱 210
7.8揭示与技巧 211
7.9参考资料 211
7.10本章小结 214
8.1介绍 215
第8章 树与图 215
本章计划 217
8.2树——基本概念与术语 219
8.2.1学习内容 219
8.2.2复习题 220
8.2.3练习 221
8.3二叉树 221
8.3.1学习内容 221
8.3.2复习题 222
8.3.3练习 222
8.4顺序二叉树表示 223
8.4.1学习内容 223
8.4.2复习题 224
8.5.1学习内容 225
8.4.3练习 225
8.5应用——堆与优先队列 225
8.5.2转化成顺序表示 229
8.5.3堆操作性能的一些相关事实 232
8.5.4复习题 233
8.5.5练习 233
8.6遍历二叉树 233
8.6.1学习内容 233
8.6.2利用链接二叉树表示的遍历 235
8.6.3复习题 238
8.6.4练习 238
8.7二叉搜索树 238
8.7.1学习内容 238
8.7.2二叉搜索树的一些著名性能优势 244
8.7.4练习 249
8.7.3复习题 249
8.8AVL树及其性能 250
8.8.1学习内容 250
8.8.2利用插入与轮转构造AVL树 254
8.8.3轮转算法的平衡因子与说明 256
8.8.4AVL树的著名性能 257
8.8.5复习题 258
8.8.6练习 258
8.92-3树 258
8.9.1学习内容 258
8.9.2B－树——广义的2-3树 261
8.10级数树 262
8.10.1学习内容 262
8.9.4练习 262
8.9.3复习题 262
8.10.2复习题 263
8.10.3练习 263
8.11应用——哈夫曼编码 263
8.11.1学习内容 263
8.11.2复习题 267
8.11.3练习 267
8.12图——基本概念与术语 267
8.12.1学习内容 267
8.12.2一些正式定义 269
8.12.3路径、环路与邻接 269
8.12.4连通性与子图 269
8.12.5邻接点集与度 270
8.13.1学习内容 271
8.13图的表示 271
8.12.7练习 271
8.12.6复习题 271
8.13.2复习题 274
8.13.3练习 274
8.14图的搜索 274
8.14.1学习内容 274
8.14.2复习题 278
8.14.3练习 278
8.15拓扑排序 278
8.15.1学习内容 278
8.15.2复习题 281
8.15.3练习 281
8.16陷阱 281
8.18参考资料 282
8.17提示与技巧 282
8.19本章小结 283
第9章 散列和Table ADT 288
9.1介绍 288
本章计划 290
9.2TableADT 291
9.2.1学习内容 291
9.2.2复习题 292
9.2.3练习 292
9.3通过简单的示例介绍散列技术 292
9.3.1学习内容 292
9.3.2复习题 298
9.3.3练习 298
9.4冲突、负载因子和集群 298
9.4.1学习内容 298
9.4.3von Mises的概率讨论 299
9.4.2冲突 299
9.4.4负载因子和集群 301
9.4.5复习题 303
9.4.6练习 304
9.5使用开放定址的散列算法 304
9.5.1学习内容 304
9.5.2基本群集和它消失的两个示例 305
9.5.3保证探测序列会覆盖整个表 310
9.5.4性能公式 311
9.5.5比较理论和经验结果 313
9.5.6复习题 314
9.5.7练习 314
9.6选择散列函数 316
9.6.1学习内容 316
9.6.3其他的散列函数方法 317
9.6.2除余法 317
9.6.4复习题 318
9.6.5练习 318
9.7使用Table ADT的查找方法比较 318
9.7.1学习内容 318
9.7.2复习题 321
9.7.3练习 321
9.8陷阱 321
9.9提示与技巧 322
9.10参考资料 322
9.11本章小结 323
第10章 排序 327
10.1介绍 327
本章计划 328
10.2.1学习内容 330
10.2背景知识 330
10.2.3练习 333
10.3优先队列排序方法 333
10.3.1学习内容 333
10.2.2复习题 333
10.3.2一些预设 334
10.3.3优先队列排序 334
10.3.4SelectionSort 336
10.3.5HeapSort 338
10.3.6复习题 340
10.3.7练习 340
10.4分而治之方法 340
10.4.1学习内容 340
10.4.2MergeSort 341
10.4.3QuickSort 342
10.4.5练习 345
10.4.4复习题 345
10.5插入关键字且保持有序的方法 346
10.5.1学习内容 346
10.5.2InsertionSort 346
10.5.3TreeSort 348
10.5.4复习题 349
10.5.5练习 349
10.6O（n）方法——地址计算排序 350
10.6.1学习内容 350
10.6.2ProxmapSort 350
10.6.3RadixSort 361
10.6.4复习题 362
10.6.5练习 362
10.7.1学习内容 363
10.7.2ShellSort 363
10.7其他方法 363
10.7.3BubbleSort 367
10.7.4复习题 368
10.7.5练习 368
10.8比较与展望 368
10.8.1学习内容 368
10.8.2一些简单的智慧 371
10.8.3复习题 372
10.8.4练习 372
10.9陷阱 372
10.10提示与技巧 372
10.11参考资料 373
10.12本章小结 373
A.1JAVATM向导 378
附录A JAVATM要点回顾 378
本附录计划 381
A.2标识符、保留字、名称和变量 381
A.2.1学习内容 381
A.2.2复习题 383
A.2.3练习 383
A.3Java中的数据类型 383
A.3.1Java中的引用数据类型 385
A.3.2复习题 387
A.3.3练习 388
A.4Java操作符和表达式 388
A.4.1Java中的操作符优先级和结合 389
A.4.2复习题 393
A.5Java中的控制流 394
A.5.1选择语句 394
A.4.3练习 394
A.5.2循环语句 396
A.5.3break、continue和return语句 397
A.5.4复习题 399
A.5.5练习 399
A.6Java中的类、方法和对象 399
A.6.1学习内容 399
A.6.2复习题 400
A.6.3练习 401
A.7在Java中引入包 401
A.7.1学习内容 401
A.8Java中的注释 402
A.8.1学习内容 402
A.7.2复习题 402
A.7.3练习 402
A.8.2复习题 403
A.8.3练习 403
A.9参考资料 403
附录B 表示效率的语言 405
B.1介绍 405
本附录计划 405
B.2.1学习内容 406
B.2我们用什么来作为衡量标准 406
B.2.2复习题 411
B.2.3练习 411
B.3O－符号意义的直观认识 411
B.3.1学习内容 411
B.3.2注意 415
B.3.3本书其余部分所涉及的内容 416
B.4.1学习内容 418
B.4O－符号的定义和操纵 418
B.3.4复习题 418
B.3.5练习 418
B.4.2O－符号的正式证明的例子 419
B.4.3用于操纵O－符号的实用的简化操作 420
B.4.4复习题 422
B.4.5练习 422
B.5O－表示法没有包含的知识 423
B.5.1学习内容 423
B.5.2复习题 424
B.5.3练习 424
B.6参考资料 424
B.7本附录小结 425
附录C 软件工程概念 427
C.1介绍 427
本附录计划 428
C.2.2你是否有张获奖彩票 429
C.2面向对象设计与自顶向下编程 429
C.2.1学习内容 429
C.2.3选定Table的数据表示 438
C.2.4第二种求精 441
C.2.5复习题 444
C.2.6练习 444
C.3程序正确性证明 445
C.3.1学习内容 445
C.3.2一个小错误 450
C.3.3形式逻辑一瞥 452
C.3.4复习题 455
C.3.5练习 455
C.4程序转换与优化 456
C.4.1学习内容 456
C.5.1学习内容 461
C.5测试程序 461
C.4.2复习题 461
C.4.3练习 461
C.5.2自底向上测试 462
C.5.3单元测试、带格式的调试辅助器与测试容器 463
C.5.4集成测试 464
C.5.5可接受性测试与回归测试 464
C.5.6自顶向下测试与桩 465
C.5.7测试计划 467
C.5.8测试与验证的角色比较 467
C.5.9复习题 467
C.5.10练习 468
C.6度量与调节哲学 468
C.6.1学习内容 468
C.6.2比较一些二叉搜索方法 469
C.6.4练习 473
C.6.3复习题 473
C.7软件重用与自底向上编程 474
C.7.1学习内容 474
C.7.2复习题 477
C.7.3练习 477
C.8程序结构化与文档 477
C.8.1学习内容 477
C.8.2编程风格原则 483
C.8.3文档 484
C.8.4复习题 485
C.8.5练习 485
C.9陷阱 486
C.10提示与技巧 487
C.11参考资料 488
C.12附录小结 489