考研_专业课_数据结构

---

2023/7/12 21:30 本来今天晚上是打算再看一会数学的，但是实在是看不下去了，数学这个科目一天看太久了真的会变得及其没有效率（当然晚上熬夜玩手机会导致第二天早晨也没有效率，这两个的原因不同但是造成的结果是相同的）；最近反正也没什么事情就打算开始把专业课拿起来复习一下，最好就是感觉自己没有效率的时候看一看，先过一遍知识点，其他的怎么复习相关的细节到时候再根据临时情况补充即可；其实在我之前的博客中是有写过很多有关数据结构或者算法相关的文章的，比如力扣算法经典题目刷题、北邮算法设计与分析以及大话数据结构笔记，但是无论写过多少次，根据“不使用就会遗忘”定律，现在我基本上已经把数据结构的知识点都忘得差不多了（而且当时的知识点总结的很差，根本不适合用来考研复习）；写这篇博客的目的就是结合之前学过的知识点(整理过的笔记)以及北邮官方的数据结构和算法教材，专门针对809数据结构考研进行一个模块化的学习（就是为了应付考试所以才写这篇博客）；

2023/7/13 20:14 因为实际上北邮本身的教材就足够有参考意义，所以这里第一遍过知识点的之后我就尽量不参考其他的资料包括之前做的笔记，完全按照教材上的内容对知识结构进行总结，遇到实在很难理解或者比较超纲的知识点再选择其他资料参考；

2023/7/14 22:20 因为数据结构这门课程本身就有一定的不严谨，所以无论是北邮的教材还是大话数据结构其实有些概念会令人误解，所以在学习的时候不要过度去解读某些概念，只要能够按照自己的思维方式理解区分就行。另外，之前做的数据结构的笔记是真的垃，现在看来那个笔记中能够借鉴的东西非常少，可能也就ADT的定义可以借鉴，其他的具体存储结构实现代码什么的就完全按照北邮教材来就行（知识框架的结构也按照北邮教材来，之前笔记中的结构有问题，容易让人产生误解）；

2023/7/15 20:23 这个只能慢慢看，反正现在也不着急，最重要的是打好基础所以一定要书上的基本知识点掌握牢靠，宁愿多做一些笔记也是可以的。需要注意的是做笔记一定要做好目录知识结构的整理，这对形成整体的知识体系极其重要；

2023/7/16 21:30 数据结构第一遍过就是按照现在这样把书上的知识点整理到笔记上形成完整的知识结构即可。至于知识点会遗忘是肯定的毕竟高数你都不能全部记住别说数据结构才刚开始。数据结构因为有基础所以看起书来基本上没什么问题，第一遍过数据结构的目的就是把所有考纲规定的知识点整理在一起。整理完之后再集中精力刷题；

2023/7/17 22:27 并没有将书上的所有知识点都详尽的整理在笔记中，只是将最基础的知识点整理了出来。针对某些拓展性问题（比如课后思考题等）现在没有必要去思考该怎么解决，那是之后第二轮刷题的时候应该做的事（现在就算看懂了过段时间也可能会忘记）；

2023/7/20 12:47 这个书上有些答案是错的，比如说KMP那一节的next数组求解书上完全就是乱写的…所以也不要过度相信教材上的“金科玉律”，适当觉得看不懂的时候就上网寻找标准答案不要浪费时间在那里纠结是否是教材出错或者是否是教材太难理解（这两个没有本质区别，这个教材有些地方就喜欢把简单的讲的很难真服了…）。另一点就是卡尔的哪个前缀表的求法也是错的，也就是说教材和卡尔的方法都是错的（我也不知道为什么你运气这么好就刚好碰上），所以花了一个上午在那里不知道干什么，属于是被自己的定势思维坑了。反正现在第一遍做的笔记也不能全部认为是百分百正确的，之后还要在反复的刷题过程中不断验证；

2023/7/20 17:34 之所以前期花费很多功夫去琢磨一些字眼上的概念就是为了在重塑知识体系的时候能够更加清晰明了，加快后期的复习速度（这一点的优势其实已经体现出来，现在能够对书上那些编写有问题或者说不严谨的地方进行再整理）。数据结构的课程中穿插了一些算法相关的知识点，这些出现的知识点无疑是非常重要的考研肯定会考察的，但是我想放在之后学习完所有的数据结构之后再回头专攻算法，所以书上做了标记的地方表示跳过后期需要回头整理的知识点；

2023/7/20 22:52 感觉你被之前做过的无效笔记搞得很恼火啊，我再说一遍，像什么高数之类的你都全盘推翻了，更别说这个数据结构了，之前你做过的那些笔记说实话就没什么可以参考的意义（因为做的真的太简单了…完全就只是写了个大概的框架，另一点是有些知识点和教材上的知识点不兼容…甚至都是错的）。所以之后做笔记之前的那个参考笔记就真的只是用来看看就行，一切都以教材为主，其他的参考教材啊参考资料什么的都放一边不要扰乱自己的心态！！！（最近心态真的太容易受影响了，把这段时间作为一个考验熬过去吧…加油！！）

2023/7/22 22:11 截至目前，基本的数据结构已经复习完毕（剩下的算法相关放在之后刷题过程中进行）；接下来需要做的就是把教材上的题刷一遍巩固知识点，如果说第一遍仅仅只是快速的过知识点的话，第二遍就需要完全静下心来好好的理解消化；

数据结构一轮复习完毕

2023/7/23 21:28 北邮教材上的习题给我一种不是特别全的感觉？？？…怎么办呢，初步先把北邮教材上的题刷一遍（毕竟整理的笔记就是按照北邮教材来整理的，刷题是为了进一步巩固知识点）；完了第二遍就可以找王道数据结构上的题来刷，进一步的加大题量，无论如何不要同时使用多种教材，这只会带来负面影响。另外北邮的那本参考答案上面有很多详细的讲解，暂时因为状态原因先不看，但个人认为是非常重要的考点，后期还是需要回过头来看（一句话概括就是北邮的两本教材是重中之重，吃透了这门专业课肯定不成问题，所以无论怎么安排这两本书一定要完整的看完并非常熟练）

2023/7/24 21:28 书上出现的每一道例题以及辅导教材上的相关文字都应当仔细阅读并理解，再次强调这两本书就是考研的致胜法典，因此说是逐字逐句或者咬文嚼字的阅读这两本教材都是没有任何夸大成分的。现在是第二轮的强化理解阶段，不要求你刷很多题，只需要静下心来好好看书慢慢理解吃透考纲上的每个数据结构以及算法即可；

2023/7/25 20:29 最近是真的大晚上的复习数据结构那是一个看不进去啊…感觉就像是强行往脑子里面塞东西似的，我不知道是不是因为白天做数学把精力耗费的太多的缘故，如果真的是这样的话可以适当调整把线代和概率论放在晚上（毕竟也已经过完一遍，不需要那么细致的磕知识点）。反正现在的状态就是强行让自己坚持学习，关于数据结构的复习策略我并没有完全按照网上推荐的来，反正如果什么时候觉得进度不合适或者方法不行的话就适当停下来在网上找找相关的复习建议，这里贴一个看到的比较好的文章数据结构考研如何120+可适当参考（注意一定是适当，这文章里的东西不能按部就班）；

2023/7/27 22:00 之前数据结构复习的规划有问题，这里调整一下。静下心来把高分笔记和配套的练习题全部过一遍，最后北邮的教材和对应的习题可以稍微练一练。之前跟着北邮的教材进行复习真的很懵，看完一遍之后完全抓不住重点（另一方面很可能是因为你自己当时把重心放在了过知识点整理知识点而不是细心理解上，无论如何第二遍的复习必须将每一节的知识点都吃透）。因此这里暂时调整数据结构的复习重心全部放在高分笔记及其练习题上，其他的资料可以先不用看，保持复习资料的简洁；

2023/7/30 20:03 最近也是花了不少的时间在复习数据结构上，但是这门科目给我的感觉非常奇怪（与其他两门课的真的很不一样），没有复习的正反馈不说（最近开始手写代码才有一点点的满足感），我根本抓不住复习的重点啊…也不是说什么复习资料找的不够好还是怎么的，现阶段我基本上把市面上数据结构相关的复习资料全部整理完毕了，我选择的资料肯定是最适合复习的，但是仍然出现这样的问题就让我百思不得其解（就因为这门课我真的在很多时候莫名其妙的焦虑和烦躁，我甚至都不想复习这门课…有抵触情绪了属于）。刚刚突然有一点感想，选用的天勤数据结构，这本教材我们确实需要静下心来看，结合手写代码（选用天勤的代码是因为真的很好理解）能够把最基本的数据结构和基本算法操作完全掌握。这本书的槽点在于它经常给你一些例题啥的，这种例题的代码非常的长而且非常的综合，我真的很不喜欢这种感觉，为什么不能分门别类的将各个算法的基本操作介绍完毕之后再通过例题进行强化训练呢？是否本末倒置？（王道刚好与它相反，但是王道我们放在后面再用别混着用）因此在接下来的复习过程中，我们只需要将书上的重要知识点以及基本代码掌握（这里所说的掌握就是真的能够熟记于心的掌握而不是第一遍那种走马观花），对于那种大综合的例题什么倒置算法啊归并算法这种属于面试或者考察大题的算法题放在之后统一整理（卡尔的数据结构那种分类方式相当好，通过按照不同的数据结构来区分算法题，让我们知道不同的数据结构能够考出什么花样） – 说白了你现在觉得没有正反馈看的很难受就是因为这些教材的组织方式，相当于让你边学基本功边修炼高级功法，这对基础好的人来说可能很爽但是对于脚踏实地想要一步步打怪升级的复习者来说不是一个值得推荐的行为 – 漂亮！刚才无意间刷到了天勤数据结构的配套视频，然后发现这个视频上面的分类还挺好的（那个书的主要问题是有些介绍不够详细并且考点总结的不是很系统，刚好它的配套视频在一定程度上弥补了这两方面的缺陷），所以现在再次调整复习方案，在第二遍的基础复习的过程中结合天勤的视频(视频链接哔哩哔哩_bilibili（B站有字幕）)把书上的知识点好好的掌握；

2023/8/1 17:20 八月份如约而至，不管之前复习的咋样状态咋样，现在都应该按照原定计划加入专业课和政治课的复习。现在唯一有一点点复习问题的就是专业课，因为前期无脑乱冲导致从复习资料的选取一开始就犯下了错误，进而导致之后的半个多月的复习效果非常差，甚至打击到了本人的自尊心。好在经过不断地探索和试错之后总结出了一套适合我自己的数据结构专业课的复习方法，这里简单概述一下方便之后回顾。首先是参考书的选择，暂时选定的是王道、天勤以及北邮数据结构(包括拓展教材)一共四本，严的数据结构因为难度较大且暂时没有更多的时间去试错，所以在前期不考虑。之所以选择这四本作为参考资料而不是像其他学科一样只跟一本的原因是，这三本教材各有各自的优点但是又有对方不具备的缺点。王道和天勤的书作为第二轮的复习主力，天勤主要还是拿给我抄代码使用（毕竟天勤是真的简单易懂），王道主要指明有哪些要考的知识点，至于北邮的两本教材推荐放在最后使用，里面有一些非常牛的算法设计思路以及新题型是王道和天勤这种针对408统考而设计的辅导书不具备的，但是因为北邮的两本教材难度实在是有点大所以真的不推荐一上来就抱着啃（不管是算法思想还是代码风格都挺需要花时间去消化，这个在第一轮的时候已经领教过）。截止目前我已经把四本书的第一章也就是绪论全部攻克（这意味着之后没有必要再花时间在这四本书的第一章上面），接下来从线性表开始就属于是真正的考纲要求的内容，暂时定下来的复习方法是先看天勤的书然后手写重要代码跟着走一遍，完了看王道的书把要考的知识点和课后题刷一遍，最后将天勤和王道上面剩余的具有代表性但不是基础性的算法代码进行总结归纳（总结归纳还是得整理到笔记上，可以重新开一个专门的手写代码笔记模块，便于之后的复习回顾）；将王道和天勤对应章节的内容全部理解完毕之后就可以看北邮的两本教材，注意无论是看哪本书，如果出现超纲的内容就暂时放弃放在后面回顾的时候再来整理（相较于408数据结构就一门科目，所以这四本教材反复被翻阅其实也不是什么难事，后期反复总结是常有的事）。

2023/8/4 16:50 刚才刷完了王道线性表的例题，也标志着线性表的基础理论知识这部分已经全部完成（高级算法设计放在后续强化阶段进行），这里我简单总结一下最新的这种复习规划是否有效以及后续的安排。这一段时间的数据结构复习主要使用的就是两本书，《王道数据结构》和《天勤高分笔记》，至于北邮的那两本教材基础性的知识早就在“快速过一遍”那会总结到这篇blog上了，剩下的也都是具有创新意义和思考价值的高级算法设计题，针对我们现在第二阶段的“慢慢打基础”作用不大。我简单把数据结构的复习归为这几个阶段：快速过一遍、慢慢打基础、强化提高、极限冲刺。现在正是处于慢慢打基础的时候，需要做的主要就是把王道和天勤上面有关基本数据结构的代码和基本算法思想全部消化和吃透，而针对这两本书以及北邮两本书上的高级算法设计题专门放在强化提高的阶段来进行（因为很多设计题的思想其实并不是只适用于一种数据结构）。最后极限冲刺打算刷刷真题卷即可，数据结构这门课程急不得，更多的是需要去理解和背诵，所以我并没有按照网上说的那样假期就开始刷真题（其实和高数复习是一个道理，需要一遍又一遍的巩固，刷100道题还不如吃透同一种出题思想。）因为数据结构的复习参考确实不多所以一开始确实显得有点手忙脚乱，但是这段时间的磨合调整还是有一定的作用的，继续坚持下去，这样的复习规划确实可行。“慢慢打基础阶段”，针对每一章，先看天勤的书，总结算法代码并刷题，再看王道的书，拓展算法代码并刷题，两本书上的知识点注意都需要总结到这篇blog上（不要总是想着总结总结，花费大量时间用于总结在前期或许是一件性价比较高的行为，但是在后期时间紧张的情况下无脑刷题背知识点就OK）。

2023/8/31 20:29 天勤的视频说实话讲的真的很好，而且针对书上没有的知识点也有更进一步的探讨，所以之后回顾过程中如果有疑问可以参考天勤视频，同时搭配有对习题的讲解，刷题刷不动可以适当听一听；

2023/9/2 16:49 截止目前，数据结构第二轮的全面复习结束（尽管可能还有比如说某些算法设计没有细致学习，或者如B+树这种新颖困难知识点还不是很懂/得刷题巩固理解）。数据结构这门课程不同于其他三门，它极度依赖于教材，因此在之后的几轮复习过程中不能丢掉三本主要参考教材，争取做到把这三本教材背下来。强化阶段的工作目前还没有做好打算，合适的时候找一找相关资料作为复习指导。

数据结构二轮复习完毕

2023/9/5 16:08 通过借鉴他人总结的数据结构资料，我才明白天勤上面的知识点原来这么全面，而且几乎是明确区分了重点和非重点，因此之后的复习天勤确实需要作为主力教材；

突然之间不需要考研了…再写点东西

2023/9/25 20:28 最近打算把这部分知识点和代码那篇博客做一个结合，便于学习和记忆。因为数据结构属于应用学科，因此没有哪个代码可以说是万精油，同理，没有任何一本教材可以说自己能够涵盖考研数据结构的所有内容。学数据结构不要背代码，需要我们去理解其内部核心思想（比如顺序表的删除的实质就是移动元素）并养成自己的代码风格。写一个完整并且易于记忆的复习指导难度确实很大，每天没事的时候写一写，反正也不着急，将其作为放松的方式即可；

2023/10/24 20:18 本来是打算把知识点汇总上面的代码全部整理到这篇博客里面，但是最近事情太多了，做这件事情的性价比相对来说也不是很高，所以暂时就搁置（即现在这篇博客单循环链表之前是整合过的，单循环链表之后就是原始版本）。这并不意味着这篇博客没有参考价值，作为快速回顾复习数据结构的资料还是很不错的。如果想看之前没有整合的版本我放在了github仓库

• blog_backup/考研_专业课_数据结构.pdf at master · Gintoki-jpg/blog_backup (github.com)；

---

第一章 绪论

在开始全书的章节之前一定要先辨析“数据结构”和“算法”这两个概念是有区别的，也就是说实际上“数据结构与算法”是两门课程，分别是“数据结构设计”和“算法设计”，对应大学期间大一和大三学习的两门课程，这两门课程的侧重点是不同的。下面简单说明“数据结构”和“算法”之间的联系和区别。

现实世界中的所有问题都可以归类为两大类：

• 数值计算问题：如概率统计、求极限、求面积，该类问题一般采用数学建模、公式推导来解决；
• 非数值计算问题：如图书管理问题、对弈问题、路由问题，该类问题一般使用数据结构与算法来解决；

程序设计（也就是利用编程来解决现实生活中的非数据计算问题）主要关注两个方面：

• 数据表示：考虑如何将待处理的数据存储到计算机中，其本质是数据结构设计（研究如何将现实生活中的复杂数据合理高效的存储在计算机中的方法）；
• 数据处理：使用何种逻辑来操作这些数据，其本质是算法设计（研究面对实际问题需要进行的操作如增加、删除、修改、查找某一本书的方法，简单来说算法主要研究如何进行高效稳定的查询、删除以及其他操作）；

不同的数据结构设计会对应不同的算法设计，进而导致设计的程序具有不同的执行效率。

1.数据结构的基本概念

• 数据（data），是信息的载体，能够被计算机识别、存储和加工处理。在计算机领域中，人们通常将数据分为两大类：一类是数值型数据，如代数方程求解程序中所使用的整数或实数数据；另一类是非数值型数据，如音视频播放器程序播放的声音或视频、互联网络中的Web数据等。
• 数据元素（data element），是数据的基本单位，在计算机程序中通常作为一个整体进行处理。例如，学生成绩单中每个学生的信息就是一个数据元素。有些情况下，数据元素也称为元素、结点、顶点或记录。
• 数据项（data item），是构成数据元素的不可分割的最小单位。每个数据元素可以包含多个不同的数据项，每个数据项具有独立的含义。例如，学生成绩单中每个学生的信息可以包含学生的班级、学号、姓名、成绩等，这些都是数据项。有时也将数据项称为字段或域。
• 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
• 数据类型（data type），是具有相同性质的计算机数据的集合以及在这个数据集合上的一组操作（简记为“一个值得集合和定义在这个值集合上的一组运算的总称”）。数据类型可以分为简单类型（或称为原子类型）和构造类型（或称为结构类型）。例如，C++语言中，整数、实数、字符等都是简单的数据类型，而数组、结构类型、类等都是构造类型。每种类型的数据都有各自的特点及相关运算。可以将一种数据类型看成是一种实例化了的数据结构。
• 数据结构（data structure），是指按照某种逻辑关系组织起来的一组数据，按一定的存储方式存储在计算机的存储器中，并在这些数据上定义了一组运算的集合。通常人们认为数据结构包含以下 3 个方面的内容
  • 数据元素之间的逻辑关系，也称为数据的逻辑结构（logical structure）
  • 数据元素及其关系在计算机存储器内的存储形式，称为数据的存储结构（storage structure）或物理结构
  • 对数据的基本操作或运算

Tips：上述数据结构的定义出自北邮《数据结构与算法》，被认为是一种广义上的定义（严蔚敏的《数据结构》中有提到过，有关“数据结构”的定义至今没有一个统一的定论）。

1.1 逻辑结构

数据的逻辑结构描述了数据相互间的关联形式或邻接形式，反映了数据内部的构成方式，定义了数据的本质特点，因此人们常常将数据的逻辑结构直接称为数据结构。数据的逻辑结构独立于计算机，与存储方式无关，可认为是从具体问题抽象出来的数学模型。数据元素之间不同的逻辑特点代表不同的逻辑结构，常见的逻辑结构有4种，分别是集合、线性结构、树和图。

• 集合，其数据元素之间的逻辑特点是满足“共同属于一个集合”的关系。通常要求集合中的元素不可重复，不考虑元素之间的先后次序。
• 线性结构，其数据元素之间的逻辑特点是有且只有一个起始结点和一个终端结点，并且其他结点的前面有且只有一个结点（称为直接前驱），每个结点的后面有且只有一个结点（称为直接后继）。线性结构的数据元素之间在一维线性空间中有确定的先后次序。
• 非线性结构，这种结构区别于集合和线性结构
  • 树结构，其数据元素之间存在着一对多的层次关系。
  • 图结构，数据元素之间存在着多对多的关系。

1.2 存储结构

数据的存储结构考虑的是如何在计算机的存储器中存储各个数据元素，并且同时反映数据元素间的逻辑关系。对于每种逻辑结构，都可以设计多种存储方法，基本的存储结构通常有两大类：顺序存储结构和链式存储结构。

• 顺序存储结构，即用一组连续的存储单元依次存储各个数据元素。数据元素间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构借助于程序设计语言的数组来描述。
• 链式存储结构，即用一组任意的存储单位存储各个数据元素，数据元素间的关系通常用指针来表示，例如，后一个元素的地址存储在前一个元素的某个特定数据项中。

---

Q：数据的逻辑结构和存储结构之间有什么关系？

