“数据结构”是计算机专业的核心课程，是从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及，“数据结构”课程也在不断地发展。
本书按照清华大学计算机系本科“数据结构”大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始,从线性结构到非线性结构，从简单到复，深入地讨论了各种数据结构内在的逻辑关系及其在计算机中的实现方式和使用。此外，对常用的迭代、递归、回溯等算法设计技巧，搜索和排序算法等都做了详尽的描述，并引入了简单的算法分析。
全书采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化基本知识和基本能力的双基训练。全书条理清晰，通俗易懂，图文并茂，适于自学。
与本书配套的《数据结构习题解析——用面向对象方法与C++语言描述》一书已经由清华大学出版社出版。本书适合大专院校计算机、软件专业本科生使用，也可作为教师和有关科研人员的参考书。

　　计算机的普及极大地改变了人们的工作和生活。目前各个行业、各个领域都与计算机建立了紧密的联系，也随之带来了开发各种软件的需求。为了能够以最少的成本，最快的速度，最好的质量开发出合乎需要的软件，必须遵循软件工程的原则，把软件的开发、维护标准化、工程化，不能再像以前那样，把软件看作是个人雕琢的精品。就软件产品而言，最重要的就是建立合理的软件体系结构和程序结构，设计有效的数据结构。因此，要做好软件开发工作，必须了解如何组织各种数据在计算机中的存储、传递和转换。这样，《数据结构》这门课程显得格外重要。自1978年美籍华裔学者冀中田在国内首开这门课程以来(当时作者也在场)，经过20余年的发展，本课程已成为各大学计算机专业本科的主干课程，也成为非计算机类学生和研究生学习计算机的必修课程。

“数据结构”课程脱胎于“离散数学结构”，它涉及各种离散结构(如向量、集合、树、图、代数方程、多项式等)在计算机上如何存储和处理。其内容丰富，涉及面广泛，而且还在随各种基于计算机的应用技术的发展，不断增加新的内容。特别是面向对象技术出现以后，人们认识到，用它开发出来的软件体系结构更加符合人们的习惯，质量更容易得到保证，尤其是更容易适应使用者和用户不断提出的新的需求。因此，在国际上，面向对象技术得到迅速普及，出现了大批面向对象的软件开发工具。为了适合形势的要求，有必要开设结合面向对象技术的数据结构课程。

用面向对象的观点讨论数据结构，与传统的面向过程的讲法相比，变化较大。各种数据结构的讨论都是基于抽象数据类型和软件复用的，有新意，也有继承。我们力图与过去的讲授体系保持一致，但又必须引入一些新的概念。为了能够让读者容易学习，我们对内容进行了精选。许多从基本数据结构派生出来的概念，如双端堆、二项堆、最小最大堆、斐波那契堆、左斜树、扁树、B*树等都舍去了。同时，把动态存储管理部分归到“操作系统”课程，把文件组织部分归到“数据库原理”，只保留了重要的应用最广泛的一些结构。对这些结构做全面深入的讲解，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型事例说明它们在解决应用问题时的动态行为和各种必要的操作，并以C++语言为表述手段，介绍在面向对象程序设计过程中各种数据结构的表达和实现。只要是学过C或PASCAL语言，就能够很容易地阅读和理解，并因此学习C++语言，提高读者的软件设计和编程能力。

本书是作为清华大学信息学院平台课“数据结构”的教材编写的，在编写过程中得到清华大学信息学院领导的支持，并获得教育部“十一五”规划教材的资助。参与策划的有计算机系教师殷人昆、邓俊辉、舒继武、朱仲涛，电子系教师朱明方、吴及，自动化系教师李宛洲、刘义，微纳电子学系教师李树国，软件学院教师张力以及信息学院办公室的教师王娜等。第4章由舒继武执笔，第5章由朱仲涛执笔，第8章由邓俊辉执笔，第9章由吴及执笔，其他各章由殷人昆执笔。作者们都是在清华大学从事“数据结构”课程第一线教学的教师，有着丰富的数据结构和软件工程教学的经验，教学效果良好。

