数据结构与算法设计2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

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

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

第1章 结论1

1.1 问题求解1

1.2 算法表达中的抽象数据机制1

1.3 抽象数据类型4

1.3.1 抽象数据类型的基本概念4

1.3.2 使用抽象数据类型的好处6

1.3.3 数据结构、数据类型和抽象数据类型6

1.4 用 C＋＋描述数据结构与算法7

1.4.1 变量、指针和引用7

1.4.2 函数与参数传递8

1.4.3 C＋＋的类8

1.4.4 类的对象9

1.4.5 构造函数与析构函数11

1.4.6 运算符重载11

1.4.7 友元函数11

1.4.8 内联函数11

1.4.9 结构12

1.4.10 联合12

1.4.11 异常12

1.4.12 模板12

1.4.13 动态存储分配13

1.5 算法复杂性分析15

1.5.1 算法与程序15

1.5.2 算法复杂性的概念15

1.5.3 算法复杂性的渐近性态16

习题一18

第2章 表20

2.1 ADT表20

2.2 用数组实现表21

2.3 用指针实现表25

2.4 用间接寻址方法实现表31

2.5 用游标实现表34

2.6 循环链表41

2.7 双链表45

习题50

第3章 栈54

3.1 ADT栈54

3.2 用数组实现栈55

3.3 用指针实现栈58

3.4 等价类划分问题61

习题三63

第4章 队列66

4.1 ADT队列66

4.2 用指针实现队列66

4.3 用循环数组实现队列69

4.4 电路布线问题74

习题四77

第5章 串79

5.1 ADT串79

5.2 用数组实现串80

5.3 用指针实现串85

5.4 串的块链表示法86

5.5 串的堆结构86

5.6 模式匹配86

5.6.1 朴素的模式匹配算法86

5.6.2 模式匹配的KMP算法88

习题五93

第6章 排序与选择95

6.1 简单排序算法95

6.1.1 冒泡排序95

6.1.2 插入排序96

6.1.3 选择排序97

6.1.4 简单排序算法的计算复杂性97

6.2 快速排序算法98

6.2.1 算法基本思想及实现98

6.2.2 算法的性能100

6.2.3 随机快速排序算法100

6.3 合并排序算法101

6.3.1 算法基本思想及实现101

6.3.2 消除递归101

6.3.3 自然合并排序103

6.4 线性时间排序算法103

6.4.1 计数排序103

6.4.2 桶排序105

6.5 中位数与第k小元素106

6.5.1 平均情况下的线性时间选择算法106

6.5.2 最坏情况下的线性时间选择算法109

习题六109

第7章 树111

7.1 树的定义111

7.2 树的遍历113

7.3 树的表示法115

7.3.1 父结点数组表示法116

7.3.2 儿子链表表示法116

7.3.3 左儿子右兄弟表示法116

7.4 二叉树117

7.5 ADT二叉树119

7.6 二叉树的实现120

7.6.1 二叉树的顺序存储结构120

7.6.2 二叉树的结点度表示法121

7.6.3 用指针实现二叉树122

7.7 线索二叉树126

习题七128

第8章 图131

8.1 图的基本概念131

8.2 抽象数据类型ADT图134

8.3 图的表示法135

8.3.1 邻接矩阵表示法135

8.3.2 邻接表示法136

8.3.3 紧缩邻接表136

8.4 用邻接矩阵实现图137

8.4.1 用邻接矩阵实现赋权有向图137

8.4.2 用邻接矩阵实现赋权无向图140

8.4.3 用邻接矩阵实现有向图141

8.4.4 用邻接矩阵实现无向图141

8.5用邻接表实现图141

8.5.1 邻接表基类141

8.5.2 用邻接表实现有向图143

8.5.3 用邻接表实现无向图144

8.5.4 用邻接表实现赋权有向图145

8.5.5 用邻接表实现赋权无向图148

8.6 图的遍历149

8.6.1 图的搜索游标150

8.6.2 广度优先搜索152

8.6.3 深度优先搜索154

8.7 最短路径155

8.7.1 单源最短路径155

8.7.2 所有顶点对之间的最短路径159

8.8 最小生成树155

8.8.1 最小生成树性质160

8.8.2 算法161

8.8.3 算法163

8.9 图匹配166

习题八168

第9章 集合170

9.1 以集合为基础的抽象数据类型170

9.1.1 集合的定义和记号170

9.1.2 定义在集合上的基本运算171

9.1.3 集合的简单表示法171

9.2 字典179

9.2.1 实现字典的简单方法179

9.2.2 用散列表实现字典180

9.3 有序字典189

9.3.1 有序字典的定义189

9.3.2 用数组实现有序字典189

9.3.3 用二叉搜索树实现有序字典190

9.3.4 AVL树199

9.3.5 红黑树209

9.4 优先队列218

9.4.1 优先队列的定义218

9.4.2 用字典实现优先队列219

9.4.3 优先级树和堆219

9.4.4 用数组实现堆221

9.4.5 可并优先队列224

9.5 并查集224

9.5.1 并查集的定义及其简单实现229

9.5.2 用父亲数组实现并查集230

习题九233

第10章 算法设计策略236

10.1 递归与分治策略236

10.1.1 递归的概念236

10.1.2 分治法的基本思想238

10.1.3 二分搜索技术239

10.1.4 棋盘覆盖问题240

10.2 动态规划242

10.2.1 矩阵连乘问题243

10.2.2 动态规划算法的基本要素247

10.2.3 最大子段和问题250

10.3 贪心算法256

10.3.1 活动安排问题256

10.3.2 贪心算法的基本要素258

10.3.3 哈夫曼编码算法261

10.4 回溯法265

10.4.1 回溯法的算法框架265

10.4.2 符号三角形问题270

10.4.3 圆排列问题273

10.4.4 连续邮资问题275

10.4.5 回溯法的效率分析277

10.5 分支限界法280

10.5.1 分支限界法的基本思想280

10.5.2 装载问题282

10.5.3 批处理作业调度问题290

习题十295

参考文献299