数据结构与算法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 字符串的特征向量N 80

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 VSAM 351

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