第1章 哈希表

1.1 哈希表的基本原理

1.2 哈希表的基本概念

1.3 哈希函数的构造

1.4 哈希表的基本操作

1.5 冲突的处理

1.6 哈希表的性能分析

1.7 哈希表的应用举例

1.8 本章习题

第2章 树与二叉树

2.1 树

2.1.1 树的存储结构

2.1.2 树的遍历

2.2 二叉树

2.2.1 普通树转换成二叉树

第1章 哈希表 1.1 哈希表的基本原理 1.2 哈希表的基本概念 1.3 哈希函数的构造 1.4 哈希表的基本操作 1.5 冲突的处理 1.6 哈希表的性能分析 1.7 哈希表的应用举例 1.8 本章习题

第2章 树与二叉树 2.1 树 2.1.1 树的存储结构 2.1.2 树的遍历 2.2 二叉树 2.2.1 普通树转换成二叉树 2.2.2 二叉树的遍历 2.2.3 二叉树的其他操作 2.2.4 二叉树的形态 2.3 二叉排序树 2.4 哈夫曼二叉树 2.5 字典树 2.6 本章习题

第3章 优先队列与二叉堆 3.1 优先队列 3.2 二叉堆 3.2.1 Put操作 3.2.2 Get操作 3.3 可并堆 3.3.1 左偏树的定义 3.3.2 左偏树的基本操作 3.4 本章习题

第4章 并查集 4.1 并查集的主要操作 4.2 并查集的实现 4.2.1 并查集的数组实现 4.2.2 并查集的链表实现 4.2.3 并查集的树实现 4.3 并查集的应用举例 4.4 本章习题

第5章 线段树 5.1 线段树的应用背景 5.2 线段树的初步实现 5.2.1 线段树的结构 5.2.2 线段树的性质 5.2.3 线段树的存储 5.2.4 线段树的常用操作 5.2.4.1 线段树的构造 5.2.4.2 线段树的查询 5.2.4.3 线段树的修改 5.2.4.4 线段树的延迟修改 5.3 线段树在一些经典问题中的应用 5.3.1 逆序对问题 5.3.2 矩形覆盖问题 5.4 线段树的扩展 5.4.1 用线段树优化动态规划 5.4.2 将线段树扩展到高维 5.4.3 线段树与平衡树的结合 5.5 线段树与其他数据结构的比较 5.6 线段树的应用举例 5.7 本章习题

第6章 树状数组 6.1 树状数组的问题模型 6.2 树状数组的基本思想 6.3 树状数组的实现 6.3.1 子集的划分方法 6.3.2 查询前缀和 6.3.3 修改子集和 6.4 树状数组的常用技巧 6.4.1 查询任意区间和 6.4.2 利用SHill数组求出原数组a的某个元素值 6.4.3 找到某个前缀和对应的前缀下标index 6.4.4 成倍扩张/缩减 6.4.5 初始化树状数组 6.5 树状数组与线段树的比较 6.6 树状数组扩展到高维的情形 6.7 树状数组的应用举例 6.8 本章习题

第7章 伸展树 7.1 伸展树的主要操作 7.1.1 伸展操作 7.1.2 伸展树的基本操作 7.2 伸展树的算法实现 7.3 伸展树的效率分析 7.4 伸展树的应用举例 7.5 本章习题

第8章 Treap 8.1 Treap的基本操作 8.2 Treap的算法实现 8.3 Treap的应用举例 8.4 本章习题

第9章 平衡树 9.1 AVL树 9.2 红-黑树 9.3 SBT 9.3.1 SBT的基本操作 9.3.2 SBT的效率分析 9.3.3 SBT的算法实现 9.4 本章习题

第10章 块状链表与块状树 10.1 块状链表的基本思想 10.2 块状链表的基本操作 10.3 块状链表的扩张 10.3.1 维护区间和以及区间最值 10.3.2 维护局部数据有序化 10.3.3 维护区间翻转 10.4 块状链表与其他数据结构的比较 10.5 分块思想在树上的应用--块状树 10.6 块状链表的应用举例 10.7 本章习题

