数据结构(C++版)

第0章 预备知识1

0.1 数学预备知识1

0.1.1 常用数学术语1

0.1.2 对数1

0.1.3 级数求和2

0.2 常用数学证明方法3

0.2.1 反证法3

0.2.2 数学归纳法3

0.3 离散数学预备知识4

0.3.1 集合4

0.3.2 谓词6

0.3.3 关系6

0.4 c++程序设计语言预备知识7

0.4.1 程序结构7

0.4.2 变量、常量与数据类型8

0.4.3 控制语句13

0.4.4 函数14

0.4.5 继承与派生19

0.4.6 多态与虚函数20

0.4.7 模板21

.0.4.8 动态存储分配22

0.4.9 输入与输出23

0.4.10 异常处理23

第1章 绪论27

1.1 数据结构的兴起和发展27

1.2 数据结构的研究对象29

1.3 数据结构的基本概念31

1.3.1 数据结构31

1.3.2 数据结构的访问接口33

1.3.3 抽象数据类型33

1.4 算法及算法分析35

1.4.1 算法35

1.4.2 算法分析38

1.5 案例综述42

习题1 45

思考题1 47

第2章 线性表49

2.1 线性表的逻辑结构49

2.1.1 线性表的定义49

2.1.2 线性表的抽象数据类型定义50

2.2 线性表的顺序存储结构及实现51

2.2.1 线性表的顺序存储结构——顺序表51

2.2.2 顺序表的实现52

2.3 线性表的链接存储结构及实现57

2.3.1 线性表的链接存储结构——单链表58

2.3.2 单链表的实现59

2.4 顺序表和单链表的比较66

2.4.1 时间性能比较66

2.4.2 空间性能比较66

2.5 线性表的其他存储方法67

2.5.1 循环链表67

2.5.2 双链表68

2.5.3 静态链表69

2.5.4 间接寻址70

2.6 应用举例71

2.6.1 顺序表的应用举例——符号表71

2.6.2 单链表的应用举例——一元多项式求和72

2.6.3 高校学籍管理75

习题2 76

思考题2 79

第3章 特殊线性表——栈、队列和串81

3.1 栈81

3.1.1 栈的逻辑结构81

3.1.2 栈的顺序存储结构及实现83

3.1.3 栈的链接存储结构及实现88

3.1.4 顺序栈和链栈的比较89

3.2 队列90

3.2.1 队列的逻辑结构90

3.2.2 队列的顺序存储结构及实现91

3.2.3 队列的链接存储结构及实现94

3.2.4 循环队列和链队列的比较97

3.3 串97

3.3.1 串的逻辑结构97

3.3.2 串的存储结构99

3.3.3 模式匹配100

3.4 应用举例104

3.4.1 栈的应用举例——递归104

3.4.2 队列的应用举例——火车车厢重排107

3.4.3 串的应用举例——恺撒密码109

3.4.4 高校实验任务安排问题110

习题3 111

思考题3 113

第4章 广义线性表——多维数组和广义表115

4.1 多维数组115

4.1.1 数组的定义115

4.1.2 数组的存储结构与寻址117

4.2 矩阵的压缩存储118

4.2.1 特殊矩阵的压缩存储119

4.2.2 稀疏矩阵的压缩存储121

4.3 广义表127

4.3.1 广义表的逻辑结构127

4.3.2 广义表的存储结构及实现129

4.4 应用举例132

4.4.1 数组的应用举例——魔方阵132

4.4.2 本科生选导师问题134

习题4 135

思考题4 137

第5章 树和二叉树139

5.1 树的逻辑结构139

5.1.1 树的定义和基本术语139

5.1.2 树的抽象数据类型定义142

5.1.3 树的遍历操作143

5.2 树的存储结构144

5.2.1 双亲表示法144

5.2.2 孩子表示法145

5.2.3 双亲孩子表示法147

5.2.4 孩子兄弟表示法147

5.3 二叉树的逻辑结构148

5.3.1 二叉树的定义148

5.3.2 二叉树的基本性质150

5.3.3 二叉树的抽象数据类型定义153

5.3.4 二叉树的遍历操作154

5.4 二叉树的存储结构及实现156

5.4.1 顺序存储结构156

5.4.2 二叉链表157

5.4.3 三叉链表166

5.4.4 线索链表167

5.5 树、森林与二叉树的转换171

5.6 应用举例175

5.6.1 二叉树的应用举例——哈夫曼树及哈夫曼编码175

5.6.2 树的应用举例——8枚硬币问题179

5.6.3 高校学生会组织机构的管理180

习题5 182

思考题5 184

第6章 图185

6.1 图的逻辑结构185

6.1.1 图的定义和基本术语185

6.1.2 图的抽象数据类型定义189

6.1.3 图的遍历操作191

6.2 图的存储结构及实现194

6.2.1 邻接矩阵194

6.2.2 邻接表197

6.2.3 十字链表202

6.2.4 邻接多重表202

6.2.5 边集数组203

6.2.6 图的存储结构的比较204

6.3 图的连通性205

6.3.1 无向图的连通性205

6.3.2 有向图的连通性205

6.3.3 生成树和生成森林206

6.4 应用举例206

6.4.1 最小生成树206

6.4.2 最短路径211

6.4.3 aov网与拓扑排序216

6.4.4 aoe网与关键路径220

6.4.5 校园最短路径问题223

习题6 224

思考题6 227

第7章 查找技术229

7.1 概述229

7.1.1 查找的基本概念229

7.1.2 查找算法的性能230

7.2 线性表的查找技术231

7.2.1 顺序查找231

7.2.2 折半查找233

7.2.3 斐波那契查找236

7.2.4 插值查找237

7.3 树表的查找技术238

7.3.1 二叉排序树238

7.3.2 平衡二叉树245

7.4 散列表的查找技术249

7.4.1 概述249

7.4.2 散列函数的设计251

7.4.3 处理冲突的方法253

7.4.4 散列查找的性能分析257

7.4.5 开散列表与闭散列表的比较258

习题7 260

思考题7 262

第8章 排序技术263

8.1 概述263

8.1.1 排序的基本概念263

8.1.2 排序算法的性能265

8.2 插入排序265

8.2.1 直接插入排序265

8.2.2 希尔排序268

8.3 交换排序270

8.3.1 起泡排序270

8.3.2 快速排序272

8.4 选择排序277

8.4.1 简单选择排序277

8.4.2 堆排序279

8.5 归并排序284

8.5.1 二路归并排序的非递归实现284

8.5.2 二路归并排序的递归实现288

8.6 各种排序方法的比较289

习题8 292

思考题8 294

第9章 索引技术297

9.1 索引的基本概念297

9.2 线性索引技术298

9.2.1 稠密索引298

9.2.2 分块索引299

9.2.3 多重表300

9.2.4 倒排表300

9.3 树形索引301

9.3.1 2-3树302

9.3.2 b-树304

9.3.3 b+树308

习题9 311

参考文献313