数据结构 C++语言版

前言 1

第1章 数据结构与算法概论 1

1.1 算法及其复杂性的概念 1

1.1.1 算法与程序 1

1.1.2 算法复杂性的概念 1

1.1.3 算法复杂性的渐近性态 2

1.2 数据结构与抽象数据类型 3

1.3 用C十十描述数据结构与算法 4

1.3.1 指针和引用 4

1.3.2 函数与参数传递 4

1.3.3 C十十的类 5

1.3.4 类的对象 6

1.3.5 模板 6

1.3.6 动态存储分配 7

1.4 递归 8

1.5 应用举例 10

习题1 19

实验1 20

实验题1.1 实系数复变多项式问题 20

实验题1.2 平面几何问题 21

实验题1.3 m进制数间题 21

第2章 线性表 23

2.1 表的基本概念 23

2.2 用数组实现表 24

2.3 用指针实现表 28

2.4 用间接寻址方法实现表 33

2.5 用游标实现表 36

2.6 循环链表 43

2.7 双链表 47

2.8 表的搜索游标 54

2.9 应用举例 58

习题2 65

实验2 66

实验题2.1 实系数一元多项式问题 66

实验题2.2 Josephus排列问题1 68

实验题2.3 向量分类问题 68

实验题2.4 条形图轮廓问题 69

实验题2.5 Josephus排列问题2 70

第3章 栈 72

3.1 栈的基本概念 72

3.2 用数组实现栈 73

3.3 用指针实现栈 76

3.4 应用举例 78

习题3 85

实验3 86

实验题3.1 车皮编序问题 86

实验题3.2 单柱Hanoi塔问题 87

实验题3.3 多栈模拟问题 88

实验题3.4 亲兄弟问题 88

第4章 队列 90

4.1 队列的基本概念 90

4.2 用指针实现队列 90

4.3 用循环数组实现队列 93

4.4 应用举例 97

习题4 101

实验4 102

实验题4.1 组队列问题 102

实验题4.2 双栈队列问题 103

实验题4.3 猴子分桃问题 104

实验题4.4 逆序表问题 105

第5章 集合 106

5.1 集合的基本概念 106

5.2 抽象数据类型集合 107

5.3 用位向量实现集合 107

5.4 用链表实现集合 111

5.5 应用举例 113

习题5 114

实验5 115

实验题5.1 半数集问题 115

第6章 排序与选择 117

6.1 简单排序算法 117

6.1.1 冒泡排序算法 117

6.1.2 插入排序算法 118

6.1.3 选择排序算法 118

6.1.4 简单排序算法的计算复杂性 119

6.2 快速排序算法 120

6.2.1 算法基本思想及实现 120

6.2.2 算法性能分析 121

6.2.3 随机快速排序算法 122

6.3 合并排序算法 122

6.3.1 算法基本思想及实现 122

6.3.2 消除递归 123

6.3.3 自然合并排序算法 124

6.4 线性时间排序算法 125

6.4.1 计数排序算法 125

6.4.2 桶排序算法 126

6.5 中位数与第k小元素 127

6.5.1 平均情况下的线性时间选择算法 128

6.5.2 最坏情况下的线性时间选择算法 128

6.6 应用举例 130

习题6 134

实验6 135

实验题6.1 交换排序问题 135

实验题6.2 DNA排序问题 136

实验题6.3 输油管道问题 136

实验题6.4 最优服务次序问题 137

第7章 树 138

7.1 树的定义 138

7.2 树的遍历 140

7.3 树的表示法 141

7.3.1 父结点数组表示法 142

7.3.2 儿子链表表示法 142

7.3.3 左儿子右兄弟表示法 142

7.4 二叉树的基本概念 143

7.5 二叉树的运算 145

7.6 二叉树的实现 146

7.6.1 二叉树的顺序存储结构 146

7.6.2 二叉树的结点度表示法 147

7.6.3 用指针实现二叉树 148

7.7 线索二叉树 152

7.8 应用举例 154

习题7 157

实验7 159

