本书作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。
　　在体例方面，作者结合多年教学实践，对知识点进行了重新整理编排，许多处理方法在同类教材中独树一帜，旨在将读者引向更高层次，使读者形成对数据结构的宏观认识。
　　在内容方面，本书并未对各种数据结构面面俱到，而是按照CC2001标准对必要知识点和技能要求精心加以裁剪，通过系统分类和启发式讲解，在基本数据结构与高级数据结构之间架起一座桥梁。
　　在算法方面，本书不仅强调对复杂度等基本概念的把握，同时结合具体问题介绍算法复杂度的各种分析方法，尤其是分摊分析等高级技巧。而且所有数据结构仍然构成一个完整的体系，帮助读者养成面向实际应用的意识，并掌握构建实际应用的基本能力。
　　要获取本书中的代码及相关教学资料，请访问:http://vis.cs.tsinghua.edu.cn/~deng/dsaj.htm。

无

关于计算机教育规范，最有权威、影响最大的莫过于ACM与IEEECS联合制订的Computing Curricula。比如，Computing Curricula 1991(CC1991)就曾对我国高校的计算机教育产生深刻的影响。正在制订中的CC2001（后改称CC2004）认为，随着近年来计算概念的快速发展，计算学科已经发展成为一个内涵繁杂的综合性学科，至少可以划分为计算机工程（CE）、计算机科学（CS）、信息系统（IS）、信息技术（IT）和软件工程（SE）五个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。尽管如此，从目前已经完成的部分来看，数据结构与算法在各领域的知识体系中仍占据重要的位置。比如在CE分卷（草案）中，Programming Fundamentals共39个核心学时，其中Algorithms and Problem Solving占8个学时，Data Structures占13个学时； 在CS分卷（正式稿）中，Programming Fundamentals共38个核心学时，其中Algorithms and Problem Solving占6个学时，Data Structures占14个学时。
　　为什么数据结构与算法长期以来一直受到如此重视呢？数据结构和算法是一对孪生兄弟，数据结构研究的问题包括数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。我们在编写计算机程序解决应用问题时，最终都要归结并落实到这两个问题上。正因为此，NWirth早在20世纪70年代就曾指出“程序＝数据结构+算法”。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成，到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。
　　为遵循上述原则，本书选择Java作为描述语言，因为相对于其他语言，Java语言比较完整、彻底地体现了面向对象的设计思想，这也是目前国际上同行们的一个主要取向。不过，关于Java语言本身的介绍，本书并未花费多少笔墨，而是直接假定读者已经熟练掌握了该语言。这既能缩减本书篇幅，也符合此领域教学今后的规范。比如，CC2001的CS分卷将Data Structures and Algorithms课程编号为CS103,并明确指出该课程是Programming Fundamentals(CS101)和The　ObjectOriented Paradigm(CS102)的后续课程。
　　在内容选取、剪裁与体例结构上，作者力图突破现成的模式。这里并未对各种数据结构面面俱到，而是通过分类和讲解典型结构，力图使读者形成对数据结构的宏观认识； 并结合各部分的具体内容，在书中穿插了大量的问题，把更多的思考空间留给读者。
　　根据内容侧重，本书具体分为10章。
　　第1章是全书的基础，重点在于介绍算法与数据结构的关系，以及算法时间、空间复杂度的概念及其度量方法。
　　第2~4章覆盖了基本的数据结构，既有传统的栈与队列，也有更为抽象和通用的向量和列表。面向对象技术在现代数据结构理论中的重要地位在此得到体现，我们利用接口实现数据结构的封装，抽象出位置的概念，在向量和列表的基础上定义并实现序列结构，引入迭代器概念并针对上述结构具体实现。通过结合数组与链表结构的优点，第4章自然地导出了树结构的概念、实现及算法。
　　第5~7章介绍了若干高级数据结构。通过在一般性队列中引入优先级概念，导出了优先队列结构； 面向实际问题中的查找需求，导出了映射和词典结构； 针对全序集的查找问题，引入了查找树结构，并结合AVL树、伸展树和B树的实例介绍了平衡查找树结构的原理及其实现。面向对象的思想在这里继续得到贯彻，普遍采用了抽象、封装及继承等技术。
　　这一部分的侧重点逐渐转向算法，并结合具体问题介绍其应用与实现，包括堆结构的生成及调整算法、Huffman（赫夫曼）编码树算法、散列算法以及二路或多路平衡查找树的生成、插入、删除算法。在这三章中，读者也将对算法复杂度的各种分析方法有所了解。
　　第8~10章的论述重点完全转向算法。第8章对此前各章中陆续介绍过的排序算法进行了归纳与分类，着重介绍了归并排序算法与快速排序算法，并给出了此类算法的复杂度下界。结合串结构的应用，第9章着重讨论了串匹配问题，从蛮力算法出发，采用不同的启发式加速策略，分别介绍了KMP算法及BM算法。
　　关于图结构，第10章将重点放在相关算法上，并力图使初学者从各种图算法中梳理出清晰的脉络。为此，这里尝试通过一条主线——遍历——将各种算法串接起来。在这里，面向对象技术的魅力再次得以展现：　基于统一的图遍历算法模板，分别实现了深度优先、广度优先和最佳优先三大类遍历算法。实际上，这三类算法本身仍然以模板形式实现，包括边分类、可达分量、连通分量、最短路径以及最小生成树在内的各种具体算法，都进而基于这三个模板分别得到了实现。
　　书中涉及的所有代码，都符合J2SDK141规范，并构成一个名为dsa(Data Structures & Algorithms)的包；　所有类之间的扩展、继承关系，可以参见书后的“DSA类关系图”。
　　要获取本书中的代码及相关教学资料，请访问： http: //viscstsinghuaeducn/~deng/dsajhtm。
　　本书从筹划、撰写、审订到定稿，其间跨越三个年头，在此漫长的过程中，我的父母和妻子给了我巨大的支持，就这个意义而言，他们也是本书的完成者。年幼的女儿总是以她独有的方式，不时将我从写作和调试的苦海中解救出来，她让我体会了禁用PowerOff按钮的妙用（尽管除了拔掉接头外我还没有找到更好的办法，使得在她恶作剧地按下Reset按钮后依然能够继续写作）。我的确需要感谢她，她让我养成了及时备份的良好习惯，更使我意识到在离开电脑后自己依然能够而且更好地思考。
　　在清华大学执教多年，我日益深刻地体会到教育的伟大和神圣，是我的同事、学生使我懂得了如何忘却劳动的艰辛，并从教育的过程中获得乐趣。
　　我还要特别感谢机械工业出版社的温莉芳女士，在我一次次地推迟交稿时，她表现出的耐心与理解都令我既钦佩又惭愧，正是这非凡的宽容激励着我不断追求完美。
　　虽反复斟酌，在本书即将出版之际，内心依然惶恐。“丑媳妇终要见公婆”，恳请读者批评指正。

