（1）根据教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范编写。

　　（2）内容涵盖数据结构与算法的基本概念和算法分析的简单方法，以及C语言编程的要点。

　　（3）作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排了教材内容，力求透彻、全面。对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西，都有适当的提示。

　　（4）是学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材。

　　第2版前言

　　本书第2版的初稿完成于2015年12月，作为另一本教材《数据结构精讲与习题详解》（第2版）的写作参照，相互融合，相互补充，首先完成了该书，再回过头来第二次修改本书，所以本书实际上是第2版的修订本。

　　自从1978年美籍华人冀中田*次在中国讲授“数据结构”课开始，很多老师对课程的内容和讲授方法做了大量的研究，也可以说是在做中学，总结出许多好的经验，使得课程的教学比当时进步了很多。我本人在这门课程的教学中也积累了一些心得，非常希望与正在学习这门课程的同学们分享，这是我修改这本教材的初衷。

　　既然数据结构与算法相辅相成，密不可分，而算法就是解决问题的过程描述，那么，描述数据结构与算法的语言就应该是过程性的。早期用伪代码描述，实践证明不可持续，因为很多用伪代码描述的算法转换为使用某种编程语言编写的程序后，怎么也通不过。原因是很多人编程语言的实践能力太差，算法的实现细节太粗糙。所以我认为，使用某种过程性语言，如C、C++等，对于学习和实现数据结构与算法是合适的。

　　由于数据结构课程学时的限制（多数学校为48～64学时），作为本科生的教材，包含的知识容量应有一定限度。知识点太少，学生在未来的学习和工作中可联想的思考空间狭窄，使解决问题的能力受限；知识点太多，必然沦为百科全书式的阅读，基础不牢靠，同样使得解决问题的能力受限。通过教学实践证明，本书的第1版在内容上取材是恰当的，范围上取材的深度和广度也是恰当的，但联想不够，某些算法的实现上偏向使用伪代码描述，造成部分读者在学习上和实践上的困惑。本书第2版修改部分包括：

　　（1）在结构上从第1版的10章改为8章，虽然章数压缩了，但叙述内容不减反增。增加的知识点大多作为“扩展阅读”出现，它们不作为考核内容，主要是拓展视野。

　　（2）各章的“想想看”改为“思考题”，目的是增加一些互动环节。这些思考题触及的都是可联想的内容，或者是对理解正文有用的知识“点拨”。所谓“学问”就是有“学”还要有“问”。正面的“问”有助于理解“应该做什么”，反面的“问”有助于理解“不该做什么”。

　　（3）书中所有使用C语言书写的算法，包括辅助教材《数据结构精讲与习题详解》（第2版）中的800道算法题，都重新使用VC++ 6.0编译程序调试过，有的还按照软件工程的要求做了边界值测试。因为书中算法的正确运行需要构建运行环境，所以对于书中所涉及的主要数据结构的存储表示，绝大多数都在第2版给出了结构定义、初始化或创建算法、输出算法等，这样可由读者自行搭建运行环境。

　　（4）第3章增加了多栈共享同一存储时的栈浮动技术、递归程序的非递归模拟方法、优先队列的内容；第4章增加了w对角矩阵的压缩存储、稀疏矩阵的链表存储、串的BM模式匹配算法的内容；第5章增加了等价类与并查集的内容；第6章增加了构造*小生成树的破圈法、Dijkstra算法的内容；第7章增加了跳表、红黑树、伸展树、字典树的内容。此外对保留的内容有部分增删。教材现有内容基本覆盖大多数学校的教学大纲和考研大纲。

　　（5）附录增加了词汇索引，书中出现的重要概念都收录在索引中，大大方便了读者查阅相关的词汇。

　　各章所附习题不包括选择题，但精选了许多综合应用题，这些习题的参考解答请参看作者的另一本配套教材《数据结构精讲与习题详解》。

　　因为作者的水平有限，可能在某些方面有考虑不周的地方，书中难免存在疏漏或错误，诚恳希望读者提出宝贵意见。

　　作 者

　　2016年8月于清华大学

收起全部↑

第1章 绪论 1 

1.1 数据结构的概念及分类 1 

1.1.1 为什么要学习数据结构 1 

1.1.2 与数据结构相关的基本术语 2 

1.1.3 数据结构的分类 5 

1.1.4 数据结构的存储结构 6 

1.1.5 定义在数据结构上的操作 7 

