数据结构 C++版PDF格式文档图书下载

第1章 绪论 1

1.1 数据结构的研究内容 1

1.2 数据结构的基本概念和相关术语 3

1.3 算法和算法分析 8

1.3.1 算法的概念 8

1.3.2 算法效率和存储量的估算方法 9

1.4 习题 11

第2章 线性表 13

2.1 线性表的基本概念 13

2.2 线性表的顺序存储结构 14

2.3 线性表的链式存储结构 19

2.3.1 线性链表 19

2.3.2 循环链表 27

2.3.3 双向链表 28

2.3.4 静态链表 31

2.4 一元多项式的表示和相加运算 35

2.5 习题 38

第3章 栈和队列 41

3.1 栈 41

3.1.1 栈的概念和抽象数据类型 41

3.1.2 栈的顺序存储结构 42

3.1.3 栈的链式存储结构 44

3.1.4 表达式求值 46

3.2 队列 50

3.2.1 队列的概念和抽象数据类型 50

3.2.2 队列的链式存储结构 52

3.2.3 队列的顺序存储结构——循环队列 54

3.3 栈和队列的应用实例 57

3.3.1 停车场管理 57

3.3.2 银行业务模拟 58

3.4 递归 62

3.4.1 递归的基本概念 62

3.4.2 递归算法设计 63

3.4.3 递归过程和递归工作栈 68

3.5 习题 69

第4章 数组和矩阵压缩存储 72

4.1 数组的逻辑特点 72

4.2 数组的存储结构 73

4.3 矩阵的压缩存储 75

4.3.1 特殊矩阵的压缩存储方法 75

4.3.2 稀疏矩阵的概念 77

4.3.3 稀疏矩阵的三元组表表示 79

4.3.4 稀疏矩阵的十字链表表示 84

4.4 习题 87

第5章 串 88

5.1 串的基本概念 88

5.2 串的存储结构 89

5.2.1 串的顺序存储结构 89

5.2.2 串的链式存储结构 91

5.3 串操作的实现 92

5.4 串的模式匹配 95

5.4.1 简单的模式匹配算法 96

5.4.2 KMP算法 97

5.5 建立词索引表 100

5.6 习题 103

第6章 广义表 105

6.1 广义表的基本概念 105

6.2 广义表的存储结构 107

6.3 广义表的基本运算 109

6.4 多元多项式的表示 112

6.5 习题 114

第7章 树 116

7.1 树的基本概念 116

7.1.1 树的定义 116

7.1.2 树的基本术语 117

7.1.3 树的抽象数据类型 118

7.2 二叉树的概念和存储结构 119

7.2.1 二叉树的定义 119

7.2.2 二叉树的性质 120

7.2.3 二叉树的存储结构 121

7.3 二叉树的数据类型 123

7.4 二叉树的遍历 125

7.4.1 先序遍历二叉树 126

7.4.2 中序遍历二叉树 127

7.4.3 后序遍历二叉树 129

7.4.4 按层次遍历二叉树 130

7.4.5 二叉树遍历的应用例子 131

7.5 线索二叉树 135

7.5.1 线索二叉树的概念 135

7.5.2 中序线索二叉树和中序线索链表 137

7.6 树和森林 139

7.6.1 树的存储结构 139

7.6.2 树、森林与二叉树的转换 145

7.6.3 树和森林的遍历 146

7.7 哈夫曼树及其应用 148

7.7.1 哈夫曼树 148

7.7.2 哈夫曼编码 150

7.8 习题 152

第8章 图 156

8.1 图的基本概念 156

8.2 图的存储结构 160

8.2.1 数组表示 160

8.2.2 邻接表 164

8.2.3 十字链表 169

8.2.4 邻接多重表 171

8.3 图的遍历 172

8.3.1 深度优先遍历 172

8.3.2 广度优先遍历 174

8.4 有向无环图及其应用 175

8.4.1 拓扑排序 175

8.4.2 关键路径 179

8.5 最小生成树 182

8.5.1 普里姆算法 182

8.5.2 克鲁斯卡尔算法 185

8.6 最短路径 186

8.6.1 求从一个源点到其他各顶点的最短路径 186

8.6.2 求任意两个顶点之间的最短路径 189

8.7 习题 190

第9章 查找 193

9.1 概述 193

9.2 线性表的查找 194

9.2.1 顺序查找 194

9.2.2 折半查找 196

9.2.3 斐波那契查找 197

9.3 线性索引结构 198

9.3.1 线性稠密索引 199

9.3.2 分块索引 199

9.4 二叉排序树 200

9.4.1 二叉排序树的概念 201

9.4.2 二叉排序树的查找 201

9.4.3 二叉排序树的插入 202

9.4.4 二叉排序树的删除 204

9.4.5 二叉排序树的查找性能分析 206

9.5 平衡二叉树 207

9.5.1 平衡二叉树的概念和基本旋转操作 207

9.5.2 平衡二叉树的平衡旋转 209

9.5.3 在平衡二叉树上插入元素 211

9.6 B树 213

9.6.1 B树的基本概念和查找操作 213

9.6.2 B树的插入操作 215

9.6.3 B树的删除操作 217

9.6.4 B＋树的基本概念 218

9.7 键树 219

9.8 散列表 223

9.8.1 散列表的基本概念 223

9.8.2 散列函数的构造方法 224

9.8.3 处理冲突的方法 226

9.8.4 散列表的查找方法 227

9.9 习题 228

第10章 排序 230

10.1 排序的基本概念 230

10.2 插入排序 231

10.2.1 直接插入排序 231

10.2.2 折半插入排序 232

10.2.3 表插入排序 232

10.2.4 希尔排序 233

10.3 交换排序 234

10.3.1 冒泡排序 234

10.3.2 快速排序 235

10.4 选择排序 237

10.4.1 简单选择排序 237

10.4.2 树形选择排序 238

10.4.3 堆排序 239

10.5 归并排序 241

10.6 基数排序 242

10.6.1 多关键字排序 242

10.6.2 链式基数排序 243

10.7 各种内部排序方法的性能比较 246

10.8 外部排序 247

10.8.1 外部排序过程 247

10.8.2 多路平衡归并 248

10.8.3 使用置换—选择排序生成初始归并段 250

10.8.4 最佳归并树 253

10.9 习题 254

第11章 文件 256

11.1 文件概述 256

11.2 顺序文件 257

11.3 索引文件 258

11.4 散列文件 262

11.5 多关键字文件 263

11.6 习题 264

参考文献 265

查看更多关于数据结构 C++版的内容