VFP二级笔试考试课件

第1章 数据结构与算法（13%）重要考点提示：1） 算法复杂度。2） 栈、队列、线性链表的基本概念3） 二叉树的存储结构4） 线性表、树的结点计算和遍历5） 冒泡排序的最坏次数计算 一、算法考点1 算法的基本概念 记一些概念即可1、算法：对解题方案的准确而完整的描述。重点2、算法的基本特征 重点可行性 针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须考虑它的可行性，否则将得不到满意的结果。确定性 算法的确定性是指算法中的每一个步骤必须有明确的定义，不能产生歧义。这一性质也反映了算法与数学公式的明显差别。有穷性 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还包括合理的执行时间的含义，因为如果一个算法需要执行千万年，显然失去了价值。拥有足够的情报 一个算法是否有效，还取决为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。有的认为是：可行性、确定性、有穷性、有输入、有输出。3、算法的基本要素 重点算法中对数据的运算和操作算法的控制结构可理解为：一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。即：算法 = 控制结构 + 原操作 （固有数据类型的操作解释：了解算法中对数据的运算和操作每个算法实际上是按解题要求，从环境能进行的操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作以指令形式来描述，所有指令的集合构成计算机指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算、数据传输（如输入输出、赋值等）。计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时，通常要考虑很多与方法和分析无关的细节问题（如语法规则），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法，而是用别的描述工具（如流程图，专门的算法描述语言、自然语言）来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的控制结构一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各个操作间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择（或称分支）、循环（也称重复）3种基本控制结构组合而成。4、算法设计的基本方法 列举法归纳法递推递归减半递推技术回溯法*考点2 算法的复杂度 重点算法的复杂度主要包括：时间复杂度和空间复杂度。重点1、算法的时间复杂度 重点算法的时间复杂度：是指执行算法所需要的计算工作量。解释： 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。因此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。 算法的工作量基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。如：在考虑两个矩阵相乘时，要以将两个实数之间的乘法运算作为基本运算，而对于所用的加、减法运算可以忽略不计。如：当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。算法所执行的基本运算次数还与问题的规模有关。如：两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者所需要的运算次数更多。时间复杂度为: n3因此，在分析算法的工作量时，还必须对问题的规模进行度量。综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量=O(n)其中，n是问题的规模。例如：两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为O(n3)。在具体分析一个算法工作量时，还会存在这样的问题：对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有情况下算法所执行的基本运算次数都列出来。如：在长度为n的一维数组中查找值为x的元素。查找6，25，9621028-302325若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较。显然，如果第一个元素恰好为x，则只需要比较1次。但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。因此，在这个问题的算法中，其基本运算（即比较）的次数与具体的被查值x有关。在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：平均性态 重点，记名词及概念即可平均性态：用各种特定输入下的基本运算次数的加权平均值来度量算法的工作。了解设x是所有可能输入中的某个特定输入，p(x)是x出现的概率（即输入为x的概率），t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：A(n)=其中Dn表示当规模为n时，算法执行时所有可能输入的集合。这个式子中的t(x)可以通过分析算法来加以确定；而p(x)必须由经验或用算法中有关的一些特定信息来确定，通常是不能解析地加以计算的。如果确定p(x)比较困难，则会给平均性态的分析带来困难。最坏情况复杂性 重点最坏情况复杂性：在规模为n时，算法所执行的基本运算的最大次数。它的定义为：W(n)=显然，W(n)的计算要比A(n)的计算方便得多。由于W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。例：采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。解：平均性态分析。略 最坏情况分析。在这个例子中，最坏情况发生在需要查找的x是数组中的最后一个元素或x不在数组中的时候，此时，显然有：W(n)=maxti | 1in+1=n2、算法的空间复杂度 重点算法的空间复杂度：是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中，额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间相对于问题规模来说是常数，则称该算法是原地（in place）工作的。在许多问题中，为了减少算法所占的存储空间，通常采用压缩存储技术， 以便尽量减少不必要的额外空间。二、数据结构的基本概念利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：数据集合中各数据元素之间所固有的逻辑结构，即数据的逻辑结构。在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。对各种数据结构进行的运算。讨论以上问题的主要目的是为了提高数据处理的效率。提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。考点3 什么是数据结构 计算机已经被广泛用于数据处理，实际问题中的各数据元素之间总是相互关联的。所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。l 数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素。l 数据对象：性质相同的数据元素的集合是数据的一个子集。l 数据结构：数据结构是指相互关联的数据元素的集合，即数据组织形式。所谓结构，就是指数据元素之间的前后件关系。数据结构包括两个方面的信息：一是表示数据元素的信息；二是表示各数据元素之间的前后件关系。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系即联系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继来描述）。如：描述一年四季的季节名 春、夏、秋、冬 可以作为季节的数据元素。在考虑一年四个季节的顺序关系时，“春”是“夏”的前件（即直接前驱），而“夏”是“春”的后件（即直接后继）；同样，“夏”是“秋”的前件，“秋”是“夏”的后件，等。如：表示家庭成员的各成员名： 父亲、儿子、女儿可以作为家庭成员的数据元素。1、数据的逻辑结构前面提到，数据结构是指反映数据元素之间关系的数据元素集合的表示。它包括两个方面的信息：一是表示数据元素的信息；二是表示各数据元素之间的前后件关系。在以上所述的数据结构中，其中数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关。因此，上面所述的数据结构实际上是数据的逻辑结构。数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构有两个要素：一是数据元素的集合，记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，记为R。即一个数据结构可以表示成：B=（ D， R ）为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。如：假设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。例：一年四季的数据结构可以表示成： B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）例：家庭成员数据结构可以表示成： B=（D，R） D=父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）2、数据的存储结构（也称为数据的物理结构）数据的存储结构（物理结构）：指的是数据的逻辑结构在计算机存储空间中的存放形式。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，而且各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。正是因为这一点，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需存放各数据元素之间的前后件关系的信息。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链式、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。考点4 线性结构的图形表示一个数据结构除了可用二元关系表示外，还可以直观地用图形来表示。B=（D，R） 二元关系表示在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）；除根结点和叶子结点外，其它的结点称为内部结点。例如，一年四季的数据结构可以用下图表示。通常，一个数据结构中的元素结点可能是动态变化的。根据需要或者在数据结构进行处理的过程中，不仅数据结构中的结点个数在动态地变化，而且各元素之间的关系也有可能动态地变化。*考点5 线性结构与非线性结构 重点如果在一个数据结构中没有一个数据元素，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构与非线性结构。 重点如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。 重点注：在一个线性结构中插入或删除任何一个结点后还应是线性结构。春夏秋冬图，就是一个线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。 下图的家庭成员图，就是一个非线性结构。线性结构与非线性结构都可以是空的数据结构。根据具体情况来确定。三、线性表及其顺序存储结构考点6 线性表的基本概念线性表是最简单、最常用的一种数据结构。线性表是一组数据元素组成。如：一个n维向量（x1,x2,xn）是一个长度为n的线性表，其中的每一个分量就是一个数据元素。如：英文小写字母表（a, b, c, , z）是一个长度为26的线性表，其中每一个小写字母就是一个数据元素。如：一年中的四个季节（春，夏，秋，冬）是一个长度为4的线性表，其中的每一个季节名就是一个数据元素。如：学生表，每条记录称为一个数据元素。线性表是由n(n0)个数据元素a1, a2, , an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为： （a1, a2, ,ai , , an）其中ai（i=1,2, , n）是属于数据对象的元素，通常也称其为线性表中的一个结点。显然，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。非空线性表有如下一些结构特征： 有且只有一个根结点a1，它无前件； 有且只有一个终端结点an，它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。*考点7 线性表的顺序存储结构 重点在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。线性表的顺序存储结构具有以下两个基本特点：重点 线性表中所有元素所占的存储空间是是连续的； 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。因此，线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。重点长度为n的线性表（a1, a2, , an），在计算机中的顺序存储结构如下图所示。线性表的顺序存储结构在用一维数组存放线性表时，该数组的长度通常要定义得比线性表的实际长度大一些。在一般情况下，如果线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表的动态变化过程中可能达到的最大长度。在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算如下：8个l 在线性表的指定位置处加入一个新的元素（线性表的插入）。l 在线性表中删除指定位置处的数据元素（线性表的删除）。l 在线性表中查找某个（或某些）特定的元素（线性表的查找）。l 对线性表中的元素进行排序（线性表的排序）。l 按要求将一个线性表分解成多个线性表（线性表的分解）。l 按要求将多个线性表合并成一个线性表（线性表的合并）。l 复制一个线性表（线性表的复制）。l 逆转一个线性表（线性表的逆转）等。考点8 线性表的插入运算 首先分析，插入元素时，线性表的逻辑结构发生什么变化？在一般情况下，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾，即在第n个元素之后（可以认为在第n+1个元素之前）插入新元素，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。插入操作的时间复杂度为：n也有记为：O（n）注意，上溢。例：图1为一个长图为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素（即18）之前插入一个新元素87，其插入过程：略。插入一个新元素后，线性表的长度变为9。 （V(1:10)表示一维数组的存储空间） V（1：10） V（1：10） 图1 插入后如果再要在线性表的第9个元素之前插入一个新元素14，则采用类似的方法：略。插入后，线性表的长度变成了10。如下图所示。此时，不能再插入了。 V（1：10） V（1：10）考点9 线性表的删除运算 删除元素时，线性表的逻辑结构发生什么变化？在一般情况下，要删除第i（1in）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。例：图2为一个长度为8的一线性表顺序存储在长度为10的存储空间中。删除线性表中的第1个元素： 删除线性表中的第6个元素：显然，在线性表采用顺序存储结构时，如果删除运算在线性表的末尾，即删除第n个元素，则不需要移动表中元素；如果要删除线性表的第1个元素，则需要移动表中所有的元素。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。删除操作的时间复杂度为：n O(n)由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储方式对于元素经常需要变动的大线性表就不太合适了。因为插入与删除的效率比较低。其时间复杂度均为n。四、栈和队列*考点10 栈及其基本运算 重点1栈的定义栈（stack）实际上也是线性表，只不过是一种特殊的线性表。其插入和删除运算都只能在表的一端进行。栈是限定在一端进行插入和删除的线性表。课件演示：栈的基本概念.ppt 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与操作的另一端称为栈底，当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，也是最早被删除的元素；栈底元素是最早被插入的元素，也是最晚被删除的元素。即栈的修改原则是先进后出（first in last out，FILO）或后进先出（last in first out，LIFO）。通常，用指针top来指示栈顶的位置，用指针bottom来指示栈底的位置。2栈的顺序存储及运算与一般的线性表一样，在程序设计语言中，用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）。如下图a所示为容量为10的栈顺序存储空间，栈中已有6个元素；图b与图c分别为入栈与退栈后的状态。栈的运算有3种：入栈、退栈与读栈顶元素。入栈运算入栈运算是指在栈顶位置插入一个新元素。此运算有两个基本操作：首先将栈顶指针进入（即top加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。退栈运算退栈是指取出栈顶元素并赋给一个指定的变量。此运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋予一个指定的变量，然后将栈顶指针退1（即top减1）当栈顶指针为0时，说明栈空，不可能再进行退栈操作。这种情况称为栈“下溢”错误。读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，此运算不删除栈顶元素，只是将其赋给一个变量，因此在这个运算中，栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。课件演示：入栈与退栈操作.ppt *考点11 队列及其基本运算 重点1队列的定义队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称队头），通常也用一个排头指针(front)指向排头元素的前一个位置。队列又称为“先进先出”(first in first out，FIFO)或“后进后出” (last in last out，LILO)的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针与排头指针共同反映了队列中元素动态变化的情况。当队列中没有元素时称为空队列。下图为具有6个元素的队列示意图。 往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。下图为入队、退队运算示意图。2循环队列及其运算 重点在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，长度s=0表示队列空，s=m且front=rear表示队列满其它内容不再介绍了五、线性链表*考点12 线性链表的基本概念 重点在链式存储结构中，要求每个结点由两部分组成：一部分是用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中，指针用于指向该结点的前一个或后一个结点（即前件或后件）。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。1线性链表线性表的链式存储结构称为线性链表。为了适应线性表中的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。每个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点，称为指针域。在线性链表中，存储空间的结构如下图所示。在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点。线性表中最后一个元素没有后件，因此线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。线性链表中存储结点的结构如下图所示。线性链表的逻辑结构如下图所示。例：设线性表为（a1, a2, a3 , a4 , a5），存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图1所示。为了直观地表示该线性表中各元素之间的前后件关系，还可以用如图2所示的逻辑状态来表示，其中每一个结点上面的数字表示该结点的存储序号（简称结点号）。一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系不一致。在线性链表中，各数据元素之间的前后件关系是由各结点的指针的指针域来指示的，指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。从头指针开始，依次输出各结点值。上面讨论的线性链表又称为线性单链表。在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。为了弥补线性链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为双向链表，其逻辑状态如下图所示。2带链的栈略3带链的队列略考点13 线性链表的基本运算 线性链表的运算主要有以下几种： 在线性链表中包含指定元素的结点前插入一个新元素。 在线性链表中删除包含指定元素的结点。 将两个线性链表按要求合并成一个线性链表。 将一个线性链表按要求进行分解。 逆转线性链表。 复制线性链表。 线性链表的排序。 线性链表的查找。主要讨论查找、插入和删除。查找：插入：把元素b插入到链表中。插入前：插入后：删除： 删除前： 删除后：考点14 循环链表及其基本运算 了解 循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：l 在循环链表中增加了一个表头结点，其数据域可根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。l 循环链表中最后一个结点的指针域不为空，而是指向表头结点，即循环链表中所有结点的指针构成了一个环状链。循环链表的示意图如下图所示。图1是一个非空的循环链表，图2是一个空的循环链表。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。另外，由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。循环链表的插入和删除的方法与线性链表基本相同，但由循环链表的特点可以看出，在对循环链表进行插入和删除的过程中，实现了空表与非空表的运算统一。六、树与二叉树考点15 树的基本概念 树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用。直观来说，树是以分支关系定义的层次结构。树（tree）是一种简单的非线性结构。在这种数据结构中，所有数据元素之间的关系具有明显的层次特性。下图表示了一棵树。从图中可以看出，在用图形表示这种数据结构时，很像自然界中的树，只不过是一棵例长的树，因此，这种数据结构就用“树”来命名。在树的图形表示中，一般认为在用直线连接起来的两端结点中，上端结点是前件，下端结点是后件，这样表示前后件关系的箭头就可以省略。在现实世界中，能用树这种数据结构表示的例子有很多。如下图为学校的行政关系图。基本特征及术语：重点1、父结点与根结点在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为根结点，简称为根。 如：上面一般的树图中，根结点为：R2、子结点与叶子结点在树结构中，每一个结点可以拥有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点，简称为叶子。 如：上面一般的树图中，叶子结点为：C、E、X、S、M、F、G、L3、结点的度在树结构中，一个结点所拥有的后件个数称为该节点的度。如：上面一般的树图中，结点K、T的度分别为2和3。 叶子结点的度为0，根结点的度为4。4、树的度在树中，所有结点中的最大的度称为树的度。如：上面一般的树图中，树的度为4。5、树的层次结构中的分层原则树是一种层次结构，它有明显的层次关系。在树结构中，一般按如下原则分层：根结点在第一层；同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树，叶子结点没有子树。这棵树的深度为5。以K和T结点为根所构成的子树分别为：在计算机中可以用树结构来表示算术表达式。原则，略。树在计算机中通常用多重链表表示。略。对比树型结构和线性结构的结构特点：*考点16 二叉树及其性质 重点1、什么是二叉树 重点二叉树（binary tree）是一种重要的非线性结构。二叉树具有以下两个特点：非空二叉树只有一个根结点。每个结点最多有两棵子树，且分别称为该结点的左子树与右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，但树结构中的每一个结点的度可以是任意的。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。图1是一棵只有根结点的二叉树，图2是一棵深度为4的二叉树。2、二叉树的基本性质 重点性质1 在二叉树的第k层上，最多有2k-1（k1）个结点。 根据二叉树的特点，这个性质是显然的。性质2 深度为m的二叉树最多有2m-1个结点。深度为m的二叉树是指二叉树共有m层。根据性质1，只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即：21-1+22-1+23-2+2m-1=2m-1性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多1个。解释：不讲了。假设二叉树中有n0个叶子结点，n1个度为1的结点，n2个度为2的结点，则二叉树中总的结点数n为：n= n0+n1+n2 (1)由于在二叉树中除了根结点外，其余每一个结点都有惟一的一个分支进入。设二叉树中所有进入分支的总数为m，则二叉树中总的结点数为：n= m+1 (2)又由于二叉树中这m个进入分支是分别由非叶子结点射出的。其中度为1的每个结点射出1个分支，度为2的每个结点射出2个分支。因此，二叉树中所有度为1与度为2的结点射出的分支总数为n1+2n2。而在二叉树中，总的射出分支数应与总的进入分支数相等，即：m= n1+2n2 (3)将（3）代入（2）式有：n= n1+2n2 +1 (4)最后比较（1）式和（4）式有：n0+n1+n2= n1+2n2 +1化简后得：n0 =n2 +1例：图2所示的二叉树中，3个叶子结点，有2个度为2的结点，度为0的叶子结点比度为2的结点多一个。性质4 具有n个结点的二叉树，其深度至少为 +1，其中表示取log2n的整数部分。 这个性质可以由性质2直接得到。不讲了。解释：2m-1=n，则m= log2(n+1)+13、满二叉树与完全二叉树 重点满二叉树与完全二叉树是两种特殊形态的二叉树.（1）满二叉树除了最后一层外，每一层上的所有结点都有两个子结点的二叉树称为满二叉树。也就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。图3、图4和图5分别是深度为2、3、4的满二叉树。结点数为3结点数为7结点数为15（2）完全二叉树除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。这样的二叉树称为完全二叉树。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。满二叉树是完全二叉树，但完全二叉树一般不是满二叉树。图6、图7分别是深度为3、4的完全二叉树。完全二叉树还具有以下两个性质：了解，不讲了具有n个结点的完全二叉树深度为+1。如果对一棵有n个结点的完全二叉树的结点按层编号，则对于编号为k(1kn)的结点有以下结论。l 如果k=1，则结点k没有父结点，是二叉树的根；如果k1，则该结点的父结点编号为INT(k/2)。l 如果kn，则结点k左子结点编号为2k；否则该结点没有左子结点（显然也没有右子结点）。l 如果2i+1n，则结点k左子结点编号为2k+1；否则该结点没有右子结点。考点17 二叉树的存储结构 了解在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。由于每一个元素可以有两个后件（即两个子结点），因此用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指抽该结点的右子结点的存储地址，称为右指针域。如下图所示。其中，L( i )为结点i的左指针域，即L( i )为结点i的左子结点的存储地址；R( i )为结点i的右指针域，即R( i )为结点i的右子结点的存储地址，V( i )为数据域。由于二叉树的存储结构中每一个存储结点有两个指针，因此二叉树的链式存储结构也称为二叉链表。对于满二叉树与完全二叉树来说，根据完全二叉树的性质，可以按层序进行顺序存储，这样不仅可以节省存储空间，也可以方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储对于一般的二叉树不适用。*考点18 二叉树的遍历 重点二叉树的遍历是指不重复地访问二叉树中的所有结点。由于二叉树是一种非线性结构，因此对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问要结点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。1、前序遍历（DLR）所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后访问右子树。若二叉树为空，则结束返回，否则：a.访问根结点。b.前序遍历左子树。c.前序遍历右子树。一句话：根左右2、中序遍历（LDR）所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后访问右子树。若二叉树为空，则结束返回，否则：a.中序遍历左子树。b.访问根结点。c.中序遍历右子树。一句话：左根右3、后序遍历（LRD）所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。若二叉树为空，则结束返回，否则：a.后序遍历左子树。b.后序遍历右子树。c.访问根结点。一句话：左右根重要的例子：例1：对下图二叉树进行前序遍历，结果为：FCADBEGHP中序遍历，其结果为：ACBDFEHGP 称为该二叉树的中序序列。后序遍历，其结果为：ABDCHPGEF 称为该二叉树的后序序列。例2：已知一棵二叉树的前序遍历结果为：FCADBEGHP，中序遍历结果为：ACBDFEHGP，画出这棵二叉树，并写出后序遍历结果。解：根据前序和中序遍历结果，构造出这棵二叉树如上图所示，则后序遍历结果为：ABDCHPGEF七、查找技术*考点19 顺序查找 重点顺序查找又称顺序搜索。它一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到（即查找成功）；若线性表中所有的元素都与被查元素不相等，则表示线性表中没有要找的元素（即查找失败）。在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高，但在下列两种情况下，也只能采用顺序查找：l 如果线性表是无序的（却表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能顺序查找。l 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。*考点20 二分查找 重点二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列，即从小到大，但允许相邻元素值相等。设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：将x与线性表的中间项进行比较。若中间项的值等于x，则说明查到，查找结束。若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。此过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。显然，当有序线性表为顺序存储时才可能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。重点：对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找则需要比较n次。八、排序技术排序也是数据处理的重要内容。排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。现介绍一些常用的排序方法。排序可以在各种不同的存储结构上实现。现介绍的方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。*考点21 交换类排序法 重点交换排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。1冒泡排序法冒泡排序法是一种最简单的交换类类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。冒泡排序法的基本过程如下：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。然后，从后到前扫描剩下的线性表，同样，在扫描过程