A：数据的逻辑结构反映了数据内部的逻辑关系，是面向实际问题的；而存储结构是面向计算机具体实现的，其目标是将数据及其逻辑关系存储到计算机中。仅有逻辑结构，只能确定对数据有哪些操作，而如何实现这些操作是不得而知的。因此，只有确定了数据的存储结构，才能设计对数据的具体操作算法。而且对于相同逻辑结构的同一种操作，如果采用不同的存储结构进行存储，对数据处理的效率往往也是不同的。因此，需要根据对数据的操作来设计合理的存储方式，以提高处理效率。上述逻辑结构和存储结构以及算法之间的关系为接下来学习不同的数据结构提供了指导思想：

1. 首先分析其逻辑结构；
2. 基于逻辑结构学习其各种常见的存储结构；
3. 针对每种存储结构研究各种算法的实现；

总的来说，数据结构课程重点之一就是研究各种逻辑结构的不同存储结构。

---

1.3 抽象数据类型ADT

数据类型是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称，因为不同的数据类型有不同隐藏的细节，进而引出了抽象数据类型ADT的概念

抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系以及对数据元素的操作。ADT体现了程序设计中对问题的分解、抽象和信息隐藏的特性

为了便于在之后的学习中对抽象数据类型进行规范的描述，给出如下抽象数据类型的标准格式

ADT 抽象数据类型名
Data （数据集合和数据关系集合）
    数据元素之间逻辑关系的定义
Operation（操作集合）
    操作1
    操作2
    操作3
    ......
endADT

举例说明

• 栈的抽象数据类型可以描述为：插入和删除只能在一端进行的线性表；
  • 数据对象集合是存储在栈内的数据元素
  • 操作集合为元素进栈、元素出栈、判断栈空等操作
  • 数据关系集合为一对一（线性表是一对一，树是一对多，图是多对多）
• 队列的抽象数据类型可以描述为：插入元素只能在一端进行，删除元素只能在另一端进行的线性表；
  • 数据对象集合是存储在队列内的数据元素
  • 操作集合为元素进队、元素出队、判断队空等操作
  • 数据关系集合为一对一

设计ADT的题目需要注意以下几点：

1）注意 ADT 的结构格式，类似于 C 语言的结构体的写法
2）ADT 大括号内用数据对象集、数据关系集和操作集分开（或者参考上述代码块中用Data和Operation分开）
3）考研中出现的题目，一般必有数据对象集。
4）如果数据对象之间有很强的关联性，则应写出合适的数据关系集。如果遇到树形结构或图结构的数据关系，则用类似的边集表示方法写出。考研中最可能出现的 4 种关系：没关系、顺序关系、树形关系和图关系。
5）若有操作集，则写出。
6）不同的数据对象类型，自上而下依次列出
7）相同类型的数据对象，用集合表示法写出，一般考研中涉及的题目用集合的列举法表示即可
8）不同的操作自上而下依次列出

---

Q：抽象数据类型和逻辑结构之间有什么关系？

A：参考链接(5条消息) 数据结构、数据类型、抽象数据类型之间的关系_抽象数据类型和数据结构的关系_Xu Ricol的博客-CSDN博客；

不妨从抽象数据类型和逻辑结构之间的形式定义上入手

• 逻辑结构的形式定义为一个二元组(D,S)，其中D是数据元素的有限集，S是D上关系的有限集；
• 抽象数据类型的形式定义为一个三元组(D,S,P)，其中P是对D的基本操作集合；

抽象数据类型描述了数据的逻辑结构和抽象运算，通常用(数据对象，数据关系，基本操作集)三元组表示，从而构成一个完整的数据结构定义；

---

2.算法的基本概念

2.1 算法定义

算法的基本定义：算法是指对数据的操作方法的描述，即解决一个特定问题的一系列步骤，是指令的有限序列，其中每一条指令有一条或多条操作。

算法可以使用多种方法来描述，如自然语言、流程图、伪代码(也被称为算法语言)、程序设计语言(如C、Python)或其他约定的语言。能够使用程序设计语言描述最好，但对于初学者来说掌握基于C++语言的伪代码来描述算法即可。

算法是解决问题的方法，从计算机的角度来看算法是由若干条指令组成的有穷序列，通常一个问题可以有多种不同的算法，无论什么算法都必须满足以下5个准则(五大特征)：

1. 输入：具有 0个或多个输入的参数。
2. 输出：算法执行要有输出结果，不同的输入通常对应不同的输出。
3. 有穷性：算法中每条指令的执行次数必须是有限的，也就是说算法在执行了有穷步后能够结束（算法和程序的区别，程序可以不满足有穷性，如操作系统）
4. 确定性：每条指令必须有确切的含义，无二义性。简单来说就是相同输入只能有相同的输出。
5. 可行性：每条指令的执行时间都是有限的。

注：算法可以没有输入，但不能没有输出

在满足上述五大特征的基础上，要设计一个“好”的算法，通常需要实现以下目标：

• 正确性
• 可读性
• 健壮性
• 高效率与低存储需求

2.2 算法分析

2.2.1 时间复杂度

算法的时间复杂度是对算法执行时间的度量。

• 算法的执行时间往往与算法本身、计算工具以及问题的规模等因素相关。
• 在分析算法的时间复杂度时，可以忽略计算工具的因素。
• 问题规模通常是指算法处理的数据量的大小，例如对同一个排序算法，对10个数排序和对10000个数排序的执行时间是不同的。在分析时间的复杂度时要处理的数据量往往不能确定，因此通常将问题规模设为n作为参数分析。运行算法所需要的时间T可以看作是问题规模n的函数，记作T(n)。

一个算法的执行时间，应该是该算法每条语句执行的时间之和。假定每条语句执行一次所需的时间是单位时间，则每条语句执行的时间正比于该语句执行的次数。通常将语句执行的次数称为该语句的频度（frequency count）。算法运行所需要的时间可认为是算法中所有语句的频度之和。

在分析时间复杂度时，也可以直接利用算法中的基本语句进行计算。所谓基本语句，是指其执行次数与算法的执行次数成正比的语句。

常见的时间复杂度有：常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2^)、立方阶O(n^3^)、k次方阶O(n^k^)、指数阶O(k^n^)等，通常认为具有指数阶量级的算法是不可计算的

随问题规模n的增大，上述时间复杂度的增长率依次增大

其大小关系如下
$$
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$

结论1：对于实现同样的功能，递归函数的执行效率往往比非递归算法的效率低得多（即时间复杂度更大）；

(1)递归函数时间复杂度分析

若算法调用递归函数，其时间复杂度分析较为复杂，通常将其时间复杂度的分析转化为一个递归方程的求解渐进阶的问题。递归方程的形式有多种多样，因此求解方法也有不同，比较常见的方法如：

（1）代入法（Substitution Method）：先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。
（2）迭代法（Iteration Method）：迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。

（3）套用公式法（Master Method）：该方法针对形如“T（n）=a*T（n/b）+f（n）”的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子问题的解的综合，得到原问题的解。
（4）差分方程法（Difference Formula Method）：可以将某些递归方程看成差分方程(数三专有考点)，f通过解差分方程的方法来解递归方程，然后对解做出渐近阶估计。

理论知识点可以参看链接递归方程渐近阶的求解，具体时间复杂度这一节还是应该落实到刷题+整理笔记上，建议自行总结常见时间复杂度的题型和求解方法。

(2)加法法则和乘法法则

注意这里的加法法则和乘法法则与先前概率论中介绍的概念不同，此处

• 加法法则指的是程序总时间复杂度=量级最大的代码段的时间复杂度，即T(n)=O(max(f(n),g(n)))
• 乘法法则指的是嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，即T(n)=O(f(n)*g(n))

2.2.2 空间复杂度

算法的空间复杂度是指算法在执行过程中所耗费的存储空间。一般来说，算法的空间复杂度也是问题规模n的函数。早期的计算机系统内存较小，因此在设计算法时往往需要在很大程度上将注意力放在如何降低算法运行时占用的空间。随着计算机内存储器成本的降低及存储容量的不断增大，常常可以牺牲算法的空间效率来获得其更高的时间效率。当然，如果问题规模n很大，算法的空间效率也是非常重要的，此时也需要准确分析其空间复杂度，如海量数据处理问题。

考点：

1. 算法原地工作是指算法所需的辅助空间为常量O(1)
2. 对于递归算法，其空间复杂度等于递归调用的深度

2.2.3 NP问题

将以多项式时间解决为衡量标准的问题归为三大类：

1. NP多项式复杂程度的非确定性问题；
2. NP完全问题；
3. NP难度问题；

对于某个问题，若存在以问题规模 n为变量的多项式函数 p（n），解决该问题的算法的时间复杂度为O（p（n）），则称该问题为多项式时间问题（polynomial time problem），简称P问题，或者说，如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。其解决算法为多项式时间算法（polynomial time algorithm）。例如，时间复杂度为O(1)、O(3n^3^)等的算法均为多项式时间算法。

另外一类算法，其任何时间复杂度函数都不能用多项式函数去界定，这类算法称为指数时间算法。例如时间复杂度为O(2^n^)、O(n^n^)的算法都可以认为是指数时间算法。如果问题规模n很大，显然多项式时间算法优于指数时间算法。

对于很多问题，可能不清楚是否存在一个能在多项式的时间里解决它的算法，但可以在多项式的时间里验证一个解，这种问题称为非确定性多项式时间问题（non-deterministic polynomial time problem），简称NP问题，显然 P包含于NP。

例如，大的合数分解质因数的问题，没有一个公式，把合数代进去，就直接可以算出它的因子。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这就是非确定性问题。而这些问题通常有个算法，它不能直接告知答案是什么，但可以告知，某个可能的结果是正确的还是错误的。这个可以告知“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就称作NP问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就称作NP完全问题，也称作NPC问题。例如，教学安排中的排课算法就是一个 NPC问题。

NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。若 NP 中所有问题到某一个问题是图灵可归约的，则该问题为 NP-hard问题。NP-hard问题不一定是一个NP问题，但所有的 NP问题都可以约化到该问题。例如，售货员旅行问题即 TSP（Traveling Salesman Problem）问题，是最具有代表性的 NP 问题之一。

（其实上面讲的已经足够直观了…但对于初学者来说可能真的很难理解，可以再去网上找一找相关的资料辅助理解）

3.STL概述

(这部分不是考纲上的内容，属于北邮本科教学的拓展，此处仅做简单介绍。关于STL在另外两篇博客中有非常详细的介绍，分别是STL初级和STL中级)

STL（Standard Template Library，标准模板类）是 C++语言提供的一个基础模板集合，包含了各种常用的存储数据的模板类及相应的操作函数，为开发者提供了一种快速有效的访问机制。

通常认为STL由空间管理器、迭代器、泛函、适配器、容器和算法 6 部分构成，其中前面4部分服务于后面两部分

• 空间管理器为容器类模板提供用户自定义的内存申请和释放功能。默认情况下STL仍然采用C/C++的内存管理函数或操作符来完成动态内存的申请和释放。用户也可以不使用这些方法，而采用自己重新定义的新策略来实现内存管理，但这往往只有高级用户才有改变内存分配策略的需求，因此空间管理器对于一般用户来说并不常用。

• 迭代器（iterator）类似于指针，存储某个对象的地址或者说指向某个对象，有时也被称为广义指针。迭代器可以为STL中的算法提供数据输入，也可以用来遍历容器类或流中的对象。指针本身也可以认为是一个迭代器，用户也可以自定义迭代器。

• 在STL中，如果某个类重载了函数调用运算符“（）”，则称该类为泛函类，并称其对象为泛函。通过引入泛函，可以为算法提供某种策略。例如，同一个排序算法，可以利用泛函完成对不同关键字进行升序或降序等各种排序策略。

• 适配器对象将自己与另外一个对象绑定，使对适配器对象的操作转换为对被绑定对象的操作。STL中适配器应用较广，有容器适配器，如栈（stack）、队列（queue）、优先队列（priority queue），以及迭代器适配器和泛函适配器等。

• 所谓容器，是指可以包含若干对象的数据结构，并提供少量操作接口。STL 提供3 类标准容器，即顺序容器、排序容器和哈希容器，后两类容器有时也统称为关联容器。

  • 顺序容器，包括向量（vector）、列表（list）、双端队列（deque）。顺序容器将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。
  • 排序容器，包括集合（set）、多重集合（multiset）、映射（map）以及多重映射（multimap）。排序容器中的元素位置一般通过元素键值的大小关系来确定，可以通过键值高效地查找和读取元素。
  • 哈希容器，包括哈希集合（hash_set）、哈希多重集合（hash_multiset）、哈希映射（hash map）和哈希多重映射（hash_multimap）。哈希容器中的元素位置直接通过元素的键值确定，通过键值将会更加高效地查找和读取元素。

• 算法可以认为是STL的精髓，所有算法都是采用函数模板的形式提供的。STL 提供的算法大致分为 4 类：日常事务类算法、查找类算法、排序类算法、工作类算法。

4.C/C++基础

4.1 ‘.’&’->’概念辨析

C语言中的.和->是用于访问结构体和联合体成员的操作符，它们之间有明显的区别：

1. . 操作符：

   • . 操作符用于访问结构体和联合体的成员。
   • 使用 . 操作符时，左边的操作数必须是一个结构体或结构体指针的实例。
   • . 操作符后面跟着成员的名称，用于指定要访问的成员。
   • 示例：

     struct Point {
         int x;
         int y;
     };
     
     struct Point p1;
     p1.x = 10;
     p1.y = 20;

2. -> 操作符：

   • -> 操作符用于访问结构体和联合体的成员，但左边的操作数必须是一个指向结构体或联合体的指针。
   • -> 操作符后面跟着成员的名称，用于指定要访问的成员。
   • 示例：

     struct Point {
         int x;
         int y;
     };
     
     struct Point p2;
     struct Point *ptr = &p2;
     ptr->x = 30;
     ptr->y = 40;

总之，.和->操作符都用于访问结构体和联合体成员，但它们的主要区别在于左边的操作数类型。.用于直接访问结构体或联合体的成员，而->用于通过指向结构体或联合体的指针来访问成员。

第二章 线性表

1.线性表概述

线性表是一种最简单、最常用的数据结构，也是最典型的线性结构。

1.1 线性表定义

线性表是具有相同特性/相同数据类型的数据元素的一个有限序列：

• 线性表可以是有序也可以是无序的；
• 线性表强调有限，即元素的个数有限；

线性表的逻辑结构如下

ADT 线性表/List
Data
    线性表的数据对象集合为{a1,a2,a3...}，每个元素类型均为DataType。数据元素之间的关系是一对一的关系
Operation
    InitList(*L):初始化线性表，建立一个空的线性表L（即线性表元素个数为0，空表）
    ListEmpty(L):若线性表为空返回1，否则返回0
    ClearList(*L):将线性表清空
    GetElem(L,i,*e):将线性表中的第i个位置元素值返回给e
    LocateElem(L,e):在线性表L中查找值为e的元素，查找成功则返回给元素在表中的序号，否则返回0
    ListInsert(*L,i,e):在线性表L中的第i个位置插入新元素e
    ListDelete(*L,I,*e):删除线性表L中第i个位置的元素并用e返回该值
    ListLength(L):返回线性表L的元素个数
endADT

关于线性表更复杂的操作，可以由上述基本操作的组合来实现

1.2 线性表的存储结构

常用的线性表的存储结构包括顺序存储结构（顺序表）和链式存储结构如单链表、循环链表、双向链表、静态链表等。

不同于顺序表，链表用一组任意的存储单元存放线性表中的各个元素。这组存储单元可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置。因此，链表中数据元素的逻辑次序和物理次序不一定相同，为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针（pointer）或链（link），这两部分信息构成了实际的存储结构，称为结点（node），然后各个结点通过指针链接起来形成一个完整的链式结构，称为链表。

为了方便的表示链表的存储结构，这里以单链表为例，通常采用如下形式

用箭头来表示存储后继结点地址的指针域。其中指向第一个结点的指针，我们称为头指针；最后一个结点，由于其没有后继结点，设置为空指针，即NULL（一般在图中用lambda示意）。

根据链表结构或者结点结构的不同，可以把链表分为单链表、循环链表和双链表三种。

1.2.1 顺序表

顺序表是最简单的线性表存储方式，即把线性表中的数据元素按逻辑次序依次存放在一组地址连续的存储空间中。通常认为线性表中的所有数据元素具有相同的数据类型，占用相同的存储空间。

在C++中可以使用数组来顺序存储顺序表中的所有元素。需要注意的是，C++中数组的下标是从0开始的，因此通常将顺序表中第i个元素存储在数组中下标为i-1的位置。

1.2.2 单链表

单链表是指链表中的每个结点只包含一个指向直接后继的指针的链表。

若链表为空，则头指针值为NULL；如果链表不空，头指针存储第一个结点的地址。

有时，单链表第一个结点不存放数据，仅作为表头使用，则称其为带头结点的单链表；否则称其为不带头结点的单链表。下图所示为两种单链表，front为指向头结点的指针。

单链表的长度不包括头结点

1.2.3 单循环链表

如果将单链表最后一个结点的指针域指向头结点，则整个链表构成一个环，这种首尾相接的单链表被称为单循环链表

上述形式的单循环链表查找最后一个元素很慢（时间复杂度为O(1)），因此增加一个指向链表最后结点的尾指针rear（此时可以只保留尾指针不保留头指针），可以很方便的访问链表首尾两端的元素

1.2.4 双循环链表

对于单链表，由于前一个结点已经存储了直接后继结点的地址，因此可以直接得到直接后继结点。而如果查找当前结点的直接前驱结点，则需要从第一个元素开始遍历，操作比较烦琐。为此，可在每个结点中再加入一个指针域，用于存储前一个元素的地址，这样便可以方便地得到直接前驱元素。这种链表中有两条方向相反的链，因此称为双向链表（doublelinked list），简称双链表（下图展示的是双向循环链表，因为实际应用中使用循环链表便于直接访问尾结点）

无论是循环单链表还是循环双链表都没有空指针域（带头结点的情况下），因此单循环链表判空的条件是头结点的next指针是否等于头指针，双循环链表的判空条件是头结点的prior和next都等于头指针；

1.3 顺序表VS.链表

顺序表	链表
既随机存取也可以顺序存取	只能顺序存取
插入操作需要移动多个元素（接近一半）	插入操作无需移动元素
静态分配（一次性分配，占用连续的存储空间）	动态分配（多次分配）
结点空间利用率较高（存储密度=1）	结点空间利用率较低（存储密度<1）

$$
存储密度=（结点数据域所占空间）/结点结构所占空间
$$

线性表的两种常用存储结构：顺序表和链表（单链表、单循环链表、双链表、双向循环链表），下面主要关注其时间性能和空间性能

1.3.1 时间性能

顺序表是由C++实现的，因此是一种随机存取结构，对表中任意结点进行存取操作的时间复杂度为O（1）。而查找链表中的结点，需要从头指针起顺着链扫描，平均时间复杂度为O（n）。因此，若线性表的主要操作是进行查找，而很少进行插入或删除操作，则采用顺序表比较合适。

对于链表，在某个位置上进行插入和删除操作，只需要修改指针即可，无须移动大量元素，操作的时间复杂度为0（1）。而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为表长的一半，平均时间复杂度为0（n）。因此，若对线性表进行频繁的插入和删除操作时，采用链表相对合适。若插入和删除主要发生在表头和表尾，则采用循环链表更为方便。

1.3.2 空间性能

顺序表的存储空间是静态分配的，因此必须提前确定其存储大小。若线性表的长度变化较大，则存储规模应按最大长度来确定，否则会出现溢出的情况。但如果大量空间只是偶尔才会使用到，则势必会造成空间的浪费。因此顺序表常常用于存储规模比较容易确定的线性表。

动态链表的存储空间是动态分配的，因此只要内存空间还有空闲就不会出现溢出的情况。因此，对于长度变化较大或长度难以估计的线性表，应采用动态链表作为存储结构。

另外，顺序表在存储时，利用了数组元素之间的相对位置来表示结点间的逻辑次序，因此没有使用额外的存储空间。而对于链表，除了存储当前结点的数据外，还需要额外的存储空间保存下一个结点的位置，以维护结点间的逻辑关系。换句话说，顺序表的存储密度(为1)大于链表的存储密度(小于1)

2.顺序表详解

2.1 顺序表结构体定义

因为一维数组可以是静态分配也可以是动态分配，所以顺序表结构体定义也有两种（ElemType表示任意元素类型，天勤习惯使用int，王道习惯使用ElemType）

#define maxSize 100
typedef struct Sqlist{
    int data[maxSize];
    int length;
}Sqlist; // 静态数组

typedef struct Sqlist{
    int *data; // ElemType *data;
    int maxSize,length;
}Sqlist； // 动态数组

2.2 成员函数实现

定义了顺序表的存储结构之后，就可以实现相应的各种基本运算

2.2.1 初始化

void initList(Sqlist &L){
    L.length = 0;
}

2.2.2 插入操作

插入操作是指在顺序表的第i（1≤i≤n+1）个位置上插入值为 x 的新元素。若在表尾追加，则不涉及表中已有元素的移动；如果在表头或中间某个位置i插入，则顺序表中原来序号从i到n的元素都要后移一个位置。最终顺序表的长度由n变为n+1

需要注意的是，数据元素在后移时，必须从最后一个元素开始移动，即先移动an，到n+1位置，再移动an-1到n位置，依次类推，直到将ai移动到i+1位置。

