（已有3条评价）基本信息
内容简介
作译者
王建德 国务院特殊津贴专家、上海师范大学特聘教授、控江中学特级教师。他辅导学生在国际奥林匹克信息学竞赛（IOI）中获8金、4银、2铜，先后出版了《新编实 用算法分析与程序设计》和《程序设计中常用的计算思维方式》等多本广受好评的图书，这些图书长期以来是国内各类程序设计竞赛的必备教程。
吴 永辉 博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会成员，复旦大学ACM程序设计竞赛队教练。自2001年起连续带队进入 ACM-ICPC世界总决赛，并取得过世界第六名的佳绩。主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论 文，参与翻译的著作有《数据通信与网络》和《数据通信、计算机网络与开放系统》。
吴 永辉 博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会成员，复旦大学ACM程序设计竞赛队教练。自2001年起连续带队进入 ACM-ICPC世界总决赛，并取得过世界第六名的佳绩。主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论 文，参与翻译的著作有《数据通信与网络》和《数据通信、计算机网络与开放系统》。
目录
《程序设计中实用的数据结构》
上篇 讨论线性表
第1 章 数组 3
1.1 数组的基本概念 3
1.1.1 数组是一种顺序存储结构 3
1.1.2 数组是程序设计中使用频率最高的数据类型 4
1.2 优化数组的存储方式 6
1.2.1 规则矩阵的压缩存储 6
1.2.2 稀疏矩阵的压缩存储 7
1.2.3 01 矩阵的压缩存储 11
1.3 排序与顺序统计 14
1.3.1 排序的基本概念 14
1.3.2 计数排序与贪心策略 15
1.3.3 采用“二分”策略的排序方法 21
1.3.4 顺序统计的基本方法 28
第2 章 链式存储结构 34
2.1 链表的基本概念 34
2.1.1 单链表 34
2.1.2 循环链表 35
2.1.3 双向链表 35
上篇 讨论线性表
第1 章 数组 3
1.1 数组的基本概念 3
1.1.1 数组是一种顺序存储结构 3
1.1.2 数组是程序设计中使用频率最高的数据类型 4
1.2 优化数组的存储方式 6
1.2.1 规则矩阵的压缩存储 6
1.2.2 稀疏矩阵的压缩存储 7
1.2.3 01 矩阵的压缩存储 11
1.3 排序与顺序统计 14
1.3.1 排序的基本概念 14
1.3.2 计数排序与贪心策略 15
1.3.3 采用“二分”策略的排序方法 21
1.3.4 顺序统计的基本方法 28
第2 章 链式存储结构 34
2.1 链表的基本概念 34
2.1.1 单链表 34
2.1.2 循环链表 35
2.1.3 双向链表 35
序言
最近几年，我们长期从事程序设计研究和竞赛辅导，并在此基础上精心编写了ACM/ICPC竞赛的系列教程，其中包括《新编实用算法分析与程序设计》（人民邮电出版社2008年出版）、《程序设计中常用的计算思维方式》（人民铁道出版社2009年出版）、《程序设计中常用的解题策略》（人民邮电出版社2009年出版）和《程序设计中实用的数据结构》（即本书）。按照“数据结构＋算法＝程序”的定义，《新编实用算法分析与程序设计》和《程序设计中实用的数据结构》属于程序设计的知识范畴，而《程序设计中常用的计算思维方式》和《程序设计中常用的解题策略》分别从思维方式和行为特征这两个角度给出了解决问题的基本方法，属于基于算法和数据结构知识的编程能力范畴。上述所有著作贴近实际，结合实例进行阐释，使读者对什么是程序设计，为什么要学习程序设计，怎样进行程序设计等诸多问题产生浓厚的兴趣和探索意识。因此可以说，这4部著作从知识、能力和情感体验3个维度，建立了程序设计学习的基本框架。
数据结构是计算机软件专业的核心课程，也是编程人员必学的知识。现在关于数据结构的书很多，章节结构大致雷同，具体描述也大同小异。为了避免本书落入“千篇一律”的俗套，我们按照数据结构知识的分类，将全书分为3篇。
上篇“讨论线性表”根据线性结构存储方式的不同，讲解了顺序存储结构和链式存储结构， 并根据元素存取方式的不同，讲解了栈和队列两种特殊的线性结构，另外还介绍了线性结构的如下3个重要的应用。
(1) 排序与顺序统计。探讨了贪心策略中的序关系和分治策略在排序中的应用，并在排序知识的基础上阐释了顺序统计的有关方法。
(2) 散列表。介绍了如何使用散列函数确定关键字存储位置，并介绍了在多个关键字的运算结果相同的情况下，如何采用链式存储结构的分离链接法和采用顺序存储结构的开放定址法解决“冲突”。
(3) 后缀数组。介绍了一种专用于字符串处理的重要工具。
中篇“讨论树型问题”详细阐释了什么是树，树有哪些类型，如何通过不同的遍历规则将非线性结构的树转化为线性序列，程序中可采用哪些数据类型存储树，这些数据类型与树操作的效率之间有什么样的关系，怎样通过树形式的并查集实现集合间的合并，以及在哪个集合中查找元素。这一篇着重阐释了结构简单、操作方便且便于二分处理数据的二叉树，介绍了普通有序树转化为等价二叉树的基本方法和如下4种特殊类型的二叉树。
(1) 用二叉堆实现元素入队和按照优先级出队的优先队列。
(2) 在数据通信等方面有广泛用途的最优二叉树。
(3) 用于区间处理和数据统计的线段树。
(4) 用于高效查找数据的3种二叉查找树，即二叉排序树、静态二叉排序树和平衡树。
下篇“讨论图型问题”详尽地阐释了图的基本概念和简单分类，介绍了图的4种存储方式（相邻矩阵、邻接表、关联矩阵和邻接压缩表）和2种遍历规则（宽度优先遍历和深度优先遍历），深入讨论了图的连通性问题，分别给出了在有向图中计算强连通分量和传递闭包以及在无向图中计算割点、桥和双连通分量的基本思路，并重点讲解了计算最小生成树和最短路径的策略。二分图和引入流量因素的单源单汇简单有向图（网络流图）是两类重要的图，我们给出了求解二分图最大匹配以及在加权二分图中计算权和最大匹配的基本方法，并分别叙述了应对不同网络流问题的算法。
在上述3篇的论述中，我们尽力凸显如下特色。
(1) 与时俱进。尽可能将近年来数据结构研究上涌现的新知识、新成果纳入本书，并且以贴近实际、深入浅出的形式展现给读者。
(2) 注重实际应用能力。通过实例教会读者，怎样寻找问题中各对象之间的关系，确定数学模型所使用的逻辑结构；怎样实现对各个对象的操作，即确定数据所采用的存储结构；怎样融数据类型与定义在该类型上的运算于一体，为面向对象的程序设计方法奠定基础。
(3) 掌握并联两种数据结构的映射方法。教会读者在运算对象需要同时采用两种数据结构时，怎样将两种数据结构的元素一一对应起来，使得当一种数据结构中的关键元素发生变化时，另一种数据结构的相应元素也随之变化。
(4) 辩证地看问题。使读者既能了解线性结构这种基本数据结构的局限性，又可以掌握采用基本数据结构实现复杂非线性结构的基本方法，还进一步探索了用基本数据结构取代非线性结构的简化途径。如果说基本数据结构到非线性结构是一种提高，那么从非线性结构回到基本数据结构却不是一种简单的回归，而是一种螺旋式发展。对于基本数据结构的再次运用，是基于对整个数据结构知识的一种深刻领悟，在进一步理解和运用基本数据结构的过程中，可使我们的知识与思想得到升华。
(5) 精益求精。随着试题难度和问题规模的不断提升，对算法时空效率的要求愈来愈高，数据结构对算法效率的制约力也愈来愈大。因此，本书旨在引导读者充分考虑数据结构对程序效率所产生的影响，在选择数据结构时，尽可能采用“扬长避短”的原则并结合“取长补短”的方法，更加有效地优化算法。
为了使选用本教程的辅导教师容易教，参与竞赛培训的学生容易学，读者在解题查阅时容易懂，本书在表述上采取了如下4条措施。
(1) 对于每个比较难懂的概念，都举实例加以说明；对于每个比较抽象的定理，都提供具体的应用例证帮助理解；对于每个经典的算法，都有清晰的程序流程给予示范。
数据结构是计算机软件专业的核心课程，也是编程人员必学的知识。现在关于数据结构的书很多，章节结构大致雷同，具体描述也大同小异。为了避免本书落入“千篇一律”的俗套，我们按照数据结构知识的分类，将全书分为3篇。
上篇“讨论线性表”根据线性结构存储方式的不同，讲解了顺序存储结构和链式存储结构， 并根据元素存取方式的不同，讲解了栈和队列两种特殊的线性结构，另外还介绍了线性结构的如下3个重要的应用。
(1) 排序与顺序统计。探讨了贪心策略中的序关系和分治策略在排序中的应用，并在排序知识的基础上阐释了顺序统计的有关方法。
(2) 散列表。介绍了如何使用散列函数确定关键字存储位置，并介绍了在多个关键字的运算结果相同的情况下，如何采用链式存储结构的分离链接法和采用顺序存储结构的开放定址法解决“冲突”。
(3) 后缀数组。介绍了一种专用于字符串处理的重要工具。
中篇“讨论树型问题”详细阐释了什么是树，树有哪些类型，如何通过不同的遍历规则将非线性结构的树转化为线性序列，程序中可采用哪些数据类型存储树，这些数据类型与树操作的效率之间有什么样的关系，怎样通过树形式的并查集实现集合间的合并，以及在哪个集合中查找元素。这一篇着重阐释了结构简单、操作方便且便于二分处理数据的二叉树，介绍了普通有序树转化为等价二叉树的基本方法和如下4种特殊类型的二叉树。
(1) 用二叉堆实现元素入队和按照优先级出队的优先队列。
(2) 在数据通信等方面有广泛用途的最优二叉树。
(3) 用于区间处理和数据统计的线段树。
(4) 用于高效查找数据的3种二叉查找树，即二叉排序树、静态二叉排序树和平衡树。
下篇“讨论图型问题”详尽地阐释了图的基本概念和简单分类，介绍了图的4种存储方式（相邻矩阵、邻接表、关联矩阵和邻接压缩表）和2种遍历规则（宽度优先遍历和深度优先遍历），深入讨论了图的连通性问题，分别给出了在有向图中计算强连通分量和传递闭包以及在无向图中计算割点、桥和双连通分量的基本思路，并重点讲解了计算最小生成树和最短路径的策略。二分图和引入流量因素的单源单汇简单有向图（网络流图）是两类重要的图，我们给出了求解二分图最大匹配以及在加权二分图中计算权和最大匹配的基本方法，并分别叙述了应对不同网络流问题的算法。
在上述3篇的论述中，我们尽力凸显如下特色。
(1) 与时俱进。尽可能将近年来数据结构研究上涌现的新知识、新成果纳入本书，并且以贴近实际、深入浅出的形式展现给读者。
(2) 注重实际应用能力。通过实例教会读者，怎样寻找问题中各对象之间的关系，确定数学模型所使用的逻辑结构；怎样实现对各个对象的操作，即确定数据所采用的存储结构；怎样融数据类型与定义在该类型上的运算于一体，为面向对象的程序设计方法奠定基础。
(3) 掌握并联两种数据结构的映射方法。教会读者在运算对象需要同时采用两种数据结构时，怎样将两种数据结构的元素一一对应起来，使得当一种数据结构中的关键元素发生变化时，另一种数据结构的相应元素也随之变化。
(4) 辩证地看问题。使读者既能了解线性结构这种基本数据结构的局限性，又可以掌握采用基本数据结构实现复杂非线性结构的基本方法，还进一步探索了用基本数据结构取代非线性结构的简化途径。如果说基本数据结构到非线性结构是一种提高，那么从非线性结构回到基本数据结构却不是一种简单的回归，而是一种螺旋式发展。对于基本数据结构的再次运用，是基于对整个数据结构知识的一种深刻领悟，在进一步理解和运用基本数据结构的过程中，可使我们的知识与思想得到升华。
(5) 精益求精。随着试题难度和问题规模的不断提升，对算法时空效率的要求愈来愈高，数据结构对算法效率的制约力也愈来愈大。因此，本书旨在引导读者充分考虑数据结构对程序效率所产生的影响，在选择数据结构时，尽可能采用“扬长避短”的原则并结合“取长补短”的方法，更加有效地优化算法。
为了使选用本教程的辅导教师容易教，参与竞赛培训的学生容易学，读者在解题查阅时容易懂，本书在表述上采取了如下4条措施。
(1) 对于每个比较难懂的概念，都举实例加以说明；对于每个比较抽象的定理，都提供具体的应用例证帮助理解；对于每个经典的算法，都有清晰的程序流程给予示范。
