《数据结构》求取 ⇩

目录1

第一章 概论1

1.1 为什么要研究数据结构1

1.2 数据结构的概念2

1.2.1 几个基本概念2

1.2.2 数据结构4

1.3 算法和抽象数据类型的描述7

1.3.1 算法及其描述7

1.3.2 算法评价和算法分析7

1.3.3 程序设计步骤和算法实例10

1.3.4 抽象数据类型的描述13

习题17

第二章 线性表18

2.1 线性表18

2.1.1 线性表的定义和特点18

2.1.2 线性表上的操作说明19

2.2 顺序存储实现线性表23

2.3 链接存储实现线性表33

2.3.1 单链表33

2.3.2 循环链表42

2.3.3 双向链表44

2.3.4 对称链表46

2.3.5 静态链表49

2.3.6 三元整系数多项式的算术运算51

2.4 索引存储实现线性表57

2.5 动态存储管理59

2.5.1 边界标识法60

2.5.2 伙伴系统67

2.6 广义表72

习题78

第三章 数组、栈和队列81

3.1 数组的顺序分配81

3.1.1 数组的顺序分配81

3.1.2 特殊矩阵83

3.2.1 顺序存储85

3.2 稀疏矩阵85

3.2.2 矩阵的转置87

3.2.3 正交（十字）链表91

3.3 栈94

3.3.1 栈的定义及其说明94

3.3.2 数组实现的栈96

3.3.3 链表实现的栈99

3.4 栈的应用实例101

3.4.1 后缀表达式的求值101

3.4.2 地图着色问题106

3.5 栈与递归108

3.5.1 如何实现递归109

3.5.2 采用递归算法的问题111

3.5.3 递归转换为非递归114

3.6 队列119

3.6.1 队列及其说明119

3.6.2 循环数组实现的队列120

3.6.3 链表实现的循环队列124

习题125

第四章 字符串129

4.1 串及其说明129

4.1.1 串的概念129

4.1.2 串的说明130

4.2 串的存储结构132

4.2.1 顺序存储132

4.2.2 链接存储133

4.3 串的模式匹配134

4.3.1 简单的模式匹配算法134

4.3.2 无回溯匹配算法135

4.3.3 从模式末端往前匹配算法140

4.3.4 模式匹配KMP-BM算法142

4.3.5 字符串的广义匹配145

习题147

5.1.1 树的定义149

5.1 基本概念149

第五章 树149

5.1.2 基本术语150

5.2 二叉树151

5.2.1 二叉树的定义151

5.2.2 二叉树的性质153

5.2.3 二叉树的说明155

5.2.4 二叉树的存储结构157

5.3 遍历二叉树160

5.3.1 二叉树三种遍历的递归算法161

5.3.2 二叉树三种遍历的非递归算法165

5.3.3 巧用二叉树遍历递归算法169

5.4.1 建立线索树174

5.4 线索二叉树174

5.4.2 检索线索二叉树中结点176

5.4.3 在中序线索树中插入结点178

5.5 树和森林179

5.5.1 森林和二叉树的转换179

5.5.2 遍历树和森林180

5.5.3 树的存储结构181

5.6 哈夫曼树及其应用188

5.6.1 扩充二叉树和哈夫曼树定义188

5.6.2 建立（构造）哈夫曼树的方法191

5.6.3 哈夫曼树的应用195

5.7 树的应用198

5.7.1 用树结构表示集合199

5.7.2 判定树201

5.7.3 表达式求值203

习题206

第六章 图211

6.1 图的基本概念212

6.2 图的存储表示法215

6.2.1 图的矩阵表示法215

6.2.2 图的邻接表表示法218

6.3 图的运算222

6.4.1 深度优先搜索（depth first search）225

6.4 图的遍历225

6.4.2 宽度优先搜索（breadth first search）228

6.4.3 图中两顶点间所有简单路径231

6.5 拓扑排序和关键路径233

6.5.1 拓扑排序（topological sort）233

6.5.2 关键路径（critical path）237

6.6 最小代价生成树243

6.6.1 Prim算法244

6.6.2 Kruskal算法247

6.7 最短路径253

6.7.1 单源最短路径254

6.7.2 每对顶点之间的最短路径258

习题261

第七章 查找263

7.1 集合与查找263

7.2 有序表查找266

7.2.1 顺序查找（sequential search）267

7.2.2 对半查找268

7.2.3 一致对半查找272

7.2.4 斐波那契（Fibonacci）查找274

7.2.5 索引顺序查找278

7.3 树表查找281

7.3.1 二叉排序树281

7.3.2 二叉平衡树291

7.3.3 B-树309

7.3.4 键树（key tree）317

7.4 散列表查找325

7.4.1 散列表325

7.4.2 散列函数327

7.4.3 冲突调节328

习题332

第八章 内部排序334

8.1 基本概念334

8.2 插入排序335

8.2.1 直接插入排序335

8.2.2 希尔排序336

8.3.1 冒泡排序339

8.3 交换排序339

8.3.2 快速排序340

8.4 选择排序343

8.4.1 简单选择排序343

8.4.2 堆排序344

8.5 合并排序347

8.5.1 两路合并排序347

8.5.2 自然两路合并排序350

8.6 基数排序352

习题356

9.1.1 磁带存储器359

第九章 文件359

9.1 外存储器简介359

9.1.2 磁盘存储器361

9.2 文件的基本概念363

9.3 顺序文件366

9.4 散列文件369

9.5 索引文件370

9.5.1 ISAM文件371

9.5.2 VSAM文件376

9.6 多关键字文件378

9.6.1 多重表文件379

9.6.2 倒排文件380

习题381

第十章 外部排序383

10.1 外排序、初始游程、多路合并383

10.1.1 外排序383

10.1.2 初始游程的生成383

10.1.3 多路合并387

10.2 磁盘排序391

10.3 磁带排序392

习题397

11.1 算法分析技术398

11.1.1 空间分析398

第十一章 算法分析和设计技术398

11.1.2 时间分析401

11.2 算法设计技术408

11.2.1 分治法409

11.2.2 贪心法410

11.2.3 动态规划法412

11.2.4 回溯法420

11.2.5 分枝界限法424

习题431

第十二章 数据结构的程序设计实例434

附录 名词索引468

参考文献475