数据结构考研考点精讲及复习思路

《《数据结构》考研考点精讲及复习思《数据结构》考研分析与指导~、考试特点分１．在计算机专业入学统，作为专业课综合中的一个版块进行。在部分自主命题院校入学考试中有单独作为一个科目进行，也有和其他一门或者两门科目联合出题。２．出题形式多为选择题和综合应用３．侧重于基础知识点及对知识点灵活运用的考二、复习方１．分清复习的阶段，把握复习进２．亲手做题，在练习中总结出题方向和方法，重视，透彻分析，揣摩出题人心理。只有做好一定量的习题，才能帮助理解和牢固掌握考点。３．讲过的知识点和题彻底掌握并及时回顾，不要学过忘过。４．注重知识点之间的联系５．不可忽视基础概念和知识体系。但是同时还要做到重点突出，突破难点，查缺补漏三、考试内容及分值分布章重难必考考试题１．绪选２．线性√√√选择、综合分３．栈和队√√√选择、综合分４．√√选择、填５．数组和广义选择、填６．√√√选择、综合分７．√√√选择、综合分８．查√√√选择、综合分９．排√√√选择、综合分１四、章节知识点及题型分章知识题型题型易考１数据结构的定义、逻辑结的分类、算法的定义和杂度和物理结构法性能的选题逻辑结构和物理结构的和算法性能的复杂度分类、法的定义２性表的概念及运算性表的顺序性表的链式元多项式的表示相加选题１．线性表的定义和基２．线性表的顺序３．线性表的链式本运算综合析题１．线性表算法的设的定义和运的顺序和链选题１．栈和队列的定义和２．栈和队列的顺序运链式３栈队的应列的定义和运列的顺序和链列的应用式综合析题栈和队列的应用算４类型的定的顺序和链式的模式匹配算法选题１．串的定义和综合析题２．串的模式匹配算５组的定义和运算组的顺序殊矩阵的压缩义表选题数组和广义表的定义和矩阵的压缩的概念与定叉树的定义和结构选题树与二叉树的定义树、森林和二叉树的系结构６二叉树的遍历与线化、森林和二叉树的关夫曼树及其应用系综合析题哈夫曼树及其应选题图的定义和结图的定义与图的结构７的遍小生成扑排序和关键路径短路径综合析题最小生成树拓扑排序关键路径最短路２续章知识题题型易考选择查找的定义顺序查找１．查找基本概念折半查找８２．基于静３．基于综合分题索二引叉顺排序序表树查找４．哈希的查找平衡二叉排序树Ｂ树哈希的解决９①排②交换排③选择排④归并排⑤基数排综合分题各种排序方法的应用３第一 绪~、考试分考重点与难考中常见题复习思路与方数逻、四综１．熟和物；练，结◦构二、考点讲数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。１．基本概·数据（Ｄａｔａ）对客观事物的符号描述，能输入到计算机中并被计算机程序处理的符号的总称；能被计算机识别、和加工处理的信息的载体。字母：ａ～ｚ，单词图、音频信号等表·数据元素（ＤａｔａＥｌｅｍｅｎｔ）数据元素是组成数据的基本单位，是数据集合的，在计算机中通常作为一个整体进行考虑和处理。例，“对弈树”中的一个格４书目信息中的一条书数据项：一个数据元素可由若干个数据项组成例，一条书目信息是由书名、作者名、分类等多个数据项组成的数据项是数据的不可分割的最小单位。例如：有一个学生表如下所示。这个表中的数据元素是学生记录，每个数据元素由四个数据（即学号、姓别、和班号）组成学班１张男８刘女李女陈男王男董男５王女·数据结构（Ｄａｔａ数据结构是指相互之间存在一种或多种特定关系的数据元素集合结构（Ｓｔｒｕｃｔｕｒｅ）：数据元素相互之间的关系。在形式上可用二元组表示：ＤａｔａＳｔｒｕｃｔｕｒｅ＝（Ｄ，Ｄ：数据元素的有限集Ｓ：Ｄ上关系的有限集Ｄ＝｛ｋｉ｜１≤ｎ０ｋｉ示集合Ｄ中的第ｉ个结点或数据元ｎ为Ｄ中结点的个若ｎ＝０，则Ｄ是一个空集，表示Ｄ无结构可言，有时也可以认为它具有任意的结构Ｓ＝｛ｒｊ｜１≤ｍｍ０ｒｊ示集合Ｓ中的第ｊ个二元关系（简称关系ｍ为Ｓ中关系的个若ｍ＝０，则Ｓ是一个空集，表明集合Ｄ中的元结点间不存在任何关系，彼此是独立Ｄ上的一个关系ｒ是序偶的集合，对于ｒ中的任一序偶＜ｘ，ｙ＞（ｘ，ｙＤ），称序偶的第一结点为第二结点的直接前驱结点（通常简称前驱结点），称第二结点为第一结点的直接后继结点（通常简称后继结点）。如在＜ｘ，ｙ＞的序偶中，ｘ为ｙ的前驱结点，而ｙ为ｘ的后继结点。若某个结点没有前驱，则称该结点为开始结点；若某个结点没有后继，则称该结点为终端结点；除此之外的节点称为节点“尖括号”表示有向关系，“圆括号”表示无向关系例如：用二元组表示学生表，学生表有７个结点，依次用ｋ１～ｋ７表示，则对应的二元组表示为：ＤａｔａＳｔｒｕｃｔｕｒｅ＝（Ｄ，Ｓ）其中：Ｄ＝｛ｋ１，ｋ２，ｋ３，ｋ４，ｋ５，ｋ６，ｋ７Ｓ＝｛＜ｋ１，ｋ２＞，＜ｋ２，ｋ３＞，＜ｋ３，ｋ４＞，＜ｋ４，ｋ５＞，＜ｋ５，ｋ６＞，＜ｋ６，ｋ７＞逻辑结构图：可以将数据结构用图形形象地表示出来，图形中的每个结点对应着一个数据元素，两结点之间的连线对应着关系中的一个序偶。上述“学生表”数据结构用下图的图形表示２．数据结构的内逻辑结数据元间的关逻辑结构可看作是从具体问题抽象出来的数学模型按照逻辑关系的不同特性分类：逻辑结构类型的分（１）线性结所谓线性结构，该结构中的结点之间存在一对一的关系其特点是：开始结点和终端结点都是惟一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前驱结点，有且仅有一个后继结点。顺序表就是典型的线性结构（２）非线性结所谓非线性结构，该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。所谓树形结构，该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱６但可以有多个后继，可以有多个终端结点。非线性结构树形结构简称为树ＵＮＩＸ文件系统的系统结构所谓图形结构，该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此，可能没有开始结点和终端结点，也可能有多个开始结点、多个终端结点。图形结构简称为图。结构（物理结构）逻辑结构在计算机中的 映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。顺序结非顺序结构（链式 结构）索引结构散列结例如：用顺序法和链式法表示下面的学生表学班１张男８刘女李女陈男王男董男５王女用顺序法存放学生表的结构体定义为７《《数据结构》考研考点精讲及复习思ｓｔｒｕｃｔＳｔｕｄ／号／／／号／／／／／ ｃｈａｒｎａｍｅ［８］；ｃｈａｒｓｅｘ［２］ｃｈａｒｃｌａｓｓ［４］ Ｓｔｕｄｓ［７］＝｛１，“张斌”，“男”，“９９０１”｝…｛５，＂王萍＂，＂女＂，＂９９０１＂｝结构体数组Ｓｔｕｄｓ各元素在内存中按顺序存放，即第ｉ（１ｉ６个学生对应的元素Ｓｔｕｄｓ［ｉ］存放在第ｉ＋１个学生对应的元素Ｓｔｕｄｓ［ｉ＋１］之前，Ｓｔｕｄｓ［ｉ＋１］正好在Ｓｔｕｄｓ［ｉ］之后。用链式法存放学生表的结构体定义为：ｔｙｐｅｄｅｆｓｔｒｕｃｔｎｏｄｅ｛ｉｎｔ／号／ｃｈａｒｎａｍｅ［８］／／ｃｈａｒｓｅｘ［２］ｃｈａｒｃｌａｓｓ［４］／ 性别／ 指向下ｓｔｒｕｃｔ指向下｝

