第1章 绪论 1
1.1 数据结构起源 1
1.2 基本概念和术语 1
1.2.1 基本概念 1
1.2.2 数据结构 2
1.3 抽象数据类型 4
1.4 算法和算法分析 5
1.4.1 算法 5
1.4.2 算法的时间复杂度 5
1.4.3 最好、最坏和平均时间复杂度 6
1.4.4 算法的空间复杂度 7
1.5 本章小结 7
习题 7
第2章 线性表 9
2.1 线性表定义 9
2.2 线性表的顺序存储结构和实现 10
2.2.1 线性表的顺序存储结构 10
2.2.2 顺序表基本运算的实现 11
2.3 线性表的链式存储结构和实现 14
2.3.1 单链表的定义和表示 15
2.3.2 单链表基本运算的实现 15
2.3.3 带表头结点的单链表 20
2.3.4 单循环链表 22
2.3.5 双向链表 22
2.4 顺序表与链表的比较 23
2.5 线性表的应用 24
2.6 本章小结 27
习题 27
第3章 堆栈和队列 29
3.1 堆栈 29
3.1.1 堆栈ADT 29
3.1.2 堆栈的顺序表示 29
3.1.3 堆栈的链接表示 31
3.2 队列 31
3.2.1 队列ADT 31
3.2.2 队列的顺序表示 32
3.2.3 队列的链接表示 35
3.3 表达式计算 35
3.3.1 中缀表达式 35
3.3.2 后缀表达式及其求值方法 35
3.3.3* 中缀表达式转换为后缀
表达式 40
3.4 递归 44
3.4.1 递归的概念 44
3.4.2 递归的实现 45
3.5 本章小结 46
习题 47
第4章 数组和字符串 48
4.1 数组 48
4.1.1 一维数组 48
4.1.2 二维数组 49
4.1.3 多维数组 50
4.2 数组的抽象数据类型 50
4.3 特殊矩阵 53
4.3.1 对称矩阵 53
4.3.2 三角矩阵 54
4.4 稀疏矩阵 55
4.4.1 稀疏矩阵的抽象数据类型 55
4.4.2 稀疏矩阵的转置算法 57
4.5 字符串 60
4.5.1 字符串的抽象数据类型 60
4.5.2 简单字符串匹配算法 61
4.5.3 改进的字符串匹配算法 64
4.6 本章小结 68
习题 68
第5章 树和二叉树 70
5.1 树 70
5.1.1 树的定义 70
5.1.2 基本术语 71
5.2 二叉树 72
5.2.1 二叉树的定义 72
5.2.2 二叉树的性质 73
5.2.3 二叉树ADT 74
5.2.4 二叉树的存储表示 75
5.2.5 二叉树的存储实现和基本运算 76
5.3 二叉树的遍历 78
5.3.1 二叉树遍历的递归算法 78
5.3.2 二叉树遍历的应用实例 81
5.3.3 二叉树遍历的非递归算法 83
5.3.4 线索二叉树的基本概念和构造 85
5.4 树和森林 86
5.4.1 森林与二叉树的转换 86
5.4.2 树和森林的存储表示 88
5.4.3 树和森林的遍历 91
5.5 堆和优先权队列 92
5.5.1 堆 92
5.5.2 优先权队列 95
5.6 哈夫曼树和哈夫曼编码 99
5.6.1 树的路径长度 100
5.6.2 哈夫曼树和哈夫曼算法 102
5.6.3 构造哈夫曼树 103
5.6.4 哈夫曼编码 104
5.7 本章小结 105
习题 105
第6章 集合和搜索 108
6.1 集合的表示 108
6.1.1 集合的基本概念 108
6.1.2 动态集ADT 109
6.1.3 集合的表示 109
6.2 顺序搜索 110
6.2.1 无序表的顺序搜索 110
6.2.2 有序表的顺序搜索 110
6.3 对半搜索 111
6.3.1 对半搜索方法 111
6.3.2 二叉判定树 114
6.4 本章小结 115
习题 115
第7章 搜索树 116
7.1 二叉搜索树 116
7.1.1 二叉搜索树的定义 116
7.1.2 二叉搜索树的搜索 117
7.1.3 二叉搜索树的插入 118
7.1.4 二叉搜索树的删除 119
7.1.5 二叉搜索树的高度 121
7.2* 二叉平衡树 122
7.2.1 二叉平衡树的定义 122
7.2.2 二叉平衡树的平衡调整
方法 122
7.2.3 二叉平衡树的插入 126
7.2.4 二叉平衡树的高度 127
7.3 m叉搜索树 128
7.3.1 m叉搜索树的定义 128
7.3.2 m叉搜索树的高度 129
7.4 B?树 130
7.4.1 B?树的定义 130
7.4.2 B?树的高度 131
7.4.3 B?树的搜索 131
7.4.4 B?树的插入 132
7.4.5 B?树的删除 133
7.5 本章小结 136
习题 136
第8章 散列表 138
8.1 散列技术简介 138
8.2 散列函数 139
8.3 散列冲突处理 141
8.3.1 拉链法 141
8.3.2 开地址法 142
8.3.3 性能分析 149
8.4 本章小结 149
习题 150
第9章 图 151
9.1 图的基本概念 151
9.1.1 图的定义 151
9.1.2 图的基本术语 152
9.1.3 图的类型定义 154
9.2 图的存储结构 154
9.2.1 邻接矩阵表示法 154
9.2.2 邻接矩阵的实现 155
9.2.3 邻接表表示法 158
9.2.4 邻接表的实现 158
9.3 图的遍历 161
9.3.1 深度优先遍历 162
9.3.2 宽度优先遍历 163
9.4 拓扑排序 165
9.4.1 AOV网 165
9.4.2 AOV网的拓扑排序 166
9.5 关键路径 167
9.5.1 AOE网 167
9.5.2 AOE网的关键路径 168
9.6 最小代价生成树 171
9.6.1 最小代价生成树的基本概念 171
9.6.2 普里姆算法 171
9.6.3 克鲁斯卡尔算法 173
9.7 单源最短路径 176
9.7.1 最短路径问题 176
9.7.2 单源最短路径问题 176
9.8 所有顶点之间的最短路径 179
9.9 本章小结 181
习题 182
第10章 排序 185
10.1 排序的基本概念 185
10.2 简单排序算法 186
10.2.1 简单选择排序 186
10.2.2 直接插入排序 189
10.2.3 冒泡排序 191
10.3 快速排序算法 194
10.4 两路合并排序算法 198
10.5 堆排序算法 201
10.6 外排序 204
10.6.1 预处理 204
10.6.2 多路合并 208
10.6.3 最佳合并树 211
10.6.4 完整的外排序过程 213
10.7 本章小结 213
习题 213
附录1 综合实验 215
附录2 配套慕课使用说明 220