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

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

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

第1章 绪论1

1.1 预备知识1

1.1.1 集合的笛卡儿积1

1.1.2 二元关系2

1.1.3 二元关系的基本性质和几种重要关系3

1.2 什么是数据结构4

1.2.1 从实际问题理解数据结构4

1.2.2 数据结构所讨论的内容6

1.2.3 如何表示数据结构9

1.3 抽象数据类型10

1.3.1 什么是抽象数据类型10

1.3.2 抽象数据类型的定义与实现12

1.4 算法与算法分析13

1.4.1 什么是算法13

1.4.2 算法描述15

1.4.3 常用的算法设计方法16

1.4.4 算法分析21

习题24

上机练习题26

第2章 线性表的顺序存储及其运算27

2.1 线性表的概念27

2.1.1 什么是线性表27

2.1.2 线性表的抽象数据类型29

2.2 顺序表及其运算实现30

2.2.1 线性表的顺序存储——顺序表30

2.2.2 顺序表的基本运算31

2.2.3 顺序表应用例——求子集36

2.3 栈36

2.3.1 什么是栈37

2.3.2 栈的抽象数据类型39

2.3.3 顺序栈及其运算39

2.4 栈应用42

2.4.1 栈在优先级处理中的应用42

2.4.2 栈与分治法48

2.4.3 栈与回溯法50

2.4.4 栈与递归55

2.5 队列63

2.5.1 队列及其抽象数据类型63

2.5.2 顺序队列及其运算64

2.5.3 队列应用例68

2.5.4 优先队列72

2.6 数组与特殊矩阵的表示74

2.6.1 数组的顺序存储74

2.6.2 规则矩阵的压缩存储76

2.6.3 稀疏矩阵的三列二维数组表示——三元组顺序表78

习题81

上机练习题82

第3章 链表83

3.1 线性表的链式存储——线性链表83

3.1.1 线性链表的结构特点83

3.1.2 线性链表的运算84

3.2 链式栈与链式队列91

3.2.1 栈的链式存储——链式栈91

3.2.2 队列的链式存储——链式队列95

3.3 循环链表98

3.3.1 循环链表的结构特点98

3.3.2 循环链表的基本运算99

3.3.3 链表应用例103

3.4 多重链表109

3.4.1 多重链表结构109

3.4.2 双向链表110

3.5 广义表112

3.5.1 什么是广义表113

3.5.2 广义表的存储表示114

3.5.3 广义表的基本运算116

习题120

上机练习题121

第4章 树与二叉树122

4.1 树的基本概念122

4.1.1 什么是树122

4.1.2 树的性质127

4.2 二叉树128

4.2.1 什么是二叉树128

4.2.2 二叉树的基本性质128

4.2.3 二叉树的抽象数据类型131

4.2.4 二叉树的存储结构131

4.2.5 二叉树的遍历及其他运算133

4.2.6 线索二叉树138

4.3 二叉树应用141

4.3.1 表达式线性化141

4.3.2 最优二叉树143

4.3.3 二叉搜索树148

4.3.4 堆154

4.3.5 二叉树与减治法160

4.4 树的运算163

4.4.1 树的抽象数据类型163

4.4.2 树的存储结构164

4.4.3 树的遍历165

4.4.4 树的其他运算167

4.5 树与回溯法170

4.5.1 问题解的描述——解空间树171

4.5.2 回溯法的求解过程分析——遍历解空间树172

4.5.3 回溯法求解问题的形式化描述174

4.6 森林的遍历176

4.6.1 森林与二叉树的转换176

4.6.2 森林的遍历177

习题178

上机练习题179

第5章 图180

5.1 图的基本概念180

5.1.1 图的定义和概念180

5.1.2 图的抽象数据类型184

5.1.3 欧拉路径185

5.2 图的存储结构186

5.2.1 图的邻接矩阵表示186

5.2.2 图的邻接表表示189

5.2.3 图的其他表示方法192

5.3 图的遍历195

5.3.1 图的深度优先遍历195

5.3.2 图的广度优先遍历197

5.3.3 图遍历的应用198

5.3.4 图的连通性200

5.4 有向图与有向无环图201

5.4.1 有向图的连通性和传递闭包202

5.4.2 有向无环图和拓扑排序204

5.4.3 关键路径207

5.5 最小生成树208

5.5.1 图的生成树与最小生成树209

5.5.2 普里姆（Prim）算法210

5.5.3 克鲁斯卡尔（Kruskal）算法213

5.5.4 贪心算法215

5.6 最短路径问题218

5.6.1 单源最短路径218

5.6.2 全源最短路径220

5.6.3 动态规划算法223

5.7 图应用例——城市间公路交通网问题227

5.7.1 问题描述227

5.7.2 问题求解思路228

习题228

上机练习题230

第6章 查找231

6.1 线性查找表231

6.1.1 顺序查找232

6.1.2 折半查找232

6.1.3 斐波那契查找234

6.1.4 线性查找表的性能比较234

6.2 二叉搜索树查找性能235

6.3 AVL树236

6.3.1 BST的旋转操作237

6.3.2 AVL树的插入和平衡化旋转238

6.3.3 AVL树的删除240

6.3.4 AVL树的性能241

6.4 B-树242

6.4.1 多路动态搜索树242

6.4.2 B-树的查找243

6.4.3 B-树的插入244

6.4.4 B-树的删除245

6.5 散列方法246

6.5.1 散列技术246

6.5.2 散列函数247

6.5.3 冲突处理250

6.5.4 散列的删除252

6.5.5 散列的性能252

6.6 静态索引结构253

6.6.1 索引查找253

6.6.2 索引存储方式254

6.6.3 索引文件结构255

6.7 模式匹配258

6.7.1 字符串及其ADT258

6.7.2 字符串的存储表示259

6.7.3 字符串的模式匹配及简单匹配算法259

6.7.4 字符串匹配的KMP算法260

习题263

上机练习题264

第7章 排序265

7.1 排序的概念及算法性能分析265

7.2 基本排序方法266

7.2.1 冒泡排序267

7.2.2 插入排序268

7.2.3 直接选择排序272

7.2.4 基本排序方法的比较273

7.3 快速排序274

7.3.1 快速排序的过程274

7.3.2 快速排序的性能分析275

7.4 归并排序276

7.4.1 二路归并276

7.4.2 自底向上的归并排序276

7.4.3 自顶向下的归并排序278

7.5 锦标赛排序279

7.6 堆排序280

7.6.1 堆排序的思想280

7.6.2 堆排序的实现282

7.7 内排序方法分析283

7.7.1 排序方法的下界283

7.7.2 内排序方法的比较284

7.8 线性时间复杂度的排序算法285

7.8.1 计数排序285

7.8.2 基数排序287

7.9 外部排序290

7.9.1 外部排序方法290

7.9.2 基于败者树的k路归并方法291

7.9.3 排序—归并的改进292

习题296

上机练习题297

实验指导298

实验一 顺序表及其应用299

实验二 求解迷宫问题301

实验三 简单算术表达式的处理302

实验四 求解简单背包问题303

实验五 链表及其应用304

实验六 实验室机时机位的管理305

实验七 实现Huffman编码307

实验八 文件管理的模拟309

实验九 求网络站点间的最短连接312

实验十 查找最高分与次高分314

实验十一 比赛日程安排与成绩统计316