学生的指针学生表构成的链表如下图所示。其中的ｈｅａｄ为第一个数据元素的指针链式法的缺点·空间占用无法随机８链式法的优点便于修改（、删除、移动）３．算法（１）算法（Ａｌｇｏｒｉｔｈｍ）的定Ａｌｇｏｒｉｔｈｍｉｓａｆｉｎｉｔｅｓｅｔｏｆｒｕｌｅｓｗｈｉｃｈｇｉｖｅｓａｓｅｑｕｅｎｃｅｏｆｏｐｅｒａｔｉｏｎｆｏｒｓｏｌｖｉｎｇａｓｐｅｃｉｆｉｃｔｙｐｅｏｆｐｒｏｂｌｅｍ．（算法是规则的有限集合，是为解决特定问题而规定的一系列操作。）（２）算法的特①有穷性：有限步骤之内正常结束，不能形成无穷循环②确定性：算法中的每一个步骤必须有确定含义，无二义性③可行性：原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成④输入：有多个或０个输入⑤输出：至少有一个或多个输出在算法的五大特性中，最基本的是有限性、确定性和可行性。４．算法描述的工具描述算法的方自然语言：优 简单。缺 有歧异，表达复杂思想不明晰，不能方式很好结高级程序设计语言，如Ｐａｓｃａｌ，Ｃ／Ｃ＋＋，Ｊａｖａ等。优点 克服了自然语言的缺点，可直接执行。缺点 对部分问题的描述比较烦杂， 类语言。和高级程序设计语言类似，但是对其中一些比较烦杂的部分进行和简化（原因：类举法主要目的是为了清晰的表述思想）例：两个数据ａ，ｂ交换空举自然语言：交换ａ，ｂ的空间高级语言：｛ｘ＝ａ；ａ＝ｂ；ｂ＝ｘ；｝类语言：ａｂ；／／交换空间５．对算法作性能评衡量算法效率的方法主要有两大类事后统计：利用计算机的时钟事前分析估算：用高级语言编写的程序运行的时间主要取决于如下因素算法问题规模使用语言：级别越高，效率越低；编译程序；机器通常，从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法执行的时间度量。基本操作重复执行的次数分别为１，ｎ，９设算法的问题规模为频度：语句重复执行的次数称为该语句的频度，记ｆ（ｎ）对算法各基本操作的频度求和，便可得算法的时间复杂度。但实际中所关心的主要是一个算法所花时间的数量级，即取算法各基本操作的最大频度数量级。时间复杂度：算法执行时间度量，记Ｔ（ｎ）＝Ｏ（ａｘｌｅｖｅｌｆ（ｎ）））。ｆ（ｎ）＝１＋ｎ＋ｎ２＋ｎ３Ｔ（ｎ）＝Ｏ（ｎ３）Ｏ的数学定义：若Ｔ（ｎ）和ｆ（ｎ）是定义在正整数集合上的两个函数，则如果存在正常数Ｃ和ｎ得当ｎ≥时，总满足０Ｔｎ）≤Ｃｆｎ），则记做Ｔ（ｎ）＝Ｏ（ｆ（ｎ））也就是只求出Ｔ（ｎ）的最高阶（数量级），忽略其低阶项和常系数，这样既可简化Ｔ（ｎ）的计算，能比较客观地反映出当ｎ很大时，算法的时间性能。６．算法的空间复杂度关于算法的空间需求，类似于算法的时间复杂度，采用空间复杂度作为算法所需空间的量度，记作：Ｓ（ｎ）＝Ｏ（ｆ（ｎ）三、举１．从逻辑结构上可以把数据结构分为（ ）两大类．【交通科技大学】Ａ．动态结构、静态结构Ｂ．顺序结构、链式结Ｃ．线性结构、非线性结构Ｄ．初等结构、构造型结２．在下面的程序段中，对ｘ的赋值语句的频度为（ ）【工商大学】ＦＯＲｉ：＝１ＴＯｎＤＯＦＯＲｊ：＝１ＴＯｎｘ：＝ｘ＋２Ａ．Ｏ（ Ｂ．Ｏ（ Ｃ．Ｏ（ｎ２ Ｄ．Ｏ（ｌｏｇ２３．以下属于逻辑结构的是 ）【西安电子科技大学Ａ．顺序 Ｂ．哈希 Ｃ．有序 Ｄ．单链四、本讲小本章讲解了数据、数据结构、算法的基本概念，数据的逻辑结构和物理结构。重点讲解了数据的４种逻辑结构和４种物理结构，以及算法复杂度。第二 线性分２． 线性表的概念及运算［一般了解２．２ 线性表的顺序［熟练掌握］２． 线性表的链式［熟练掌握第１考重点与难考考重点与难考中常见题复习思路与方线性表的基本概念和常用线性表在常用操作、性表选择题、２．储掌握线性◦操作、线性表的顺序方式◦的顺序◦综合分析题二、考点讲２． 线性表的概念及运１．线性表的定—个线性表是具有ｎ个数据元素的有限序列。２．线性表的长度

