第1章 绪论 1
1.1 数据结构研究内容 1
1.2 基本概念和术语 4
1.3 算法和算法分析 6
1.3.1 算法定义 7
1.3.2 算法分析预备知识 9
1.3.3 算法分析 11
本章小结 15
练习 15
第2章 线性表 17
2.1 线性表的定义 17
2.2 线性表的顺序存储结构及其运算 19
2.2.1 线性表的顺序存储结构 19
2.2.2 顺序表的基本运算 20
2.3 线性表的链式存储结构及其运算 25
2.3.1 单链表及其基本运算 25
2.3.2 循环链表 33
2.3.3 双向链表 34
2.4 顺序表和链表的比较 37
2.5 线性表的简单应用举例 38
本章小结 42
练习 42
第3章 栈和队列 45
3.1 栈的定义 45
3.2 栈的存储结构 46
3.2.1 顺序栈 46
3.2.2 链式栈 51
3.3 栈的简单应用举例 53
3.4 队列定义 61
3.5 队列的存储结构 62
3.5.1 循环队列 62
3.5.2 链式队列 68
3.6 队列的简单应用举例 71
本章小结 74
练习 74
第4章 矩阵的压缩存储 76
4.1 多维数组 76
4.1.1 数组的定义和操作 76
4.1.2 数组的顺序存储 77
4.2 特殊矩阵的压缩存储 78
4.2.1 对称矩阵 78
4.2.2 三角矩阵 79
4.2.3 带状矩阵 80
4.3 稀疏矩阵的压缩存储 81
4.3.1 三元组表 81
4.3.2 十字链表 88
本章小结 93
练习 94
第5章 递归 96
5.1 递归的定义 96
5.2 递归算法的工作原理 99
5.3 递归算法的实现形式 102
5.4 递归算法的分类 102
5.4.1 尾递归 102
5.4.2 非尾递归 103
5.4.3 间接递归 103
5.5 递归的简单应用举例 103
本章小结 106
练习 106
第6章 树与二叉树 107
6.1 树的基本概念 107
6.1.1 树的定义及相关术语 107
6.1.2 树的表示方法 109
6.1.3 树的性质 110
6.1.4 树的存储结构 111
6.2 二叉树 114
6.2.1 二叉树的定义 114
6.2.2 二叉树的性质 116
6.2.3 二叉树的存储结构 117
6.3 二叉树的运算 121
6.3.1 二叉树的遍历 121
6.3.2 二叉树的其他运算举例 127
6.4 线索化二叉树 129
6.4.1 线索二叉树的概念 129
6.4.2 二叉树的线索化 131
6.4.3 线索二叉树上的运算 132
6.5 树、森林与二叉树的转换 134
6.5.1 树转换为二叉树 135
6.5.2 森林转换为二叉树 135
6.5.3 二叉树转换为树和森林 136
6.6 树与森林的遍历 137
6.6.1 树的遍历 137
6.6.2 森林的遍历 138
6.7 Huffman树及其应用 138
6.7.1 哈夫曼树的基本概念 139
6.7.2 哈夫曼树的构造及实现 140
6.7.3 哈夫曼树的应用 142
本章小结 146
练习 146
第7章 图 148
7.1 图的定义与基本术语 148
7.2 图的存储结构 152
7.2.1 邻接矩阵表示法 152
7.2.2 邻接表表示法 156
7.3 图的遍历 162
7.3.1 图的深度优先搜索 162
7.3.2 图的广度优先搜索 164
7.4 图的生成树和最小生成树 165
7.4.1 生成树和最小生成树的概念 165
7.4.2 Prim算法 167
7.4.3 Kruskal算法 170
7.5 拓扑排序及其应用 171
7.6 最短路径 174
7.6.1 单源点的最短路径 174
7.6.2 每一对顶点之间的最短路径 178
本章小结 179
练习 179
第8章 查找 181
8.1 查找的基本概念 181
8.2 线性表的查找 183
8.2.1 顺序查找 183
8.2.2 折半查找 184
8.2.3 分块查找 186
8.3 树表的查找 187
8.3.1 二叉排序树 188
8.3.2 AVL树 193
8.3.3 B＿树与B＋树 200
8.4 散列表的查找 210
8.4.1 散列表的概念 210
8.4.2 散列函数 211
8.4.3 解决冲突的方法 213
8.4.4 散列表的查找及其分析 216
本章小结 217
练习 217
第9章 排序 219
9.1 排序的基本概念 219
9.2 插入排序 221
9.2.1 直接插入排序 221
9.2.2 希尔排序 223
9.3 交换排序 225
9.3.1 冒泡排序 226
9.3.2 快速排序 227
9.4 选择排序 230
9.4.1 直接选择排序 230
9.4.2 堆排序 232
9.5 二路归并排序 237
9.6 基数排序 240
9.7 外部排序 246
本章小结 246
练习 247
参考文献 249