本书是国家精品课程教材，以教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”为依据，以基本数据结构为知识单元而编写。全书共分12章，包括引论、表、栈、队列、排序与选择、树、图、集合、符号表、字典、优先队列、并查集等。 全书采用C语言作为描述语言，内容丰富，叙述简明，理论与实践并重，每章设有应用举例和算法实验题，并为任课教师免费提供电子课件和课程实验用数据。     读者对象：可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业的数据结构课程教材，也适合工程技术人员和自学者学习参考。

前 言 为了以最少的成本、最快的速度、最好的质量开发出适合多种应用需求的软件，开发人员必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要“编程小技巧”，更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域“数据结构设计”所研究的主要内容。 计算机科学是一种创造性思维活动，其教育必须面向设计。数据结构正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对数据结构知识的系统学习与研究，理解和掌握数据结构与算法设计的主要方法，为独立完成软件设计和分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者来说是必不可少的。为了适应21世纪我国培养各类计算机人才的需要，本课程结合我国高等学校教育工作的现状，追踪国际计算机科学技术的发展水平，更新了教学内容和教学方法，以基本数据结构为知识单元，系统介绍数据结构知识与应用，以期为计算机相关专业的学生提供一个扎实的数据结构设计的知识基础。本课程的教学改革实践取得了丰硕的成果，该课程2007年被评为国家精品课程。 本书以ACM和IEEE/CS Computing Curricula 课程体系及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中关于算法与数据结构的知识结构和体系为依据编写，全书共分12章。 第1章引论，介绍数据结构、抽象数据类型和算法等基本概念，并简要阐述了算法的计算复杂性和对算法的描述。 第2~4章依次介绍基于序列的抽象数据类型表、栈和队列。 第5章介绍在实际应用中常用的排序与选择算法。 第6章讨论反映层次关系的抽象数据类型树。 第7章介绍非线性结构图及其算法。 第8章讨论表示集合的抽象数据类型。 第9章讨论抽象数据类型符号表及散列表等实践中常用实现符号表的方法。 第10章的主题是以有序集为基础的抽象数据类型字典及其实现方法。 第11章讨论以集合为基础的抽象数据类型优先队列及其实现方法。 第12章讨论以不相交集合为基础的抽象数据类型并查集及其实现方法。 考虑到学生的知识基础和课程体系需要，本书用C语言作为描述语言，尽量使数据结构和算法的描述简明、清晰。参考学时数为54~68。 数据结构是一门理论性强、实践难度较大的专业基础课程。为了使学生在深刻理解课程内容的基础上，灵活运用所学的知识解决实际问题，我们在章首增加了学习要点提示，章末有本章小结和难易适当的习题，并特别设计了算法实验题，以强化实践环节，要求学生课后通过上机实验来完成。作者的教学实践表明，这类算法实验题对学生掌握课堂教学内容有很大帮助，效果非常好。为便于教学，本教材还将免费提供电子课件和课程实验数据，请任课教师登录华信教育资源网http://www.hxedu.com.cn免费注册下载。作者还结合精品课程建设，建立了教学网站http://ds.fzu.edu.cn ，欢迎广大读者访问，并提出宝贵意见，作者E-mail：wangxd135@139.com。 本书在编写过程中，得到了全国高等学校计算机专业教学指导委员会的关心和支持。福州大学“211工程”计算机与信息工程重点学科实验室为本书的写作提供了优良的设备和工作环境。田俊教授在百忙之中认真审阅了全书，提出了许多宝贵意见。本课程组的吴英杰、傅仰耿和傅清祥老师也为本书的出版和教学资源建设做出了贡献。在此，谨向每一位曾经关心和支持本书编写工作的人士表示衷心的感谢！ 由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正，以使本书不断改进，日臻完善。 作 者

