数据结构 c++_邓俊辉

清华大学985名优教材立项资助 数据结构(c++语言版) 第3版 邓俊辉 清华大学出版社 2013年9月·北京 丛书序 “清华大学计算札系列教材”已经出版发行了3余种,包括计算机科学与技术专业的基础 数学、专业技术基础和专业等课程的教材,覆盖了计算机科学与技术专业本科生和研究生的主要 教学内容。这是一批至今发行数量很大并赢得广大读者赞誉的书籍,是近年来出版的大学计算机 专业教材中影响比较大的一批精品。 本系列教材的作者都是我熟悉的教授与同事,他们长期在第一线担任相关课程的教学工作, 是一批很受本科生和研究生欢迎的任课教师。编写高质量的计算机专业本科生(和研究生)教材, 不仅需要作者具备丰富的教学经验和科研实践,还需要对相关领域科技发展前沿的正确把握和了 解。正因为本系列教材的作者们具备了这些条件,才有了这批高质量优秀教材的产生。可以说, 教材是他们长期辛勤工作的结晶。本系列教材出版发行以来,从其发行的数量、读者的反映、已 经获得的国家级与省部级的奖励,以及在各个高等院校教学中所发挥的作用上,都可以看出本系 列教材所产生的社会影响与效益。 计算杋学科发展异常迅速,内容更新很快。作为教材,一方面要反映本领域基础性、普遍性 的知识,保持内容的相对稳定性;另一方面,又需要跟踪科技的发展,及时地调整和更新内容。 本系列教材都能按照自身的需要及时地做到这一点。如王爱英教授等编著的《计算机组成与结 构》、戴梅萼教授等编著的《微型计算杋技术及应用》都已经岀版了第四版,严蔚敏教授的《数 据结构》也岀版了三版,使教材既保持了稳定性,又达到了先进性的要求 本系列教材内容丰富,体系结构严谨,概念清晰,易学易懂,符合学生的认知规律,适合于 教学与自学,深受广大读者的欢迎。系列教材中多数配有丰富的习题集、习题解答、上机及实验 指导和电子教案,便于学生理论联系实际地学习相关课程。 随着我国进一步的开放,我们需要扩大国际交流,加强学习国外的先进经验。在大学教材建 设上,我们也应该注意学习和引进国外的先进教材。但是,“清华大学计算机系列教材”的出版 发行实践以及它所取得的效果告诉我们,在当前形势下,编写符合国情的具有自主版权的高质量 教材仍具有重大意义和价值。它与国外原版教材不仅不矛盾,而且是相辅相成的。本系列教材的 出版还表明,针对某一学科培养的要求,在教育部等上级部门的指导下,有计划地组织任课教师 编写系列教材,还能促进对该学科科学、合理的教学体系和内容的研究。 我希望今后有更多、更好的我国优秀教材出版 清华大学计算机系教授 中国科学院院士 序 为适应快速发展的形势,计算机专业基础课的教学必须走内涵发展的道路,扎实的理论基础 计算思维能力和科学的方法论是支撑该学科从业人员进行理性思维和理性实践的重要基础。“程 序设计基础”、“面向对象技术”、“离散数学”以及“数据结构”等相关课程,构成了清华大 学计算机系专业基础课程体系中的一条重要脉络。近年来为强化学生在计算思维和实践能力方面 的训练力度,课程组通过研究,探索和实践,着力对该课程系列的教学目标、内容、方法和各门 课的分工,以及如何衔接等进行科学而系统的梳理,进一步明确了教学改革的方冋。在这样的背 景下,由邓俊辉撰写的《数据结构(C++语言版)》正式出版了 为了体现教材的先进性,作者研读并参考了计算学科教学大纲(ACM/ IEEE Computing Curricula),结合该课程教学的国际发展趋势和对计算机人才培养的实际需求,对相关知识点 做了精心取舍,从整体考虑加以编排,据难易程度对各章节内容重新分类,给出了具体的教学计 划方案。 为了不失系统性,作者依据多年的教学积累,对各种数据结构及其算法,按照分层的思想精 心进行归纳和整理,并从数据访问方式、数据逻辑结构、算法构成模式等多个角度,理出线索加 以贯穿,使之构成一个整体,使学生在学习数据结构众多知识点的同时,获得对这门学问相关知 识结构的系统性和全局性的认识。 计算机学科主张“抽象第一”,这没有错,但弄不好会吓倒或难倒学生。本书从具体实例入 手,运用“转换-化简”、“对比-类比”等手法,借助大量插图和表格,图文并茂地展示数据结 构组成及其算法运转的内在过程与规律,用形象思维帮助阐释抽象过程,给出几乎所有算法的具 体实现,并通过多种版本做剖析和对比,引领读者通过学习提升抽象思维能力 计算机学科实践性极强,不动手是学不会的。为了强化实践,本书除了每章都布置人人必做 的习题和思考题外,还有不少于授课学时的上机编程要求,旨在培养学生理性思维和理性实践的 动脑动手能力。 《中国计算杋科学与技术学科教程2θθ2》曾批评国内有关程序设计类的课,一是淡化算法, 是“一开始就扎进程序设计的语言细节中去”。本书十分重视从算法的高度来讲述数据结构与 算法的相互依存关系,在书的开篇就用极其精彩的例子讲清了算法效率和算法复杂度度量的基本 概念和方法,这就给全书紧密结合算法来讲数据结构打下了很好的基础。 这本书是精心策划和撰写的,结构严整,脉络清晰,行文流畅,可读性强。全书教学日标明 确,内容丰富,基本概念和基本方法的阐述深入浅出,最大的特点是将算法知识、数据结构和编 程实践有机地融为一体。我以为,引导学生学好本书,对于奠定扎实的学科基础,提高计算思维 能力能够起到良好的作用。 清华大学计算机系教授 2811年9月 第3版说明 在第2版的基础上,本书第3版推出了配套的《习题解析》,故在体例上也做了相应的调整, 主要包括以下方面 原各章所附习题,均统一摘出并汇编为《习题解析》;除了部分实践型和研究型习题,大部 分习题均提供了详尽的分析和解答 删除了少量习题,同时也补充了若干。大题的总数,已增至292道;因多数习题都是逐层递 进式的,小题的总数已超过588道。 关于伸展树性能分摊分析的原8.1.4小节,作为习题转入《习题解析》 图灵机模型、RAM模型等基本概念,以及(线性)归约、封底估算及基本技巧,也结合对应 的习题予以介绍 同时,结合读者反馈以及新一轮教学实践效果,也在以下方面做了相应修订: 1.4节补充了对记忆策略与动态规划策略的介绍,并通过实例展示二者的联系与区别。 鉴于前四章已经充分地展示了相关技巧,后续 Bintree和 Dictionary等结构不再过于严格 地封装,使读者更好地将注意力集中于这些结构的机理木身 通过多重继承,统一了 ComplHeap、 LeftHeap、 ListHeap等结构的实现方式,使之封装更 紧凑、代码更简洁 精简了 Vector:: mergesort()、 GraphMatrix: insert()、Sp1ay:: splay() RedB1ack:: solveDoublered()、 trivia1 Median()等算法的实现。 关于函数调用栈、栈与递归、 Huffman编码算法等各节的叙述与讲解,也尽可能地做了精简。 统一了“环路”、“众数”、“最左/右侧通路”、“波峰集”、“输入/输岀敏感”等概念 严格了“完全二叉树”等概念以及“黑高度”等指标的定义 参照BFS和DFS的实现方式改进PFS框架,使之支持多个连通域(或可达域)。 借助几何分布等概率模型,简化对跳转表、散列表的平均性能分析 插图、表格、代码等均有大幅增加,关键词索引项进一步细化。 增加了若干重要的参考文献。 修正了原书及代码中的若干错误,详细对比请见勘误表。 最后,鉴于第3版采用双色印刷方式,故在版面及样式等方面也做了相应的调整 第2版说明 本书的初稿完成于2609年冬季,随后在清华大学经过了三个学期共四个课堂的试用,根据 各方的反馈意见做过调整补充之后,第1版于2811年夏季由清华大学出版社正式出版发行。此后, 又在清华大学经过两个学期共三个课堂的教学实践,并汇总读者的反馈进一步修订完善之后,第 2版终于2012年夏季出版发行,也就是目前读者所看到的这个版本。 第2版继承并强化了此前版本的叙述风格,基本保留了总体的体例结构,同时在针对性、简 洁性、实用性和拓展性等方面,也做了大量的修改、删节与扩充。与此前的版本相比较,主要的 变化包括以下几个方面 针对多种数据结构的算法实现及其性能分析,精简了行文叙述与代码实现,比如有序向量的 查找、树和图的遍历、 Huffman编码、平衡二叉搜索树的重平衡、二叉堆的调整等。 更换并补充了大量的实例和插图,比如向量、词典、关联数组、高级平衡二叉搜索树和优先 级队列等数据结构,以及表达式求值、KMP、BM、平衡二叉搜索树的重平衡、字符串散列、 快速排序、中位数及众数等算法的原理及过程等等,插图增至260多组。 重写了多个章节的总结部分,比如针对各类查找算法、串匹配算法,就其性能特点均做了统 的归纳与梳理,指明其中的关键因素以及不同的适用范围 进一步规范和统一了几个基本概念的定义及其表述方式,使得各章节之间的相互引述更趋 致,比如栈混洗、真二叉树、完全二叉树、满树、闭散列策略等概念的定义,以及遍历序列 红黑树不同类型节点等概念的图解示意方式 细化了针对一些关键知识点的讲解,比如第1章的渐进复杂度层次和伪复杂度、第8章中B 树及kd-树的引入动机、第11章中BM算法好后缀策略中的GS[]表构造算法等 添加了大量的习题,总量已超过28道。在帮助读者梳理主要知识点、加深对讲解内容理解 的同时,还从以下方面为他们的进一步拓展,提供了必要的线索:插入排序算法性能与逆序 对的关系、选择排序算法性能与循环节的关系、插值査找、指数査找、马鞍査找、CBA式排 序算法平均性能的下界、栈混洗甄别、栈堆、队堆、算术表达式的组合搜索、键树、关联矩 阵、prim算法与 Krusa1算法的正确性、欧氏最小支撑树、并查集、计数排序、四叉树、八 叉树、范围树、优先级搜索树、树堆、AL树节点删除算法的平均性能、A树的合并与分 裂、堆节点插入算法的平均性能、支持重复元素的一叉搜索树、双向平方试探、轴点构造算 法版本C、希尔排序算法的正确性,等等。 提供了一批相关的参考文献,包括经典的教材专著28余册、拓展的学术论文38余篇 修正了多处排版问题及若干实质错误。请此前版本的读者下载勘误表并做相应更正,同时感 谢我的读者、学生和同行,他们的意见与建议是本教材不断完善的保证。 第1版前言 背景 伴随着计算学科( Computing Discipline)近年来的迅猛发展,相关专业方向不断细化和 分化,相应地在计算机教育方面,人才培养的定位与目标呈现明显的多样化趋势,在知识结构与 专业素养方面对人才的要求也在广度与深度上拓展到空前的水平。以最新版计算学科教学大纲 (ACM/ IEEE Computing Curricula,以下简称CC大纲)为例,2801年制定的CC2601因只能覆 盖狭义的计算机科学方向而更多地被称作CS2881。所幸的是,CC2881的意义不仅在于针对计算 机科学方向的本科教学提出了详纽的指导意见,更在于构建了一个开放的CC2081框架(CC2881 Model)。按照这一规划,首先应该顺应计算学科总体发展的大势,沿着计算机科学(CS)、计 算机工程(CE)、信息系统(IS)、信息技术(IT)和软件下程(SE)以及更多潜在的新学科 方向,以分卷的形式制订相应的教学大纲计划,同时以综述报告的形式概括统领;另外,不宜仍 拘泥于十年的周期,而应更为频繁地调整和更新大纲,以及时反映计算领域研究的最新进展,满 足应用领域对人才的现实需求 饶有意味的是,无论从此后发表的综述报告还是各分卷报告都可看出,作为计算学科知识结 构的核心与技术体系的基石,数据结构与算法的基础性地位不仅没有动摇,反而得到进一步的强 化和突出,依然是计算学科研究开发人员的必备素养,以及相关应用领域专业技术人员的看家本 领。以CC大纲的综述报告( Computing Curricu1a2005- The Overview Report)为例, 在针对以上五个专业方向本科学位所归纳的共同要求中,数据结构与算法作为程序设计概念与技 能的核心,紧接在数学基础之后列第二位。这方面的要求可进一步细分为五个层次:对数据结构 与算法核心地位的充分理解与认同,从软件视角对处理器、存储器及显示器等硬件资源的透彻理 解,通过编程以软件方式实现数据结构与算法的能力,基于恰当的数据结构与算法设计并实现大 型结构化组件及其之间通讯接口的能力,运用软件工程的原理与技术确保软件鲁棒性、可靠性及 其面向特定目标受众的针对性的能力 自28世纪末起,我有幸参与和承担清华大学计算机系以及面向全校“数据结构”课程的教 学工作,在学习和吸收前辈们丰富而宝贵教学经验的同时,通过悉心体会与点滴积累,逐步摸索 和总结出一套较为完整的教学方法。作为数据结构与算法一线教学工作者中的一员,我与众多的 同行一样,在为此类课程的重要性不断提升而欢欣鼓舞的同时,更因其对计算学科人才培养决定 性作用的与日俱增而倍感责任重大。尽管多年来持续推进的教学改革已经取得巨大的进展,但面 对新的学科发展形势和社会发展需求,为从根本上提高我国计算机理论及应用人才的培养质量, 我们的教学理念、教学内容与教学方法仍然有待于进一步突破。 与学校“高素质、高层次、多样化、创造性”人才培养总体目标相呼应,我所在的清华大学 计算机系长期致力于培养“面向基础或应用基础的科学技术问题,具备知识创新、技术创新或集 成创新能力的研究型人才”。沿着这个大方向,近年来我与同事们从讲授、研讨、作业、实践、 考核和教材等方面入手,在系统归纳已有教学资源和成果的基础上,着力推进数据结构的课程建 设与改革。其中,教材既为所授知识提供了物化的载体,也为传授过程指明了清晰的脉络,更为 教师与学生之间的交流建立了统一的平台,其重要性不言而喻。继28θ6年出版《数据结构与算 法(Java语言描述)》之后,木教材的出版也是作者对自己数据结构与算法教学工作的又一次 系统总结与深入探索。 原则 在读者群体定位、体例结构编排以及环节内容取舍等方面,全书尽力贯彻以下原则。 兼顾基础不同、目标不同的多样化读者群体 全书12章按四大部分组织,既相对独立亦彼此呼应,难度较大的章节以星号标注,教员与 学生可视具体情况灵活取舍。其中第1章绪论旨在尽快地将背景各异的读者引导至同一起点,为 此将系统地引入计算与算法的一般性概念,确立时空复杂度的度量标准,并以递归为例介绍算法 设计的一般模式;第2至7章为基础部分,涵盖序列、树、图、初级搜索树等基木数据结构及其算 法的实现方法及性能分析,这也是多数读者在实际工作中最常涉及的内容,属于研读的重点;第 8至18章为进阶部分,介绍高级搜索树、词典和优先级队列等高级数据结构,这部分内容对更加 注重计算效率的读者将很有帮助;最后两章分别以串匹配和高级排序算法为例,着重介绍算法性 能优化以及针对不同应用需求的调校方法与技巧,这部分内容可以帮助读者深入理解各类数据结 构与算法在不同实际环境中适用性的微妙差异。 注重整体认识,着眼系统思维 全书体例参照现代数据结构普遍采用的分类规范进行编排,其间贯穿以具体而本质的线索, 帮助读者在了解各种具体数据结构之后,通过概括与提升形成对数据结构家族的整体性认识。行 文从多个侧面体现“转换-化简”的技巧,引导读者逐步形成和强化计算思维( computationa1 thinking)的意识与习惯,从方法论的高度掌握利用计算机求解问题的一般性规律与方法 比如从逻辑结构的角度,按照线性、半线性和非线性三个层次对数据结构进行分类,并以遍 历算法为线索,点明不同层次之间相互转换的技巧。又如,通过介绍动态规划、减而治之、分而 治之等算法策略,展示如何将人所擅长的概括化简思维方式与计算杋强大的枚举迭代能力相结 合,高效地求解实际应用问题。再如,从数据元素访问形式的角度,按照循秩访问、循位置访问 或循链接访问、循关键码访问、循值祊问、循优先级访问等方式,对各种数据结构做了归类,并 指明它们之间的联系与区别。 通过引入代数判定树模型以及对应的下界等概念,并讲解如何针对具体计算模型确定特定问 题的复杂度下界,破除了部分读者对计算机计算能力的盲目迷信。按照CC大纲综述报告的归纳结 论,这也是对计算学科所有专业本科毕业生共同要求中的第三点—不仅需要了解计算机技术可 以做什么( possibi] ities)以及如何做,更需要了解不能做什么(1 imitations)以及为什 么不能做。 尊重认知规律,放眼拓展提升 在相关学科众多的专业基础课程中,数据结构与算法给学生留下的印象多是内容深、难度大, 而如何让学生打消畏难情绪从而学有所乐、学有所获,则是摆在每位任课教师面前的课题。计算 机教学有其独特的认知规律,整个过程大致可以分为记忆( remember)、理解( understand)、 应用(app1y)、分析(ana]yze)、评估( evaluate)和创造( create)等若干阶段,本书 也按照这一脉络,在叙述方式上做了一些粗浅的尝试。 h