编辑推荐
遵循《全国硕士研究生入学考试计算机专业基础综合考试大纲》和《高等学校计算机专业公共核心知识体系与课程》的要求,全面覆盖数据结构课程的基本知识点。对于每一个基本知识点,按照“知识点复习―选择题―判断题―简答题―算法题”的顺序,归纳了该知识点的要点和容易忽略的细节。作者从1978年学习数据结构,1984年进入数据结构教学岗位,1996年开始担任数据结构考研、考博的命题教师,近40年来积累了丰富的教学经验,并融入本书中。总习题量增加到2840题,囊括了历年考研和入职考试的精华,从不同角度复习各知识点基本概念。每题的出题和解析都经过仔细考虑,没有雷同的情况。算法题增加到700多道。所有算法都采用C语言描述,并在VC 6.0的环境下调试通过。为力求简单可读,引入了“引用参数”的概念,对于大多数读者没有语言的障碍。
作者简介
殷人昆,清华大学计算机系教授,1985年赴日本国东京理科大学做访问学者,研究方向为软件工程过程的质量管理和软件产品的质量评价。主要教学工作为计算机系大学本科“数据结构”、“软件工程”和研究生“软件工程设计与技术”、“软件项目管理”课程负责人,主持教育部-微软精品课程“数据结构”的建设。曾与人合作或单独编写和出版教材20余部,其中,《数据结构》教材被评为教育部普通高等教育“十一五”国家规划教材,并于2005年获“北京市精品教材”。曾在核心刊物和专业会议发表论文多篇,并参加或主持多项科研项目。
内容简介
本书是清华大学出版社出版的《数据结构(C语言版)》(第2版)的配套教材,对“数据结构”课程常用习题进行了解析,对许多不易通过自学理解的概念和知识做了深入讲解,并针对“数据结构”课程的学习给出了指导性建议。本书覆盖了数据结构与算法的主要知识点,共分为8章,包括数据结构绪论,线性表,栈和队列,多维数组、字符串与广义表,树与二叉树,图,查找以及排序。每章划分为多个知识点,首先给出知识点提要,归纳有关要点和容易忽略的细节;然后给出选择题、判断题、简答题和算法题4种题型的典型习题。全书的题量为2840题。 本书既可以作为大学计算机科学与技术、软件工程等专业的本科生学习“数据结构”课程的辅助教材,也可供考研人员自学参考。
目录
第1章 数据结构绪论
1.1 数据结构的概念及分类
1.2 算法设计与算法分析
第2章 线性表
2.1 线性表的概念
2.2 顺序表
2.3 线性表的链接存储表示
2.4 两种存储表示的比较
2.5 线性表的应用
第3章 栈和队列
3.1 栈
3.2 队列
3.3 栈与队列的应用
3.4 栈与递归
第4章 多维数组、字符串与广义表
4.1 多维数组
4.2 特殊矩阵与稀疏矩阵
4.3 字符串
4.4 广义表
第5章 树与二叉树
5.1 树的基本概念
5.2 二叉树及其存储表示
5.3 二叉树的遍历
5.4 线索二叉树
5.5 树与森林的存储与遍历
5.6 Huffman树
5.7 堆
5.8 并查集
第6章 图
6.1 图的基本概念
6.2 图的存储表示
6.3 图的遍历
6.4 最小生成树
6.5 最短路径
6.6 拓扑排序和关键路径
第7章 查找
7.1 查找的概念与简单查找方法
7.2 二叉查找树
7.3 AVL树
7.4 B树与B 树
7.5 散列法
第8章 排序
8.1 排序的概念
8.2 插入排序
8.3 交换排序
8.4 选择排序
8.5 归并排序
8.6 桶排序
8.7 内排序方法的比较
8.8 外排序
参考文献
前言
本书是《数据结构精讲与习题详解》的第2版,与前一版相比,它做了如下改变:
(1) 对第1版参考答案中存在的代码错误和低效之处进行了全面修改。
(2) 局部改变了第1版的章节编排。将“树与二叉树”与“树的应用”合并为一章,将“内排序”与“外排序”合并为一章,将“二叉查找(排序)树”与“AVL树”调整到第7章“查找”中。
(3) 题量从1250 题增加到2840题,同时将“疑难点辨析”改为“判断题”,部分调整到“简答题”中。这是考虑到“判断题”更能够激发读者的深度思考。
(4) “知识点提要”部分没有如同主教材那样系统、详细地讨论有关知识点的细节,而是从复习的角度归纳了知识点的要点和容易忽略的细节。因此,如果要系统地学习数据结构的主要概念,还是应当以主教材为主,本书为辅,配合学习。
(5) 由于篇幅原因,“选择题”和“判断题”部分仅给出答案,删去了解析。因此,这两部分对于读者来说更需要“研读”而不应“走马观花”,不但要知其然,而且要知其所以然。对于“选择题”,首先要了解相关知识点的主要概念,如果有把握,可直接确定正确的选项;如果没有把握,可采用排除法,利用自己掌握的知识,排除那些不合理的选项。对于“判断题”,直接与主教材的内容有关,如果没有把握,最好先去温习主教材,但这要求选好主教材。
(6) 本书的“简答题”部分相当精彩,如果仔细研读之后必有大的收获。其内容包括简单的问答题、画图题、计算题、证明题。这些题直接与相关的数据结构和算法有关,通过这些题目,可加深对各种数据结构特点的理解,搞清容易忽略或容易混淆的概念,且对某些较复杂的算法,可以通过实例理顺其中的细节。
(7) 本书的“算法题”有700多题,一部分来自国内外的经典数据结构教材和题典,一部分来自各大学、各大公司的入学考试和入职面试,涵盖了各种数据结构和算法的应用,而且都已用Visual C 6.0调试通过。研读这些习题,对于提高读者分析问题和解决问题的能力很有帮助。希望读者每做完一道算法题都能够进行小结,把这类题的解题思路和辅助数据结构的应用牢记于心。
(8) 细节决定成败。对“数据结构”课程所讲的知识是否掌握得好,关键在于对细节是否把握得好。对课程的每一个知识点,通过练习从不同侧面理解其精髓,使得以后不论从什么角度,用什么表述方式提出问题,都能想到使用什么方法,利用什么数据结构来解决,这样才能够为以后的科研、开发打下坚实的基础。
本书实际上是一个题库,不同程度的读者可选择力所能及的题目来做。有些简答题和算法题比较难,不是考研或参加入职考试的读者可以不看它们。本书不设难度标识,无论多难的题目,只要看过参考答案,都能了解其解题思路。为此,本书在算法描述上尽可能做到简单、清晰、易读。
本书覆盖了数据结构与算法的主要知识点,但对于某些没有普遍列入数据结构教材的知识点,如红黑树、数字查找树、伸展树、跳表、左斜堆、B树、动态散列、k\|d树等,都没有涉及。这样取舍对于多数院校已经足够了。本书既可以作为大学计算机科学与技术或软件工程专业学习“数据结构”课程的辅助教材,也可以作为考研复习的辅导教材。
本书得到清华大学2015年度本科精品教材项目资助。在成书过程中得到清华大学计算机系和清华大学出版社相关老师的鼓励和支持,也得到家人的理解和照顾,本人在此一并表示感谢。限于本人的学识和能力,书中不可避免地还会有一些错误和欠缺,诚请读者多提宝贵意见。我的联系地址是yinrk@tsinghua.edu.cn或yinrk@sohu.com。