另外，对于一些操作不成功的特殊情况，需要抛出异常或返回错误号。例如，如果在插入之前顺序表已满，则抛出上溢异常；如果插入的位置不合理，则抛出位置异常。

(1)算法伪代码

插入操作的算法伪代码描述如下

(2)代码实现

插入操作的C++实现如下

int insertElem(Sqlist &L;int p;int e){
    if(p<0 || p>L.length || L.length == maxSize)
        return 0; //插入失败
    for(int i=L.length-1;i>=p;i--)
        L.data[i+1]=L.data[i];
    L.data[p]=e;
    ++(L.length);
    return 1;
}
/*
最好情况：表尾插入，元素不用后移，时间复杂度为O(1)

最坏情况：表头插入，元素后移语句执行n次，时间复杂度为O(n)

平均情况：平均移动次数为n/2，时间复杂度为O(n)
*/

(3)复杂度分析

插入算法的问题规模是顺序表的长度 n，基本语句是for循环中元素后移的语句。

当插入的位置在表尾，即i=n+1时，不执行元素后移操作，这是最好的情况，时间复杂度为0（1）；当插入的位置在表头，即i=1时，所有元素都要进行后移操作，这是最坏的情况，时间复杂度为O（n）；当插入的位置在表的中间某一位置时，则要分析算法的平均时间复杂度。

设T(n)表示元素移动的平均次数，插入位置为i（1≤i≤n+1），元素的移动次数为n-i+1。因此有

其中pi表示在顺序表第i个位置插入新元素的概率。假如在任意位置进行插入操作的概率相同都是1/(n+1)，因此有

上述式子的意义为，对顺序表进行插入操作，在等概率的情况下平均要移动表中一半的元素，算法的平均复杂度为O(n)

2.2.3 删除操作

删除操作是指把顺序表的第i（1≤i≤n）个位置上的元素删除，并把删除的元素返回。若删除表尾元素，则不涉及原来元素的移动；如果要删除表头或中间某个位置i上的元素，则顺序表中原来序号从 i+1 到 n 的元素都要向前移动一个位置。最终顺序表的长度由 n 变为 n-1

与插入操作相反，数据元素在前移时，必须从第i+1 个位置开始移动，即先移动ai+1到i位置，再移动ai+2到i+1位置，依次类推，直到将最后一个元素an，移动到n-1位置。类似于插入运算，对于操作不成功的特殊情况需要抛出异常或返回错误号。例如，如果在删除操作之前顺序表已经为空表，则抛出下溢异常；如果删除的位置不合理，则抛出位置异常。

(1)算法伪代码

(2)代码实现

删除操作的C++实现代码如下

int deleteElem(Sqlist &L,int p,int &e){
    if(p<0 || p>L.length-1)
        return 0;
    e = L.data[p]; // 保存删除元素
    for(int i=p;i<=L.length-2;i++)
        L.data[i]=L.data[i+1]; // 覆盖以达到删除的目的
    --(L.length);
    return 1;
}
/*
最好情况：删除表尾元素，时间复杂度为O(1)

最坏情况：删除表头元素，移动除表头元素外的所有元素，时间复杂度为O(n)

平均情况：平均移动次数为(n-1)/2，时间复杂度为O(n)
*/

(3)复杂度分析

算法的问题规模是顺序表的长度n，基本语句是for循环中元素前移的语句。

当删除的位置在表尾，即i=n时，不执行元素前移操作，这是最好的情况，时间复杂度为O（1）；当删除的位置在表头，即 i=1时，其余所有 n-1 个元素都要进行前移操作，这是最坏的情况，时间复杂度为O（n）；当删除的位置在表的中间某一位置时，则要分析算法的平均时间复杂度。设T（n）表示元素移动的平均次数，删除位置为i（l≤i≤n），元素的移动次数为 n-i，因此有

其中pi表示删除表中第i个位置上的元素的概率，假定各位置被删除的概率相同则对于任意的i有pi=1/n，因此有

在顺序表上进行删除操作的等概率情况下，平均要移动表中一半的元素，算法的平均复杂度为O（n）。

2.2.4 查找操作

(1)按位查找

按位查找是指查找顺序表中指定位置的数据元素。由于顺序表中采用数组存储数据元素，第i个数据元素对应的数组下标为i-1，所以其算法实现比较简单。

int getElem(Sqlist L,int p,int &e){
    if(p<0 || p>L.length-1)
        return 0; // 查找失败
    e = L.data[p];
    return 1; //查找成功
}

顺序表具有随机存储特性，因此按位查找的时间复杂度为O(1)

(2)按值查找

按值查找是指查找顺序表中指定数值的数据元素。在实现时需要依次比较顺序表中的每个数据元素，直到找到指定数值的数据元素或遍历完整顺序表都没有找到。如果没有找到，称为查找不成功，返回查找失败错误号，如“0”。算法实现如下。

int findElem(Sqlist L, int e){
    for(int i=0;i<L.length;i++){
        if(e==L.data[i])
            return i; // 查找成功返回下标
    }
    return 0； // 查找失败
}
/*
最好情况：查找元素就在表头，只需要比较一次，时间复杂度为O(1)

最坏情况：查找元素在表尾或不存在，比较n次，时间复杂度为O(n)

平均情况：平均比较次数为(n+1)/2，时间复杂度为O(n)
*/

该算法的时间复杂度分析方法同前面的插入操作或删除操作

• 对于查找成功的情况，最好的情况是比较第一个数据元素时就找到，时间复杂度为O（1）。最坏的情况是遍历到最后一个数据元素时才找到，此时的时间复杂度为O（n）。而平均情况下，假定要查找的元素存在，且其位置是等概率分布的，则平均要比较（n+1）/2个元素。因此，按值查找算法查找成功的平均时间复杂度为O（n）。

• 对于查找不成功的情况，需要循环n次，因此按值查找算法查找不成功的最好、最坏和平均时间复杂度均为O（n）。

2.3 顺序表的优缺点

顺序表利用物理位置上的相邻关系来表示数据元素之间的逻辑关系，这一特点导致顺序表这种存储结构具有如下优缺点，顺序表的优点是：

• 不需要为表示元素之间的逻辑关系而增加额外的存储空间。
• 可以方便地随机访问顺序表中任一位置的元素。

顺序表的缺点如下：

• 插入和删除操作需移动大量的数据元素，效率较低。在等概率条件下，两种操作平均需要移动顺序表中约一半的元素。
• 顺序表难以选择合适的存储容量。顺序表要求占用连续的存储空间，存储分配只能预先进行，因此属于静态存储分配方式。若开始时分配的空间过小，则插入操作很容易引起顺序表的溢出；若分配的空间过大，则可能造成一部分空间长期闲置，不能被充分利用。

3.单链表详解

为了克服顺序表的缺点，可以采用链式（或称为链接）存储方式存储线性表。最简单的链式存储方式就是单链表（single linked list），这种方法采用动态存储分配方式，即程序在运行时根据实际需要随时申请内存，在不需要时将申请的内存释放。

3.1 单链表结点定义

单链表由一个一个结点通过结点的指针（pointer）或链（link）按照元素逻辑顺序链接而成，因此，单链表的每一个结点（node）都由数据域（data）和指针域（next）两部分构成。data域用于存储元素的值；next域用来存储直接后继的地址或位置。

typedef struct LNode{ //单链表结点定义
    int data;
    struct LNode *next;
}LNode;

单链表除第一个结点外，其他每个结点的地址都存储在前一个结点的next域中，因此，只要取得第一个结点的地址，就可以顺序遍历单链表的所有结点，因此头指针具有标识一个单链表的作用。

带头结点的链表可以统一处理对非空单链表中的任意结点的操作（尤其是开始结点结点，注意开始结点和头结点是不同的），使得单链表的很多操作实现起来更加方便。因此之后再不特殊说明的情况下都默认链表带头结点，头结点的地址保存在头指针中

---

Q：关于头指针，头结点和开始结点概念辨析

A：

• 带头结点的单链表中有一个结点不存储信息(或只存储一些描述链表属性的信息如表长)，不带头结点的单链表中的所有结点都存储信息；
• 头指针是标识一个链表是否存在的标志，这意味着无论链表是否为空只要存在头指针就一定存在；
• 无论链表是否带头结点，头指针指向的都是链表中的第一个结点（要么是头结点(带头结点的链表)要么是开始节点(不带头结点的链表)）

---

3.2 成员函数实现

3.2.1 建表

一般来说建立单链表的方法有两种，分别为头插法和尾插法。

(1)头插法

采用头插法建立单链表是指每次插入元素都从单链表的开始结点位置(如果从头结点开始插的话会导致头结点移动而不再是头结点)插入，先前插入的结点随着新结点的插入而不断后移。因此，若希望数组a中的各个元素插入后在单链表后的次序依然为a[0]，a[1]，…，a[n-1]，则插入时应先插入a[n-1]，再插入a[n-2]，依次类推最后插入a[0]。

头插法的执行过程如下所示（a是插入第一个结点，b表示插入其他结点，而无论是哪种情况操作的步骤都是一样的，体现了带头结点的单链表的简便性）

对应上述图像有如下执行流程，需要注意的是步骤3必须在步骤4之前执行

下面给出利用头插法建立单链表的算法

void createlistF(L Node *&C,int a[],int n){
    LNode *s;
    C=(LNode *)malloc(sizeof(LNode)); // 申请头指针C指向的头结点空间
    C->next=NULL;
    // 初始化完成开始头插法
    for(int i=0;i<n;i++){
        s=(LNode *)malloc(sizeof(LNode)); // S指向新申请的结点
        s->data=a[i];
        // 头插法（先接屁股再接头）
        s->next = C->next;
        C->next = s;
    }
}

头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点的插入时间为O(1)，因此长度为n的单链表的建表时间复杂度为O(n)

(2)尾插法

尾插法是指每次新插入的元素都在单链表的表尾。通常尾插法需要一个指针变量保存终端结点的地址，称为尾指针，设为r。每插入一个结点后，r指向新插入的终端结点。

尾插法的执行流程如下所示

对应上述图像有如下执行流程，每个新结点的插入都可以分为四个步骤

利用尾插法建立单链表的算法如下所示，算法的时间复杂度为O(n)

void creatlistR(LNode *&C,int a[],int n){ // 利用数组a中的n个元素建立不含头结点的单链表C
    LNode *s,*r;
	C=(LNode *)malloc(sizeof(LNode)); // 申请头指针C指向的头结点空间
    C->next=NULL;
    r=C; 
    // 链表初始化完成，开始尾插法
    for(int i=0;i<n;i++){
        s=(LNode *)malloc(sizeof(LNode)); // S指向新申请的结点
        s->data=a[i];
        // 尾插法（只需要接头）
        r->next=s; // 将新结点接入链表尾部
        r=r->next; // r始终指向终端结点，这句写为 r=s; 等价
    }
    r->next = NULL;
}

尾插法生成的链表中结点的次序和输入数据的顺序一致，因为有尾指针r的存在因此时间复杂度为n*O(1)=O(n)

3.2.2 查找算法

(1)按位查找

也称为按序查找。顺序表采用数组存储，是一种随机存取的存储方式，即通过索引可以快速访问表中的任意元素。而链表是一种顺序存储方式，只能从链表的表头出发，顺着每个结点的指针域往后依次搜索访问每个结点。

设单链表的长度为 n，要查找表中的第i个元素，则i应满足1≤<n。设工作指针为p，当开始查找时 p 指向第一个结点，用整型变量j作计数器，初始时 j=1。p 每指向下一个结点，j进行加1操作，直到j等于i，此时p指向的结点（有时简称p结点）就是所要找的结点；或者j不等于i但p已经为空，此时说明i是不合法的，算法可抛出异常或返回错误标识。

在实现时，可直接返回p，因为若p 为空，说明第i个元素不存在，返回空地址；否则，p 指向的元素就是所查找的元素，即返回元素地址。

(1)算法伪代码

按位查找的算法伪代码如下

(2)代码实现

根据上述伪代码，可以给出C++描述的具体算法如下

int GetElem(LNode *C,int i){
    if(i<1)
        return NULL;
    LNode *p = C->next; // 头结点指向的下一个结点（第一个结点）
    int j = 1;
    while(p!=NULL && j<i){
        p=p->next;
        j++; // 计数器
    }
    return p;
}
//按序查找的时间复杂度显然为O(n)（没有说明具体什么复杂度的时候统一认为是最坏时间复杂度）

(3)复杂度分析

算法中 p=p->next是其中一条基本语句，该语句执行次数与被查找结点在单链表中的位置有关。在查找成功的情况下，查找位置i满足1≤i≤n，则基本语句执行次数为i-1，假定查找每个结点的概率相等（pi=1/n），则查找成功的平均时间复杂度为

若查找不成功则需要执行基本语句n次，因此查找不成功的时间复杂度为

(2)按值查找

按值查找是指在单链表中查找给定值的结点，找到后返回元素地址或序号。相对于按位查找，按值查找算法比较简单，下面直接给出按值查找算法的C++描述，在这里算法返回的是元素的序号。

int findElem(LNode *C,int x){
	LNode *p = C->next; // 从开始结点开始比较
    while(p!=NULL && p->data!=e){
        p=p->next;
    }
    return p;
}
//很明显按值查找的时间复杂度为O(n)

3.2.3 插入操作

单链表的插入操作必须先找到其前驱结点的位置

单链表的插入操作在这里定义为在单链表的第i个位置上插入值为 x 的元素。该操作可分为两个阶段，首先进行按位查找操作，即找到第i-1个位置的元素，然后在该元素后插入新元素。

//后插操作
s->next = p->next;
p->next = s;

算法的主要时间开销在查找元素，时间复杂度为O(n)，若直接给定结点在后面插入新结点则时间复杂度为O(1)

另一种插入方式是前插，其时间复杂度为O(1)，任何前插操作都可以转换为后插操作

3.2.5 删除操作

与插入操作相同，单链表的删除操作必须知道其前驱结点的位置，对应的，要在某一结点后插入一个结点则必须知道这个结点的地址；

删除操作是指删除线性表中的第i个元素，并将该元素的值返回。与插入操作类似，删除操作首先进行查找操作，找到第 i-1个元素，然后再将第i个元素删除。

对应的删除操作过程可以分为如下五个步骤

对应的C++算法描述如下

q=p->next;
p->next = p->next->next;
free(q);

核心是找到被删除结点的前一个结点，与插入操作相同需要先使用按序查找，因此其时间复杂度同样为O(n)。删除结点还有一种时间复杂度为O(1)的算法，本质上就是将其后继节点的值赋予本身然后删除后继节点

4.单循环链表详解

循环链表就是将链表首尾相连的链表，下面是两种不同的单循环链表

用头指针 front 表示的单循环链表中，如果查找第一个元素，其地址为 front-> next，时间复杂度显然为O（1），但如果查找最后一个元素，则时间复杂度为O（n）。但若是使用尾指针rear指向单循环链表的最后一个结点，如图（b）所示，这样，无论查找第一个元素（地址为 rear->next-> next）还是最后一个元素（地址为 rear），时间复杂度都为O（1），从而简化操作。

带尾指针的单循环链表相对于单链表，存储结构并没有太多变化，只是改用指向终端结点的尾指针，并且尾结点/最后一个结点的指针域指向头结点。其基本操作的实现与单链表类似，不同之处主要在于以下两点。

• 头指针的表示：单链表使用 front 标识头指针，单循环链表使用 rear->next 标识头指针；
• 判断 p 指向的某结点是否为尾结点的方法：单链表中若 p->next==NULL，则 p 指向尾结点，而单循环链表中的判别条件应为p==rear；

4.1 类声明

下面仅给出单循环链表的类声明，具体各个成员函数的实现与单链表类似这里不再赘述

5.双循环链表详解

