第1章 绪论 1
1.1 为什么要学习数据结构 1
1.2 如何学好数据结构 2
1.3 基本概念和术语 2
1.4 算法 3
1.4.1 算法的特性与设计要求 3
1.4.2 算法性能分析与度量 4
1.5 对数据结构和算法的描述语言的说明 6
1.6 习题 7
第2章 C语言复习与进阶 9
2.1 指针 9
2.1.1 指向基本数据类型的变量的指针 10
2.1.2 指向数组的指针 12
2.1.3 指向指针变量的指针 18
2.2 函数 20
2.2.1 函数的定义与声明 20
2.2.2 函数的调用 21
2.2.3 函数的参数传递 22
2.2.4 递归算法设计 25
2.2.5 函数的指针 29
2.3 堆内存空间的使用 33
2.3.1 堆内存空间的申请与释放 34
2.3.2 动态数组的使用 37
2.4 其他数据类型及链表 39
2.4.1 结构体与共用体 39
2.4.2 结构体与共用体的比较 44
2.4.3 位段的定义与引用 45
2.4.4 链表概述 45
2.5 预处理命令 49
2.5.1 宏定义 49
2.5.2 文件包含 52
2.5.3 条件编译 53
2.6 习题 54
第3章 线性表 60
3.1 线性表的逻辑结构 60
3.1.1 线性表的定义 60
3.1.2 线性表的基本操作 60
3.2 线性表的物理结构 61
3.2.1 顺序存储结构 61
3.2.2 链式存储结构 68
3.2.3 顺序表和链表的比较 79
3.3 线性表的应用实例 80
3.4 习题 83
第4章 栈 86
4.1 栈的逻辑结构 86
4.1.1 栈的定义 86
4.1.2 栈的常见基本操作 87
4.2 栈的物理结构 87
4.2.1 顺序存储结构 87
4.2.2 链式存储结构 91
4.3 栈的应用实例 94
4.4 习题 96
第5章 队列 98
5.1 队列的逻辑结构 98
5.1.1 队列的定义 98
5.1.2 队列的常见基本操作 98
5.2 队列的物理结构 99
5.2.1 顺序存储结构 99
5.2.2 链式存储结构 103
5.3 队列的应用实例 106
5.4 习题 109
第6章 串 110
6.1 串的定义及其基本操作 110
6.1.1 串的基本概念 110
6.1.2 串的常见基本操作 110
6.2 串的表示与实现 111
6.2.1 串的定长顺序存储 111
6.2.2 串的堆存储结构 115
6.2.3 串的链式存储结构 118
6.3 串的模式匹配算法 120
6.4 习题 121
第7章 数组与广义表 123
7.1 数组 123
7.1.1 数组的定义 123
7.1.2 数组的顺序表示和实现 124
7.2 矩阵的压缩存储 126
7.2.1 特殊矩阵的压缩存储 126
7.2.2 稀疏矩阵的压缩存储 127
7.3 广义表 136
7.3.1 广义表的定义 136
7.3.2 广义表的存储结构 137
7.4 习题 137
第8章 树和二叉树 140
8.1 树的定义及相关术语 140
8.2 二叉树的定义及性质 142
8.2.1 二叉树的定义 142
8.2.2 二叉树的基本操作 143
8.2.3 二叉树的主要性质 145
8.3 二叉树的存储结构 146
8.3.1 顺序存储结构 146
8.3.2 链式存储结构 147
8.4 二叉树常见操作的实现 149
8.4.1 二叉树常见的四种遍历方法 149
8.4.2 二叉树的创建算法 157
8.4.3 二叉树其他常见操作的相关算法 162
8.5 线索二叉树 167
8.6 树和森林 171
8.6.1 树的存储 171
8.6.2 树、森林与二叉树的转换 174
8.7 二叉表示树 175
8.8 哈夫曼树 176
8.8.1 哈夫曼树的概念 176
8.8.2 哈夫曼树的具体构造方法 177
8.8.3 哈夫曼树的应用 177
8.9 回溯法 182
8.10 习题 185
第9章 图 189
9.1 图的逻辑结构 189
9.1.1 图的定义及相关术语 189
9.1.2 图的常见操作 191
9.2 图的存储结构 192
9.2.1 数组表示法 192
9.2.2 邻接表 200
9.3 图的遍历 208
9.3.1 深度优先搜索 208
9.3.2 广度优先搜索 210
9.4 最小生成树 213
9.5 有向无环图的应用 217
9.5.1 拓扑排序 217
9.5.2 关键路径 219
9.6 最短路径 223
9.7 迷宫路径求解 226
9.8 习题 232
第10章 查找 237
10.1 静态查找表 237
10.1.1 无序表的查找 238
10.1.2 有序表的查找 239
10.2 动态查找表 244
10.2.1 二叉查找树和平衡二叉树 245
10.2.2 B树 254
10.3 哈希表 255
10.3.1 哈希表概念 255
10.3.2 构造哈希表 256
10.3.3 哈希表的查找及分析 259
10.4 习题 260
第11章 内部排序 262
11.1 概述 262
11.2 插入排序 263
11.2.1 直接插入排序 263
11.2.2 折半插入排序 265
11.2.3 希尔排序 265
11.3 交换排序 267
11.3.1 冒泡排序 267
11.3.2 快速排序 268
11.4 选择排序 271
11.4.1 简单选择排序 271
11.4.2 堆排序 272
11.5 归并排序 277
11.6 基数排序 279
11.7 各种内部排序方法的比较 283
11.8 习题 284
第12章 文件 286
12.1 概述 286
12.2 顺序文件 287
12.3 索引文件 288
12.4 哈希文件 289
12.5 多关键字文件 289
12.6 习题 290