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

1.1 算法与数据结构 1

第1章 基础知识 1

1.2 什么是数据结构 2

1.2.1 基本概念 2

1.2.2 数据的逻辑结构 3

1.2.3 数据的存储表示 4

1.2.4 数据结构的运算 5

1.3 数据抽象和抽象数据类型 6

1.3.1 抽象、数据抽象和过程抽象 6

1.3.2 封装与信息隐蔽 6

1.3.3 数据类型和抽象数据类型 7

1.3.4 数据结构与抽象数据类型 7

1.4 描述数据结构和算法 8

1.4.1 数据结构的规范 8

1.4.2 实现数据结构 9

1.5.1 算法及其性能标准 10

1.5 算法分析的基本方法 10

1.5.2 算法的时间复杂度 11

1.5.3 渐近时间复杂度 12

1.5.4 最坏、最好和平均情况时间复杂度 13

1.5.5 算法的空间复杂度 14

本章小结 14

习题 14

第2章 线性表 17

2.1 线性表ADT 17

2.2 线性表的顺序表示 18

2.3 线性表的链接表示 23

2.3.1 单链表 23

2.3.2 带表头结点的单链表 29

2.3.3 单循环链表 30

2.3.4 双向链表 31

2.4.1 项结点的C＋＋类 32

2.4 多项式的算术运算 32

2.4.2 多项式的C＋＋类 35

2.4.3 多项式类的实现 35

本章小结 38

习题 38

第3章 堆栈和队列 40

3.1 堆栈 40

3.1.1 堆栈ADT 40

3.1.2 堆栈的顺序表示 41

3.1.3 堆栈的链接表示 42

3.2 队列 43

3.2.1 队列ADT 43

3.2.2 队列的顺序表示 44

3.2.3 队列的链接表示 46

3.3 表达式计算 46

3.3.1 表达式 46

3.3.2 计算后缀表达式的值 47

3.3.3 中缀表达式转换为后缀表达式 50

3.4 递归 53

3.4.1 递归的概念 53

3.4.2 递归的实现 54

本章小结 55

习题 55

第4章 数组和字符串 57

4.1 数组 57

4.1.1 数组ADT 57

4.1.2 数组的顺序表示 58

4.1.3 一维数组的C＋＋类 58

4.2 特殊矩阵 61

4.2.1 对称矩阵 61

4.2.2 带状矩阵 61

4.3 稀疏矩阵 63

4.3.1 稀疏矩阵ADT 63

4.3.2 稀疏矩阵的顺序表示 64

4.3.3 稀疏矩阵转置 65

4.4 字符串 67

4.4.1 字符串ADT 68

4.4.2 字符串的存储表示 68

4.4.3 简单模式匹配算法 69

4.4.4 模式匹配的KMP算法 71

本章小结 75

习题 75

第5章 树 77

5.1 树的基本概念 77

5.1.1 树的定义 77

5.1.2 基本术语 78

5.2 二叉树 79

5.2.1 二叉树的定义 80

5.2.2 二叉树的性质 80

5.2.4 二叉树的存储表示 82

5.2.3 二叉树ADT 82

5.2.5 二叉树类 83

5.2.6 实现二叉树基本运算 84

5.3 二叉树的遍历 86

5.3.1 二叉树遍历算法 86

5.3.2 二叉树遍历的递归算法 88

5.3.3 二叉树遍历的应用实例 89

5.4 二叉树遍历的非递归算法 90

5.4.1 遍历器类 90

5.4.2 中序遍历器类 91

5.5 树和森林 93

5.5.1 森林与二叉树的转换 93

5.5.2 树和森林的存储表示 95

5.5.3 树和森林的遍历 97

5.6 堆和优先权队列 98

5.6.1 堆 98

5.6.2 优先权队列ADT 100

5.6.3 优先权队列类 101

5.6.4 实现优先权队列 102

5.7 哈夫曼树和哈夫曼编码 104

5.7.1 树的路径长度 104

5.7.2 哈夫曼树和哈夫曼算法 105

5.7.3 哈夫曼树类 106

5.7.4 构造哈夫曼树 106

5.7.5 哈夫曼编码 107

5.8 并查集和等价关系 109

5.8.1 并查集ADT 109

5.8.2 并查集的存储表示 109

5.8.3 并查集类 110

5.8.4 函数Union和Find 111

5.8.5 改进的函数Union和Find 111

5.8.6 按等价关系分组 112

习题 113

本章小结 113

第6章 集合与搜索 116

6.1 基本概念 116

6.1.1 集合与搜索 116

6.1.2 动态集ADT 118

6.1.3 集合的表示 119

6.2 顺序搜索 119

6.2.1 无序表的顺序搜索 119

6.2.2 有序表的顺序搜索 120

6.2.3 平均搜索长度 121

6.3 二分搜索 121

