第1章 绪论 1
1.1数据结构概述 1
1.1.1 基本概念 1
1.1.2数据结构 2
1.2算法 5
1.2.1算法的概念 5
1.2.2算法的描述 7
1.3 算法分析 11
1.3.1 时间复杂度 11
1.3.2空间复杂度 13
小结 13
知识巩固 13
实训演练 14
第2章线性表 16
2.1 线性表的定义及操作 16
2.1.1线性表的定义 16
2.1.2线性表的操作 17
2.2线性表运算 17
2.2.1顺序存储实现 18
2.2.2链式存储实现 21
2.2.3循环链表实现 24
2.2.4双向循环链表 25
2.2.5 顺序表与链表的比较 27
2.3经典应用实例 28
2.3.1 约瑟夫问题 28
2.3.2多项式求和 32
小结 37
知识巩固 38
实训演练 39
第3章 栈 41
3.1 栈的定义及基本运算 41
3.1.1 栈的定义 41
3.1.2栈的基本运算 42
3.2栈的顺序存储实现 42
3.2.1 栈的顺序存储 42
3.2.2栈的基本运算在顺序栈上的实现 43
3.2.3 栈的应用 44
3.3栈的链式存储实现 45
3.3.1栈的链式存储 45
3.3.2 栈的基本运算在链栈上的实现 45
3.4经典应用实例 46
3.4.1 数制转换 46
3.4.2表达式求值 48
小结 55
知识巩固 56
实训演练 57
第4章 队列 58
4.1 队列的定义及基本运算 58
4.1.1 队列的定义 58
4.1.2 队列的基本运算 59
4.2队列的顺序存储实现 59
4.2.1 队列的顺序存储 59
4.2.2 队列的基本运算在顺序存储上的实现 60
4.2.3循环队列 60
4.3 队列的链式存储实现 62
4.3.1 队列的链式存储 62
4.3.2 队列的基本运算在链式存储上的实现 63
4.4经典应用实例 64
4.4.1 迷宫问题 64
4.4.2模拟就诊过程 68
小结 72
知识巩固 72
实训演练 74
第5章 串 75
5.1 串的概念与操作 75
5.1.1 串的概念 75
5.1.2 串的操作 76
5.1.3 malloc（）和free（）函数 77
5.2 串的顺序存储结构与运算 78
5.2.1 串的顺序存储结构 78
5.2.2 串的基本运算及算法 78
5.2.3 常用的字符串处理函数 79
5.3 串的链式存储结构与运算 81
5.3.1 串的链式存储结构 81
5.3.2 串的基本运算 82
5.4经典应用实例 84
5.4.1 测试串的基本操作 84
5.4.2模式匹配 91
小结 94
知识巩固 94
实训演练 95
第6章 数组和广义表 97
6.1 数组 97
6.1.1 一维数组 97
6.1.2二维数组 98
6.1.3 多维数组 99
6.2矩阵的压缩存储 99
6.2.1 三角矩阵 99
6.2.2对称矩阵 101
6.2.3 稀疏矩阵 101
6.2.4带状矩阵 103
6.3 广义表 104
6.3.1 广义表的概念 104
6.3.2广义表的存储结构 104
6.3.3 广义表的运算 105
6.4经典应用实例 106
6.4.1 矩阵鞍点 106
6.4.2稀疏矩阵相加 108
小结 113
知识巩固 113
实训演练 114
第7章 树 115
7.1 树的定义及基本概念 115
7.1.1树的定义 115
7.1.2树的基本术语 116
7.1.3树的存储结构 117
7.2二叉树 118
7.2.1二叉树的定义 118
7.2.2二叉树的性质 118
7.2.3 二叉树的存储结构 120
7.3二叉树的遍历及算法 122
7.3.1 二叉树的遍历 122
7.3.2二叉树遍历算法 124
7.4树、森林与二叉树的转换 125
7.4.1树转换为二叉树 125
7.4.2森林转换为二叉树 126
7.4.3二叉树转换为树 128
7.4.4二叉树转换为森林 128
7.4.5树和森林的遍历 129
7.5 哈夫曼树 129
7.5.1 哈夫曼树及其构造 129
7.5.2哈夫曼树的应用 131
7.6经典应用实例 133
7.6.1二叉树的操作 133
7.6.2信息编码 136
小结 142
知识巩固 142
实训演练 143
第8章 图 145
8.1 基本概念 145
8.1.1 图的实际背景 145
8.1.2图的定义和术语 146
8.2图的存储结构 148
8.2.1 图的顺序存储——邻接矩阵 148
8.2.2图的链式存储——邻接表 150
8.3 图的遍历 151
8.3.1深度优先搜索遍历 151
8.3.2广度优先搜索遍历 152
8.4生成树 154
8.4.1最小生成树 154
8.4.2最小生成树算法 157
8.5 拓扑排序 159
8.5.1 拓扑排序的概念 159
8.5.2拓扑序列 160
8.5.3拓扑排序算法 160
8.6经典应用实例 161
8.6.1 最短路径 161
8.6.2教学计划编制 166
小结 169
知识巩固 169
实训演练 170
第9章 内部排序 172
9.1 基本概念 172
9.2插入排序 173
9.2.1直接插入排序 174
9.2.2折半插入排序 175
9.2.3希尔排序 176
9.3 交换排序 177
9.3.1 冒泡排序 177
9.3.2快速排序 179
9.4选择排序 180
9.4.1直接选择排序 181
9.4.2堆排序 182
9.5 归并排序 184
9.6基数排序 186
9.6.1多关键字排序 186
9.6.2链式基数排序 186
9.7经典应用实例 189
9.7.1考试成绩排序 189
9.7.2荷兰国旗问题 191
小结 193
知识巩固 194
实训演练 195
第10章 查找 197
10.1 基本概念 197
10.2线性表的查找 198
10.2.1 顺序查找 198
10.2.2二分查找 199
10.2.3分块查找 200
10.3树表的查找 201
10.3.1 二叉排序树查找 201
10.3.2平衡二叉树查找 203
10.4散列表查找 204
10.4.1散列表的概念 204
10.4.2散列函数的构造 205
10.4.3处理冲突的方法 206
10.4.4散列表的查找分析 207
10.5经典应用实例 207
10.5.1 模拟算法查询过程 208
10.5.2电话号码查询 211
小结 216
知识巩固 216
实训演练 218
参考文献 220