记为（ａ１，…，ａｉ－ａｉａｉ，…，ａｎ线性表中元素的个数ｎ（ｎ＞＝０），ｎ＝０时，称为空表

ｉ个元素，称ｉ为数据元素ａｉ性表中的位序４．线性表的逻辑结例子英文字母表（Ａ，Ｂ，…，Ｚ）车辆登记表５．线性表的特同一性：线性表由同类数据元素组成，每一个ａｉ须属于同一数据对象有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数有序性：线性表中相邻数据元间存在着序偶关系＜ａｉ，ａｉ＋１＞。６．线性表的基本运算初始化ＩｎｉｔＬｉｓｔ（Ｌ建立一个空表求表长ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回线性表的长度读表元素ｅｔＥｍＬ，ｉ，ｅ用ｅ返回Ｌ中第ｉ个数据元素的值定位ＬａｅＥｌｅｍＬ，ｅ，ｃｍｅ））返回满足关系的数据元素的位序ＬｉｓｔＩｎｓｅｒｔ（Ｌｉ，ｅ）在Ｌ中第ｉ个位置之前新的数据元素ｅ，线性表的长度增１。删除ＬｉｓｔＤｅｌｅｔｅ（Ｌｉ，＆ｅ）删除Ｌ的第ｉ个位置上的数据元素ｅ，线性表的长度减１输出ＬｉｓｔＤｉｓｐｌａｙ（Ｌ）按前后次序输出线性表的所有元素练习１：两个线性表ＬＡ和ＬＢ分别表示两个集合Ａ和Ｂ，现求一个新的集合Ａ＝∪Ｂ。ｖｏｉｄｕｎｉｏｎ（ＬｉｓｔａＬｉｓｔＬｂ）｛Ｌａｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）；Ｌｂｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）ｆｏｒ（ｉ＝１；ｉ＜＝Ｌｂｌｅｎ；ｉ＋＋）｛ｔＥｍＬｂ，ｉ，ｅ）；ｉｆ（！ａｅＥｍＬａ，ｅ，ｅｑｕａｌ））ＬｉｓｔＩｎｓｅｒｔ（Ｌａ，＋＋Ｌａｌｅｎ，ｅ）；｝｝练习

Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）×ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）两个线性表ＬＡ和ＬＢ中的数据元素按值非递减有序排列，现将ＬＡ和ＬＢ归并为一个新的线性表，ＬＣ中的数据元素仍按值非递减有序排列。ＬＡ＝（３，５，８，ＬＢ＝（２，６，８，９，１１，１５，ＬＣ＝（２，３，５，６，８，８，９，１１，１１，１５，ａ，当ａ!ｂｃｂ，当ａ＞ｂｖｏＭｒｇｅｉｔＬｉｓｔＬａ，ＬｉｓｔＬｂ，Ｌｉｓｔ｛ＩｎｉｔＬｉｓｔ（Ｌｃ）Ｌａｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）； Ｌｂｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）；ｉ＝ｊ＝１；ｋ＝０；ｗｈｉｌｅ（（ｉ＜＝Ｌａｌｅｎ）＆＆（ｊ＜＝Ｌｂｌｅｎ））ｔＥｍＬａ，ｉ，ａ）；ｔＥｍＬｂ，ｊ，ｂ）ｉｆ（ａ＜＝ｂ）｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；＋＋ｉ；｝ｅｌｓｅ｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；＋＋ｊ；｝｝ｗｈｉｌｅ（ｉ＜＝Ｌａｌｅｎ）ｔＥｍＬａ，ｉ＋＋，ａ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；｝ｗｈｉｌｅ（ｊ＜＝Ｌｂｌｅｎ）｛ｔＥｍＬｂ，ｊ＋＋，ｂ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；｝Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）＋ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ））例，Ｌａ＝（３，５，８），Ｌｂ＝（２，６，８，９，１５）构造Ｌｃ＝（２，３，５，６，８，８，９，１５）首先，Ｌａｌｅｎ＝３；Ｌｂｌｅｎ＝５；２．２ 线性表的顺序表示１．顺序表：按顺序方式构造的线性表假设线性表中有ｎ个元素，每个元素占ｋ个单元，第一个元素的地址为ｌｏｃ（ａ），则可以通过如下公式计算出第ｉ个元素的地址ｌｏｃ（ａｉ）：ｌｏｃ（ａｉ）＝ｌｏｃ（ａ１）＋（ｉ－１）×ｋ其中ｌｏｃ（ａ１）称为址。２．顺序表的特点逻辑结构中相邻的数据元素在结构中仍然相邻线性表的顺序结构是一种随机存取的结构。３．顺序表的描述：ｔｙｐｅｄｅｆ｛ＥｌｅｍＴｙｐｅ ／／当前长 ｌｉｓｔｓｉｚｅ；／／分配的容｝／／ＥｌｅｍＴｙｐｅｅｌｅｍ［Ｅｔｙｐｅｄｅｆ＃Ｅｐｅ ＃为根据具体问题确定的数据类型ｔｙｐｅｄｅｆｉｎｔ ４．顺序表上基本运算的实初始化ＳｔａｔｕｓＩｎｉｔＬｉｓｔＳｑ（ＳｑＬｉｓｔ｛Ｌ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ａｌｃ（ＬＩＳＴＩＮＩＴＳＩＺＥｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））；ｉｆ（！Ｌ．ｅｘｉｔ（ＯＥＬＷ；Ｌ．ｌｅｎｇｔｈ＝０；Ｌ．ｌｉｓｔｓｉｚｅ＝ＬＩＳＴＩＮＩＴｒｅｔｕｒｎ｝Ｌ．ｅｌｅｍ＝ｎｅｗＥｌｅｍＴｙｐｅ［ＬＩＳＴＩＮＩＴＳＩＺＥ］顺序表的：在表中第４个元前“２１“顺序表中元ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔＳｑ（ＳｑＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅｅ）｛ｉｆ（（ｉ＜１）｜｜（ｉ＞Ｌ．ｌｅｎｇｔｈ＋１））ｒｅｔｕｒｎＥＲＲＯＲ；ｉｆ（Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ）｛ｒｅａｌｌｏｃ（…）；…．；／／越界处理；｝ｑ＝＆（Ｌ．ｅｌｅｍ［ｉ－１］）ｆｏｒ（ｐ＝＆（Ｌ．ｅｌｅｍ［Ｌ．ｌｅｎｇｔｈ－１］；ｐ＞＝ｑ；－－（ｐ＋１）＝ｐ；ｑ＝ｅ；＋＋Ｌ．ｌｅｎｇｔｈ；ｎ｝／／越界处ｉｆ（Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ ｎｅｗｂａｓｅ＝（ＥｌｅｍＴｙｐｅ）ｒｅａｌｌｏｃ（Ｌ．ｅｌｅｍ（Ｌ．ｌｉｓｔｓｉｚｅ＋ＬＩＳＴＩＮＣＲＥＭＥＮＴ）ｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））ｉｆ（！ｎｅｗｂａｓｅ） ｅｘｉｔ（ＯＶＥＬＷ；Ｌ．ｅｌｅｍ＝ｎｅｗｂａｓｅ；Ｌ．ｌｉｓｔｓｉｚｅ＋＝ＬＩＳＴＩＮＣＲＥＭＥＮＴ；算法时间复杂度：时间主要花在移动元素上，而移动元素的个数取决于元素位置。ｉ＝１，需移动ｎ个元素；ｉ＝ｎ＋１，需移动０个元素ｉ＝ｉ，需移动ｎ－ｉ＋１个元素假设ｐｉ是在第ｉ个元前一个新元素的概则长度为ｎ的线性表 一个元素所需移动元素次数的期望Ｅｉｓ＝∑ｐｉ（ｎ－ｉ＋１）ｉ设在任何位置元素等概率，ｎ

