算法与数据结构
《算法与数据结构(第2版)》是由宁正元、赖贤伟编著，2012年清华大学出版社出版的高等院校信息技术规划教材。该教材可以适应于不同院校计算机科学与技术学科各专业的教学需求，也可作为从事计算机科学与技术工作的科技人员的参考用书。
全书内容共8章。主要内容包括:算法与程序，常用数据结构，简单数据结构，树与二叉树，图与网，数据结构的程序实现，检索及基本算法，排序及基本算法。
- 书名 算法与数据结构(第2版)
- 作者 宁正元、赖贤伟
- 类别 高等院校信息技术规划教材
- 出版社 清华大学出版社
- 出版时间 2012年3月1日
成书过程
修订过程
作者在总结教学经验和体会的基础上，结合大学生的素质特点与学习现状(截止2012年3月1日)，按照《中国计算机科学与技术学科教程2002》中设定的"算法与数据结构"课程教学大纲要求编写而成。
该教材由宁正元教授和赖贤伟博士共同编著，其中第1~8章由宁正元教授执笔，赖贤伟博士针对该教材制作了电子教案。王秀丽教授、陈国龙教授、康宝生教授、林大辉副教授、易金聪副教授、黄思先副教授、刘雄恩副教授、黄建实验师、林敏讲师等在该教材的成稿前期工作或精品课程建设中做了部分工作或提供了帮助，高等教育出版社计算机分社社长张龙和清华大学出版社计算机分社高级策划编辑袁勤勇对该教材的出版都给予了支持。
出版工作
2012年3月1日，该教材由清华大学出版社出版。
责任编辑 | 封面设计 | 责任校对 | 责任印制 |
|---|---|---|---|
袁勤勇、顾冰 | 傅瑞学 | 李建庄 | 李红英 |
内容简介
全书内容共8章。第1章介绍算法与程序的基本概念、表示、设计和分析方法，是在前导课程"高级语言程序设计"基础上的进一步引申和总结;第2章由前导课程中的数据类型概念引出数据结构的有关基本概念，并介绍读者已在前导课程中熟知的数组结构和串结构的进一步内容;第3章介绍一些简单的线性结构(如顺序表、链表、栈、队列、广义表等结构)的定义、基本算法和典型应用;第4章和第5章介绍非线性结构中的树、二叉树、图与网的有关内容;第6章介绍各类数据结构在程序设计语言中的实现策略和大批量数据的组织策略，并结合实际问题讨论了数据结构在问题建模中的应用方法;第7章和第8章介绍了在实际应用中使用的检索和排序的基本算法，并进行了算法分析。
教材目录
第1章算法与程序1 1.1算法的基本概念1 1.1.1什么是算法1 1.1.2算法的基本特性2 1.2算法的表示3 1.2.1自然语言表示3 1.2.2流程图表示3 1.2.3N-S图表示4 1.2.4伪代码表示4 1.2.5程序语言表示5 1.3算法的设计与评价6 1.3.1评价算法的标准6 1.3.2算法的环路复杂度7 1.3.3算法的时空效率8 1.3.4常见的算法设计方法11 1.4算法与程序14 1.4.1程序的基本概念14 1.4.2问题求解与实现策略14 1.4.3程序调试与查错策略16 1.4.4程序设计方法概述17 习题121 第2章常用数据结构23 2.1数据类型与数据结构23 2.1.1数据、数据元素与数据类型23 2.1.2数据结构的基本概念25 2.1.3抽象数据类型27 2.2数组29 2.2.1数组及其运算29 2.2.2数组的顺序存储结构30 2.2.3特殊矩阵的压缩存储31 2.3串34 2.3.1串的基本概念34 2.3.2串的定长顺序存储及运算实现35 2.3.3模式匹配38 2.3.4串的堆式动态存储及运算实现43 2.3.5汉字串46 习题249 上机实验题51 第3章简单数据结构52 3.1顺序表52 3.1.1线性表的基本概念52 3.1.2线性表的顺序存储结构--顺序表53 3.1.3顺序表上的基本运算54 3.2链表58 3.2.1线性表的链式存储结构--链表58 3.2.2单链表上的基本运算60 3.2.3循环链表和双向链表65 3.2.4线性表应用举例--一元多项式相加问题67 3.3栈69 3.3.1栈的概念及运算69 3.3.2顺序栈及运算实现69 3.3.3链栈及运算实现72 3.3.4栈的应用举例--递归的实现74 3.4队列76 3.4.1队列的概念及其运算76 3.4.2顺序队列及运算实现77 3.4.3链队列及运算实现80 3.4.4队列的应用举例--I/O缓冲区管理及其他82 3.5广义表84 3.5.1广义表的概念84 3.5.2广义表的存储结构及运算实现85 3.5.3广义表的应用--m元多项式的表示87 习题389 上机实验题92 第4章树与二叉树93 4.1树的基本概念93 4.1.1树的定义及表示93 4.1.2树的常用术语及运算94 4.2二叉树96 4.2.1二叉树的概念96 4.2.2二叉树的性质97 4.2.3二叉树的存储结构98 4.2.4二叉树的简单运算实现101 4.3二叉树的遍历102 4.3.1遍历二叉树的递归算法102 4.3.2遍历二叉树的非递归算法104 4.3.3遍历序列与二叉树的复原108 4.3.4基于遍历的几种二叉树运算的实现和应用举例110 4.4线索二叉树111 4.4.1线索二叉树的概念111 4.4.2线索二叉树的构造算法113 4.4.3线索二叉树上的运算实现114 4.5树和森林115 4.5.1树和森林的存储结构116 4.5.2树和森林与二叉树之间的转换117 4.5.3树和森林的遍历119 4.5.4树的应用举例--判定树120 4.6哈夫曼树121 4.6.1哈夫曼树的概念及其构造算法121 4.6.2哈夫曼树的应用--哈夫曼编码124 习题4125 | 上机实验题128 第5章图与网129 5.1图与网的基本概念129 5.1.1图与网的定义129 5.1.2图的相关术语130 5.2图与网的存储结构132 5.2.1邻接矩阵132 5.2.2邻接表与逆邻接表133 5.2.3邻接多重表135 5.3图的遍历136 5.3.1深度优先搜索遍历136 5.3.2广度优先搜索遍历138 5.3.3图的遍历应用举例--图的连通性与生成树139 5.4无向连通网的最小生成树140 5.4.1最小生成树的概念140 5.4.2Prim算法141 5.4.3Kruskal算法143 5.5有向网的最短路径144 5.5.1单源最短路径144 5.5.2所有顶点对之间的最短路径146 5.6有向无环图及其应用148 5.6.1有向无环图的概念148 5.6.2AOV网与拓扑排序150 5.6.3AOE网与关键路径154 习题5159 上机实验题161 第6章数据结构的程序实现162 6.1基本的实现策略162 6.1.1简单数据结构的程序实现162 6.1.2构造型数据结构的程序实现163 6.1.3数据结构的链式实现163 6.1.4数据结构的数组实现163 6.2动态结构的静态实现163 6.2.1静态链表164 6.2.2二叉树的静态二叉链表表示法164 6.2.3树和森林的双亲表示法165 6.2.4哈夫曼算法的静态实现166 6.3大批量数据的组织策略170 6.3.1文件的组织170 6.3.2数据库技术177 6.4数据结构在问题建模中的应用179 6.4.1Josephus问题180 6.4.2教务管理与二分图182 6.4.3学籍管理系统中的数据组织185 习题6190 上机实验题191 第7章检索及基本算法192 7.1检索的概念192 7.2线性表的检索194 7.2.1顺序检索194 7.2.2二分法检索195 7.2.3黄金分割点检索198 7.2.4精算点检索200 7.2.5分块检索202 7.3树表的检索204 7.3.1二叉检索树204 7.3.2二叉检索树的平衡性调整211 7.3.3B树和B+树214 7.4哈希检索217 7.4.1哈希检索与哈希表217 7.4.2哈希函数的构造方法218 7.4.3地址冲突的消解策略220 7.4.4哈希表的检索算法及性能分析222 习题7224 上机实验题226 第8章排序及基本算法228 8.1排序的基本概念228 8.2插入排序229 8.2.1直接插入排序230 8.2.2希尔排序231 8.2.3其他插入排序简介234 8.3交换排序237 8.3.1冒泡排序237 8.3.2快速排序238 8.4选择排序241 8.4.1直接选择排序241 8.4.2树型选择排序242 8.4.3堆排序243 8.5归并排序247 8.5.1归并相邻两个有序序列248 8.5.2二路归并排序的递归算法249 8.5.3二路归并排序的非递归算法249 8.6基数排序250 8.6.1多关键字排序250 8.6.2链式基数排序251 8.7各种内部排序方法的比较和选择254 8.8外部排序简介256 习题8258 上机实验题260 参考文献261 |
(注:目录排版顺序为从左列至右列 )
教学资源
- 配套教材
该教材有配套教材--《算法与数据结构习题精解与实验指导(第2版)》。
书名 | 书号 | 出版社 | 出版时间 | 作者 |
|---|---|---|---|---|
《算法与数据结构习题精解与实验指导(第2版)》 | 9787302276524 | 清华大学出版社 | 2012.03.01 | 宁正元、赖贤伟、宁静 |
- 课程资源
该教材提供电子教案。
教材特色
该教材是针对应用型本科教学特点和需求编写的课程教材之一，它覆盖了《中国计算机科学与技术学科教程2002》中关于核心课程"算法与数据结构"的所有知识单元和课程提纲，介绍了各种常用数据结构的有关知识和各种基本的检索排序算法。每章配有例题、习题和上机实验题。
该教材强调算法与数据结构之间的联系，体现程序设计方法中抽象、枚举、归纳三个原则的运用，反复再现算法的复杂性、效率、折中、重用等重要概念，并增加了"数据结构的程序实现"一章内容。围绕基本内容，除了增加"数据结构的程序实现"一章内容外，还介绍了一些同类其他书籍中没有或很少讨论的内容，如由层次序列和中序序列恢复二叉树、黄金点检索、精算点检索、共享栈插入排序等。
作者简介
宁正元，1957年生，男，陕西武功人，福建农林大学计算机与信息学院教授，主要研究方向为智能计算算法分析。
赖贤伟，1981年生，男，福建漳州人，硕士，福建农林大学计算机与信息学院助教，主要研究方向为多Agent系统、数理逻辑。