目 录
第 1 章 绪论 1
1.1 数据结构的3种基本结构 1
1.1.1 线性结构 1
1.1.2 层次结构 3
1.1.3 网状结构 5
1.2 数据结构研究的主要问题 7
1.3 算法及描述 7
1.3.1 算法与算法特性 8
1.3.2 算法表示 9
1.4 算法效率分析 10
习 题 11

第 2 章 Java语言基础知识 13
2.1 Java语言概述 13
2.2 Java语言基础知识 14
2.2.1 数据类型 14
2.2.2 运算符 15
2.2.3 流程控制 16
2.2.4 数组 18
2.2.5 类与对象 20
2.2.6 类的封装性 24
2.2.7 类的继承性 24
2.2.8 类的多态性 24
2.2.9 抽象类和内部类 25
2.2.10 接口 26
2.2.11 包 27
2.2.12 异常处理 28
2.3 Java中的“指针”实现 31
习 题 34

第 3 章 线性表 36
3.1 实例引入 36
3.2 线性表的概述 37
3.2.1 线性表的概念 37
3.2.2 线性表的存储结构及操作 38
3.3 顺序表的基本操作及实现 39
3.3.1 顺序表的概述 39
3.3.2 顺序表的基本操作及实现 39
3.4 链表的基本操作及实现 43
3.4.1 链表 43
3.4.2 链表的分类 44
3.4.3 单链表的基本运算及实现 45
3.4.4 其他形式的链表的相关运算 47
3.4.5 算法实例 47
3.5 线性表的应用 48
3.5.1 顺序表的连接 49
3.5.2 单链表的逆转算法 50
习 题 52
实 训 53
实训3-1 顺序表应用 53
实训3-2 链表应用 56

第 4 章 栈和队列 58
4.1 实例引入 58
4.2 栈的相关概述 59
4.2.1 栈的定义 59
4.2.2 栈的相关概念 59
4.2.3 栈的操作过程 59
4.2.4 栈的存储结构 61
4.3 用数组实现顺序栈及操作 62
4.4 用类实现链式栈及相应操作 64
4.5 队列的相关概述 68
4.5.1 队列的定义 68
4.5.2 队列的相关概念 68
4.5.3 队列的存储结构 69
4.6 用数组实现顺序队列及相应操作 70
4.7 用类实现链队列及相应操作 73
4.8 栈和队列的实例应用 75
习 题 80
实 训 81
实训4-1 栈操作及应用 81
实训4-2 队列操作及应用 83

第 5 章 数组 85
5.1 实例引入 85
5.2 数组 86
5.2.1 数组的基本概念 86
5.2.2 一维数组 87
5.2.3 二维数组 87
5.3 特殊矩阵 91
5.3.1 对称矩阵 92
5.3.2 三角矩阵 93
5.3.3 对角矩阵 94
5.4 稀疏矩阵 94
习 题 99
实 训 100
实训5-1 数组操作 100

第 6 章 串 103
6.1 实例引入 103
6.2 串的概述 104
6.3 串的类型定义、存储结构及运算 104
6.3.1 串的抽象类型定义 104
6.3.2 串的存储结构 105
6.4 串的模式匹配 110
6.4.1 经典匹配算法 111
6.4.2 KMP匹配算法 112
习 题 115
实 训 116
实训6-1 串的基本操作 116
实训6-2 串的模式匹配 119

第 7 章 树与二叉树 122
7.1 实例引入 123
7.2 树 123
7.2.1 树的定义 123
7.2.2 树的表示方法 125
7.2.3 树的抽象数据类型 126
7.2.4 树的存储结构 126
7.3 二叉树 128
7.3.1 二叉树的定义 129
7.3.2 二叉树的性质 129
7.3.3 二叉树的抽象数据类型 131
7.3.4 二叉树的存储结构 132
7.4 二叉树的结点类及二叉树类 133
7.4.1 二叉树结点类 133
7.4.2 二叉树类 134
7.5 二叉树的遍历 135
7.5.1 二叉树遍历算法 135
7.5.2 二叉树遍历算法的实现 137
7.5.3 非递归的二叉树遍历算法 138
7.5.4 二叉树遍历的应用 139
*7.6 线索二叉树 141
7.6.1 线索二叉树的定义 141
7.6.2 线索二叉树的存储结构 141
7.6.3 遍历线索二叉树 142
7.6.4 构造中序线索二叉树 143
7.7 树和森林 144
7.7.1 树、森林与二叉树的转换 145
7.7.2 树和森林的遍历 147
7.8 树的应用 147
7.8.1 二叉排序树 147
7.8.2 哈夫曼树和哈夫曼编码 153
*7.8.3 决策树（Decision Tree） 160
习 题 164
实 训 166
实训7-1 二叉树 166
实训7-2 二叉排序树 168
实训7-3 哈夫曼树 170

第 8 章 图 172
8.1 实例引入 172
8.2 图的基本概念 173
8.2.1 图的定义 173
8.2.2 图的相关概念 174
8.3图的类型定义 177
8.4 图的存储结构 178
8.4.1 邻接矩阵 179
8.4.2 邻接表 180
8.5 图的遍历 181
8.5.1 深度优先搜索遍历 181
8.5.2 广度优先搜索遍历 185
8.6 生成树和最小生成树 189
8.6.1 生成树 189
8.6.2 克鲁斯卡尔（Kruskal）算法 190
8.6.3 普里姆（Prim）算法 191
8.7 最短路径问题 194
8.8 拓扑排序 199
8.8.1 AOV网 199
8.8.2 拓扑排序 200
8.9 关键路径 203
8.9.1 AOE网 203
8.9.2 关键路径 204
习 题 208
实 训 211
实训8-1 图的遍历 211
实训8-2 拓扑排序和关键路径 218

第 9 章 查找 220
9.1 实例引入 220
9.2 基本概念与术语 222
9.2.1 查找的概念 222
9.2.2 查找方法 222
9.3 顺序查找法 222
9.4 折半查找法 224
9.5 二叉排序树法 226
9.6 哈希查找法 232
9.6.1 哈希查找概念 233
9.6.2 哈希函数 234
9.6.3 冲突解决方法 236
9.7 应用实例 238
习 题 241
实 训 242
实训9-1顺序查找 242
实训9-2 折半查找 244

第 10 章 排序 246
10.1 实例引入 246
10.2 排序的概念 247
10.3 排序的分类 247
10.3.1 按照存储交换分类 247
10.3.2 按照内部排序的过程分类 248
10.3.3 按照排序的稳定性分类 248
10.4 插入排序 248
10.4.1 直接插入排序 248
10.4.2 希尔排序 250
10.5 交换排序 252
10.5.1 冒泡排序 252
10.5.2 快速排序 253
10.6 选择排序 255
10.6.1 直接选择排序 255
10.6.2 堆排序 257
10.7 其他排序 259
10.7.1 归并排序 260
10.7.2 基数排序 262
10.8 排序的工程应用举例 264
10.9 Java API提供的排序 266
习 题 267
实 训 268
实训10-1 插入排序 268
实训10-2 交换排序 270
实训10-3 选择排序 272
参考文献 278