6.3.1 二分搜索算法 121

6.3.2 对半搜索 122

6.3.3 二叉判定树 123

本章小结 125

习题 125

7.1.1 二叉搜索树的定义 126

7.1 二叉搜索树 126

第7章 搜索树 126

7.1.2 二叉搜索树的搜索 127

7.1.3 二叉搜索树的插入 128

7.1.4 二叉搜索树的删除 129

7.1.5 平均情况时间分析 131

7.2 二叉平衡树 132

7.2.1 二叉平衡树的定义 132

7.2.2 二叉平衡树类 132

7.2.3 二叉平衡树的平衡旋转 133

7.2.4 二叉平衡树的插入 139

7.2.5 二叉平衡树的删除 141

7.2.6 二叉平衡树的高度 144

7.3 B-树 145

7.3.1 m叉搜索树 145

7.3.3 B-树的高度 147

7.3.2 B-树的定义 147

7.3.4 B-树的搜索 148

7.3.5 B-树的插入 148

7.3.6 B-树的删除 150

7.4 伸展树 152

本章小结 154

习题 155

8.2 跳表 156

8.1 字典 156

第8章 跳表和散列表 156

8.2.1 什么是跳表 157

8.2.2 跳表类 159

8.2.3 跳表的搜索 160

8.2.4 跳表的插入 161

8.2.5 跳表的删除 162

8.3 散列表 163

8.3.1 散列技术 163

8.3.2 散列函数 164

8.3.3 拉链法 166

8.3.4 开地址法 167

8.3.5 线性探查法 167

8.3.6 其他开地址法 171

8.3.7 性能分析 172

本章小结 173

习题 173

9.1.1 图的定义与术语 174

9.1 图的基本概念 174

第9章 图 174

9.1.2 图ADT 176

9.2 图的存储结构 178

9.2.1 图的矩阵表示法 178

9.2.2 图的邻接矩阵实现 179

9.2.3 图的邻接表表示法 182

9.2.4 图的邻接表实现 182

9.3.1 扩充的图类 185

9.3 图的遍历 185

9.3.2 深度优先遍历 186

9.3.3 宽度优先遍历 188

9.4 拓扑排序 189

9.4.1 用顶点代表活动的AOV网 189

9.4.2 什么是拓扑排序 191

9.4.3 拓扑排序算法 191

9.5 关键路径 194

9.5.1 用边代表活动的AOE网 194

9.5.2 什么是关键路径 195

9.5.3 关键路径算法 197

9.6 最小代价生成树 198

9.6.1 基本概念 198

9.6.2 普里姆算法 198

9.6.3 克鲁斯卡尔算法 200

9.7.1 最短路径问题 202

9.7 单源最短路径 202

9.7.2 迪杰斯特拉算法 203

9.7.3 选择数据结构 204

9.7.4 迪杰斯特拉算法 204

9.8 所有顶点之间的最短路径 207

9.8.1 选择数据结构 207

9.8.2 弗洛伊德算法 207

本章小结 209

习题 209

第10章 内排序 212

10.1 基本概念 212

10.2 简单排序算法 213

10.2.1 简单选择排序 213

10.2.2 直接插入排序 214

10.2.3 冒泡排序 215

10.3 快速排序 217

10.4 两路合并排序 219

10.5 堆排序 221

10.6 基数排序 222

本章小结 226

习题 227

第11章 文件和外排序 228

11.1 辅助存储器简介 228

11.1.1 主存储器和辅助存储器 228

11.1.2 磁盘存储器 228

11.2 文件 229

11.2.1 文件的基本概念 229

11.2.2 文件的组织方式 230

11.3 文件的索引结构 233

11.3.1 静态索引结构 233

11.3.2 动态索引结构 233

11.4 外排序 234

11.4.2 初始游程的生成 235

11.4.1 外排序的基本过程 235

11.4.3 多路合并 237

11.4.4 最佳合并树 239

本章小结 240

习题 241

第12章 实习指导和实习题 242

12.1 实习目的和要求 242

12.1.1 实习目的 242

12.1.2 实习要求 242

12.2 实习步骤 243

12.3 面向对象方法及其表示法 243

12.3.1 面向对象方法 243

12.3.2 表示法 245

12.4 实习报告和样例 247

12.4.1 实习报告 247

12.4.2 实习样题 247

12.4.3 实习报告样例 248

12.5 实习题 253

12.5.1 实习一 253

12.5.2 实习二 254

12.5.3 实习三 255

12.5.4 实习四 256

12.5.5 实习五 256

12.5.6 实习六 257

12.5.7 实习七 258

12.5.8 实习八 259

12.5.9 实习九 259

12.5.10 实习十 260

12.5.11 实习十一 261

附录 程序调试 262

附录1 调试步骤 262

附录2 VC＋＋调试器 263

参考文献 267