本书是根据2007年教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范和2010年修订的《全国硕士研究生入学考试计算机专业基础综合考试大纲》编写的数据结构主教材。全书共分7章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2章～第7章对应考试大纲的6个知识单元，包括线性表，栈、队列和数组，树与二叉树，图，查找，排序。作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排了教材内容，力求透彻、全面；对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西，都有适当的提示。
本书既可作为普通大学计算机科学与技术专业本科生学习数据结构课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机考试的复习教材，还可以作为从事计算机系统开发的人员参考的学习资料。
数据结构
C语言描述
殷人昆 编著
Data Structures in C
本书特点
采用“工科”思维，启发学生掌握“化复杂为简单”的方式，从问题入手，通过“问题/子问题”分解，寻找解决方案。
对基本知识点讲深讲透，通过多种应用举例，让学生了解不同问题需要采取什么方法来应对。
通过大量习题，从不同视点、不同层面训练学生，培养其联想能力，提高其分析问题、解决问题的能力。
可配合辅助教材《数据结构习题精析与考研辅导》进行学习，该书提供了600多题的参考答案和解析，并就关键点进行点拨，另外，提供了多套模拟题。
涵盖2009～2011年计算机学科研究生联考数据结构部分的真题及解析。
作者简介
殷人昆 清华大学计算机系教授，中国科学院研究生院工程教育部兼职教授。1985年赴日本东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要负责清华大学计算机系“数据结构”、“软件工程”的本科课程教学工作和“软件工程技术与设计”、“软件项目管理”的研究生课程教学工作。主讲的“数据结构”课程被评为清华大学精品课程。曾与人合作或单独编写教材十余本。曾在核心刊物和专业会议发表论文多篇。
从2006年到2007年，为适应计算机科学与技术专业人才培养的需求，教育部高等学校计算机科学与技术教学指导委员会颁发了《高等学校计算机科学与技术专业公共核心知识体系与课程》规范，该规范参照ACM、AIS和IEEE-CS发布的Computing Curricula 2005，从问题空间、知识取向、能力要求等方面，给出了教育改革和专业能力培养的新要求。按照知识取向的不同，把计算机科学与技术学科划分为计算机科学（CS）、计算机工程（CE）、软件工程（SE）和信息技术（IT）四个方向。从问题空间划分，计算机科学属于科学型，计算机工程和软件工程属于工程型，信息技术属于应用型。
规范中规定，数据结构课程涵盖的知识单元有5个：基本算法（AL3）、算法与问题求解（PF2）、基本数据结构（PF3）、递归（PF4）和分布式算法（AL4）。教学大纲包括：(1)算法、算法的时间复杂度和空间复杂度，最坏和平均时间复杂度等概念；(2)算法描述；(3)常用算法设计方法：迭代法、穷举搜索法、递推法、算法的递归描述技术；(4)数据结构的基本概念和术语：数据结构、数据类型、抽象数据类型、信息隐藏；(5)线性表、线性表的存储结构：顺序、链接；(6)栈、队列；(7)串；(8)多维数组和广义表；(9)树形结构及其应用：树、森林、二叉树、线索二叉树、Huffman树；(10)图及其应用：图的基本概念、图的存储结构、图的遍历、生成树和最小生成树、最短路径、拓扑排序；(11)常用排序算法：插入排序、交换排序、选择排序；(12)常用查找技术：线性表上的查找、树的查找、散列技术；(13)文件：顺序文件、索引文件、索引顺序文件、散列文件。
不同的学科方向对以上知识单元的侧重点有所不同，见下表。
学科方向涵盖知识点学时计算机科学 算法分析基础、算法策略、基本算法、分布式算法、可计算性理论基础、算法与问题求解、基本数据结构、递归48+16计算机工程 基本算法分析、算法策略、计算算法、分布式算法、算法复杂性、算法与问题求解、基本数据结构、递归48+16软件工程 计算机科学基础（程序设计基础、算法及数据结构/表示、抽象（使用和支持）程序设计语言基础）、测试（例外处理）48+16信息技术 基本数据结构、算法和问题解决、递归48+16
在2008年，教育部决定从2009年起，对全国硕士研究生入学统一考试计算机科学与技术学科的初试科目进行调整，其中对（工科）专业课采取了全国统一命题、统一考试。数据结构课程被列为考试科目之一。从3年批改考卷的经验来看，考试范围基本没有脱离考试大纲，也没有超出规范的要求。
然而，从考生的表现来看，答题的水平相差太多。2011年北京8000多名考生参加考试，选择题80分，平均得分48分；综合应用题70分，平均得分30分。这说明很多考生学得不够深入、扎实。为此，作者决心基于多年的教学经验和知识积累，编写一本适合广大有志于学好数据结构课程的学生学习的教材。
本书以专业基础能力培养为目标，承续计算机程序设计基础课程，完全遵照《全国硕士研究生入学统一考试计算机科学与技术学科联考考试大纲》，并参考教育部计算机科学与技术教学指导委员会《高等学校计算机专业人才专业能力构成与培养》的要求编写而成，旨在培养学生的基本计算思维能力，提高学生的算法设计和程序实现能力，并为学生提高系统开发能力打下良好的基础。为此，在编写本书的过程中做了如下工作：
(1)采用“工科”思维，启发学生掌握“化复杂为简单”的方式，从问题入手，通过“问题/子问题”分解，寻找解决方案。
(2)对基本知识点讲深讲透，通过多种应用举例，让学生了解不同问题需要采取什么方法来应对。
(3)通过大量习题，从不同视点、不同层面训练学生，培养其联想能力，提高其分析问题、解决问题的能力。
(4)配合辅助教材《数据结构习题精析与考研辅导》。辅助教材提供了600多题的参考答案和解析，并就关键点进行点拨，另外，提供了多套模拟题。
也就是说，本书的宗旨是培养学生从对问题的理解入手，运用已掌握的算法和数据结构知识寻找解决途径，构建适当的算法和基本程序，以求得问题的解决。在从简单到复杂讨论数据结构的过程中，逐步引入常用的算法设计策略，通过编程上机实验到工程实践，使学生初步掌握分析问题、解决问题的方法。
全书共分7章，各章内容如下：
第1章介绍了数据、数据结构及其算法等基本概念与基本知识，以及学习数据结构所需要掌握的C语言程序设计预备知识（这部分内容考试大纲未列出，但它为全书打下了基础，其中有一些概念在2011年的试卷中出现过）。
第2章介绍了线性结构及其基本操作内容，并给出基于数组与链表表示的情况下，其基本操作函数的实现方法。在介绍线性表的应用时，讨论了集合、字符串和多项式的实现。
第3章介绍了栈、队列、数组和双端队列的常用表示方法，以及栈、队列和数组的应用举例，还讨论了递归、分治、回溯、动态规划等算法设计的策略。
第4章介绍了树与二叉树的概念、表示方法及其常用操作的实现，还介绍了线索二叉树等特殊的二叉树结构，树与森林的常用表示方法及其基本操作的实现方法，二叉树与树的应用，包括二叉排序树、平衡二叉树、Huffman树、堆等。特别地，本章借讨论高斯八皇后问题，进一步讨论了回溯法，并引入了状态树和剪枝方法。
第5章介绍了图的概念、图的基本表示方法及其常用操作的实现，还介绍了图的遍历以及连通图、重连通图，此外还介绍了图的应用，包括生成树和最小生成树、最短路径、拓扑排序、关键路径等，多次涉及贪婪法等算法设计策略。
第6章介绍了多种常用的查找算法，包括顺序查找、折半查找算法及其扩展、索引顺序查找（分块查找）、多路查找树、B树、B+树、散列表等。
第7章介绍了多种常用的排序算法。
全书采用C语言作为数据结构及算法的描述工具，适当采用C++的少量语句以简化程序。算法描述力求结构化，注重编程风格，每个算法基本保持在100行之内，可读性强。
本书可以作为计算机科学与技术及相关专业本科生的教材，也可以作为计算机专业考研（硕士、工程硕士、博士）的复习教材，还可以供使用计算机做系统开发的人员学习使用。
本书是从作者多年在清华大学讲授“数据结构”课程的课件取材，并经过一定改编而成，因此在叙述上适合学生理解，在内容上浅显易懂，在选材上舍弃了很多超出规范和大纲的内容，增加了许多在一些老教材中忽略了的内容，希望不会辜负读者的期望。
各章所附习题不包括选择题，但精选了大量综合应用题，这些习题的参考解答请参看配套教材《数据结构习题精析与考研辅导》。
由于作者的水平有限，可能在某些方面考虑不周，书中难免存在疏漏或错误，恳请读者提出宝贵意见。
作者邮箱：yinrk@tsinghua.edu.cn或yinrk@sohu.com。
编 者
2011年4月于清华园荷清苑
本书已由机械工业出版社出版，ISBN 978-7-111-32283-2，定价：45.00元。——编辑注
计算机\数据结构
(1) 采用“工科”思维，启发学生掌握“化复杂为简单”的方式，从问题入手，通过“问题/子问题”分解，寻找解决方案；
(2) 对基本知识点讲深讲透，通过多种应用举例，让学生了解不同问题需要采取什么方法来应对；
(3) 通过大量习题，从不同视点不同层面训练学生，见多才能识广，才能培养出联想能力，提高分析问题、解决问题的能力；
(4) 配合辅助教材《数据结构习题精析与考研辅导》，提供了多达600多题的参考答案和解析，并就关键点进行点拨；另外，提供了多套模拟题。
出版者的话
编委会
丛书序言
前言
教学安排建议
第1章 绪论1
1.1 数据结构的概念及分类1
1.1.1 为什么要学习数据结构1
1.1.2 与数据结构相关的基本术语2
1.1.3 数据结构的分类4
1.1.4 数据结构的存储结构6
1.1.5 定义在数据结构上的操作6
1.2 使用C语言描述数据结构6
1.2.1 数据类型7
1.2.2 算法的控制结构7
1.2.3 算法的函数结构8
1.2.4 动态存储分配10
1.2.5 逻辑和关系运算的约定11
1.2.6 输入与输出11
1.3 算法和算法设计12
1.3.1 算法的定义和特性12
1.3.2 算法的设计步骤12
1.3.3 算法设计的基本方法13
1.4 算法分析与度量16
1.4.1 算法的评价标准16
1.4.2 算法的时间和空间复杂度度量16
1.4.3 算法的渐近分析19
小结21
习题21
第2章 线性表23
2.1 线性表的定义及操作23
2.1.1 线性表的定义和特点23
2.1.2 线性表的主要操作24
2.2 顺序表25
2.2.1 顺序表的定义和特点25
2.2.2 顺序表的结构定义25
2.2.3 顺序表主要操作的实现26
2.2.4 顺序表主要操作的性能分析28
2.2.5 顺序表的应用举例29
2.3 单链表30
2.3.1 单链表的定义和特点30
2.3.2 单链表的结构定义31
2.3.3 单链表中的插入与删除31
2.3.4 带头结点的单链表33
2.3.5 单链表主要操作的性能分析35
2.3.6 单链表的顺序访问与尾递归36
2.3.7 单链表的应用举例38
2.4 顺序表与线性链表的比较40
2.5 线性链表的其他变形41
2.5.1 循环链表41
2.5.2 双向链表44
2.5.3 静态链表46
2.6 线性表的应用：字符串47
2.6.1 字符串的概念47
2.6.2 字符串的初始化和赋值48
2.6.3 C语言中有关字符串的库函数48
2.6.4 自定义字符串的存储表示50
2.7 单链表的应用：一元多项式及其运算53
2.7.1 一元多项式的表示53
2.7.2 多项式的结构定义54
2.7.3 多项式的加法55
2.7.4 多项式的乘法56
小结58
习题58
第3章 栈、队列和数组61
3.1 栈61
3.1.1 栈的概念61
3.1.2 顺序栈62
3.1.3 链式栈66
3.1.4 栈的混洗68
3.2 队列69
3.2.1 队列的概念69
3.2.2 循环队列70
3.2.3 链式队列73
3.3 栈的应用75
3.3.1 数制转换75
3.3.2 括号匹配75
3.3.3 表达式的计算与优先级处理76
3.3.4 栈与递归的实现80
3.4 队列的应用83
3.4.1 打印杨辉三角形与逐行处理83
3.4.2 电路布线与两点间的最短路径84
3.5 数组86
3.5.1 一维数组86
3.5.2 多维数组87
3.5.3 数组的应用举例89
3.6 在算法设计中使用递归89
3.6.1 汉诺塔问题与分治法90
3.6.2 迷宫问题与回溯法92
3.6.3 计算组合数与动态规划95
3.7 特殊矩阵96
3.7.1 对称矩阵的压缩存储96
3.7.2 三对角线矩阵的压缩存储97
3.7.3 稀疏矩阵的压缩存储98
3.8 双端队列100
3.8.1 双端队列的概念100
3.8.2 双端队列的主要操作101
3.8.3 双端队列的顺序存储表示101
3.8.4 双端队列的链接存储表示103
小结103
习题104
第4章 树与二叉树108
4.1 树的基本概念108
4.1.1 树的定义和术语108
4.1.2 树的基本操作110
4.2 二叉树111
4.2.1 二叉树的概念111
4.2.2 二叉树的性质112
4.2.3 二叉树的主要操作113
4.3 二叉树的存储表示114
4.3.1 二叉树的顺序存储表示114
4.3.2 二叉树的链表存储表示115
4.4 二叉树的遍历116
4.4.1 二叉树遍历的递归算法116
4.4.2 递归遍历算法的应用举例117
4.4.3 二叉树遍历的非递归算法120
4.4.4 非递归遍历算法的应用举例123
4.4.5 二叉树的计数125
4.5 线索二叉树127
4.5.1 线索二叉树的概念127
4.5.2 线索二叉树的种类128
4.5.3 中序线索二叉树的建立和遍历129
4.5.4 前序与后序线索二叉树131
4.6 树与森林132
4.6.1 树的存储表示132
4.6.2 森林与二叉树的转换134
4.6.3 树与森林的深度优先遍历135
4.6.4 树与森林的广度优先遍历137
4.6.5 树遍历算法的应用举例138
4.7 二叉树的应用：二叉排序树138
4.7.1 二叉排序树的概念138
4.7.2 二叉排序树的查找139
4.7.3 二叉排序树的插入140
4.7.4 二叉排序树的删除141
4.7.5 二叉排序树的性能分析142
4.8 二叉树的应用：平衡二叉树144
4.8.1 平衡二叉树的概念144
4.8.2 平衡化旋转144
4.8.3 平衡二叉树的插入146
4.8.4 平衡二叉树的删除147
4.8.5 平衡二叉树的性能分析149
4.9 二叉树的应用：Huffman树150
4.9.1 带权路径长度的概念150
4.9.2 Huffman树与Huffman算法151
4.9.3 Huffman树的应用：最优判定树153
4.9.4 Huffman树的应用：Huffman编码154
4.10 二叉树的应用：堆155
4.10.1 小根堆和大根堆155
4.10.2 堆的建立156
4.10.3 堆的插入158
4.10.4 堆的删除158
4.11 树的应用：八皇后问题与树的剪枝159
4.11.1 八皇后问题的提出159
4.11.2 八皇后问题的状态树160
4.11.3 八皇后问题算法161
小结162
习题162
第5章 图168
5.1 图的基本概念168
5.1.1 与图有关的概念168
5.1.2 图的基本操作170
5.2 图的存储结构171
5.2.1 图的邻接矩阵表示171
5.2.2 图的邻接表表示175
5.2.3 邻接矩阵表示与邻接表表示
的比较178
5.2.4 图的邻接多重表表示179
5.3 图的遍历180
5.3.1 深度优先搜索181
5.3.2 广度优先搜索182
5.3.3 连通分量183
5.3.4 重连通图184
5.3.5 欧拉回路与一笔画问题186
5.3.6 有向图的强连通分量187
5.4 最小生成树188
5.4.1 最小生成树求解和贪婪法188
5.4.2 Kruskal算法190
5.4.3 Prim算法193
5.5 最短路径194
5.5.1 非负权重的单源最短路径194
5.5.2 所有顶点之间的最短路径197
5.5.3 无权重的最短路径199
5.6 用顶点表示活动的网络（AOV网络）200
5.7 用边表示活动的网络（AOE网络）204
小结207
习题208
第6章 查找212
6.1 查找的基本概念与性能分析212
6.1.1 查找的概念212
6.1.2 查找算法的性能分析213
6.2 顺序查找法213
6.2.1 顺序表上的顺序查找算法213
6.2.2 线性链表上的顺序查找算法216
6.3 折半查找法216
6.3.1 一般的折半查找法216
6.3.2 拟最优查找树：折半查找的
改进方法219
6.3.3 斐波那契查找：折半查找的
变形222
6.3.4 插值查找：折半查找的变形223
6.4 B树224
6.4.1 索引顺序表与分块查找224
6.4.2 多级索引结构与m叉查找树225
6.4.3 B树的概念226
6.4.4 B树上的查找227
6.4.5 B树上的插入228
6.4.6 B树上的删除229
6.4.7 B+树231
6.5 散列表及其查找233
6.5.1 散列的概念233
6.5.2 常见的散列函数234
6.5.3 解决冲突的开地址法236
6.5.4 解决冲突的链地址法242
6.5.5 散列法分析244
小结245
习题245
第7章 排序250
7.1 排序的概念与算法性能250
7.1.1 排序的概念250
7.1.2 排序算法的性能251
7.1.3 数据表和静态链表的结构定义251
7.2 几种简单的排序方法253
7.2.1 直接插入排序253
7.2.2 基于链表的直接插入排序254
7.2.3 折半插入排序255
7.2.4 起泡排序256
7.2.5 简单选择排序258
7.3 希尔排序259
7.3.1 希尔排序的设计思路259
7.3.2 希尔排序的算法实现260
7.4 快速排序261
7.4.1 快速排序的设计思路261
7.4.2 快速排序的算法描述262
7.4.3 快速排序的算法分析262
7.4.4 快速排序的改进算法263
7.5 堆排序264
7.5.1 大根堆264
7.5.2 堆排序的算法265
7.5.3 堆排序的算法分析267
7.6 归并排序267
7.6.1 两路归并267
7.6.2 递归的归并排序算法268
7.6.3 迭代的归并排序算法269
7.6.4 基于链表的归并排序算法271
7.7 基数排序272
7.7.1 基数排序的概念272
7.7.2 MSD基数排序273
7.7.3 LSD基数排序274
7.8 内排序算法的分析与比较276
7.8.1 排序方法的下界276
7.8.2 各种内排序方法的比较279
7.8.3 链表排序结果的重排280
小结282
习题283
附录一 2009～2011年全国考研计算机学科联考专业基础综合考试数据结构部分试题解析288
附录二 大作业要求及样例303
参考文献308
