第1章 绪论 1
1.1 数据结构 1
1.1.1 学习数据结构的重要性 1
1.1.2 什么是数据结构 3
1.1.3 数据的逻辑结构 5
1.1.4 数据的存储结构 9
1.1.5 数据的运算 11
1.2 算法 12
1.2.1 什么是算法 12
1.2.2 算法的描述 13
1.2.3 算法设计 15
1.2.4 算法设计要求 17
1.2.5 算法分析 18
1.3 程序、程序设计与程序设计方法学 19
1.3.1 程序 19
1.3.2 程序设计 20
1.3.3 程序设计方法学 20
1.4 计算思维与抽象数据类型 22
1.4.1 计算思维 23
1.4.2 计算机求解问题 24
1.4.3 抽象数据类型 25
1.4.4 数据类型、数据结构与抽象数据类型 27
1.5 课程设计相关知识 27
1.5.1 课程设计目的与内涵 28
1.5.2 课程设计步骤 28
1.5.3 课程设计报告规范 29
课后练习与课程设计 30
第2章 线性表 32
2.1 线性表ADT 32
2.2 顺序表 34
2.2.1 向量的顺序存储表示 34
2.2.2 向量运算 35
2.2.3 应用举例 41
2.2.4 不等长结点的索引表示——目录表 44
2.3 链表 45
2.3.1 指针与指针对象 45
2.3.2 单链表 48
2.3.3 线性表的两种存储比较 60
2.3.4 可利用空间表及其管理 60
2.4 线性表的其他链接存储表示 62
2.4.1 循环链表 62
2.4.2 双向链表 63
2.4.3 静态链表 65
2.5 课程设计相关知识与应用示例 67
2.5.1 算法设计中的基本方法 67
2.5.2 一元多项式相乘 68
课后练习与课程设计 72
第3章 栈和队列 75
3.1 栈ADT 75
3.2 顺序栈 77
3.2.1 顺序栈的存储表示 77
3.2.2 顺序栈基本运算的实现 77
3.3 链接栈 81
3.3.1 链接栈的存储表示 81
3.3.2 链接栈基本运算的实现 81
3.4 栈的应用举例 82
3.4.1 数制转换 82
3.4.2 表达式求值 84
3.5 队列ADT 88
3.6 顺序队列 89
3.6.1 顺序队列的存储表示 89
3.6.2 顺序队列的基本运算的实现 90
3.7 链接队列 92
3.7.1 链接队列的存储表示 92
3.7.2 链接队列基本运算的实现 93
3.8 随机事件模拟 96
3.9 课程设计相关知识与应用示例 99
3.9.1 递归概念 99
3.9.2 递归过程设计 101
3.9.3 递归过程与非递归过程 101
课后练习与课程设计 104
第4章 几种特殊线性表 107
4.1 串 107
4.1.1 串的基本概念 107
4.1.2 串ADT 109
4.1.3 串的存储表示 110
4.1.4 串运算的实现 112
4.2 数组 113
4.2.1 数组ADT 113
4.2.2 数组的顺序存储表示 115
4.3 矩阵 116
4.3.1 对称矩阵的压缩存储 116
4.3.2 对角矩阵的压缩存储 117
4.3.3 稀疏矩阵的三元组顺序表存储表示 119
4.3.4 稀疏矩阵的十字链表存储表示 120
4.3.5 稀疏矩阵的转置运算 121
4.3.6 稀疏矩阵的插入运算 122
4.4 广义表 124
4.4.1 广义表的基本概念 124
4.4.2 广义表ADT 125
4.4.3 广义表的存储表示 126
4.4.4 多元多项式的存储表示 128
4.5 课程设计相关知识与应用示例 129
4.5.1 梵天塔问题 129
4.5.2 再谈递归过程设计 131
4.5.3 求广义表的深度 132
课后练习与课程设计 133
第5章 内排序 137
5.1 排序的基本概念 137
5.2 直接插入排序 138
5.3 直接选择排序 141
5.4 冒泡排序 143
5.5 希尔排序 145
5.6 快速排序 147
5.7 归并排序 152
5.7.1 排序文件的归并 152
5.7.2 2—路归并排序 153
5.8 基数排序 155
5.9 各种排序方法的比较 159
5.10 课程设计相关知识与应用示例 161
5.10.1 自顶向下设计技术与方法 161
5.10.2 逐步求精设计技术与方法 162
5.10.3 积木游戏 162
课后练习与课程设计 165
第6章 树和二叉树 168
6.1 树的基本概念 168
6.2 树的存储结构 171
6.2.1 树的标准形式存储结构 171
6.2.2 树的逆形式存储结构 172
6.2.3 树的扩充标准形式存储结构 173
6.2.4 树的双亲数组存储结构 174
6.2.5 树的孩子链表存储结构 174
6.2.6 树的三重链表存储结构 176
6.3 树的遍历和树的线性表示 177
6.3.1 树的前序遍历 177
6.3.2 树的后序遍历 179
6.3.3 树的层次遍历 180
6.3.4 树的线性表示 182
6.4 二叉树 183
6.4.1 二叉树定义和二叉树ADT 183
6.4.2 二叉树的性质 185
6.4.3 二叉树与树（或森林）之间的转换 186
6.4.4 二叉树的存储表示 188
6.5 二叉树遍历 192
6.5.1 二叉树遍历 192
6.5.2 由遍历序列构造二叉树 203
6.5.3 基于二叉树遍历操作的算法举例 204
6.6 线索二叉树 206
6.6.1 线索二叉树 206
6.6.2 线索二叉树的利用 208
6.6.3 二叉树的线索化 210
6.7 哈夫曼树及其应用 212
6.7.1 二叉树的路径长度和带权路径长度 212
6.7.2 哈夫曼树和哈夫曼算法 213
6.7.3 哈夫曼树的应用 216
6.8 课程设计相关知识与应用示例 223
6.8.1 结构化方法概述 223
6.8.2 模块化设计技术与方法 223
6.8.3 模块化应用示例 224
课后练习与课程设计 227
第7章 图 230
7.1 图的基本概念 230
7.2 图的存储结构 234
7.2.1 邻接矩阵 234
7.2.2 邻接表 236
7.3 图的遍历 238
7.3.1 深度优先搜索法 239
7.3.2 广度优先搜索法 240
7.3.3 求图的（强）连通分量 242
7.4 生成树与最小生成树 242
7.4.1 生成树概念 242
7.4.2 最小生成树 243
7.5 最短路径 248
7.5.1 单源最短路径 249
7.5.2 每一对顶点间的最短路径 253
7.6 拓扑排序 255
7.6.1 AOV网 255
7.6.2 拓扑排序 256
7.7 关键路径 258
7.7.1 AOE网 258
7.7.2 关键路径 258
7.8 课程设计相关知识与应用示例 262
7.8.1 递推算法 262
7.8.2 分治法概述 263
7.8.3 数字旋转方阵 264
课后练习与课程设计 267
第8章 查找 271
8.1 线性表查找 271
8.1.1 顺序查找 271
8.1.2 折半查找 273
8.1.3 分块查找 275
8.2 树型结构查找 276
8.2.1 二叉排序树 276
8.2.2 平衡查找树 281
8.2.3 B树和B+树 288
8.2.4 堆排序 293
8.3 哈希表及其查找 296
8.3.1 哈希表 296
8.3.2 哈希函数构造方法 297
8.3.3 解决冲突方法 299
8.3.4 哈希表的查找 301
8.4 课程设计相关知识与应用示例 304
8.4.1 动态规划法概述 304
8.4.2 贪心法概述 305
8.4.3 背包问题 305
课后练习与课程设计 308
第9章 文件与外部排序 311
9.1 文件概述 311
9.2 文件组织 312
9.2.1 顺序文件 312
9.2.2 索引文件 313
9.2.3 哈希文件 315
9.2.4 多关键字文件 316
9.3 外部排序 318
9.3.1 2—路平衡归并排序法 318
9.3.2 多路平衡归并排序法 320
9.3.3 置换—选择排序 322
9.3.4 最优归并树 326
9.4 课程设计相关知识与应用示例 327
9.4.1 回溯法概述 328
9.4.2 分支限界法概述 329
9.4.3 数据结构课程设计示例 331
课后练习与课程设计 333
参考文献 335