Data Abstraction and Problem Solving with Java Walls and Mirrors

第i部分 问题求解技术

第1章 编程原理与软件工程

1．1 问题求解与软件工程

1．1．1 问题求解的含义

1．1．2 软件的生命周期

1．1．3 优秀解决方案的定义

1．2 模块化设计

1．2．1 抽象与信息隐藏

1．2．2 面向对象的设计

1．2．3 自上而下的设计

1．2．4 一般设计原则

1．3 关键编程问题

1．3．1 模块化

1．3．2 可修改

1．3．3 易用

1．3．4 防故障编程

1．3．5 风格

1．3．6 调试

1．4 小结

1．5 提示

.1．6 自我测试题

1．7 练习题

1．8 编程问题

第2章 递归：镜子

2．1 递归解决方案

2．1．1 递归值方法：n的阶乘

2．1．2 递归void方法：逆置字符串

2．2 计数

2．2．1 兔子繁殖

2．2．2 组织游行队伍

2．2．3 spock的困惑

2.3 数组查找

2．3．1 查找数组最大项

2．3．2 折半查找

2．3．3 查找数组中第k个最小项

2．4 组织数据

2．5 递归与效率

2．6 小结

2．7 提示

2．8 自我测试题

2．9 练习题

2．10 编程问题

第3章 数据抽象：墙

3．1 抽象数据类型

3．2 指定adt

3．2．1 adt列表

3．2．2 adt有序表

3．2．3 设计adt

3．2．4 公理

3．3 实现adt

3．3．1 java类

3．3．2 java接口

3．3．3 java异常

3．3．4 基于数组的adt列表实现

3．4 小结

3．5 提示

3．6 自我测试题

3．7 练习题

3．8 编程问题

第4章 链表

4．1 预备知识

4．1．1 对象引用

4．1．2 变长数组

4．1．3 基于引用的链表

4．2 链表编程

4．2．1 显示链表内容

4．2．2 从链表中删除指定节点

4．2．3 在链表特殊位置插入节点

4．2．4 adt列表的基于引用的实现

4．2．5 比较基于数组的实现和基于引用的实现

4．2．6 将链表传给方法

4．2．7 递归地处理链表

4．3 链表的各种变化

4．3．1 尾引用

4．3．2 循环链表

4．3．3 虚拟头节点

4．3．4 双向链表

4．4 清单应用程序

4．5 小结

4．6 提示

4．7 自我测试题

4．8 练习题

4．9 编程问题

第5章 递归问题求解技术

5．1 回溯

5．2 定义语言

5．2．1 语法知识基础

5．2．2 两种简单语言

5．2．3 代数表达式

5．3 递归和数学归纳法的关系

5．3．1 factorial递归算法的正确性

5．3．2 hanoi塔的成本

5．4 小结

5．5 提示

5．6 自我测试题

5．7 练习题

5．8 编程问题

第ii部分 使用抽象数据类型解决问题

第6章 栈

6．1 抽象数据类型

6．2 adt栈的简单应用

6．2．1 检查括号匹配

6．2．2 识别语言中的字符串

6．3 adt栈的实现

6．3．1 adt栈的基本数组的实现

6．3．2 adt栈的基于引用的实现

6．3．3 使用adt列表的实现

6．3．4 各种实现方式的比较

6．4 应用：代数表达式

6．4．1 计算后缀表达式

6．4．2 中缀表达式与后缀表达式的等价转换

6．5 应用：查找问题

6．5．1 使用栈的非递归解决方案

6．5．2 递归解决方案

6．6 栈和递归的关系

6．7 小结

6．8 提示

6．9 自我测试题

6．10 练习题

6．11 编程问题

第7章 队列

7．1 adt队列

7．2 adt队列的简单应用

7．2．1 读取字符串

7．2．2 识别回文

7．3 实现adt队列

7．3．1 基于引用的实现

7．3．2 基于数组的实现

7．3．3 用adt列表的实现

7．3．4 实现比较

7．4 基于位置的adt总览

7．5 模拟应用

7．6 小结

7．7 提示

7．8 自我测试题

7．9 练习题

7．10 编程问题

第8章 类关系

8．1 继承

8．1．1 java包

8．1．2 java访问修饰符

8．1．3 is-a和has-a关系

8．2 动态绑定和抽象类

8．2．1 抽象类

8．2．2 java接口

8．3 adt列表和有序表

8.3.1 列表迭代器的实现

