数据结构教程 抽象数据类型描述 C语言版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

数据结构教程 抽象数据类型描述 C语言版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 数据类型5

1.2.3 抽象数据类型5

1.2.4 数据结构6

1.3 抽象数据类型7

1.3.1 抽象数据类型的描述7

1.3.2 抽象数据类型的说明7

1.3.3 抽象数据类型的表示10

1.3.4 实现的独立性12

1.3.5 一个复数抽象数据类型13

1.4 算法分析16

1.4.1 算法的概念17

1.4.2 算法的时间复杂性19

1.4.3 大○运算规则21

1.4.4 时间复杂性分析23

1.4.5 再论增长率的决定作用27

1.4.6 算法的空间复杂性28

习题一29

第2章 线性表、数组和串30

2.1 抽象数据类型List30

2.2.1 数组实现34

2.2 线性表的实现34

2.2.2 指针实现——链表40

2.2.3 记住当前位置的线性表47

2.2.4 游标实现48

2.3 特殊链表51

2.3.1 循环链表51

2.3.2 双向链表54

2.4 应用举例——模拟存储管理56

2.4.1 存储空间的分配57

2.4.2 存储空间的释放59

2.4.3 存储管理的堆实现62

2.5 数组70

2.5.1 数组的结构70

2.5.2 矩阵的压缩存储71

2.6 串79

2.6.1 抽象数据类型String79

2.6.2 串的表示和实现81

2.6.3 串的模式匹配算法84

习题二91

第3章 栈和队列93

3.1 栈的数据类型93

3.1.1 栈的概念93

3.1.2 抽象数据类型Stack94

3.1.3 栈与子程序调用96

3.2 栈的实现98

3.2.1 栈的数组实现98

3.2.2 栈的链接实现101

3.2.3 多个栈共享一个存储区103

3.3 队列108

3.3.1 抽象数据类型Queue108

3.3.2 队列的数组实现110

3.3.3 队列的链接实现114

3.4 算术表达式的计算116

3.4.1 计算后缀表达式116

3.4.2 将中缀表达式转变为后缀表达式119

习题三123

第4章 树125

4.1 树的基本概念和术语126

4.1.1 树的定义126

4.1.2 树的术语127

4.2.1 树的存储形式129

4.2 一般树129

4.2.2 树的遍历131

4.2.3 树的表示132

4.3 二叉树133

4.3.1 二叉树的概念133

4.3.2 二叉树的存储形式134

4.3.3 有序树与二叉树的转化135

4.3.4 抽象数据类型BinaryTree137

4.3.5 二叉树的表示和实现140

4.4 遍历二叉树142

4.4.1 前序遍历142

4.4.2 中序遍历146

4.4.3 后序遍历148

4.5.2 抽象数据类型BST151

4.5.1 二叉排序树的概念151

4.5 二叉排序树151

4.5.3 二叉排序树的查找153

4.5.4 在二叉排序树中插入一个结点155

4.5.5 在二叉排序树中删除结点156

4.6 穿线二叉树159

4.6.1 穿线树的概念159

4.6.2 构造中序穿线树162

4.6.3 在穿线树上插入一个结点163

4.6.4 用游标实现的穿线二叉树165

4.7 最优二叉搜索树166

4.7.1 最优二叉搜索树概念166

4.7.2 哈夫曼编码树167

4.7.3 哈夫曼算法的实现170

4.8 堆和优先队列172

4.8.1 堆的数据结构173

4.8.2 抽象数据类型PQueue174

4.8.3 用堆实现优先队列175

4.9 背包问题179

4.9.1 问题的提出179

4.9.2 查找解答树180

4.9.3 用回溯法解背包问题183

4.9.4 用约束查找法解背包问题186

习题四187

第5章 无向图190

5.1 基本概念190

5.1.1 引言190

5.1.2 定义和术语191

5.2 抽象数据类型Graph193

5.3 图的表示和实现194

5.3.1 图的邻接矩阵的表示和实现195

5.3.2 代价邻接矩阵199

5.3.3 图的邻接表的表示和实现199

5.3.4 图的邻接多重表表示205

5.3.5 图的边表表示207

5.4 图的遍历208

5.4.1 深度优先搜索DFS208

5.4.2 广度优先搜索BFS210

5.4.3 优先度优先搜索PFS211

5.5 生成树和最小代价生成树212

5.5.1 生成树212

5.5.2 最小代价生成树215

5.6 割点和双连通分量223

5.7 货郎担问题227

5.7.1 问题的提出227

5.7.2 用贪心法解TSP问题228

5.7.3 局部搜索法229

习题五232

第6章 有向图235

6.1 有向图的概念和表示235

6.1.1 有向图的概念235

6.1.2 有向图的表示和遍历235

6.1.3 状态表236

6.2 单源最短路径237

6.2.1 迪杰斯特拉算法的正确性237

6.2.2 迪杰斯特拉算法的实现和分析238

6.3 所有顶点间的最短路径和传递闭包241

6.3.1 弗洛伊德算法241

6.3.2 传递闭包244

6.3.3 求赋权有向图的中心244

6.4 强连通分量246

6.5 无圈有向图248

6.5.1 拓扑排序248

6.5.2 关键路径249

习题六253

第7章 集合和查找技术254

7.1 抽象数据类型Set254

7.2 集合的表示和实现257

7.2.1 用位向量实现集合257

7.2.2 用有序链接表实现集合259

7.3 查找表261

7.3.1 查找表的概念261

7.3.2 顺序查找表262

7.3.3 有序表的查找264

7.3.4 分块查找266

7.4 散列技术267

7.4.1 字典和哈希表267

7.4.2 哈希表的表示和实现269

7.4.3 哈希函数的选择274

7.4.4 冲突处理276

7.5 MergeFind抽象数据类型279

7.5.1 定义和概述279

7.5.2 MergeFind的树实现280

7.5.3 加权合并282

7.5.4 路径压缩284

7.5.5 MFSet的应用285

习题七286

第8章 排序288

8.1 排序的概念288

8.2 简单排序方法289

8.2.1 选择排序290

8.2.2 冒泡排序291

8.2.3 插入排序294

8.3 分治法排序297

8.3.1 合并排序297

8.3.2 快速排序303

8.4.1 堆排序309

8.4 其他的比较型排序方法309

8.4.2 希尔排序313

8.4.3 二次选择排序316

8.5 分布型排序方法317

8.5.1 基数排序317

8.5.2 散列排序321

8.6 内部排序算法的比较324

8.7 外部排序325

8.7.1 多路合并326

8.7.2 简单合并排序329

8.7.3 自然分配331

8.7.4 多阶段合并排序332

8.7.5 菲波那契分布的多阶段合并排序333

习题八337

9.1.1 各级基本术语339

第9章 文件339

9.1 文件的基本概念339

9.1.2 文件的操作340

9.2 顺序文件343

9.3 索引文件348

9.3.1 索引非顺序文件348

9.3.2 索引顺序文件349

9.4 散列文件351

9.5 多关键字文件352

9.5.1 链表文件和多重链表文件352

9.5.2 倒排文件354

习题九355

10.1.1 实习的目的和要求356

10.1 数据结构实习指导356

第10章 数据结构实习356

10.1.2 实习步骤357

10.2 实习报告范例——迷宫问题360

10.2.1 问题定义360

10.2.2 系统开发361

10.2.3 源程序清单、输入数据及运行结果367

10.3 实习题376

10.3.1 线性结构376

10.3.2 树形结构380

10.3.3 图形结构381

10.3.4 集合与查找技术382

10.3.5 排序383

参考文献385