前言

随着高等教育的一系列改革，发展应用型本科教育已成为中国高等教育改革和发展的重要方向。“算法与数据结构”是计算机及相关专业的核心基础课程，涵盖计算机学科的算法设计、操作系统和编译原理等后续课程涉及的大部分算法的应用与实现。为了适应新形势的发展需要，作者根据计算机专业的相关培养计划和教学大纲，结合多年从事“算法与数据结构”课程的教学实践，在对教学内容进行改革的基础上确定了本书的编写大纲。在本书的编写中，既要符合应用型本科人才培养目标的要求，又要体现理论与应用相结合的原则。在教学中，既要讲授基本的理论知识，又要进行必要的采用相应数据结构和算法的软件开发技能的训练。通过本课程的学习，学生可以采用相应的数据结构与算法进行算法设计、算法应用和实际应用软件的开发，并提高复杂应用软件的开发能力，为成为计算机学科算法设计、软件开发和软件应用人才奠定基础。

本书的特点一是理论与实践应用相结合，不仅注重算法与数据结构理论知识的讲解，而且注重算法与数据结构在实际软件开发中的应用，强化实践与应用；二是实用性强，方便使用，每章都有大量数据结构的例题和应用实例，应用实例都有完整的C语言源程序，并在Visual C++环境下调试通过，方便读者学习和调试。

全书共9章，每章后均配有小结和习题，第1章是绪论，介绍数据结构的基本概念和术语、逻辑结构和存储结构、抽象数据类型以及算法的时间复杂度和空间复杂度。第2章是线性表，介绍线性表的抽象数据类型、线性表的顺序存储结构(包括顺序表的定义、线性表的基本运算在顺序表上的实现以及顺序表的应用实例)、线性表的链式存储结构(包括单链表的定义、线性表的基本运算在单链表上的实现以及单链表的应用实例)、单循环链表和双向链表。第3章是栈，介绍栈的抽象数据类型、栈的顺序存储结构(包括顺序栈的定义、栈的基本运算在顺序栈上的实现、顺序栈的应用实例)、栈的链式存储结构(包括链栈的定义、栈的基本运算在链栈上的实现、链栈的应用实例)、栈与递归。第4章是队列，介绍队列的抽象数据类型、队列的顺序存储结构(包括循环队列的定义、队列的基本运算在循环队列上的实现、循环队列的应用实例)、队列的链式存储结构(包括链队列的定义、队列的基本运算在链队列上的实现、链队列的应用实例)；第5章是数组和稀疏矩阵，介绍数组的概念、数组的顺序存储和稀疏矩阵的表示。第6章是树和二叉树，介绍树的定义和存储结构，二叉树的定义、性质和存储结构，二叉树的遍历(包括先序、中序和后序遍历)，以及遍历算法的应用、森林和二叉树的转换、构造哈夫曼树和哈夫曼编码。第7章是图，介绍图的抽象数据类型、图的存储结构(包括邻接矩阵和邻接表），图的遍历(包括深度优先搜索和广度优先搜索），最小生成树的算法（包括Prim算法和Kruskal算法），拓扑排序、关键路径、最短路径和图的应用实例。第8章是查找，介绍查找表定义和分类、静态查找表(包括顺序查找、折半查找和分块查找)、动态查找表(包括二叉排序树和平衡二叉树)，散列表的定义、构造以及散列冲突的解决方法，以及查找的应用实例。第9章是排序，介绍排序的定义和分类、插入排序(包括直接插入排序、希尔排序)、交换排序(包括冒泡排序和快速排序)、选择排序(包括直接选择排序和堆排序)、归并排序和基数排序，以及排序的应用实例。

本书由上海工程技术大学的5位教师在多年从事C语言、算法与数据结构等课程教学工作以及计算机软件开发工作的基础上编写而成。第1、2章由赵敏媛编写，第3、4章由闫丰亭编写，第5、6章由张娟、张辉编写，第7～9章由施一萍编写，全书由施一萍负责统稿。本书获得了上海工程技术大学教材建设项目和地方高校改革发展项目的资助，在此一并表示感谢。

由于编者水平有限，书中难免存在不足和疏漏之处，敬请读者批评指正。

编者2023年1月