＝ｎ＋１ ｎ＋１（ｎ－ｉ＋１）ｉ ｎ＋ｉ

Ｏ（顺序表的归并，表中元素非递减排列ｖｉｄＭｅｒｇｓＳｑ（ＳｑＬｉｓｔＬａ，ＳｑＬｉｓｔＬｂ，ＳｑＬｉｓｔｃ｛ｐａ＝Ｌａ．ｅｌｅｍ；ｐｂ＝Ｌｂ．Ｌｃ．ｌｉｓｔｓｉｚｅ＝Ｌｃ．ｌｅｎｇｔｈ＝Ｌａ．ｌｅｎｇｔｈ＋Ｌｂ．ｌｅｎｇｔｈ；ｐｃ＝Ｌｃ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ｌｃ…）；ｉｆ（！Ｌｃ．ｅｌｅｍ）ｅｘｉｔ（ＯＶＬＷ；ｐａｌａｓｔ＝Ｌａ．ｅｌｅｍ＋Ｌａ．ｌｅｎｇｔｈ－１；ｐｂｌａｓｔ＝Ｌｂ．ｅｌｅｍ＋Ｌｂ．ｌｅｎｇｔｈ－１；ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆ｐｂ＜＝ｐｂｌａｓｔ））｛ｉｆ（ｐａ＜＝ｐｂ） ｐｃ＋＋＝ｐａ＋＋；ｅｌｓｅｐｃ＋＋＝ ｐｂ＋＋；｝ｗｈｉｌｅ（ｐａ＜＝ｐａｌａｓｔ）ｐｃ＋＋＝ｐａ＋＋；ｗｈｉｌｅ（ｐｂ＜＝ｐｂｌａｓｔ） ｐｃ＋＋＝ｐｂ＋＋；｝顺序表的基础要点１．无需为表示元素间的逻辑关系而增加额外的空间，密度大（１００％）；２．可随机存取表中的任一元素。３．或删除一个元素时，需平均移动表的一半元素，具体的个数与该元素的位置有关，在等概率情况下，ｎ／２，删除（ｎ－１）／２；Ｏ（ｎ）４．分配只能预先进行分配５．将两个各有ｎ个元素的有序表归并为一个有序表，其最少的比较次数是：ｎ练习２．２９已知Ａ、Ｂ、Ｃ为三个元素值递增有序的顺序表，现要求对Ａ作如下运算，删去那些既在Ｂ中出现又在Ｃ中出现的元素，实现上述算法并分析时间复杂度。Ａ＝Ａ－（Ａ＝（１，２，６，６，８，９，１０，１０，１１，１５）Ｂ＝（１，２，６，６，７，９，１０，１５）Ｃ＝（３，４，６，７，７，９，９，９，１０，Ａ＝（１，２，８，１１，１５）分析：先从Ｂ和Ｃ中找出公有元素，记为ｅＡ中从当前位置开始，凡小于ｓａｍｅ的元素均保留（存到新的位置），等于ｓａｍｅ的跳过大于ｓａｍｅ时就再找下一个ｖｏｉｄＳｑＬｉｓｔＩｎｔｅｒｓｅｃｔＤｅｌｅｔｅ（ＳｑＬｉｓｔＡＳｑＬｉｓｔＢ，ＳｑＬｉｓｔ ｐａ＝Ａ．ｅｌｅｍ；ｐａｌａｓｔ；ｐｂ；ｐｂｌａｓｔ；ｐｃ；ｐｃｌａｓｔ；ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆（ｐｂ＜＝ｐｂｌａｓｔ）＆＆（ｐｃ＜＝ｐｃｌａｓｔ））｛ｉｆ（ｐｂ＜ｐｃ） ｐｂ＋＋；ｅｌｓｅ｛

ｐｃ＋＋ｓａｍｅ＝ｗｈｉｌｅ（（ｐｂ＜＝ｐｂｌａｓｔ）ｗｈｉｌｅ（（ｐｃ＜＝ｐｃ

＆＆（ｐｂ＝＝ａｅ＆＆（ｐｃ＝＝ｍｅ

ｐｂ＋＋；ｐｃ＋＋ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆（ｐａ＜ｍｅ）ｐ０＋＋＝ ｐａ＋＋；｝／／

ｗｈｉｌｅ（（ｐａ＜＝ｐａ