全书共分10章。第1章是预备知识，主要介绍什么是数据，数据与信息的关系；什么是数据结构，数据结构的分类。通过学习，读者能够了解抽象数据类型和面向对象的概念。并对对象、类、继承、消息以及其他关系的定义、使用有基本认识。由于我们选择了具有面向过程和面向对象双重特点的C++语言，可以帮助读者自然而轻松地从传统程序设计观念向面向对象方法转变。在这一章的最后还讨论了算法设计和简单的算法分析方法。

第2章是全书的基础，讨论了线性表、它的数组表示和链表表示，以及利用它们定义出来的各种结构，如顺序表、代数多项式等。通过学习，读者可以了解对象和类的基本实现，并通过模板、多态性等的使用，对数据抽象概念有进一步的理解。

第3章引入4种存取受限的表，即栈、队列、优先级队列和双端队列。通过对它们的定义、实现和应用的深入介绍，使读者能够了解在什么场合使用它们，为以后更复杂的数据结构和算法的实现，提供了多种辅助手段。

第4章介绍在许多领域中经常遇到的多维数组、字符串和广义表。这些都是应用广泛又十分灵活的结构。

第5章和第8章介绍在实际应用中最重要的非线性结构——树与图。在管理、电子设计、机械设计、日常生活中许多方面都会用到它们。

第6章、第7章和第10章介绍集合、跳表、散列、搜索树、索引以及文件等结构。在实际与信息处理相关的应用中，这些结构十分重要。许多非数值处理都涉及这些结构，它们与内存、外存上的数据组织关系密切。例如在外存组织文件时全面应用了这些结构。它们又是许多新结构的生长点。因此，读者学习这些内容将获益匪浅。

第9章介绍排序。这也是应用十分广泛的技术。只要是数据处理，就少不了排序。如何才能高效地完成排序，本章分别就内、外存使用的多种排序方法进行介绍和讨论，读者可以深入了解排序的机制，也能从中学到许多程序设计的技巧。

本书的篇幅虽然较大，但给读者以选择。可以根据时间、能力，适当对学习的内容加以剪裁。本着少讲多练的原则，可以对每种结构只介绍类定义和关键操作的实现，其他内容可自学。通过上机练习，加深理解。在本书目录中加**的章节可以酌情不讲。

在本书的成书过程中得到清华大学出版社的支持，在此表示衷心的感谢。最后需要说明的是，由于作者们的水平有限，书中肯定存在许多疏漏或错误，请读者及时来信批评指教。邮件地址是： yinrk@tsinghua.edu.cn或yinrk@sohu.com。

作者
2006年11月于北京

第1章数据结构概论1
1.1数据结构的概念1
1.1.1数据结构举例1
1.1.2数据与数据结构2
1.1.3数据结构的分类3
1.1.4数据结构课程的内容4
1.2数据结构的抽象形式6
1.2.1数据类型6
1.2.2数据抽象与抽象数据类型7
1.3作为ADT的C++类9
1.3.1面向对象的概念9
1.3.2C++中的类10
1.3.3C++中的对象12
1.3.4C++的输入输出13
1.3.5C++中的函数14
1.3.6动态存储分配17
1.3.7C++中的继承18
1.3.8多态性19
1.3.9C++的模板23
1.4算法定义24
1.5算法性能分析与度量26
1.5.1算法的性能标准26
1.5.2算法的后期测试26
1.5.3算法的事前估计27
1.5.4算法的渐进分析32
1.5.5最坏、最好和平均情况36
习题37

第2章线性表43
2.1线性表43
2.1.1线性表的概念43
2.1.2线性表的类定义44
2.2顺序表45
2.2.1顺序表的定义和特点45
2.2.2顺序表的类定义及其操作45
2.2.3顺序表的性能分析50
2.2.4顺序表的应用52
2.3单链表52
2.3.1单链表的概念53
2.3.2单链表的类定义54
2.3.3单链表中的插入与删除56
2.3.4带附加头结点的单链表59
2.3.5单链表的模板类60
2.4线性链表的其他变形66
2.4.1循环链表66
2.4.2双向链表69
2.5单链表的应用：多项式及其运算73
2.5.1多项式的表示74
2.5.2多项式的类定义75
2.5.3多项式的加法77
2.5.4多项式的乘法79
2.6静态链表80
习题83

