1.1 数据结构讨论的范畴 1
第1章 绪论 1
1.2 基本概念及术语 2
1.2.1 数据 2
1.2.2 数据元素 3
1.2.3 数据对象 3
1.2.4 数据结构 3
1.2.5 数据类型 4
1.2.6 抽象数据类型 4
1.3.1 C++的简单程序 5
1.3 抽象数据类型的实现 5
1.3.2 C++作用域的说明 6
1.3.3 C++的类和对象 6
1.3.4 C++的参数传递 8
1.3.5 C++的输入输出 10
1.3.6 C++的动态存储分配 11
1.3.7 C++的友元函数 13
1.3.8 C++的运算符重载 13
1.3.9 结构与类 15
1.3.10 C++的模板 15
1.4.1 算法 18
1.4 算法和算法分析 18
1.4.2 算法分析 19
第2章 线性表 23
2.1 线性表的逻辑结构 23
2.2 线性表的顺序存储结构 25
2.3 线性表的链式存储结构 33
2.3.1 单链表 33
2.3.2 循环链表 41
2.3.3 双向链表 45
2.3.4 保存当前位置和元素个数 48
3.1.1 栈的基本概念 61
第3章 栈和队列 61
3.1 栈 61
3.1.2 顺序栈 62
3.1.3 链式栈 67
3.1.4 栈的应用 74
3.2 队列 77
3.2.1 队列的基本概念 77
3.2.2 链式队列 79
3.2.3 循环队列——队列的顺序存储结构 82
第4章 串 88
4.1 串的定义 88
4.2.1 定长顺序存储表示 90
4.2 串的存储表示 90
4.2.2 堆分配存储表示 92
4.2.3 链表存储表示 95
4.3 串的模式匹配算法 96
4.3.1 简单算法 96
4.3.2 首尾匹配算法 98
4.3.3 KMP算法 98
第5章 数组和广义表 103
5.1 数组 103
5.1.1 数组的基本概念 103
5.1.2 数组的存储实现 104
5.2 数组的类定义 105
5.2.1 一维数组的类定义及实现 106
5.2.2 二维数组的类定义及实现 108
5.3 矩阵 111
5.3.1 矩阵的定义和操作 111
5.3.2 特殊矩阵 116
5.3.3 稀疏矩阵 120
5.4 广义表 126
5.4.1 基本概念 126
5.4.2 广义表的存储结构 128
6.1.1 树的定义 135
6.1 树的基本概念 135
第6章 树和二叉树 135
6.1.2 基本术语 136
6.2 二叉树 137
6.2.1 二叉树的定义 137
6.2.2 二叉树的性质 138
6.3 二叉树的存储结构 139
6.3.1 顺序存储结构 140
6.3.2 链式存储结构 141
6.4 二叉树遍历 145
6.4.1 遍历的定义 145
6.4.2 遍历算法 146
6.4.3 二叉树遍历的应用 151
6.5 线索化二叉树 153
6.5.1 线索化的概念 153
6.5.2 线索化算法 156
6.5.3 遍历线索化二叉树 157
6.6 树和森林 159
6.6.1 树的存储表示 159
6.6.2 树和森林的遍历 161
6.6.3 树和森林与二叉树的转换 163
6.7 哈夫曼树与哈夫曼编码 164
6.7.1 哈夫曼树的基本概念 164
6.7.2 哈夫曼树构造算法 165
6.7.3 哈夫曼编码 168
6.8 树的计数 170
第7章 图 175
7.1 图的定义和术语 175
7.2 图的存储表示 179
7.2.1 邻接矩阵 179
7.2.2 邻接表 185
7.3 图的遍历 193
7.3.1 深度优先搜索 194
7.3.2 广度优先搜索 195
7.4.1 Prim算法 197
7.4 图的最小代价生成树 197
7.4.2 Kruskal算法 200
7.5 有向无环图及应用 203
7.5.1 拓扑排序 204
7.5.2 关键路径 206
7.6 最短路径 211
7.6.1 单源点最短路径问题 211
7.6.2 所有顶点之间的最短路径 214
第8章 查找 219
8.1 查找的基本概念 219
8.2.1 顺序查找 220
8.2 静态表的查找 220
8.2.2 有序表的查找 221
8.2.3 分块查找 224
8.3 动态查找表 225
8.3.1 二叉排序树 225
8.3.2 二叉平衡树 233
8.3.3 B树和B+树 252
8.4 散列表 254
8.4.1 散列表的概念 254
8.4.2 构造散列函数的方法 254
8.4.3 处理冲突的方法 255
8.4.4 散列表的实现 256
8.4.5 散列法性能分析 261
第9章 排序 263
9.1 概述 263
9.2 插入排序 264
9.3 希尔排序 266
9.4 交换排序 268
9.4.1 起泡排序 268
9.4.2 快速排序 269
9.5 选择排序 272
9.5.1 简单选择排序 272
9.5.2 堆排序 273
9.6 归并排序 277
9.7 基数排序 279
9.7.1 多关键排序 280
9.7.2 基数排序 280
9.8 外部排序 283
9.8.1 外部排序基础 283
9.8.2 外部排序的方法 283
第10章 文件 287
10.1 主存储器和辅助存储器 287
10.2 磁盘 288
10.2.1 磁盘结构 288
10.2.2 磁盘访问代价分析 292
10.2.3 磁盘缓存 293
10.3 文件结构 295
10.3.1 顺序文件 295
10.3.2 索引文件 297
10.3.3 ISAM文件和VSAM文件 298
10.3.4 散列文件 301
10.3.5 多关键字文件 302
第11章 算法设计技术 305
11.1 算法设计 305
11.2.1 算法思想 308
11.2.2 应用 308
11.2 贪心算法 308
11.3 分治算法 311
11.3.1 算法思想 311
11.3.2 应用 311
11.4 回溯算法 315
11.4.1 算法思想 315
11.4.2 应用 315
11.5 分支定界 318
11.5.1 算法思想 318
11.5.2 应用 318
11.6.2 应用 322
11.6.1 算法思想 322
11.6 动态规划 322
第12章 分析技术与可计算问题 325
12.1 分析技术 325
12.1.1 求和分析 325
12.1.2 递归分析 326
12.1.3 均摊分析 328
12.1.4 算法分析举例 329
12.2 可计算问题 332
12.2.1 归约 332
12.2.2 难解问题 334
12.2.3 不可解问题 338