＆＆（ｐａ＝＝ａｅ ｐａ＋＋｝／／ｗｈｉｌｅ（ｐａ＜＝ｐａｐ０＋＋＝ Ａ．ｌｅｎｇｔｈ＝ｐ０"Ａ．ｅｌｅｍ；｝三、举１．下面关于线性表的叙述中，错误的是哪一个？（ ）【北方交通大学】Ａ．线性表采用顺序，必须占用一片连续的单元。Ｂ．线性表采用顺序，便于进行和删除操作Ｃ．线性表采用，不必占用一片连续的单元。Ｄ．线性表采用，便于和删除操作。２．若长度为ｎ的线性表采用顺序结构，在其第ｉ个位置一个新元素的算法的时间复杂为 ）（１＜＝ｉ＜＝ｎ＋１）。【航空航天大学Ａ．Ｏ（ Ｂ．Ｏ（ Ｃ．Ｏ（ Ｄ．Ｏ（ｎ２四、本讲小本讲主要讲解了：线性表的基本概念和常用操作、线性表的顺序方式。常考题型：选择题，综合分析题。应试方法：理解并熟练掌握线性表的顺序方式和线性表的基本运算在现行方式下在实现方法。第２~、考试分考重点与难考试中常见题复习思路与方线性表的链式结构◦综◦式存二、考点讲２．３ 线性表的链式表示线性表链式结构的特点：用一组任意的单元线性表的元素，不要求逻辑上相邻的元素在物理位置上也相邻删除时不需移动大量元素；失去顺序表可随机存取的优点。例，整数数组ａ［３］＝｛３，５，６｝１．线性链表（单链表结点：数据元素的映象数据域用来结点的值指针域用来数据元素的直接后继的地址（或位置）头指指示链表中第一个结点的位置，单链表可由头指针唯一确定单链表的映头结在链表的第一个结点之前附设一个结点，头指针指向头结点。设置头结点的目的是空表与非空表的操作，简化链表操作的实现。首元结链表中线性表中第一个数据元素的结点链表结构描述：ＴｙｐｅｄｅｆｓｔｒｕｃｔＬＮｏｄｅ｛ＥｌｅｍＴｙｐｅｓｔｒｕｃｔ 单链表基本运算实现（１）初始化线性表ＩｎｉｔＬｉｓｔ（该运算建立一个空的单链表，即创建一个头结点。ｖｏｉｄＩｎｉｔＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）｛Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））创／创／Ｌ－＞ｎｅｘｔ＝｝

建头结（２）销毁线性表ＤｅｓｔｒｏｙＬｉｓｔ（单链表Ｌ占用的内存空间。即逐一全部结点的空间。《《数据结构》考研考点精讲及复习思ｖｏｉｄＤｅｓｔｒｏｙＬｉｓｔ（ＬｉｎｋＬｉｓｔ｛ＬｉｎｋＬｉｓｔｐ＝Ｌ，ｑ＝ｐ－＞ｎｅｘｔ；ｗｈｉｌｅ（ｑ！＝ＮＵＬＬ） ｆｒｅｅ（ｐ）ｐ＝ｑ；ｑ＝ｐ－＞｝ｆｒｅｅ（ｐ）｝（３）判线性表是否为空表ＬｉｓｔＥｍｐｔｙ（若单链表Ｌ没有数据结点，则返回真，否则返回假。ｉｎｔＬｉｓｔＥｍｐｔｙ（ＬｉｎｋＬｉｓｔＬ）｛ｒｅｔｕｒｎ（Ｌ－＞ｎｅｘｔ＝＝ＮＵＬＬ）｝（４）求线性表的长度ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回单链表Ｌ中数据结点的个数。ｉｎｔＬｉｓｔＬｅｎｇｔｈ（ＬｉｎｋＬｉｓｔＬ）｛ＬｉｎｋＬｉｓｔｐ＝Ｌ；ｉｎｔｉ＝０；ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ！＝ＮＵＬＬ）｛ｉ＋＋ｐ＝ｐ－＞｝ｒｅｔｕｒｎ（ｉ）｝（５）输出线性表ＤｉｓｐＬｉｓｔ（逐一扫描单链表Ｌ的每个数据结点，并显示各结点的ｄａｔａ域值。ｖｏｉｄＤｉｓｐＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；ｗｈｉｌｅ（ｐ！＝ＮＵＬＬ） ｐｒｉｎｔｆ（＂％ｃ＂，ｐ－＞ｄａｔａ）；ｐ＝ｐ－＞ｎｅｘｔ；｝ｐｒｉｎｔｆ（＂＼ｎ＂）｝（６）取表元ＳｔａｔｕｓｔＥｍＬｉｎｋＬｉｓｔＬ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ－＞ｎｅｘｔ；ｊ＝１；ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋｝ｉｆ（！ｐ｜｜ｊ＞ｉ）ｒｅｔｕｒｎＥＲＲＯＲ；ｅ＝ｐ－＞ｄａｔａ；ｒｅｔｕｒｎ｝例，取第ｉ＝３个元素ｅ＝ｐ－＞ｄａｔａ＝Ｓｕｎ时间复杂度：Ｏ（ｎ）·在单链表第ｉ个结点前一个结点的过（７）ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（！ｐ｜｜ｊ＞ｉ－１） ｒｅｔｕｒｎＥＲＲＯＲ；ｓ＝ （ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓ－＞ｄａｔａ＝ｅ；ｓ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｓ；ｒｅｔｕｒｎ｝·删除单链表的第ｉ个结点的过（８）删ＳｔａｔｕｓＬｉｓｔＤｅｌｅｔｅ（ＬｉｎｋＬｉｓｔＬｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（！（ｐ－＞ｎｅｘｔ）｜｜ｊ＞ｉ－１）ｒｅｔｕｒｎＥＲＲＯＲ；ｒ＝ｐ－＞ｎｅｘｔ；ｅ＝ｒ－＞ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－ｎｅｘｔ；／／（ｐ－＞ｎｅｘｔ＝ｒ－＞ｎｅｘｔ；）ｆｒｅｅ（ｒ）；ｒｅｔｕｒｎＯＫ；｝·动态建立单链表的过（９）头插法建ＣｒｅａｔｅＬｉｓｔＨ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｓ；｝｝·法建（１０）法建ＣｒｅａｔｅＬｉｓｔＴ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛ｔａｉｌ＝Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝ＮＵＬＬ；ｔａｉｌ－＞ｎｅｘｔ＝ｓ；①ｔａｉｌ＝ｓ；｝｝（１１）按元素值查找ａｔｅＥｍＬ，思路：在单链表Ｌ中从头开始找第１个值域与ｅ相等的结点，若存在这样的结点，则返回位置，否则返回０。ｉｎｔｏａｅＥｍＬｉｎｋＬｉｓｔＬ，ＥｌｅｍＴｙｐｅ｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；ｉｎｔｎ＝１；ｗｈｉｌｅ（ｐ！＝ＮＵＬＬ＆＆ｐ－＞ｄａｔａ！＝ ｐ＝ｐ－＞ｎｅｘｔ；ｎ＋＋； ｉｆ（ｐ＝＝ＮＵＬＬ） ｒｅｔｕｒｎ（０）；ｅｌｓｅｒｅｔｕｒｎ（ｎ）｝练习：已知Ｌ是结点的非空单链表，指针ｐ所指的结点既不是第一个结点，也不是最后一个结点。删除 ｐ结点的直接后继结点的语句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；删除 ｐ结点的直接前驱结点的语句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ－＞ｎｅｘｔ！＝ｐ） ｑ＝ｑ－＞ｎｅｘｔ；ｓ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｓ）；删除 ｐ结点的语句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ！＝ｐ） ｑ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｆｒｅｅ（ｐ）删除首元结点的语句序列ｑ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；删除最后一个结点的语句序ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ！＝ＮＵＬＬ） ｐ＝ｐ－＞ｎｅｘｔ；ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｒｅｅ（ｑ）；链式结构的特点非随机存贮结构，所以取表元素要慢于顺序表。节约了大块内存适合于和删除操实际上用空间换取了时间，结点中加入了指针，使得这两种操作转换为指针操作；２．静态链表有些高级程序设计语言并没有指针类型，如ＦＯＲＴＲＡＮ和ＪＡＶＡ。可以用数组来表示一个链表，称为静态链表。可定义如下＃ｄｅｆｉｎｅＭＡＸＳＩＺＥ ／／最多元素个数ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＥｌｅｍＴｙｐｅ ｃｕｒ；／／游标，指示｝ｐｅｎｔＳＬｉｎｋＬｉｓｔ［ＸＥｉ＝ｓ［ｉ］．ｃｕｒ；指针后移操ｌｃｉ＝ｓ［０］．ｃｕｒ；第一个可用结点位ｉｆ（ｓ［０］． ｓ［０］．ｃｕｒ＝ｓ［ｉ］． ／／ｋ结ｓ［ｋ］．ｃｕｒ＝ｓ［０］．ｃｕｒ；［０］．ｃｕｒ＝Ｉｎｓｅｒｔ：／／将ｉ插在ｒ之ｓ［ｉ］．ｃｕｒ＝ｓ［ｒ］．ｃｕｒ；ｓ［ｒ］．ｃｕｒ＝ｉ；Ｄｅｌｅｔｅ：；／／ｐ为ｋ的直接前驱，ｓ［ｐ］．ｃｕｒ＝ｓ［ｋ］．ｃｕｒＦｒｅｅ（ｋ）；单链表基础要点在单链表中，不能从当前结点出发到任一结点在单链表中，删除某一指定结点时，必须找到该结点的前驱结点线性表的链式结构是一种顺序存取的结构，不具有随机任一元素的特点设置头结点的作用：使在链表的第一个位置上的操作和表中其它位置上的操作—致，无需进行特殊处理，对空表和非空表的处理。循环链表循环链表是另一种形式的链式结构可从当前结点出发，到任一结点循环单链表多重循环链表。单循环链表设置尾指针ｒｅａｒ，比设头指针更好连接两个只设尾指针的单循环链表Ｌ１和Ｌ２操作如下：ｐ＝Ｒ１"＞ｎｅｘｔ；／／保存Ｌ１的头结点指针Ｒ１－＞ｎｅｘｔ＝Ｒ２－＞ｎｅｘｔ－＞ｎｅｘｔ；／／头尾连接ｆｒｅｅ（Ｒ２－＞ｎｅｘｔ）；／／第二个表的头结Ｒ２－＞ｎｅｘｔ＝操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是ｐ是否为空，而是ｐ是否等于头指针。例：取循环链表第ｉ个元素ＳｔａｔｕｓＧｅｔＥｌｅｍＬ（ ＆ｅ ｐ＝Ｌ－＞ｎｅｘｔ；ｊ＝１ｗｈｉｌｅ（ｐ！＝Ｌ＆＆ ｊ＜ｉ） ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ；｝ｉｆ（ｐ＝＝Ｌ｜｜ｊ＞ｉ）ｒｅｔｕｒｎＥＲＲＯＲ；ｅ＝ｐ－＞ｄａｔａ；ｒｅｔｕｒｎ｝双链表希望查找前驱的时间复杂度达到Ｏ（１），可以用空间换时间，每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为双向链表。结点的结构图双向链表的逻辑表示双向链表（ＤｏｕｂｌｅＬｉｎｋｅｄＬｉｓｔ）类型描述ｔｙｐｅｄｅｆｓｔｒｕｃｔｓｔｒｕｃｔＤｕＬＮｏｄｅ

