数据结构

　　本书系统、全面地论述数据结构的重要内容，包括基本概念和方法、线性表、链表、树、堆结构、图、排序和搜索结构。在充分继承国内外经典教材的合理体系结构和优秀内容的基础上，结合国内实际教学情况编写，内容系统、精炼，且经过优化整合，在深度和广度上有明显增强；突出重点、难点，强调分析问题和解决问题的方法，以及产生这些方法的背景。书中内容都经过编者深入研究，且在教学实践中反复验证，因而较易理解。本书注重启发创新思维，培养能力；概念准确，逻辑性强；自然引用面向对象设计思想，用C++语言描述算法。本书适于作为计算机科学与技术、软件工程以及相关专业的教材，也可供从事相关工作的科技与工程人员参考。本书前言设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。数据和世上万物一样，都是具有结构的。因此，人们很自然地用数据结构表示应用领域的被处理对象。为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应操作。数据结构的实现是由下一层数据结构表示上一层数据结构，直至由程序设计语言提供的基本数据类型表示的过程。评价数据结构表示优劣的标准主要是其能否方便且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。因此，数据结构的定义、表示以及操作的实现相互关联，都是数据结构研究的重要内容。计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。通过多层表示，完成计算机对应用领域问题的求解过程。在此，中间层数据结构起着核心作用。数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。这些结构不仅为我们提供了设计软件系统的有用工具，而且向我们展示了在广泛的应用领域表示与解决问题的精巧思路和技术。系统地学习和掌握数据结构知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是十分重要的。因此，数据结构早已成为计算机科学与技术和软件工程等专业的核心课程。数据结构课程内容丰富，涵盖了计算机科学与技术的许多重要的成果，分析问题和解决问题的思路和方法新颖，创新点多，技巧性强，对学生专业素质的培养作用明显，但同时也是一门较难学习的课程。我校计算机科学与工程系开设的"数据结构"课程一直采用美国南加州大学教授E.Horowitz等编著的《数据结构基础》作为教材。该书注重培养学生分析问题、解决问题的能力，在数据结构和算法设计以及时空复杂性分析的深度和广度方面特色明显。但在教学中也感到该书内容的表达形式学生较难理解，方法和技术的论述还不够简明扼要，有的内容不够精炼，部分章节存在一些小错误，教学效果较多依赖于教师的讲解。为此，编者在充分继承该书体系结构和内容优点的基础上，吸收其他教材长处，进行优化整合，并结合自身多年的教学改革与实践经验，编写了这本教材，力图使其系统全面，内容深刻，表达简洁，易于理解，以适应计算机科学与技术及相关专业的教学需要。本书共分为8章。第1章论述数据结构的基本概念和方法，包括数据结构与软件系统，数据抽象与封装，算法，递归，性能分析、性能测量，以及效率与权衡等。特别引入了代价分摊分析方法，将相关的操作序列联系起来分析，从而得到更接近实际代价的结果。此外，还从软件重用的角度描述了C++的模板机制。第2章介绍线性表的概念及其顺序表示方法，讨论了通过线性表表示的多项式、稀疏矩阵和字符串等结构。在描述著名的字符串模式匹配算法KMP时，采用了简明易懂的图示方法。还通过两个字符串的最长公共子序列问题的求解，展示了利用动态规划改进算法效率的方法。由于栈和队列是受限的线性表，因此也被整合到这一章。此章不仅给出了通用栈和队列的实现方法，还分别通过求解迷宫问题、表达式计算以及机场模拟问题描述了栈和队列的应用。第3章论述以链表形式实现线性表的方法和技术，讨论了遍历通用模板类容器对象的游标技术。还介绍了广义表的功能及其实现方法，并结合C++的动态类型，讨论了异构表的实现方法。第4章介绍最基本的非线性结构：树，包括树和森林的概念、二叉树、二叉树的遍历及应用、线索二叉树、胜者树、败者树、森林的二叉树表示及遍历、树在并查集问题中的应用和二叉树计数等。特别给出了有一定难度的中序线索二叉树的后序遍历算法，还给出了生成所有可能的二叉树的算法。第5章介绍支持各种优先队列的堆结构，包括最大堆、最大最小堆、双堆、左偏树、二项式堆和斐波纳契堆。在分析二项式堆和斐波纳契堆的性能时，采用了代价分摊方法。第6章介绍更普遍的非线性结构：图，包括图的定义和表示方法、图的遍历、图的连通性、最小代价生成树、最短路径和传递闭包以及活动网络等。特别讨论了应用斐波纳契堆改进最短路径算法性能的技术。在数据结构中，数据元素之间的次序是一种重要的关系。按照数据元素的特定属性对其进行排序是最频繁的计算任务之一。第7章介绍各种典型的排序方法，包括插入排序、希尔排序、快速排序、归并排序、堆排序、基数排序、基于链表和映射表排序结果的顺序化以及外排序。第8章介绍符号表概念以及实现符号表的各种结构，包括二叉查找树、AVL树、2-3树、Splay树、B树、B+树、Trie、静态散列和动态散列等，特别分析了二叉查找树的平均性能。在分析Splay树的性能时，采用了代价分摊方法。此外，还论述了上述结构的演变关系，帮助读者理解其设计思想。本书可供各种层次的读者选用，既适用于教学，也可供从事相关工作的科技与工程人员参考。可以按"数据结构基础"（64学时，必修）和"高级数据结构"（24～32学时，选修）两门课组织教学。本书的2.4、2.9、3.10、4.5、4.8、4.9、5.2～5.6、6.4、7.8、8.4、8.5、8.7和8.9节可作为"高级数据结构"课程的内容，其余作为"数据结构基础"课程的内容。本书引用了数据结构研究的大量先进成果，在此，作者谨向这些成果的原创者表示崇高的敬意和衷心的感谢。同时，对本书所引用的参考文献的作者也表示衷心的感谢。在本书的写作过程中，作者与徐宝文、孙志挥、王茜、徐冬梅、王树梅、吉根林和张丽晖老师开展了卓有成效的讨论，并由此得到很多启发。南京大学计算机科学与技术系陈道蓄教授认真审读了全部书稿，并提出了十分宝贵的修改意见，在此对他们表示最诚挚的谢意。感谢清华大学出版社的鼓励与支持。感谢东南大学教学改革基金的资助。还要感谢作者的众多学生，他们在数据结构课程学习过程中表现出的热情与执着给了作者很大的鼓励，与他们的讨论和交流使作者对教学内容和教学方法的改进有了更深刻的认识。

