前言
数据结构研究计算机系统内表示、组织、处理和存储数据的方式,算法则着重于程序处理流程的优化,二者相辅相成,共同提高程序的时间与空间效率。数据结构课程已经成为高等学校计算机科学与技术、信息管理与信息系统、软件工程等专业的核心课程,并有越来越多的专业技术人员对数据结构知识提出了更高的需求。
本书共10章和两个附录。第1章绪论,主要介绍学习数据结构的意义、数据结构的基本概念,算法中的抽象数据类型及其在C++语言中的表示与算法实现的原则,算法的定义、特征及效率分析。第2章线性表,主要介绍线性表的基本概念和逻辑结构,线性表的顺序存储结构和链表的存储结构,顺序表、单链表、双向链表及循环链表的相关操作与C++算法实现。第3章栈与队列,主要介绍栈和队列的基本概念、存储结构和基本操作,以及对应的C++算法实现,并以算术表达式转化和求值为例介绍栈和队列的应用。第4章串,主要介绍串的定义、特点、存储结构和基本的串处理操作,以及对应的C++算法实现。第5章数组和广义表,主要介绍数组和广义表的定义、特点、存储结构与C++算法实现。第6章树和二叉树,主要介绍二叉树的基本概念、存储结构及其操作,并研究树和森林、二叉树之间的相互转换方法，以及树的一个重要应用——最优树和哈夫曼编码方法。第7章图,主要介绍图的基本概念,图的邻接矩阵、邻接表、十字链表、邻接多重表等存储结构,图的深度优先遍历与广度优先遍历算法、最小生成树算法以及其他应用算法。第8章查找,主要介绍查找的基本概念,静态查找表、动态查找表及哈希表的表示方法,顺序查找、折半查找、分块查找、二叉排序树、二叉平衡树、B树、哈希表等查找方法以及C++算法实现与算法分析。第9章排序,主要介绍排序的基本概念,插入排序、希尔排序、快速排序、直接选择排序、堆排序、归并排序、基数排序的方法与C++算法实现,以及各种排序算法的比较分析。第10章是一个综合案例,通过实际生产问题的求解过程，深化读者对数据结构的理解，提高读者的综合应用能力,展示数据结构与算法的魅力。附录A给出本书中算法实现时的文件夹结构,附录B给出本书中算法实现时C++类中间的UML关系图。每章习题及其参考答案可以通过扫描每章后所附的二维码得到。
本书的主要特点如下。
(1) 参照数据结构普遍的分类规范进行内容编排,涵盖了一般需要掌握的所有基础数据结构与算法,并对算法的效率进行了对比分析。
(2) 实例引入和图文讲解展现了将实际问题转换为抽象的数据结构的方法，并设计了相应的算法。
(3) 基于C++语言面向对象的概念和对象类设计原则进行算法实现,体现了面向对象的三大特点——封装、继承和多态,利用封装实现其独立的原理特点,利用继承实现各个数据结构之间的关联,利用多态展现数据结构在实际问题中的调用方法。附录B中涵盖了各个C++类对应的UML类图,从中可清晰地看到每个类中的属性与方法,以及各个类之间的关系。
(4) 为了满足教学过程中的上机练习需求,书中所有的算法实现均可以通过直接编译运行,并附上相应的算例和运行结果,便于读者对比实现。同时，采用.h头文件与.cpp定义文件分离的方式进行算法实现,避免对数据结构重复定义,引用位置也在附录A的文件夹结构中详细展示。
(5) 建议将书中的数据结构进行自主实现,但同时本书也介绍了几种基础数据结构对应的标准模板库(STL)里的容器,若读者时间不足,可以在了解后直接使用现有组件。
(6) 每一章最后通过扫描二维码都有匹配的思考和练习题,包含概念理解、算法拓展、解决实际问题等题型,同时参考答案里附上了每个问题的解题思路、可执行的C++代码及运行结果供读者参考。
本书内容丰富、结构合理、实用性强,配有电子课件、完整的程序源代码、习题参考答案等教学资源。
本书由张千帆任主编,莫嘉铭、王翀任副主编。本书的编写得到了漆鹏飞、吴庆华的支持,并参考了同行专家的著作和成果,在此向他们表示衷心的感谢！
由于作者水平有限,书中难免有不当之处,敬请专家和读者批评指正。
张千帆2020年5月
书单推荐
