本书全面介绍了基本的数据结构，是高等院校“数据结构”课程的理想教材。本书作者从简单介绍开始，提供了直观的讨论和实际的应用，因此本书非常适合于学生阅读。条理清晰，内容翔实。书中的算法都有完整的Java程序，且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材，也是读者自学数据结构的极好读物。

本书涵盖了“数据结构和算法”的核心知识，使用Java语言描述，并对每种数据结构和算法的设计提供了多个实际应用。

本书共由三部分组成。第1部分包括第l～4章，回顾了Java编程概念及分析和测量程序性能的方法。第2部分包括第5～17章，深入研究了主要的数据结构。其中，第5～7章是本书研究的主干，探讨了表示数据的各种方法——数组、链表和模拟指针，其余章节论及了数据结构的其他表示方法。第3部分包括第18~22章，探讨了常见算法的设计方法。

本书条理清晰，内容翔实。书中的算法都有完整的Java程序，且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材，也是读者自学数据结构的极好读物。

前言

致谢

关于本书

第1章 Java综述

  1.1 简介

  1.2.Java程序结构

1.2.1 独立运行的程序和Applet

 1.2.2包

1.2.3引入类和包

1.2.4超类和子类

113 Java编译器和虚拟机

  1.4文档注释

  1.5数据类型

1.6方法

 1.6.1 参数

1.6.2重载方法

1.7异常

1.7.1抛出一个异常

1.7.2处理异常

 1.8 自定义数据类型

1.8.1Currency类

1.8.2 currency的数据成员

1.8.3 Currency的方法成员

1.8.4 Currency的构造函数

1.8.5创建Cu~ency的实例

1.8.6 Curtency的存取器(获取)方法

1.8.7 Currency的存取器(设置)方法

1.8.8调用方法和访问数据成员

1.8.9 Currency的输出和算术方法

1.8.10 main方法

1.9访问修饰符

1.1O继承和方法重写

 1.11重访Currency

 1.12定义一个异常类

 1.13泛型方法

1.13.1Computable接口

1.13.2泛型方法abc

1.13.3 java.1ang.Comparable接口

1.13-4 Operable接口

1.13.5 Zero和CloneableObject接口

1.13.6 MyInteger封装类

1.13.7使用数据类型和方法作为参数一

 1.14垃圾收集

 1.15递归

1.15.1 递归函数

1.15.2归纳

1.15.3递归方法

 1.16测试和调试

1.16.1什么是测试

1.16.2设计测试数据

1.16.3调试

 1.17参考资料和选择性读物

第2章 性能分析

 2.1什么是性能

 2.2空间复杂度

2.2.1空间复杂度的组成

2.2.2 范例

 2.3时间复杂度

2.3.1时间复杂度的组成

2.3.2运算计数

2.3.3最佳、最差和平均运算计数

2.3.4步骤计数

第3章 渐近表示法

 3.1 简介

 3.2渐近表示法

3.2.1 O表示法

3.2.2 Ω和Θ表示法

 3.3渐近数学(可选)

3.3.1O表示法

3.3.2 Ω表示法

3.3.3 Θ表示法

3.3.4 o表示法

3.3.5属性

 3.4复杂度分析范例

 3.5实用的复杂度

 3.6参考资料和选择性读物

第4章 性能测量

 4.1 简介

 4.2选择实例规模

 4.3开发测试数据

 4.4建立试验

 4.5缓存管理

4.5.1 一个简单的计算机模型

4.5.2遗漏缓存对运行时间的影响

4.5.3矩阵乘法

 4.6参考资料和选择性读物

第5章 线性列表——数组表示形式

 5.1数据对象和结构

 5.2线性列表数据结构

5.2.1 抽象数据类型LinearList

5.2.2 LinearList接口

5.2.3 LinearListAsAbstractClass抽象类

 5.3数组表示形式

5.3.1 表示形式

5.3.2改变一维数组的长度

5.3.3类ArrayLinearList

5.3.4 ArrayLinearLst的lterator

 5.4矢量表示形式

 5.5在单个数组中的多个列表

 5.6性能测量

5.7 java.util.ArrayList类

5-8参考资料和选择性读物

第6章 线性列表一链表表示

 6.1单向链表和链

6.1.1表示形式

6.1.2 ChainNode类

