第1章 数据结构与算法概述 1
1.1数据和数据类型 1
1.1.1数据和数据元素 1
1.1.2数据类型 2
1.1.3抽象数据类型 4
1.1.4抽象数据类型程序应用实例 5
1.1.5数据对象 6
1.2数据结构 6
1.2.1数据的逻辑结构 6
1.2.2数据元素的存储结构 8
1.2.3常用的数据运算 10
1.3算法和算法评价 11
1.3.1算法的概念 11
1.3.2算法描述工具 12
1.3.3算法的性质 13
1.3.4算法的评价标准 14
1.4算法性能分析 15
1.4.1算法的时间性能分析 15
1.4.2算法的空间性能分析 18
本章小结 19
本章习题 19
第2章 顺序表及其应用 22
2.1顺序表的基本概念 22
2.1.1顺序表的定义 22
2.1.2顺序表的数据结构分析 22
2.1.3顺序表的数据类型描述 23
2.2顺序表基本算法 24
2.3顺序表基本算法性能分析 27
2.3.1时间性能分析 27
2.3.2空间性能分析 28
2.4顺序表的应用1——查找问题 28
2.4.1查找的概念 28
2.4.2简单顺序查找算法 29
2.4.3有序表的二分查找算法 31
2.4.4分块查找算法 33
2.4.5 3种查找算法的性能比较 34
2.5顺序表的应用2——排序问题 35
2.5.1排序的概念 35
2.5.2顺序表的数据类型 36
2.5.3插入排序——直接插入排序算法 37
2.5.4插入排序——希尔排序算法 39
2.5.5交换排序——冒泡排序算法 41
2.5.6交换排序——快速排序算法 43
2.5.7选择排序——直接选择排序算法 46
2.5.8归并排序算法 47
2.5.9排序算法的性能分析与比较 51
2.6顺序表的应用3——字符处理问题 51
2.6.1串和顺序串的定义及相关概念 51
2.6.2顺序串的数据结构分析 52
2.6.3顺序串的基本运算 52
2.6.4顺序串的数据类型定义 54
2.6.5顺序串的基本运算算法 54
2.6.6串的模式匹配算法 56
本章小结 57
本章习题 58
第3章 链表及其应用 63
3.1链表的基本概念 63
3.1.1链表的定义 63
3.1.2链表的逻辑结构 63
3.1.3链表的存储结构 64
3.1.4静态链表和动态链表 64
3.1.5链表基本运算 65
3.2单链表的数据结构 66
3.2.1单链表的逻辑结构 66
3.2.2单链表的存储结构 66
3.3单链表基本算法及性能分析 67
3.3.1单链表的基本算法 67
3.3.2单链表基本算法性能分析 71
3.4单链表基本运算应用实例 71
3.5循环链表 73
3.5.1单向循环链表 74
3.5.2.双向循环链表 75
3.5.3双向循环链表的结点插入算法 76
3.5.4双向循环链表的结点删除算法 77
3.6链表的应用 78
3.6.1多项式相加问题 78
3.6.2两个链表的归并问题 81
3.6.3箱子排序问题 83
3.6.4链表在字符处理方面的应用——链串 85
本章小结 86
本章习题 86
第4章 堆栈及其应用 91
4.1堆栈的基本概念 91
4.1.1堆栈的定义 91
4.1.2堆栈的逻辑结构 91
4.1.3堆栈的基本算法 92
4.2顺序栈及其基本算法 92
4.2.1顺序栈的概念及其数据类型 92
4.2.2顺序栈的基本算法 93
4.2.3顺序栈基本算法性能分析 94
4.3链栈及其基本算法 94
4.3.1链栈的概念及数据类型 94
4.3.2链栈的基本算法 95
4.3.3链栈基本算法性能分析 96
4.4堆栈的应用 97
4.4.1数制转换问题 97
4.4.2简单的文字编辑器问题 98
4.4.3表达式计算问题 99
4.4.4括号匹配问题 104
4.4.5汉诺塔问题 105
4.4.6火车车厢重排问题 109
4.4.7开关盒布线问题 113
4.4.8离线等价类问题 116
4.4.9迷宫老鼠问题 119
本章小结 122
本章习题 122
第5章 队列及其应用 125
5.1队列的基本概念 125
5.1.1队列的定义 125
5.1.2队列的逻辑结构 126
5.1.3队列的基本运算 126
5.2顺序队列及其基本运算 126
5.2.1顺序队列的概念及数据类型 126
5.2.2循环队列 127
5.2.3循环队列的基本运算实现 129
5.2.4循环队列基本算法性能分析 130
5.3链队列及其基本算法 130
5.3.1链队列的概念及数据类型 130
5.3.2链队列的基本运算实现 131
5.3.3链队列基本算法性能分析 133
5.4基数排序问题 133
5.4.1多关键字排序问题 133
5.4.2链式基数排序算法思想 134
5.4.3链式基数排序算法实现的技术要点 135
5.4.4链表基数排序算法及其性能分析 136
5.5火车车厢重排问题 137
5.5.1问题分析及算法思想 137
5.5.2火车车厢重排算法设计 138
5.5.3火车车厢重排算法及其性能分析 139
5.6电路布线问题 140
5.6.1电路布线问题分析 140
5.6.2电路布线问题算法思想 140
5.6.3电路布线问题算法设计 141
5.6.4电路布线问题算法及其性能分析 141
5.7识别图元问题 143
5.7.1识别图元问题分析 143
5.7.2识别图元算法设计 143
5.7.3识别图元算法及其性能分析 144
5.8工厂仿真问题 145
5.8.1工厂仿真问题分析 145
5.8.2工厂仿真问题算法设计 146
5.8.3工厂仿真问题算法及其性能分析 147
本章小结 149
本章习题 149
第6章 特殊矩阵、广义表及其应用 152
6.1数组与矩阵 152
6.1.1数组与矩阵的概念及其相互关系 152
6.1.2数组的存储结构 153
6.2特殊矩阵的压缩存储 154
6.2.1对称矩阵及其存储结构 155
6.2.2三角矩阵及其存储结构 155
6.2.3对角矩阵及其存储结构 156
6.2.4稀疏矩阵及其存储结构 157
6.3矩阵的应用实例 161
6.3.1稀疏矩阵的转置问题 161
6.3.2稀疏矩阵的加法运算 163
6.4广义表 167
6.4.1广义表的概念 167
6.4.2广义表的存储结构 168
6.4.3广义表的应用——m元多项式的表示 170
本章小结 172
本章习题 172
第7章 二叉树及其应用 176
7.1二叉树的基本概念 176
7.1.1二叉树的定义 176
7.1.2二叉树的基本术语 177
7.1.3两种特殊的二叉树 177
7.1.4二叉树的性质 178
7.2二叉树的存储结构 179
7.2.1二叉树的顺序存储结构 179
7.2.2二叉树的链接存储结构 180
7.2.3建立二叉树的算法 181
7.3二叉树的遍历算法 182
7.3.1二叉树遍历的概念 182
7.3.2二叉树遍历递归算法 184
7.3.3二叉树先序遍历非递归算法 185
7.3.4二叉树中序遍历非递归算法 187
7.3.5二叉树后序遍历非递归算法 187
7.4线索二叉树 188
7.4.1线索二叉树的概念 188
7.4.2二叉树的线索化 189
7.4.3线索二叉树的查找算法 190
7.5二叉树的应用1——二叉树遍历的应用实例 191
7.6二叉树的应用2——哈夫曼树 193
7.6.1基本概念 193
7.6.2哈夫曼树定义 194
7.6.3哈夫曼树的构造过程 195
7.6.4哈夫曼树的存储结构及哈夫曼算法思想 195
7.6.5哈夫曼算法 196
7.6.6哈夫曼树的应用——哈夫曼编码 197
7.7二叉树的应用3——二叉排序树 198
7.7.1二叉排序树定义 198
7.7.2二叉排序树的存储结构 199
7.7.3二叉排序树的结点查找算法 199
7.7.4二叉排序树的结点插入算法 200
7.7.5二叉排序树的生成算法 201
7.7.6二叉排序树的结点删除算法 202
7.7.7二叉排序树的结点查找算法性能分析 204
7.7.8平衡二叉排序树 205
7.8二叉树的应用4——堆和堆排序 212
7.8.1堆和堆排序的概念 212
7.8.2堆的调整算法 213
7.8.3建堆 214
7.8.4堆排序算法及性能分析 214
本章小结 216
本章习题 216
第8章 树和森林及其应用 224
8.1树和森林的基本概念 224
8.1.1树和森林的定义 224
8.1.2树的性质 225
8.1.3树和森林的遍历 226
8.1.4树、森林与二叉树的关系 227
8.2树的存储结构 228
8.2.1树的顺序存储结构和建树算法 228
8.2.2树的链接存储结构和建树算法 229
8.3树的基本算法及性能分析 231
8.3.1树转换为二叉树算法及性能分析 231
8.3.2森林转换为二叉树算法及性能分析 232
8.3.3二叉树转换为树算法及性能分析 233
8.3.4二叉树转换为森林算法及性能分析 234
8.3.5树的遍历算法 235
8.3.6森林的遍历算法 235
8.4树的应用——B-树 236
8.4.1 B-树的概念 236
8.4.2 B-树的数据存储类型 237
8.4.3 B-树的查找算法 237
8.4.4 B-树的插入算法 239
8.4.5 B-树的删除算法及实例 243
本章小结 244
本章习题 245
第9章 散列结构及其应用 248
9.1散列结构的基本概念 248
9.1.1散列结构的概念 248
9.1.2散列存储结构——散列表 249
9.1.3散列函数 250
9.1.4冲突处理方法——开放定址法 253
9.1.5冲突处理方法——链地址法 254
9.2线性探测散列算法 255
9.2.1线性探测散列算法的数据类型 255
9.2.2线性探测散列基本算法 255
9.3链地址法散列算法 257
9.3.1链地址散列算法的数据类型 257
9.3.2链地址散列基本算法 258
9.4散列结构的查找性能分析 260
9.5散列结构应用——LZW压缩问题 261
9.5.1 LZW压缩问题 261
9.5.2 LZW压缩算法及其算法性能分析 262
9.5.3 LZW解压缩问题 262
9.5.4 LZW解压缩算法及其算法性能分析 263
本章小结 264
本章习题 264
第10章 图及其应用 267
10.1图的概念 267
10.1.1图的定义 267
10.1.2图的基础知识 268
10.1.3图的基本运算 271
10.2图的存储结构及其基本算法 271
10.2.1邻接矩阵及其数据类型 272
10.2.2基于邻接矩阵的基本算法 273
10.2.3邻接表及其数据类型 274
10.2.4基于邻接表的基本算法 276
10.2.5逆邻接表 277
10.2.6十字链表及其数据类型 277
10.2.7基于十字链表的基本算法 279
10.2.8邻接多重表及其数据类型 280
10.2.9基于邻接多重表的基本算法 281
10.3图的遍历及算法 283
10.3.1深度优先搜索遍历 283
10.3.2深度优先搜索遍历算法 284
10.3.3广度优先搜索遍历 284
10.3.4广度优先搜索遍历算法 285
10.4有向图的连通性和最小生成树 286
10.4.1有向图的连通性分析 286
10.4.2连通网的最小生成树问题——通信网络问题 286
10.5图的（最小）生成树问题 287
10.5.1图的生成树 287
10.5.2最小生成树算法——普利姆算法 288
10.5.3最小生成树算法——克鲁斯卡尔算法 290
10.6非连通图的生成森林算法 291
10.7最短路径 293
10.7.1最短路径问题 293
10.7.2从某源点到其余各顶点之间的最短路径问题——迪杰斯特拉算法 294
10.7.3每一对顶点之间的最短路径问题——弗洛伊德算法 296
10.8有向无环图及其应用 298
10.8.1有向无环图及其应用问题实例 298
10.8.2 AOV网及其特性 300
10.8.3拓扑排序及其算法 300
10.8.4 AOE网 302
10.8.5关键路径及有关概念 303
10.8.6求解关键路径算法思想 303
10.8.7 AOE网关键路径求解算法的数据类型 304
10.8.8 AOE网中求解关键路径的算法 305
10.8.9关键路径求解算法分析 306
本章小结 307
本章习题 308
第11章 算法性能分析和算法设计方法 312
11.1算法和程序 312
11.1.1算法与程序分析 312
11.1.2空间复杂性分析 313
11.1.3时间复杂度分析 314
11.2再谈算法性能问题 315
11.2.1时间复杂度的上限值 315
11.2.2时间复杂度的下限值 316
11.2.3有关渐进符号的计算 317
11.3算法性能测量问题 318
11.3.1算法性能测量问题分析 318
11.3.2算法性能测量实例 318
11.4算法设计方法简介 319
11.4.1分而治之算法设计方法 319
11.4.2最优化问题简介 320
11.4.3贪婪算法设计方法 321
11.4.4回溯算法设计方法 322
11.5 NP问题简介 323
11.6散列表查找性能 324
11.7讨论题 326