第1章 绪论 1
1.1 数据结构的概念和学习数据结构的必要性 1
1.2 数据结构的基本概念 2
1.2.1 数据 2
1.2.2 数据元素和数据项 2
1.2.3 数据结构 3
1.3 抽象数据类型及其实现 4
1.3.1 数据类型 4
1.3.2 抽象数据类型 4
1.3.3 C＋＋程序的典型构架 5
1.3.4 C＋＋的类和对象 6
1.3.5 C＋＋的友元函数 7
1.3.6 运算符重载 9
1.3.7 C＋＋的参数传递 12
1.3.8 C＋＋的输入输出 14
1.3.9 有关C＋＋的动态存储分配 15
1.3.10 结构与类 17
1.3.11 C＋＋的模板 17
1.4 算法和算法分析 19
1.4.1 算法 19
1.4.2 算法分析 20
1.5 实用程序软件包 23
1.6 实例研究 31
1.6.1 生命游戏 31
1.6.2 计算任意位数的π 31
1.7 深入学习导读 38
习题1 38
上机实验题1 39
第2章 线性表 41
2.1 线性表的逻辑结构 41
2.2 线性表的顺序存储结构 42
2.3 线性表的链式存储结构 51
2.3.1 单链表 51
2.3.2 循环链表 59
2.3.3 双向链表 63
2.3.4 在链表结构中保存当前位置和元素个数 66
2.4 实例研究 78
2.4.1 一元多项式的表示 78
2.4.2 计算任意大整数的阶乘 83
2.5 深入学习导读 86
习题2 87
上机实验题2 87
第3章 栈和队列 88
3.1 栈 88
3.1.1 栈的基本概念 88
3.1.2 顺序栈 89
3.1.3 链式栈 94
3.2 队列 100
3.2.1 队列的基本概念 100
3.2.2 链队列 102
3.2.3 循环队列——队列的顺序存储结构 106
3.2.4 队列应用——显示二项式（a+b）i的系数 111
3.3 优先队列 112
3.4 实例研究 116
3.4.1 表达式求值 116
3.4.2 事件驱动模拟 119
3.5 深入学习导读 124
习题3 125
上机实验题3 125
第4章 串 127
4.1 串类型的定义 127
4.2 字符串的实现 128
4.3 字符串模式匹配算法 134
4.3.1 简单字符串模式匹配算法 134
4.3.2 首尾字符串模式匹配算法 136
4.3.3 KMP字符串模式匹配算法 136
4.4 实例研究 141
4.4.1 文本编辑 141
4.4.2 查找子序列 142
4.5 深入学习导读 143
习题4 143
上机实验题4 143
第5章 数组和广义表 144
5.1 数组 144
5.1.1 数组的基本概念 144
5.1.2 数组的顺序存储方式 144
5.1.3 数组的类定义 147
5.2 矩阵 150
5.2.1 矩阵的定义和操作 150
5.2.2 特殊矩阵 152
5.2.3 稀疏矩阵 157
5.3 广义表 167
5.3.1 基本概念 167
5.3.2 广义表的存储结构 169
5.4 实例研究 179
5.4.1 稳定伴侣问题 179
5.4.2 m元多项式的表示 179
5.5 深入学习导读 182
习题5 183
上机实验题5 183
第6章 树和二叉树 184
6.1 树的基本概念 184
6.1.1 树的定义 184
6.1.2 基本术语 184
6.2 二叉树 186
6.2.1 二叉树的定义 186
6.2.2 二叉树的性质 188
6.2.3 二叉树的存储结构 190
6.3 二叉树遍历 199
6.3.1 遍历的定义 199
6.3.2 遍历算法 200
6.3.3 二叉树遍历应用举例 206
6.4 线索二叉树 211
6.4.1 线索的概念 211
6.4.2 线索二叉树的实现 213
6.5 树和森林 221
6.5.1 树的存储表示 221
6.5.2 树的显示 228
6.5.3 森林的存储表示 228
6.5.4 树和森林的遍历 233
6.5.5 树和森林与二叉树的转换 235
6.6 哈夫曼树与哈夫曼编码 238
6.6.1 哈夫曼树的基本概念 238
6.6.2 哈夫曼树构造算法 239
6.6.3 哈夫曼编码 239
6.6.4 哈夫曼树的实现 241
6.7 树的计数 245
6.8 实例研究 247
6.8.1 树与等价关系 247
6.8.2 Huffman压缩算法 251
6.9 深入学习导读 256
习题6 256
上机实验题6 257
第7章 图 258
7.1 图的定义和术语 258
7.2 图的存储表示 262
7.2.1 邻接矩阵 262
7.2.2 邻接表 267
7.3 图的遍历 274
7.3.1 深度优先搜索 275
7.3.2 广度优先搜索 276
7.4 图的最小代价生成树 277
7.4.1 Prim算法 278
7.4.2 Kruskal算法 280
7.5 有向无环图及应用 284
7.5.1 拓扑排序 284
7.5.2 关键路径 287
7.6 最短路径 291
7.6.1 单源点最短路径问题 291
7.6.2 所有顶点之间的最短路径 294
7.7 实例研究 296
7.7.1 周游世界问题——哈密尔顿圈 296
7.7.2 一笔画问题——欧拉问题 298
7.8 深入学习导读 299
习题7 299
上机实验题7 301
第8章 查找 302
8.1 查找的基本概念 302
8.2 静态表的查找 305
8.2.1 顺序查找 305
8.2.2 有序表的查找 306
8.3 动态查找表 309
8.3.1 二叉排序树 309
8.3.2 二叉平衡树 319
8.3.3 B树和B＋树 343
8.4 散列表 345
8.4.1 散列表的概念 345
8.4.2 构造散列函数的方法 345
8.4.3 处理冲突的方法 346
8.4.4 散列表的实现 347
8.5 实例研究 352
8.5.1 查找3个数组的最小共同元素 352
8.5.2 查找最小元素 353
8.6 深入学习导读 354
习题8 354
上机实验题8 355
第9章 排序 356
9.1 概述 356
9.2 插入排序 357
9.2.1 直接插入排序 357
9.2.2 Shell排序 358
9.3 交换排序 360
9.3.1 起泡排序 360
9.3.2 快速排序 361
9.4 选择排序 364
9.4.1 简单选择排序 364
9.4.2 堆排序 365
9.5 归并排序 368
9.6 基数排序 373
9.6.1 多关键排序 373
9.6.2 基数排序 373
9.7 各种内部排序方法讨论 376
9.8 外部排序 378
9.8.1 外部排序基础 378
9.8.2 外部排序的方法 378
9.9 实例研究 380
9.9.1 宴会中来宾数目的最大值 380
9.9.2 各种排序算法运行时间测试 382
9.9.3 用堆实现优先队列 385
9.10 深入学习导读 388
习题9 388
上机实验题9 389
第10章 文件 390
10.1 主存储器和辅助存储器 390
10.2 各种常用文件结构 390
10.2.1 顺序文件 390
10.2.2 索引文件 391
10.2.3 散列文件 392
10.3 实例研究 392
10.3.1 VSAM文件 392
10.3.2 多关键字文件 393
10.4 深入学习导读 395
习题10 395
上机实验题10 395
第11章 算法设计与分析 397
11.1 算法设计 397
11.1.1 递归算法 397
11.1.2 分治算法 401
11.1.3 动态规划算法 407
11.1.4 贪心算法 422
11.1.5 回溯算法 425
11.1.6 分支限界法 430
11.2 算法分析 440
11.2.1 递归分析 440
11.2.2 利用生成函数进行分析 443
11.3 可计算性问题 445
11.3.1 归约 445
11.3.2 难解问题、N问题、NP问题和NP完全性问题 446
11.3.3 不可编程问题 447
11.4 实例研究 449
11.4.1 图着色问题 449
11.4.2 多边形游戏 451
11.5 深入学习导读 455
习题11 456
上机实验题11 456
附录A 调和级数 458
附录B 泊松分布 459
附录C 配套的软件包 460
附录D 课程设计项目 466
附录E 实验报告格式 471
附录F 课程设计报告格式 472
参考文献 473