8．3．2 使用adt列表的adt有序表的实现

8．4 面向对象方法的优势

8．5 小结

8．6 提示

8．7 自我测试题

8．8 练习题

8．9 编程问题

第9章 算法效率和排序

9．1 确定算法效率

9．1．1 算法的执行时间

9．1．2 算法增率

9．1．3 数量阶分析和大o表示法

9．1．4 正确分析问题

9．1．5 查找算法的效率

9．2 排序算法及其效率

9．2．1 选择排序

9．2．2 起泡排序

9．2．3 插入排序

9．2．4 归并排序

9．2．5 快速排序

9．2．6 基数排序

9．2．7 各种排序算法的比较

9．3 小结

9．4 提示

9．5 自我测试题

9．6 练习题

9．7 编程问题

第10章 树

10．1 术语

10．2 adt二叉树

10．2．1 adt二叉树的基本操作

10．2．2 adt二叉树的一般操作

10．2．3 二叉树的遍历

10．2．4 二叉树的表示

10．2．5 adt二叉树的基于引用的实现

10．2．6 用迭代器遍历树

10．3 adt二叉查找树

10．3．1 adt二叉查找树的操作算法

10．3．2 adt二叉查找树的基于引用的实现

10．3．3 二叉查找树操作的效率

10．3．4 树排序

10．3．5 将二叉查找树保存到文件

10．4 一般树

10．5 小结

10．6 提示

10．7 自我测试题

10．8 练习题

10．9 编程问题

第11章 表和优先队列

11．1 adt表

11．1．1 选择实现

11．1．2 adt表的基于数组的有序实现

11．1．3 adt表的二叉查找树实现

11．2 adt优先队列：adt表的变体

11．2．1 堆

11．2．2 adt优先队列的堆实现

11．2．3 堆排序

11．3 小结

11．4 提示

11．5 自我测试题

11．6 练习题

11．7 编程问题

第12章 表的高级实现

12．1 平衡查找树

12．1．1 2-3树

12．1．2 2-3-4树

12．1．3 红-黑树

12．1．4 avl树

12．2 散列

12．2．1 散列函数

12．2．2 解决冲突

12．2．3 散列效率

12．2．4 如何确立散列函数

12．2．5 表遍历：散列的低效操作

12．3 按多种形式组织数据

12．4 小结

12．5 提示

12．6 自我测试题

12．7 练习题

12．8 编程问题

第13章 图

13．1 术语

13．2 将图作为adt

13．3 图的遍历

13．3．1 深度优先查找

13．3．2 广度优先查找

13．4 图的应用

13．4．1 拓扑排序

13．4．2 生成树

13．4．3 最小生成树

13．4．4 最短路径

13．4．5 回路

13．4．6 一些复杂问题

13．5 小结

13．6 提示

13．7 自我测试题

13．8 练习题

13．9 编程问题

第14章 外部方法

14．1 了解外部存储

14．2 排序外部文件的数据

14．3 外部表

14．3．1 确定外部文件的索引

14．3．2 外部散列

14．3．3 b-树

14．3．4 遍历

14．3．5 多索引

14．4 小结

14．5 提示

14．6 自我测试题

14．7 练习题

14．8 编程练习

附录a java基本原理

a．1 程序结构

a．1．1 包

a．1．2 类

a．1．3 数据字段

a．1．4 方法

a．1．5 对象成员的访问方法

a．2 java语言基础知识

a．2．1 注释

a．2．2 标识符和关键词

a．2.3 变量

a．2．4 基本数据类型

a．2．5 引用

a．2．6 字面常量

a．2．7 命名常量

a．2．8 赋值和表达式

a．2．9 数组

a．3 有用的java类

a．3．1 object类

a．3．2 字符串类

a．4 java异常

a．4．1 捕获异常

a．4．2 抛出异常

a．5 文本输入和输出

a．5．1 输入

a．5．2 输出

a．6 选择语句

a．6．1 if语句

a．6．2 switch语句

a．7 迭代语句

a．7．1 while语句

a．7．2 for语句

a．7．3 do语句

a．8 文件输入和输出

a．8．1 文本文件

a．8．2 对象串行化

a．9 比较java和c++

a．10 小结

a．11 提示

附录b 统一字符代码

附录c java资源

c．1 java web站点

c．2 使用java 2软件开发包

附录d 数字归纳法

d.1 公理1

d.2 公理2

d.3 自我测试题

d.4 练习题

附录e java操作符