[IT认证]二级考试公共基础知识.ppt

全国计算机等级考试全国计算机等级考试二级二级C语言培训语言培训公共基础知识公共基础知识2024/5/23周四1n n数据结构与算法n n程序设计基础n n软件工程基础n n数据库设计基础2024/5/23周四2算法算法n n算法的基本概念是指解题方案的准确而完整的描述。是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序，对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。正确的结果，则称这个问题是算法可解的。算法不等于程序，也不等于计算方法。算法不等于程序，也不等于计算方法。2024/5/23周四3算法算法n n算法的基本特征可行性：算法总是在某个特定的计算工具上执可行性：算法总是在某个特定的计算工具上执行，算法在执行过程中往往受到计算工具的限行，算法在执行过程中往往受到计算工具的限制，使执行结果产生偏差。制，使执行结果产生偏差。uu例：某计算工具有例：某计算工具有7 7位有效数字，且位有效数字，且A=10A=101212,B=1,C=-,B=1,C=-10101212，则，则A+B+C=0A+B+C=0，A+C+B=1A+C+B=1确定性：算法的每一个步骤都必须是有明确定确定性：算法的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有义的，不允许有模棱两可的解释，也不允许有多义性。多义性。2024/5/23周四4算法算法n n有穷性：算法必须能在有限的时间内做完，算法必须能在执行有限个步骤后终止。n n拥有足够的情报2024/5/23周四5算法的复杂度算法的复杂度n n主要包括时间复杂度和空间复杂度主要包括时间复杂度和空间复杂度n n算法的时间复杂度算法的时间复杂度指执行算法所需要的计算工作量。指执行算法所需要的计算工作量。算法的工作量：用算法所执行的基本运算次数来度量。算法的工作量：用算法所执行的基本运算次数来度量。例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于加法（或减法）运算忽略不计。算作为基本运算，而对于加法（或减法）运算忽略不计。算法所执行的基本运算次数还与问题的规模有关，例如，两个算法所执行的基本运算次数还与问题的规模有关，例如，两个2020阶矩阵相乘与两个阶矩阵相乘与两个1010阶矩阵相乘，所需的基本运算次数显然是阶矩阵相乘，所需的基本运算次数显然是不同的，在分析算法时，还必须对问题的规模进行度量。不同的，在分析算法时，还必须对问题的规模进行度量。算法所执行的基本运算次数是问题规模的函数，即算法所执行的基本运算次数是问题规模的函数，即算法的工作量算法的工作量=f(n)=f(n)其中其中n n是问题的规模是问题的规模2024/5/23周四6算法的时间复杂度算法的时间复杂度 在具体分析一个算法的工作量时，还会存在在具体分析一个算法的工作量时，还会存在这样的问题，对于一个固定的规模，算法所执行这样的问题，对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基际上又不可能将所有可能情况下算法所执行的基本运算次数都列出来。本运算次数都列出来。例如，在长度为例如，在长度为n n的一维数组中查找值为的一维数组中查找值为x x的的元素，若采用顺序搜索法，即从数组的第一个元元素，若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值素开始，逐个与被查值x x进行比较，显然，如果第进行比较，显然，如果第一个元素恰为一个元素恰为x x，则只需比较，则只需比较1 1次，如果次，如果x x为数组的为数组的最后一个元素，或最后一个元素，或x x不在数组中，则需比较不在数组中，则需比较n n次才次才能得到结果。因此，这个问题算法中，基本运算能得到结果。因此，这个问题算法中，基本运算次数与具体的被查值次数与具体的被查值x x有关。有关。2024/5/23周四7算法的时间复杂度算法的时间复杂度 在同一问题规模下，如果算法执行所需的基本在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可用以下两种方运算次数取决于某一特定输入时，可用以下两种方法来分析算法的工作量。法来分析算法的工作量。1.1.平均性态平均性态是指用各种特定输入下的基本运算次数的加权平均值来度是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。量算法的工作量。设设x x是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，p(x)p(x)是是x x出现的概率，出现的概率，t(x)t(x)是算法在输入为是算法在输入为x x时所执行的基本运算次数，则算法的时所执行的基本运算次数，则算法的平均性态定义为平均性态定义为A(n)=p(x)t(x)A(n)=p(x)t(x)x xDnDnDDn n表示当问题规模为表示当问题规模为n n时，算法执行时所有可能输入的集合。时，算法执行时所有可能输入的集合。2024/5/23周四8算法的时间复杂度算法的时间复杂度2.最坏情况复杂性是指在规模为是指在规模为n n时，算法所执行的基本运算的最时，算法所执行的基本运算的最大次数。大次数。W(n)=maxW(n)=maxt(x)t(x)x xDnDn2024/5/23周四9算法的空间复杂度算法的空间复杂度是指执这个算法所需要的内存空间。n n一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。n n在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。2024/5/23周四10 数据结构数据结构n n数据结构的基本概念数据结构的基本概念是指反映数据元素之间关系的数据元素集合的表示。是指反映数据元素之间关系的数据元素集合的表示。即是指带有结构的数据元素的集合。即是指带有结构的数据元素的集合。作为某种处理，其中的数据元素一般具有某种共同的特作为某种处理，其中的数据元素一般具有某种共同的特征。例如，春，夏，秋，冬这四个数据元素有一征。例如，春，夏，秋，冬这四个数据元素有一个共同特征，即它们都是季节名。个共同特征，即它们都是季节名。一般情况下，在具有相同特征的数据元素集合中，各个一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（联系），这种关系反数据元素之间存在有某种关系（联系），这种关系反映了该集合中的数据元素所固有的一种结构。映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系来描述。系简单地用前后件关系来描述。例，考虑一年四季的顺序关系时，春是夏的前件，夏是例，考虑一年四季的顺序关系时，春是夏的前件，夏是秋的前件等等；考虑家庭成员辈分关系时，父亲是儿秋的前件等等；考虑家庭成员辈分关系时，父亲是儿子和女儿的前件，而儿子与女儿都是父亲的后件。子和女儿的前件，而儿子与女儿都是父亲的后件。一般来说，数据元素之间的任何关系都可以用前后件关一般来说，数据元素之间的任何关系都可以用前后件关系来描述。系来描述。2024/5/23周四11数据结构数据结构n n数据的逻辑结构数据的逻辑结构结构是指数据元素之间的前后件关系。结构是指数据元素之间的前后件关系。数据元素之间的前后件关系是指它们的逻辑关系，与数据元素之间的前后件关系是指它们的逻辑关系，与它们在计算机中的存储位置无关。它们在计算机中的存储位置无关。数据的逻辑结构是指反映数据元素之间逻辑关系的数数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。据结构。逻辑结构的两要素：一是数据元素的集合，通常记为逻辑结构的两要素：一是数据元素的集合，通常记为DD；二是；二是DD上的关系，反映了上的关系，反映了DD中各数据元数之间的前后中各数据元数之间的前后件关系，通常记为件关系，通常记为R R。逻辑结构可表示为逻辑结构可表示为B=(D,R)B=(D,R)例，一年四季的数据结构可表示成例，一年四季的数据结构可表示成B=(D,R)D=B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=R=(春，夏春，夏)，(夏，秋夏，秋)，(秋，冬秋，冬)2024/5/23周四12数据结构数据结构n n数据的存储结构数据的存储结构各数据元素在计算机存储空间中的位置关系与它们的各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同，而且一般也不可能相同。逻辑关系不一定相同，而且一般也不可能相同。数据的逻辑结构在计算机存储空间中的存放形式称为数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据的存储结构（也称为数据的物理结构）。数据的存储结构中，不仅要存放各数据元素的信息，数据的存储结构中，不仅要存放各数据元素的信息，还需存放各数据元素之间的前后件关系信息。还需存放各数据元素之间的前后件关系信息。一般来说，一种数据逻辑结构根据需要可表示成多种一般来说，一种数据逻辑结构根据需要可表示成多种存储结构，常用的存储结构有顺序、链接、索引等存存储结构，常用的存储结构有顺序、链接、索引等存储结构。储结构。2024/5/23周四13数据结构的图形表示数据结构的图形表示一个数据结构除了用二元关系表示外，还可以用图形直观的表示。例如，一年四季的数据结构的图形表示。反映家庭间辈分关系的数据结构的图形表示。春夏秋冬父亲儿子女儿2024/5/23周四14线性结构与非线性结构线性结构与非线性结构n n在数据结构中，没有前件的结点称为根结点，没有后件的在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（叶子结点），其他的结点称为内部结结点称为终端结点（叶子结点），其他的结点称为内部结点。点。n n根据数据结构中数据元素之间前后件关系的复杂程度，一根据数据结构中数据元素之间前后件关系的复杂程度，一般将数据结构分为：线性结构和非线性结构。般将数据结构分为：线性结构和非线性结构。n n如果一个非空的数据结构满足下列条件：如果一个非空的数据结构满足下列条件：有且仅有一个根结点。有且仅有一个根结点。每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后件。则该数据结构为线性结构，又称为线性表。则该数据结构为线性结构，又称为线性表。n n如果一个数据结构不是线性结构，称之为非线性结构。如果一个数据结构不是线性结构，称之为非线性结构。n n如果在一个数据结构中一个元素都没有，称之为空的数据如果在一个数据结构中一个元素都没有，称之为空的数据结构。结构。n n对一个空的数据结构的运算按线性结构的规则处理，则属对一个空的数据结构的运算按线性结构的规则处理，则属于线性结构，否则属于非线性结构。于线性结构，否则属于非线性结构。2024/5/23周四15线性表线性表n n线性表是由n(n0)个数据元素a1,a2,an组成的一个有限序列，表中的每一个元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为：（a1,a2,a1,a2,ai,ai,an),an)2024/5/23周四16线性表线性表n n非空线性表有如下一些特征：有且只有一个根结点有且只有一个根结点a1a1，它无前件，它无前件有且只有一个终端结点有且只有一个终端结点anan，它无后件，它无后件除根结点与终端结点外，其它所有结点有且只除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。有一个前件，也有且只有一个后件。n n线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。2024/5/23周四17线性表的顺序存储结构线性表的顺序存储结构n n线性表的顺序存储结构具有以下两个基本特点：线性表的顺序存储结构具有以下两个基本特点：线性表中所有元素所占的存储空间是连续的线性表中所有元素所占的存储空间是连续的线性表中各元素在存储空间中是按逻辑顺序依次存放线性表中各元素在存储空间中是按逻辑顺序依次存放的。的。n n在线性表的顺序存储结构中，其前后件两个元素在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。后件元素的前面。n n在程序设计中，通常定义一个一维数组来表示线在程序设计中，通常定义一个一维数组来表示线性表的顺序存储空间。性表的顺序存储空间。2024/5/23周四18线性表的插入运算线性表的插入运算n n一般情况下，要在第i个元素之前插入一个新的元素，首先要从最后一个元素开始，直到第n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。n n在平均情况下，要插入一个新元素，需要移动表中一半的元素，其效率是很低的。2024/5/23周四19线性表的删除运算线性表的删除运算n n在一般情况下，要删除第i个元素，要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。n n在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素，其效率是很低的。2024/5/23周四20栈栈n n栈是限定在一端进行插入与删除的线性表。栈是限定在一端进行插入与删除的线性表。n n在栈中，允许插入与删除的一端称为在栈中，允许插入与删除的一端称为栈顶栈顶，而不，而不允许插入与删除的一端称为允许插入与删除的一端称为栈底栈底。n n栈是按照栈是按照“先进后出先进后出”或或“后进先出后进先出”的原则组的原则组织数据的。栈具有记忆功能。织数据的。栈具有记忆功能。n n通常用指针通常用指针toptop表示栈顶位置，用表示栈顶位置，用bottombottom指向栈底。指向栈底。n n在栈中插入一个元素称为入栈，从栈中删除一个在栈中插入一个元素称为入栈，从栈中删除一个元素（即删除栈顶元素）称为退栈。栈顶指针元素（即删除栈顶元素）称为退栈。栈顶指针toptop动态反映了栈中元素的变化情况。动态反映了栈中元素的变化情况。n n例如，子弹夹是一种栈，一端封闭、一端开口的例如，子弹夹是一种栈，一端封闭、一端开口的容器也是一种栈。容器也是一种栈。2024/5/23周四21栈的顺序存储及运算栈的顺序存储及运算a amma a2 2a a1 1 入栈 退栈栈顶 top栈底 bottom在程序设计中，用一维数据组在程序设计中，用一维数据组S(1:m)作为栈的顺序作为栈的顺序存储空间，存储空间，m为栈的最大容量。为栈的最大容量。top=0 表示栈空表示栈空 top=m 表示栈满表示栈满入栈运算：在栈顶插入一个新元素。入栈运算：在栈顶插入一个新元素。有两个基本操作：首先将栈顶指针进一（即有两个基本操作：首先将栈顶指针进一（即top加加1），然后将新元素插入到栈顶指针指向的位），然后将新元素插入到栈顶指针指向的位置。置。“上溢上溢”错误：当栈顶指针已指向存储空间的错误：当栈顶指针已指向存储空间的最后一个位置时，不可能再进行入栈操作。最后一个位置时，不可能再进行入栈操作。退栈运算：指取出栈顶元素并赋给一个指定的变量。退栈运算：指取出栈顶元素并赋给一个指定的变量。有两个基本操作：首先将栈顶元素赋给一个指有两个基本操作：首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一（即定的变量，然后将栈顶指针退一（即top减减1)“下溢下溢”错误：错误：top=0，栈空，不可能再进行退，栈空，不可能再进行退栈操作。栈操作。读栈顶元素：指将栈顶元素赋给一个指定的变量。读栈顶元素：指将栈顶元素赋给一个指定的变量。这个运算中栈顶指针不会改变。这个运算中栈顶指针不会改变。2024/5/23周四22队列及基本运算队列及基本运算n n队列：指允许在一端进行插入、在另一端进行删队列：指允许在一端进行插入、在另一端进行删除的线性表。除的线性表。n n队尾：允许插入的一端队尾：允许插入的一端，用，用rearrear指针指向，即指针指向，即rearrear总是指向最后被插入的元素总是指向最后被插入的元素n n队头：允许被删除的一端队头：允许被删除的一端，用排头指针，用排头指针frontfront指向指向排头元素的前一个位置。排头元素的前一个位置。n n队列称为队列称为“先进先出先进先出”或或“后进后出后进后出”的线性表，的线性表，最先被插入的元素最先被删除。最先被插入的元素最先被删除。n n在程序设计中，用一维数组作为队列的顺序存储在程序设计中，用一维数组作为队列的顺序存储空间。空间。2024/5/23周四23循环队列及运算循环队列及运算n n在实际应用中，队列的顺序存储结在实际应用中，队列的顺序存储结构一般采用循环队列的形式。构一般采用循环队列的形式。n n循环队列：将队列的最后一个位置循环队列：将队列的最后一个位置绕到第一个位置，形成逻辑上的环绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。状空间，供队列循环使用。n n当存储空间的最后一个位置被使用当存储空间的最后一个位置被使用而再要进行入队运算时，只要存储而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元空间的第一个位置空闲，便可将元素加入到第一个位置。素加入到第一个位置。n n从排头指针从排头指针frontfront指向的后一个位置指向的后一个位置直到队尾指针直到队尾指针rearrear指向的位置之间指向的位置之间所有的元素均为队列中的元素。所有的元素均为队列中的元素。Q(1:m)rear mfront122024/5/23周四24循环队列及运算循环队列及运算图图a a是一个容量为是一个容量为8 8的循环队列，其中已有的循环队列，其中已有6 6个元素。图个元素。图b b是在是在图图a a的循环队列中又加入了的循环队列中又加入了2 2个元素后状态，图个元素后状态，图c c是在图是在图b b的的循环队列中退出了循环队列中退出了1 1个元素后的状态。个元素后的状态。X XF FE EDDC CB BA AY YF FE EDDC CB BA AX XF FE EDDC CB BY YQ(1:8)Q(1:8)Q(1:8)876543218765432187654321rearfrontfrontrearfrontrear(a)具有6个元素的循环队列（b)加入X、Y后的队列(c)退出一个元素后的循环队列2024/5/23周四25循环队列及运算循环队列及运算n n队列为空还是满的标志队列为空还是满的标志S S，s=0s=0队空，队空，s=1s=1，且，且front=rear,front=rear,队队满。满。n n循环队列的初始状态为空，即循环队列的初始状态为空，即rear=front=mrear=front=mn n循环队列有两种运算：入队与退队循环队列有两种运算：入队与退队n n入队：在循环队的队尾加入一个新元素。入队：在循环队的队尾加入一个新元素。有两个基本操作：首先将队尾指针进一（即有两个基本操作：首先将队尾指针进一（即rear=rear+1)rear=rear+1)，并当，并当rear=m+1rear=m+1时置时置rear=1rear=1；然后将新元素插入到队尾指针指向的位置。；然后将新元素插入到队尾指针指向的位置。上溢：当循环队列非空且队尾指针等于排头指针，说明队列满，上溢：当循环队列非空且队尾指针等于排头指针，说明队列满，不能进行入队运算。不能进行入队运算。n n退队：在循环队列的排头位置退出一个元素并赋给指定的退队：在循环队列的排头位置退出一个元素并赋给指定的变量。变量。有两个基本操作：首先将排头指针进一（即有两个基本操作：首先将排头指针进一（即front=front+1front=front+1），并当），并当front=m+1front=m+1时置时置front=1front=1，然后将排头指针指向的元素赋给指定的变，然后将排头指针指向的元素赋给指定的变量。量。下溢：当循环队列为空时，不能进行退队运算。下溢：当循环队列为空时，不能进行退队运算。2024/5/23周四26线性链表线性链表n n对于大的线性表，特别是元素变动频繁的大线性表不宜采对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用链式存储结构。用顺序存储结构，而是采用链式存储结构。n n链式存储结构中，要求每个结点由两部分组成：一部分用链式存储结构中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存入指针，于存放数据元素值，称为数据域；另一部分用于存入指针，称为指针域。指针用于指向该结点的前一个或后一个结点。称为指针域。指针用于指向该结点的前一个或后一个结点。n n链式存储结构中，存储空间可以不连续，数据结点的存储链式存储结构中，存储空间可以不连续，数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据之间的顺序与数据元素之间的逻辑关系可以不一致，数据之间的逻辑关系不由指针域确定。逻辑关系不由指针域确定。n n线性链表：线性表的链式存储结构。线性链表：线性表的链式存储结构。n n线性链表中，用专门的指针线性链表中，用专门的指针HEADHEAD指向线性表中的第一个指向线性表中的第一个数据元素的结点，线性表中最后一个元素没有后件，指针数据元素的结点，线性表中最后一个元素没有后件，指针域为空（用域为空（用NULLNULL或或0 0表示，表示链表终止。表示，表示链表终止。数据1数据2数据n NULLHEAD2024/5/23周四27线性链表线性链表n n当当HEAD=NULLHEAD=NULL（或（或0 0）时称为空表。）时称为空表。n n栈和队列也是线性链表，也可以采用链式存储结栈和队列也是线性链表，也可以采用链式存储结构。构。n n线性单链表：每个结点只有一个指针域，由这个线性单链表：每个结点只有一个指针域，由这个指针域只能找到后件结点。指针域只能找到后件结点。n n双向链表：对线性链表中每个结点设置两个指针，双向链表：对线性链表中每个结点设置两个指针，一个指向其前件结点，称为左指针；一个指向后一个指向其前件结点，称为左指针；一个指向后件结点，称为右指针。件结点，称为右指针。n n带链的栈：可以用来收集计算机存储空间的所有带链的栈：可以用来收集计算机存储空间的所有空闲的存储结点，这种带链的栈称为可利用栈。空闲的存储结点，这种带链的栈称为可利用栈。n n带链的队列带链的队列2024/5/23周四28线性链表的基本运算线性链表的基本运算n n在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值在非空线性链表中寻找包含指定元素值x x的前一的前一个结点个结点p p的基本方法：的基本方法：uu从头指针指向的结点开始往后进行扫描，直到后面从头指针指向的结点开始往后进行扫描，直到后面已没有结点或下一个结点的数据域为已没有结点或下一个结点的数据域为x x为止。由这种为止。由这种方法找到的结点方法找到的结点p p有两种可能：当线性链表中存在包有两种可能：当线性链表中存在包含元素含元素x x的结点时，则找到的的结点时，则找到的p p为第一次遇到的包含为第一次遇到的包含元素元素x x的前一个结点序号；当线性链表中不存在包含的前一个结点序号；当线性链表中不存在包含元素元素x x的结点时，则找到的的结点时，则找到的p p为线性链表中的最后一为线性链表中的最后一个结点号。个结点号。2024/5/23周四29线性链表的基本运算线性链表的基本运算n n线性链表的插入为了要在线性链表中插入一个新元素，首先要给为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素该元素分配一个新结点，以便用于存储该元素的值。新结点可以从可利用栈中取得。的值。新结点可以从可利用栈中取得。n n线性链表的删除首先要在线性链表中找到这个结点，然后将要删首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。除结点放回到可利用栈。2024/5/23周四30循环链表循环链表n n循环链表中最后一个结点的指针域不是空，而是循环链表中最后一个结点的指针域不是空，而是指向头结点。指向头结点。n n在循环链表中，只要指出一个结点的位置，就可在循环链表中，只要指出一个结点的位置，就可以从它出发访问到表中其他所有结点，而线性单以从它出发访问到表中其他所有结点，而线性单链表做不到这一点。链表做不到这一点。n n循环链表中增加了一个表头结点，其数据域任意，循环链表中增加了一个表头结点，其数据域任意，指针域指向线性表的第一个元素的结点。指针域指向线性表的第一个元素的结点。n n在线性链表中，对于空表和对第一个结点的处理在线性链表中，对于空表和对第一个结点的处理必须单独考虑，而循环链表实现了空表与非空表必须单独考虑，而循环链表实现了空表与非空表的运算统一。的运算统一。2024/5/23周四31树与二叉树树与二叉树n n树是一种简单的非线性结构，所有数据元素之间具有明显的层次特性。n n上端结点是前件，下端结点是后件。书第一章第二章第三章第四章1.1节1.2节2.1节2.2节3.1节2024/5/23周四32树与二叉树树与二叉树n n结构中，每一个结点只有一个前件，称为结构中，每一个结点只有一个前件，称为父结点父结点。在树中，。在树中，没有前件的结点只有一个，称为树的没有前件的结点只有一个，称为树的根结点根结点，简称为树根。，简称为树根。n n结构中，每一个结点可以有多个后件，称为该结点的子结结构中，每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为点。没有后件的结点称为叶子结点叶子结点。n n一个结点所拥有的后件结点的个数，称为该一个结点所拥有的后件结点的个数，称为该结点的度结点的度。n n树是一种层次结构，根结点在第树是一种层次结构，根结点在第1 1层，同一层上所有结点层，同一层上所有结点的子结点在下一层。树的最大层次称为的子结点在下一层。树的最大层次称为树的度树的度。n n在树中，以某结点的一个子结点为根构成的树称为该结点在树中，以某结点的一个子结点为根构成的树称为该结点的一棵的一棵子树子树。叶子结点没有子树。叶子结点没有子树。n n树在计算机中通常用多重链表表示。多重链表中的每个结树在计算机中通常用多重链表表示。多重链表中的每个结点描述了树中的对应结点的信息，而每个结点中的链域点描述了树中的对应结点的信息，而每个结点中的链域（即指针域）个数将随树中该结点的度而定。（即指针域）个数将随树中该结点的度而定。2024/5/23周四33二叉树二叉树n n树结构的所有术语都可用到二叉树这种数据结构树结构的所有术语都可用到二叉树这种数据结构上。上。n n二叉树具有如下特点：二叉树具有如下特点：非空二叉树只有一个根结点。非空二叉树只有一个根结点。每一个结点最多有两棵子树，且分别称为该结点的左每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。子树和右子树。n n二叉树中，每一个结点的度最大为二叉树中，每一个结点的度最大为2 2；一个结点可；一个结点可以只有左子树而没有右子树，也可以只有右子树以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有而没有左子树。当一个结点既没有左子树也没有右子树，该结点为叶子结点。右子树，该结点为叶子结点。2024/5/23周四34二叉树的基本性质二叉树的基本性质n n在二叉树的第k层上，最多有2k-1(k1)个结点。n n深度为m的二叉树最多有2m-1个结点。2 21-11-1+2+22-12-1+2+2m-1m-1=2=2mm-1-1n n在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。n n具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分。2024/5/23周四35满二叉树满二叉树n n满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。n n在满二叉树的第k层上有2k-1个结点。n n深度为m的满二叉树有2m-1个结点。2024/5/23周四36完全二叉树完全二叉树n n完全二叉树：除最后一层外，每一层上结点数均完全二叉树：除最后一层外，每一层上结点数均达到最大值；在最后一层上只缺少达到最大值；在最后一层上只缺少右边右边的若干结的若干结点。点。n n如果从根结点起，对二叉树的结点自上而下、自如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为左至右用自然数进行连续编号，则深度为mm、且、且有有n n个结点的二叉树，当且仅当每一个结点都与深个结点的二叉树，当且仅当每一个结点都与深度为度为mm的满二叉树中编号从的满二叉树中编号从1 1到到n n的结点一一对应，的结点一一对应，称之为完全二叉树。称之为完全二叉树。n n对于完全二叉树，叶子结点只可能在层次最大的对于完全二叉树，叶子结点只可能在层次最大的两层上出现。两层上出现。n n满二叉树一定是完全二叉树，但完全二叉树一般满二叉树一定是完全二叉树，但完全二叉树一般不是满二叉树。不是满二叉树。2024/5/23周四37完全完全 二叉树的性质二叉树的性质n n具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+1n+1n n设完全二叉树共有设完全二叉树共有n n个结点。如果从根结点开始，个结点。如果从根结点开始，按层序（每一层从左至右）用自然数按层序（每一层从左至右）用自然数1,2,1,2,n,n给结点给结点编号，则对于编号为编号，则对于编号为k(k=1,2,k(k=1,2,n),n)的结点有以下结的结点有以下结论：论：若若k=1k=1，则该结点为根结点；若，则该结点为根结点；若k1k1，则该结点父结点编，则该结点父结点编号为号为INT(k/2)INT(k/2)。若若2kn,2kn,则编号为则编号为k k的结点左子结点编号为的结点左子结点编号为2k2k;否则该结点否则该结点无左子结点。无左子结点。若若2k+1 n2k+1 n，则编号为，则编号为k k的结点的右子结点编号为的结点的右子结点编号为2k+12k+1；否则该结点无右子结点。否则该结点无右子结点。2024/5/23周四38二叉树的存储结构二叉树的存储结构n n计算机中，二叉树常采用链式存储结构。n n二叉树存储结构中，每一个结点有两个指针域，一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。n n二叉树的链式存储结构也称为二叉链表。2024/5/23周四39二叉树的遍历二叉树的遍历n n遍历：是指不重复地访问二叉树中的所有结点。遍历：是指不重复地访问二叉树中的所有结点。n n二叉树的遍历分为：二叉树的遍历分为：前序遍历、中序遍历、后序遍历前序遍历、中序遍历、后序遍历n n前序遍历：首先访问根结点，然后遍历左子树，最后遍历前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。然后遍历左子树，最后遍历右子树。n n中序遍历：先遍历左子树，然后访问根结点，最后遍历右中序遍历：先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左右子树时，仍然先遍历左子树，然子树；并且，在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。后访问根结点，最后遍历右子树。n n后序遍历：先遍历左子树，然后遍历右子树，最后访问根后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。然后遍历右子树，最后访问根结点。2024/5/23周四40二叉树的遍历二叉树的遍历FCEADBGHPn n前序遍历结果为：FCADBEGHPn n中序遍历结果为：ACBDFEHGPn n后序遍历结果为：ABDCHPGEF2024/5/23周四41查找技术查找技术n n顺序查找：一般指在线性表中查找指定的元素。顺序查找：一般指在线性表中查找指定的元素。n n顺序查找的基本方法：顺序查找的基本方法：从线性表的第一个元素开始，依次将线性表中的元素与从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到；若线性表中被查元素进行比较，若相等则表示找到；若线性表中所有元素都与被查元素进行了比较但都不相等，则表所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素。示线性表中没有要找的元素。n n平均情况下，利用顺序查找法在线性表中查找一平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中的个元素，大约要与线性表中的一半一半的元素进行比的元素进行比较。较。2024/5/23周四42二分法查找二分法查找n n只适用于顺序存储的有序表。只适用于顺序存储的有序表。n n设有序线性表的长度为设有序线性表的长度为n n，被查元素为，被查元素为x x，则对分，则对分查找的方法如下：查找的方法如下：将将x x与线性表的中间项进行比较，如果中间项的值等于与线性表的中间项进行比较，如果中间项的值等于x x，则说，则说明查到，查找结束；如果明查到，查找结束；如果x x小于中间项的值，则在线性表的前小于中间项的值，则在线性表的前半部分以相同的方法进行查找；如果大于中间项的值，则在半部分以相同的方法进行查找；如果大于中间项的值，则在线性表的后半部分以相同的方法进行查找。这个过程一直进线性表的后半部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为行到查找成功或子表长度为 0 0（说明线性表中没有该元素）为（说明线性表中没有该元素）为止。止。n n当有序表线性表为顺序存储时才能采用二分查找，当有序表线性表为顺序存储时才能采用二分查找，效率比顺序查找高得多。效率比顺序查找高得多。n n对于长度为对于长度为n n的有序线性表，在最坏情况下，二的有序线性表，在最坏情况下，二分法查找只需要比较分法查找只需要比较loglog2 2n n次。次。2024/5/23周四43二分法查找的二分法查找的C语言程序语言程序2024/5/23周四44二分查找又称折半查找，它是一种效率较高的查找方法。二分查找又称折半查找，它是一种效率较高的查找方法。【二分查找要求二分查找要求】：1.1.必须采用顺序存储结构。必须采用顺序存储结构。2.2.必须按关键字大小有序排列。必须按关键字大小有序排列。【优缺点优缺点】折半查找法的优点是比较次数少，查找速度折半查找法的优点是比较次数少，查找速度快，平均性能好快，平均性能好;其缺点是要求待查表为有序表，且插入删除其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。有序列表。【算法思想算法思想】首先，将表中间位置记录的关键字与查找首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。或直到子表不存在为止，此时查找不成功。2024/5/23周四45程序：程序：/找到时返回元素下标，否则返回找到时返回元素下标，否则返回0/前提：前提：a1.2.n是非递减有序的是非递减有序的#include#define N 10int binsearch(int