Java数据结构

第1章 准备旅行

1.1 我们要去哪儿

本章计划

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

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

1.4 软件系统结构的原则

1.5 效率与权衡

1.6 软件工程原则

1.7 数学方法

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

1.9 后续内容简介

1.10 本章小结

第2章 面向对象编程导论

2.1 介绍

本章计划

2.2 绘制矩形ApPkt

2.2.1 学习内容

2.2.2 复习题

2.2.3 练习

2.3 Draw5hapes Applet

2.3.1 学习内容

2.3.2 复习题

2.3.3 练习

2.4 结论

2.4.1 学习内容

2.4.2 复习题

2.4.3 练习

2.5 陷阱

2.6 提示和技巧

2.7 参考资料

2.8 本章小结

第3章 链式数据表示

3.1 介绍

本章计划

3.2 什么是指针

3.2.1 学习内容

3.2.2 链式表示的两个实例

3.3 使用Java的隐式指针

3.3.1 学习内容

3.3.2 复习题

3.3.3 练习

3.4 指针图例表示法

3.4.1 学习内容

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 其他链式数据结构

3.6.1 学习内容

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.3 复习题

4.4.4 练习

4.5 陷阱

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.2 复习题

6.4.3 练习

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.7 Java如何利用堆栈实现递归方法调用

6.7.1 学习内容

6.7.2 复习题

6.7.3 练习

6.8 队列ADT的实现

6.8.1 学习内容

6.8.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.12 参考资料

6.13 本章小结

第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 广义表

7.3.1 学习内容

7.3.2 复习题

7.3.3 练习

7.4 广义表的应用

7.4.1 学习内容

7.4.2 复习题

7.4.3 练习

7.5 字符串

7.5.1 学习内容

7.5.2 Java中的只读字符串

7.5.3 Java中的String Buffer

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

7.5.5 复习题

7.5.6 练习

7.6 动态内存分配

7.6.1 学习内容

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章 树与图

8.1 介绍

本章计划

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.12 图——基本概念与术语

8.12.1 学习内容

8.12.2 一些正式定义

8.12.3 路径、环路与邻接

8.12.4 连通性与子图

8.12.5 邻接点集与度

8.12.6 复习题

8.12.7 练习

8.13 图的表示

8.13.1 学习内容

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.17 提示与技巧

8.18 参考资料

8.19 本章小结

第9章 散列和Table ADT

9.1 介绍

本章计划

9.2 Table ADT

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.2 冲突

9.4.3 von Mises的概率讨论

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.2 除余法

9.6.3 其他的散列函数方法

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 背景知识

10.2.1 学习内容

10.2.2 复习题

10.2.3 练习

10.3 优先队列排序方法

10.3.1 学习内容

10.3.2 一些预设

10.3.3 优先队列排序

10.3.4 SelectionSort

10.3.5 HeapSort

10.3.6 复习题

10.3.7 练习

10.4 分而治之方法

10.4.1 学习内容

10.4.2 MergeSort

10.4.3 QuickSort

10.4.4 复习题

10.4.5 练习

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

10.5.1 学习内容

10.5.2 InsertionSort

10.5.3 TreeSort

10.5.4 复习题

10.5.5 练习

10.6 O(n)方法——地址计算排序

10.6.1 学习内容

10.6.2 ProxmapSort

10.6.3 RadixSort

10.6.4 复习题

10.6.5 练习

10.7 其他方法

10.7.1 学习内容

10.7.2 ShellSort

10.7.3 BubbleSort

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 JAVA要点回顾

A.1 JAVA向导

本附录计划

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

A.2.1 学习内容

A.2.2 复习题

A.2.3 练习

A.3 Java中的数据类型

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

A.3.2 复习题

A.3.3 练习

A.4 Java操作符和表达式

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

A.4.2 复习题

A.4.3 练习

A.5 Java中的控制流

A.5.1 选择语句

A.5.2 循环语句

A.5.3 break、continue和return语句

A.5.4 复习题

A.5.5 练习

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

A.6.1 学习内容

A.6.2 复习题

A.6.3 练习

A.7 在Java中引入包

A.7.1 学习内容

A.7.2 复习题

A.7.3 练习

A.8 Java中的注释

A.8.1 学习内容

A.8.2 复习题

A.8.3 练习

A.9 参考资料

附录B 表示效率的语言

B.1 介绍

本附录计划

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

B.2.1 学习内容

B.2.2 复习题

B.2.3 练习

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

B.3.1 学习内容

B.3.2 注意

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

B.3.4 复习题

B.3.5 练习

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

B.4.1 学习内容

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

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

B.4.4 复习题

B.4.5 练习

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

B.5.1 学习内容

B.5.2 复习题

B.5.3 练习

B.6 参考资料

B.7 本附录小结

附录C 软件工程概念

C.1 介绍

本附录计划

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

C.2.1 学习内容

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

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.4.2 复习题

C.4.3 练习

C.5 测试程序

C.5.1 学习内容

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.3 复习题

C.6.4 练习

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 附录小结