第3章栈和队列88
3.1栈88
3.1.1栈的定义88
3.1.2顺序栈89
3.1.3链式栈92
3.1.4栈的应用之一——括号匹配94
3.1.5栈的应用之二——表达式的计算95
3.2栈与递归101
3.2.1递归的概念101
3.2.2递归过程与递归工作栈105
3.2.3用回溯法求解迷宫问题109
3.3队列114
3.3.1队列的概念114
3.3.2循环队列114
3.3.3链式队列118
3.3.4队列应用举例：打印二项展开式(a+b)i的系数120
3.3.5队列应用举例：电路布线121
3.4优先级队列124
3.4.1优先级队列的概念124
3.4.2优先级队列的存储表示和实现125
3.5双端队列126
3.5.1双端队列的概念126
3.5.2双端队列的数组表示128
3.5.3双端队列的链表表示129
习题131

第4章数组、串与广义表135
4.1多维数组的概念与存储135
4.1.1多维数组的概念135
4.1.2多维数组的存储表示136
4.2特殊矩阵138
4.2.1对称矩阵的压缩存储138
4.2.2三对角线/多对角线矩阵的压缩存储140
4.3稀疏矩阵141
4.3.1稀疏矩阵及其三元组数组表示141
4.3.2稀疏矩阵的转置145
4.3.3稀疏矩阵的相加和相乘147
4.3.4矩阵的正交链表表示152
4.4字符串153
4.4.1字符串的概念153
4.4.2C++有关字符串的库函数154
4.4.3字符串的实现156
4.4.4字符串的自定义类158
4.4.5字符串操作的实现159
4.4.6字符串的模式匹配161
4.4.7字符串的存储方法167
4.5广义表169
4.5.1广义表的定义与性质169
4.5.2广义表的表示170
4.5.3广义表存储结构的实现170
4.5.4广义表的递归算法174
4.5.5三元多项式的表示181
习题183

第5章树186
5.1树的基本概念186
5.1.1树的定义和术语186
5.1.2树的抽象数据类型188
5.2二叉树189
5.2.1二叉树的定义189
5.2.2二叉树的性质190
5.2.3二叉树的抽象数据类型191
5.3二叉树的存储表示192
5.3.1二叉树的数组存储表示192
5.3.2二叉树的链表存储表示193
5.4二叉树遍历及其应用198
5.4.1二叉树遍历的递归算法198
5.4.2二叉树遍历的应用200
5.4.3二叉树遍历的非递归算法203
5.4.4二叉树的计数207
5.5线索二叉树210
5.5.1线索210
5.5.2中序线索二叉树的建立和遍历211
5.5.3中序线索二叉树的插入与删除216
5.5.4前序与后序的线索化二叉树218
5.6树与森林220
5.6.1树的存储表示220
5.6.2森林与二叉树的转换225
5.6.3树与二叉树的转换227
5.7树与森林的遍历及其应用227
5.7.1树与森林的深度优先遍历227
5.7.2树和森林的广度优先遍历230
5.7.3树遍历算法的应用231
5.7.4其他基于遍历序列的几种存储表示232
5.8堆235
5.8.1最小堆和最大堆235
5.8.2堆的建立236
5.8.3堆的插入与删除238
5.9Huffman树及其应用240
5.9.1路径长度240
5.9.2Huffman树241
5.9.3Huffman树的应用：最优判定树243
5.9.4Huffman树的应用：Huffman编码244
习题246

第6章集合与字典251
6.1集合及其表示251
6.1.1集合的基本概念251
6.1.2用位向量实现集合抽象数据类型252
6.1.3用有序链表实现集合的抽象数据类型257
6.2并查集与等价类262
6.2.1并查集的定义及其实现262
6.2.2并查集的应用：等价类划分267
6.3字典268
6.3.1字典的概念269
6.3.2字典的线性表描述270
6.4跳表273
6.4.1跳表的概念273
6.4.2跳表的类定义274
6.4.3跳表的搜索、插入和删除276
6.5散列279
6.5.1散列表与散列方法279
6.5.2散列函数280
6.5.3处理冲突的闭散列方法282
6.5.4处理冲突的开散列方法291
6.5.5散列表分析293
习题294