邓俊辉
2005年岁末定稿

无

无

第1章算法及其复杂度
11计算机与算法
111过指定垂足的直角边
112三等分线段
113排序
114算法的定义
12算法性能的分析与评价
121三个层次
122时间复杂度及其度量
123空间复杂度
13算法复杂度及其分析
131O(1)——取非极端元素
132O(logn)——进制转换
133O(n)——数组求和
134O(n2)——起泡排序
135O(2r)——幂函数
14计算模型
141可解性
142有效可解
143下界
15递归
151线性递归
152递归算法的复杂度分析
153二分递归
154多分支递归
第2章栈与队列
21栈
211栈ADT
212基于数组的简单实现
213Java虚拟机中的栈
214栈应用实例
22队列
221队列ADT
222基于数组的实现
223队列应用实例
23链表
231单链表
232基于单链表实现栈
233基于单链表实现队列
24位置
241位置ADT
242位置接口
25双端队列
251双端队列ADT
252双端队列接口
253双向链表
254基于双向链表实现的双端队列
第3章向量、列表与序列
31向量与数组
311向量ADT
312基于数组的简单实现
313基于可扩充数组的实现
314javautilArrayList类和javautilVector类
32列表
321基于节点的操作
322由秩到位置
323列表ADT
324基于双向链表实现的列表
33序列
331序列ADT
332基于双向链表实现序列
333基于数组实现序列
34迭代器
341迭代器ADT
342迭代器接口
343迭代器的实现
344Java中的列表及迭代器
第4章树
41术语及性质
411节点的深度、树的深度与高度
412节点的度与内部节点、外部节点
413路径
414祖先、后代、子树和节点的高度
415共同祖先及最低共同祖先
416有序树、m叉树
417二叉树
418满二叉树与完全二叉树
42树ADT及其实现
421“父亲长子弟弟”模型
422树ADT
423树的Java接口
424基于链表实现树
43树的基本算法
431getSize()——统计（子）树的规模
432getHeight()——计算节点的高度
433getDepth()——计算节点的深度
434前序、后序遍历
435层次遍历
436树迭代器
44二叉树ADT及其实现
441二叉树ADT
442二叉树的Java接口
443二叉树类的实现
45二叉树的基本算法
451getSize()、getHeight()和getDepth()
452updateSize()
453updateHeight()
454updateDepth()
455secede()
456attachL()和attachR()
457二叉树的遍历
458直接前驱、直接后继的定位算法
46完全二叉树的Java实现
461完全二叉树的Java接口
462基于向量的实现
第5章优先队列
51优先级、关键码、全序关系与优先队列
52条目与比较器
521条目
522比较器
523Comparator接口及其实现
53优先队列ADT及其Java接口
531优先队列的ADT描述
532优先队列的Java接口
533基于优先队列的排序器
54用向量实现优先队列
55用列表实现优先队列
551基于无序列表的实现及分析
552基于有序列表的实现及分析
56选择排序与插入排序
561选择排序
562插入排序
563效率比较
57堆的定义及性质
571堆结构
572完全性
58用堆实现优先队列
581基于堆的优先队列及其实现
582插入与上滤
583删除与下滤
584改变任意节点的关键码
585建堆
59堆排序
591直接堆排序
592就地堆排序
510Huffman编码树
5101二叉编码树
5102最优编码树
5103Huffman编码与Huffman编码树
5104Huffman编码树的构造算法
5105基于优先队列的Huffman编码树构造算法
第6章映射与词典
61映射
611映射的ADT描述
612映射的Java接口
613判等器
614javautil包中的映射类
615基于列表实现映射类
62散列表
621桶及桶数组
622散列函数
623散列码
624压缩函数
625冲突的普遍性
626解决冲突
627基于散列表实现映射类
628装填因子与重散列
63无序词典
631无序词典的ADT描述
632无序词典的Java接口
633列表式无序词典及其实现
634散列表式无序词典及其实现
64有序词典
641全序关系与有序查找表
642二分查找
643有序词典的ADT描述
644有序词典的Java接口
645基于有序查找表实现有序词典
第7章查找树
71二分查找树
711定义
712查找算法
713完全查找算法
714插入算法
715删除算法
716二分查找树节点类的实现
717二分查找树类的实现
718二分查找树的平均性能
72AVL树
721平衡二分查找树
722等价二分查找树
723等价变换
724AVL树
725插入节点后的重平衡
726节点删除后的重平衡
727AVL树的Java实现
73伸展树
731数据局部性
732逐层伸展
733双层伸展
734分摊复杂度
735伸展树的Java实现
736插入
737删除
74B树
741分级存储
742B树的定义
743关键码的查找
744性能分析
745上溢节点的处理
746关键码的插入
747下溢节点的处理
748关键码的删除
第8章排序
81归并排序
811分治策略
812时间复杂度
813归并算法
814Mergesort的Java实现
82快速排序
821分治策略
822轴点
823划分算法
824Quicksort的Java实现
825时间复杂度
83复杂度下界
831比较树与基于比较的算法
832下界
第9章串
91串及其ADT描述
92串模式匹配
921概念与记号
922问题
923算法效率的测试与评价
93蛮力算法
931算法描述
932算法实现
933算法分析
94KMP算法
941蛮力算法的改进
942next［］表的定义及含义
943KMP算法描述
944next［］表的特殊情况
945next［］表的构造
946next［］表的改进
947KMP算法的Java实现
948性能分析
95BM算法
951坏字符策略
952好后缀策略
953BM算法
954BM算法的Java实现
955性能
第10章图
101概述
1011无向图、混合图及有向图
1012度
1013简单图
1014图的复杂度
1015子图、生成子图与限制子图
1016通路、环路及可达分量
1017连通性、等价类与连通分量
1018森林、树以及无向图的生成树
1019有向图的生成树
10110带权网络
102抽象数据类型
1021图
1022顶点
1023边
103邻接矩阵
1031表示方法
1032时间性能
1033空间性能
104邻接表
1041顶点表和边表
1042顶点与邻接边表
1043边
1044基于邻接表实现图结构
105图遍历及其算法模板
106深度优先遍历
1061深度优先遍历算法
1062边分类
1063可达分量与DFS树
1064深度优先遍历算法模板
1065可达分量算法
1066单强连通分量算法
1067强连通分量分解算法
1068浓缩图与弱连通性
107广度优先遍历
1071广度优先遍历算法
1072边分类
1073可达分量与BFS树
1074广度优先遍历算法模板
1075最短距离算法
108最佳优先遍历
1081最佳优先遍历算法
1082最佳优先遍历算法模板
1083最短路径
1084最短路径序列
1085Dijkstra算法
1086最小生成树
1087PrimJarnik算法DSA类关系图