第11章 后缀树与后缀数组 11.1 后缀树的简介 11.2 后缀树的定义 11.3 后缀树的构建 11.3.1 后缀树的朴素构建算法 11.3.2 后缀树的线性时间构建算法 11.3.2.1 隐式树的朴素构建 11.3.2.2 扩展规则约定 11.3.2.3 后缀链加速 11.3.2.4 进一步加速 11.3.2.5 后缀树拓展到多串的形式 11.3.2.6 代码实现 11.3.2.7 相关证明 11.4 后缀树的应用 11.4.1 字符串(集合)的精确匹配 11.4.1.1 情形一 11.4.1.2 情形二 11.4.1.3 情形三 11.4.1.4 情形四 11.4.2 公共子串问题 11.4.2.1 情形五 11.4.2.2 情形六 11.4.2.3 情形七 11.4.2.4 情形八 11.4.2.5 情形九 11.4.3 重复子串问题 11.4.3.1 情形十 11.4.3.2 情形十一 11.4.3.3 情形十二 11.5 后缀数组的简介 11.6 后缀数组的定义 11.7 后缀数组的构建 11.7.1 一种直接的构建算法 11.7.2 倍增算法 11.7.2.1 倍增算法描述 11.7.2.2 倍增算法代码 11.7.3 由后缀树得到后缀数组 11.7.4 DC3算法和DC算法 11.7.4.1 DC3算法 11.7.4.2 DC算法 11.8 LCP的引入 11.9 后缀数组的应用 11.9.1 后缀排序的直接应用 11.9.1.1 Burrows-Wheeler变换 11.9.1.2 多模式串的匹配 11.9.2 通过引入LCP优化 11.9.2.1 多模式串的匹配 11.9.2.2 重复子串问题 11.9.2.3 最长回文子串 11.9.2.4 最长公共子串 11.9.3 后缀数组的应用举例 11.10 本章习题

第12章 树链剖分与动态树 12.1 树链剖分的思想和性质 12.2 树链剖分的实现及应用 12.3 动态树的初探 12.3.1 动态树的常用功能 12.3.2 动态树的简单情形 12.4 动态树的实现 12.4.1 动态树的基本操作及其实现 12.4.1.1 动态树的问题模型 12.4.1.2 用Splay维护实路径 12.4.2 动态树操作的时间复杂度分析 12.4.2.1 动态树操作的次数 12.4.2.2 Splay操作的平摊时间 12.5 动态树的经典应用 12.5.1 求最近公共祖先 12.5.2 并查集操作 12.5.3 求最大流 12.5.4 求生成树 12.6 动态树的应用举例 12.7 本章习题

第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 数据结构所讨论的内容 6

1.2.3 如何表示数据结构 9

1.3 抽象数据类型 10

1.3.1 什么是抽象数据类型 10

1.3.2 抽象数据类型的定义与实现 12

1.4 算法与算法分析 13

1.4.1 什么是算法 13

1.4.2 算法描述 15

1.4.3 常用的算法设计方法 16

1.4.4 算法分析 21

习题 24

上机练习题 26

第2章 线性表的顺序存储及其运算 27

2.1 线性表的概念 27

2.1.1 什么是线性表 27

2.1.2 线性表的抽象数据类型 29

2.2 顺序表及其运算实现 30

2.2.1 线性表的顺序存储--顺序表 30

2.2.2 顺序表的基本运算 31

2.2.3 顺序表应用例--求子集 36

2.3 栈 36

2.3.1 什么是栈 37

2.3.2 栈的抽象数据类型 39

2.3.3 顺序栈及其运算 39

2.4 栈应用 42

2.4.1 栈在优先级处理中的应用 42

2.4.2 栈与分治法 48

2.4.3 栈与回溯法 50

2.4.4 栈与递归 55

2.5 队列 63

2.5.1 队列及其抽象数据类型 63

2.5.2 顺序队列及其运算 64

2.5.3 队列应用例 68

* 2.5.4 优先队列 72

2.6 数组与特殊矩阵的表示 74

2.6.1 数组的顺序存储 74

2.6.2 规则矩阵的压缩存储 76

* 2.6.3 稀疏矩阵的三列二维数组表示--三元组顺序表 78

习题 81

上机练习题 82

第3章 链表 83

3.1 线性表的链式存储--线性链表 83

3.1.1 线性链表的结构特点 83

3.1.2 线性链表的运算 84

3.2 链式栈与链式队列 91

3.2.1 栈的链式存储--链式栈 91

