读书笔记摘抄新闻资讯
数据结构（第3版）
《数据结构（第3版）》是由刘大有、杨博、黄晶、朱允刚、谷方明、姜丽编着，高等教育出版社2017年出版的“十二五”普通高等教育本科国家级规划教材、面向21世纪课程教材与 “十一五”国家级规划教材。该教材可作为高等院校计算机科学与技术、软体工程及相关专业的教材和教学参考书，也可供相关专业的工程技术人员参考使用。
该教材共8章，系统介绍了数据结构的概念、原理、技术和套用实例，主要包括数学準备、绪论、基本数据结构、排序与查找等内容。
基本介绍
- 书名：数据结构（第3版）
- 作者：刘大有、杨博、黄晶、朱允刚、谷方明、姜丽
- ISBN：978-7-04-046787-1
- 类别：“十二五”普通高等教育本科国家级规划教材等
- 页数：342页
- 出版社：高等教育出版社
- 出版时间：2017年3月6日
- 装帧：平装
- 开本：16开
- 版面字数：500千字
成书过程
修订情况
该教材修订部分如下：
1. 精简部分内容。从2010年《数据结构（第2版）》（以下简称“第2版”）中，删去了“递归”“记忆体管理”“档案”和“随机数”4章和附录等内容，对“绪论”“线性表堆叠和伫列”“数组和字元串”“树”“图排序”和“查找”等各章进行了改写。
2.算法分析或其关键部分的正确性证明是读者学习数据结枃需要掌握的技巧，为此增加了新的一章“数学準备”。
3.在第6章“图”中新增了6.6.4节“满足约东的最短路径”，给出了其ADL描述和实例分析。
4.在6.7.2节中增加了 Kruskal算法的ADL描述、时间複杂性分析和关键部分的正确性证明。
5.增加了背景历史介绍，以及推荐读物与参考文献。
6.将第2版附录（算法的C++代码、习题答案或解题思路）与教师讲课视频、算法动画等以数位化资源存于网站。
2015年7月18日，《数据结构（第3版）》入选教育部“十二五”职业教育国家规划教材。
2017年3月6日，《数据结构（第3版）》由高等教育出版社出版。
人员分工
该教材编写分工为：刘大有对全书进行了架构设计和统稿，并撰写了第1章、第2章、前言和内容提要；杨博撰写了第6章；黄晶撰写了第3章及第4章；姜丽、朱允刚撰写了第8章；谷方明撰写了第5章；朱允刚撰写了第7章。吉林大学数据结构数学团队的部分教师指导学生对一些较难的算法设计实现了动画程式。朱允刚指导学生进行了该教材涉及的数位化资源的网上试验。团队成员虞强源、刘亚波、贾海洋、高滢和赖永等在撰写人二校的基础上又对书稿进行了校对，提出了修改建议。
内容简介
该教材系统介绍了数据结构的概念、原理、技术和套用实例，由纸介质部分和线上数位化资源部分所组成，纸介质部分主要包括数学準备、绪论、基本数据结构、排序与查找等内容，共8章。其中，第1章“数学準备”，系统地介绍与算法分析紧密相关的数学分支(生成函式与渐近表示除外，渐近表示在第2章简要介绍)的基本知识；第2章“绪论”，对算法描述语言ADL和算法书写规範、数据结构与算法的基本概念、算法分析基础等进行阐述；第3、4章介绍线性结构，系统地描述线性表、堆叠、伫列、数组和字元串等结构的存储、操作和套用；第5章“树与二叉树”，在详细刻画树和二叉树结构的基础上，从套用和数据结构扩展的视角渐进地讨论线索二叉树、哈夫曼树、并查集和决策树等内容；第6章“图”，系统地阐述图的基本概念、基本存储结构和基本算法，新增了带约束的最短路径算法和功能同Warshall算法但更高效的传递闭包求解算法，从套用的视角讨论複杂网路概念和基于图的典型信息搜寻算法；第7、8章“排序”与“查找”，深入讨论排序和查找的重要内容，并给出典型算法的描述、时间複杂性分析和相关算法的比较等。
教材目录
前辅文第1章 数学準备 1.1 数学归纳法 1.2 数、幂与对数 1.3 和与积 1.4 整数函式和初等数论 1.5 排列和阶乘 1.6 二项式係数 1.7 调和数 1.8 斐波那契数 小结 推荐读物与参考文献 习题 第2章 绪论 2.1 为什幺要学习数据结构 2.2 数据结构概念 2.2.1 数据的逻辑结构 2.2.2 数据的存储结构 2.2.3 对数据结构的操作 2.2.4 数据结构示例 2.3 算法 2.3.1 算法及其特性 2.3.2 算法的描述 2.3.3 算法的评价準则 2.4 算法的正确性证明 2.5 算法分析基础 2.5.1 算法时间複杂性的分析方法 2.5.2 複杂性函式的渐近表示 2.5.3 算法时间与空间分析 2.5.4 计算複杂性和算法的效率 小结 推荐读物与参考文献 习题 第3章 线性表、堆叠和伫列 3.1 线性表的定义和基本操作 3.2 线性表的顺序存储结构 3.3 线性表的连结存储结构 3.3.1 单鍊表 3.3.2 循环鍊表 3.3.3 双向鍊表 3.4 複杂性分析 3.5 堆叠 3.5.1 堆叠的定义和基本操作 3.5.2 顺序栈 3.5.3 链式栈 3.5.4 顺序栈与链式栈的比较 3.5.5 堆叠套用——括弧匹配 3.5.6 堆叠套用——递归 3.6 伫列 3.6.1 伫列的定义和基本操作 3.6.2 顺序伫列 3.6.3 链式伫列 小结 推荐读物与参考文献 习题 第4章 数组和字元串 4.1 数组 4.1.1 数组的存储和定址 4.1.2 一维数组的基本操作 4.2 矩阵 4.2.1 矩阵的数组表示 4.2.2 特殊矩阵的压缩存储 4.2.3 三元组表 4.2.4 十字鍊表 4.3 字元串 4.3.1 字元串的定义与存储 4.3.2 模式匹配算法 小结 推荐读物与参考文献 习题 第5章 树与二叉树 5.1 树的基本概念 5.1.1 树的定义 5.1.2 树的相关术语 5.1.3 树的表示 5.2 二叉树 5.2.1 二叉树定义和主要性质 5.2.2 二叉树顺序存储 5.2.3 二叉树连结存储 5.2.4 二叉树遍历 5.2.5 二叉树的其他操作 5.2.6 表达式树 5.3 线索二叉树 5.3.1 线索二叉树的概念 5.3.2 线索二叉树的操作 5.3.3 线索二叉树的进一步说明 5.4 压缩与哈夫曼树 5.4.1 档案编码 5.4.2 扩充二叉树 5.4.3 哈夫曼树和哈夫曼编码 5.5 树的存储和操作 5.5.1 树与二叉树的转换 5.5.2 树的存储结构 | 5.5.3 树和森林的遍历5.5.4 树的顺序表示 5.6 等价类与并查集 5.6.1 等价类 5.6.2 并查集的实现 5.7 分类与决策树 小结 推荐读物与参考文献 习题 第6章 图 6.1 图的基本概念 6.2 图的存储结构 6.2.1 邻接矩阵 6.2.2 邻接表 6.3 图的遍历算法 6.3.1 深度优先遍历 6.3.2 广度优先遍历 6.4 拓扑排序 6.5 关键路径 6.6 最短路径问题 6.6.1 无权最短路径问题 6.6.2 正权最短路径问题 6.6.3 每对顶点之间的最短路径 6.6.4 满足约束的最短路径 6.7 最小支撑树 6.7.1 普里姆算法 6.7.2 克鲁斯卡尔算法 6.8 图的套用 6.8.1 可及性及传递闭包算法 6.8.2 连通分量 6.8.3 图在网路分析和信息检索中的套用 小结 推荐读物与参考文献 习题 第7章 排序 7.1 排序问题的基本概念 7.2 插入排序 7.2.1 直接插入排序 7.2.2 Shell排序 7.3 交换排序 7.3.1 冒泡排序 7.3.2 快速排序 7.4 选择排序 7.4.1 直接选择排序 7.4.2 堆排序 7.5 合併排序 7.6 基于关键字比较的排序算法分析 7.6.1 平方阶排序算法及改进算法 7.6.2 线性对数阶排序算法 7.6.3 分治排序的一般方法 7.6.4 基于关键字比较的排序算法下界 7.7 分布排序 7.8 外排序 7.8.1 外存储器 7.8.2 磁带排序 7.8.3 磁碟排序 小结 推荐读物与参考文献 习题 第8章 查找 8.1 顺序查找 8.1.1 无序表的顺序查找 8.1.2 有序表的顺序查找 8.2 基于关键字比较的查找 8.2.1 对半查找 8.2.2 一致对半查找 8.2.3 斐波那契查找 8.2.4 插值查找 8.3 二叉查找树 8.3.1 基本概念和性质 8.3.2 查找、插入和删除 8.3.3 平均情况时间分析 8.4 最优二叉查找树 8.4.1 访问频率 8.4.2 最优二叉查找树 8.4.3 近似最优树的构造 8.5 高度平衡树 8.5.1 基本概念和性质 8.5.2 查找和插入操作 8.5.3 线性表的平衡树表示 8.5.4 删除操作 8.6 B树 8.6.1 多叉树 8.6.2 B树 8.7 数字查找 8.7.1 检索结构查找 8.7.2 数字树查找 8.8 散列 8.8.1 散列函式 8.8.2 冲突调节 8.8.3 删除 小结 推荐读物与参考文献 习题 |
教学资源
- 课程资源
《数据结构（第3版）》配套建设有数据结构数字课程，该数字课程包括电子教案、重要内容的讲解视频、较难算法的动画演示及示例原始码等辅助教学内容。
| 数字课程名称 | 出版社 | 出版时间 | 内容提供者 |
|---|---|---|---|
数据结构数字课程 | 高等教育出版社、高等教育电子音像出版社 | 2017年6月 | 刘大有 |
教材特色
该教材针对一些重要知识点，着力设计启发式教学内容。
①在选择与组织材料时，着力构造由多个求解同一问题的不同算法组成的“算法链条”。
②在对某算法进行具体描述之前，阐明该算法的关键思想，使部分读者能给出该算法的描绘（或较粗略的描绘）。
③对算法涉及的关键难点给出严格证明，这不仅能帮助读者透彻理解算法，而且能培养其严谨的科学精神。
④在每章的结尾处给出相关算法的比较，点明对其进一步改进或提升的思路。
⑤针对一些较难的算法，设计能帮助读者理解的动画程式。
⑥针对一些典型算法，选择与改写恰当的例子，进一步加深读者对算法机理和重要性的理解。
该教材每章之后都附加了精选的习题，并且对每道习题都列出了其重要属性及属性值，以使读者更好地了解和选择习题，具体包括：按难度将习题分为5个等级，5级是最高的难度级别；标注解答习题所需的大致平均时间；对用到高等数学知识的习题进行标记；对难度级别≥3的习题般给出了提示或分级提示（这些习题通常是有相当难度的题目，建议在读了第一级提示后仍然没有解题思路，才去读第二级提示，依此类推）。
该教材重视内容的严谨性，并试图使读者在这方面受到一定的训练。具体做法主要包括：对书中与某些算法之正确性有关的一些问题，以及与算法複杂性分析或数据结构概念相关的重要定理、引理等都给出了严格的数学证明；对主要概念都试图给出严格的形式化定义。
作者简介
刘大有，男，硕士，吉林大学计算机科学与技术学院教授，博士生导师。
杨博，男，硕士，吉林大学计算机科学与技术学院教授，吉林大学符号计算与知识工程教育部重点实验室主任。
黄晶，女，博士，吉林大学计算机科学与技术学院副教授。
朱允刚，男，博士，吉林大学计算机科学与技术学院副教授。
谷方明，男，博士，吉林大学计算机科学与技术学院讲师。
姜丽，女，博士，吉林大学计算机科学与技术学院讲师。