在[线性表的存储结构–双循环链表](# 1.2.4 双循环链表)中已经说明一般所使用的不是双向链表而是双循环链表，无论是双向链表还是双循环链表使用的结点结构如下

有时候其结点结构中的两个指针域分别定义为left和right（一般地定义为prior和next）

typedef struct DLNode{ //双链表结点定义
    int data;
    struct DLNode *prior;
    struct DLnode *next;
}DLNode;

5.1 基本操作

关于双循环链表的类声明以及具体的成员函数实现这里不赘述。

对于双链表结构，通过当前结点可以方便地查找直接前驱和直接后继。设p指向当前结点，则 p->prior指向直接前驱，p->next指向直接后继，而p->prior->next=p->next->prior=p。下面仅讨论双向链表的插入和删除操作。

5.1.1 尾插法建表

void createDlistR(DLNode *&L,int a[],int n){
    DLNode *s,*r; // s指向新申请的结点，r始终指向终端结点
    L=(DLNode *)malloc(sizeof(DLNode));
    L->prior = NULL;
    L->next = NULL;
    r=L;
    // 初始化完成，开始尾插法
    for(int i=0;i<n;i++){
        s = (DLNode *)malloc(sizeof(DLNode));
        s->data = a[i];
        // 尾插法
        r->next = s; //两条链互相链接才算作接入双链表
        s->prior = r;
        r=s;
    }
    r->next = NULL;
}

5.1.1 插入操作

在p结点后面插入一个新结点s示意图如下

主要分为如下四个步骤，注意步骤2和3必须在步骤4前面

其代码描述如下（在p结点后插入s结点）

s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior =s;

5.1.2 删除操作

将p结点的直接后继删除，操作过程如下

需要注意的是，被删除结点必须在摘链前保存地址（即步骤1必须在步骤3之前），以备释放结点时使用。具体操作步骤如下

其代码描述如下（删除p结点后的q结点）

q = p->next; // q指向被删除结点
//先将要被删除的结点的两端链子处理
p->next = q->next;
q->next->prior = p;
free(q); // 删除结点

6.静态链表

前面介绍的链表都是利用C++指针来存储结点的地址，结点空间的分配和收回都是由操作符new和delete动态执行的，因此称之为动态链表（dynamic linked list）。对于某些高级语言，如BASIC、Java等，没有提供“指针”数据类型，因此多采用数组来描述单链表，用数组元素的下标来模拟链表的指针，一般称之为“游标”。这种用数组存储的链表结构，称为静态链表（static linked list）。

静态链表的每个数组元素同样由两个域构成：data 域存储数据元素，next 域存储直接后继元素的下标。整个链表元素通过 next 域链接起来，定义起始下标为 front，指向起始结点。对于数组中未使用的元素，为了便于将来分配给链表使用，也使用next域链接起来，定义起始下标为 tail。因此，静态链表实际上有两个链表，一个用于存储链表的各个元素，另一个存储所有未分配的数组元素，在这里称之为空闲链表。两个链表的终点结点的 next域都设为-1，表示链表结束。

考点：

• 一般链表结点的空间来自内存，而静态链表的结点空间来自一个结构体数组；
• 静态链表中的指针并不是C语言中的用来存储内存地址的指针型变量，而是一个存储数组下标的整型变量。因为通过它可以找到后继节点在数组中的位置，其功能类似真实的指针因此将其也称为指针；
• 静态链表中指针指示的是链表中下一元素在数组中的地址
  • 静态链表结点的指针域存储的是数组下标，指示的是下一个结点的位置，而非指示的数组下标；
  • 静态链表中的指针表示的是下一个元素在数组中的位置，而不是下一个元素的地址；
• 静态链表用数组表示因此需要分配较大的连续空间，而静态链表具有一般链表的优点即插入删除操作不需要移动元素

6.1 静态链表定义

与顺序表相同，静态链表也需要预先分配一块连续的内存空间，静态链表以next==-1作为结束标志

#define maxSize 50
typedef struct Slinklist{
    Elemtype data; // 数据域
    int next; // 指针域
}Slinklist;
Slinklist[maxSize]; // 结构体数组，数组中的每个元素都是上述定义的Slinklist结构体

静态链表的插入、删除操作与单链表相同，只需要修改指针不需要移动元素

6.2 成员函数实现

下图是一个完整的静态链表操作示意图

初始化时链表为空，front=-1，tail指向空闲链的第一个元素，如图 2-26（a）所示。插入5 个元素后，front指向链表表头，链表最后一个元素的指针域设置为-1，tail指向空闲链新的起始元素，如图2-26（b）所示。图2-26（c）为删除元素as的示意图，下标为2的数组元素被回收到空闲链中，成为空闲链表的第一个空闲元素，其指针域指向原来的空闲链表头，tail指向新的空闲链表头。图2-26（d）为删除静态链表表头元素a的示意图，被删元素被回收为空闲链的第一个元素，同时 front 需要修改为指向静态链表新的表头元素。

下面仅介绍部分静态链表的算法。

6.2.1 无参构造函数

无参构造函数用于建立空静态链表。空静态链表的所有数组元素都没有分配，令tail为0，即存储第一个元素的下标，除最后一个数组元素外，空闲链中每个元素的next域存储下一个数值元素的下标，这样所有未分配空间就链接起来。同时令front 等于-1，表示为空静态链表。下图是建立空静态链表的示意图

对应的C++算法描述如下

6.2.2 有参构造函数

有参构造函数使用数组初始化静态链表。待所有数组元素添加到静态链表后，链表的最后一个元素的 next 域应设置为-1，同时 front 指向第一个数组元素，tail 指向第一个未分配的数组元素。

对应的C++算法描述如下

6.2.3 申请结点

由于静态链表采用下标来模拟指针，因此空间的申请和释放不能再使用new或delete这样的操作符来实现，而是要由程序员自己编写函数实现。

申请结点空间时，若还有未分配的数组元素，则将未分配数组元素链表中的第一个结点分配，同时 tail指向数组的下一个未分配元素。操作过程如下

6.2.4 释放结点

静态链表的结点若不再使用，则需要回收到未分配元素构成的空闲链表中。在具体实现时可直接将其作为表头插入空闲链表的起始位置。需要注意的是，如果要释放静态链表的第一个结点，则 front 需要重新指向下一个元素。算法描述如下

第三章 线性表拓展

第二章介绍了基本的线性表结构(逻辑结构)，本章将学习几种特殊类型的线性表 – 栈、队列、串以及多维数组（注意这几个概念同样也是逻辑结构）

• 栈的插入和删除操作只能在表尾进行；队列的插入操作只能在表尾进行，删除操作只能在表头进行。因此，栈和队列被认为是操作受限的线性表。因而不是任何对线性表的操作都可以作为栈和队列的操作，比如不可以随便读取栈或队列中间的某个数据。
• 串是一种以字符作为数据元素的线性表，也称为字符串，是重要的非数值处理对象，在各种程序设计语言中，一般都有“串”的概念。
• 数组是有限个类型相同的变量的集合，而多维数组则是数组的扩展，多维数组在不同的程序设计语言中的实现方式各有不同。

考点：任何数据结构都具备插入、删除和查找3个基本运算 – 错误，栈和队列不具备查找

1.拓展线性表概述

1.1 栈

栈是限定仅在表尾进行插入和删除操作的线性表，主要有以下性质：

• 把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈
• 栈对线性表的插入和删除的位置进行了限制，但是没有对元素进出的时间进行限制，即出栈可以随时进行，只要保证式栈顶元素出栈

将元素插入栈中的操作称为入栈（或进栈）操作，元素入栈后就变成新的栈顶。将元素从栈中删除的操作称为出栈（或退栈）操作，出栈时被删除的总是原来的栈顶元素。因此，每次出栈的元素总是当前栈中“最新”的元素，即最后入栈的元素，而最先插入的元素被放到了栈底，待其他元素都已出栈，栈底元素才能被删除。栈的操作是按后进先出（LIFO，Last In First Out）原则进行的。

栈的逻辑结构如下

ADT 栈（stack）
Data 
    元素具有相同类型，相邻元素具有前驱和后继的关系
Operation
    InitStack(*S):初始化栈，即建立一个空栈S
    DestroyStack(*S):若栈存在则销毁它
    ClearStack(*S):将栈清空
    StackEmpty(*S):若栈为空则返回1，否则返回0
    GetTop(S,*e):若栈存在且非空则用e返回S的栈顶元素
    Push(*S,e):若S存在，插入新元素e到S中使其成为栈顶元素
    Pop(*S,*e):删除S中的栈顶元素并用e返回它的值
    StackLength(S):返回栈S的元素个数
endADT

1.2 队列

队列是指只允许在一端进行插入操作，而在另一端进行删除的线性表，主要有以下性质：

• 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头

队列是先进先出（FIFO，First In First Out）的线性表。无论入队操作或出队操作的先后时间如何，元素的入队序列和出队序列必然相同。

队列的逻辑结构如下

ADT 队列（Queue）
Data 
    元素具有相同类型，相邻元素具有前驱和后继关系
Operation
    InitQueue(*Q):初始化操作，建立一个空队列
    DestroyQueue(*Q):若队列Q存在则销毁它
    ClearQueue(*Q):将队列Q清空
    QueueEmpty(*Q):若队列为空则返回1否则返回0
    GetHead(Q,*e):若队列存在且非空，用e返回队列Q的队头元素
    EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并使其成为队尾元素
    DeQueue(*Q,*e):删除队列Q中的队头元素，并用e返回其值
    QueueLength(Q):返回队列Q的元素个数
endADT

栈和队列的共同点是都只允许在端点处插入和删除元素，即都是限制存取点的线性结构

1.3 串

串是由零个和多个字符组成的有限序列，又称为字符串：

• 一般将串记为s=”a1a2a3…an”(n>=0)，其中s是串的名称，双引号括起来的字符序列是串的值，值可以是字母、数字或其他字符，i就是该字符在串中的位置，n称为串的长度
• 串的逻辑结构和线性表很相似，但是串中的元素都是字符（结点元素仅由一个字符构成的特殊线性表）。线性表更关注的是单个元素的操作，而串中更多的是针对子串（而不是单个字符）的操作
• 空格串（只包含空格的串）和空串（长度为0的串，不包含任何字符）不同

串的逻辑结构如下

ADT 串（string）
Data 
    串中的元素仅由一个字符组成，相邻元素之间具有前驱和后继的关系
Operation
    StrAssign(T,*chars):生成一个值等于字符串常量chars的串T——这个地方指针的使用我不是很理解
    StrCopy(T,S):若串S存在，则将串S复制得到串T
    ClearString(S)：若串S存在，则将S清空
    StringEmpty(S):若串S为空则返回1，否则返回0
    StrLength(S):返回串S的元素个数，即串的长度
    StrCompare(S,T):比较两个串的大小
    Concat(T,S1,S2)：用T返回由S1和S2联接得到的新串
    SubString(Sub,S,pos,len):Sub返回串S的第pos个字符起长度为len的子串
    Index(S,T,pos):若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符后第一次出现的位置
    Replace(S,T,V):用V替换主串S中出现的所有与T相等的不重叠的子串
    StrInsert(S,pos,T):在串S的第pos个字符之前插入串T
    StrDelete(S,pos,len):从串S中删除第pos个字符起长度为len的子串
endADT

1.4 多维数组

数组array是由n(n>=1)个类型相同的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。（注意这里的数组是一个逻辑结构，并不是前面C++程序设计语言中的数组基本数据类型）：

• 一维数组是有序的元素序列，二维数组可以理解为数组元素是一维数组的数组，类推可以得到n维数组是每个元素均为n-1维数组的一维数组
• 多维数组通常用来存储结构比较复杂的相关联数据

数组一旦被定义，其维数和维界就不再改变，因此除了结构体的初始化和销毁外，数组只会进行存取元素和修改元素的操作（最常见的两种操作是查找和修改）。

一个基本的数组的逻辑结构如下

ADT 数组（Array）
Data
    数组的元素类型定义为ElementType，假设数组元素的下标范围为[0, MaxSize-1]
    数组的实际长度定义为Length（表示数组中已存储的元素个数）
Operation
    InitArray(&arr): 初始化一个空数组
    DestroyArray(&arr): 销毁数组，释放相关内存空间
    GetLength(arr): 返回数组的实际长度
    IsEmpty(arr): 判断数组是否为空，若为空则返回1，否则返回0
    ClearArray(&arr): 将数组清空，将长度设置为0
    GetElement(arr, i): 返回数组中第i个元素的值
    SetElement(&arr, i, e): 设置数组中第i个元素的值为e
    InsertElement(&arr, i, e): 在数组的第i个位置插入元素e
    DeleteElement(&arr, i): 删除数组中第i个位置的元素
    Traverse(arr, visit): 遍历数组的所有元素，依次调用visit函数进行访问
endADT

---

Q：前面不是说采用数组基本数据类型作为顺序表存储结构的底层实现，怎么这里又来了一个数组数据结构？这是否是”鸡生蛋，蛋生鸡“？

A：这里的数组是一个逻辑结构，而不是数组基本数据类型，参考什么是数组（数据结构），数组及其定义详解 。之所以会产生上述混淆是因为大部分编程语言默认将数组作为基本数据类型直接实现了，所以会有人认为数组只是一个基本数据类型。换句话说，如果C++直接内置了队列、栈等基本数据类型，那么当需要使用C++实现一个队列或者栈的时候就不需要再像前面一样自定义类，而是直接使用即可。

数组和其他线性结构不同。顺序表、链表、栈和队列存储的都是不可再分的数据元素（如数字 5、字符 ‘a’ 等），而数组既可以用来存储不可再分的数据元素，也可以用来存储像顺序表、链表这样的数据结构。比如说，数组可以直接存储多个顺序表。我们知道，顺序表的底层实现还是数组，因此等价于数组中继续存储数组，这与平时使用的二维数组类似。

最重要的一点是，无论数组的维数是多少，数组中的数据类型都必须一致。

综上，可以认为一维数组是线性表(特指顺序表)的基本表现形式，n维数组是对线性表数据结构的一种拓展。

Q：数组与线性表的关系？

A：数组是线性表的推广，一维数组可以视为一个线性表，二维数组可以视为其数据元素为线性表的线性表。

---

1.5 广义表

广义表是指，表元素可以是原子或广义表的一种线性表的拓展结构。下面是一些广义表的例子

考研题型中最常考察的是广义表的长度和深度求法，总结如下：

• 广义表的长度：为表中最上层元素的个数，如广义表 C 的长度为 2，注意不是 3。

• 广义表的深度：为表中括号的最大层数。注意，求深度时需要将子表展开，如广义表D应该展开为（（d，e），（b，（c，d））），深度为 3。

表头（Head）和表尾（Tail）：当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾。

1.5.1 头尾链表存储结构

下图展示了例子中广义表的头尾链表存储结构的存储情况，其中有两种结点：原子结点和广义表结点。其中原子结点有两个域：标记域和数据域；广义表结点有三个域：标记域、头指针域和尾指针域。

标记域用于区分当前节点是原子(0标记)还是广义表(1标记)，头指针域指向原子或广义表结点，尾指针域为空或指向本层中的下一个广义表结点

1.5.2 拓展线性表存储结构

下图展示了例子中广义表的拓展线性表存储结构的存储情况，其中也有两种结点，即原子结点和广义表结点，不同的是原子结点有3个域：标记域、数据域和尾指针域；广义表结点也有3个域：标记域、头指针域与尾指针域。

其中，标记域用于区分当前结点是原子（用0来表示），还是广义表（用1来表示）。这种存储结构类似于带头结点的单链表存储结构（而上一种类似于不带头结点的单链表存储结构），每一个子表都有一个不存储信息的头结点来标记其存在。

2.栈详解

栈的数学性质：当n个不同的元素进栈，出栈元素不同的排列个数为

上述公式称为卡特兰公式，使用数学归纳法可证明，此处不再赘述

2.1 顺序栈

栈的顺序存储结构简称为顺序栈。类似于顺序表，顺序栈也可以用C++数组来实现。由于栈底位置固定不变，因此可将栈底设置在数组两端的任意一端，通常把数组下标为0的一端作为栈底。同时设置栈顶指针top表示栈顶位置，当进行入栈操作时，top加1，当进行出栈操作时，top减1，栈的高度为top+1。当栈为空时，top=-1。设数组的大小为StackSize，则当栈满时，top=StackSize-1。下图说明了在顺序栈中进行入栈和出栈时，栈中元素和栈顶指针的变化。

2.1.1 类声明

直接给出顺序栈的C++类声明

2.1.2 成员函数实现

顺序栈的基本操作相对简单，下面直接给出具体的C++实现，这些算法的时间复杂度均为O(1)

2.2 链式栈

栈的链式存储结构称为链栈，其实现原理类似于单链表，结点结构与单链表相同。由于插入和删除操作都在表头进行，因此链栈在实现时直接将栈顶指针指向栈顶元素，无须像单链表一样增加表头结点（头结点的存在本身是为了统一开始结点和其他结点上的操作的不同，但因为栈只会操作开始结点所以头结点失去存在的意义）。

因为链栈在链表的头部进行操作，而链表插入和删除都需要找到开始结点的前驱节点，因此在没有头结点的情况下，只有表头指针没有表尾指针的循环单链表是不能快速找到开始结点的前驱结点的（时间复杂度为O(n)），因此不适合做链栈

2.2.1 类声明

下面给出链栈的C++模板类声明

2.2.2 成员函数实现

(1)入栈和出栈

由于栈是操作受限的线性表，因此链栈的基本操作可以看成是单链表操作的简化。链栈的入和出操作如下所示

下面直接给出链栈的入栈和出栈成员函数的C++实现

链栈的入栈和出栈操作时间复杂度均为O（1）

(2)析构函数

链栈类的实例在生命期结束时，需要利用析构函数将所有链表中的结点释放

析构函数的时间复杂度为O（n）

2.3 共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图所示

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1 号栈进栈时 top1 先减 1 再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为 0（1），所以对存取效率没有什么影响。

2.4 栈的应用

因为栈具有记忆当前状态的功能，因此栈常用于递归调用（调用自己）、子程序调用（调用其他函数）、表达式求值以及括号匹配等

2.4.1 表达式转换&求值

参考链接：《数据结构》：中缀表达式转后缀表达式 + 后缀表达式的计算_Amentos的博客-CSDN博客；

• 中缀表达式：操作符以中缀形式位于运算数中间（如：3+2），是我们日常通用的算术和逻辑公式表示方法。

• 后缀表达式：又称逆波兰式（Reverse Polish Notation - RPN），操作符以后缀形式位于两个运算数后（如：3+2的后缀表达形式就是3 2 +）。

• 前缀表达式：又称波兰式（Polish Notation），操作符以前缀形式位于两个运算数前（如：3+2的前缀表达形式就是+ 3 2）。

中缀表达式往往需要使用括号将操作符和对应的操作数括起来，用于指示运算的次序。中缀表达式适合于人类的思维结构和运算习惯，但并不适用于计算机。尤其是包含括号的中缀表达式，对计算机而言是非常复杂的结构。与中缀表达式不同，后缀表达式不需要使用括号来标识操作符的优先级。后缀表达式的计算按操作符从左到右出现的顺序依次执行(不考虑运算符之间的优先级)，对于计算机而言是比较简单的结构。

下面介绍借助字符栈完成中缀表达式到后缀表达式的转换：从左至右依次遍历中缀表达式各个字符

1. 若字符为运算数：直接送入后缀表达式
2. 若字符为左括号：直接入栈（左括号优先级最低）
3. 若字符为右括号：直接出栈（不送入后缀表达式），并将出栈字符依次送入后缀表达式，直到栈顶字符为左括号（左括号也要出栈，但不送入后缀表达式）
4. 若字符为操作符
   • 若栈空，直接入栈
   • 若栈非空，判断栈顶操作符，若栈顶操作符优先级低于该操作符，该操作符入栈；否则一直出栈，并将出栈字符依次送入后缀表达式，直到栈空或栈顶操作符优先级低于该操作符，该操作符再入栈
   • 总结：只要满足栈空或者优先级高于栈顶操作符即可将该操作符入栈，否则出栈直到满足条件之一
5. 重复以上步骤直至遍历完成中缀表达式，接着判断字符栈是否为空，非空则直接出栈，并将出栈字符依次送入后缀表达式

而实际上我们在解题的时候这样进行会非常缓慢，下面举一个例子快速得到后缀表达式（作图法，依次根据运算顺序进行转换，该方法同样适用于得到前缀表达式，把每个部分的符号放在最前即可）

得到后缀表达式之后，同样可以借助一个运算数栈来对其进行计算：从左至右依次遍历后缀表达式各个字符

1. 若字符为运算数：直接入栈
2. 若字符为操作符：连续出栈两次，使用出栈的两个数据进行相应计算，并将计算结果入栈
   • 第一个出栈的运算数为 a ，第二个出栈的运算数为 b ，此时的操作符为 - ，则计算 b-a （注：a和b顺序不能反），并将结果入栈
   • 运算先后顺序为：第二次出栈运算数 操作符 第一次出栈运算数
3. 重复以上步骤直至遍历完成后缀表达式，最后栈中的数据就是中缀表达式的计算结果

关于表达式转换，其实不仅与栈相关，与树也密切关联（因此既可以使用上述作图也可以使用二叉树转换）

• 中缀表达式实际是一棵以运算符为双分支结点，操作数为叶子叶子的二叉树中序遍历对应序列；
• 后缀表达式是对上述二叉树后序遍历的结果；
• 前缀表达式是对上述二叉树前序遍历的结果；

仅由中缀表达式并不能得出唯一的后缀表达式或前缀表达式！！！因为中缀表达式不能唯一确定一棵二叉树

3.队列详解

3.1 循环队列

类似于顺序表，队列也可以采用顺序存储结构进行存储，即使用数组存储队列元素。由于队列的操作是在队列两端进行的，因此一般需要设置队头和队尾两个指针。对于空队列，队头和队尾均为-1，随着元素的入队，队尾不断后移。假定队头位置固定，不难发现当队头元素出队时，队列中的其他每个元素都需要向前移动一个单元，因此出队操作的时间复杂度为O（n）

为了简化出队操作，可以允许队头指针改变，当队头元素出队时，其他元素不需要移动，而只需要将队头指针后移。但这也带来一个问题，由于元素出队时队头指针后移，出队元素所占用的空间就不能再使用了，这势必会导致存储队列的空间越来越小，直到无法使用。为了解决这个问题，通常采用循环队列实现顺序存储结构。

若将存储队列的数组看成是头尾相接的循环结构，则称之为循环队列。当队尾指针移动到数组最后时，数组前端的空间可能已经空闲。因此，如果再有元素进行入队操作，队尾指针可移动到数组最前面。

不难发现，上述循环队列中的队头指针位置的下一个元素才是真正的队头元素，队头指针指向的数组元素并非队列中的元素，因此没有意义。在此规定队头指针所指位置永不存储队列元素（通过不存储元素的位置来区分队列为空和队列为满）。当队列满时，其长度实际为数组长度减 1。下图展示了队列满时的几种情况。当队头和队尾指针指向同一位置时，队列为空队列。

3.1.1 类声明

下面给出循环队列的C++模板类声明

在循环队列的模板类中，定义 data 数组作为存储空间，定义 front 和 rear 分别代表队列的队头指针和队尾指针。队列的头元素在队头指针的“下”一个位置，即（front+1）%QueueSize。队尾指针指向的就是队列的队尾元素。队列在初始化时为空队列，只要front和rear指向数组中任意的同一位置即可，在类的构造函数中可将其设置为0。

3.1.2 成员函数实现

(1)入队操作

根据前面的分析，若队列不满，当有元素入队后，队尾指针移向“下”一个位置，即rear=（rear+1）%QueueSize

(2)出队操作

若队列为非空队列，则队头元素出队时，队头指针也要移向“下”一个位置，即front=（front+1）%Queuesize

(3)查找队头元素

查找队头元素的操作仅返回队头元素的值，不需要队头元素出队，因此队头指针保持不变，而队头元素的位置是队头指针的“下”一个位置，即（front+1）%Queuesize

(4)求队列长度

当队头指针小于等于队尾指针时，可得队列长度为队尾指针减去队头指针，即rear-front。

当队头指针大于队尾指针时，队列占据了数组的首尾两端，此时空闲区的长度为front-rear，因此队列长度为 rear-front+QueueSize，如下所示

将以上两种情况统一，则队列长度可表示为（rear-front+QueueSize）%QueueSize

3.2 链队列

队列的链式存储结构称为链队列，因此链队列可看成仅在表头删除和表尾插入的单链表。

如果仅有单链表的头指针，不便于在表尾进行插入操作，因此通常会在表尾增加一个尾指针，指向最后一个结点。为了使空队列和非空队列的操作一致，多采用带有头结点的链队列。

• 对于带头结点的链表来说，只带队尾指针（队尾指针指向终端结点）的循环单链表因为入队操作和出队操作的时间复杂度都为O(1)（入队从队尾入，出队从队头出，因为知道终端结点所以可以直接操作）
• 类似的分析，因为只带队首指针的非循环双链表在插入操作时需要O(n)的时间复杂度找到最后一个元素，因此不适合用于做链队列
• 用含头结点的单链表表示的链队的队头在链表的链尾（队列元素为1，此时既是队头也是队尾）或链中（队列元素大于1，因为头结点存在故队头在链表中间），队尾始终在链尾

3.2.1 类声明

下面是链队列的C++模板类声明

链队列类的构造函数将队列初始化为空队列，front 和 rear 都指向头结点。反之，当front和rear都指向同一结点时，队列为空队列。

3.2.2 成员函数实现

(1)入队操作

链队列的入队操作比较简单，在队尾元素后插入新结点并移动队尾指针

具体实现如下

(2)出队操作

链队列的出队操作需要注意，当队列只有一个元素时，出队后rear指向的结点被释放，因此需要修改 rear队尾指针

(1)算法伪代码

(2)代码实现

(3)查找队头元素

(4)析构函数

析构函数完成链队列中所有结点的释放，具体实现如下

3.3 双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，如图所示

其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。可以将双端队列看作栈底连在一起的两个栈，与共享栈不同之处在于双端队列的“栈顶指针”向两端延伸而不是向中间靠拢

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。

还有一种概念是输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列，如图所示

与此对应的，有输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为，输入受限的双端队列。

若限定双端队列从某个端点插入的元素只能从该端点删除（即输入输出均受限），则该双端队列就蜕变为两个栈底相邻接的栈。

4.串详解

4.1 串的存储结构

串是一种结点元素仅由一个字符构成的线性表（即串的数据元素是单个字符而非多个字符），存储时既可以采用顺序存储结构，也可以采用链式存储结构。需要注意的是，串的操作往往将串作为一个整体来考虑，因此串在存储时还要考虑一些特殊技巧。

长度为n(n!=0)的串，其子串(包含空串也包含本身)数目为n(n+1)/2+1

• 长度为0的子串有1个
• 长度的1的子串有n个
• 长度为2的子串有n-1个
• …
• 长度为n-1的子串有2个
• 长度为n的子串有1个

4.1.1 顺序串

串的顺序存储结构称为顺序串，可采用数组存储串中的字符序列。一般来说，串的顺序存储方式有多种，在此介绍两种最常用的方法。

第一种存储方法中，data数组存储字符串序列，length表示串的长度，可以使用顺序表的C++模板类SqlList<char>来实现

另一种存储方法采用特殊字符作为串的结束标记，因而不需要额外的空间来存储串的长度。比如C和C++语言采用特殊字符”\0”作为串的结束标记

4.1.2 链串

串的链式存储结构称为链串。链串具有同链表相同的结点结构，只是链串结点中的数据类型是字符类型。因此可直接使用链表的C++模板类LinkList<char>来实现链串。

下图是最简单的链串的存储示意图。该链串中的结点的数据类型为字符类型（如char只占1字节），而指针域通常占用4个字节，因此其存储密度只有20%空间利用率很低

为了提高空间利用率可以对链串进行压缩存储，令每个结点存储多个字符

实际应用中为了提高读写效率，每个结点不一定将存储空间全部填满。

4.2 串的模式匹配*

4.2.1 朴素模式匹配算法

朴素模式匹配算法又称为BF算法，其基本思想是将模式串T中的各个字符依次与目标串S进行比较，如果T的全部字符比较完成后都与S的对应字符相同，则说明在目标串 S 中已经找到模式串T。如果比较到某个字符不同后，则将模式串T 与目标串 S 的下一个字符重新进行比较。不妨设当前串 S 和串 T比较的字符下标分别为i和j(i和j都是从1开始而非0！！！)，下图给出了BF算法的示意图

BF算法中，当出现比较不成功则i需要回溯到本次起始位置的下一个位置，而j需要回溯到开始位置。假定本次的起始位置是主串的k位置，则有如下等式成立（即当前匹配的主串长度和当前匹配的子串长度相同）
$$
i-k=j-1
$$
可以得到起始位置k的表达式为k+1-j，因此如果i需要进行回溯，应当回溯到i+2-j的位置；

(1)算法伪代码

(2)代码实现

(3)时间复杂度

设主串长度为 n，模式串长度为m，下面通过字符的比较次数来分析算法的时间复杂度。

如果进行多趟匹配后匹配成功（这是大前提，此处没有分析第一轮就匹配成功和遍历到最后一轮发现匹配不成功的情况）

• 最好的情况是每一趟匹配时比较的第一个字符不同，直到匹配成功，如在串”aaaaaaabc”中匹配模式”bc”

  • 设从主串的第i个位置开始匹配时(简称为第i趟匹配)，成功的概率为pi，其中i应满足1≤i≤n-m+1；

  • 在前i-1 趟共有i-1 次字符比较均失败，第i趟匹配成功，共比较了 m 个字符，则匹配成功需要总的字符比较次数为 m+i-1；

  • 假定从第 1 趟到第 n-m+1 趟，匹配成功是等概率的(也就是说从主串的第i个位置开始匹配的概率是相同的)，即pi=1/（n-m+1）；

  • 则最好情况下匹配成功的平均比较次数为
    

  • 一般来说，n远大于m(主串长度远大于子串长度)，因此最好情况下的BF算法匹配成功的平均时间复杂度为O(n)

• 最坏的情况是每一趟匹配比较到最后一个字符时两字符不同，如在串”aaaaaaab”中匹配模式”aab”

  • 设从主串的第i个位置开始匹配，即第i趟匹配时，成功的概率为pi，此时i应满足1≤i≤n-m+1；
  • 在前i-1趟匹配时，每趟都是 m 次字符比较，只是比较最后一个字符时不同。第i趟匹配成功，也比较了m个字符。所以总的字符比较次数为m×i（匹配失败意味着此处的i=n-m+1）；
  • 假定从第1 趟到第 n-m+1趟，匹配成功是等概率的(也就是说从主串的第i个位置开始匹配的概率是相同的)，即pi=1/（n-m+1），则最坏情况下匹配成功的平均比较次数为
    
  • 因此最坏情况下的BF算法匹配成功的平均时间复杂度为O(nm)

BF算法的特点是匹配过程简单，易于理解，但是算法效率不高，其原因是每次匹配不成功，只能回溯到上次起始位置的下一个位置。实际上，很多回溯是不必要的，由此提出KMP改进算法。

4.2.2 KMP模式匹配算法

对于BF算法，每次匹配不成功时，模式串需要回溯到开头，主串需要回溯到上次起始位置的下一个位置。而如果事先对模式串进行分析，则不需要回溯主串，因为主串从上次起始位置到匹配不成功的前一个位置构成的子串一定是模式串的前缀子串，其信息通过事先对模式串的分析存储到next数组中，这就是KMP的基本思想。

(1)next数组构造

next数组的构造非常简单，利用口诀“前缀和后缀进行比较，如果前缀和后缀没有相同前缀，则为0+1，如果相同，则相同的字符个数+1”

序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
next[]: 0 1

 1.next[1],next[2]无论是什么模式串数组，永远都是0和1。
 
 2.next[3]：如上，序号j[3]对应的模式串s[3]，那么我们就看模式串s[3]前面的字符即可，即为a b,那么s[3]的前缀为a,后缀为b,a和b不相同,则next[3]为0+1=1;
 
 3.next[4]:序号j[4]对应的s[4],找s[4]的前面字符，为a b a,字符前缀为a、ab；后缀为ba, a;有1个相同字符，则next[4]=1+1=2;

 4.next[5]:序号j[5]对应的s[5],找s[5]的前面字符，为a b a b,字符前缀为a、ab、aba三个，后缀为bab、ab、b三个，进行比较，有字符串ab相同，则next[5]=2+1=3

 以此类推......

 5.next[12]:序号j[12]对应的模式串字符为s[12],取前n-1个字符，为a b a b a a a b a b a,前缀为：ababaaabab、ababaaaba...后缀为babaaababa、abaaababa...可看出前缀中 ababa与后缀中ababa5个字符相同，则next[12]=5+1=6;

最终生成的next字符串为
j: 1 2 3 4 5 6 7 8 9 10 11 12
s: a b a b a a a b a b  a  a
next: 0 1 1 2 3 4 2 2 3 4  5  6

关于next数组的构造，这是一个小重点有必要掌握，参考链接KMP算法中next数组与nextval如何求进行刷题练习（一定要找有标准答案的题来练习，网上很多坑人的教程千万别随便学）；

下面给出next数组的构造函数

(2)nextval数组构造

nextval数组在北邮的官方教材中并没有用到，但是在其他参考资料中next数组和nextval是一起出现的所以这里做一个简单的补充

这里只介绍最简单的生成nextval数组的方法，nextval数组第一个字符永远为0。既然我们上面生成了next数组，nextval数组直接通过next数组便可生成

• 若对应字符不同，直接填入next的值；
• 若对应字符相同，填入该值对应的序号的next的值

  序号 : 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1 1 2 3 4 2 2 3 4  5  6
nextval: 0 

1.nextval[1]=0,默认值
2.nextval[2]：s[2]对应的next值为1，则以1为下标s[1]=a,与s[2b进行对比,不相同，则将s[2]对应的next值直接下发到nextval，nextval[2]=next[2]=1;
3.nextval[3]：s[3]对应的next值为1，则以1为下标，与s[3]=a进行对比，相同，则nextval[3]=nextval[1]=0;
4.nextval[4]：s[4]对应的next值为2,则以2为下标,与s[4]=b进行对比，相同，则nextval[4]=nextval[1]=0;
5.依次同理.....
6.nextval[12]:s[12]对应的next值为6，则s[6]=a与s[12]=a对比,相同，则nextval[12]=nextal[6]=4;

最终生成的nextval为：
  序号 : 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1 1 2 3 4 2 2 3 4  5  6
nextval: 0 1 0 1 0 4 2 1 0 1  0  4

(3)KMP算法

KMP的C++算法描述如下

KMP 算法不需要对主串进行回溯，相对于 BF 算法做了很大的改进，算法的时间复杂度为O（m+n）。

尽管BF匹配的最坏时间复杂度为O(nm)，但在一般情况下其实际执行时间近似为O(m+n)，因此BF算法至今仍被采用。KMP算法仅仅只在主串与子串有大量“部分匹配”的特点时其执行时间才比BF算法快得多，其主要优点是主串不需要回溯，这意味着对于规模较大的外存中字符串的匹配操作可以分段进行，先读入内存一部分进行匹配，完成后写回外存，主串无需回溯确保了在发生不匹配时不需要将之前写回外存的部分再次读入，减少了I/O操作提高执行效率。

5.多维数组详解

对于k维数组，每个元素都受到k个线性关系的约束，比如m行n列的二维数组

其中每个元素均被两个线性关系约束：

• 第j列上，除第一个结点外aij的直接前驱为ai-1,j，除最后一个结点外aij的直接后继为ai+1,j；

• 第j列上，除第一个结点外aij的直接前驱为ai,j-1，除最后一个结点外aij的直接后继为ai,j+1；

• 矩阵、多维数组与广义表都属于拓展线性结构，表中的数据元素本身也是一个复合结构 – 一般讨论多维数组都以二维数组为例，同时以矩阵来称呼二维数组
• 考研数据结构中，矩阵的逻辑表示中第一个元素有的为a0,0，有的为a1,1（王道/北邮和天勤的书写方式就不一样），解题时需要区分。而使用二维数组作为矩阵的存储结构，则二维数组的第一个元素基本都是A[0][0](C语言中数组下标一定从0开始)。学习和解题时注意区分即可，数据结构的教辅和试题相当灵活没有统一性。

5.1 一般数组的存储结构

大多数计算机语言都提供了数组数据类型，因此逻辑意义上的数组可以采用计算机语言中的数组数据类型进行存储，一个数组中的所有元素在内存中占用一段连续的存储空间。

由于计算机的内存结构都是一维的，因此在存储多维数组时，需要将数组中的所有元素按某种次序排成一个线性序列，然后将其按顺序存储到内存中。一般来说，数组不执行删除和插入操作，所以通常采用顺序存储方法来存储数组。多维数组通常有两种存储方式：行优先存储和列优先存储（这是书上的原话，很多学校的试题答案也是这样写的。然而对于三维除了行、列还有宽，因此其实这句话并不严谨。暂且认为书上研究多维数组都默认以二维数组作为研究对象）。下面将以二维数组(矩阵)为例说明这两种存储方式。

5.1.1 行优先存储

基本思想是按行存储，即存储完第i行再接着存储第i+1 行。如存储二维数组 Amn，按行优先顺序存储的线性序列为

二维数组以及其按行优先存储的示意图如下

二维数组中任意一个元素aij，其前面共有(i-1)*n+j-1个元素。设a11在内存中的地址为Loc(a11)，每个数组元素占c个存储单元，则aij的地址为
$$
Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*c
$$

在C++、PASCAL等语言中数组都是按行优先存储。以下讨论数组的存储结构时，均以C++语言的规范表示数组，数组中第一个元素各维的下标均为 0

5.1.2 列优先存储

基本思想是按列存储，即存储完第j列再接着存储第j+1列。如存储二维数组Amn，按列优先顺序存储的线性序列为

二维数组以及其按列优先存储的示意图如下

对于二维数组中的任意一个元素aij，其前面共有i-1+m*(j-1)个元素。设a11在内存中的地址为Loc(a11)，每个元素占c个存储单元，则aij的地址为
$$
Loc(aij)=Loc(a11)+[i-1+m*(j-1)]*c
$$

在FORTRAN语言中数组按列优先存储

5.2 稀疏矩阵的存储结构

当矩阵Amn中的非零元素个数远小于矩阵元素的总数时(具体什么叫远小于目前没有统一的定论)，称Amn为稀疏矩阵（稀疏矩阵被认为是一种具备特殊逻辑结构的多维数组）。在存储稀疏矩阵时，只需要存储非零元素即可。（严书对于稀疏矩阵的定义非常抽象，“相同元素或零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵”，这个定义知道就好，考研以北邮所给定义为准）

下面将介绍常见的稀疏矩阵的压缩方法（以下压缩方法都属于存储结构而非逻辑结构，专用于存储稀疏矩阵）：

• 稀疏矩阵的顺序存储：三元组表示法、伪地址表示法
• 稀疏矩阵的链式存储：邻接表表示法、十字链表表示法

稀疏矩阵压缩存储后，会失去随机存取的功能

5.2.1 稀疏矩阵的顺序存储

(1)三元组表示法

将稀疏矩阵中每个非零元素的行号、列号及值构成一个三元组（3-tuples），将所有的三元组组成一个线性表进行顺序存储，就构成了三元组表。

使用C++实现的三元组结构如下

使用C++实现的三元组表模板结构如下

下图展示了使用三元组表存储稀疏矩阵的示意图，一般按照行优先顺序遍历稀疏矩阵的每个非零元素，然后追加到三元组表中。所有三元组表的元素按行号有序，行号相同的元素按列号有序，这种特性称为三元组表的有序性。

下面以矩阵的转置操作为例，说明采用三元组表存储结构如何实现矩阵的操作以及操作中可采用的一些技巧。

a)稀疏矩阵的简单转置

对于 m 行n列的稀疏矩阵，转置后变为n行m 列的稀疏矩阵，但转置前后三元组表的结构并没有改变，而只是表中的各个三元组的行号和列号互换，并且次序发生了变化，以保证新表的有序性。一种简单的转置方法是遍历n趟三元组表(即遍历“列”趟三元组)，第一趟遍历找出列号为0的三元组，并将其行号和列号对调，添加到转置矩阵对应的三元组表中。第二趟遍历找出列号为1 的三元组并进行相同的操作，依次类推，最后一趟遍历找出列号为n-1的三元组。由于每趟遍历都需要比较所有的t个三元组的列号（其中t是稀疏矩阵非零元素的个数），因此算法的时间复杂度为O（nt）。

下图是将上面原始矩阵进行转置过后得到的结果

稀疏矩阵简单转置算法的C++实现代码如下

b)稀疏矩阵的快速转置

