数据结构 使用C++语言描述PDF电子书下载

第1章 绪论 1

1.1 什么是数据结构 1

1.2 数据抽象与抽象数据类型 2

1.3 面向对象方法 3

1.4 C++程序设计 4

1.4.1 函数与参数传递 4

1.4.2 动态存储分配 6

1.4.3 C++类 6

1.4.4 继承性与派生类 9

1.4.5 多态性、虚函数与动态联编 10

1.4.6 纯虚函数与抽象类 11

1.4.7 模板 12

1.5 数据结构的描述 14

1.6 算法及其性能分析 16

1.6.1 算法及其性能标准 16

1.6.2 算法的空间复杂度 16

1.6.3 算法的时间复杂度 17

1.6.4 渐近时间复杂度 17

习题 18

第2章 线性表 19

2.1 线性表抽象数据类型 19

2.2 线性表的顺序表示 20

2.3 线性表的链接表示 24

2.3.1 单链表 24

2.3.2 带表头结点的单链表 29

2.3.3 循环链表 30

2.3.4 双向链表 31

2.4 多项式的算术运算 32

2.4.1 项结点的C++类 32

2.4.2 多项式的C++类 34

2.4.3 多项式类的实现 34

习题 37

第3章 栈与队列 38

3.1 栈 38

3.1.1 栈抽象数据类型 38

3.1.2 栈的顺序表示 39

3.1.3 栈的链接表示 40

3.2.2 后缀表达式求值 41

3.2.1 表达式 41

3.2 表达式计算 41

3.2.3 中缀表达式转换为后缀表达式 44

3.3 队列 46

3.3.1 队列抽象数据类型 46

3.3.2 队列的顺序表示 47

3.3.3 队列的链接表示 49

习题 50

第4章 数组与字符串 51

4.1 数组 51

4.1.1 数组抽象数据类型 51

4.1.2 数组的顺序表示 51

4.1.3 一维数组的C++类 52

4.1.4 特殊矩阵 53

4.2 稀疏矩阵 54

4.2.1 稀疏矩阵抽象数据类型 54

4.2.2 稀疏矩阵的顺序表示 55

4.2.3 稀疏矩阵的链接表示 57

4.3 字符串 61

4.3.1 字符串抽象数据类型 61

4.3.2 字符串的存储表示 62

4.3.3 字符串的模式匹配 63

习题 68

第5章 递归 70

5.1 递归与递归过程 70

5.1.1 递归的概念 70

5.1.2 递归过程 71

5.2 顺序搜索与二分搜索 73

5.2.1 顺序搜索 73

5.2.2 二分搜索 75

5.2.3 二叉判定树 76

5.3 广义表 78

5.3.1 广义表的定义 78

5.3.2 广义表的性质 78

5.3.3 广义表抽象数据类型 79

5.3.4 广义表的存储表示 79

5.3.5 广义表的算法 81

习题 81

6.1.2 基本术语 82

6.1.1 树的定义 82

6.1 树的基本概念 82

第6章 树 82

6.2 二叉树 83

6.2.1 二叉树的定义与性质 83

6.2.2 二叉树抽象数据类型 85

6.2.3 二叉树的存储表示 85

6.2.4 二叉树的遍历 88

6.2.5 二叉树遍历的非递归算法 91

6.2.6 线索二叉树 93

6.3 树与森林 96

6.3.1 森林与二叉树的转换 96

6.3.2 树与森林的存储表示 97

6.4.1 堆 99

6.3.3 树与森林的遍历 99

6.4 堆与优先权队列 99

6.4.2 优先权队列 101

6.5 哈夫曼树与哈夫曼编码 103

6.5.1 哈夫曼树 103

6.5.2 哈夫曼编码 106

习题 107

第7章 集合与搜索树 109

7.1 集合及其表示 109

7.1.1 集合与搜索 109

7.1.2 集合抽象数据类型 109

7.2.1 并查集的定义 110

7.1.3 集合的表示 110

7.2 并查集与等价关系 110

7.2.2 并查集的实现 111

7.2.3 按等价关系分组 113

7.3 二叉搜索树 114

7.3.1 二叉搜索树的定义 114

7.3.2 二叉搜索树的搜索 115

7.3.3 二叉搜索树的插入 116

7.3.4 二叉搜索树的删除 117

7.3.5 二叉搜索树的高度 119

7.4 二叉平衡树 119

7.4.1 二叉平衡树的定义 119

7.4.2 二叉平衡树的高度 120

7.4.3 二叉平衡树的平衡旋转 121

7.4.4 二叉平衡树的插入 123

7.4.5 二叉平衡树的删除 127

7.5 B-树 129

7.5.1 m叉搜索树 129

7.5.2 B-树的定义 130

7.5.3 B-树的高度 130

7.5.4 B-树的搜索 131

7.5.5 B-树的插入 131

7.5.6 B-树的删除 132

7.6 键树 134

7.6.1 键树的定义 134

7.6.2 双链树 135

7.6.3 Trie树 136

习题 137

第8章 散列与跳表 138

8.1 字典 138

8.2 跳表描述 138

8.2.1 跳表 138

8.2.2 跳表的C++类 140

8.2.3 跳表的搜索 142

8.2.4 跳表的插入 143

8.2.5 跳表的删除 144

8.3.1 散列表 145

8.3 散列表描述 145

8.3.2 散列函数 146

8.3.3 冲突调节 148

8.3.4 性能分析 153

习题 153

第9章 图 155

9.1 图的基本概念 155

9.1.1 图的定义与术语 155

9.1.2 图抽象数据类型 158

9.2 图的存储结构 159

9.2.1 矩阵表示法 159

9.2.2 邻接表表示法 163

9.2.3 邻接多重表表示法 166

9.3.1 深度优先遍历 167

9.3 图的遍历 167

9.3.2 宽度优先遍历 169

9.4 拓扑排序与关键路径 171

9.4.1 拓扑排序 171

9.4.2 关键路径 174

9.5 最小代价生成树 178

9.5.1 普里姆算法 178

9.5.2 克鲁斯卡尔算法 180

9.6 最短路径 182

9.6.1 单源最短路径 183

9.6.2 所有顶点之间的最短路径 186

习题 188

第10章 内排序 190

10.1 基本概念 190

10.2 简单排序算法 190

10.2.1 简单选择排序 190

10.2.2 直接插入排序 191

10.2.3 冒泡排序 192

10.3 快速排序 193

10.4 2路合并排序 195

10.5 基数排序 197

习题 200

11.1.1 主存储器与外存储器 201

11.1.2 磁盘存储器 201

11.1 辅助存储器简介 201

第11章 文件与外排序 201

11.2 文件 202

11.2.1 文件的基本概念 202

11.2.2 文件的组织方式 203

11.2.3 C++文件 206

11.3 文件的索引结构 207

11.3.1 静态索引结构 207

11.3.2 动态索引结构 207

11.4 外排序 208

11.4.1 外排序的基本过程 208

11.4.2 初始游程的生成 209

11.4.3 多路合并 211

11.4.4 最佳合并树 213

习题 214

附录A 面向对象系统开发方法概述 215

A1 面向对象软件生命周期 215

A2 面向对象分析 215

A3 面向对象设计 217

A4 编码实现 217

附录B 实习要求和实习题 217

B1 实习目的 217

B2 实习要求 218

B3 实习步骤 218

B4 实习报告 218

B5 实习题 219

参考文献 222