作者：(美国)卡拉诺 (Frank M.Carrano) (美国)普里查德 (Janet J.Prichard) 译者：郭平 张敏

作者简介

Frank M.Carrano，Syracuse大学博士毕业，现任Rhode Island大学计算机科学系教授。主要研究方向为数据抽象技术、教育软体及多媒体技术。曾编写多本计算机书籍，如tOProblem Solving and DataAbstraction with C++；Walls andMirrors，Intermediate Problem Solving andData Structures：WallsandMirrors等.

Janet J.Prichard，Rhode Island大学博士毕业，现任Bryant大学计算机科学系副教授，具有15年程式设计课程的教学经验。主要研究方向为实时资料库与Web技术。

译者简介

郭平，湖南大学硕士。一直从事计算机网路与通信、高级程式设计、网路系统安全方面的教学、科研和开发工作；取得多项科研、学术成果，在核心期刊、国际国内会议卜发表论文30余篇。编着出版教材和译着5本，获军队科技进步奖励3项。卡要研究领域为计算机网路系统设计、网路性能分析、Web套用系统。

张敏，华中理工大学硕士，高级网路系统管理员。一直从事计算机网路系统与套用、高级程式设计与网路系统安全等方面的教学、科研和开发工作；取得多项科研，学术成果，在核心期刊、国际闲内会议上发表论文10余篇。主要研究领域为计算机网路套用系统、网路办公系统、Web应川系统。

《数据抽象和问题求解-Java语言描述》全面系统地讲述了如何利用Java语言解决实际问题，重点剖析了数据结构和数据抽象的核心概念，并通过大量示例向读者展示了面向对象程式设计理念的精髓。《数据抽象和问题求解-Java语言描述》在第1版的基础上完善了所有的Java代码，使用UML处理了所有伪代码，通过準确的概念讲解、贴切的示例和範围广泛的问题讨论，使老师和学生的教与学都变得轻鬆自如。《数据抽象和问题求解-Java语言描述》能够使读者系统地掌握问题求解技术和相关的编程技能，为日后的软体开发工作打下坚实的基础。

《数据抽象和问题求解-Java语言描述》表述严谨、推理缜密，适合作为计算机及相关专业本科学生的教材，也是一本技术含量很高的专业参考书。

第I部分问题求解技术

第1章Java编程基础

1.1程式结构

1.1.1包

1.1.2类

1.1.3数据栏位

1.1.4方法

1.1.5对象成员的访问方法

1.2Java基础知识

1.2.1注释

1.2.2标识符和关键字

1.2.3变数

1.2.4基本数据类型

1.2.5引用

1.2.6字面常量

1.2.7命名常量

1.2.8赋值和表达式

1.2.9数组

1.3分支结构

1.3.1if语句

1.3.2switch语句

1.4循环结构

1.4.1while语句

1.4.2for语句

1.4.3do语句

1.5有用的Java类

1.5.1Object类

1.5.2字元串类

1.6Java异常

1.6.1捕获异常

1.6.2抛出异常

1.7文本输入和输出

1.7.1输入

1.7.2输出

1.8档案输入和输出

1.8.1文本档案

1.8.2对象串列化

1.9小结

1.10提示

第2章编程原理与软体工程

2.1问题求解与软体工程

2.1.1问题求解的含义

2.1.2软体的生命周期

2.1.3优秀的解决方案

2.2面向对象设计

2.2.1抽象与信息隐藏

2.2.2面向对象的设计

2.2.3功能分解

2.2.4一般设计原则

2.2.5使用UML为面向对象的设计建模

2.2.6面向对象方式的优点

2.3关键编程问题

2.3.1模组化

2.3.2可修改性

2.3.3易用性

2.3.4防故障编程

2.3.5风格

2.3.6调试

2.4小结

2.5提示

2.6自我测试题

2.7练习题

2.8编程问题

第3章递归：镜子

3.1递归解决方案

3.1.1递归值方法：n的阶乘

3.1.2递归void方法：逆置字元串

3.2计数

3.2.1兔子繁殖(Fibonacci序列)

3.2.2组织游行队伍

3.2.3Spock的困惑

3.3数组查找

3.3.1查找数组的最大项

3.3.2二叉查找

3.3.3查找数组中的第k个最小项

3.4组织数据

3.5递归与效率

3.6小结

3.7提示

3.8自我测试题

3.9练习题

3.10编程问题

第4章数据抽象：墙

4.1抽象数据类型

4.2指定ADT

4.2.1ADT列表

4.2.2ADT有序表

4.2.3设计ADT

4.2.4公理(可选)

4.3实现ADT

4.3.1Java类

4.3.2Java接口

4.3.3Java包

4.3.4基于数组的ADT列表的实现

4.4小结

4.5提示

4.6自我测试题

4.7练习题

4.8编程问题

第5章鍊表

5.1预备知识

5.1.1对象引用

5.1.2变长数组

5.1.3基于引用的鍊表

5.2鍊表编程

5.2.1显示鍊表的内容

5.2.2从鍊表中删除指定的节点

5.2.3在鍊表的指定位置插入节点

5.2.4ADT列表的基于引用的实现

5.2.5比较基于数组的实现和基于引用的实现

5.2.6将鍊表传给方法

5.2.7递归地处理鍊表

5.3鍊表的各种变体

5.3.1尾引用

5.3.2循环鍊表

5.3.3虚拟头节点

5.3.4双向鍊表

5.4清单应用程式

5.5Java集合框架

5.5.1泛型

5.5.2叠代器

5.5.3JCF的List接口

5.6小结

5.7提示

5.8自我测试题

