数据结构与算法设计——高等学校计算机专业规划教材 (2009 年度畅销榜NO.9027 )

为适应21世纪计算机各类人才的需要，结合我国高等学校教育工作现状，立足更新教学内容和方法，编写了本书。\r\n 本书以基本数据儿算法设计策略为知识单元，系统地介绍了数据结构的基本知识与实际应用，介绍了抽象数据类型和算法的基本概念以及计算机算法的设计方法与分析技巧。\r\n 本书内容丰富，观点新颖，注重理论联系实际，可作为高等院校计算机学科与工程专业本科生、研究生的教材，也适合广大工程技术人员和自学读者学习参考。

第1章 绪论 \r\n 1.1　问题求解 \r\n 1.2　算法表达中的抽象机制 \r\n 1.3　抽象数据类型 \r\n 1.3.1　抽象数据类型的基本概念 \r\n 1.3.2　使用抽象数据类型的好处 \r\n 1.3.3　数据结构.数据类型和抽象数据类型 \r\n 1.4　用C＋＋描述数据结构与算法 \r\n 1.4.1　变量.指针和引用 \r\n 1.4.2　函数与参数传递 \r\n 1.4.3　C＋＋的类 \r\n 1.4.4　类的对象 \r\n 1.4.5　构造函数与桥构函数 \r\n 1.4.6　运算符重载 \r\n 1.4.7　友元函数 \r\n 1.4.8　内联函数 \r\n 1.4.9　结构 \r\n 1.4.10 联合 \r\n 1.4.11　异常 \r\n 1.4.12　模板 \r\n 1.4.13　动态存储分配 \r\n 1.5　算法复杂性分析 \r\n 1.5.1　算法与程序 \r\n 1.5.2　算法复杂性的概念 \r\n 1.5.3　算法复杂性的渐近性态 \r\n 习题一 \r\n第2章　表 \r\n 2.1　ADT表 \r\n 2.2　用数组实现表 \r\n 2.3　用指针实现表 \r\n 2.4　用间接寻址方法实现表 \r\n 2.5　用游标实现表 \r\n 2.6　循环链表 \r\n 2.7　双链表 \r\n 习题二 \r\n第3章　栈 \r\n 3.1 ADT栈 \r\n 3.2 用数组实现栈 \r\n 3.3　用指针实现栈 \r\n 3.4　等价类划分问题 \r\n 习题三 \r\n第4章　队列 \r\n 4.1 ADT队列 \r\n 4.2　用指针实现队列 \r\n 4.3　用循环数组实现队列 \r\n 4.4　电路布线问题 \r\n 习题四 \r\n第5章 串 \r\n 5.1 ADT串 \r\n 　 5.2　用数组实现串 \r\n 　5.3　用指针实现串 \r\n 　 5.4　串的块链表示法 \r\n 　5.5　串的堆结构 \r\n 　5.6　模式匹配 \r\n 　 5.6.1　朴素的模式匹配算法 \r\n 　 5.6.2　模式匹配的KMP算法 \r\n 　习题五 \r\n第6章　排序与选择 \r\n 　 6.1　简单排序算法 \r\n 　 6.1.1　冒泡排序 \r\n 　 6.1.2　插入排序 \r\n 　6.1.3　选择排序 \r\n 　 6.1.4　简单排序算法的计算复杂性 \r\n 　6.2　快速排序算法 \r\n 　 6.2.1 算法基本思想及实现 \r\n 　6.2.2　算法的性能 \r\n 　 6.2.3　随机快速排序算法 \r\n 　6.3　合并排序算法 \r\n 　 6.3.1　算法基本思想及实现 \r\n 　6.3.2　消除递归 \r\n 　 6.3.3　自然合并排序 \r\n 　6.4　线性时间排序算法 \r\n 　 6.4.1 计数排序 \r\n 　6.4.2　桶排序 \r\n 　 6.5　中位数与第是小元素 \r\n 　 6.5.1　平均情况下的线性时间选择算法 \r\n 　 6.5.2　最坏情况下的线性时间选择算法 \r\n 　 习题六 \r\n第7章　树 \r\n 　 7.1　树的定义 \r\n 7.2　树的遍历 \r\n 7.3　树的表示法 \r\n 7.4 二叉树 \r\n 7.5 ADT二叉树 \r\n 7.6　二叉树的实现 \r\n 7.6.1　二叉树的顺序存储结构 \r\n 7.6.2　二叉树的结点度表示法 \r\n 7.6.3　用指针实现二叉树 \r\n 7.7 线索二叉树 \r\n 习题七 \r\n第8章 图 \r\n 8.1　图的基本概念 \r\n 8.2　抽象数据类型ADT图 \r\n 8.3　图的表示法 \r\n 8.3.1　邻接矩阵表示法 \r\n 8.3.2　邻接表表示法 \r\n 8.3.3　紧缩邻接表 \r\n 8.4　用邻接矩阵实现图 \r\n 8.4.1　用邻接矩阵实现赋权有向图 \r\n 8.4.2　用邻接矩阵实现赋权无向图 \r\n 8.4.3　用邻接矩阵实现有向图 \r\n 8.4.4　用邻接矩阵实现无向图 \r\n 8.5　用邻接表实现图 \r\n 8.5.1　邻接表基类 \r\n 8.5.2　用邻接表实现有向图 \r\n 8.5.3　用邻接表实现无向图 \r\n 8.5.4　用邻接表实现赋权有向图 \r\n 8.5.5　用邻接表实现赋权无向图 \r\n 8.6　图的退伍 \r\n 8.6.1　图的搜索游标 \r\n 8.6.2　广度优先搜索 \r\n 8.6.3　深度优先搜索 \r\n 8.7　最短路径 \r\n 8.7.1　单源最短路径 \r\n 8.7.2　所有顶点对之间的最短路径 \r\n 8.8　最小生成树 \r\n 8.8.1 最小生成树性质 \r\n 8.8.2 Prim算法 \r\n 8.8.3 Kruskal算法 \r\n 8.9　图匹配 \r\n 习题八 \r\n第9章　集合 \r\n 9.1　以集合为基础的抽象数据类型 \r\n 9.1.1　集合的定义和记号 \r\n 9.1.2　定义在集合上的基本运算 \r\n 9.1.3　集合的简单表示法 \r\n 9.2　字典 \r\n 9.2.1　实现字典的简单方法 \r\n 9.2.2　用散列表实现字典 \r\n 9.3　有序字典 \r\n 9.3.1　有序字典的定义 \r\n 9.3.2　用数组实现有序字典 \r\n 9.3.3　用二叉搜索树实现有序字典 \r\n 9.3.4　AVL树 \r\n 9.3.5　红黑树 \r\n 9.4　优先队列 \r\n 9.4.1 优先队列的定义 \r\n 9.4.2　用字典实现代先队列 \r\n 9.4.3　优先级树和堆 \r\n 9.4.4　用数组实现推 \r\n 9.4.5　可并优先队列 \r\n 9.5　并查集 \r\n 9.5.1　并查集的定义及其简单实现 \r\n 9.5.2　用父亲数组实现并查集 \r\n 习题九 \r\n第10章　算法设计策略 \r\n 10.1　递归与分治策略 \r\n 10.1.1　递归的概念 \r\n 10.1.2　分治法的基本思想 \r\n 10.1.3　二分搜索技术 \r\n 10.1.4　棋盘覆盖问题 \r\n 10.2　动态规划 \r\n 10.2.1　矩阵连乘问题 \r\n 10.2.2　动态规划算法的基本要素 \r\n 10.2.3　最大子段和问题 \r\n 10.3　贪心算法 \r\n 10.3.1　活动安排问题 \r\n 10.3.2　贪心算法的基本要素 \r\n 10.3.3　哈夫曼编码算法 \r\n 10.4　回溯法 \r\n 10.4.1　回溯法的算法框架 \r\n 10.4.2　符号三角形问题 \r\n 10.4.3　圆排列问题 \r\n 10.4.4　连续邮资问题 \r\n 10.4.5　回溯法的效率分析 \r\n 10.5　分支限界法 \r\n 10.5.1　分支限界法的基本思想 \r\n 10.5.2　装载问题 \r\n 10.5.3　批处理作业调度问题 \r\n 习题十 \r\n参考文献\r\n