第7章搜索结构297
7.1静态搜索结构298
7.1.1静态搜索表298
7.1.2顺序搜索300
7.1.3基于有序顺序表的顺序搜索和折半搜索302
7.1.4基于有序顺序表的其他搜索方法307
7.2二叉搜索树308
7.2.1二叉搜索树的概念309
7.2.2二叉搜索树上的搜索310
7.2.3二叉搜索树的插入311
7.2.4二叉搜索树的删除313
7.2.5二叉搜索树的性能分析314
7.2.6最优二叉搜索树317
7.3AVL树320
7.3.1AVL树的概念321
7.3.2平衡化旋转321
7.3.3AVL树的插入326
7.3.4AVL树的删除329
7.3.5AVL树的性能分析333
7.4伸展树334
7.5红黑树337
7.5.1红黑树的概念和性质337
7.5.2红黑树的搜索338
7.5.3红黑树的插入338
7.5.4红黑树的删除339
习题342

第8章图346
8.1图的基本概念346
8.1.1与图有关的若干概念346
8.1.2图的抽象数据类型348
8.2图的存储结构349
8.2.1图的邻接矩阵表示350
8.2.2图的邻接表表示355
8.2.3图的邻接多重表表示361
8.3图的遍历363
8.3.1深度优先搜索364
8.3.2广度优先搜索365
8.3.3连通分量366
8.3.4重连通分量368
8.4最小生成树370
8.4.1Kruskal算法371
8.4.2Prim算法373
8.5最短路径375
8.5.1非负权值的单源最短路径376
8.5.2任意权值的单源最短路径379
8.5.3所有顶点之间的最短路径381
8.6用顶点表示活动的网络（AOV网络）383
8.7用边表示活动的网络（AOE网络）388
习题392

第9章排序397
9.1排序的概念及其算法性能分析397
9.1.1排序的概念397
9.1.2排序算法的性能评估398
9.1.3排序表的类定义400
9.2插入排序401
9.2.1直接插入排序401
9.2.2折半插入排序403
9.2.3希尔排序404
9.3快速排序405
9.3.1快速排序的过程406
9.3.2快速排序的性能分析407
9.3.3快速排序的改进算法409
9.3.4三路划分的快速排序算法412
9.4选择排序413
9.4.1直接选择排序413
9.4.2锦标赛排序414
9.4.3堆排序419
9.5归并排序422
9.5.1归并422
9.5.2归并排序算法423
9.6基于链表的排序算法425
9.6.1链表插入排序425
9.6.2链表归并排序427
9.6.3链表排序结果的重排428
9.7分配排序431
9.7.1桶式排序431
9.7.2基数排序432
9.7.3MSD基数排序433
9.7.4LSD基数排序435
9.8内部排序算法的分析437
9.8.1排序方法的下界437
9.8.2各种内部排序方法的比较439
习题440

第10章文件、外部排序与搜索444
10.1主存储器和外存储器444
10.1.1磁带444
10.1.2磁盘存储器446
10.1.3缓冲区与缓冲池448
10.2文件组织449
10.2.1文件的概念449
10.2.2文件的存储结构450
10.3外排序459
10.3.1外排序的基本过程459
10.3.2k路平衡归并与败者树461
10.3.3初始归并段的生成（run generation）466
10.3.4并行操作的缓冲区处理470
10.3.5最佳归并树473
10.4多级索引结构475
10.4.1静态的ISAM方法475
10.4.2动态的m路搜索树476
10.4.3B树478
10.4.4B树的插入480
10.4.5B树的删除482
10.4.6B+树486
10.4.7VSAM489
10.5可扩充散列490
10.5.1二叉Trie树490
10.5.2将二叉Trie树转换为目录表491
10.5.3目录表扩充与收缩493
10.5.4性能分析494
10.6Trie树494
10.6.1Trie树的定义494
10.6.2Trie树的搜索495
10.6.3在Trie树上的插入和删除496
习题497

附录A程序索引500
附录B词汇索引504
参考文献512