第1章 数据结构概述 1
本章学习目标 1
1.1 为什么要学习数据结构 1
1.2 数据结构的有关概念和术语 3
1.2.1 基本概念和术语 3
1.2.2 数据结构定义 4
1.3 算法和算法描述 5
1.3.1 算法与算法特性 5
1.3.2 算法描述 6
1.4 算法时空效率分析方法 7
习题 9
第2章 线性表 12
本章学习目标 12
2.1 线性表的逻辑结构 12
2.1.1 线性表的定义 12
2.1.2 线性表的基本操作 13
2.2 线性表的顺序存储结构及运算实现 13
2.2.1 顺序表 13
2.2.2 顺序表上基本运算的实现 14
2.3 线性表的链式存储和运算实现 18
2.3.1 单链表 18
2.3.2 单链表基本运算的实现 20
2.3.3 循环链表 24
2.3.4 双向链表 25
2.3.5 静态链表 28
2.3.6 顺序表和链表的比较 29
2.4 线性表的典型应用 29
习题 32
上机实习 33
第3章 栈和队列 39
3.1 栈 39
3.1.1 栈的定义及基本运算 39
3.1.2 栈的顺序存储结构及运算实现 40
3.1.3 栈的链式存储结构及运算实现 42
3.2 队列 43
3.2.1 队列的定义及基本运算 43
3.2.2 队列的顺序存储结构及运算实现 44
3.2.3 队列的链式存储结构及运算实现 46
3.3 栈和队列的典型应用 48
习题 56
上机实习 57
第4章 数组、特殊矩阵和广义表 64
本章学习目标 64
4.1 数组 64
4.1.1 数组的基本概念 64
4.1.2 数组的存储结构 65
4.2 特殊矩阵的压缩存储 66
4.2.1 对称矩阵 66
4.2.2 三角矩阵 67
4.2.3 对角矩阵 68
4.2.4 稀疏矩阵 69
4.3 广义表 75
4.3.1 广义表的定义和性质 75
4.3.2 广义表的基本运算 76
习题 76
上机实习 77
5.1.2 串的基本运算 80
5.1.1 串的基本概念 80
5.1 串的定义及其基本运算 80
第5章 串 80
本章学习目标 80
5.2 串的存储结构 81
5.2.1 串的顺序存储 81
5.2.2 串的链式存储 82
5.3 串运算的应用 83
习题 85
上机实习 86
6.1 树的概念与表示 89
6.1.1 树的定义 89
本章学习目标 89
第6章 树 89
6.1.2 树的相关术语 90
6.1.3 树的表示 91
6.2 二叉树的概念与性质 91
6.2.1 二叉树的基本概念 91
6.2.2 二叉树的重要性质 92
6.3 二叉树的存储结构 93
6.3.1 顺序存储结构 93
6.3.2 链式存储结构 94
6.3.3 建立二叉树的二叉链表 95
6.4 二叉树的遍历 96
6.5 线索二叉树 100
6.5.1 线索二叉树的定义及结构 100
6.5.2 中序线索二叉树操作 102
6.6 树的存储结构 104
6.7 树、森林与二叉树的转换 105
6.7.1 树和森林转换为二叉树 105
6.8 哈夫曼树及其应用 107
6.7.2 二叉树还原为树和森林 107
习题 113
上机实习 114
第7章 图 118
本章学习目标 118
7.1 图的基本概念 118
7.2 图的存储表示 120
7.2.1 邻接矩阵 120
7.2.2 邻接表 121
7.3.1 深度优先遍历（DFS） 123
7.3 图的遍历 123
7.3.2 广度优先遍历（BFS） 124
7.4 图的生成树 125
7.4.1 生成树 125
7.4.2 最小生成树的基本概念 126
7.4.3 构造最小生成树的Prim算法 126
7.4.4 构造最小生成树的Kruskal算法 128
7.5 最短路径 128
7.6.2 AOV网与拓扑排序 131
7.6.1 有向无环图的概念 131
7.6 拓扑排序 131
7.7 关键路径 134
7.7.1 AOE网 134
7.7.2 关键路径 135
7.7.3 关键路径的确定 135
7.8 工程应用实例 136
习题 138
上机实习 140
8.2.1 静态查找表结构 145
8.2 静态查找表 145
本章学习目标 145
8.1 基本概念与术语 145
第8章 查找 145
8.2.2 顺序查找 146
8.2.3 二分查找 147
8.2.4 分块查找 149
8.3 动态查找表 150
8.3.1 二叉排序树 150
8.3.2 二叉排序树的建立 150
8.3.3 平衡二叉树 154
8.3.4 B树 156
8.4 哈希表查找 157
8.4.1 哈希表与哈希方法 157
8.4.2 常用的哈希函数 158
8.4.3 处理冲突的方法 160
8.4.4 哈希表的查找分析 161
习题 161
上机实习 162
9.1 基本概念 166
本章学习目标 166
第9章 排序 166
9.2 插入排序 167
9.2.1 直接插入排序 167
9.2.2 希尔排序 168
9.3 交换排序 169
9.3.1 冒泡排序 169
9.3.2 快速排序 170
9.4 选择排序 172
9.4.1 直接选择排序 172
9.4.2 堆排序（Heap Sort） 174
9.5 归并排序 176
9.6 基数排序 178
9.7 内部排序的比较 180
9.8 外部排序 180
9.8.1 外部排序 180
9.8.2 多路平衡归并的实现 182
习题 182
上机实习 183
参考文献 187