计算机的普及极大地改变了人们的生活. 目前各行业. 各领域都与计算机建立了紧密的联系, 并由此产生开发各种应用软件的需求. 为了以最少的成本. 最快的速度. 最好的质量开发出适合各种应用需求的软件, 必须遵循软件工程的原则, 设计出高效率的程序. 一个高效的程序既需要“编程小技巧”, 更需要合理的数据组织和清晰高效的算法. 这正是计算机科学领域里数据结构与算法设计所研究的主要内容. 一些著名的计算机科学家在有关计算机科学教育的论述中认为, 计算机科学是一种创造性思维活动, 其教育必须面向设计. 数据结构与算法设计正是一门面向设计, 且处于计算机学科核心地位的教育课程. 通过对数据结构与算法设计的系统学习与研究, 理解和掌握算法设计的主要方法, 培养对算法的计算复杂性进行正确分析的能力, 为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础, 对从事计算机系统结构. 系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的. 为了适应培养我国对世纪计算机各类人才的需要, 结合我国高等学校教育工作的现状, 立足培养学生能跟上国际计算机科学技术的发展水平, 更新教学内容和教学方法, 本书以基本数据结构和算法设计策略为知识单元系统地介绍数据结构知识与应用. 计算机算法的设计方法与分析技巧. 以期为计算机学科的学生提供一个广泛坚实的数据结构与算法设计基础知识.

全书共分10章. 首先在第1章中介绍了数据结构. 抽象数据类型和算法的基本概念, 接着对算法的计算复杂性和算法的描述做了简要的阐述. 然后以抽象数据类型为主线索, 围绕设计算法常用的基本数据结构和基本设计策略, 组织了第2章～第10章的内容.

第2章～第5章依次介绍基于序列的抽象数据类型表. 栈. 队列和串.

第6章介绍在实际应用中常用的排序与选择算法.

第7章讨论反映层次关系的抽象数据类型树.

第8章介绍非线性结构图及图的算法.

第9章讨论表示集会的抽象数据类型, 如字典. 优先队列和并查集等.

最后, 在第10章系统地阐述算法设计的策略与技巧.

本书采用面向对象的C++语言为表述手段, 在保持C++优点的同时, 尽量使数据结构与算法的描述简明. 清晰.

为了加深对知识的理解, 各章配有难易适当的习题, 以适应不同程度读者练习的需要.

由于作者的知识和写作水平有限, 书稿虽几经修改, 仍难免有缺点和错误. 热忱欢迎同行专家和读者批评指正, 使本书在使用中不断改进. 日臻完善.

在本书的编写过程中, 得到全国高等学校计算机专业教学指导委员会的关心和支持, 福州大学“211工程”计算机与信息工程重点学科实验室为本书的写作提供了优良的设备与工作环境, 电子工业出版社负责本书编辑出版工作的全体同仁工作认真细致, 一丝不苟, 为本书的出版付出了大量辛勤劳动, 傅清祥教授在百忙之中认真审阅了全书, 提出了许多宝贵的改进意见. 在此, 一并表示衷心的谢意！

作者

2001年10月