上述稀疏矩阵的简单转置算法并不是最优的，下面给出一种快速的稀疏矩阵转置算法，其时间复杂度为 O（n+t）。

稀疏矩阵快速转置算法的基本思想是在原始三元组表（设为A）中依次取每个三元组，交换其行号和列号后，直接存放到转置矩阵的三元组表（设为B）中的适当位置。其中关键的问题是如何确定三元组在 B 中的位置。不难发现，A 中第 0 列的第一个非零元素一定存储在 B中下标为0 的位置上，该列中其他非零元素应存放在B[0]后面连续的位置上，那么第1列的第一个非零元素在 B 中的位置便等于第0列的第一个非零元素在 B 中的位置加上第 0 列的非零元素的个数，依次类推。因此引入两个数组作为辅助数据结构：

• number[n]：存储矩阵 A 中每列非零元素的个数；
• position[n]：初始值表示矩阵 A 中每列的第一个非零元素在 B 中的位置；

显然，number数组可以通过遍历一次三元组表A 得到。position数组可以通过number数组计算得到，计算公式如下：

position[0]=0 表示 A 中第 0 列的第一个非零元素一定存储在 B 中下标为 0 的位置上。position[i]=position[i-1]+number[i-1]表示第 i 列的第一个非零元素在 B 中的位置等于第i-1 列的第一个非零元素在 B 中的位置加上第i-1列的非零元素的个数。可以参照下图理解

辅助数据结构 number与position数组确定后，接下来进行转置就非常简单了。顺序读取每一个三元组，得到列号col，则position[col]就是该元素在新三元组表中的位置，将行号和列号交换后写入新表，并将position[col]进行增1操作，这样同列的下一个元素依然可以根据position[col]确定其在新三元组表中的位置。

(1)算法伪代码

(2)代码实现

(3)复杂度分析

稀疏矩阵快速转置算法中有 3 个循环操作，前两个操作各循环 n 次，第三个操作循环 t次，因此算法的时间复杂度为O（n+t），相对于时间复杂度为O（nt）的简单转置算法，这种算法效率更高。

(2)伪地址表示法

伪地址即元素在矩阵中按照行优先或列优先存储的相对位置。该方法存储稀疏矩阵与三元素类似，只是三元组每一行中有两个存储单元存放地址，而伪地址法只需要一个。故伪地址法每一行只需要两个存储单元，一个用来存放矩阵元素值，另一个用来存放伪地址。

伪地址表示法需要2N个存储单元，其中N为非零元素个数。对于一个m*n的稀疏矩阵A，元素A[i][j]的伪地址计算方法为n(i-1)+j。

5.2.2 稀疏矩阵的链式存储

由于三元组表是一种顺序存储方式，对于经常进行插入或删除结点操作的稀疏矩阵，三元组表并不适合，此时采用链式存储结构存储这种矩阵更为恰当。链式存储结构存储稀疏矩阵的方法也有多种，最常用的是邻接表表示法和十字链表表示法。

(1)十字链表表示法

采用十字链表存储稀疏矩阵时，同三元组表一样，也是仅存储所有非零元素。同一行的非零元素构成一个带头结点的循环链表，同一列的非零元素也构成一个带头结点的循环链表。对于每个非零元素，采用一个五元组结点表示，五元组分别为非零元素的行号（row）、列号（col）、值（val）、同一行下一个非零元素的地址（rnext）、同一列下一个非零元素的地址（cnext）。下图是十字链表的结点结构示意图

使用C++实现的十字链表的非零元素结点结构如下

每行和每列构成的循环链表的头结点，可采用与非零元素结点相同的结构。每行头结点的 row 域表示本行的行号，而 col 域表示本行非零元素的个数。每列头结点的 col域表示本列的列号，而row域表示本列非零元素的个数，val域不使用。所有行的头结点又可以构成一个带头结点的循环链表，同理，所有列的头结点也可以构成一个带头结点的循环链表，两个链表可采用同一个头结点存储，该结点的 row 域和 col 域可用于表示矩阵的行数和列数。下图展示了采用十字链表存储稀疏矩阵的示意图

(2)邻接表表示法

邻接表表示法将矩阵中的每一行的非零元素串成一个链表，链表结点中有两个分量，分别表示该结点对应的元素值及其列号。

这里的邻接表和图中的邻接表是同一个东西。图的邻接矩阵相当于这里的稀疏矩阵，图的邻接表相当于稀疏矩阵的邻接表表示（由此也可以发现图之所以使用邻接表也是出于一种节约空间的考量）。邻接表表示将在图的章节详细介绍。

5.3 特殊矩阵的存储结构

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。考研数据结构中主要涉及三种特殊矩阵：对称矩阵、三角矩阵以及对角矩阵。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

5.3.1 对称矩阵

n阶矩阵中的元素可以分为三个部分：上三角区、主对角线和下三角区

对一个n阶矩阵A中的任意一个元素ai,j都有aij==aj,i则称其为对称矩阵。因为对于n阶对称矩阵，其上三角区和下三角区的元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将n阶对称矩阵A存放在一维数组B[n（n+1）/2]中，即元素ai,j存放在bk中。比如只存放下三角部分（含主对角）的元素。

元素ai,j与元素bk的下标对应关系如下（数组下标从0开始，下三角部分按行优先存储（下面与之类似，默认都是行优先存储））

5.3.2 三角矩阵

下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将n阶下三角矩阵A压缩存储在 B[n（n+1）/2+1]中。

元素下标之间的对应关系如下（数组下标从0开始）

下三角矩阵在内存中的压缩存储形式如下

与之类似的，上三角矩阵中，下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在 B[n（n+1）/2+1]中。

元素下标之间的对应关系如下（数组下标从0开始）

上三角矩阵在内存中的压缩存储形式如下

5.3.3 对角矩阵

对角矩阵也称带状矩阵。对于n阶矩阵A中的任意一个元素ai,j，当|i-j|>1时，有ai,j=0（1<=i，j<=n），则称为三对角矩阵。

在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为零（天勤规定的是均为c，其中c可以为0）。

三对角矩阵也可以采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且a1,1存放于B[0]中，其存储形式如图所示。

因此矩阵A中3条对角线上的元素ai,j在一维数组B中存放的下标为k=2i+j-3。反之，若已知三对角矩阵中某元素ai,j存放在一维数组B中第k个位置，可得i=向下取整[(k+1)/3+1],j=k-2i+3。

第四章 树

树型结构是一类重要的非线性结构，其特点是结点之间有分支，并具有层次关系。树在计算机领域中有着广泛的应用，在源程序的编译中，用树来表示源程序的语法结构；在数据库系统中，可以用树来组织信息；在计算机信息存储或传输方式中，XML、DOM树、JSON数据、磁盘路径结构等也都是用树来组织信息的。

1.基本概念

1.1 树概述

树是一种复杂的非线性数据结构，它是由 n(n≥1)个有限结点组成的一个具有层次关系的集合，把它叫作“树”是因为它看起来像一棵倒挂的树，也就是说树是根朝上，而叶朝下的，如下图所示

树的定义是递归的，即在树的定义中用到了树的定义

树具有如下特点：

• 每个结点有零个或多个子结点；
• 每个子结点只有一个父结点；
• 没有前驱的结点为根结点；
• 除了根结点外，每个子结点可以分为 m 个不相交的子树 T1…Tm；

