目录 1
第1章绪论 1
1.1基本概念和术语 1
1.2发展历程 4
1.3算法和算法描述 5
1.3.1概念和特性 5
1.3.2算法设计要求 5
1.3.3算法描述 6
1.4.1时间复杂度 7
1.4算法的性能分析 7
1.4.2空间复杂度 9
小结 9
习题 9
实习 10
第2章线性表 11
2.1概念和定义 11
2.1.1概念 11
2.1.2定义 12
2.2顺序存储结构 12
2.2.2顺序表的基本操作的实现 13
2.2.1顺序表的存储表示 13
2.3链式存储结构 17
2.3.1单链表的存储表示 17
2.3.2单链表基本操作的实现 18
2.3.3循环链表的表示和基本操作的实现 22
2.3.4双向链表的表示和基本操作的实现 22
2.4应用举例 24
2.4.1顺序表 24
2.4.2单链表 26
小结 28
习题 29
实习 31
第3章栈 32
3.1概念和定义 32
3.2顺序存储表示 33
3.2.1顺序栈的存储表示 33
3.2.2顺序栈基本操作的实现 34
3.3链式存储结构 36
3.3.1链栈的存储表示 36
3.3.2链栈基本操作的实现 36
3.4应用举例 38
习题 42
小结 42
实习 44
第4章队列 45
4.1概念和定义 45
4.2顺序存储结构 46
4.2.1顺序队列的存储表示 46
4.2.2顺序队列基本操作的实现 46
4.2.3循环队列 49
4.3链式存储结构 50
4.3.1链队列的存储表示 50
4.3.2链队列基本操作的实现 51
4.4应用举例 53
小结 54
习题 55
实习 56
第5章串 57
5.1概念和定义 57
5.2顺序存储结构 59
5.2.1定长顺序串的存储表示及操作的实现 59
5.2.2堆存储表示及操作的实现 61
5.4应用举例 65
5.3块链存储表示 65
小结 67
习题 67
实习 68
第6章二维数组和广义表 69
6.1二维数组概念和定义 69
6.2二维数组的顺序存储结构 70
6.3矩阵的压缩存储 70
6.3.1概念 71
6.3.2特殊矩阵的压缩存储 71
6.3.3稀疏矩阵的顺序存储表示和基本操作的实现 72
6.3.4稀疏矩阵的链式存储表示和基本操作的实现 79
6.4广义表的概念和定义 82
6.5广义表的操作和链式存储结构 82
小结 85
习题 86
实习 88
第7章树与二叉树 89
7.1树的概念 89
7.1.1定义 89
7.1.2表示方法 90
7.1.3基本概念和常用术语 91
7.2.1概念和定义 92
7.2二叉树 92
7.2.2性质 93
7.2.3存储结构 94
7.2.4遍历 95
7.2.5二叉树的线索化 99
7.3树和森林 104
7.3.1树的存储结构 104
7.3.2树和森林的遍历 106
7.3.3树、森林与二叉树的转换 107
7.4.1概念和定义 108
7.4哈夫曼树 108
7.4.2哈夫曼树的构造 109
7.4.3哈夫曼编码的实现 112
小结 115
习题 115
实习 116
第8章图 118
8.1图的概念 118
8.1.1定义 118
8.1.2基本概念和常用术语 119
8.2存储结构 120
8.2.1邻接矩阵表示及各操作的实现 121
8.2.2邻接表的表示及各操作的实现 125
8.3图的遍历 131
8.3.1深度优先搜索 131
8.3.2广度优先搜索 134
8.4生成树和最小生成树 135
8.4.1生成树的概念和分类 135
8.4.2最小生成树的概念和实现方法 136
8.5.1概念 143
8.5.2拓扑排序 143
8.5 AOV网及其应用 143
8.6 AOE网及其应用 148
8.6.1概念 148
8.6.2关键路径 148
8.7最短路径 155
8.7.1任意源点到其余各点的最短路径 155
8.7.2任意两点间的最短路径 159
小结 160
习题 160
实习 162
9.1概念及分类 163
第9章排序 163
9.2插入排序 164
9.2.1直接插入排序 164
9.2.2折半插入排序 167
9.2.3 2－路插入排序 169
9.2.4希尔排序 170
9.3交换排序 172
9.3.1冒泡排序 173
9.3.2快速排序 175
9.4.1简单选择排序 178
9.4选择排序 178
9.4.2树型选择排序 181
9.4.3堆排序 182
9.5 K－路归并排序 186
9.6基数排序 190
9.7内部排序方法的比较 191
9.7.1时间性能 192
9.7.2空间性能 192
9.7.3稳定性 192
9.7.4排序方法的选择 193
小结 193
习题 194
实习 195
第10章查找 196
10.1概念 196
10.2顺序存储结构查找 198
10.2.1顺序查找 198
10.2.2折半查找 200
10.2.3分块查找 203
10.3树存储结构查找 206
10.3.1二叉排序树 206
10.3.2 B－树 210
10.4哈希表查找 212
10.4.1基本概念 213
10.4.2哈希函数的构造方法 213
10.4.3解决冲突的方法 215
10.4.4查找方法 218
小结 221
习题 221
实习 222
习题答案 223
参考文献 225