ｓｔｒｕｃｔ ｝ 双向循环链ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞·双向链表的前（后 操①ｓ－＞ｐｒｉｏｒ＝ｐ－＞ ②ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝③ｓ－＞ｎｅｘｔ＝ ④ｐ－＞ｐｒｉｏｒ＝①ｓ－＞ｎｅｘｔ＝ｑ－＞ ②ｑ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝③ｓ－＞ｐｒｉｏｒ＝ ④ｑ－＞ｎｅｘｔ＝双向链表的删除操①ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ－＞②ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞删除 ｐ的直接后继结点的语句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ；ｆｒｅｅ（ｑ）删除 ｐ的直接前驱结点的语句序列ｑ＝ｐ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｑ）《《数据结构》考研考点精讲及复习思ｒｅｔｕｒｎ｝②找结点的中序后继结结点ｐ，无右孩子，右指针指向其后继，否则ｐ的右子树中“最左下”结点。ＢｉＴｈｒＴｒｅｅＰｏｓｔＮｏｄｅ（ＢｉＴｈｒＴｒｅｅｐ）｛ｐｏｓｔ＝ｐ－＞ｉｆ（ｐ－＞ＲＴａｇ＝＝０）／／有右孩子ｗｈｉｌｅ（ｐｏｓｔ－＞ＬＴａｇ＝＝０）ｐｏｓｔ＝ｐｏｓｔ－＞ｌｃｈｉｌｄ；ｒｅｔｕｒｎ｝结点的线索二叉链表结点的中序线索二叉链表中序遍历线索二叉树 ／／０：有孩子；１：无孩子ＶｏｉｄＩｎＯｒｄｅｒＴｒａｖｅｒｓｅＴｈｒ（ＢｉＴｈｒＴｒｅｅ ｛ｐ＝Ｔ－＞ｌｃｈｉｌｄ；ｗｈｉｌｅ（ｐ！＝Ｔ）ｗｈｉｌｅ（ｐ－＞ＬＴａｇ＝＝０）ｐ＝ｐ－＞ｌｃｈｉｌｄ；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；ｗｈｉｌｅ（（ｐ－＞ＲＴａｇ＝＝１）＆＆（ｐ－＞ｒｃｈｉｌｄ！＝Ｔ） ｐ＝ｐ－＞ｒｃｈｉｌｄ；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；｝ｐ＝ｐ－＞｝｝建立线索化链表（以中序为例按某种次序将二叉链表线索化，实质是在遍历过程中用线索取代空指针对线索树进行遍历，显然其效率要比传统方式高些。如果程序中经常要进行二叉树的遍历或者需要查找在遍历过程中所的线性序列中前驱和后继，此时应当采用线索链表表示。６． 树和森１．树的结构（三种方法双亲表示法：用一组连续的空间来树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下：树的双亲结构示意＃ｄｅｆｉｎｅＭＡＸＴＲＥＥＳＩＺＥ１００ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛ＴＥｌｅｍ ｝ＰＴＮｏｄｅ；Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＰＴＮｏｄｅｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］ ｒ， ／／根的位置和结点｝双亲表示法的类型说明孩子表示法①定长结点长空链域个数：ｎｋ"（ｎ）＝ｎ（ｋ－１）＋②把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。ｎ个结点共有ｎ个孩子链表（叶子结点的孩子链表为空表），而ｎ个结点的数据和ｎ个孩子链表的头指针又组成一个顺序表ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＴＮｏｄｅ｛／孩子结点的定义 ｓｔｒｕｃｔＣＴＮｏｄｅ｝