树的逻辑结构如下

ADT 树（tree）
Data 
    树是由一个根节点和若干子树构成，树中结点具有相同的数据类型以及层次关系
Operation
    InitTree(*T):构造空树
    CreateTree(*T,definition):按照definition给出的树的定义来构造树
    Value(T,cur_e):cur_e是树T中的一个结点，返回此结点的值
    Assign(T,cur_e,value):给树T的结点cur_e赋值为value
    InsertChild(*T,*p,i,c):插入子树c作为树T中p指向的结点的第i棵子树，注意i只能是p的度+1
    DeleteChild(*T,*p,i):删除树T中p所指向的结点的第i棵子树，注意i只能是p的度

为了方便描述树的特点，本章涉及的基本概念罗列如下：

1. 结点：结点不仅包含数据元素，通过是包含指向子树的分支（即同时含有数据域和指针域）
2. 结点的度：一个结点含有的子树的个数称为该结点的度。
3. 树的度：一棵树中，最大的结点的度称为树的度。
4. 叶结点：度为零的结点称为叶结点或终端结点。
5. 分支结点：度不为零的结点称为分支结点或非终端结点。
6. 孩子结点：一个结点子树的根结点称为孩子结点。
7. 双亲结点：在含有孩子的结点中，这个结点称为孩子结点的双亲结点或父结点（双亲结点并不是两个而是一个）。
8. 兄弟结点：具有相同双亲结点的结点互称为兄弟结点。
9. 祖先结点：从根到该结点所经分支上的所有结点。
10. 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点。
11. 结点的层次：从根开始定义，根为第一层，根的孩子为第二层，如图所示

11. 树的高度或深度：树中结点的最大层次。

12. 结点的高度和深度：

    • 结点的深度是指从根结点到该结点路径上的结点个数（包含本身）
    • 结点的高度是指从该结点到叶子结点的路径中最长的路径的结点个数（包含本身，根结点的高度就是树的高度）

13. 路径：两个结点之间的路径即连接这两个结点的边（树的路径是从上到下有向的）

14. 路径长度：路径经过的边的个数，如图所示

按照树中任意结点的子结点之间是否有顺序关系，可以把树分成无序树和有序树。有序树的任意结点的子结点相互交换顺序之后构成不同的树；反之，则是无序树。本章后续内容讨论的都是有序树。

树有如下常用结论（了解即可，相比二叉树的常用结论更重要

1.2 二叉树概述

二叉树是每个结点最多有两个子树的有序树，通常子树的根被称为“左子树”和“右子树”。因此，二叉树是一种最简单的树结构，特别适合计算机处理，而且任何树都可以简单地转化为二叉树，所以这也是本章的重点。

可以参照树的ADT定义二叉树的ADT如下

ADT 二叉树（BinaryTree）
Data
    二叉树的结点具有相同的数据类型以及左右孩子关系
Operation
    InitBinaryTree(*BT): 构造空二叉树
    CreateBinaryTree(*BT, definition): 按照definition给出的二叉树的定义来构造二叉树
    DestroyBinaryTree(*BT): 销毁二叉树，释放内存
    IsEmptyBinaryTree(BT): 判断二叉树是否为空树，是则返回true，否则返回false
    Root(BT): 返回二叉树的根结点
    Parent(BT, cur_e): 返回二叉树中结点cur_e的双亲结点
    LeftChild(BT, cur_e): 返回二叉树中结点cur_e的左孩子结点
    RightChild(BT, cur_e): 返回二叉树中结点cur_e的右孩子结点
    InsertLeftChild(*BT, *p, value): 插入值为value的结点作为树BT中p指向的结点的左孩子
    InsertRightChild(*BT, *p, value): 插入值为value的结点作为树BT中p指向的结点的右孩子
    DeleteLeftChild(*BT, *p): 删除树BT中p所指向的结点的左子树
    DeleteRightChild(*BT, *p): 删除树BT中p所指向的结点的右子树
    PreOrderTraverse(BT, Visit): 前序遍历二叉树BT，并对每个结点调用函数Visit
    InOrderTraverse(BT, Visit): 中序遍历二叉树BT，并对每个结点调用函数Visit
    PostOrderTraverse(BT, Visit): 后序遍历二叉树BT，并对每个结点调用函数Visit

树和二叉树都是逻辑结构，主要区别如下：

• 树的结点个数至少为 1，而二叉树的结点个数可以为 0；
• 树中结点的最大度数没有限制，而二叉树结点的最大度数为2（当然二叉树的度可以小于2）；

二叉树具有5种基本的形态，由这5种基本形态可以形成不同的二叉树

在实际的关于二叉树的应用中，经常用到两种特殊的二叉树分别是满二叉树和完全二叉树

1.2.1 满二叉树

如果一棵二叉树中所有的叶结点均位于最后一层，而其他分支结点的度数均为2，则称此二叉树为满二叉树

1.2.2 完全二叉树

如果一棵二叉树扣除其最大层次那层后即成为一棵满二叉树，且最后一层的所有结点均向左靠齐，则称该二叉树为完全二叉树。

若对深度相同的满二叉树和完全二叉树中的所有结点按自上而下、同一层次按自左向右的顺序依次编号，则两者对应位置上的结点编号应该相同。

• 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树；
• 对于完全二叉树的定义，有另外两种更直观的理解
  • 如果对一棵深度为k有n个结点的二叉树编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，则该二叉树是完全二叉树；
  • 一棵完全二叉树一定是由一棵满二叉树从右至左、从下至上挨个删除结点得到的；

1.2.3 二叉树性质

在利用二叉树解决相关问题时，往往可以根据二叉树的性质设计出简单明了的存储结构和算法。首先要知道的是一些基本性质

• 在一棵二叉树中，所有结点的分支数等于单分支结点数加双分支结点数的两倍即n1+2n2；
• 对任何树都有，总分支数=总结点数-1（除根结点外，每个结点都有唯一的一个分支指向）；

下面是根据基本性质推导得到的一些常见性质

• 性质1：二叉树的第i层上至多有2^i-1^个结点（i≥1） – 数比数列的通项（首项为1，公比为2）

• 性质2：深度为h的二叉树至多有2^h^-1个结点（其中h≥1） – 等比数列求和

• 性质3：对于任何一棵二叉树，如果其终端结点数为 n0，度为 2 的结点数为 n2，则n0=n2+1

• 性质4：具有 n 个结点的完全二叉树的深度为 [log2n]+1（向下取整）或[log2(n+1)]（向上取整）

• 性质5：对于具有 n 个结点的完全二叉树，如果按照从上到下、同一层次上的结点按从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于序号为i的结点，有

  • 如果 i>1，则序号为i 的结点其双亲结点的序号为[i/2]（[i/2]表示对 i/2 的值取整）；如果i=1，则结点i为根结点，没有双亲。

  • 如果 2i>n，则结点i无左孩子（此时结点i为终端结点）；否则其左孩子为结点 2i。

  • 如果 2i+1>n，则结点i无右孩子；否则其右孩子为结点 2i+1。

• 性质6：给定n个结点，可以构成h种不同的二叉树，其中C(2n,n)/(n+1) (n=0,1,2,…)

• 性质7：含有n个结点的二叉链表（二叉树）中，有n+1个空链域

1.3 森林概述

由 m（m>0）棵互不相交的树构成的集合称为森林

2.基本操作

2.1 树的遍历

树的遍历的定义如下：按照某种次序访问树中的所有结点，使得每个结点被访问且仅被访问一次。其中，“访问”的含义很广泛，可定义为读取结点的数据、打印结点的信息等。

根据树的定义可知，一棵树由根结点和 m棵子树构成，因此只要遍历根结点和 m 棵子树就可以遍历整棵树。通常树的遍历方法有 3 种：前序遍历、后序遍历和层序遍历。

（1）前序遍历

1. 访问根结点；
2. 按照从左到右的顺序前序遍历根结点的每一棵子树。

（2）后序遍历

1. 按照从左到右的顺序后序遍历根结点的每一棵子树；
2. 访问根结点。

（3）层序遍历

树的层序遍历也称树的广度遍历，其操作定义为从树的第一层（即根结点）开始自上而下逐层遍历，每一层按照从左到右的顺序逐个访问结点。

下图展示了一棵树按照上述三种遍历方式对应的遍历结果

树的先序遍历与其对应的二叉树的先序遍历相同，树的后序遍历与其对应的二叉树的中序遍历相同

2.2 二叉树遍历

给出任意一棵二叉树，它的遍历序列都是唯一的。

2.2.1 遍历序列

二叉树最主要的算法就是二叉树的遍历。所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问且仅访问一次。

按照根结点访问位置的不同，不妨约定 D 表示根结点，L 表示左子树，R 表示右子树。通常把二叉树的遍历分为3种：前序遍历、中序遍历和后序遍历。

（1）前序遍历

1. 访问根结点；
2. 前序遍历访问根结点的左子树；③ 前序遍历访问根结点的右子树。

（2）中序遍历

1. 中序遍历访问根结点的左子树；
2. 访问根结点；
3. 中序遍历访问根结点的右子树。

（3）后序遍历

1. 后序遍历访问根结点的左子树；② 后序遍历访问根结点的右子树；
2. 访问根结点。

此外，按照从上到下、同一层次从左到右的顺序访问二叉树，也是一种遍历方式，称为层序遍历。因此，根据以上二叉树遍历的定义，可得下图所示二叉树的前序、中序、后序和层序遍历的结果。

结论：

• 同一棵二叉树的所有叶子结点在前序序列、中序序列、后序序列中都按相同的相对位置出现
• 满足如下条件的二叉树：
  • 先序序列与后序序列相同：空树或只有根结点的二叉树
  • 中序序列与后序序列相同：空树或任一结点至多只有左子树的二叉树
  • 先序序列与中序序列相同：空树或任一结点至多只有右子树的二叉树
  • 中序序列与层次序列相同：空树或任一结点至多只有右子树的二叉树
  • 先序序列和后序序列相反（非空）：只有一个叶子结点的二叉树
  • 先序序列和中序序列相反（非空）：空树或任一结点至多只有左子树的二叉树

2.2.2 反问题

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树，实现方法留给读者思考。

总结，由遍历序列构造二叉树，可唯一确定一棵二叉树的情况：

1. 前序遍历序列 +中序遍历序列
2. 后序遍历序列+中序遍历序列
3. 层序遍历序列 +中序遍历序列

前/后/层序两两组合无法唯一确定一棵二叉树

2.3 森林的遍历

森林的遍历方式有两种：前序遍历森林和后序遍历森林

（1）前序遍历森林，若森林非空，则：

1. 访问森林中的第一棵树的根结点；
2. 前序遍历第一棵树中根结点的每一棵子树；
3. 前序遍历除第一棵树以外的其他树。

（2）后序遍历森林，若森林非空，则：

1. 后序遍历第一棵树的根结点的各个子树；
2. 访问第一棵树的根结点；
3. 后序遍历除第一棵树以外的其他树。

下图展示了包含3棵树的森林的前序遍历和后序遍历结果

简言之，前序遍历森林就是从左到右前序遍历森林中的每一棵树；后序遍历森林就是从左到右后序遍历森林中的每一棵树。

• 森林的先序遍历对应二叉树的先序遍历，森林的后序遍历对应二叉树的中序遍历
• 森林的中序遍历和后序遍历被认为是同一回事

2.4 树、森林和二叉树的转换

在树、森林和二叉树之间有一个一一对应关系，任何一个森林或一棵树可唯一地对应一棵二叉树；反之，任何一棵二叉树也能唯一地对应一个森林或一棵树。

根据森林、树和二叉树之间的关系，有如下结论（前面有提及，这里做汇总）：

• 前序遍历森林=前序遍历该森林对应的二叉树；
• 后序遍历森林=中序遍历该森林对应的二叉树；
• 前序遍历树=前序遍历该树对应的二叉树；
• 后序遍历树=中序遍历该树对应的二叉树；

故当用二叉链表作为存储结构时，树和森林的前序遍历、后序遍历可以用二叉树的前序遍历和中序遍历实现。

2.4.1 树转换为二叉树

实际上，前面介绍树的时候说过，二叉链表同样可以作为树的存储结构，但是与用二叉链表存储二叉树的指针域的意义不同：

• 二叉链表存储二叉树，lchild指针域指向左孩子，rchild指针域指向右孩子；
• 二叉链表存储树，child指针域指向一个孩子结点，sibling指针与指向兄弟结点；

要使用二叉链表存储树，需要先将树转换为二叉树后再使用孩子兄弟存储结构存储。

树中的每个结点可能有多个孩子，但二叉树中每个结点最多只能有两个孩子。要把树转换为二叉树，就必须要找到一种结点和结点之间至多有两个变量就能说明的关系。后面我们将提到树的一种存储结构：孩子兄弟表示法，即树中每个结点最多只有一个最左边的孩子（长子）和一个右邻的兄弟，这就是我们要找的关系。利用这种关系，我们很自然地就能将树转换成二叉树。具体方法如下。

1. 在所有兄弟之间加一连线。
2. 对每个结点，除保留与其长子的连线外，去掉该结点与其他孩子的连线。

下图就是按照上述方法进行的转换步骤，首先按照步骤１和２修改树中结点之间的连线，它就已经是一棵二叉树了，再旋转45°，就更加清楚了。

2.4.2 森林转换为二叉树

将森林转换成二叉树的方法与树类似，首先将森林中的每一棵树转换成二叉树，然后将每棵二叉树的根结点视为兄弟连在一起，如下图所示。

因为要求是将森林转换为“一棵”二叉树，因此最终需要进行连接操作，具体做法就是将转换完成的二叉树依次作为前面二叉树的右子树连接即可。

2.4.3 二叉树转换成树

将二叉树转换成树实际就是将树转换为二叉树的逆过程：

1. 从左上到右下进行分层，调整为水平方向；
2. 将每层的结点和其父结点相连，删除每层结点之间的连接；

2.4.4 二叉树转换成森林

相应地，只需不停将根结点中有右孩子的二叉树的右孩子链接断开，直到不存在根节点有右孩子的二叉树。接着将每个二叉树按照上述转换成树的方法依次转化即可。

3.存储结构

顺序存储方式同样适合图和树，但这种顺序存储一般不简单

3.1 树的存储结构

无论采用什么存储结构来表示树，都要求具备两个特性：

• 能够存储各结点的信息；
• 能够唯一地表示树中各结点之间的逻辑关系——父子关系；

一般来说，无论多么复杂的逻辑结构，其存储结构一般为顺序结构、链式结构或二者的组合结构这3种，下面就介绍几种树的基本存储结构。

3.1.1 双亲表示法

树的顺序存储结构中最简单直观的就是双亲表示法，用一维数组即可实现：

• 数组下标表示树的结点
• 数组元素的内容表示该结点的双亲结点

双亲表示法在克鲁斯卡尔算法中有重要应用

数组中的第一个元素表示根结点，该结点无双亲，因此parent域用-1表示，其他结点按照层序存储。如结点B、C、D的双亲结点是下标为0的根结点，其parent域用0表示。

双亲表示法的存储结构实质上是一个静态链表，每个数组元素的结点结构如下图所示

其中data表示数据域，parent是指针域，存储该结点的双亲在数组中的下标。整棵树的C++描述如下。

双亲表示法存储树的结构的优点在于结构简单，查找结点的双亲或者祖先非常方便。

3.1.2 孩子表示法

链式存储结构（该存储结构实际上就是图的邻接表存储结构）

如果应用时需要查找当前结点的孩子，双亲表示法就会比较复杂，此时可以设计其他的存储结构来适应查找孩子结点的需求，即孩子表示法，如下图所示。

孩子表示法采用一维数组和多个单链表结合的方法。其中，一维数组的每个元素包含一个结点和一个指针，该指针指向一个链表，这个链表即该结点的所有孩子结点的集合，结点的结构如上图所示。

用C++描述上述结构，代码如下

从上述结构可知，孩子表示法与双亲表示法正好相反，查找孩子结点很方便，但是查找双亲结点较为复杂。

3.1.3 孩子-双亲表示法

顺序+链式存储结构

这种存储结构受到上述存储结构的启发，既可以方便的查找双亲结点也可以方便的查找孩子结点

3.1.4 多重链表法

链式存储结构

多重链表法指每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域的值反映出树中各结点之间的逻辑关系，如图所示。

在这种表示法中，树中每个结点有多个指针域，从而形成了多条链表。由于每个结点的孩子个数没有限制，各结点的度数又各异，可能会造成存储空间的浪费。例如，一棵度为k的树，若其结点总数为n，则至少要浪费nk-n+1个空指针域。所以多重链表法不适合存储度数较大的树。

3.1.5 孩子兄弟表示法

链式存储结构（该存储结构与树和森林与二叉树的相互转换关系密切）

孩子兄弟表示法又称二叉链表表示法，链表中的每个结点包含一个数据域和两个指针域，其中，数据域用来存储结点数据；第1 个指针域指向该结点的第一个孩子结点；第2 个指针域指向该结点的第一个右兄弟。

按照孩子兄弟表示法，树的存储结构如图所示

用C++描述上述结构代码如下

由于二叉树是一种最简单的树，这种方法便于实现树的各种操作。因此，该结构最大的优点就是可以将任意复杂的树结构转换成二叉树，这样对树的研究就可以转化为对二叉树的研究，降低了问题的复杂程度。

3.2 二叉树的存储结构

二叉树的存储结构应能体现二叉树结点之间的逻辑关系，也就是双亲和孩子之间的关系。不同的实际应用需求不同，因此衍生出了不同的存储结构。

3.2.1 顺序存储结构

二叉树的顺序存储结构使用一维数组存储二叉树的结点，利用结点的存储位置来表示结点之间的关系。由于二叉树结点之间不具有顺序关系，因此利用二叉树的性质5实现顺序存储。具体如下：

将二叉树按照完全二叉树编号；其中无结点的位置使用 NULL 表示，结点则存储在一维数组相应的位置上，如图所示。

显然，这种存储数据的方法逻辑简单但会造成空间的浪费，因此，该方法最适合存储完全二叉树。

3.2.2 二叉链表

二叉树每个结点最多有两个分支，因此一般多采用二叉链表的存储结构，其基本思想如下所示

二叉链表的结点结构如图所示

其中每一个结点由 3 个域组成。其中，数据域存储结点的数据；左指针域存储左孩子结点的地址；右指针域存储右孩子结点的地址。

二叉链表的C++的类型描述如下

二叉链表的存储方式和树的孩子兄弟表示法的存储结构完全相同，任何一棵复杂的树都可以容易地使用二叉链表的方式进行存储，因此，许多树和二叉树的应用都是围绕二叉链表这种存储结构展开的。

3.2.3 三叉链表

在二叉链表的存储方式下，从某结点出发可以直接访问到它的孩子结点，但要找到它的双亲，则必须从根结点开始搜索，最坏情况下，可能需要遍历整个二叉链表。所以，在这种情况下，可以采用三叉链表来存储二叉树，以避免该问题的发生。三叉链表的结构如图所示

三叉链表的结点结构如下所示

其中每一个结点由4个域组成。其中，数据域存储结点的数据；左指针域存储左孩子结点的地址；右指针域存储右孩子结点的地址；双亲指针域存储双亲结点的地址。

三叉链表结点的C++描述如下

4.二叉树详解

4.1 类声明

本节采用二叉链表作为二叉树的存储结构，其简单的C++类声明如下

4.2 成员函数实现

4.2.1 二叉树的创建

建立二叉树有很多种方法，其中较为简单的就是使用顺序存储结构来建立二叉链表。根据顺序存储结构的特点和二叉树的性质5，可知如果当前结点的位置为i，则其左孩子位置为2i，右孩子为2i+1。所以，以顺序存储结构为输入创建二叉树时，采用先建立根结点，再建立左右孩子的方法递归地建立用二叉链表表示的二叉树，其C++描述如下：

上述递归程序分解步骤如下，假设输入为下图的顺序存储结构表示的二叉树，则递归地建立用二叉链表表示的二叉树示意图如下

4.2.2 前序、中序、后序遍历

由二叉树的前序遍历定义，结合递归，可以很容易地写出前序遍历的递归算法，前序遍历的结果如图所示。

C++算法描述如下：

对于中序遍历，只需要把语句cout < data；移到语句PreOrder（R-> 1child）；之后即可；对于后续遍历，只需要把语句 cout <data；移到语句 PreOrder（R-> rchild）；之后即可。在这里不再给出具体代码。

4.2.3 层序遍历

在进行层序遍历时，对某一层的结点访问完毕后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层地进行，先访问的结点其左右孩子也要先访问，这与队列的特性比较吻合。因此，我们可以利用队列来实现二叉链表的层序遍历。

二叉链表的层序遍历基本思想如下，以下图(a)所示二叉树为例，层序遍历的步骤分解如下图(b)所示。

算法流程描述如下

层序遍历的C++描述代码如下

4.2.4 析构函数

二叉链表属于动态存储分配，因此，需要在析构函数中释放二叉链表的所有结点。为了防止内存泄漏，释放结点时应先释放该结点的左右子树，左右子树全部释放完毕后再释放该结点。采用后序遍历的方法，其具体算法如下：

5.哈夫曼树详解

本节将介绍二叉树的一种应用 – 哈夫曼（Huffman）编码。哈夫曼编码是1952年最先由Huffman提出的一种广泛应用于数据压缩的有效的编码方法，如JPEG中就应用了哈夫曼编码。哈夫曼编码的基础是哈夫曼树，这是一种特殊的二叉树，下面首先介绍什么是哈夫曼树。