暂缺《数据结构》作者简介

第1章 基本概念和方法 1
1.1 数据结构与软件系统 1
1.2 数据抽象与封装 2
1.3 算法定义 5
1.4 递归算法 6
1.5 性能分析 9
1.5.1 空间复杂性 9
1.5.2 时间复杂性 10
1.5.3 O表示法 14
1.5.4 代价分摊 16
1.5.5 实际可行的复杂性 19
1.6 性能测量 20
1.7 C++中的模板 22
1.8 效率与权衡 24
习题1 24
第2章 线性表 26
2.1 线性表与数组 26
2.2 多项式 27
2.2.1 多项式的表示 28
2.2.2 多项式相加 30
2.3 稀疏矩阵 31
2.3.1 稀疏矩阵的表示 32
2.3.2 稀疏矩阵的转置 32
2.4 字符串 35
2.4.1 字符串模式匹配的简单算法 36
2.4.2 字符串模式匹配的KMP算法 36
2.4.3 两个字符串的最长公共子序列 39
2.5 栈 41
2.6 队列 44
2.7 迷宫问题 47
2.8 表达式计算 51
2.8.1 表达式 51
2.8.2 后缀表示 51
2.8.3 将中缀转化为后缀 52
2.9 机场模拟 54
习题2 61
第3章 链表 66
3.1 单链表 66
3.1.1 单链表的表示 67
3.1.2 基本操作 68
3.2 可重用链表类 70
3.2.1 用模板定义链表 70
3.2.2 链表游标 71
3.2.3 链表操作 74
3.3 环链表 75
3.4 链式栈和队列 77
3.5 链式多项式 79
3.5.1 多项式表示 79
3.5.2 多项式相加 80
3.5.3 删除多项式 81
3.5.4 环链多项式 82
3.6 等价类 84
3.7 稀疏矩阵的链表实现 87
3.7.1 稀疏矩阵表示 87
3.7.2 输入稀疏矩阵 90
3.7.3 删除稀疏矩阵 91
3.8 双链表 92
3.9 广义表 94
3.9.1 广义表的概念及表示 94
3.9.2 递归算法 96
3.9.3 引用计数、共享与递归表 100
3.10 动态类型与异构表 102
习题3 105
第4章 树 109
4.1 树和森林的概念及其表示 109
4.2 二叉树 111
4.2.1 二叉树定义 111
4.2.2 二叉树的性质 112
4.2.3 二叉树表示 114
4.3 二叉树遍历与树游标 115
4.3.1 中序遍历 116
4.3.2 前序遍历 117
4.3.3 后序遍历 118
4.3.4 中序游标 118
4.3.5 后序游标 120
4.3.6 按层次遍历 121
4.4 满足性问题 122
4.5 线索二叉树 125
4.5.1 线索 125
4.5.2 中序遍历线索二叉树 127
4.5.3 后序遍历线索二叉树 128
4.5.4 将结点插入线索二叉树 131
4.6 选择树 133
4.6.1 胜者树 133
4.6.2 败者树 134
4.7 森林的二叉树表示及遍历 136
4.8 集合表示 137
4.8.1 并查集 137
4.8.2 在等价类问题中的应用 143
4.9 二叉树计数 144
习题4 149
第5章 堆结构 152
5.1 最大堆 152
5.1.1 优先队列与最大堆 152
5.1.2 插入操作 154
5.1.3 删除操作 155
5.2 最小最大堆 156
5.2.1 双端优先队列与最小最大堆 156
5.2.2 插入操作 157
5.2.3 删除最小元素操作 160
5.3 双堆 162
5.3.1 双堆定义 162
5.3.2 插入操作 164
5.3.3 删除最小元素 166
5.4 左偏（leftist）树 168
5.5 二项式堆 172
5.5.1 二项式堆定义 173
5.5.2 插入操作 175
5.5.3 合并操作 175
5.5.4 删除最小元素 175
5.5.5 分析 177
5.6 斐波纳契堆 178
5.6.1 斐波纳契堆定义 178
5.6.2 删除操作 178
5.6.3 key值减少操作 179
5.6.4 瀑布修剪 179
5.6.5 分析 181
习题5 182
第6章 图 185
6.1 图的基本定义 185
6.2 图的表示 188
6.2.1 邻接矩阵 188
6.2.2 邻接表 189
6.2.3 邻接多表 192
6.3 连通图的遍历 194
6.3.1 深度优先搜索 194
6.3.2 广度优先搜索 195
6.3.3 生成树 196
6.4 图的连通性 197
6.4.1 连通分量 197
6.4.2 双连分量 198
6.5 最小代价生成树 201
6.5.1 克鲁斯卡尔算法 201
6.5.2 普瑞姆算法 204
6.6 最短路径和传递闭包 205
6.6.1 边长非负时的单源点到所有终点的最短路径 205
6.6.2 所有顶点对之间的最短路径 209
6.6.3 传递闭包 211
6.7 活动网络 212
6.7.1 AOV网络 212
6.7.2 AOE网络 216
习题6 222
第7章 排序 225
7.1 引言 225
7.2 插入排序 226
7.3 希尔（Shell）排序 228
7.4 快速排序 230
7.5 归并排序 233
7.5.1 迭代归并排序 233
7.5.2 递归归并排序 236
7.6 堆排序 238
7.7 基数排序 241
7.8 基于链表和映射表排序结果的顺序化 244
7.9 外排序 249
7.9.1 概述 249
7.9.2 k-路归并 251
7.9.3 生成初始归并段 252
7.9.4 归并段的最佳归并和哈夫曼树 256
习题7 259
第8章 查找结构 262
8.1 符号表 262
8.2 二叉查找树 263
8.2.1 二叉查找树定义 263
8.2.2 二叉查找树的查找、插入和删除操作 264
8.2.3 二叉查找树的结合与分裂 266
8.2.4 二叉查找树的性能分析 269
8.2.5 最佳二叉查找树 272
8.3 AVL树 278
8.4 2-3树 285
8.4.1 定义与性质 285
8.4.2 2-3树的查找 287
8.4.3 2-3树的插入操作 287
8.4.4 2-3树的删除操作 289
8.5 Splay树 292
8.6 B树 297
8.6.1 m叉查找树 297
8.6.2 m叉查找树的查找 299
8.6.3 B树的定义和性质 300
8.6.4 B树的插入操作 302
8.6.5 B树的删除操作 304
8.6.6 B+树 307
8.7 Trie 310
8.7.1 Trie的定义 310
8.7.2 Trie的查找 311
8.7.3 取样策略 312
8.7.4 在Trie中插入和删除元素 312
8.8 静态散列 313
8.8.1 散列表 313
8.8.2 散列函数 315
8.8.3 溢出处理 316
8.9 动态散列 320
8.9.1 带目录动态散列 321
8.9.2 无目录动态散列 327
习题8 328
索引 332
参考文献 336