该孩子结点性表中的位置／ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＴＥｌｅｍＴｙｐｅｄａｔａ；

／顺序表结点的结构定 指 结点的信息指 ＦｉｒｓｔＣｈｉｌｄ；｝

向孩子链表的头指 树ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ 的定 树顺 ｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］； 序 顺根ｉｎｔｒｏｏｔ，ｎｕｍ；根／｝结孩子兄弟表示法ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＳＮｏｄｅ｛ＥｌｅｍＴｙｐｅｄａｔａ； 结

结点的位置和树的结点个数第点信 第ＳｔｒｕｃｔＣＳＮｏｄｅＦｉｒｓｔＣｈｉｌｄ，ＮｅｘｔＳｉｂｌｉｎｇ；｝

—个孩子，下一个兄弟树树的孩子兄弟结构示意２．树、森林与二叉树的相互转·树转换为二叉（１）在所有相邻兄弟结点之间加一水平连线（２）对每个非叶结点ｋ，除了其最左边的孩子结点外，删去ｋ与其他孩子结点的连线（３）所有水平线段以左边结点为顺时针旋转４５度，使之结构层次分明。树做这样的转换所构成的二叉树是唯一的。树与二叉树的对·森林转换为二叉森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下（１）将森林中的每棵树转换成相应的二叉树（２）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。·二叉树还原为树或森将一棵二叉树还原为树或森林，具体方法如下《《数据结构》考研考点精讲及复习思（１）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。（２）删掉原二叉树中所有双亲结点与右孩子结点的连线（３）整理由（１）、（２）两步所得到的树或森林，使之结构层次分明二叉树到森林的转换示３．树与森林的遍·树的遍历（两种１）先根遍若树非空，则遍历方法为①根结点②从左到右，依次先根遍历根结点的每一棵子树。等同于转换的二叉树进行先序遍历先根遍历序列ＡＢＥＣＦＨＧＤ２）后根遍历若树非空，则遍历方法为①从左到右，依次后根遍历根结点的每一棵子树②根结点等同于转换的二叉树进行中序遍历后根遍历序列为ＥＢＨＦＧＣＤＡ·森林的遍历（２种１）中序遍若森林非空，则遍历方法为①森林中第一棵树的根结点②先序遍历第一棵树的根结点的子树森林③先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历序列为ＡＢＣＤＥＦＧＨＩＪ等同于转换的二叉树进行先序遍历２）先序遍历若森林非空，则遍历方法为①中序遍历森林中第一棵树的根结点的子树森林②第一棵树的根结点③中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历序列为 等同于转换的二叉树进行中序遍历４．几个问题①给定树的先根遍历序列和后根遍历序列可唯一画出一棵树。先根遍历序列：ＡＢＥＣＦＨＧＤ后根遍历序列：ＥＢＨＦＧＣＤ②给定森林的先序遍历序列和中序遍历序列可唯一确定一森林。先序遍历序列：ＡＢＣＤＥＦＧＨＩＪ中序遍历序列：ＢＣＤＡＦＥＨＪＩ③关于二叉树的先序、中序和后序遍历序列确定二叉树的问题·任何ｎ（ｎ０个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定证明先序序列是ａ１ａ２…ａｎ中序序列是ｂ１ｂ２…ｂｎ根结点：ａ在中序序列中与ａ同的结点为：ｂｊ｛ｂ１…ｂｊ－１｝ｂｊ｛ｂｊ＋１…ｂｎ｝←→ａ１｛ａ２…ａｋ｝｛ａｋ＋１…ａｎ例已知先序序列为ＡＢＤＧＣＥＦ，中序序列为·任何ｎ（ｎ＞０）个不同结点的二叉树，都可由它的中序序列和后序序列唯一地确定。证明：后序序列是ａ１ａ２…ａｎ中序序列是ｂ１ｂ２…ｂｎ根结点：ａｎ在中序序列中与ａｎ同的结点为：ｂｊ｛ｂ１…ｂｊ－１｝ｂｊ｛ｂｊ＋１…ｂｎ｝←→ａ１ａ２…ａｋ｝｛ａｋ＋１…ａｎ－１｝ａｎ例后序序列为ＧＤＢＥＦＣＡ，中序序列为ＤＧＢＡＥＣＦ６．５树与等价问离散数学中的定等价关系：若集合Ｓ中的关系Ｒ是自反的、对称的和传递的，则称为等价关系等价类：Ｒ是集合Ｓ的等价关系，由［ｘ］Ｒ＝｛ｙ｜ｙ∈Ｓ∧ｙ给出的集合［ｘ］Ｒ称为由ｘ生成的一个Ｒ等价类。划分：Ｒ是Ｓ上的等价关系，可以按Ｒ将Ｓ划分为若干不相交的子集……，它们的并即为Ｓ，则这些子集Ｓｉ是Ｓ的Ｒ等价类。如何划分等价类假设集合Ｓ有ｎ个元素，ｍ个形如（ｘ，ｙ）的等价偶对确定了等价关系Ｒ，求Ｓ的划分。一种算法：１）令Ｓ中每个元素各自形成一个只含单个成员的子集，记为…，Ｓｎ２）重复读入ｍ个偶对，对每个偶对（ｘ，ｙ），判断ｘ和ｙ所属的子集，设ｘ∈Ｓ，ｙ∈Ｓ，若ＳｉＳ，则将Ｓｊ入Ｓｉ并置Ｓｊ空。处理完ｍ个偶对后剩下的非空子集就是Ｓ的Ｒ等价类。划分等价类需要的操作：１）构造只含单个元素的集合２）判定某个元素所属集合３）合并两个互不相交的集ＦＳｔ若Ｓ是ＦＳｅ类型的集合，则它由子集Ｓｉ构成，∪…Ｓ＝Ｓ。基本操作：Ｉｎｉｔｉａｌ（＆Ｓ，ｎ，ｘ１，ｘ…，ｘｎ）：构造由ｎ个子集构成的集合Ｓ，每个子集只含单个元素。Ｆｉｎｄ（Ｓ，ｘ）：查找ｘ所属的子集Ｓｉｅｅ＆Ｓ，ｉ，ｊ）：合并两个不相交的集合ＳｉＳｊｅ类型的实现根据Ｆｉｎｄ和Ｍｅｒｇｅ两个操作的特点，用树来实现Ｓｅｔ以森林Ｆ＝（…，Ｔｎ）表示Ｓｅ类型的集合Ｓ，每颗树Ｔｉ示一个子集Ｓｉ树中每个结点表示子集中的一个成员ｘ令每个结点中包含一个指向其双亲的指针约定根结点兼作子集的名称集合的合并将一棵树的根指向另一颗树的根＃ｄｅｆｉｎｅＭＡＸＴＲＥＥＳＩＺＥ１００ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛ＴＥｌ ｝ＰＴＮｏｄｅ；Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＰＴＮｏｄｅｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］；ｉｎｔｒ，ｎ； ／／根的位置和结点数｝ＴｙｐｅｄｅｆＰＴｒｅｅＳｔｉｎｔｆｉｎｄｍｆｓｅｔ（ＭＦＳｅｔＳ，ｉｎｔ｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］． ｒｅｔｕｒｎ｝Ｓｔａｔｕｓｍｅｒｇｅｍｆｓｅｔ（ＭＦＳｅｔＳｉｎｔｉ，ｉｎｔ｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎＥＲＲＯＲ；Ｓ．ｎｏｄｅ［ｉ］．ｐａｒｅｎｔ＝ｊ；ｒｅｔｕｒｎ｝时间复杂度分别为Ｏ（ｄ）和Ｏ（１），ｄ为树的深（７）掌握线索二叉树的概念和相关算法的实现（８）掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法（９）灵活运用二叉树这种数据结构解决一些综合应用问题二、举１．已知一棵二叉树的前序遍历结果为ＡＢＣＤＥＦ，中序遍历结果为ＣＢＡＥＤＦ，则后序遍历的结果 ）【浙江大学Ａ． Ｂ． Ｃ． Ｄ．不２．已知某二叉树的后序遍历序列是ｄａｂｅｃ，中序遍历序列是ｄｅｂａｃ，它的前序遍历是（ 大学】Ａ． Ｂ． Ｃ． Ｄ．３．一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（ ）【合肥工业大学】Ａ．不确定 Ｂ．０ Ｃ．１ Ｄ．２４．若Ｘ是二叉中序线索树中一个有左孩子的结点，且Ｘ不为根，则Ｘ的前驱为（ 大学】Ａ．Ｘ的双 Ｂ．Ｘ的右子树中最左的结Ｃ．Ｘ的左子树中最右结 Ｄ．Ｘ的左子树中最右叶节５．设Ｆ是一个森林，Ｂ是由Ｆ变换得的二叉树。若Ｆ中有ｎ个非终端结点，则Ｂ中右指针域为空的结点有（ ）个。【西安电子科技大学】Ａ．ｎ－ Ｂ． Ｃ．ｎ＋ Ｄ．ｎ＋三、本讲小线索二叉树的概念和相关算法的实现。树、森林与二叉树的关系树的简单应第３~、考点讲情况：改进方法Ｍｅｒｇｅ时，总是将成员少的子集根结点指向含成员多的子集的修改结构，令根结点的ｐａｒｅｎｔ域子集中所含成员数目的负可以将ｆｉｎｄｍｆｓｅｔ的复杂度降到Ｏ（ｌｏｇｎ）Ｓｔａｔｕｓｍｉｘｍｆｓｅｔ（ｅＳｉｎｔｉ，ｉｎｔｊ）｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎｉｆ（Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＞Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ）｛Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ；Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＝｝Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＝ｉ；｝ｒｅｔｕｒｎ｝进一步的改进：Ｆｉｎｄ时压缩路当所查元素不在第二层时，将所有从根到该元素路径上的元素都变成根结点的孩子ｉｎｔｆｉｘｍｆｓｅｔ（ＭＦＳｅｔＳｉｎｔｉ）｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］．ｐａｒｅｎｔ） ｆｏｒ（ｋ＝ｉ；ｋ！ ＝ｊ；ｋ＝ｔ）｛ｔ＝Ｓ．ｎｏｄｅｓ［ｋ］． Ｓ．ｎｏｄｅｓ［ｋ］．ｐａｒｅｎｔ＝｝ｒｅｔｕｒｎ｝６．６ 哈夫曼树及其应用１．哈夫曼树①路径长从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。②树的路径长从树根到每一结点的路径长度之和③结点的权和带权路径长给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。在树形结构中，把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。④树的带权路径长度ＷＰＬ（ＷｅｉｇｈｔＰａｔｈＬｅｎｇｔｈｏｆＴｒｅｅ）树中所有叶子结点的带权路径长度之和，通常记为：ｗｎ∑ＷＰＬｗｎ∑ｋ１ｋＬａ）＝７×２＋５×２＋２×２＋４×２＝３６Ｌｂ）＝４×２＋７×３＋５×３＋２×１＝４６Ｌｃ）＝７×１＋５×２＋２×３＋４×３＝３５⑤哈夫曼树（最优二叉树设二叉树具有ｎ个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和，叫做二叉树的带权路径长度。具有最小带权路径长度的二叉树称为哈夫曼树２．构造哈夫曼树（哈夫曼算法１）由给定的ｎ个权值｛．．．，Ｗｎ｝，构造ｎ棵只有一个叶子结点的二叉树，从而得到一个二２）在Ｆ中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；３）在集合Ｆ中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合Ｆ中；４）重复（２）、（３）两步，当Ｆ中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。给定权值ｗ＝（１，３，５，７）来构造一棵哈夫曼树３．哈夫曼编码１）编码例，传送ＡＢＡＣＣＤ，四种字符，可以分别编码为００，０１，１０，１１。则原电文转换为０００１００１０１０１１。对方接收后，采用二位一分进行译码当然，为电文编码时，总是希望总长越短越好如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符