数据结构与算法 C++PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法 C++PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 绪论1

1.1 数据类型与数据结构1

1.2 数据类型（数据结构）的实现2

1.3 面向对象的设计和ADT4

1.3.1 面向函数的数据结构4

1.3.2 面向对象的数据结构4

1.3.3 在C++中的数据结构的构造5

1.4 算法12

1.5 时间复杂性的度量13

1.5.1 大O表示法15

1.5.2 大Ω，？及小o表示法19

1.6 有效算法的重要性19

1.7 渐进的空间复杂性21

2 线性表22

2.1 线性表的定义及ADT22

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

2.2.1 顺序表类24

2.2.2 顺序表的基本操作25

2.3 线性表的链接存储结构30

2.3.1 链表的抽象数据类型32

2.3.2 链表迭代器类32

2.3.3 单链表类、基本操作及迭代器的实现34

2.4 单向循环链表40

2.5 双链表、双向循环链表41

2.6 一元多项式的加法43

3 栈和队列48

3.1 栈48

3.1.1 栈的定义和抽象数据类型48

3.1.2 栈的顺序存储49

3.1.3 栈的链式存储53

3.2 队列55

3.2.1 队列的定义和抽象数据类型56

3.2.2 队列的顺序存储56

3.2.3 队列的链式存储60

3.3 优先队列62

3.4 栈和队列的应用64

3.4.1 括号配对检查64

3.4.2 中缀式和后缀式68

3.4.3 简单计算器的实现70

3.4.4 Josephus问题75

4 串77

4.1 串、存储、串的基本运算77

4.1.1 串定义及相关概念77

4.1.2 串的存储77

4.1.3 串的基本操作78

4.2 字符串类79

4.3 串的模式匹配84

4.3.1 Brute-Force算法（BF算法）84

4.3.2 KMP算法85

5 树及二叉树90

5.1 树的定义和术语90

5.2 二叉树92

5.2.1 二叉树的定义92

5.2.2 二叉树的性质93

5.2.3 二叉树的存储结构95

5.3 二叉树的遍历100

5.3.1 前序遍历100

5.3.2 中序遍历101

5.3.3 后序遍历102

5.4 二叉树遍历的迭代器类104

5.4.1 前序遍历迭代器类105

5.4.2 后序遍历迭代器类106

5.4.3 中序遍历迭代器类108

5.5 中序穿线树109

5.6 最优二叉树及其应用114

5.6.1 基本概念114

5.6.2 哈夫曼算法的实现116

5.6.3 哈夫曼编码118

5.7 树和森林120

5.7.1 树的存储结构120

5.7.2 树、森林与二叉树的转换122

5.7.3 树和森林的遍历123

6 查找126

6.1 静态查找技术126

6.1.1 顺序查找128

6.1.2 折半查找130

6.1.3 插值查找133

6.2 二叉排序树133

6.2.1 二叉排序树的抽象数据类型133

6.2.2 基本操作136

6.2.3 顺序统计142

6.3 平衡二叉排序树（AVL树）145

6.3.1 插入操作146

6.3.2 删除操作153

6.3.3 最大高度155

6.4 红-黑树156

6.4.1 插入操作157

6.4.2 自顶向下的删除操作160

6.4.3 红-黑树的实现161

6.5 B-树和B+树165

6.5.1 B-树166

6.5.2 B-树的查找分析167

6.5.3 插入操作168

6.5.4 删除操作170

6.5.5 B+树171

6.6 哈希方法173

6.6.1 常用的散列函数173

6.6.2 线性探测法176

6.6.3 二次探测法179

6.6.4 链法184

7 图186

7.1 图的基本概念186

7.1.1 图的概念、术语186

7.1.2 图的抽象数据类型189

7.2 图的存储表示190

7.2.1 邻接矩阵和加权邻接矩阵190

7.2.2 邻接表193

7.2.3 邻接多重表198

7.2.4 十字链表199

7.3 图的遍历和连通性199

7.3.1 深度优先搜索DFS200

7.3.2 广度优先搜索BFS202

7.3.3 优先度优先搜索PFS204

7.3.4 有向图的强连通分量204

7.4 最小代价生成树205

7.4.1 普里姆算法206

7.4.2 克鲁斯卡尔算法209

7.5 最短路径问题211

7.5.1 单源最短路径211

7.5.2 所有顶点对之间的最短路径215

7.6 AOV网和AOE网217

7.6.1 拓扑排序218

7.6.2 关键路径222

8 排序230

8.1 引言230

8.2 合并排序231

8.2.1 合并排序的来源231

8.2.2 算法分析233

8.3 用比较法进行排序的时间下界234

8.4 选择排序和堆排序235

8.4.1 选择排序235

8.4.2 堆排序236

8.4.3 堆和优先队列、最左树246

8.5 插入排序和希尔排序249

8.5.1 简单插入排序249

8.5.2 折半插入排序251

8.5.3 希尔排序252

8.6 快速排序253

8.6.1 快速排序的基本原理253

8.6.2 快速排序的分析255

8.6.3 算法的实现257

8.7 基数排序260

8.7.1 多关键字排序261

8.7.2 口袋排序法262

9 算法设计的基本方法265

9.1 分治法265

9.1.1 最大最小问题265

9.1.2 Strassen矩阵乘法269

9.1.3 顺序统计271

9.2 动态规划276

9.2.1 货郎担问题276

9.2.2 多级图问题278

9.2.3 最优二叉查找树281

9.3 回溯法286

9.3.1 皇后问题287

9.3.2 背包问题290

9.4 分支限界法296

9.4.1 n后问题296

9.4.2 背包问题297

9.4.3 单源最短路径问题299

9.4.4 电路板排列302

10 标准模板库307

10.1 名字空间307

10.2 基本概念309

10.2.1 容器309

10.2.2 迭代器309

10.2.3 算法310

10.2.4 函数对象311

10.3 标准容器313

10.3.1 向量313

10.3.2 表317

10.3.3 双端队列318

10.3.4 堆栈320

10.3.5 队列321

10.3.6 优先队列321

10.3.7 排序323

10.3.8 集和多集327

10.3.9 映射和多重映射330

参考文献332