5.1 基本概念

哈夫曼树是二叉树的一种应用，但实际上并没有明确的规定说哈夫曼树一定是二叉树，这意味着可能有哈夫曼n叉树。若题干要求构造哈夫曼n叉树但所给权值结点不足，则需要手动补充权值为0的结点使其能够构造为哈夫曼n叉树（构造方法模仿哈夫曼二叉树自底向上依次选择结点即可）

5.1.1 哈夫曼树

与哈夫曼树相关的一些概念：

• 路径长度：从树中一个结点到另一个结点的分支的数目（注意是分支的数目而非结点的数目）
• 树的路径长度：指从根结点到每个结点的路径长度的求和
• 树的带权路径长度WPL：树中所有叶子结点的带权路径长度求和

通过计算下图中的3棵二叉树的带权路径长度可以更好的理解上述概念

哈夫曼树的几个特点：

1. 权值越大的结点离根结点越近；
2. 树中不存在度为1的结点（这是因为它是自底向上构造的）；
3. 树的带权路径长度WPL最短；

给定n个权值，使用这n个权值构造哈夫曼树的算法描述如下

哈夫曼树的形态标准：左子树根权值小于右子树权值，若两者全职相同则较矮的子树在左边

5.1.2 哈夫曼编码

有了哈夫曼树，就可以对所有的结点进行编码了。哈夫曼编码根据字符出现的概率来构造平均长度最短的编码，是一种变长的编码（经哈夫曼编码得到的字符编码，其长度因符号出现的概率而不同，所以说哈夫曼编码是变长的编码）。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同，但最终编码的平均长度是最小的。

以字符出现的概率为权值构造一棵哈夫曼树后，经哈夫曼编码得到对应的码值。哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然也可以反过来规定。例如，设字符A、B、Z、C出现的次数分别为9、6、2、3，其构造的哈夫曼树和哈夫曼编码如图所示

根据哈夫曼树得到字符A、B、Z、C的编码分别为0、11、100、101。只要使用同一棵哈夫曼树，就可以把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任何一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。

• 构造哈夫曼编码时使用编码规则表更方便；
• 反向解码时直接使用哈夫曼树更方便：
  1. 遇到叶子结点则解码；
  2. 遇到非叶子结点则继续向下读取；

5.2 类声明

如何设计存储结构来存储一棵哈夫曼树呢？我们可以采用如前所述的二叉树存储方法。在这里，我们采用一种新的静态存储结构 – 静态三叉链表来存储。静态存储结构一般采用数组来实现，数组中的每个元素包含多个数据域，存储一个树结点。

静态三叉链表结点的C++描述如下

哈夫曼树是一棵正则二叉树。所谓正则二叉树，即只有度为 0 和2 的结点的二叉树。根据二叉树的性质，一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1 的一维数组存放哈夫曼树的各个结点。

图（a）所示的哈夫曼树含有4个叶子结点，因此可定义存储结构为

HNode*HTree=new HNode（7）；

其存储内容如图（b）所示，值为-1表示无孩子结点或双亲结点

为了记录每个结点的编码，需要设计哈夫曼编码表对其进行存储。编码表中每个元素的C++描述如下

其中，data存储结点的内存，在这里其数据类型假设为char，在实际应用中，可根据需要选择合适的数据类型。code数组存储结点对应的编码，在这里编码采用字符串存储。使用 HCod类型定义一个一维数组，就可以存储所有结点的编码了。

存储结构设计好以后，就可以设计哈夫曼编码的相关算法，如哈夫曼树的构造、编码算法、解码算法等。其 C++类描述如下：

其中，HTree存储哈夫曼树的结构，HCodeTable存储每个结点的编码内容。在这里，假设要编码的数据和编码结果均为字符串类型。

5.3 成员函数实现

5.3.1 哈夫曼树的创建

创建(构造)哈夫曼树的方法就是哈夫曼算法，哈夫曼树的构造算法描述如下

这里举一个例子帮助理解，一篇文档中只有4种字符，分别是A、B、Z、C，每个字符出现次数分别为9、6、2、3，每个字符出现的次数可看成是字符的权值，则按照哈夫曼算法，构造哈夫曼的步骤如图所示

下面来验证哈夫曼编码的压缩效果。若4 个字符按照定长编码，则A、B、Z、C的编码最短为00、01、10、11，按照这个编码方式，该文档的大小为(9+6+3+2)*2=40bit；而如果按照哈夫曼编码则得到的文档大小为9*1+6*2+(2+3)*2=36bit；

假设已知需要编码的数据中每种字符的权值，则可以按照哈夫曼树的建树方法对静态三叉链表进行处理，如下所示。

5.3.2 哈夫曼编码表的创建

在哈夫曼树构建完成后，下一步就是生成编码表。下面将采用向上而下递归的处理方式，对每一个结点进行编码。从哈夫曼树的根结点开始，设其编码为空，然后分别对其左右子树中的结点进行编码。若子树的根结点是其父结点的左分支则编码“0”，若是右分支则编码“1”，然后递归处理，直到叶子结点为止。

生成编码表的C++描述如下

下图(a)所示的哈夫曼树其对应的编码表可以是下图(b)所示的结构实际上字符的编码应该用bit表示，即对于1个字符“Z”使用3个bit“100”表示。由于本算法主要用来说明算法思想，为方便起见，字符编码采用纯字符串形式，即对“Z”的编码“100”使用3个字符表示（这个地方作者的意思实际上就是“编码表中的编码是以纯字符串形式表示的，而不是常见的二进制形式。在实际的计算机应用中，编码会用二进制位来表示，而不是纯字符串形式。”）。

5.3.3 哈夫曼编码&解码

通常，我们对一段信息进行哈夫曼编码时，需要对编码的数据进行两遍扫描。第一遍用来统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并要把树的信息及编码表保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍根据第一遍扫描得到的哈夫曼编码表对原始数据进行编码，并把编码后得到的码字存储起来。生成编码表后，对于要编码的字符串，如”ACCZBBBAAACBBZABAAAA”，每读出一个字符，只要在编码表中找出对应的编码即可。哈夫曼编码的代码书上并没有给出，这里给出自行编写的一个编码函数（不一定完全正确）

// 哈夫曼编码函数
void Huffman::Encode(char* s, char* d)
{
    while (*s != '\0')
    {
        // 寻找当前字符在编码表中对应的编码
        char c = *s;
        int index = -1;
        for (int i = 0; i < N; i++)
        {
            if (HCodeTable[i].data == c)
            {
                index = i;
                break;
            }
        }

        // 如果找到了对应的编码
        if (index != -1)
        {
            string code = HCodeTable[index].code;
            // 将当前字符的编码逐个写入输出缓冲区（d指针指向的位置）
            for (char bit : code)
            {
                *d = bit;
                d++;
            }
        }

        s++; // 处理下一个字符
    }

    // 最后加上字符串结束符
    *d = '\0';
}
/*

在这个编码函数中，我们逐个处理输入的字符，然后在编码表中查找对应的编码。找到编码后，将每个二进制位（'0'或'1'）逐个写入输出缓冲区（d指针指向的位置）。最后，我们加上字符串结束符'\0'，确保输出的编码字符串正确终止。

请注意，为了更好地与解码函数配合，编码表（HCodeTable）应该在创建哈夫曼树后创建，并且在编码和解码过程中都需要使用相同的编码表。

*/

对于解码，如”010110110011111100010111111000110000”编码串，其基本思想是将编码串从左到右逐位判别，直到确定一个字符。即从哈夫曼树的根结点开始，根据每一位是0还是1，确定选择左分支还是右分支，直到到达叶子结点，至此一个字符解码结束。然后，再从根结点开始下一个字符的解码。所以上述编码串的解码结果为”ACCZBBB…”。哈夫曼解码的C++描述如下

上述算法采用字符串的方式对哈夫曼编码算法进行模拟，如字符“C”使用了“101”这3 个字符进行编码，这种情况下是没有任何压缩效果的，反而会增大存储空间。实际上真正的哈夫曼编码采用比特方式进行，如字符”C”应该使用“101”这3个bit进行编码，此外，若解码时编码表未知，则必须将编码表保存在压缩后的信息中，才能保证正确解压缩。

6.并查集详解

• 并查集超简单详解：并查集；
• 相关代码及其优化：并查集；

并查集是一种树状结构，在图的最小生成树中有应用。并查集是一种简单的集合表示，管理一系列不相交的集合，主要执行对集合的“并”以及对集合元素的“查”操作：

• Union（S，Root1，Root2）：把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并；
• Find（S，x）：查找集合S中单元素x所在的子集合，并返回该子集合的根结点；

通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内（森林的定义：m棵互不相交的树的集合）。

在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从 0 到 SIZE-1其中 SIZE 是最大元素的个数。下面是并查集的结构定义以及主要运算的实现（有些地方令根的双亲小于0，有的令其等于自身，规定不同操作略有不同）。

第五章 图

在线性结构中，数据元素之间是一对一的关系，树结构中数据元素之间是一对多的关系，图结构是一种比树结构还要复杂的非线性结构，图结构中数据元素之间是多对多的关系。因此，图结构具有极强的表达能力，可用于描述各种复杂的数据对象，在通信系统、交通系统、人工智能、计算机网络、信息处理等领域有着广泛的应用。

1.基本概念

图G由两个集合V和E组成，记为G=（V，E），其中，V代表图中顶点的集合，E代表顶点之间的关系。E可以是空集，表示图只有顶点而没有边。

线性表、树与图之间的联系与区别如下：

• 线性表中的数据元素称为元素，树中的数据元素称为结点，图中的数据元素称为顶点Vertex
• 线性表中可以没有数据元素（空表），树中可以没有结点（空树），但是在图结构中不允许没有顶点
• 图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，顶点集不能为空，但是边集可以为空

为了与树区分，图中的结点称为顶点

图的逻辑结构如下

ADT 图（graph）
Data 
    顶点的非空有穷集合和边的集合
Operation 	
    CreateGraph(*G,V,VR):按照顶点集和边弧集VR的定义构造图G
    LocateVex(G,u):若图G中存在顶点u则返回u在图中的位置
    GetVex(G,u):若图G中存在顶点u则返回u的值
    DeleteVex(*G,v):删除图G中顶点v以及其相关的弧
    DeleteArc(*G,v,w):删除图中的有向弧<v,w>，若G是无向图则还需要删除其对称弧<w,v>
    DFSTraverse(G):深度优先遍历
    HFSTraverse(G):广度优先遍历
endADT

为了方便描述图的特点，本章涉及的基本概念如下：

1. 顶点：数据元素通常称为顶点。

2. 边：顶点之间的无向连线，如图（a）所示。

3. 弧：顶点之间的有向连线，如图（b）所示。

   • 含箭头的一端称为弧头，另一端称为弧尾

4. 无向图：图中的每条连线都是无方向的，如图（a）所示。

5. 有向图：图中的每条连线都是有方向的，如图（b）所示。

6. 简单图：不存在顶点到其自身的边，且同一条边不重复。图（c）和图（d）都不是简单图

   • 多重图：与简单图是相对的概念，既允许顶点通过一条边与自己关联，也允许两个顶点之间的边数对于一条

7. 邻接点：如果（vi,vj）是图中的一条边，则称vi与vj互为邻接点；如果 <vi,vj>是图中的一条弧，则称vj是vi的邻接点。

8. 含有 n 个顶点、n（n-1）/2 条边的图称为完全无向图，如图（e）所示；含有 n 个顶点、n（n-1）条弧的图称为完全有向图，如图（f）所示。

   • 若无向图有n个顶点，则最多有(n-1)n/2条边；称有(n-1)n/2条边的无向图为无向完全图
   • 若有向图有n个顶点，则最多有(n-1)n条边；称有(n-1)n条边的有向图为有向完全图

9. 边或弧很少的图，称为稀疏图；边或弧较多的图，称为稠密图。稀疏图和稠密图常常是相对而言的，如图（g）和图（h）对比，则图（g）是稀疏图，图（h）是稠密图。

10. 度：一个顶点的度是与它相关联的边或弧的条数。
11. 入度：有向图中到达顶点的弧数，下图中顶点 A 的入度为 1。
12. 出度：有向图中顶点出发的弧数，下图中顶点 A 的出度为 2。
13. 网：带权的图；根据网是否有向可分为有向网和无向网。

14. 子图：图的子集

15. 路径：接续的边的端点构成的顶点序列，下图中v1到v5的路径为(v1,v4,v3,v5)；
16. 路径长度：路径上边或弧的数目；在网中为路径上边或弧的权值之和。下图中v1到v5的路径长度为3；

17. 回路：起点和终点相同的路径。
18. 简单路径：路径序列中，顶点不重复出现的路径，如图（a）所示。
19. 简单回路：路径序列中，除了起点和终点外，其余顶点均不相同的回路，如图（c）所示

20. 连通图：在无向图中，若任意一对顶点都存在路径，则称其为连通图，否则为非连通图。
21. 连通分量：当图非连通时，无向图中的极大连通子图称为联通分量
    • 极大连通子图包含所有连通的顶点以及和这些顶点相关联的所有边，无法继续扩充顶点
    • 极小联通子图中的“极小”指的是添加一条边就会出现环

22. 强连通图：在有向图中，若任意一对顶点都存在路径(双向路径)，则称其为强连通图，否则为非强连通图。
23. 强连通分量：当图非连通时，有向图中的极大连通子图称为强连通分量

24. 生成树：连通图中一个极小连通子图，即含有全部顶点，但只有足以构成树的 n一1条边，如图所示。

25. 生成森林：在非连通图中，每个连通分量都可以得到一棵生成树，这些连通分量的生成树构成生成森林，如图所示。

2.图的存储结构

图是一种复杂的非线性结构，因此要想设计出合理的图的存储结构，就一定要先讨论图的逻辑结构关系。数据结构中除集合外还有3种逻辑结构，即线性结构、树结构和图结构，对比分析如下。

1. 线性结构：结点之间的关系是线性关系，即除头结点和尾结点外，每个结点只有唯一一个前驱和唯一一个后继。
2. 树结构：结点之间的关系实质上是层次关系，即除根结点外，每个结点都只有唯一一个前驱，但每个结点可以有0个或多个后继。
3. 图结构：结点之间是多对多的关系，即每个结点都可以有 0个或多个前驱和 0 个或多个后继，结点之间的关系是任意的。

根据图的定义，一个图包括两部分信息，即顶点和顶点之间的关系。顶点之间的关系表示是设计图存储结构的关键。下面将讨论5种图的存储结构：邻接矩阵、邻接表、十字链表、邻接多重表和边集数组。

2.1 邻接矩阵

二维数组可以用来表示顶点之间相邻关系。设G=（V，E）是具有 n 个顶点的图，顶点序号依次为 0，1，…，n-1，则邻接矩阵表示为

无向图的邻接矩阵一定是一个对称矩阵，如图（a）所示；而有向图的邻接矩阵可以是不对称的，如图（b）所示；

网的邻接矩阵可以定义为

不同的教材对结点到自身的路径长度规定不同，有的规定尾0有的规定的∞，需要注意辨别；

实际编程中，可以使用一个计算机允许的、大于所有边上权值的数，即宏 MAX_VALUE代替∞。下图给出了一个网的邻接矩阵存储的示例。

用邻接矩阵表示法来表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还要用一个顺序表来存储顶点信息。

下面给出邻接矩阵的 C++描述：

2.2 邻接表

(1)有向图的邻接表存储

邻接表表示法类似于树的孩子链表表示法，是一种顺序结构和链式结构相结合的存储方法。对于图的每个顶点vi，将所有邻接于vi的顶点链接成一个单链表，称其为顶点vi的边表（对于有向图称为出边表）；对所有顶点使用顺序结构进行存储，得到顶点表，用来存放顶点v的信息和对应边表的头指针，如图所示。

所以，邻接表的存储结构中有两种结点结构：顶点结点VertexNode 和弧结点ArcNode，如图所示。

邻接表顶点和弧结点的 C++描述如下：

(2)无向图的邻接表存储

在存储无向图时，每一条边相当于两条弧，如图所示。

(3)网的邻接表存储

若采用邻接表存储无向网，那么每条弧还需要存储边权值

(4)有向图的逆邻接表

有向图还有一种表示方法称为逆邻接表表示法，该方法为图中每个顶点vi，建立一个入边表，入边表中的每个表结点均对应一条以vi为终点的边，其方法与出边表类似

邻接表用C++语言描述如下

2.3 十字链表

对于有向图，可以采用十字链表作为存储结构。十字链表可以看成是将邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应有向图的每一条弧都有一个弧结点，对应有向图的每一个顶点都有一个头结点。每条弧对应的弧结点分别组织到出边表和入边表，其顶点结构如下

十字链表头结点的C++描述如下

十字链表弧结点的C++描述如下

在十字链表中既可以很容易地找到以vi为弧头的弧，也可以很容易地找到以vi为弧尾的弧，因而容易求得每个顶点的入度和出度。因此，在某些有向图的应用中，十字链表是一个很有用的工具。如何建立十字链表教材并没有给出相关代码，需自行解决。

下图是一个十字链表的示例

2.4 邻接多重表

无向图可以采用邻接多重表来存储。用邻接表存储无向图，其每条边的两个顶点分别在该边所依附的两个顶点的边表中，这种重复存储给图的某些操作带来不便。例如，在对已访问过的边做标记，或者要删除图中某一条边时，都需要找到表示同一条边的两个边表结点。在进行这类操作的无向图中采用邻接多重表作为存储结构更为适宜。

邻接多重表的存储结构和邻接表类似，也是由顶点表和边表组成，每条边用一个边表结表示，其顶点表和边表的结点结构如下

邻接多重表顶点表结点的C++描述如下

邻接多重表边表结点C++描述如下

下图是一个邻接多重表的示例

2.5 边集数组

图的另外一种常见的存储方法是边集数组。它利用两个一维数组，其中一个数组存储图中的顶点，另一个数组存储图中的边。在存储边的数组中，每个数组元素存储一条边的起点、终点（对于无向图，可选定边的任意一个顶点为起点）和权（网），在数组中的次序可任意安排。下图给出了一个有向网的边集数组的存储示意图。

在边集数组中，查找一条边或求一个顶点的度都需要扫描整个边数组，其时间复杂度为O（e），因此适用于那些对边依次进行处理的操作，不适用于对顶点的操作和对任意一条边的操作。另外，边集数组表示一个图时需要一个边数组和一个顶点数组，所以其空间复杂度为O（n+e），从空间复杂度上讲，边集数组也适合表示稀疏图。

3.图详解

3.1 类声明

此处使用图的邻接表作为图的存储结构，其简单的C++类声明如下

3.2 成员函数实现

3.2.1 图的构建

假定图的所有的信息全部存储在文本文件中。文件首先存储顶点数量、边的数量，然后存储每个顶点的名字，最后存储所有的边。每条边用弧尾结点编号和弧头结点编号表示，编号从0开始顺序编号。文件中所有信息用空格或回车分开。例如，图（a）所示的有向图，对应的文件内容如图（b）所示（b中的边用数表示，01表示头结点为v1尾结点为v2的有向边，以此类推）。

该文件可用ifstream对象打开，则构造函数中需要该对象作为实参传递进来。下面给出一个用邻接表建立有向图的算法，即图的构造函数的C++描述。

该算法的时间复杂度是O（n+e）。在邻接表表示中，每个边表对应于邻接矩阵的一行，边表中结点个数等于对应行非零元素的个数。对于一个具有n个顶点、e条边的图G，若G是无向图，则它的邻接表表示中有n个顶点表结点和2e个边表结点。若G是有向图，则它的邻接表表示中均有n个顶点表结点和e个边表结点。因此邻接表表示的空间复杂度为O（n+e）。

需要注意的是，同一个图的邻接表表示不唯一，这是因为在邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。但若采用邻接矩阵表示，则是唯一的。

3.2.2 深度优先遍历

和树的遍历类似，图的遍历也是指从图中的某一顶点出发，对图中的每一个顶点访问且仅访问一次。若给定的图是连通图，则从图中任一顶点出发可以访问到所有顶点。然而图的遍历比树要复杂得多，这是因为图中任一顶点都可能和其他顶点邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。

为避免重复访问同一个顶点，必须记住每个顶点是否已被访问过。所以，图的遍历算法必须添加一个布尔向量 bool visited[n]，初始值为 FALSE，一旦访问了顶点v，则 visited[i-1]设置为TRUE。

根据搜索路径的方向不同，图的遍历方式有两种，即深度优先遍历和广度优先遍历。这里先介绍深度优先遍历。

深度优先遍历（DFS，Depth-First Search）类似于树的前序遍历，假定给定图 G的初始状态是所有顶点均未曾访问过，它的基本思想如下

很显然这是一个递归的过程，对下图从v1开始进行深度遍历，得到的结点依次为v1,v2,v3,v4,v5,v6；若从v3开始进行深度遍历结点依次为v3,v1,v2,v5,v6,v4；

具体的，下图展示了一个深度优先遍历访问过程中栈结构的示意

无论采用哪种存储结构，深度优先遍历的思想是一致的，只是在寻找结点 v 的第一个未访问邻接点时的实现方法不同。邻接表需要根据表头结点找到出边表，然后遍历弧结点所在的链表，从而找到邻接顶点。

