第1章 绪论 1
1.1 基本术语 1
1.2 算法的概念 4
1.3 算法描述 6
1.4 算法分析 7
1.4.1 时间复杂度 8
1.4.2 空间复杂度 11
1.5 算法设计的基本步骤 11
习题 12
第2章 线性表 15
2.1 线性表的概念和基本操作 15
2.1.1 线性表的定义 15
2.1.2 线性表的基本操作 17
2.2 线性表的顺序存储结构 18
2.2.1 数组——线性表的顺序存储结构 18
2.2.2 数组中基本操作的实现 19
2.2.3 操作的时间分析 22
2.3.1 单链表和指针 23
2.3 线性表的链式存储结构 23
2.3.2 单链表的基本操作 25
2.3.3 链表的实现 30
2.3.4 单链表的其他操作 31
2.4 循环链表及其操作 33
2.5 双向链表及其操作 36
2.5.1 双向链表的构造 36
2.5.2 双向链表的插入与删除算法 37
习题 39
第3章 堆栈和队列 43
3.1 堆栈的概念及操作 43
3.1.1 堆栈的定义 43
3.1.2 堆栈的有关操作 44
3.2 堆栈的顺序存储结构 45
3.3 堆栈的链式存储结构 47
3.4 堆栈的应用举例 49
3.4.1 算术表达式的求值 49
3.4.2 在递归问题中的应用 51
3.5 队列的概念及操作 52
3.5.1 队列的定义 52
3.5.2 队列的有关操作 53
3.6 队列的顺序存储结构 53
3.7 队列的链式存储结构 57
3.8 综合实例——算符优先算法 59
习题 63
4.1 数组的定义和操作 65
第4章 数组 65
4.2 数组的顺序存储结构 66
4.3 特殊矩阵的压缩存储 68
4.3.1 对称矩阵的压缩存储 68
4.3.2 对角矩阵的压缩存储 69
4.4 稀疏矩阵的表示法 70
4.4.1 三元组表示法 70
4.1.2 稀疏矩阵的顺序存储 71
4.1.3 稀疏矩阵的链式存储 71
4.1.4 稀疏矩阵的运算 73
习题 76
第5章 字符串 77
5.1 字符串的概念和基本操作 77
5.1.1 字符串的定义 77
5.1.2 字符串的基本操作 78
5.2 字符串的存储结构 79
5.2.1 字符串的顺序存储结构 80
5.2.2 字符串的链式存储结构 81
5.3 字符串操作的实现 82
习题 84
第6章 广义表 85
6.1 广义表的定义 85
6.2 广义表的存储结构 87
6.3 广义表的操作 88
习题 89
第7章 树与二叉树 91
7.1 树的概念 91
7.1.1 树的定义 91
7.1.2 树的逻辑表示法 93
7.1.3 树的基本术语 94
7.1.4 树的基本操作 95
7.2 二叉树 96
7.2.1 二叉树的定义 96
7.2.2 二叉树的基本操作 97
7.2.3 二叉树的性质 98
7.3 二叉树的存储结构 101
7.3.1 二叉树的顺序存储结构 101
7.3.2 二叉树的链式存储结构 102
7.4 二叉树的遍历 104
7.4.1 遍历的概念 104
7.4.2 遍历的算法 106
7.5 线索二叉树 108
7.5.1 二叉树的线索化 108
7.5.2 利用线索进行遍历 111
7.6 二叉排序树 112
7.6.1 二叉排序树的定义 112
7.6.2 二叉排序树的查找 113
7.6.3 二叉排序树的插入和生成 114
7.6.4 二叉排序树中结点的删除 117
7.7 哈夫曼树 120
7.7.1 哈夫曼树的基本术语 120
7.7.2 哈夫曼树的构造 121
7.7.3 哈夫曼编码 122
7.8 树和森林 123
7.8.1 树的存储结构 124
7.8.2 二叉树与树、森林之间的转换 126
习题 127
第8章 图 131
8.1 图的基本概念 131
8.1.1 图的定义 131
8.1.2 图的基本术语 132
8.1.3 图的基本操作 135
8.2 图的存储结构 136
8.2.1 邻接矩阵(数组) 136
8.2.2 邻接表 137
8.2.3 邻接多重表 138
8.2.4 邻接表的生成算法 140
8.3 图的遍历 140
8.3.1 DFS和BFS的基本思想 141
8.3.2 DFS和BFS算法 142
8.3.3 非连通图的遍历 148
8.3.4 DFS和BFS算法的应用 149
8.4 网的最小生成树 151
8.5 最短路径 154
8.6 拓扑排序 156
习题 160
第9章 查找 165
9.1 顺序查找 165
9.2 二分查找 167
9.3 分块查找 170
9.4 树表的查找 173
9.5 哈希表查找 180
9.5.1 哈希表 180
9.5.2 哈希函数的构造方法 181
9.5.3 冲突解决的方法 183
习题 186
第10章 排序 189
10.1 排序的概念 189
10.2 插入排序 190
10.3 快速排序 191
10.4 选择排序 197
10.5 归并排序 202
10.6 小结 203
习题 204
实验指导书 207
实验一 顺序表的插入与删除 207
实验二 单链表的插入与删除 208
实验三 堆栈的操作 208
实验四 二叉排序树的构造与查找 209
实验五 冒泡排序 210
实验六 快速排序 211
参考文献 212