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

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

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

第1章 概论1

1.1 为什么要学习数据结构1

1.2 什么是数据结构1

1.2.1 数据的逻辑结构1

1.2.2 数据的存储结构4

1.3 抽象数据类型7

1.4 算法及其特性10

1.4.1 算法10

1.4.2 计算复杂性和算法的效率11

1.5 算法的执行效率及其度量12

1.5.1 算法的渐进分析12

1.5.2 最坏、最好和平均情况14

1.5.3 时间和空间资源开销15

1.5.4 大Θ表示法及其分析规则15

1.6 数据结构的选择和评价16

习题17

第2章 线性表、栈和队列18

2.1 线性表19

2.1.1 线性表的抽象数据类型19

2.1.2 线性表的存储结构21

2.1.3 线性表运算分类21

2.2 顺序表——向量22

2.2.1 向量的类定义22

2.2.2 向量的运算23

2.3.1 单链表25

2.3 链表25

2.3.2 双链表29

2.3.3 循环链表31

2.4 线性表实现方法的比较31

2.5 栈32

2.5.1 顺序栈33

2.5.2 链式栈35

2.5.3 栈的应用——计算表达式的值36

2.5.4 栈与递归41

2.6 队列48

2.6.1 顺序队列50

2.6.2 链式队列53

习题54

2.6.3 顺序队列与链式队列的比较54

第3章 字符串56

3.1 字符串抽象数据类型56

3.1.1 基本概念56

3.1.2 String抽象数据类型61

3.2 字符串的存储结构和类定义66

3.2.1 字符串的顺序存储67

3.2.2 字符串类class String的存储结构67

3.3 字符串运算的算法实现70

3.3.1 C＋＋标准串运算的实现70

3.3.2 String串运算的实现73

3.4 字符串的模式匹配76

3.4.1 模式匹配原始算法77

3.4.2 字符串的特征向量N80

3.4.3 KMP模式匹配算法82

习题83

上机题84

第4章 二叉树85

4.1 二叉树的概念85

4.1.1 二叉树的定义及相关概念85

4.1.2 满二叉树、完全二叉树和扩充二叉树86

4.2 二叉树的主要性质88

4.3 二叉树的抽象数据类型89

4.4 周游二叉树91

4.4.1 深度优先周游二叉树91

4.4.2 广度优先周游二叉树97

4.5.1 用指针实现二叉树98

4.5 二叉树的实现98

4.5.2 空间开销101

4.5.3 用数组实现完全二叉树102

4.5.4 穿线二叉树103

4.6 二叉搜索树111

4.7 堆与优先队列116

4.8 Huffman编码树123

4.8.1 建立Huffman编码树123

4.8.2 Huffman编码及其用法126

习题128

上机题130

5.1 树的概念131

5.1.1 树和森林131

第5章 树131

5.1.2 森林与二叉树的等价转换133

5.1.3 树的抽象数据类型135

5.1.4 树的周游136

5.2 树的链式存储139

5.2.1 子结点表表示法139

5.2.2 左子结点／右兄弟结点表示法140

5.2.3 动态结点表示法141

5.2.4 动态“左子结点／右兄弟结点”二叉链表表示法143

5.2.5 父指针表示法及等价类的并查算法148

5.3 树的顺序存储155

5.3.1 带右链的先根次序表示法155

5.3.2 带双标记位的先根次序表示法156

5.3.3 带左链的层次次序表示法158

5.3.4 带度数的后根次序表示法160

5.4 K叉树161

习题161

上机题163

第6章 图165

6.1 图的基本概念165

6.2 图的抽象数据类型168

6.3 图的存储结构169

6.3.1 图的相邻矩阵表示法169

6.3.2 图的邻接表表示法174

6.4 图的周游180

6.4.1 深度优先搜索181

6.4.2 广度优先搜索182

6.4.3 拓扑排序183

6.5 最短路径问题187

6.5.1 单源最短路径187

6.5.2 每对顶点间的最短路径191

6.6 最小支撑树193

6.6.1 Prim算法194

6.6.2 Kruskal算法196

习题198

上机题201

第7章 内排序203

7.1 排序问题的基本概念203

7.2 三种O（n2）的简单排序算法206

7.2.1 插入排序206

7.2.2 冒泡排序211

7.2.3 直接选择排序213

7.2.4 简单排序算法的时间代价对比215

7.3 Shell排序217

7.4 基于分治法的排序219

7.4.1 快速排序220

7.4.2 归并排序227

7.5 堆排序231

7.6 分配排序和基数排序233

7.6.1 桶式排序233

7.6.2 基数排序235

7.7 各种排序算法的理论和实验时间代价244

7.8 排序问题的下限246

习题249

上机题253

第8章 文件管理和外排序254

8.1 主存储器和外存储器254

8.2 外存储器256

8.2.1 磁盘256

8.2.2 磁盘访问时间估算260

8.2.3 磁带262

8.3 外存文件的组织264

8.3.1 文件组织265

8.3.2 C＋＋的流文件267

8.4 缓冲区和缓冲池268

8.5 外排序271

8.5.1 置换选择排序272

8.5.2 二路外排序277

8.5.3 多路归并——选择树279

习题291

上机题293

第9章 检索294

9.1 基于线性表的检索295

9.1.1 顺序检索296

9.1.2 二分检索297

9.1.3 分块检索302

9.2 集合的检索303

9.2.1 集合的数学特性304

9.2.2 计算机中的集合304

9.3 散列方法306

9.3.1 散列函数308

9.3.2 开散列方法（拉链法）312

9.3.3 闭散列方法（开地址法）315

9.3.4 闭散列表的算法319

9.3.5 散列方法的效率分析324

习题326

上机题331

第10章 索引技术333

10.1 线性索引334

10.2 静态索引335

10.2.1 多分树335

10.2.2 ISAM－索引顺序存取方法336

10.3 倒排索引338

10.3.1 基于属性的倒排339

10.3.2 对正文文件的倒排341

10.4 动态索引343

10.4.1 B树343

10.4.2 B＋树349

10.4.3 VSAM351

10.4.4 B树的性能分析355

10.5 动态索引和静态索引性能的比较356

习题356

上机题358

第11章 高级线性结构359

11.1 多维数组359

11.1.1 特殊矩阵364

11.1.2 稀疏矩阵366

11.2 广义表372

11.2.1 广义表的存储结构374

11.2.2 广义表的周游算法378

11.3 存储管理技术380

11.3.1 可利用空间表381

11.3.2 存储的动态分配和回收385

11.3.3 伙伴系统388

11.3.4 失败处理策略和无用单元回收389

习题393

上机题393

第12章 高级树结构395

12.1 Trie结构和Patricia树395

12.2 改进的二叉搜索树399

12.2.1 最佳二叉搜索树400

12.2.2 平衡的二叉搜索树409

12.2.3 伸展树425

12.3 空间树结构428

12.3.1 k-d树429

12.3.2 PR四分树432

12.3.3 R＊树434

12.4 树形结构的应用437

12.4.1 决策树437

12.4.2 博弈树445

习题457

上机题461

参考文献469