数据结构与算法 第4版PDF|Epub|txt|kindle电子书版本下载

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

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

第1章 绪论1

1.1 数据结构的研究对象1

1.2　数据结构发展概况3

1.3　抽象数据型4

1.3.1　抽象数据型的定义4

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

1.3.3　多层次抽象技术8

1.3.4　抽象数据型的优点8

1.4　算法及其复杂性9

1.4.1　算法与程序9

1.4.2　算法的复杂性及其表示9

1.4.3　最坏、最好和平均情况分析10

1.4.4　时间复杂性分析的基本方法11

1.5 逐步求精的程序设计方法13

1.5.1　如何求解问题13

1.5.2　算法的逐步求精14

1.6　关于描述语言19

1.6.1　结构体类型说明19

1.6.2　输入／输出19

1.6.3　动态存储分配19

1.6.4　引用类型参数20

1.6.5　其他21

习题22

第2章　线性表24

2.1 线性表的抽象数据型24

2.2　线性表的实现26

2.2.1　线性表的数组实现26

2.2.2　线性表的指针实现28

2.2.3　线性表的游标实现33

2.2.4　双向链接表35

2.2.5　环形链表36

2.2.6　多项式的代数运算37

2.3　栈40

2.3.1　栈的数组实现42

2.3.2　栈的指针实现44

2.3.3　栈和递归过程45

2.3.4　栈的应用45

2.4 队列48

2.4.1　队列的指针实现48

2.4.2　队列的循环数组实现50

2.4.3　队列的应用53

2.5 串54

2.5.1 串的抽象数据型54

2.5.2　串的表示56

2.5.3　模式匹配算法60

2.6　数组64

2.6.1　数组的抽象数据型64

2.6.2　数组的表示65

2.7　广义表68

习题71

第3章　树74

3.1 基本术语74

3.2　二叉树76

3.2.1　二叉树的定义及遍历76

3.2.2　二叉树的性质78

3.2.3　二叉树的抽象数据型78

3.2.4　二叉树的表示80

3.2.5　二叉树的复制87

3.3 堆88

3.4　选择树92

3.5　树94

3.5.1　树的抽象数据型94

3.5.2　树的表示96

3.6 森林和二叉树间的转换101

3.7　树的应用105

3.7.1　集合的树结构表示105

3.7.2　判定树109

3.7.3　哈夫曼树111

3.7.4　表达式求值117

习题120

第4章　图125

4.1 基本定义125

4.2　图的表示127

4.2.1　邻接矩阵127

4.2.2　邻接表128

4.3 图的搜索129

4.3.1 深度优先搜索与深度优先编号130

4.3.2　广度优先搜索与广度优先编号131

4.4　图与树的联系132

4.4.1 深度优先生成森林和广度优先生成森林132

4.4.2　无向图与开放树的联系133

4.4.3　最小生成树134

4.5　无向图的双连通性137

4.5.1　无向图的双连通分量137

4.5.2　求关节点139

4.6　搜索产生的边143

4.7 强连通性144

4.8　拓扑排序146

4.8.1　无环路有向图146

4.8.2　拓扑排序算法147

4.9　关键路径149

4.10　单源最短路径154

4.11 每一对顶点之间的最短路径157

4.11.1　Floyd算法157

4.11.2　Warshall算法159

4.11.3　求有向图的中心点161

4.12　求有向图的基本环路162

习题165

第5章　查找170

5.1 线性查找171

5.2　折半查找172

5.3 分块查找174

5.4　二叉查找树176

5.5　AVL树180

5.6　B-树与B＋树187

5.6.1　B-树及其性质188

5.6.2　B-树的插入操作189

5.6.3　B-树的删除操作190

5.6.4　B＋树191

5.7　Trie树192

5.7.1　Trie树的定义192

5.7.2　Trie树的查找操作193

5.7.3　采样策略194

5.7.4　Trie树的插入操作195

5.7.5　Trie树的删除操作195

5.8　散列法196

5.8.1　内散列表196

5.8.2　散列函数199

5.8.3　冲突的处理202

5.8.4　外散列表204

习题206

第6章　排序210

6.1 简单的排序算法211

6.1.1　气泡排序211

6.1.2　插入排序212

6.1.3　选择排序213

6.2　快速排序214

6.3 归并排序218

6.4　堆排序220

6.5　基数排序224

6.6　词典排序228

6.7 求第K个最小元素232

习题234

第7章　文件与外部排序238

7.1　文件及文件操作238

7.1.1　文件的有关概念238

7.1.2　文件操作239

7.2　文件组织240

7.2.1　顺序式文件240

7.2.2　索引文件241

7.2.3　散列文件244

7.2.4　链接式文件和多重链表文件245

7.2.5　倒排文件248

7.3　磁盘文件的归并排序249

7.3.1　K路归并251

7.3.2　并行操作的缓冲区处理253

7.3.3　初始归并段的生成254

7.4　磁带文件的归并排序255

7.4.1　平衡归并排序255

7.4.2　多阶段归并排序257

习题259

第8章　算法设计方法261

8.1 递归方程的求解261

8.1.1 与递归方程解有关的两个问题261

8.1.2　猜解法263

8.1.3　迭代法264

8.1.4　一类递归方程的展开式与通解264

8.2 分治法268

8.2.1　基本思想268

8.2.2　整数乘法269

8.2.3　求两个矩阵的乘积270

8.2.4　平衡272

8.3　贪心法273

8.3.1　基本思想273

8.3.2　背包问题274

8.4　动态规划276

8.4.1　基本思想276

8.4.2　矩阵连乘问题277

8.4.3　联赛胜负概率问题279

8.5 回溯法282

8.5.1　基本思想282

8.5.2　单词匹配问题283

8.5.3 回溯算法与解法空间的组织284

8.5.4　8皇后问题286

8.6　分枝限界法289

8.6.1　基本思想289

8.6.2　0-1背包问题290

8.6.3　旅行商问题293

习题295

参考文献298