书结合C++面向对象程序设计的特点，构建了数据结构与算法，对所有算法都在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中进行了严格的测试，作者教学网站（http://cs.scu.edu.cn/~youhongyue）提供了大量的教学支持内容。同时本书配有《数据结构与算法（C++版）实验和课程设计教程》 (ISBN 978-7-302-17503-2）供读者学习参考。
本书共分11章，第1章是基础知识，介绍了基本概念及其术语，并讨论了实用程序软件包；第2章引入线性表；第3章介绍了栈和队列，用栈实现了表达式求值；第4章介绍串，详细讨论了串的存储结构与模式匹配算法；第5章介绍数组和广义表，首次提出了广义表的使用空间表存储结构；第6章介绍了树结构，应用哈夫曼编码实现了压缩软件；第7章介绍图结构，实现了图的常用存结构，讨论了图的相关应用，并实现了相应算法；第8章介绍查找，讨论了静态查找表、动态查找表与散列表，实现了所有算法；第9章介绍排序，以简洁方式实现各种排序算法；第10章介绍了文件，讨论了各种常用文件结构；第11章介绍了算法设计技术、分析技术与可计算问题。
通过本书的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力，经过适当的选择，本书能作为高等院校计算机及相关专业“数据结构”、“数据结构与算法”、“数据结构与算法分析”和“数据结构与算法设计”等课程的教材，也可供其他从事软件开发工作的读者参考。
目录
- 第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
- 习题138
- 上机实验题139第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
- 习题287
- 上机实验题287第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
- 习题3125
- 上机实验题3125第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
- 习题4143
- 上机实验题4143第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
- 习题5183
- 上机实验题5183第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
- 习题6256
- 上机实验题6257第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
- 习题7299
- 上机实验题7301第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
- 习题8354
- 上机实验题8355第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
- 习题9388
- 上机实验题9389第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
- 习题10395
- 上机实验题10395第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
- 习题11456
