第1章 概论 1
1.1引言 1
1.1.1什么是数据结构 1
1.1.2数据结构研究什么 1
1.2数据结构的基本概念 3
1.3算法和算法的分析 4
1.3.1算法及算法的描述 4
1.3.2算法设计的要求 4
1.3.3算法的分析 5
习题 8
第2章 线性表 10
2.1线性表的定义及运算 10
2.1.1线性表的定义 10
2.1.2线性表的基本运算 10
2.2线性表的顺序存储结构 11
2.2.1顺序表 11
2.2.2顺序表上基本运算的实现 12
2.3线性表的链式存储结构 15
2.3.1单链表及其基本运算 15
2.3.2循环链表 19
2.3.3双向链表 20
2.4顺序表与链表的比较 22
2.5典型题例 23
2.6实训例题 25
2.6.1实训例题1有序顺序表的建立及查找 25
2.6.2实训例题2航班订票系统 29
习题 34
实训习题 36
第3章 堆栈和队列 37
3.1堆栈 37
3.1.1堆栈的定义及基本运算 37
3.1.2堆栈的顺序存储结构 37
3.1.3栈的链式存储结构 40
3.2栈应用典型题例 43
3.2.1子程序的调用和返回 43
3.2.2数制转换 44
3.2.3行编辑程序 45
3.2.4算术表达式求值 46
3.3栈与递归的实现 49
3.3.1递归算法 49
3.3.2递归算法的执行过程 49
3.3.3递归算法的设计 50
3.4队列 52
3.4.1队列的定义及运算 52
3.4.2队列的顺序存储结构 53
3.4.3队列的链式存储结构 56
3.5队列应用典型题例 58
3.5.1求解报数问题 58
3.5.2购买彩票问题 58
3.6实训例题 60
3.6.1实训例题1链队列与链栈的操作 60
3.6.2实训例题2回文判断 64
习题 68
实训习题 70
第4章 串与数组 72
4.1串及其基本运算 72
4.1.1串的基本概念 72
4.1.2串的基本运算 73
4.2串的存储结构 74
4.2.1串的顺序存储 74
4.2.2串的堆存储结构 76
4.2.3串的链式存储 77
4.3串的模式匹配算法及子串替换算法 78
4.3.1模式匹配的Brute-Force算法 78
4.3.2子串替换算法 79
4.4数组 80
4.4.1数组的定义 80
4.4.2一维数组、二维数组和多维数组 81
4.5典型题例 82
4.5.1对称矩阵与对角矩阵的压缩存储 82
4.5.2稀疏矩阵的压缩存储 83
4.6实训例题 86
4.6.1实训例题1行编辑程序 86
4.6.2实训例题2稀疏矩阵相加 91
习题 95
实训习题 97
第5章 树和二叉树 98
5.1树 98
5.1.1树的基本概念 98
5.1.2树的基本操作 100
5.1.3树的存储结构 101
5.2二叉树 104
5.2.1二叉树的定义及基本操作 104
5.2.2二叉树的性质 105
5.2.3二叉树的存储结构 107
5.3遍历二叉树 109
5.3.1二叉树的遍历方法 110
5.3.2典型例题 118
5.4线索二叉树 121
5.5树、森林和二叉树的关系 126
5.5.1树、森林转换为二叉树 126
5.5.2树、森林的遍历 127
5.6哈夫曼树及其应用 128
5.6.1哈夫曼树的定义及构造 129
5.6.2哈夫曼树的应用 132
5.7实训例题 134
5.7.1实训例题1设计哈夫曼编码 134
5.7.2实训例题2前缀算术表达式转换 138
习题 142
实训习题 145
第6章图 146
6.1图的定义和术语 146
6.1.1图的定义 146
6.1.2图的基本术语 146
6.2图的存储结构 148
6.2.1邻接矩阵 148
6.2.2邻接表 151
6.2.3邻接矩阵和邻接表的比较 153
6.3图的遍历 154
6.3.1连通图的深度优先搜索 154
6.3.2连通图的广度优先搜索 156
6.3.3.非连通图的遍历 157
6.4最小生成树 158
6.4.1生成树及最小生成树 158
6.4.2普里姆算法 159
6.4.3克鲁斯卡尔算法 162
6.5最短路径 163
6.6拓扑排序 166
6.7典型题例 170
6.8实训例题 172
6.8.1实训例题1设计学习计划 172
6.8.2实训例题2渡河问题 175
习题 180
实训习题 182
第7章 查找 184
7.1基本概念 184
7.2线性表的查找 184
7.2.1顺序查找 185
7.2.2折半查找 186
7.2.3分块查找 188
7.3二叉排序树的查找 189
7.3.1二叉排序树（Binary Sort Tree）的定义 189
7.3.2二叉排序树的查找算法 190
7.3.3二叉排序树的建立与插入 191
7.3.4二叉排序树的删除 193
7.3.5二叉排序树的查找算法分析 197
7.4哈希表的查找 197
7.4.1哈希表的概念 197
7.4.2哈希函数的构造方法 198
7.4.3处理冲突的方法 200
7.4.4哈希表上的运算 204
7.5 典型题例 206
7.6实训例题 209
7.6.1实训例题1构造二叉排序树 209
7.6.2实训例题2设计哈希表 212
习题 215
实训习题 216
第8章排序 217
8.1排序的基本概念 217
8.2插入排序 218
8.2.1直接插入排序 218
8.2.2希尔排序 220
8.3交换排序 221
8.3.1冒泡排序 221
8.3.2快速排序 222
8.4选择排序 224
8.4.1直接选择排序 225
8.4.2堆排序 226
8.5归并排序 230
8.6基数排序 232
8.6.1多关键字排序 232
8.6.2基数排序方法 233
8.7各种内部排序方法的比较 234
8.8典型题例 235
8.9实训例题 239
8.9.1实训例题1不同排序算法的比较 239
8.9.2实训例题2学生成绩名次表 246
习题 253
实训习题 256
附录A数据结构实训指南 257
A.1综述 257
A.2实训步骤 257
A.3实训报告规范 259
A.4数据结构实训所使用的上机环境 260
A.5 Trubo C 2.0编译、连接时的错误和警告信息 272
参考文献 277