目录
教育技术学专业主干课程系列教材总序
序
前言
第1章 概述 1
1.1 数据结构 2
1.1.1 数据与数据结构的定义 2
1.1.2 逻辑结构、物理结构和抽象数据类型 3
1.2 算法与算法分析 5
1.2.1 算法 5
1.2.2 算法的性质和判断算法优劣的标准 5
1.2.3 算法分析 7
1.3 全国青少年信息学奥林匹克联赛简介 10
1.4 C STL简介 11
习题 12
第2章 线性表 13
2.1 顺序表 13
2.1.1 顺序表的基本概念 13
2.1.2 顺序表的实现 14
2.1.3 顺序表操作的时间复杂度 19
2.2 C STL中顺序表的用法 19
2.3 信息学竞赛中顺序表的应用 21
2.4 单链表 26
2.4.1 链表的基本概念 26
2.4.2 链表的实现 28
2.4.3 链表操作的时间复杂度 32
2.5 循环链表、双向链表和静态链表 32
2.5.1 循环链表 32
2.5.2 双向链表 33
2.5.3 静态链表 35
2.6 C STL中链表的用法 36
2.7 信息学竞赛中链表的应用 37
习题 39
第3章 栈与队列 40
3.1 栈 40
3.1.1 栈的基本概念 40
3.1.2 顺序栈的实现 41
3.2 C STL中栈的用法 42
3.3 信息学竞赛中栈的应用 42
3.4 队列 48
3.4.1 队列的基本概念 48
3.4.2 链式队列的实现 51
3.5 C STL中队列的用法 52
3.5.1 队列queue的用法 52
3.5.2 优先级队列priority_queue的用法 52
3.6 信息学竞赛中队列的应用 54
习题 57
第4章 递归 59
4.1 基本概念与用法 59
4.1.1 递归的基本概念 59
4.1.2 递归的特点 61
4.2 递归与栈的关系 61
4.3 递归算法 63
4.3.1 穷举法 63
4.3.2 分治法 65
4.3.3 回溯法 70
4.4 信息学竞赛中递归的应用 74
习题 78
第5章 串 79
5.1 串的基本概念 79
5.2 串的存储结构 80
5.2.1 串的顺序存储 80
5.2.2 串的链式存储 85
5.3 串的模式匹配算法 85
5.3.1 Brute-Force算法 85
5.3.2 KMP算法 87
5.4 C STL中字符串的用法 91
5.4.1 string的头文件、定义与初始化 91
5.4.2 string的基本操作 91
5.5 信息学竞赛中字符串的应用 93
习题 95
第6章 树 97
6.1 树的基本概念 97
6.2 二叉树 98
6.2.1 二叉树的基本概念与性质 98
6.2.2 二叉树遍历 101
6.3 哈夫曼树 108
6.3.1 变长编码 108
6.3.2 哈夫曼树与哈夫曼编码 110
6.4 树与森林 115
6.4.1 树与森林的表示方法 115
6.4.2 等价类问题与并查集算法 118
6.5 信息学竞赛中树的应用 121
习题 123
第7章 图 125
7.1 图的基本概念 125
7.1.1 图的定义 125
7.1.2 图的基本术语 125
7.2 图的存储方法 127
7.2.1 邻接矩阵存储方法 127
7.2.2 邻接表存储方法 129
7.3 图的遍历 131
7.3.1 深度优先搜索遍历 131
7.3.2 广度优先搜索遍历 132
7.3.3 非连通图的遍历 133
7.4 小生成树问题 134
7.4.1 生成树 134
7.4.2 小生成树 135
7.4.3 普里姆算法 135
7.4.4 克鲁斯卡尔算法 139
7.5 短路径问题 140
7.5.1 单源短路径 140
7.5.2 任意两点间的短路径 144
7.6 拓扑排序 147
7.7 信息学竞赛中图的应用 149
习题 154
第8章 排序 156
8.1 冒泡排序 156
8.1.1 冒泡排序算法 156
8.1.2 冒泡排序的时间复杂度 159
8.2 插入排序 159
8.2.1 插入排序算法 159
8.2.2 插入排序的时间复杂度 161
8.3 归并排序 161
8.3.1 归并排序算法 161
8.3.2 归并排序的时间复杂度 163
8.4 快速排序 165
8.4.1 快速排序算法 165
8.4.2 快速排序的时间复杂度 167
8.5 堆排序 170
8.5.1 堆的概念与建立堆的方法 170
8.5.2 堆排序算法 174
8.5.3 堆排序的时间复杂度 175
8.6 比较排序算法的实质 175
8.7 基数排序 177
8.7.1 线性时间排序算法 177
8.7.2 基数排序算法 178
8.7.3 链式基数排序算法 179
8.8 各种排序算法复杂度比较 181
8.9 C STL中排序算法的用法 182
8.9.1 几种常用的STL sort算法函数简介 182
8.9.2 sort函数使用方法 183
8.10 信息学竞赛中排序的应用 184
习题 188
第9章 查找 189
9.1 二分查找法 189
9.1.1 二分查找法的实现 189
9.1.2 C STL中二分查找的用法 191
9.2 哈希表 193
9.2.1 哈希函数 194
9.2.2 开放定址法 195
9.2.3 链地址法 198
9.2.4 哈希表的时间复杂度 199
9.2.5 C STL中哈希表的用法 201
9.3 查找树 203
9.3.1 二叉查找树 203
9.3.2 红黑树 210
9.3.3 C STL中二叉查找树的用法 217
9.4 信息学竞赛中查找的应用 219
习题 223
第10章 动态规划 225
10.1 动态规划基础 225
10.2 背包问题 230
10.3 区间动态规划 234
10.4 信息学竞赛中动态规划的应用 238
习题 244
习题参考答案或提示 245
参考文献 248
书单推荐