3.2.2 队列的链式存储--链式队列 95

3.3 循环链表 98

3.3.1 循环链表的结构特点 98

3.3.2 循环链表的基本运算 99

3.3.3 链表应用例 103

*3.4 多重链表 109

3.4.1 多重链表结构 109

3.4.2 双向链表 110

*3.5 广义表 112

3.5.1 什么是广义表 113

3.5.2 广义表的存储表示 114

3.5.3 广义表的基本运算 116

习题 120

上机练习题 121

第4章 树与二叉树 122

4.1 树的基本概念 122

4.1.1 什么是树 122

4.1.2 树的性质 127

4.2 二叉树 128

4.2.1 什么是二叉树 128

4.2.2 二叉树的基本性质 128

4.2.3 二叉树的抽象数据类型 131

4.2.4 二叉树的存储结构 131

4.2.5 二叉树的遍历及其他运算 133

* 4.2.6 线索二叉树 138

4.3 二叉树应用 141

4.3.1 表达式线性化 141

4.3.2 最优二叉树 143

4.3.3 二叉搜索树 148

4.3.4 堆 154

* 4.3.5 二叉树与减治法 160

4.4 树的运算 163

4.4.1 树的抽象数据类型 163

4.4.2 树的存储结构 164

4.4.3 树的遍历 165

* 4.4.4 树的其他运算 167

* 4.5 树与回溯法 170

4.5.1 问题解的描述--解空间树 171

4.5.2 回溯法的求解过程分析--遍历解空间树 172

4.5.3 回溯法求解问题的形式化描述 174

* 4.6 森林的遍历 176

4.6.1 森林与二叉树的转换 176

4.6.2 森林的遍历 177

习题 178

上机练习题 179

第5章 图 180

5.1 图的基本概念 180

5.1.1 图的定义和概念 180

5.1.2 图的抽象数据类型 184

*5.1.3 欧拉路径 185

5.2 图的存储结构 186

5.2.1 图的邻接矩阵表示 186

5.2.2 图的邻接表表示 189

*5.2.3 图的其他表示方法 192

5.3 图的遍历 195

5.3.1 图的深度优先遍历 195

5.3.2 图的广度优先遍历 197

5.3.3 图遍历的应用 198

*5.3.4 图的连通性 200

*5.4 有向图与有向无环图 201

5.4.1 有向图的连通性和传递闭包 202

*5.4.2 有向无环图和拓扑排序 204

*5.4.3 关键路径 207

5.5 最小生成树 208

5.5.1 图的生成树与最小生成树 209

5.5.2 普里姆(Prim)算法 210

5.5.3 克鲁斯卡尔(Kruskal)算法 213

5.5.4 贪心算法 215

5.6 最短路径问题 218

5.6.1 单源最短路径 218

5.6.2 全源最短路径 220

5.6.3 动态规划算法 223

5.7 图应用例--城市间公路交通网问题 227

5.7.1 问题描述 227

5.7.2 问题求解思路 228

习题 228

上机练习题 230

第6章 查找 231

6.1 线性查找表 231

6.1.1 顺序查找 232

6.1.2 折半查找 232

*6.1.3 斐波那契查找 234

6.1.4 线性查找表的性能比较 234

6.2 二叉搜索树查找性能 235

6.3 AVL树 236

6.3.1 BST的旋转操作 237

6.3.2 AVL树的插入和平衡化旋转 238

*6.3.3 AVL树的删除 240

*6.3.4 AVL树的性能 241

6.4 B-树 242

6.4.1 多路动态搜索树 242

6.4.2 B-树的查找 243

6.4.3 B-树的插入 244

*6.4.4 B-树的删除 245

6.5 散列方法 246

6.5.1 散列技术 246

6.5.2 散列函数 247

6.5.3 冲突处理 250

6.5.4 散列的删除 252

6.5.5 散列的性能 252

6.6 静态索引结构 253

6.6.1 索引查找 253

6.6.2 索引存储方式 254

*6.6.3 索引文件结构 255

6.7 模式匹配 258

6.7.1 字符串及其ADT 258

6.7.2 字符串的存储表示 259

6.7.3 字符串的模式匹配及简单匹配算法 259

6.7.4 字符串匹配的KMP算法 260

习题 263

上机练习题 264

第7章 排序 265

