1.1我们要去哪儿

本章计划

第1章 准备旅行

1.2数学、科学和工程学合而为一

1.3寻找计算机科学中的持久原则

1.4软件系统结构的原则

1.5效率与权衡

1.6软件工程原则

1.7数学方法

1.8关于编程符号的一些注释

练习

1.9后续内容简介

1.10本章小结

2.1介绍

第2章 面向对象编程导论

本章计划

2.2绘制矩形Applet

2.2.1学习内容

2.2.2复习题

2.2.3练习

2.3Draw Shapes Applet

2.3.1学习内容

2.3.2复习题

2.3.3练习

2.4结论

2.4.1学习内容

2.4.2复习题

2.6提示和技巧

2.5陷阱

2.4.3练习

2.7参考资料

2.8本章小结

第3章 链式数据表示

3.1介绍

本章计划

3.2什么是指针

3.2.1学习内容

3.2.2链式表示的两个实例

3.3使用Java的隐式指针

3.3.1学习内容

3.4指针图例表示法

3.4.1学习内容

3.3.3练习

3.3.2复习题

3.4.2复习题

3.4.3练习

3.5线性链表

3.5.1学习内容

3.5.2在链表中插入新的次节点

3.5.3声明Java链表类

3.5.4在链表中搜索某节点项

3.5.5删除链表的末端节点

3.5.6在链表中插入新的末端节点

3.5.7如何打印链表

3.5.8把所有东西合在一起

3.5.9现在还要做什么

3.5.10复习题

3.5.11练习

3.6.1学习内容

3.6其他链式数据结构

3.6.2复习题

3.6.3练习

3.7陷阱

3.8提示与技巧

3.9参考资料

3.10本章小结

第4章 递归

4.1介绍

本章计划

4.2递归地思考

4.2.1学习内容

4.2.2如何递归累加

4.2.3调用树与调用轨迹

4.2.4递归连乘

4.2.5逆转链表与数组

4.2.6逆转数组

4.2.7归纳思想

4.2.8复习题

4.2.9练习

4.3常见陷阱——无穷回归

4.3.1学习内容

4.3.2复习题

4.3.3练习

4.4一个指数级运行时间的递归算法

4.4.1学习内容

4.4.2汉诺塔

4.4.4练习

4.5陷阱

4.4.3复习题

4.6提示与技巧

4.7参考资料

4.8本章小结

第5章 模块化与数据抽象

5.1介绍

本章计划

5.2优先队列——一种抽象数据类型

5.2.1学习内容

5.2.2优先队列ADT接口

5.2.3复习题

5.2.4练习

5.3优先队列的两种实现

5.3.1学习内容

5.3.2利用已排序链表实现优先队列

5.3.3利用未排序数组实现优先队列

5.3.4复习题

5.3.5练习

5.4在优先队列中填入新型对象

5.4.1学习内容

5.4.2复习题

5.4.3练习

5.5程序设计中的模块化与信息隐藏

5.5.1学习内容

5.5.2复习题

5.6陷阱

5.7提示与技巧

5.8参考资料

5.9本章小结

第6章 线性数据结构——堆栈与队列

6.1介绍

本章计划

6.2堆栈的一些背景知识

6.2.1学习内容

6.2.2复习题

6.2.3练习

6.3堆栈与队列的ADT

6.3.1学习内容

6.3.2堆栈类与队列类的接口

6.3.3复习题

6.3.4练习

6.4使用堆栈ADT检查括号对称性

6.4.1学习内容

6.4.3练习

6.4.2复习题

6.5利用堆栈ADT计算后缀表达式

6.5.1学习内容

6.5.2复习题

6.5.3练习

6.6实现堆栈ADT

6.6.1学习内容

6.6.2顺序堆栈表示

6.6.3链式堆栈表示

6.6.4复习题

6.6.5练习

6.7Java如何利用堆栈实现递归方法调用

6.7.1学习内容

6.8.1学习内容

6.8队列ADT的实现

6.8.2顺序队列表示

6.7.3练习

6.7.2复习题

6.8.3链式队列表示

6.8.4比较链式队列表示与顺序队列表示

6.8.5复习题

6.8.6练习

6.9其他队列应用

6.9.1学习内容

6.9.2操作系统中的队列

6.9.3在模拟试验中使用队列

6.9.4复习题