对于邻接表存储结构，从邻接表中寻找结点v 的第一个未访问邻接点的实现方法如下：

值得注意的是图的邻接表表示不唯一，故对于指定的初始出发点，同一个图的遍历顺序也是不唯一的，它取决于邻接表表示中边表结点的链接次序。这里给出采用邻接表的深度优先遍历的完整 C++语言描述：

基于邻接矩阵的深度优先算法和基于邻接表的深度优先算法的区别仅在于寻找第一个未访问过的邻接点时的方法不同，前者是遍历当前结点所在邻接矩阵的一行，时间复杂度是O（n）；后者是遍历以当前结点为首的单链表，由于所有结点的单链表长度之和是e，所以当用邻接表存储图时，深度优先遍历的时间复杂度均为O（n+e），使用的栈的深度为O（n），空间复杂度为O（n）。

3.2.3 广度优先遍历

图的广度优先遍历（BFS，Breadth-First Search）类似于树的层序遍历，假定给定图G 的补始状态是所有顶点均未曾访问过，它的基本思想如下

采用广度优先遍历方式访问时的结点依次为v1,v2,v4,v3,v5。广度优先遍历以队列来得到下一个待访问的结点，其状态如下

无论采用哪种存储结构，广度优先遍历的思想是一致的，只是在寻找结点 v 的所有未访问的邻接点时的实现方法不同。

对于邻接表存储结构，从邻接表中寻找结点v的所有未访问的邻接点的方法如下：

同样地，图的邻接表表示不唯一，故对于指定的初始出发点，同一个图的遍历顺序也是不唯一的，它取决于邻接表表示中边表结点的链接次序。这里给出采用邻接表的广度优先遍历的完整 C++语言描述：

基于邻接矩阵的广度优先遍历算法和基于邻接表的广度优先遍历算法的区别仅在于寻找所有未访问过的邻接点的方法不同，前者是遍历当前结点所在邻接矩阵的一行，时间复杂度是O（n）；后者是遍历以当前结点为首的单链表，由于所有结点的单链表长度之和是e，所以当用邻接表存储图时，广度优先遍历的时间复杂度均为O（n+e），空间复杂度为O（n）。

3.2.4 析构函数

基于邻接矩阵的图类MGraph，由于图的顶点集合和弧集合都是提前定义好的数组，因此不需要析构。而基于邻接表的图类 ALGraph，其边集是存储在链表中的，因此需要析构。

析构的方法可以利用广度优先遍历的思想。代码如下：

4.关键路径

• 参考文章：关键路径算法相关概念解读_51CTO博客_关键路径 算法；

关键路径也称为最长路径，与最短路径相对，但不能借鉴最短路径的两种算法思想（因为关键路径中顶点还有前提）。在关键路径算法中，将事件定义为AOE图中的“顶点”，将活动定义为AOE图中的“弧”。需要注意辨别以下两个名词与动词之间的搭配：

• “发生”是针对于事件的，也就是图中的顶点。只有在指向该顶点的所有有向边对应的活动结束，该顶点所代表的事件才发生。举个例子，一个事件C，它仅被两条边a, b指向，仅当a，b两活动都完成时，事件C发生。
• “开始”是针对于活动的，也就是图中的弧。只有在一个顶点所代表的事件发生后，从该顶点出发的所有边对应的活动才能开始。什么时候开始？即可以在事件一完成就立马开始接下来的活动，也可以推迟活动开始的时间。

详细的这部分内容直接参考天勤书解答的很详细，本部分算法只要求掌握手工求解最长路径对代码部分并没有要求。

第六章 查找

排序的重点在对算法代码的理解上，查找的重点在对数据结构的理解上。这两章听视频课收益比纯看书要大，故此处不做过多整理。

1.基本概念

查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功；若表中不存在关键字等于给定值的记录，则称查找不成功。

平均查找长度：平均查找长度是指所有查找过程中进行关键字比较次数的平均值。对于含有 n 个记录的表，查找成功时的平均查找长度为

2.线性结构

2.1 顺序查找

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的查找。

ASL分析：下图是使用顺序查找对该表进行查找所需要的所有可能的比较次数（其中F表示查找失败标志）

查找成功ASL：

查找失败ASL：

2.2 折半查找

折半查找要求线性表有序，即表中记录按关键字有序。折半查找的算法步骤叙述如下：

a）首先确定整个查找区间的中间位置mid=（left + right）/2；
b）用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后（右）半个区域继续进行折半查找；若小于，则在前（左）半个区域继续进行折半查找；
c）对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放；

折半查找的过程可用判定树来描述，假设要在{0，1，2，3，5，8}中进行查找，构建的判定树如下（构建过程很简单，依次选择mid作为根结点构建即可）：

• 判定树是一棵平衡二叉树。若有序序列有n个元素，则对应的判定树有n个非叶结点和n+1个叶结点
• 其中红色非叶结点表示表中存在的数据，蓝色叶子结点表示查找失败的状态
• 比较次数/查找长度就是根结点到任何一个结点路径上经历的结点的个数

通过上述判定树得出查找成功和查找失败的ASL分别如下

2.3 分块查找

较快地查找又便于动态变化的查找方式：索引查找（分块查找）

索引查找算法又称分块查找，它吸取了顺序查找和折半查找各自的优点。其基本思想如下：将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二块中的所有记录的关键字，第二个块中的最大关键字小于第三块中的所有记录的关键字，以此类推。

分块查找需要额外的数据结构，即索引表。表中的每一项对应线性表中的一块，其中键值分量存放对应块的最大关键字，链值分量存放指向本块第一个元素和最后一个元素的指针/下标

分块查找分为索引查找（选块）和块内查找（块内选数），因此分块查找的平均查找长度是两次查找的平均查找长度之和。

因为索引表中的索引项都是按照关键字递增顺序排列，因此可首先使用二分查找确定待查找元素属于哪一块（二分查找结束后，到low所指的块中进行精确查找，若low不指向任何块则直查找失败），然后在块中使用顺序查找精确查找该元素。

3.树形结构

3.1 排序二叉树

二叉排序树（二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

a）左子树结点值<根结点值<右子树结点值
b）左、右子树也分别是一棵二叉排序树

对二叉排序树中序遍历，可得一个非递减的有序序列

3.1.1 排序二叉树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理：

1. 若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。
2. 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
3. 若结点 z 有左、右两棵子树，则令 z 的右子树中最小关键字/左子树中最大关键字r替代 z，然后从二叉排序树中删去结点r（转化为考虑第一或第二种情况）

下图展示了在三种情况下分别删除结点的过程

3.2 平衡二叉树

平衡二叉树是一种特殊的二叉排序树（二叉排序树的升级版），有如下几个重要概念：

• 平衡二叉树（AVL树）：任意节点左、右子树高度差的绝对值不超过1
• 平衡因子：左子树与右子树的高度差，其值只可能是-1，0，1
• 最小不平衡子树：以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树

注意：

• 二叉排序树中，插入结点 M 而后删除 M，所得二叉排序树不变。平衡二叉树不具备此性质
• 平衡调整每次调整的对象都是最小不平衡子树， 即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树

3.2.1 平衡二叉树的插入

若要保证一棵二叉排序树是平衡的，可遵循以下方式：每当二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

下面以更直观的方式展示在插入过程中如何进行平衡调整

（1）LL 平衡旋转（右单旋转）：在 A 的左孩子的左子树中插入导致不平衡。调整方式为：A 的左孩子结点右上旋

由于在结点A的左孩子的左子树上插入了新结点 ，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树

（2）RR平衡旋转（左单旋转）：在A的右孩子的右子树中插入导致不平衡。调整方式为：A的右孩子结点左上旋

由于在结点 A 的右孩子的右子树上插入了新结点，A 的平衡因子由-1 减至-2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为A 结点的右子树

（3）LR 平衡旋转（先左后右双旋转）：在 A 的左孩子的右子树中插入导致不平衡。调整方式为：A 的左孩子的右孩子先左上旋再右上旋

由于在A的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后把该C结点向右上旋转提升到A结点的位置

（4）RL平衡旋转（先右后左双旋转）：在A 的右孩子的左子树中插入导致不平衡。调整方式为：A 的右孩子的左孩子先右上旋再左上旋

由于在A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由-1 减至-2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后把该 C结点向左上旋转提升到 A 结点的位置

• LR 和 RL 旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程，上述均以插入C的左子树为例
• 上述对调整方式的命名，并不是对调整过程的描述，而是对不平衡状态的描述。如LL（Left-Left）调整，即新插入结点落在最小不平衡子树根结点的左（L）孩子的左（L）子树上，对这种不平街状态进行调整称之为LL调整。又如LR调整（Left-Right），即新插入结点落在最小不平衡子树根结点的左（L）孩子的右（R）子树上，对这种不平衡状态进行调整称之为LR调整。因此大家要在大脑里建立一个4个名称到不平衡状态的一一映射，而不是到调整过程的一一映射，从而可以在做题时减少思维量，提高做题速度。在考研数据结构题目中，常常问某种不平衡状态下应采用何种调整方式，从LL，RR，LR，RL中选其一，其实问的就是出现了哪种不平衡状态，如果你在大脑里建立的是4个名称到不平衡状态的一一映射，就可以直接选出答案。如果你在大脑里建立的是4个名称到调整方式的一一映射，则需要在脑海里过一遍调整过程才能选出答案.

3.3 红黑树

红黑树与AVL类似，都是对排序二叉树的一种改进，相对于AVL，红黑树的特性没那么严格因此在插入和删除的过程中并不会频繁调整，效率更高。对于一棵动态查找树，如果插入和删除操作比较少，查找操作比较多 ，采用AVL树比较合适，否则采用红黑树更合适。但由于维护这种高度平衡所付出的代价比获得的效益大得多，红黑树的实际应用更广泛

一棵红黑树是满足以下性质的二叉排序树：

1. 根结点是黑色的
2. 叶结点（虚构的外部结点、NULL 结点，一般指查找失败的结点）都是黑色的
   • 注意，此处红黑树的叶结点是为了便于实现和理解（保证红黑树中每个关键字内部结点的左右孩子均非空），也称为外部节点
3. 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）
4. 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同

注意：

• 上述性质常用于选择题判断一棵树是否是红黑树，可以简单记为“左根右，根叶黑；不红红，黑路同”
• 黑高的定义：从某结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（记为 bh），黑高的概念是由性质4确定的。根结点的黑高称为红黑树的黑高。

根据上述红黑树的定义，可以得出以下两个结论：

1. 从根到叶结点的最长路径不大于最短路径的2倍；
2. 拥有n个内部结点的红黑树的高度h<=2log(n+1)，这意味着红黑树的查找时间复杂度也是O(logn)

3.3.1 红黑树的插入

红黑树的插入/删除操作同样分为两部分，前半部分与二叉排序树相同，后半部分即进行红黑调整。下面仅介绍删除操作的红黑调整，删除操作难度过大仅了解一些性质即可。

红黑树的插入操作按照以下步骤进行（一般考察大题手动绘制）

• 上述黑叔的四种情况，与AVL的四种情况完全相同，不同之处在于最后调整过后，需要将互换的两个结点染色（即换色，黑变红，红变黑）
• 可以直接看王道视频红黑树的插入，这一节讲的非常简答易懂，关键还是需要清楚AVL的平衡调整

3.4 B-树

B-树是一种平衡的多路查找树，在文件系统中很有用.B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

1）树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2）若根结点不是终端结点，则至少有两棵子树。
3）除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字（此处的取整为向上取整）。
4）所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

5）所有非叶结点的结构如下

其中Ki表示结点中存储的关键字，按照有序排列；Pi为指向子树根结点的指针，且Pi-1所指子树中所有结点的关键字都小于Ki，而Pi所指子树中所有结点的关键字都大于Ki；n为结点中关键字的个数；

B树的高度是一个重要考点，注意B树的高度不包括最后的叶子结点（某些教材可能包括，数据结构就是这么有魅力…详细推导看王道视频B树）

3.4.1 B-树的插入

结论：B树中，除了根结点外，每个非叶子结点的关键字个数都在区间[[m/2]-1,m-1]内

在B树中查找到插入的位置后，不能简单的将其添加到终端结点中，这可能导致整棵树不满足B树的定义。将关键字Key插入B树的过程如下：

1. 定位。利用B树查找算法，找出插入该关键字的最底层中的某个非叶结点（在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最底层中的某个非叶结点）。
2. 插入。若插入后的结点关键字个数小于m则可以直接插入，若插入后关键字的结点个数大于等于m则需要对结点进行分裂操作。
   • 分裂的方法是：取一个新结点，在插入key后的原结点，从中间位置（[m/2]向上取整）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（[m/2]）的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

3.4.2 B-树的删除

• 参考视频：B树的插入删除

B树的删除需要保证删除后结点中的关键字个数大于等于[m/2]-1（B树的基本性质），若不满足该性质则需要进行“合并”操作。

• 当被删除关键字k不在终端结点（最底层的非叶结点）时，可以用k的前驱或后继k’来代替k，然后在相应的结点中删除k’。因为关键字k’必定在某个终端结点中因此转换为被删关键字在终端结点中的情形

• 当被删关键字在终端结点中时，有下列三种情况：

  1. 直接删除关键字。若被删关键字所在结点的关键字个数>=[m/2]，表明删除该关键字后仍满足 B 树的定义，则直接删去该关键字。
  2. 兄弟够借。若被删关键字所在结点删除前的关键字个数=[m/2]-1，且与该结点相邻的右（或左）兄弟结点的关键字个数>[m/2]，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡

  

  3. 兄弟不够借。若被删关键字所在结点删除前的关键字个数=[m/2]-1，且此时与该结点相邻的左、右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。

  

  在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0（根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到[m/2]-2，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

3.5 B+树

B+树是应数据库所需出现的一种B树的变形，一棵m阶的B+树需要满足以下条件：

1. 每个分支结点最多有m棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

m阶的B树和B+树主要差异如下（这也是考研题型中B+树的考点）

关于B+树的查找，因为非叶结点上的关键字值并不是最终索引值，因此 在 B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径

4.散列结构

4.1 基本概念

• 散列表：根据关键字而直接进行访问的数据结构

• 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash（key）= Addr

• 同义词：发生碰撞的不同关键字

• 冲突：散列函数把两个或两个以上的不同关键字映射到同一地址

• 装填因子a=表中记录个数n/散列表表长m。平均查找长度依赖于装填因子a，而不直接依赖于关键字个数和散列表表长

查找成功的平均查找长度

查找失败的平均查找长度

查找不成功的位置是哈希函数所能映射到的位置，而不是哈希表中所有的位置

4.2 散列函数

常见的散列函数有以下几种：
（1）除留余数法：H（key）= key%p，p是不大于表长的质数
（2）直接定址法：H（key）= key或H（key）= a*key + b
（3）数字分析法：选取数码分布较为均匀的若干位作为散列地址
（4）平方取中法：取关键字平方值的中间几位作为散列地址

4.3 冲突处理

需要注意，只可能尽量减少冲突的发生而不可能完全避免冲突。冲突的处理方法有以下几种：

1. 拉链法：同义词串成一个链表
2. 开放定址法：
   1. 线性探测法：di=0，1，2，…，m-1，直到找出一个空闲单元或查遍全表为止
   2. 平方探测法（二次探测法）：di=0^2^，1^2^，-1^2^，2^2^，-2^2^…
   3. 伪随机序列法：di=一个伪随机序列
3. 再散列法：Hi=（H（key）+i× Hash2（key））%m。其中，H（key）为哈希函数；m 为哈希表表长；di为增量序列。
4. 建立公共溢出区

考点：

• 线性探测法会造成大量元素在相邻的散列地址上“聚集”，会影响平均查找长度
• 平方探测法中，不能随便删除表中已有元素，应先逻辑删除并定期物理删除。该方法的缺点是不能探测到散列表上所有的单元，但至少能探测到一半单元
• 查找效率取决于散列函数、处理冲突的方法、装填因子α

第七章 排序

1.基本概念

排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

所谓稳定性，是指对于相同关键字的两个元素，排序后相对位置不变。

排序算法的衡量标准有两个：时间复杂度和空间复杂度。

由排序过程中涉及的存储器不同，可将排序方法分为两大类：

（1）内部排序：待排序的记录存放在计算机随机存储器中进行的排序过程
（2）外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外进行访问的排序过程。（此部分在 809 中不涉及）

按照排序过程中依据的不同原则，内部排序又可以分为以下几类：
（1）插入排序：直接插入排序、折半插入排序、希尔排序
（2）交换排序：冒泡排序、快速排序
（3）选择排序：简单选择排序、堆排序
（4）归并排序：二路归并排序
（5）桶排序：基数排序、基数排序、桶排序

2.内部排序

• 初始序列基本有序时，直接插入排序比较的次数最少

• 比较次数与序列初态无关的算法：二路归并排序、简单选择排序

2.1 插入类排序

2.1.1 直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增 1 有序表。直接插入排序适用于顺序表和链表。

对于直接插入排序，一趟排序后并不能确保使得一个关键字到达其最终位置。

2.1.2 折半插入排序

折半插入排序结合了直接插入排序和折半查找两种算法，先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。

折半插入排序适合关键字较多的情况，与直接插入排序相比，折半插入排序在查找插入位置上面所花时间大大减少，但关键字移动次数与直接插入排序相同，故时间复杂度与直接插入排序相同

2.1.3 希尔排序

希尔排序也叫缩小增量排序，它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序只能用于线性表。

2.2 交换类排序

2.2.1 起泡排序

冒泡排序的基本思想是：重复地走访过要排序的元素，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

在冒泡排序中：

• 所产生的有序子序列一定是全局有序的
• 每趟排序都会将一个元素放到其最终位置上

2.2.2 快速排序

快速排序基于分治思想。其基本思想是：通过一趟排序将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。取枢轴 pivot，通过一趟排序使其左边元素均小于pivot，右边元素均大于等于 pivot，这个过程称为一趟快速排序。

快速排序中的一趟并不产生子序列，但每趟排序后会将枢轴元素放到最终位置上。在快速排序计算的过程中，先处理较短分区可以减少递归深度，但递归次数与先处理哪个分区无关。

2.3 选择类排序

2.3.1 简单选择排序

选择排序（Selection sort）是一种简单直观的排序算法。其基本原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.3.2 堆排序

堆排序也称为快速选择排序，它在借助堆的性质可以很快选出序列中的最值。堆排序整个过程就是不断调整堆，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树

2.4 二路归并排序

归并排序可以看作是分治法的具体使用：先将整个序列分为两半，对每一半分别进行归并排序得到两个有序序列，将这两个有序序列归并为一个有序序列即可

2.5 桶排序

2.5.1 计数排序

计数排序不是基于元素比较，而是利用数组下标确定元素的正确位置。计数排序的基素本思想是对于给定的输入序列中的每一个元素 x，确定该序列中值小于 x 的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

2.5.2 桶排序

桶排序（Bucket sort）也不是基于比较的一种排序。其基本思想是：设计K个桶，然后将N个桶分散到K个桶中，将每个桶进行排序，然后按照次序将各个桶中元素输出即可完成排序操作。
桶排序的时间复杂度取决于各个桶之间数据进行排序的时间复杂度。桶划分的越小，各个桶之间的数据越少，排序所用时间也会越小，但相应空间消耗会增加。

2.5.3 基数排序

基数排序（Radix Sort）是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

3.外部排序

809不涉及故暂时不对这部分做要求

第八章 经典算法应用

此部分不会出具体考题，看天勤的视频理解即可（实在不放心就去看算法那篇笔记中详细的介绍）

1.贪心算法

贪心算法不从整体最优上加以考虑，所做的仅是在某种意义上的局部最优解。而局部最优解叠加到一起便是整体上的最优解。

严格意义上，若要使用贪心算法求解问题，该问题应当具备如下性质：

a）贪心选择性质：指求解的问题的整体最优解可以通过一系列的局部最优解得到。

b）最优子结构性质：一个问题的最优解包含着它的子问题的最优解。

具体实践有：

• 最优装船问题
• 哈夫曼编码
• Dijkstra 算法
• 最小生成树

2.穷举法

在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中筛选出问题的答案。

• 解空间的划定必须保证覆盖问题的全部解
• 解空间集合以及问题的解集一定是离散的集合，即可列的、有限的

3.递归与分治

将规模较大的问题分割为规模较小的同类问题，然后将这些子问题逐个加以解决。

具体实践有：折半查找

4.回溯

在包含问题的所有解的解空间，按照深度优先搜索的策略，从根节点出发深度探索解空间树。当探索至某一结点时，要先判断该结点是否包含问题的解。如包含，从该结点出发继续探索下去；如不包含，说明以该结点为根节点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间的“剪枝”操作。

5.动态规划

动态规划是一种将实例分解为更小的/相似的子问题，并存储子问题的解，使得每个子问题只求解一次，最终获得原问题的答案。

6.递归

递归程序的优点是程序结构简单、清晰、程序易读、易证明其正确性；缺点是执行中占内存空间太多，运行效率低，算法不容易优化。

• 递归定义由基本项和归纳项两部分组成。

• 当问题的定义是递归的、数据结构是递归的、问题的解法是递归的时，最好利用递归。

• 递归程序的入口语句和出口语句一般用条件判断语句实现。

• 尾递归在转为非递归算法时，可不使用栈。