基础篇 算法类课程群实训教程——算法与数据结构 1
第1章 线性表 1
1.1基础理论 1
1.1.1基本概念 1
1.1.2基本操作 2
1.2实例解析 5
1.2.1顺序表的基本操作 5
1.2.2单链表的基本操作 7
1.3实训任务 9
1.3.1实训目的 9
1.3.2实训要求 9
1.3.3实训内容 10
第2章 栈和队列 12
2.1基础理论 12
2.1.1基本概念 12
2.1.2基本操作 13
2.2实例解析 17
2.2.1顺序栈的基本操作实例 17
2.2.2链栈的基本操作实例 19
2.2.3循环队列的基本操作实例 21
2.2.4链队列的基本操作实例 22
2.3实训与实践任务 24
2.3.1实训目的 24
2.3.2实训要求 24
2.3.3实训内容 24
第3章串 27
3.1基础理论 27
3.1.1基本概念 27
3.1.2基本操作 28
3.2实例解析 30
3.3实训与实践任务 32
3.3.1实训目的 32
3.3.2实训要求 32
3.3.3实训内容 32
第4章 数组和广义表 33
4.1基础理论 33
4.1.1数组的定义 33
4.1.2特殊矩阵的压缩存储 34
4.1.3稀疏矩阵的压缩存储 34
4.2实例解析 35
4.3实训与实践任务 38
4.3.1实训目的 38
4.3.2实训要求 38
4.3.3实训内容 38
第5章树 40
5.1基础理论 40
5.1.1基本概念 40
5.1.2基本性质 41
5.1.3存储结构 41
5.1.4树的遍历 42
5.1.5线索二叉树 43
5.1.6哈夫曼树 44
5.2实例解析 45
5.3实训任务 53
5.3.1实训目的 53
5.3.2实训要求 54
5.3.3实训内容 54
第6章图 58
6.1基础理论 58
6.1.1基本概念 58
6.1.2基本运算 59
6.1.3存储结构 59
6.1.4图的遍历 61
6.1.5最小生成树 61
6.1.6最短路径 62
6.1.7拓扑排序 63
6.1.8关键路径 64
6.2实例解析 64
6.3实训任务 78
6.3.1实训目的 78
6.3.2实训要求 78
6.3.3实训内容 78
第7章 查找 81
7.1基础理论 81
7.2实例解析 85
7.3实训任务 90
7.3.1实训目的 90
7.3.2实训要求 90
7.3.3实训内容 91
第8章 排序 95
8.1基础理论 95
8.2实例解析 98
8.3实训任务 103
8.3.1实训目的 103
8.3.2实训要求 103
8.3.3实训内容 104
提高篇 算法类课程群实训教程——算法设计与分析 106
第1章 递归与分治 106
1.1算法设计方法提要 106
1.1.1分治法 106
1.1.2递归技术 106
1.1.3方法性能 107
1.2经典剖析 107
1.2.1大整数的乘法 107
1.2.2归并排序 108
1.2.3棋盘覆盖 109
1.3实战训练 111
1.3.1实训目的 111
1.3.2实训要求 111
1.3.3实训内容 111
第2章 动态规划 113
2.1算法设计方法提要 113
2.1.1求解策略 113
2.1.2算法设计步骤 113
2.1.3适用条件 114
2.1.4方法性能 114
2.2经典剖析 115
2.2.1 0-1背包问题 115
2.2.2最长公共子序列 116
2.2.3矩阵连乘 118
2.3实战训练 120
2.3.1实训目的 120
2.3.2实训要求 120
2.3.3实训内容 120
第3章 贪心法 123
3.1算法设计方法提要 123
3.1.1基本思想 123
3.1.2贪心最优算法条件 123
3.1.3方法性能 123
3.2经典剖析 124
3.2.1背包问题 124
3.2.2哈夫曼编码 124
3.2.3最小生成树 127
3.2.4单源最短路径 130
3.3实战训练 133
3.3.1实训目的 133
3.3.2实训要求 133
3.3.3实训内容 133
第4章 回溯法 135
4.1算法设计方法提要 135
4.1.1基本思想 135
4.1.2基本步骤 135
4.1.3子集树和排列数 135
4.1.4适用条件 136
4.1.5方法性能 136
4.2经典剖析 136
4.2.1 0-1背包问题 136
4.2.2 N皇后问题 138
4.2.3批处理作业调度 139
4.3实战训练 141
4.3.1实训目的 141
4.3.2实训要求 141
4.3.3实训内容 142
第5章 分支限界法 146
5.1算法设计方法提要 146
5.1.1基本思想 146
5.1.2基本步骤 146
5.1.3适用条件 146
5.1.4方法性能 146
5.2经典剖析 147
5.2.1 0-1背包问题 147
5.2.2单源最短路径问题 155
5.2.3批处理作业调度 163
5.3实战训练 168
5.3.1实训目的 168
5.3.2实训要求 168
5.3.3实训内容 168
第6章 概率算法专题 170
6.1算法设计方法提要 170
6.1.1基本思想 170
6.1.2适用条件 171
6.2经典剖析 171
6.2.1非线性方程组求解 171
6.2.2舍伍德（Sherwood）算法 175
6.2.3拉斯维加斯（Las Vegas）算法 176
6.2.4蒙特卡罗（Monte Carlo）算法 179
6.3实战训练 180
6.3.1实训目的 180
6.3.2实训要求 180
6.3.3实训内容 181
第7章 图与网络算法专题 182
7.1 A*算法 182
7.2网络流算法 183
7.2.1多个源和多个汇的网络 183
7.2.2寻求最大流的标号法 184
7.3实战训练 185
7.3.1实训目的 185
7.3.2实训要求 185
7.3.3实训内容 185
第8章 算法分析与设计综合训练 186
8.1 STL简介 186
8.2综合训练 187
参考文献 197