为了适应培养我国计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，本书以基本数据结构为知识单元系统地介绍数据结构知识与应用、计算机算法的设计与分析方法，以期为计算机学科的学生提供一个广泛坚实的数据结构基础知识。
数据结构与算法设计
王晓东 著
精品课程网站 http://course.jingpinke.com/details?uuid=8a83399b
-19cc280d-0119-cc280d75-004b&courseID=A070020
本书以基本数据结构为知识单元系统地介绍数据结构知识与应用、计算机算法的设计与分析方法；以抽象数据类型为主线来组织教学内容，融入面向对象的思想，构建面向问题求解的实践教学模式；以实际问题求解为主线来组织和设计实践教学内容，增加设计型实验和综合型实验，锻炼学生综合运用所学理论知识进行问题分析、设计和实现的能力，在实践中强化创新意识。
本课程教学体系建设较为完备：
配有完整的示例动画课件集，基本上覆盖了算法与数据结构课程本科教学中需要用动画辅助讲解的所有示例。通过动画课件示例，使得相应的算法和数据结构更直观、形象、生动，便于学生的理解和记忆。
课程组专门开发了课程的网络教学系统（http://ds.fzu.edu.cn），用于辅助课堂教学和实践教学。该系统可实现作业发布、提交、在线评测、成绩公布、优秀作业评选、疑难解答等多项功能。
为了适应培养计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，本书以基本数据结构和算法设计策略为知识单元，系统地介绍数据结构知识与应用、计算机算法的设计与分析方法，以期为计算机学科的学生提供广泛、坚实的数据结构与算法设计基础知识。
全书共分13章，第1章介绍数据结构、抽象数据类型和算法的基本概念，并对算法的计算复杂性和算法的描述作了简要的阐述。然后以抽象数据类型为主线索，围绕设计算法常用的基本数据结构和基本设计策略组织了第2～13章的内容。
第2～4章依次介绍基于序列的抽象数据类型——表、栈和队列。
第5章介绍递归的概念，以及递归在数据结构和算法设计中的广泛应用，并详细阐述分治法、动态规划和回溯法这3个实践中常用的使用递归技术的算法设计策略。
第6章介绍在实际应用中常用的排序与选择算法。
第7章讨论反映层次关系的抽象数据类型——树。
第8章讨论表示集合的抽象数据类型。
第9章讨论符号表以及散列表等实践中常用实现符号表的方法。
第10章的主题是以有序集为基础的字典及其实现方法，讨论实现字典的二叉搜索树以及AVL树等高效算法。
第11章讨论以集合为基础的优先队列及其实现方法。
第12章讨论以不相交的集合为基础的并查集及其实现方法。
第13章介绍非线性结构图及图的算法。
为了加深对知识的理解，各章均配有难易适当的习题，以适应不同程度读者练习的需要；同时在每章的最后配有相应的算法实验。
由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误，热忱欢迎同行专家和读者批评指正，以使本书不断改进、日臻完善。
计算机\数据结构
精品课程网站：http://course.jingpinke.com/details?uuid=8a83399b-19cc280d-0119-cc280d75-004b&courseID=A070020
本书以基本数据结构为知识单元系统地介绍数据结构知识与应用、计算机算法的设计与分析方法，以抽象数据类型为主线来组织教学内容，融入面向对象的思想，构建面向问题求解的实践教学模式，以实际问题求解为主线索来组织和设计实践教学内容，增加设计型实验和综合型实验，锻炼学生综合运用所学理论知识进行问题分析、设计和实现的能力，在实践中强化创新意识。
本课程教学体系建设较为完备：
1）配有完整的示例动画课件集，基本上覆盖了“算法与数据结构”课程本科教学中需要用动画辅助讲解的所有示例。通过动画课件示例，使得相应的算法和数据结构更直观、形象、生动，便于学生的理解和记忆。
2）课程组专门开发了课程的网络教学系统（http://ds.fzu.edu.cn），用于辅助课堂教学和实践教学。该系统可实现作业发布、提交、在线评测、成绩公布、优秀作业评选、疑难解答等多项功能。
出版者的话
前言
教学方案设计
第1章 引论1
1.1 算法及其复杂性的概念1
1.1.1 算法与程序1
1.1.2 算法复杂性的概念2
1.1.3 算法复杂性的渐近性态3
1.2 算法的表达与数据表示4
1.2.1 问题求解4
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
本章小结14
习题15
算法实验16
算法实验题1.1 哥德巴赫猜想问题16
算法实验题1.2 连续整数和问题16
第2章 表17
2.1 表的基本概念17
2.2 用数组实现表18
2.3 用指针实现表22
2.4 用间接寻址方法实现表25
2.5 用游标实现表27
2.6 循环链表32
2.7 双链表34
2.8 表的搜索游标37
2.8.1 用数组实现表的搜索游标38
2.8.2 单循环链表的搜索游标38
2.9 应用40
本章小结41
习题41
算法实验43
算法实验题2.1 向量分类问题43
算法实验题2.2 条形图轮廓问题43
第3章 栈45
3.1 栈的基本概念45
3.2 用数组实现栈46
3.3 用指针实现栈48
3.4 应用50
本章小结52
习题52
算法实验54
算法实验题3.1 车皮编序问题54
算法实验题3.2 单柱Hanoi塔问题55
算法实验题3.3 多栈模拟问题55
算法实验题3.4 亲兄弟问题56
第4章 队列57
4.1 队列的基本概念57
4.2 用指针实现队列58
4.3 用循环数组实现队列60
4.4 应用64
本章小结66
习题66
算法实验67
算法实验题4.1 组队列问题67
算法实验题4.2 双栈队列问题68
算法实验题4.3 猴子分桃问题69
算法实验题4.4 逆序表问题69
第5章 递归71
5.1 递归的概念71
5.2 递归程序设计76
5.2.1 分治与递归76
5.2.2 动态规划77
5.2.3 回溯与递归83
5.3 模拟递归85
5.4 应用87
本章小结89
习题89
算法实验90
算法实验题5.1 删数问题90
算法实验题5.2 最优服务次序问题91
算法实验题5.3 最大k乘积问题91
算法实验题5.4 字符串比较问题92
第6章 排序与选择93
6.1 简单排序算法93
6.1.1 冒泡排序94
6.1.2 插入排序94
6.1.3 选择排序95
6.1.4 简单排序算法的计算复杂性95
6.2 快速排序算法96
6.2.1 算法基本思想及实现96
6.2.2 算法的性能97
6.2.3 随机快速排序算法98
6.2.4 非递归快速排序算法98
6.2.5 三数取中划分算法99
6.2.6 三划分快速排序算法100
6.3 合并排序算法101
6.3.1 算法基本思想及实现101
6.3.2 对基本算法的改进102
6.3.3 自底向上的合并排序算法102
6.3.4 自然合并排序103
6.3.5 链表结构的合并排序算法103
6.4 线性时间排序算法104
6.4.1 计数排序104
6.4.2 桶排序105
6.5 中位数与第k小元素106
6.5.1 平均情况下的线性时间选择算法107
6.5.2 最坏情况下的线性时间选择算法108
6.6 应用109
本章小结110
习题111
算法实验112
算法实验题6.1 交换排序问题112
算法实验题6.2 DNA排序问题112
算法实验题6.3 输油管道问题113
算法实验题6.4 最优服务次序问题114
第7章 树115
7.1 树的定义115
7.2 树的遍历117
7.3 树的表示法119
7.3.1 父结点数组表示法119
7.3.2 儿子链表表示法119
7.3.3 左儿子右兄弟表示法120
7.4 二叉树120
7.5 ADT二叉树122
7.6 二叉树的实现123
7.6.1 二叉树的顺序存储结构123
7.6.2 二叉树的结点度表示法124
7.6.3 用指针实现二叉树124
7.7 线索二叉树128
7.8 应用129
本章小结132
习题133
算法实验135
算法实验题7.1 层序列表问题135
算法实验题7.2 最近公共祖先问题135
算法实验题7.3 子树问题136
算法实验题7.4 同构二叉树问题136
算法实验题7.5 后序中序遍历问题137
第8章 集合138
8.1 以集合为基础的抽象数据类型138
8.1.1 集合的定义和记号138
8.1.2 定义在集合上的基本运算139
8.2 用位向量实现集合140
8.3 用链表实现集合142
8.4 应用145
本章小结146
习题146
算法实验147
算法实验题 半数集问题147
第9章 符号表148
9.1 实现符号表的简单方法148
9.2 用散列表实现符号表149
9.2.1 开散列150
9.2.2 闭散列151
9.2.3 散列函数及其效率155
9.2.4 闭散列的重新散列技术156
9.3 应用156
本章小结157
习题158
算法实验158
算法实验题9.1 伪随机排列问题158
算法实验题9.2 字符串散列问题159
算法实验题9.3 英文文本分析问题159
算法实验题9.4 最长模式串问题160
第10章 字典161
10.1 字典的定义161
10.2 用数组实现字典162
10.3 用二叉搜索树实现字典162
10.4 AVL树169
10.4.1 AVL树的定义和性质169
10.4.2 旋转变换170
10.4.3 AVL树的插入运算173
10.4.4 AVL树的删除运算174
10.5 应用177
本章小结179
习题179
算法实验180
算法实验题10.1 装箱问题180
算法实验题10.2 电路板连线问题181
算法实验题10.3 辞典问题182
第11章 优先队列183
11.1 优先队列的定义183
11.2 用字典实现优先队列184
11.3 优先级树和堆184
11.4 用数组实现堆186
11.5 可并优先队列188
11.5.1 左偏树的定义188
11.5.2 用左偏树实现可并优先队列189
11.6 应用192
本章小结195
习题195
算法实验196
算法实验题11.1 多机调度问题196
算法实验题11.2 整数字典问题197
算法实验题11.3 最小权语言问题197
算法实验题11.4 二叉搜索堆问题198
第12章 并查集199
12.1 并查集的定义及其简单实现199
12.2 用父结点数组实现并查集200
12.3 应用203
本章小结204
习题204
算法实验205
算法实验题12.1 二进制方程问题205
算法实验题12.2 网络连通问题206
算法实验题12.3 朋友问题206
算法实验题12.4 无向图的连通分支问题207
第13章 图208
13.1 图的基本概念208
13.2 抽象数据类型图211
13.3 图的表示法211
13.3.1 邻接矩阵表示法211
13.3.2 邻接表表示法212
13.3.3 紧缩邻接表213
13.4 用邻接矩阵实现图213
13.4.1 用邻接矩阵实现赋权有向图213
13.4.2 用邻接矩阵实现赋权无向图215
13.4.3 用邻接矩阵实现有向图216
13.4.4 用邻接矩阵实现无向图216
13.5 用邻接表实现图217
13.5.1 用邻接表实现有向图217
13.5.2 用邻接表实现无向图219
13.5.3 用邻接表实现赋权有向图220
13.5.4 用邻接表实现赋权无向图222
13.6 图的遍历223
13.6.1 广度优先搜索223
13.6.2 深度优先搜索225
13.7 最短路径226
13.7.1 单源最短路径226
13.7.2 所有顶点对之间的最短路径229
13.8 最小支撑树230
13.8.1 最小支撑树性质230
13.8.2 Prim算法231
13.8.3 Kruskal算法233
13.9 图匹配234
本章小结236
习题237
算法实验238
算法实验题13.1 图的2着色问题238
算法实验题13.2 赋权有向图中心问题239
算法实验题13.3 最长简单路径问题239
算法实验题13.4 计算机网络问题240
算法实验题13.5 差分约束问题240
算法实验题13.6 有截止时间的工作排序问题241
参考文献243