7.1 排序的概念及算法性能分析 265

7.2 基本排序方法 266

7.2.1 冒泡排序 267

7.2.2 插入排序 268

7.2.3 直接选择排序 272

7.2.4 基本排序方法的比较 273

7.3 快速排序 274

7.3.1 快速排序的过程 274

7.3.2 快速排序的性能分析 275

7.4 归并排序 276

7.4.1 二路归并 276

7.4.2 自底向上的归并排序 276

7.4.3 自顶向下的归并排序 278

*7.5 锦标赛排序 279

7.6 堆排序 280

7.6.1 堆排序的思想 280

7.6.2 堆排序的实现 282

7.7 内排序方法分析 283

*7.7.1 排序方法的下界 283

7.7.2 内排序方法的比较 284

7.8 线性时间复杂度的排序算法 285

*7.8.1 计数排序 285

7.8.2 基数排序 287

7.9 外部排序 290

7.9.1 外部排序方法 290

*7.9.2 基于败者树的k路归并方法 291

*7.9.3 排序--归并的改进 292

习题 296

上机练习题 297

实验指导 298

实验一 顺序表及其应用 299

实验二 求解迷宫问题 301

实验三 简单算术表达式的处理 302

实验四 求解简单背包问题 303

实验五 链表及其应用 304

实验六 实验室机时机位的管理 305

实验七 实现Huffman编码 307

实验八 文件管理的模拟 309

实验九 求网络站点间的最短连接 312

实验十 查找最高分与次高分 314

实验十一 比赛日程安排与成绩统计 316

前言

第1章 绪论

1.1 数据结构的实践意义

1.2 数据结构的理论意义

1.3 数据结构研究的内容和关键问题

习题

第2章 线性表

2.1 线性表的概念及抽象数据类型定义

2.2 线性表的顺序存储

2.3 线性表的链式存储

2.4 线性表的应用--一元多项式的表示及相加

2.5 顺序表与链表的综合比较

习题

第3章 栈和队列

3.1 栈

3.2 队列

习题

第4章 串

4.1 串的定义与操作

4.2 串的存储结构及操作

4.3 串操作应用举例

习题

第5章 数组和广义表

5.1 数组的定义

5.2 数组的顺序表示和实现

5.3 矩阵的压缩存储

5.4 广义表

习题

第6章 树

6.1 树的定义、操作及基本术语

6.2 二叉树

6.3 遍历二叉树和线索二叉树

6.4 树和森林

6.5 哈夫曼树及其应用

习题

第7章 图

7.1 图定义和术语

7.2 图的存储结构

7.3 图的遍历

7.4 图的连通性

7.5 有向无环图及其应用

7.6 最短路径

习题

第8章 查找

8.1 查找的基本概念

8.2 静态查找表

8.3 动态查找表

8.4 哈希表

习题

第9章 排序

9.1 概述

9.2 插入排序

9.3 交换排序

9.4 选择排序

9.5 归并排序

9.6 外部排序简介

习题

第10章 文件

10.1 基本概念

10.2 顺序文件

10.3 索引文件

10.4 ISAM文件和VSAM文件

10.5 直接存取文件(散列文件)

习题

第11章 算法设计策略

11.1 分而治之(DivideandConqureAlgorithm)

11.2 贪心算法(GreedyAlgorithm)

11.3 动态规划算法(DynamicProgramming)

11.4 状态搜索策略(StateSearch)

11.5 回溯算法(BacktrakingAlgorithm)

11.6 随机算法(RandomAlgorithm)

11.7 算法设计中关键与技巧

习题

参考文献

……

本书可以作为大专院校数据结构课程的教材，也可以作为从事计算机应用开发的科技人员的参考书。本书以清华大学电子系数据结构讲义为蓝本，主要针对高等院校非计算机专业开设"数据结构"课程的需要而编写的。全书从应用的角度，重点介绍数据处理中常用的数据结构--线性表、树与二叉树、图，以及基本的数据处理技术--查找和排序方法，同时通过实例把回溯法、分治法、贪心法、动态规划法等常用的算法设计思想的应用融入其中，把数据结构的介绍和常用算法设计的讨论紧密结合，并且辅之以充足的练习题，从而使读者更具体、更深刻地理解各种常用的数据结构，及它们与算法之间的关系，以达到学以致用的目的。