数据结构(C语言,慕课版)

第1章 绪论 1
1.1 数据结构的发展 1
1.2 数据结构的概念 2
1.2.1 数据结构研究的领域 3
1.2.2 数据结构研究的内容 5
1.2.3 数据 5
1.2.4 数据结构 6
1.2.5 数据类型 8
1.3 算法和算法分析 9
1.3.1 算法的概念 10
1.3.2 算法的复杂性分析 10
1.4 习题 13
第2章 线性表 16
2.1 线性表的类型定义 16
2.2 线性表的顺序映像 19
2.2.1 线性表的顺序存储结构 20
2.2.2 顺序存储结构的特点 20
2.2.3 典型操作的算法实现 21
2.2.4 主要操作的算法分析 24
2.3 线性表的链式映像 25
2.3.1 线性链表的定义 25
2.3.2 线性链表的类型定义及典型操作 26
2.3.3 其他形式的链表 30
2.4 线性表实现方法的比较 37
2.4.1 顺序表和链表的比较 37
2.4.2 线性链表定义的改进 38
2.5 一元多项式的表示及相加 40
2.6 习题 44
第3章 栈 49
3.1 栈的定义 49
3.1.1 栈的特点及定义 49
3.1.2 栈的抽象数据类型定义 50
3.2 栈的存储表示及实现 51
3.2.1 栈的顺序存储表示 51
3.2.2 栈的链式存储表示 52
3.3 栈的应用 53
3.3.1 数制转换 53
3.3.2 括号匹配的检验 54
3.3.3 行编辑程序问题 55
3.3.4 迷宫求解问题 56
3.3.5 表达式求值 57
3.3.6 递归的实现 60
3.4 习题 63
第4章 队列 65
4.1 队列的定义 65
4.2 队列类型的实现 66
4.2.1 队列的顺序存储——循环队列 67
4.2.2 队列的链式存储——链队列 69
4.3 队列的应用——离散事件模拟 70
4.4 习题 74
第5章 串 76
5.1 串类型的定义 76
5.1.1 串的基本概念 76
5.1.2 串的抽象数据类型定义 77
5.1.3 串与线性表的区别 79
5.2 串的表示和实现 80
5.2.1 串的定长顺序存储表示 80
5.2.2 串的堆分配存储表示 81
5.2.3 串的块链存储表示 82
5.3 串的模式匹配算法 83
5.3.1 简单匹配算法 83
5.3.2 KMP算法 86
5.4 串应用举例 ——文本编辑 92
5.4.1 文本编辑概述 93
5.4.2 文本编辑程序 94
5.5 习题 94
第6章 数组 95
6.1 数组的基本概念 95
6.2 数组的顺序存储及实现 97
6.2.1 数组的存储方式 97
6.2.2 数组的顺序存储表示和实现 98
6.3 矩阵的压缩存储 100
6.3.1 对称矩阵的压缩存储 100
6.3.2 三角矩阵的压缩存储 101
6.3.3 对角矩阵的压缩存储 102
6.4 稀疏矩阵 103
6.4.1 稀疏矩阵的定义 103
6.4.2 稀疏矩阵的抽象数据类型定义 103
6.4.3 稀疏矩阵的压缩存储 104
6.5 习题 113
第7章 广义表 115
7.1 广义表的定义 115
7.2 广义表的存储结构 117
7.2.1 广义表的头尾链表存储表示 117
7.2.2 广义表的元素存储表示 118
7.3 广义表操作的实现 118
7.3.1 创建广义表 118
7.3.2 求表的深度 120
7.3.3 广义表的结点操作 121
7.3.4 删除广义表 122
7.3.5 求广义表的长度 123
7.3.6 广义表的复制 123
7.4 习题 125
第8章 树 127
8.1 树的类型定义和基本术语 127
8.1.1 树的定义 127
8.1.2 树的常用术语 130
8.1.3 线性结构与树形结构的比较 131
8.2 树和森林的存储结构 131
8.2.1 树的存储结构 131
8.2.2 树和森林的遍历 134
8.3 习题 138
第9章 二叉树 140
9.1 二叉树的定义和性质 140
9.1.1 二叉树的定义 140
9.1.2 两类特殊的二叉树 143
9.1.3 二叉树的重要特性 143
9.2 二叉树的存储结构 144
9.2.1 二叉树的顺序存储表示 144
9.2.2 二叉树的链式存储表示 145
9.3 二叉树的遍历与应用 146
9.3.1 二叉树的三种遍历算法 147
9.3.2 二叉树遍历算法的非递归描述 150
9.3.3 二叉树遍历算法的应用 153
9.4 线索二叉树 158
9.4.1 线索二叉树的定义 158
9.4.2 线索链表的遍历 159
9.4.3 线索链表的建立 161
9.4.4 中序线索二叉树中插入结点 162
9.4.5 线索二叉树的优缺点 163
9.5 树、森林和二叉树 163
9.5.1 森林与二叉树之间的转换 163
9.5.2 森林与二叉树转换的操作 164
9.5.3 树、森林的遍历和二叉树遍历的对应关系 165
9.6 哈夫曼树及其应用 166
9.6.1 哈夫曼树 166
9.6.2 哈夫曼编码 168
9.7 习题 172
第10章 图 176
10.1 图的基本概念 176
10.1.1 图的定义和术语 176
10.1.2 图的抽象数据类型定义 178
10.2 图的存储结构 180
10.2.1 邻接矩阵(数组)表示法 180
10.2.2 邻接表表示法 183
10.2.3 十字链表表示法 186
10.2.4 邻接多重表表示法 187
10.3 图的遍历 189
10.3.1 深度优先搜索遍历 189
10.3.2 广度优先搜索遍历 190
10.4 图的连通性问题 192
10.4.1 无向图的连通分量和生成树 192
10.4.2 有向图的强连通分量 194
10.4.3 *小生成树 195
10.5 有向无环图及其应用 200
10.5.1 拓扑排序 200
10.5.2 关键路径 203
10.6 *短路径 207
10.6.1 单源*短路径 208
10.6.2 每一对顶点间的*短路径 211
10.7 习题 213
第11章 查找 216
11.1 查找表 216
11.2 静态查找表 218
11.2.1 顺序表的查找 218
11.2.2 有序表的查找 220
11.2.3 索引顺序表的查找 222
11.3 动态查找表 224
11.3.1 二叉排序树 224
11.3.2 平衡二叉树 229
11.3.3 B-树 235
11.3.4 B 树 243
11.4 哈希表 244
11.4.1 什么是哈希表 244
11.4.2 哈希函数的构造方法 246
11.4.3 哈希表处理冲突的方法 248
11.4.4 哈希表的查找及分析 251
11.5 习题 255
第12章 内部排序 258
12.1 排序概述 258
12.1.1 排序的概念 258
12.1.2 排序方法的稳定性 259
12.1.3 内部排序和外部排序 259
12.1.4 内部排序的分类 259
12.2 插入排序 260
12.2.1 直接插入排序 260
12.2.2 折半插入排序 262
12.2.3 2-路插入排序 263
12.2.4 表插入排序 265
12.2.5 希尔排序 268
12.3 交换排序 269
12.3.1 起泡排序 270
12.3.2 快速排序 271
12.4 选择排序 273
12.4.1 简单选择排序 273
12.4.2 堆排序 274
12.5 归并排序 277
12.6 基数排序 279
12.6.1 多关键字排序 279
12.6.2 链式基数排序 281
12.7 各种内部排序方法的比较讨论 283
12.8 习题 284
第13章 外部排序 286
13.1 外部排序的方法 286
13.2 归并排序 287
13.2.1 2-路平衡归并排序 287
13.2.2 多段2-路归并排序 288
13.2.3 多路平衡归并排序 288
13.3 置换选择排序 290
13.3.1 置换选择排序的处理过程 291
13.3.2 置换选择排序算法 291
13.4 习题 294
参考文献 295