目 录 第1章 引论 （1） 1.1 算法及其复杂性的概念 （1） 1.1.1 算法与程序 （1） 1.1.2 算法复杂性的概念 （1） 1.1.3 算法复杂性的渐近性态 （3） 1.2 算法的表达与数据表示 （5） 1.2.1 问题求解 （5） 1.2.2 表达算法的抽象机制 （5） 1.3 抽象数据类型 （8） 1.3.1 抽象数据类型的基本概念 （8） 1.3.2 使用抽象数据类型的好处 （9） 1.4 数据结构、数据类型和抽象数据类型 （10） 1.5 用C语言描述数据结构与算法 （11） 1.5.1 变量和指针 （11） 1.5.2 函数与参数传递 （12） 1.5.3 结构 （13） 1.5.4 动态存储分配 （14） 1.6 递归 （15） 1.6.1 递归的基本概念 （15） 1.6.2 间接递归 （17） 本章小结 （17） 习题1 （18） 算法实验1 （19） 算法实验题1.1 哥德巴赫猜想问题 （19） 算法实验题1.2 连续整数和问题 （19） 第2章 表 （20） 2.1 表的基本概念 （20） 2.2 用数组实现表 （21） 2.3 用指针实现表 （25） 2.4 用间接寻址方法实现表 （29） 2.5 用游标实现表 （32） 2.6 循环链表 （38） 2.7 双链表 （41） 2.8 表的搜索游标 （45） 2.8.1 用数组实现表的搜索游标 （45） 2.8.2 单循环链表的搜索游标 （46） 2.9 应用举例——Josephus排列问题 （48） 本章小结 （49） 习题2 （49） 算法实验2 （51） 算法实验题2.1 向量分类问题 （51） 算法实验题2.2 条形图轮廓问题 （51） 第3章 栈 （53） 3.1 栈的基本概念 （53） 3.2 用数组实现栈 （54） 3.3 用指针实现栈 （56） 3.4 应用举例——等价类划分问题 （59） 本章小结 （61） 习题3 （61） 算法实验3 （63） 算法实验题3.1 车皮编序问题 （63） 算法实验题3.2 单柱Hanoi塔问题 （63） 算法实验题3.3 多栈模拟问题 （64） 算法实验题3.4 亲兄弟问题 （64） 第4章 队列 （66） 4.1 队列的基本概念 （66） 4.2 用指针实现队列 （67） 4.3 用循环数组实现队列 （69） 4.4 应用举例——电路布线问题 （73） 本章小结 （77） 习题4 （77） 算法实验4 （78） 算法实验题4.1 组队列问题 （78） 算法实验题4.2 双栈队列问题 （79） 算法实验题4.3 猴子分桃问题 （79） 算法实验题4.4 逆序表问题 （79） 第5章 排序与选择 （81） 5.1 简单排序算法 （81） 5.1.1 冒泡排序 （82） 5.1.2 插入排序 （82） 5.1.3 选择排序 （83） 5.1.4 简单排序算法的计算复杂性 （83） 5.2 快速排序算法 （84） 5.2.1 算法基本思想及实现 （84） 5.2.2 算法的性能 （86） 5.2.3 随机快速排序算法 （86） 5.2.4 非递归快速排序算法 （87） 5.2.5 三数取中划分算法 （88） 5.2.6 三划分快速排序算法 （89） 5.3 合并排序算法 （90） 5.3.1 算法基本思想及实现 （90） 5.3.2 对基本算法的改进 （91） 5.3.3 自底向上的合并排序算法 （92） 5.3.4 自然合并排序 （92） 5.3.5 链表结构的合并排序算法 （93） 5.4 线性时间排序算法 （94） 5.4.1 计数排序 （94） 5.4.2 桶排序 （95） 5.5 中位数与第k小元素 （96） 5.5.1 平均情况下的线性时间选择算法 （97） 5.5.2 最坏情况下的线性时间选择算法 （98） 5.6 应用举例——带权中位数问题 （100） 本章小结 （101） 习题5 （102） 算法实验5 （103） 算法实验题5.1 交换排序问题 （103） 算法实验题5.2 DNA排序问题 （103） 算法实验题5.3 输油管道问题 （104） 算法实验题5.4 最优服务次序问题 （104） 第6章 树 （105） 6.1 树的定义 （105） 6.2 树的遍历 （107） 6.3 树的表示法 （109） 6.3.1 父结点数组表示法 （109） 6.3.2 儿子链表表示法 （110） 6.3.3 左儿子右兄弟表示法 （110） 6.4 二叉树的基本概念 （111） 6.5 二叉树的运算 （113） 6.6 二叉树的实现 （114） 6.6.1 二叉树的顺序存储结构 （114） 6.6.2 二叉树的结点度表示法 （115） 6.6.3 用指针实现二叉树 （115） 6.7 线索二叉树 （120） 6.8 应用举例——信号增强装置布局问题 （122） 本章小结 （126） 习题6 （126） 算法实验6 （128） 算法实验题6.1 层序列表问题 （128） 算法实验题6.2 最近公共祖先问题 （128） 算法实验题6.3 子树问题 （129） 算法实验题6.4 同构二叉树问题 （129） 算法实验题6.5 后序中序遍历问题 （130） 第7章 图 （131） 7.1 图的基本概念 （131） 7.2 抽象数据类型ADT图 （134） 7.3 图的表示法 （134） 7.3.1 邻接矩阵表示法 （135） 7.3.2 邻接表表示法 （135） 7.3.3 紧缩邻接表 （135） 7.4 用邻接矩阵实现图 （136） 7.4.1 用邻接矩阵实现赋权有向图 （136） 7.4.2 用邻接矩阵实现赋权无向图 （139） 7.4.3 用邻接矩阵实现有向图 （140） 7.4.4 用邻接矩阵实现无向图 （140） 7.5 用邻接表实现图 （141） 7.5.1 用邻接表实现有向图 （141） 7.5.2 用邻接表实现无向图 （144） 7.5.3 用邻接表实现赋权有向图 （145） 7.5.4 用邻接表实现赋权无向图 （148） 7.6 图的遍历 （149） 7.6.1 广度优先搜索 （149） 7.6.2 深度优先搜索 （151） 7.7 最短路径 （152） 7.7.1 单源最短路径 （153） 7.7.2 Bellman-Ford最短路径算法 （156） 7.7.3 所有顶点对之间的最短路径 （158） 7.8 无圈有向图DAG （160） 7.8.1 拓扑排序 （160） 7.8.2 DAG的最短路径 （162） 7.8.3 DAG的最长路径 （163） 7.8.4 DAG所有顶点对之间的最短路径 （163） 7.9 最小支撑树 （164） 7.9.1 最小支撑树性质 （164） 7.9.2 Prim算法 （164） 7.9.3 Kruskal算法 （166） 7.10 图匹配 （169） 7.11 应用举例——差分约束系统 （170） 本章小结 （172） 习题7 （172） 算法实验7 （174） 算法实验题7.1 图的二着色问题 （174） 算法实验题7.2 赋权有向图中心问题 （174） 算法实验题7.3 最长简单路径问题 （175） 算法实验题7.4 计算机网络问题 （175） 算法实验题7.5 差分约束问题 （176） 算法实验题7.6 有截止时间的工作排序问题 （176） 第8章 集合 （178） 8.1 以集合为基础的抽象数据类型 （178） 8.1.1 集合的定义和记号 （178） 8.1.2 定义在集合上的基本运算 （179） 8.2 用位向量实现集合 （179） 8.3 用链表实现集合 （183） 8.4 应用举例——Eratosthenes筛法 （186） 本章小结 （187） 习题8 （187） 算法实验8 （188） 算法实验题8.1 半数集问题 （188） 第9章 符号表 （190） 9.1 实现符号表的简单方法 （190） 9.2 用散列表实现符号表 （191） 9.2.1 开散列 （192） 9.2.2 闭散列 （194） 9.2.3 散列函数及其效率 （198） 9.2.4 闭散列的重新散列技术 （199） 9.3 应用举例——字符串频率统计问题 （199） 本章小结 （201） 习题9 （201） 算法实验9 （202） 算法实验题9.1 伪随机排列问题 （202） 算法实验题9.2 字符串散列问题 （202） 算法实验题9.3 英文文本分析问题 （202） 算法实验题9.4 最长模式串问题 （203） 第10章 字典 （204） 10.1 字典的定义 （204） 10.2 用数组实现字典 （204） 10.3 用二叉搜索树实现字典 （205） 10.4 AVL树 （213） 10.4.1 AVL树的定义和性质 （213） 10.4.2 旋转变换 （214） 10.4.3 AVL树的插入运算 （217） 10.4.4 AVL树的删除运算 （220） 10.5 应用举例——条形图统计问题 （223） 本章小结 （225） 习题10 （225） 算法实验10 （226） 算法实验题10.1 装箱问题 （226） 算法实验题10.2 电路板连线问题 （227） 算法实验题10.3 辞典问题 （227） 第11章 优先队列 （229） 11.1 优先队列的定义 （229） 11.2 用字典实现优先队列 （230） 11.3 优先级树和堆 （230） 11.4 用数组实现堆 （232） 11.5 可并优先队列 （235） 11.5.1 左偏树的定义 （235） 11.5.2 用左偏树实现可并优先队列 （236） 11.6 应用举例——哈夫曼编码 （239） 本章小结 （243） 习题11 （243） 算法实验11 （244） 算法实验题11.1 多机调度问题 （244） 算法实验题11.2 整数字典问题 （244） 算法实验题11.3 最小权语言问题 （245） 算法实验题11.4 二叉搜索堆问题 （245） 第12章 并查集 （247） 12.1 并查集的定义及其简单实现 （247） 12.2 用父结点数组实现并查集 （248） 12.3 应用举例——离线最小值问题 （251） 本章小结 （253） 习题12 （253） 算法实验12 （254） 算法实验题12.1 二进制方程问题 （254） 算法实验题12.2 网络连通问题 （255） 算法实验题12.3 朋友问题 （255） 算法实验题12.4 无向图的连通分支问题 （255） 参考文献 （257）

王晓东，男，教授，博士生导师。1985年4月研究生毕业于福州大学计算机应用技术专业。主讲课程：算法与数据结构、算法设计与分析、文献阅读与选题报告。研究方向：计算机算法设计与算法评价、并行和分布式算法设计、计算复杂性理论等。

http://www.hxedu.com.cn/hxedu/fg/book/bookinfo.html?code=G0142240