前言

“数据结构与算法”是计算机科学与技术一级学科相关专业的重要基础课程之一，是软件开发和维护的基础。计算机的数据处理能力是计算机解决各种实际问题的关键。现实世界中的实际问题经过抽象，得出反映实际事物本质的数据表示后，才有可能被计算机处理。从实际问题抽象出数学模型，得出它的数据表示后，如何用计算机所能接受的形式来描述这些数据（包括数据本身与数据之间的关系）？如何将这些数据以及它们之间的关系存储在计算机中？如何用有效的方法去处理这些数据？如何在构建的数据结构上设计高效的算法？这些问题皆是数据结构与算法研究的主要问题。

本书是在深入研究国内外同类教材的基础上，结合多年“数据结构”“算法设计与分析”课程教学经验编写而成的，书中重点围绕抽象数据类型的C语言实现进行介绍。第1版出版后，得到了很多高校的认可，这次修订，除了改正第2版中的部分错误外，还增加了8.10节和10.6节等内容。

第1章为数据结构概述，主要介绍数据结构概念，内容包括逻辑结构、存储方法、算法复杂性分析、基本数据类型、抽象数据类型与结构描述。第2章介绍向量、栈和队列及其应用，内容有向量、栈和队列的逻辑结构，抽象数据类型向量、栈和队列的描述；Josephus问题求解、栈与后缀表达式求值、栈与递归、递归效率分析、队列与离散事件模拟等应用实例。第3章介绍链表及其应用，内容有动态存储、单链表、循环链表、双链表、栈和队列的链接存储。第4章介绍串，内容有串的定义、串的存储以及串的模式匹配算法。第5章介绍各种排序方法，内容包括排序的基本概念，被排序文件的存储表示，直接插入排序、折半插入排序、Shell排序、起泡排序、快速排序、归并排序和外部排序等各种排序方法，各种算法的实现细节和算法的时空效率等。第6章介绍线性表的查找，内容包括有关查找的概念，顺序查找、折半查找、分块查找和散列查找。第7章介绍树和二叉树，内容包括树(树林)和二叉树的概念、树（树林）和二叉树的遍历、抽象数据类型BinaryTree与BinaryTree结构、二叉树的遍历算法。第8章介绍树结构的应用，内容包括二叉排序树、平衡的二叉排序树、B树和B+树、键树和23树、Huffman最优树、堆排序、判定树、等价类和并查集、红黑树等。第9章介绍图结构，内容包括图的基本概念、图的存储表示、Graph结构的构造与实现、图的遍历、最小代价生成树、单源最短路径问题、每一对顶点间的最短路径问题、有向无回路图。第10章为算法设计与分析，内容包括递归与分治、回溯法、分支限界法、贪心算法和动态规划法等。

本书是作为计算机科学与技术专业、军事院校的基础合训专业和其他相关专业的“数据结构与算法”课程教材编写的，也可供从事计算机软件开发和计算机应用的工程与科技人员参考。具备了C语言基础的读者便可学习本书。 

书中不加注的章节可用60学时讲授，全部内容的讲授可用70～80学时完成。此外，为配合课堂教学，便于学生理解和掌握所学知识，提高程序设计编程能力，应另外配有20～30小时的上机时间。

本书由熊岳山教授、朱晨阳副教授编写。本书的出版得到清华大学出版社和国防科技大学计算机学院、计算机系、603教研室的大力支持，在此深表谢意。特别感谢陈怀义教授和姚丹霖教授的辛勤工作与许多富有创新的思想，感谢殷建平、肖晓强、刘越等老师为本书提出的宝贵意见，正是因为这些同志的热情帮助，才使得本书能顺利出版。由于时间仓促，加之编者水平有限，书中错误在所难免，敬请广大读者和专家批评指正。

 编者2023年12月