5.9练习题

5.10编程问题

第Ⅱ部分使用抽象数据

类型解决问题

第6章递归问题求解技术

6.1回溯

6.2定义语言

6.2.1语法知识基础

6.2.2两种简单语言

6.2.3代数表达式

6.3递归和数学归纳法的关係

6.3.1factorial递归算法的正确性

6.3.2Hanoi塔的成本

6.4小结

6.5提示

6.6自我测试题

6.7练习题

6.8编程问题

第7章栈

7.1ADT栈

7.2ADT栈的简单套用

7.2.1检查括弧匹配

7.2.2识别语言中的字元串

7.3ADT栈的实现

7.3.1ADT栈的基于数组的实现

7.3.2ADT栈的基于引用的实现

7.3.3使用ADT列表的实现

7.3.4各种实现的比较

7.3.5JCF的Stack类

7.4套用：代数表达式

7.4.1计算后缀表达式

7.4.2将中缀表达式转换为后缀表达式

7.5套用：查找问题

7.5.1使用栈的非递归解决方案

7.5.2递归解决方案

7.6栈和递归的关係

7.7小结

7.8提示

7.9自我测试题

7.10练习题

7.11编程问题

第8章伫列

8.1ADT伫列

8.2ADT伫列的简单套用

8.2.1读取字元串

8.2.2识别回文

8.3实现ADT伫列

8.3.1基于引用的实现

8.3.2基于数组的实现

8.3.3使用ADT列表的实现

8.3.4JCF接口Queue

8.3.5比较实现

8.4基于位置的ADT总览

8.5模拟套用

8.6小结

8.7提示

8.8自我测试题

8.9练习题

8.10编程问题

第9章高级Java主题

9.1继承

9.1.1Java访问修饰符

9.1.2is-a和has-a关係

9.2动态绑定和抽象类

9.2.1抽象类

9.2.2Java接口

9.3ADT列表和有序表

9.4Java泛型

9.4.1泛型类

9.4.2泛型通配符

9.4.3泛型类和继承

9.4.4类List的泛型实现

9.4.5泛型方法

9.5叠代器

9.6小结

9.7提示

9.8自我测试题

9.9练习题

9.10编程问题

第10章算法的效率和排序

10.1确定算法的效率

10.1.1算法的执行时间

10.1.2算法增率

10.1.3数量阶分析和大O表示法

10.1.4正确分析问题

10.1.5查找算法的效率

10.2排序算法及其效率

10.2.1选择排序

10.2.2冒泡排序

10.2.3插入排序

10.2.4归併排序

10.2.5快速排序

10.2.6基数排序

10.2.7各种排序算法的比较

10.2.8JCF的排序算法

10.3小结

10.4提示

10.5自我测试题

10.6练习题

10.7编程问题

第11章树

11.1术语

11.2ADT二叉树

11.2.1ADT二叉树的基本操作

11.2.2ADT二叉树的一般操作

11.2.3二叉树的遍历

11.2.4二叉树的表示

11.2.5ADT二叉树的基于引用的实现

11.2.6使用叠代器遍历树

11.3ADT二叉查找树

11.3.1ADT二叉查找树操作的算法

11.3.2ADT二叉查找树的基于引用的实现

11.3.3二叉查找树操作的效率

11.3.4树排序

11.3.5将二叉查找树保存到档案中

11.3.6JCF的二叉树查找算法

11.4一般树

11.5小结

11.6提示

11.7自我测试题

11.8练习题

11.9编程问题

第12章表和优先伫列

12.1ADT表

12.1.1选择实现

12.1.2ADT表的基于数组的有序实现

12.1.3ADT表的基于二叉查找树的实现

12.2ADT优先伫列：

ADT表的变体

12.2.1堆

12.2.2ADT优先伫列的堆实现

12.2.3堆排序

12.3JCF中的表和优先伫列

12.3.1JCF的Map接口

12.3.2JCF的Set接口

12.3.3JCF的PriorityQueue类

12.4小结

12.5提示

12.6自我测试题

12.7练习题

12.8编程问题

第13章表的高级实现方案

13.1平衡查找树

13.1.12-3树

13.1.22-3-4树

13.1.3红-黑树

13.1.4AVL树

13.2散列

13.2.1散列函式

13.2.2解决冲突

13.2.3散列效率

13.2.4如何确立散列函式

13.2.5表遍历：散列的低效操作

13.2.6JCF的Hashtable

和TreeMap类

13.2.7Hashtable类

13.2.8TreeMap类

13.3按多种形式组织数据

13.4小结

13.5提示

13.6自我测试题

13.7练习题

13.8编程问题

第14章图

14.1术语

14.2将图作为ADT

14.2.1实现图

14.2.2用JCF实现Graph类

14.3图的遍历

14.3.1深度优先查找

14.3.2广度优先查找

14.3.3用JCF实现BFS叠代器类

14.4图的套用

14.4.1拓扑排序

14.4.2生成树

14.4.3最小生成树

14.4.4最短路径

14.4.5迴路

14.4.6一些複杂问题

14.5小结

14.6提示

14.7自我测试题

14.8练习题

14.9编程问题

第15章外部方法

15.1了解外部存储

15.2排序外部档案的数据

15.3外部表

15.3.1确定外部档案的索引

15.3.2外部散列

15.3.3B-树

15.3.4遍历

15.3.5多索引

15.4小结

15.5提示

15.6自我测试题

15.7练习题

15.8编程练习

附录AJava与C++的区别

附录BUnicode字元代码

附录CJava资源

附录D数学归纳法

附录EJava操作符

附录F术语表

附录G自我测试题答案