1.1.6 “好”数据结构 7 

1.2 使用C语言描述数据结构 7 

1.2.1 C语言的数据类型 8 

1.2.2 算法的控制结构 9 

1.2.3 算法的函数结构 10 

1.2.4 动态存储分配 12 

1.2.5 逻辑和关系运算的约定 12 

1.2.6 输入与输出 13 

1.3 算法和算法设计 13 

1.3.1 算法的定义和特性 13 

1.3.2 算法的设计步骤 14 

1.3.3 算法设计的基本方法 15 

1.4 算法分析与度量 18 

1.4.1 算法的评价标准 18 

1.4.2 算法的时间和空间复杂度度量 18 

1.4.3 算法的渐近分析 21 

小结 24 

习题 24 

第2章 线性表 27 

2.1 线性表 27 

2.1.1 线性表的定义和特点 27 

2.1.2 线性表的主要操作 28 

2.2 顺序表 29 

2.2.1 顺序表的定义和特点 29 

2.2.2 顺序表的结构定义 30 

2.2.3 顺序表查找操作的实现 31 

2.2.4 顺序表插入和删除操作的实现 32 

2.2.5 顺序表的应用：集合运算 34 

2.3 单链表 35 

2.3.1 单链表的定义和特点 35 

2.3.2 单链表的结构定义 36 

2.3.3 单链表中的插入与删除 36 

2.3.4 带头结点的单链表 40 

2.3.5 单链表的遍历与创建 42 

2.3.6 单链表的应用：集合运算 44 

2.3.7 循环链表 46 

2.3.8 双向链表 50 

2.3.9 静态链表 53 

2.4 顺序表与线性链表的比较 54 

2.5 线性表的应用：一元多项式及其运算 56 

2.5.1 一元多项式的表示 56 

2.5.2 多项式的结构定义 57 

2.5.3 多项式的加法 59 

2.5.4 扩展阅读：多项式的乘法 60 

小结 62 

习题 63 

第3章 栈和队列 66 

3.1 栈 66 

3.1.1 栈的概念 66 

3.1.2 顺序栈 67 

3.1.3 扩展阅读：多栈处理 70 

3.1.4 链式栈 73 

3.1.5 扩展阅读：栈的混洗 74 

3.2 队列 76 

3.2.1 队列的概念 76 

3.2.2 循环队列 76 

3.2.3 链式队列 80 

3.3 栈的应用 82 

3.3.1 数制转换 82 

3.3.2 括号匹配 83 

3.3.3 表达式的计算与优先级处理 84 

3.3.4 栈与递归的实现 88 

3.4 队列的应用 91 

3.5 在算法设计中使用递归 92 

3.5.1 汉诺塔问题与分治法 92 

3.5.2 直接把递归过程改为非递归过程 94 

3.5.3 扩展阅读：递归过程的非递归模拟算法 95 

3.5.4 迷宫问题与回溯法 98 

3.5.5 计算组合数与动态规划 101 

3.6 扩展阅读：双端队列 102 

3.6.1 双端队列的概念 102 

3.6.2 输入受限的双端队列 103 

3.6.3 输出受限的双端队列 104 

3.6.4 双端队列的存储表示 104 

3.7 扩展阅读：优先队列 106 

3.7.1 优先队列的概念 106 

3.7.2 优先队列的实现 107 

小结 108 

习题 108 

第4章 数组、串和广义表 112 

4.1 数组 112 

4.1.1 一维数组 112 

4.1.2 多维数组 114 

4.2 特殊矩阵的压缩存储 116 

4.2.1 对称矩阵的压缩存储 117 

4.2.2 三对角矩阵的压缩存储 118 

4.2.3 扩展阅读：w对角矩阵的压缩存储 119 

4.3 稀疏矩阵 120 

4.3.1 稀疏矩阵的概念 120 

4.3.2 稀疏矩阵的顺序存储表示 121 

4.3.3 稀疏矩阵的链表表示 124 

4.4 字符串 125 

4.4.1 字符串的概念 126 

4.4.2 字符串的初始化和赋值 126 

4.4.3 自定义字符串的存储表示 128 

4.4.4 串的模式匹配 132 

4.5 广义表 140 

4.5.1 广义表的概念 140 

4.5.2 广义表的性质 141 

4.5.3 广义表的链接表示 141 

4.5.4 扩展阅读：三元多项式的表示 147