6.1.3 Chain类

6.1.4对ADT LinearList的扩展

  6.1.5 ExtendedChain类

6.1.6性能测量

 6.2循环列表和头节点

 6.3双向链表

 6.4链表术语表

 6.5应用

6.5.1 箱排序

6.5.2基数排序

6.5.3 凸包

第7章 线性列表——模拟指针

 7.1需要模拟指针

 7.2模拟指针

 7.3内存管理

7.3.1 SimulatedSpacel类

7.3.2 SimulatedSpace2类

7.3.3评价模拟内存管理

 7.4与垃圾收集比较

 7.5模拟链

7.5.1 SimulatedChain类

7.5.2性能测量

 7.6内存管理链

 7.7应用程序——并查问题

7.7.1 等价类

7.7.2应用程序

7.7.3第一个并查解决方案

7.7.4第二个并查解决方案

第8章 数组和矩阵

 8.1 数组

8.1.1抽象数据类型

8.1.2对一个Java数组进行索引

8.1.3行优先和列优先的映射

8.1.4数组的数组表示形式

8.1.5行优先和列优先的表示形式..

8.1.6不规则的二维数组

 8.2矩阵

8.2.1定义和操作

8.2.2 Matrix类

 8.3特殊矩阵

8.3.1定义和应用程序

8.3.2对角线矩阵，

8.3.3三对角线矩阵

8.3.4三角形矩阵

8.3.5对称矩阵

 8.4稀疏矩阵

8.4.1 目的

8.4.2使用单线性表的表示

8.4.3使用多线性表的表示

8.4.4性能测量

第9章 堆栈

 9.1定义和应用

 9.2抽象数据类型

 9.3数组表示

9.3.1实现为子类

9.3.2类arrayStack

9.3.3性能测量

 9.4链式表示

9.4.1类Derivedl-。inkedStaek

9.4.2类LinkedStack

9.4.3性能测量

 9.5应用

9.5.1括号匹配

9.5.2汉诺塔

9.5.3重排有轨电车

9.5.4开关箱路由

9.5.5离线等价类问题

9.5.6迷宫中的老鼠

 9.6参考资料和选择性读物

第10章 队列

 1O.1定义和应用

 10.2抽象数据类型

 10.3数组表示

10.3.1 表示方法

10.3.2 ArrayQueue类

 10.4链式表示

 10.5应用

10.5.1有轨电车的重新安排

10.5.2线路路由

10.5.3图像组件编号

10.5.4机械工厂模拟

 10.6参考资料和选择性读物

第11章 跳表和散列表

 11.1 字典

 11.2抽象数据类型

 11.3线性表表示

 11.4跳表表示(可选)

11.4.1理想情形

11.4.2插入和删除

11.4.3分配层级

11.4.4类SkipNode

11.4.5类SkipList

11.4.6 SkipList方法的复杂度

 11.5散列表表示

11.5.1理想散列

11.5.2散列函数和散列表

11.5.3线性探查法

11.5.4使用链表的散列

 11.6一个应用——文本压缩

11.6.1LZW压缩

11.6.2 Lzw压缩的实现

11.6.3 LZW解压缩

11.6.4 LZW解压缩的实现

11.6.5性能评估

 11.7参考资料和选择性读物

第12章 二叉树和其他树

 12.1树

 12.2二叉树

 12.3二叉树的属性

习题

 12.4二叉树的表示

12.4.1基于数组的表示

12.4.2链接表示

 12.5常见的二叉树操作

 12.6二叉树遍历

 12.7 ADT BinaryTtee

 12.8类LinkedBinaryTree

 12.9应用

12.9.1信号放大器的布置

12.9.2并查(Union.Find)问题

 12.10参考资料和选择性读物

第13章 优先级队列

 13.1定义和应用

 13.2抽象数据类型

 13.3线性表

 13.4堆

13.4.1 定义

13.4.2插入元素到最大堆

13.4.3从最大堆中删除元素

13.4.4最大堆的初始化

13.4.5 MaxHeap类

 13.5左倾树

13.5.1 基于高度和基于宽度的最小和最大左倾树

13.5.2插入到最大HBLT

13.5.3从最大HBLT中删除

13.5.4合并两棵最大HBLT

13.5.5初始化

