第1章 绪论 1
1.1 数据结构的概念 1
1.1.1 为什么要学习数据结构 3
1.1.2 数据结构主要研究的内容 4
1.2 抽象数据类型的表示和实现 6
1.2.1 数据类型 6
1.2.2 抽象数据类型 7
1.2.3 抽象数据类型表示 8
1.2.4 抽象数据类型实现 8
1.3 算法和算法分析 10
1.3.1 算法定义 10
1.3.2 算法描述 11
1.3.3 算法性能分析与度量 12
1.3.4 常见的算法类型 15
本章总结 15
练习 15
实验1 18
第2章 线性表 20
2.1 线性表的逻辑结构 20
2.1.1 线性表的定义 20
2.1.2 线性表的抽象数据类型定义 20
2.2 线性表的顺序表示和实现 21
2.2.1 线性表的顺序表示 21
2.2.2 顺序表表示 22
2.2.3 顺序表基本操作的实现 23
2.2.4 顺序表应用举例 27
2.3 线性表的链式表示和实现 28
2.3.1 单向链表的概念 29
2.3.2 链表的类定义 31
2.3.3 链表基本操作的实现 32
2.3.4 双向链表 36
2.3.5 链表应用实例 39
2.4 链表和顺序表的选取 41
本章总结 42
练习 43
实验2 46
第3章 栈和队列 49
3.1 栈 49
3.1.1 栈的定义及操作 49
3.1.2 栈的抽象数据类型定义 50
3.1.3 栈的存储及操作实现 50
3.1.4 栈的应用 56
3.2 栈与递归 63
3.2.1 递归的概念 64
3.2.2 递归过程与递归工作栈 66
3.2.3 递归算法向非递归算法的转换 67
3.2.4 递归的应用 69
3.3 队列 70
3.3.1 队列的定义及基本操作 70
3.3.2 队列的抽象数据类型 70
3.3.3 队列的存储及操作实现 70
3.3.4 双端队列 75
3.3.5 队列的应用 75
本章总结 76
练习 76
实验3 79
第4章 数组和广义表 82
4.1 数组 82
4.1.1 多维数组的概念与存储表示 82
4.1.2 特殊矩阵及压缩存储 84
4.2 稀疏矩阵的压缩存储 85
4.2.1 稀疏矩阵的三元组表示 86
4.2.2 稀疏矩阵的链式存储法 95
4.3 广义表 97
4.3.1 广义表的基本概念 97
4.3.2 广义表的存储结构 99
本章总结 105
练习 105
实验4 108
第5章 串 110
5.1 串的基本概念及抽象数据类型 110
5.1.1 串的基本概念 110
5.1.2 串的抽象数据类型 110
5.1.3 c＋＋有关串的库函数 111
5.1.4 串的存储结构 113
5.2 串的顺序存储结构及基本操作实现 114
5.2.1 串的顺序存储结构 114
5.2.2 串的基本操作及实现 115
5.2.3 串的模式匹配 119
5.3 串的链式存储 123
本章总结 124
练习 124
实验5 126
第6章 树和二叉树 129
6.1 树的定义及表示 129
6.1.1 树的定义 129
6.1.2 树的表示 130
6.2 二叉树 131
6.2.1 二叉树的定义 131
6.2.2 二叉树的抽象数据类型 134
6.2.3 二叉树的存储结构 134
6.2.4 二叉树结点类操作实现 136
6.2.5 二叉树类操作实现 137
6.3 二叉树遍历及其应用 138
6.3.1 二叉树遍历的递归算法 138
6.3.2 二叉树遍历的应用 140
6.3.3 二叉树遍历的非递归算法 142
6.4 线索二叉树 144
6.4.1 线索二叉树定义 144
6.4.2 线索二叉树存储结构 145
6.4.3 线索二叉树基本操作 146
6.5 树和森林 149
6.5.1 树的存储表示 149
6.5.2 树和森林的遍历 155
6.6 huffman树及其应用 157
6.6.1 最优二叉树概念 157
6.6.2 最优二叉树的构造 158
6.6.3 huffman树的应用：huffman编码 162
本章总结 164
练习 165
实验6 167
第7章 图 170
7.1 图的基本概念 170
7.1.1 图的定义和术语 170
7.1.2 图的抽象数据类型 172
7.2 图的存储结构 172
7.2.1 图的邻接矩阵表示 173
7.2.2 图的邻接表表示 179
7.2.3 图的十字链表表示 187
7.2.4 图的邻接多重表表示 188
7.3 图的遍历 188
7.3.1 深度优先搜索 189
7.3.2 广度优先搜索 190
7.4 最小生成树 191
7.4.1 prim算法 192
7.4.2 kruskal算法 195
7.5 最短路径 197
7.5.1 路径的概念 197
7.5.2 从一个顶点到其余各顶点的最短路径 197
7.5.3 每对顶点之间的最短路径 200
7.6 dag及其应用 203
7.6.1 aov网络与拓扑排序 203
7.6.2 aoe网络与关键路径 206
本章总结 209
练习 210
实验7 213
第8章 查找 216
8.1 查找的基本概念 216
8.2 静态查找表 217
8.2.1 顺序查找 218
8.2.2 二分查找 219
8.2.3 分块查找 221
8.3 树表的查找 223
8.3.1 二叉排序树 223
8.3.2 平衡二叉树 227
8.3.3 红黑树 230
8.3.4 b树 235
8.3.5 b＋树 238
8.4 散列表查找 239
8.4.1 散列表的基本概念 239
8.4.2 哈希函数的构造方法 240
8.4.3 处理冲突方法 241
本章总结 245
练习 246
实验8 249
第9章 内部排序 252
9.1 排序的概念及算法性能分析 252
9.1.1 排序的概念 252
9.1.2 排序算法的性能分析 253
9.1.3 排序表类定义 253
9.2 插入排序 255
9.2.1 直接插入排序 255
9.2.2 希尔排序 257
9.3 交换排序 258
9.3.1 冒泡排序 259
9.3.2 快速排序 260
9.4 选择排序 263
9.4.1 直接选择排序 263
9.4.2 堆排序 265
9.5 归并排序 271
9.5.1 归并 271
9.5.2 归并排序算法 273
9.6 基数排序 273
9.6.1 基数排序思想 273
9.6.2 lsd基数排序 274
9.7 各种内部排序方法比较 277
本章总结 278
练习 279
实验9 282
附录 实验总结 285
参考文献 288