实验题7.1 层序列表问题 159

实验题7.2 最近公共祖先问题 159

实验题7.3 子树问题 160

实验题7.4 同构二叉树问题 161

实验题7.5 后序中序遍历问题 162

第8章 二叉搜索树 163

8.1 有序集与二叉搜索树 163

8.1.1 抽象数据类型字典 163

8.1.2 用数组实现字典 163

8.1.3 二叉搜索树的基本概念 163

8.2 实现二叉搜索树 164

8.3 平衡的二叉搜索树AVL树 172

8.3.1 AVL树的定义和性质 172

8.3.2 旋转变换 174

8.3.3 AVL树的插入与重平衡运算 176

8.3.4 AVL树的删除与重平衡运算 179

8.4 应用举例 182

习题8 184

实验8 185

实验题8.1 装箱问题 185

实验题8.2 电路板连线问题 186

实验题8.3 辞典问题 186

第9章 堆与优先队列 188

9.1 优先队列的基本概念 188

9.2 用字典实现优先队列 188

9.3 优先级树和堆 189

9.4 用数组实现堆 191

9.5 可并优先队列 194

9.5.1 左偏树的定义 194

9.5.2 用左偏树实现可并优先队列 195

9.6 应用举例 198

习题9 201

实验9 202

实验题9.1 区间相交问题 202

实验题9.2 整数字典问题 202

实验题9.3 最小权语言问题 203

实验题9.4 二叉搜索堆问题 203

实验题9.5 区间覆盖问题 204

第10章 散列 206

10.1 抽象数据类型符号表 206

10.2 开散列 208

10.3 闭散列 210

10.4 散列函数的效率 214

10.5 重新散列 215

10.6 应用举例 216

习题10 217

实验10 218

实验题10.1 伪随机排列问题 218

实验题10.2 字符串散列问题 218

实验题10.3 英文文本分析问题 219

实验题10.4 最长模式串问题 220

第11章 并查集 221

11.1 并查集的基本概念 221

11.2 用父结点数组实现并查集 222

11.3 应用举例 225

习题11 227

实验11 228

实验题11.1 二进制方程问题 228

实验题11.2 网络连通问题 229

实验题11.3 朋友问题 229

实验题11.4 等价类划分问题 230

第12章 图 232

12.1 图的基本概念 232

12.2 抽象数据类型图 235

12.3 图的表示法 235

12.3.1 邻接矩阵表示法 235

12.3.2 邻接表表示法 236

12.3.3 紧缩邻接表 237

12.4 用邻接矩阵实现图 237

12.4.1 用邻接矩阵实现赋权有向图 237

12.4.2 用邻接矩阵实现赋权无向图 240

12.4.3 用邻接矩阵实现有向图 240

12.4.4 用邻接矩阵实现无向图 241

12.5 用邻接表实现图 241

12.5.1 邻接表基类 241

12.5.2 用邻接表实现有向图 243

12.5.3 用邻接表实现无向图 244

12.5.4 用邻接表实现赋权有向图 245

12.5.5 用邻接表实现赋权无向图 247

12.6 图的遍历 249

12.6.1 图的搜索游标 249

12.6.2 广度优先搜索 252

12.6.3 深度优先搜索 255

12.7 最短路径算法 256

12.7.1 单源最短路径算法 256

12.7.2 Bellman-Ford最短路径算法 259

12.7.3 所有顶点对之间的最短路径算法 261

12.8 最小支撑树 262

12.8.1 最小支撑树性质 262

12.8.2 最小支撑树的Prim算法 263

12.8.3 最小支撑树的Kruskal算法 265

12.9 图匹配算法 267

12.10 应用举例 270

习题12 272

实验12 273

实验题12.1 图的二着色问题 273

实验题12.2 赋权有向图中心问题 274

实验题12.3 最长简单路径问题 275

实验题12.4 计算机网络问题 276

实验题12.5 差分约束问题 276

实验题12.6 有截止时间的工作排序问题 277

实验题12.7 无向图的连通分支问题 278

参考文献 279