13.5.6 MaxHBLT类

 13.6应用

13.6.1堆排序

13.6.2机器调度

13.6.3哈夫曼编码

 13.7参考资料和选择性读物

第14章 比赛树

 14.1优胜树及其应用

 14.2抽象数据类型WinnerTree.

 14.3优胜树的实现

14.3.1 表示

14.3.2初始化一棵优胜树

14.3.3重新进行比赛

14.3.4类CompleteWinnerTtee

 14.4失败树

 14.5应用

14.5.1使用首次适应法的容器装包

14.5.2使用下一适应法的容器装包

 14.6参考资料和选择性读物

第15章 二叉搜索树

 15.1 定义

15.1.1二叉搜索树

15.1.2可索引二叉搜索树

 15.2抽象数据类型

 15.3二叉搜索树的操作及其实现

15.3.1BinarySearchTtee类

15.3.2搜索

15.3.3插入一个元素

15.3.4删除一个元素

15.3.5二叉搜索树的高度

 15.4有重复记录的二叉搜索树

 15.5索引的二叉搜索树

 15.6应用

15.6.1 柱状图

15.6.2最优容器装包

1.5.613交叉分配

第16章 平衡搜索树

 16.1 AVL。树

16.1.1 定义

16.1.2 AV／.树的高度

16.1.3 AVL树的表示

16.1.4 AVL搜索树的搜索

16.1.5 AVL搜索树的插入

16.1.6从AVL搜索树中删除

 16.2红黑树

16.2.1 定义

16.2.2红黑树的表示

16.2.3红黑树的搜索

16.2.4红黑树的插入

16.2.5从红黑树中删除

16.2.6实现的考虑和复杂度

 l6.3伸展树

16.3.1 引言

16.3.2伸展操作

16.3.3分摊复杂度

 16.4 B.树

16.4.1索引顺序存取法(ISAM).

16.4.2 m.叉搜索树

16.4.3 m叉排序B-树

16.4.4 B.树的高度

16.4.5搜索B.树

16.4.6插入元素到B.树

16.4.7从B.树中删除

16.4-8节点结构

 16.5参考资料和选择性读物

第17章 图

 17.1定义

 17.2应用和更多的定义

习题

 17.3属性

 17.4 ADT Graph

 17.5不带权值的图的表示

17.5.1邻接矩阵

17.5.2链式邻接表

17.5.3数组邻接表

 17.6带权图的表示形式

 17.7类的实现

17.7.1不同的类

17.7.2邻接矩阵类

17.7.3到类Chain的扩展

17.7.4链表类

 17.8图的搜索方法

17.8.1广度优先搜索

17.8.2广度优先搜索的实现

17.8.3 Graph.bfs的复杂度分析

17.8.4深度优先搜索

17.8.5深度优先搜索的实现

1。7.8.6 Graph.dfs的复杂度分析

 17.9重访的应用

17.9.1查找路径

17.9.2连通图和连通分量

17.9.3 生成树

第18章 贪婪方法

 18.1最优化问题

 18.2贪婪方法

 18.3应用

18.3.1集装箱装载

18.3.2 0／1背包问题

18.3.3拓扑排序

18.3.4二分覆盖

18.3.5单源最短路径

18.3.6最小生成树

 18.4参考资料和选择性读物

第19章 分而治之

 l9.1方法

 19.2应用

19.2.1缺陷棋盘

19.2.2归并排序

19.2.3快速排序

19.2.4选择

19.2.5最近顶点对

 19.3求解递归等式

 19.4复杂度下界

19.4.1最小最大问题的下界

19.4.2排序的下界

第20章 动态规划

 20.1方法

 20.2应用

20.2.1O／l背包问题

20.2.2矩阵乘法链

20.2.3所有对最短路径

20.2.4带负值的单源最短路径

20.2.5不相交网子集

 20.3参考资料和选择性读物

第21章 回溯法

2 1.1方法

21.2应用

21.2.1集装箱装载

21.2.2 0门背包问题

21.2.3最大集团

21.2.4旅行售货员

21.2.5电路板排列

第22章 分支限界法

 22.1方法

 22.2应用

22.2.1集装箱装载

22.2.2 O／1背包问题

22.2.3最大集团

22.2.4旅行售货员

22.2.5电路板排列