6.9.5练习

6.10陷阱

6.11提示与技巧

6.13本章小结

6.12参考资料

第7章 链表、字符串和动态内存分配

7.1引言和动机

本章计划

7.2表

7.2.1学习内容

7.2.2表的ADT

7.2.3顺序表表示

7.2.4单向链表表示

7.2.5比较顺序和链式表示

7.2.6其他链表表示

7.2.7循环链表

7.2.8双向链表

7.2.9带有头节点的链表

7.2.10复习题

7.2.11练习

7.3.1学习内容

7.3广义表

7.3.2复习题

7.3.3练习

7.4广义表的应用

7.4.1学习内容

7.4.2复习题

7.4.3练习

7.5字符串

7.5.1学习内容

7.5.2Java中的只读字符串

7.5.3Java中的String Buffer

7.5.4在文本文件和字处理程序中的字符串表示方法

7.6.1学习内容

7.6动态内存分配

7.5.6练习

7.5.5复习题

7.6.2可用空间列表和垃圾收集

7.6.3堆和动态内存分配

7.6.4最先适配

7.6.5最佳适配

7.6.6分段存储与合并

7.6.7压缩以对应分配失败

7.6.8比较各种应用中堆的使用

7.6.9引用计数

7.6.10复习题

7.6.11练习

7.7陷阱

7.8揭示与技巧

7.9参考资料

7.10本章小结

8.1介绍

第8章 树与图

本章计划

8.2树——基本概念与术语

8.2.1学习内容

8.2.2复习题

8.2.3练习

8.3二叉树

8.3.1学习内容

8.3.2复习题

8.3.3练习

8.4顺序二叉树表示

8.4.1学习内容

8.4.2复习题

8.5.1学习内容

8.4.3练习

8.5应用——堆与优先队列

8.5.2转化成顺序表示

8.5.3堆操作性能的一些相关事实

8.5.4复习题

8.5.5练习

8.6遍历二叉树

8.6.1学习内容

8.6.2利用链接二叉树表示的遍历

8.6.3复习题

8.6.4练习

8.7二叉搜索树

8.7.1学习内容

8.7.2二叉搜索树的一些著名性能优势

8.7.4练习

8.7.3复习题

8.8AVL树及其性能

8.8.1学习内容

8.8.2利用插入与轮转构造AVL树

8.8.3轮转算法的平衡因子与说明

8.8.4AVL树的著名性能

8.8.5复习题

8.8.6练习

8.92-3树

8.9.1学习内容

8.9.2B－树——广义的2-3树

8.10级数树

8.10.1学习内容

8.9.4练习

8.9.3复习题

8.10.2复习题

8.10.3练习

8.11应用——哈夫曼编码

8.11.1学习内容

8.11.2复习题

8.11.3练习

8.12图——基本概念与术语

8.12.1学习内容

8.12.2一些正式定义

8.12.3路径、环路与邻接

8.12.4连通性与子图

8.12.5邻接点集与度

8.13.1学习内容

8.13图的表示

8.12.7练习

8.12.6复习题

8.13.2复习题

8.13.3练习

8.14图的搜索

8.14.1学习内容

8.14.2复习题

8.14.3练习

8.15拓扑排序

8.15.1学习内容

8.15.2复习题

8.15.3练习

8.16陷阱

8.18参考资料

8.17提示与技巧

8.19本章小结

第9章 散列和Table ADT

9.1介绍

本章计划

9.2TableADT

9.2.1学习内容

9.2.2复习题

9.2.3练习

9.3通过简单的示例介绍散列技术

9.3.1学习内容

9.3.2复习题

9.3.3练习

9.4冲突、负载因子和集群

9.4.1学习内容

9.4.3von Mises的概率讨论

9.4.2冲突

9.4.4负载因子和集群

9.4.5复习题

9.4.6练习

9.5使用开放定址的散列算法

9.5.1学习内容

9.5.2基本群集和它消失的两个示例

9.5.3保证探测序列会覆盖整个表

9.5.4性能公式

9.5.5比较理论和经验结果

9.5.6复习题

9.5.7练习

9.6选择散列函数

9.6.1学习内容

9.6.3其他的散列函数方法

9.6.2除余法

9.6.4复习题

9.6.5练习

9.7使用Table ADT的查找方法比较

9.7.1学习内容

