基本信息
- 作者： 孙涵 黄元元 高航 秦小麟
- 丛书名： 高等学校计算机专业系列教材
- 出版社：机械工业出版社
- ISBN：9787111648208
- 上架时间：2020-3-21
- 出版日期：2020 年3月
- 开本：16开
- 页码：188
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 数据结构
教材 > 计算机教材 > 本科/研究生 > 公共课及公共选修课
内容简介
目录
前言
第1章 概论 1
1.1 引言 1
1.2 数据结构相关概念及术语 1
1.3 抽象数据类型的表示与实现 3
1.4 算法与算法分析 6
1.4.1 算法 6
1.4.2 算法分析与度量 8
1.5 小结 10
1.6 练习 10
第2章 线性表 11
2.1 引言 11
2.2 线性表的抽象数据类型 11
2.3 线性表的顺序表示与实现 15
2.3.1 顺序表的定义和特点 15
2.3.2 顺序表的存储结构 15
2.3.3 顺序表基本操作的实现与性能分析 16
2.4 线性表的链式表示与实现 19
2.4.1 单链表 20
2.4.2 其他形式的链表 24
第1章 概论 1
1.1 引言 1
1.2 数据结构相关概念及术语 1
1.3 抽象数据类型的表示与实现 3
1.4 算法与算法分析 6
1.4.1 算法 6
1.4.2 算法分析与度量 8
1.5 小结 10
1.6 练习 10
第2章 线性表 11
2.1 引言 11
2.2 线性表的抽象数据类型 11
2.3 线性表的顺序表示与实现 15
2.3.1 顺序表的定义和特点 15
2.3.2 顺序表的存储结构 15
2.3.3 顺序表基本操作的实现与性能分析 16
2.4 线性表的链式表示与实现 19
2.4.1 单链表 20
2.4.2 其他形式的链表 24
前言
“数据结构”是计算机类专业的基础课程，也是相关理工类专业的热门选修课程。本书是为该课程编写的教材，适合计算机类专业和相关理工类专业的本科生学习。
本书主要介绍如何合理地组织数据、有效地存储和处理数据、正确地设计算法以及对算法的复杂度进行分析和评价。通过深入理解各种基本数据结构的逻辑关系、物理存储和基本操作，初步建立数据结构设计、实现和运用的概念。同时，结合各种典型案例，讨论不同数据结构的特点、适用范围以及基本算法复杂度的分析方法，为后续的专业课程学习提供必要的基础知识。
本书的学习目标如下。
目标1：掌握线性表、栈和队列、数组和广义表、树和二叉树、图等各种基本数据结构的逻辑表达、物理存储和基本操作；掌握查找、排序的经典算法。
目标2：能够针对具体应用问题，根据问题的约束条件分析各种可选方案在数据存储、算法效率上的利弊，并选择恰当的数据结构、存储表示和与之对应的操作方法。
目标3：能够结合具体应用案例，合理选择和改进经典的数据结构，使之针对具体应用能够有效地存储和处理数据，能够在此基础上正确地设计算法，并对算法进行有效的分析和评价。
本书共分为8章。第1章主要介绍数据结构相关的概念及术语，以及算法的定义、特性和算法设计的目标。第2～4章主要讨论各种基本结构的抽象数据类型、顺序和链式表示与实现，以及相关的应用。第5章和第6章在讨论树和图的抽象数据类型、顺序和链式表示与实现的基础上，重点讨论树和图的遍历方法以及基于此的典型应用。第7章和第8章分别讨论查找和排序的经典算法与改进策略。
对于广大读者来说，学习数据结构课程的关键是把握两条主线。
一条主线是如何理解和实现物理世界中的各种联系在信息世界中的逻辑表示。物理世界中的万般联系都是形象而具体的，需要通过抽象建模抓住这些联系的本质，即线性、树形或者图状结构，从而将其转换为信息世界中的逻辑表示。例如：生活中的各种排队可以抽象成线性结构中的队列，家族谱可以映射为树形结构，专业课程的先修/后修关系可以构成有向的图结构。抽象建模与表示能力是工科类专业学生必须具备的基本能力。不论是不是计算机类专业的学生，在学习这门课程时，都必须牢牢把握这条主线。
另一条主线是如何在计算机中实现数据结构的存储和操作。存储的方式主要分为顺序存储和链式存储两大类。基本操作一般包括初始化及销毁操作、访问型操作和加工型操作三大类。这三类操作在两种不同存储模式下的算法的效率是有差异的，需要进行比较分析，总结各自的优势和不足，从而针对具体的现实问题，选择恰当的存储方式来保证操作执行的效率。在比较分析基础上得到有效结论是这条主线中的能力训练要求。
此外，算法设计与优化也是值得关注的问题，本书中的查找和排序部分将展示算法设计与优化的思路。例如，排序算法如何从时间复杂度O(n2)的经典算法开始，通过对恰当结构的引入将算法时间复杂度降到O(nlogn)；查找算法如何从时间复杂度O(n)的穷举算法开始，通过对数据的排序约束和树形结构的引入，将时间复杂度降到O(logn)，甚至在一些特殊规则的约束下能够接近O(1)。我们不仅要掌握经典算法本身，更要关注算法优化的策略和方向，以便在解决实际问题时能够设计出高效的算法。
最后，从不同学习者的角度来讨论一下如何学习本门课程。
对于计算机类专业的学生，本书所涉及的内容均需掌握。在此基础上，学生需要大量的训练，以具备抽象建模能力，能够就实际问题选择或设计恰当的数据结构。此外，在编程实现过程中，能够基于问题的约束，在比较、分析的基础上选择恰当的存储方式和算法的实现方式，能够对算法的时间和空间复杂度进行合理的分析，能够对算法的改进和优化有恰当的思路，从而为实际问题提供高效的解决方案。
对于其他理工类专业的学生，希望通过本门课程的学习达成两点目标：一是具备抽象建模能力，能够对物理世界中的问题描述进行抽象建模，从而在信息世界里进行合理表达；二是具备算法选择能力，能够根据输入数据的表现形式、数据结构的存储方式和基于此的算法效率特征，选择相应的数据结构和算法来高效地解决实际问题。
本书在构思和准备过程中参考了国内外相关的数据结构教材，特别是严蔚敏、殷人昆、陈越、邓俊辉等老师编写的教材，这些经典教材的内容、写法给了作者很多启发。在本书的编写过程中，南京航空航天大学的秦小麟老师给予了很多指导意见。在此一并向这些老师表示感谢。本书第1～3章由孙涵编写，第4章和第8章由高航老师编写，第5～7章由黄元元老师编写，全书由孙涵负责统稿和审定。
尽管本书是作者多年教学经验的总结，但限于作者的学识，书中难免有疏漏与不足之处，敬请各位同行与读者批评指正，以利于我们不断提升教学水平、丰富课程内容。
孙涵
南京航空航天大学计算机科学与技术学院
2019年12月
本书主要介绍如何合理地组织数据、有效地存储和处理数据、正确地设计算法以及对算法的复杂度进行分析和评价。通过深入理解各种基本数据结构的逻辑关系、物理存储和基本操作，初步建立数据结构设计、实现和运用的概念。同时，结合各种典型案例，讨论不同数据结构的特点、适用范围以及基本算法复杂度的分析方法，为后续的专业课程学习提供必要的基础知识。
本书的学习目标如下。
目标1：掌握线性表、栈和队列、数组和广义表、树和二叉树、图等各种基本数据结构的逻辑表达、物理存储和基本操作；掌握查找、排序的经典算法。
目标2：能够针对具体应用问题，根据问题的约束条件分析各种可选方案在数据存储、算法效率上的利弊，并选择恰当的数据结构、存储表示和与之对应的操作方法。
目标3：能够结合具体应用案例，合理选择和改进经典的数据结构，使之针对具体应用能够有效地存储和处理数据，能够在此基础上正确地设计算法，并对算法进行有效的分析和评价。
本书共分为8章。第1章主要介绍数据结构相关的概念及术语，以及算法的定义、特性和算法设计的目标。第2～4章主要讨论各种基本结构的抽象数据类型、顺序和链式表示与实现，以及相关的应用。第5章和第6章在讨论树和图的抽象数据类型、顺序和链式表示与实现的基础上，重点讨论树和图的遍历方法以及基于此的典型应用。第7章和第8章分别讨论查找和排序的经典算法与改进策略。
对于广大读者来说，学习数据结构课程的关键是把握两条主线。
一条主线是如何理解和实现物理世界中的各种联系在信息世界中的逻辑表示。物理世界中的万般联系都是形象而具体的，需要通过抽象建模抓住这些联系的本质，即线性、树形或者图状结构，从而将其转换为信息世界中的逻辑表示。例如：生活中的各种排队可以抽象成线性结构中的队列，家族谱可以映射为树形结构，专业课程的先修/后修关系可以构成有向的图结构。抽象建模与表示能力是工科类专业学生必须具备的基本能力。不论是不是计算机类专业的学生，在学习这门课程时，都必须牢牢把握这条主线。
另一条主线是如何在计算机中实现数据结构的存储和操作。存储的方式主要分为顺序存储和链式存储两大类。基本操作一般包括初始化及销毁操作、访问型操作和加工型操作三大类。这三类操作在两种不同存储模式下的算法的效率是有差异的，需要进行比较分析，总结各自的优势和不足，从而针对具体的现实问题，选择恰当的存储方式来保证操作执行的效率。在比较分析基础上得到有效结论是这条主线中的能力训练要求。
此外，算法设计与优化也是值得关注的问题，本书中的查找和排序部分将展示算法设计与优化的思路。例如，排序算法如何从时间复杂度O(n2)的经典算法开始，通过对恰当结构的引入将算法时间复杂度降到O(nlogn)；查找算法如何从时间复杂度O(n)的穷举算法开始，通过对数据的排序约束和树形结构的引入，将时间复杂度降到O(logn)，甚至在一些特殊规则的约束下能够接近O(1)。我们不仅要掌握经典算法本身，更要关注算法优化的策略和方向，以便在解决实际问题时能够设计出高效的算法。
最后，从不同学习者的角度来讨论一下如何学习本门课程。
对于计算机类专业的学生，本书所涉及的内容均需掌握。在此基础上，学生需要大量的训练，以具备抽象建模能力，能够就实际问题选择或设计恰当的数据结构。此外，在编程实现过程中，能够基于问题的约束，在比较、分析的基础上选择恰当的存储方式和算法的实现方式，能够对算法的时间和空间复杂度进行合理的分析，能够对算法的改进和优化有恰当的思路，从而为实际问题提供高效的解决方案。
对于其他理工类专业的学生，希望通过本门课程的学习达成两点目标：一是具备抽象建模能力，能够对物理世界中的问题描述进行抽象建模，从而在信息世界里进行合理表达；二是具备算法选择能力，能够根据输入数据的表现形式、数据结构的存储方式和基于此的算法效率特征，选择相应的数据结构和算法来高效地解决实际问题。
本书在构思和准备过程中参考了国内外相关的数据结构教材，特别是严蔚敏、殷人昆、陈越、邓俊辉等老师编写的教材，这些经典教材的内容、写法给了作者很多启发。在本书的编写过程中，南京航空航天大学的秦小麟老师给予了很多指导意见。在此一并向这些老师表示感谢。本书第1～3章由孙涵编写，第4章和第8章由高航老师编写，第5～7章由黄元元老师编写，全书由孙涵负责统稿和审定。
尽管本书是作者多年教学经验的总结，但限于作者的学识，书中难免有疏漏与不足之处，敬请各位同行与读者批评指正，以利于我们不断提升教学水平、丰富课程内容。
孙涵
南京航空航天大学计算机科学与技术学院
2019年12月
媒体评论
数据结构是计算机科学的核心内容之一，也是计算机及相关专业学生重要的基础课程。对于初学者而言，数据结构课程的抽象性强、对问题求解能力的要求高，学习难度比较大。本书基于作者多年来的教学经验编写而成，课程目标明确、主线清晰、善用案例深入浅出地介绍抽象的知识，有利于学生更好地实现和应用数据结构来解决实际问题。
本书特点：
本书有两条清晰的主线，一条主线是帮助读者理解和实现物理世界里各种联系在信息世界中的逻辑表示， 另一条主线是使读者理解如何在计算机中实现数据结构的存储和操作。读者可通过这两条主线更加透彻地理解数据结构的本质和内容。
本书通过案例引入和深入浅出的介绍，能使读者理解如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的复杂度进行分析和评价。同时，通过深入理解各种基本数据结构的逻辑关系、物理存储和基本操作，初步建立数据结构设计、实现和运用的概念。
本书包含“数据结构”课程的经典内容，能同时满足计算机专业和非计算机专业对课程的不同要求，并注重培养读者从实际出发、应用数据结构解决问题的能力。
本书特点：
本书有两条清晰的主线，一条主线是帮助读者理解和实现物理世界里各种联系在信息世界中的逻辑表示， 另一条主线是使读者理解如何在计算机中实现数据结构的存储和操作。读者可通过这两条主线更加透彻地理解数据结构的本质和内容。
本书通过案例引入和深入浅出的介绍，能使读者理解如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的复杂度进行分析和评价。同时，通过深入理解各种基本数据结构的逻辑关系、物理存储和基本操作，初步建立数据结构设计、实现和运用的概念。
本书包含“数据结构”课程的经典内容，能同时满足计算机专业和非计算机专业对课程的不同要求，并注重培养读者从实际出发、应用数据结构解决问题的能力。
