编辑推荐
（1）根据教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范编写。
（2）内容涵盖数据结构与算法的基本概念和算法分析的简单方法，以及C语言编程的要点。
（3）作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排了教材内容，力求透彻、全面。对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西，都有适当的提示。
（4）是学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材。
内容简介
《数据结构（C语言版）（第2版）/清华大学计算机系列教材》是根据教育部《高等学校计算机科学与技术专业公共核心知识体系与课程》编写的数据结构主教材。《数据结构（C语言版）（第2版）/清华大学计算机系列教材》共8章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2～8章分别介绍了线性表、栈和队列及其应用、多维数组、特殊矩阵、稀疏矩阵、字符串和广义表、树与二叉树、图、查找、排序，并做了适当延伸。作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排教材内容，力求透彻、全面，对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西都有适当的提示。
《数据结构（C语言版）（第2版）/清华大学计算机系列教材》的编写得到清华大学2015年精品教材建设项目的资助。《数据结构（C语言版）（第2版）/清华大学计算机系列教材》既可作为高等学校计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材，还可作为计算机或软件系统开发人员的参考资料。
目录
第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.1C语言的数据类型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前言/序言
第2版前言
《数据结构（C语言版）（第2版）/清华大学计算机系列教材》第2版的初稿完成于2015年12月，作为另一本教材《数据结构精讲与习题详解》（第2版）的写作参照，相互融合，相互补充，首先完成了该书，再回过头来第二次修改《数据结构（C语言版）（第2版）/清华大学计算机系列教材》，所以《数据结构（C语言版）（第2版）/清华大学计算机系列教材》实际上是第2版的修订本。
自从1978年美籍华人冀中田*次在中国讲授“数据结构”课开始，很多老师对课程的内容和讲授方法做了大量的研究，也可以说是在做中学，总结出许多好的经验，使得课程的教学比当时进步了很多。我本人在这门课程的教学中也积累了一些心得，非常希望与正在学习这门课程的同学们分享，这是我修改这本教材的初衷。
既然数据结构与算法相辅相成，密不可分，而算法就是解决问题的过程描述，那么，描述数据结构与算法的语言就应该是过程性的。早期用伪代码描述，实践证明不可持续，因为很多用伪代码描述的算法转换为使用某种编程语言编写的程序后，怎么也通不过。原因是很多人编程语言的实践能力太差，算法的实现细节太粗糙。所以我认为，使用某种过程性语言，如C、C++等，对于学习和实现数据结构与算法是合适的。
由于数据结构课程学时的限制（多数学校为48～64学时），作为本科生的教材，包含的知识容量应有一定限度。知识点太少，学生在未来的学习和工作中可联想的思考空间狭窄，使解决问题的能力受限；知识点太多，必然沦为百科《数据结构（C语言版）（第2版）/清华大学计算机系列教材》式的阅读，基础不牢靠，同样使得解决问题的能力受限。通过教学实践证明，《数据结构（C语言版）（第2版）/清华大学计算机系列教材》的第1版在内容上取材是恰当的，范围上取材的深度和广度也是恰当的，但联想不够，某些算法的实现上偏向使用伪代码描述，造成部分读者在学习上和实践上的困惑。《数据结构（C语言版）（第2版）/清华大学计算机系列教材》第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月于清华大学
