数据结构

第1章 绪论 1

1.1 数据结构的研究内容 1

1.1.1 用计算机解决实际问题的过程 1

1.1.2 学习数据结构的意义 3

1.2 数据结构的基本概念及术语 5

1.3 算法与算法分析 7

1.3.1 算法的定义及特性 7

1.3.2 算法的评价及性能分析 8

1.4 多核技术与并行算法 9

1.4.1 多核技术简介 9

1.4.2 并行算法设计 11

1.5 算法的描述与实现 19

1.5.1 C语言中的关键语法格式 19

1.5.2 C语言中的数据类型 20

1.5.3 C语言中与传递参数相关的技术 22

本章小结 23

习题及思考题 23

第2章 线性表 25

2.1 线性表的概念 26

2.1.1 线性表的定义 26

2.1.2 线性表的运算 26

2.2 线性表的顺序存储 28

2.2.1 顺序表 28

2.2.2 顺序表上的基本操作 29

2.2.3 顺序表的应用 33

2.3 线性表的链式存储 35

2.3.1 单链表 35

2.3.2 循环链表 43

2.3.3 双向链表 45

2.3.4 多线程链表 46

2.4 顺序表与链表的比较 48

2.5 应用 48

2.5.1 约瑟夫问题 48

2.5.2 一元多项式的表示及相加 52

本章小结 58

习题及思考题 58

实验题目 62

第3章 串 63

3.1 串及其运算 63

3.1.1 串的定义 63

3.1.2 串的基本运算 64

3.2 串的表示与实现 65

3.2.1 定长顺序串 66

3.2.2 堆串 67

3.2.3 块链串 69

3.3 串模式匹配算法 70

3.3.1 简单的串模式匹配算法 70

3.3.2 KMP算法 71

3.4 串的应用 74

本章小结 75

习题及思考题 75

第4章 栈与队列 77

4.1 栈 78

4.1.1 栈的定义与运算 78

4.1.2 顺序栈 79

4.1.3 链栈 82

4.1.4 多线程栈 83

4.2 栈的应用 85

4.2.1 数制转换 85

4.2.2 括号匹配检验 86

4.3 栈与递归的实现 89

4.3.1 递归的定义 89

4.3.2 递归的原理 90

4.3.3 递归的应用及算法实现 91

4.3.4 递归算法的非递归化 93

4.4 队列 95

4.4.1 队列的定义与运算 95

4.4.2 顺序队列 96

4.4.3 链队列 100

4.4.4 共享队列 103

4.5 队列的应用 105

4.5.1 回文判断 105

4.5.2 “舞会”问题 106

本章小结 108

习题及思考题 108

实验题目 111

第5章 数组与广义表 114

5.1 多维数组 115

5.1.1 数组的定义 115

5.1.2 数组的运算 116

5.2 数组的顺序存储 116

5.2.1 数组的顺序存储结构 116

5.2.2 数组元素的地址计算 117

5.3 矩阵的压缩存储 119

5.3.1 特殊矩阵 119

5.3.2 稀疏矩阵 121

5.4 矩阵相乘的并行算法 128

5.4.1 矩阵相乘的基本概念 128

5.4.2 串行算法 128

5.4.3 并行算法 128

5.5 广义表 131

5.5.1 广义表的定义 131

5.5.2 广义表的存储结构 133

5.5.3 广义表的相关算法 134

本章小结 136

习题及思考题 136

第6章 树 139

6.1 树的基本概念 140

6.1.1 树的定义 140

6.1.2 树的表示方法 141

6.1.3 树的基本术语 142

6.1.4 树的运算 143

6.2 二叉树 144

6.2.1 二叉树的基本概念 144

6.2.2 二叉树的性质 145

6.2.3 二叉树的存储结构 147

6.3 二叉树的遍历 150

6.3.1 遍历方法 150

6.3.2 遍历算法的应用 154

6.4 线索二叉树 158

6.4.1 线索二叉树的定义和实现 158

6.4.2 线索二叉树的算法实现 160

6.5 树与二叉树的转换 161

6.5.1 树与森林的存储 161

6.5.2 树、森林与二叉树的相互转换 164

6.5.3 树与森林的遍历 168

6.6 哈夫曼树 170

6.6.1 哈夫曼树的基本概念 171

6.6.2 哈夫曼树的构造 172

6.6.3 哈夫曼树的应用 174

本章小结 180

习题及思考题 180

实验题目 184

第7章 图 186

7.1 图的定义及术语 186

7.1.1 图的定义 186

7.1.2 图的运算 187

7.1.3 基本术语 188

7.2 图的存储结构 191

7.2.1 邻接矩阵表示法 191

7.2.2 邻接表表示法 196

7.3 图的遍历 201

7.3.1 深度优先搜索 201

7.3.2 广度优先搜索 206

7.4 图的连通性 210

7.4.1 无向图的连通分量 210

7.4.2 图的生成树 210

7.4.3 图的最小生成树 210

7.5 最短路径 215

7.5.1 单源点最短路径问题 215

7.5.2 Dijkstra算法的并行化 218

7.5.3 求任意一对顶点间的最短路径 220

7.6 有向无环图 221

7.6.1 拓扑排序 221

7.6.2 关键路径 225

7.7 应用实例 228

本章小结 231

习题及思考题 231

实验题目 235

第8章 查找 236

8.1 查找的基本概念 237

8.2 基于线性表的查找法 238

8.2.1 顺序查找法 238

8.2.2 折半查找法 239

8.2.3 分块查找法 243

8.3 基于树的查找法 244

8.3.1 二叉排序树 245

8.3.2 平衡二叉排序树 255

8.3.3 B树 260

8.4 散列技术 267

8.4.1 散列表的基本概念 267

8.4.2 散列函数的设计 268

8.4.3 处理冲突的方法 271

8.4.4 散列表的查找过程 274

8.4.5 散列法的性能分析 275

8.5 应用实例 277

本章小结 279

习题及思考题 280

实验题目 281

第9章 内部排序 283

9.1 排序的基本概念 284

9.2 选择排序 285

9.2.1 简单选择排序 285

9.2.2 堆排序 286

9.2.3 基于并行的锦标赛排序 291

9.3 插入排序 292

9.3.1 直接插入排序 292

9.3.2 折半插入排序 294

9.3.3 希尔排序 295

9.4 交换排序 297

9.4.1 冒泡排序 298

9.4.2 快速排序 299

9.4.3 快速排序的多线程实现 302

9.5 归并排序 303

9.6 基数排序 306

9.6.1 多关键字的排序 306

9.6.2 链式基数排序 307

9.7 排序算法分析 308

9.8 应用实例 309

本章小结 312

习题及思考题 312

实验题目 314

第10章 文件 315

10.1 文件的基本概念 315

10.2 顺序文件 316

10.3 索引文件 317

10.3.1 索引文件的基本概念 317

10.3.2 ISAM文件和VSAM文件 318

10.4 散列文件 320

10.5 倒排文件 321

本章小结 321

习题及思考题 322

附录A 期末考试模拟试卷及全国硕士研究生入学考试统考试题 323

期末考试模拟试卷一 323

期末考试模拟试卷二 325

期末考试模拟试卷三 328

期末考试模拟试卷四 330

2009年全国硕士研究生入学考试统考试题“数据结构”部分 334

2010年全国硕士研究生入学考试统考试题“数据结构”部分 337

附录B 数据结构实验报告范例 339

附录C Visual C＋＋6.0开发环境的介绍 341

附录D OpenMP并行程序设计简介 344

参考文献 349