9.7.2复习题

9.7.3练习

9.8陷阱

9.9提示与技巧

9.10参考资料

9.11本章小结

第10章 排序

10.1介绍

本章计划

10.2.1学习内容

10.2背景知识

10.2.3练习

10.3优先队列排序方法

10.3.1学习内容

10.2.2复习题

10.3.2一些预设

10.3.3优先队列排序

10.3.4SelectionSort

10.3.5HeapSort

10.3.6复习题

10.3.7练习

10.4分而治之方法

10.4.1学习内容

10.4.2MergeSort

10.4.3QuickSort

10.4.5练习

10.4.4复习题

10.5插入关键字且保持有序的方法

10.5.1学习内容

10.5.2InsertionSort

10.5.3TreeSort

10.5.4复习题

10.5.5练习

10.6O（n）方法——地址计算排序

10.6.1学习内容

10.6.2ProxmapSort

10.6.3RadixSort

10.6.4复习题

10.6.5练习

10.7.1学习内容

10.7.2ShellSort

10.7其他方法

10.7.3BubbleSort

10.7.4复习题

10.7.5练习

10.8比较与展望

10.8.1学习内容

10.8.2一些简单的智慧

10.8.3复习题

10.8.4练习

10.9陷阱

10.10提示与技巧

10.11参考资料

10.12本章小结

A.1JAVATM向导

附录A JAVATM要点回顾

本附录计划

A.2标识符、保留字、名称和变量

A.2.1学习内容

A.2.2复习题

A.2.3练习

A.3Java中的数据类型

A.3.1Java中的引用数据类型

A.3.2复习题

A.3.3练习

A.4Java操作符和表达式

A.4.1Java中的操作符优先级和结合

A.4.2复习题

A.5Java中的控制流

A.5.1选择语句

A.4.3练习

A.5.2循环语句

A.5.3break、continue和return语句

A.5.4复习题

A.5.5练习

A.6Java中的类、方法和对象

A.6.1学习内容

A.6.2复习题

A.6.3练习

A.7在Java中引入包

A.7.1学习内容

A.8Java中的注释

A.8.1学习内容

A.7.2复习题

A.7.3练习

A.8.2复习题

A.8.3练习

A.9参考资料

附录B 表示效率的语言

B.1介绍

本附录计划

B.2.1学习内容

B.2我们用什么来作为衡量标准

B.2.2复习题

B.2.3练习

B.3O－符号意义的直观认识

B.3.1学习内容

B.3.2注意

B.3.3本书其余部分所涉及的内容

B.4.1学习内容

B.4O－符号的定义和操纵

B.3.4复习题

B.3.5练习

B.4.2O－符号的正式证明的例子

B.4.3用于操纵O－符号的实用的简化操作

B.4.4复习题

B.4.5练习

B.5O－表示法没有包含的知识

B.5.1学习内容

B.5.2复习题

B.5.3练习

B.6参考资料

B.7本附录小结

附录C 软件工程概念

C.1介绍

本附录计划

C.2.2你是否有张获奖彩票

C.2面向对象设计与自顶向下编程

C.2.1学习内容

C.2.3选定Table的数据表示

C.2.4第二种求精

C.2.5复习题

C.2.6练习

C.3程序正确性证明

C.3.1学习内容

C.3.2一个小错误

C.3.3形式逻辑一瞥

C.3.4复习题

C.3.5练习

C.4程序转换与优化

C.4.1学习内容

C.5.1学习内容

C.5测试程序

C.4.2复习题

C.4.3练习

C.5.2自底向上测试

C.5.3单元测试、带格式的调试辅助器与测试容器

C.5.4集成测试

C.5.5可接受性测试与回归测试

C.5.6自顶向下测试与桩

C.5.7测试计划

C.5.8测试与验证的角色比较

C.5.9复习题

C.5.10练习

C.6度量与调节哲学

C.6.1学习内容

C.6.2比较一些二叉搜索方法

C.6.4练习

C.6.3复习题

C.7软件重用与自底向上编程

C.7.1学习内容

C.7.2复习题

C.7.3练习

C.8程序结构化与文档

C.8.1学习内容

C.8.2编程风格原则

C.8.3文档

C.8.4复习题

C.8.5练习

C.9陷阱

C.10提示与技巧

C.11参考资料

C.12附录小结