全国计算机等级考试《二级C++语言程序设计》【教材精讲+真题解析】讲义与视频课程

1、全国计算机等级考试二级C+语言程序设计【教材精讲+真题解析】讲义与视频课程最新资料，WORD式，可编辑修改！目录视频讲解教师简介教材精讲部分视频讲解第一部分公共基础知识视频讲解第1章数据结构与算法视频讲解第2章程序设计基础视频讲解第3章软件工程基础视频讲解第4章数据库设计基础视频讲解第二部分C+S言程序设计视频讲解第1章C+铺言人述视频讲解第2章数据类型、运算符和表达式视频讲解第3章基本控制结构视频讲解第4章数组、指专f与引用视频讲解第5章函数视频讲解第6章类和对象视频讲解第7章继承和派生视频讲解第8章运算符重载视频讲解第9章模板视频讲解第10章C+毓视频讲解第11章考试指导视频讲解真题解析部

2、分全国计算机等级考试二级C+铺言程序设计真题及详解（一）全国计算机等级考试二级C+吾言程序设计真题及详解（二）全国计算机等级考试二级C+铺言程序设计真题及详解（三）全国计算机等级考试二级C+吾言程序设计真题及详解（四）教材精讲部分视频讲解第一部分公共基础知识视频讲解考试形式1 .公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。2 .考试方式为上机考试，10道选择题，占10分。大纲基本要求1 .掌握算法的基本概念。2 .掌握基本数据结构及其操作。3 .掌握基本排序和查找算法。4 .掌握逐步求精的结构化程序设计方法。5 .掌握软件工程的基本方法，具有初步应用相关技术

3、进行软件开发的能力。6 .掌握数据库的基本知识，了解关系数据库的设计。知识点分布1 .数据结构与算法2 .程序设计基础3 .软件工程基础4 .数据库设计基础第1章数据结构与算法视频讲解本章考点1 .算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度)2 .数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3 .线性表的定义；线性表的顺序存储结构及其插入与删除运算。4 .栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5 .线性单链表、双向链表与循环链表的结构及其基本运算。6 .树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后

4、序遍历。7 .顺序查找与二分法查找算法；基本排序算法(交换类排序，选择类排序,插入类排序)。第一节算法一、算法的基本概念1 .算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。*算法不等于程序，也不等于计算方法。2 .算法的基本特征(1)可行性(Effectiveness)算法中的每一个步骤必须能够实现。算法执行的结果要能够达到预期的目的。(2)确定性(Definiteness)算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。(3)有穷性(Finiteness)算法的有穷性是指算法必须能在有限的时间内做完，即

5、算法必须能在执行有限个步骤之后终止。*算法的有穷性还应包括合理的执行时间(4)拥有足够的情报输入是否足够并正确，输出是否合理。初始状态是否正确。二、算法设计基本方法1 .列举法(1)基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。(2)特点简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。(3)使用将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。例1.1今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？假设买母鸡I只、公鸡J只、小鸡KN。根据题意，粗略的列举算法描

6、述如下：FORI=0TO100STEP1DOFORJ=0TO100STEP1DOFORK=0TO100STEP1DOIF(I+J+K=100)AND(3*I+2*J+0.5*K=100.0)THENPRINTI,J,KEND共有三层循环，每层循环各需要循环101次，大约为100万次。优化后的算法FORI=0TO33STEP1DOFORJ=0TO50-1.5*ISTEP1DOK=100-I-JIF(3*I+2*J+0.5*K=100.0)THENPRINTI,J,KEND共有两层循环，循环次数为2 .归纳法(1)基本思想通过列举少量的特殊情况，经过分析最后找出一般的关系。(2)特点归纳是一种抽象

7、，即从特殊现象中找出一般关系。(3)使用由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。3 .递推(1)基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。(2)特点本质上属于归纳法，递推关系式往往是归纳的结果。(3)使用递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。4 .递归*(1)基本思想为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，

8、实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。(2)特点结构清晰，可读性强。(3)使用递归在可计算性理论和算法设计中占有很重要的地位。(4)分类直接递归(自己调用自己)和间接递归(P调用QQ又调用P)。例1.2编写一个过程，对于输入的参数n,依次打印输出自然数1到n非递归算法：wrt(intn)FORk=1TOnSTEP1DOPRINTkRETURN递归算法：wrt1(intn)IF(n乎0)THENwrtl(n-1)PRINTnRETURN5 .减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减

9、半”的过程。例1.3设方程f(x)=0在区间a,b上有实根，且f(a)与f(b)异号。利用二分法求该方程在区间a,b上的一个实根。用二分法求方程实根的减半递推过程如下：首先取给定区间的中点c=(a+b)/2。然后判断f(c)是否为0o若f(c)=0,则说明C即为所求的根，求解过程结束；如果f(c)乎0,则根据以下原则将原区间减半：若f(a)f(c)<0,则取原区间的前半部分；若f(b)f(c)<0,则取原区间的后半部分。最后判断减半后的区间长度是否已经很小：若|a-b卜e,则过程结束，取(a+b)/2为根的近似值；若|a-b|e,则重复上述的减半过程。6 .回溯法(1)基本思想通过

10、对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。(2)特点在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。三、算法复杂度主要包括时间复杂度和空间复杂度。7 .算法的时间复杂度(1)定义执行算法所需要的计算工作量。(2)衡量标准通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关。综上所述，算法的工作量用算法所执行的基本运算次数来度量

11、，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)。(3)存在问题算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。(4)解决方法平均性态(AverageBehavior)用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。最坏情况复杂性(Worst-CaseComplexity)规模为n时，算法所执行的基本运算的最大次数。w=max«(X)xDn例1.4采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。

12、(1)平均性态分析设被查项x在数组中出现的概率为q,i=n+1表示x不在数组中的情况(2)最坏性态分析W(n)=maxti|l<i<n+1=n注：当算法的计算工作量与输入无关时，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n尸W(n)o8 .算法的空间复杂度定义：执行这个算法所需要的内存空间。(1)算法程序所占的空间；(2)输入的初始数据所占的存储空间；(3)算法执行过程中所需要的额外空间。*如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。*在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额

13、外空间。第二节数据结构的基本概念数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；(2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(3)对各种数据结构进行的运算。讨论以上问题的目的：(1)提高数据处理的速度；(2)尽量节省在数据处理过程中所占用的计算机存储空间。一、什么是数据结构定义：数据结构是指相互有关联的数据元素的集合。数据元素具有广泛的含义：描述一年四季的季节名：春、夏、秋、冬表示数值的各个数：18、11、35、23、16表示家庭成员的各成员名：父亲、儿子、女儿数据处理：对数据集合

14、中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。*作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。1 .数据的逻辑结构(1)定义反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系。(2)数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D;二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R;即一个数据结构可以表示成B=(D,R)。例1.

15、5一年四季的数据结构可以表示成B=(D,R)D=春，夏，秋，冬R=(春，夏)，(夏，秋)，(秋，冬)例1.6家庭成员数据结构可以表示成B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子)，(父亲，女儿)例1.7n维向量X=(x%X2,，xn)也是一种数据结构。即X=(D,R),其中数据元素的集合为：D=x1,x2,，xn关系为：R=(x1,x2),(x2,x3)，(xn-1,xn)*对于一些复杂的数据结构来说，它的数据元素可以是另一种数据结构。例如，mXn的矩阵是一个数据结构。在这个数据结构中，矩阵的每一行Ai=(a1，ai2,，烝)，i=1,2,，m可以看成是它的一个数据元素。即这个数据结构

16、的数据元素的集合为D=A1,A2,，AmD上的一个关系为R=(A,A),(A2,A),，(A,A+1),，(Am-1,A显然，数据结构A中的每一个数据元素：A(i=1,2,，m)又是另一个数据结构,即数据元素的集合为：D=a口，ai2,.，ainD上的一个关系为:(ai2, ai3),，(aj , ai, j+1),，(ai, n-1, a) R=，ai2),2.数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式。* 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。* 在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之

17、间的前后件关系的信息。* 常用的存储结构有顺序、链接、索引等存储结构。* 采用不同的存储结构，其数据处理的效率是不同的。二、数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。(1)对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；(2)对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。图1-1一年四季数据结构的图形表示图1-2家庭成员间辈分关系数据结构的图形表示例1.8用图形表示数据结构B=(D,R),其中D=di|1<i<7_d1,d2,d3,d,，ds,de,d7R=(d1,d

18、3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点(也称为叶子结点)。图1.3例1.8数据结构的图形表示三、线性结构与非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，线性结构又称线性表。* 在一个线性结构中插入或删除任何一个结点后还应是线性结构。图1.4不是线性结构的数据结构特例如果一个数据结构不是线性结构，则

19、称之为非线性结构。* 线性结构与非线性结构都可以是空的数据结构。* 一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。* 如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。第三节线性表及其顺序存储结构一、线性表的基本概念线性表(LinearList)是最简单、最常用的一种数据结构。如：一个n维向量、矩阵，学生情况登记表；综上所述，线性表是由n(n>0)个数据元素a1,a2,，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(al

20、,a2,，ai,，an)其中ai(i=1,2,，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。非空线性表有如下一些结构特征：(1)有且只有一个根结点ai它无前件；(2)有且只有一个终端结点a%它无后件；(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。*线性表中结点的个数n称为线性表的长度。*当n=0时，称为空表。二、线性表的顺序存储结构1.特点(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。图1.

21、5线性表的顺序存储结构*在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。*在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。2.在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几种：(1)在线性表的指定位置处加入一个新的元素(即线性表的插入)；(2)在线性表中删除指定的元素(即线性表的删除)；(3)在线性表中查找某个(或某些)特定的元素(即线性表的查找)；(4)对线性表中的元素进行整序(即线性表的排序)；(5)按要求将一个线性表分解成多个线性表(即线性表的分解)；(6)按要求将多个线性

22、表合并成一个线性表(即线性表的合并)；(7)复制一个线性表(即线性表的复制)；(8)逆转一个线性表(即线性表的逆转)等。三、顺序表的插入运算例1.9图1.6(a)为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素(即18)之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。图1.6线性表在顺序存储结构下的插入假设线性表的存储空间为V(1:m),线性表的长度为n(n<mj),插入的位置为i(i表示在第i个元素之前插入)，插入新元素。则插入的过程如下：(1)首先处理以下三种异常情况：* 当存储空间已满(即n=m)时为“上溢”错误，不能进行插入，算

23、法结束；* 当i>n时，认为在最后一个元素之后(第n+1个元素之前)插入；* 当i<1时，认为在第1个元素之前插入。(2)然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。(3)最后将新元素插入到第i个位置，并且将线性表的长度增加1。*由于大多数情况下需要移动数据元素，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。四、顺序表的删除运算例1.10图1.7(a)为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素(即删除元素29)o再删除线性表中的第6个元素。图1.7线性表在顺序存储结构下的删除假设线性表的存储空

24、间为V(1:m),线性表的长度为n(n<mj),删除的位置为i(表示删除第i个元素)。则删除的过程如下：(1)首先处理以下两种异常情况：*当线性表为空(即n=0)时错误，不能进行删除，算法结束；*当i<1或i>n时，错误，不能进行删除，算法结束；(2)删除线性表中的第i个元素；(3)然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置；(4)最后将线性表的长度减小1。*由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。*但这种顺序存储的方式对于元素

25、经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。第四节栈和队列一、栈及其基本运算1 .什么是栈定义：限定在一端进行插入与删除的线性表* 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。用指针top来指不栈顶的位置，用指针bottom指向栈底。* 栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。* 栈具有记忆作用。* 往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)

26、称为退栈运算。计算机系统在处理时要用一个线性表来动态记忆调用过程中的路径，其基本原则如下：(1)在开始执行程序前，建立一个线性表，初始状态为空；(2)发生调用时，将当前调用的返回点地址插入到线性表的末尾；(3)当遇到从某个子程序返回时，其返回点地址从线性表的末尾取出(即删除线性表的最后一个元素)。图1.9栈示意图图1.8中给出了具有嵌套调用关系的五个程序，其中主程序要调用子程序SUB1SUB1要调用子程序SUB2SUB2要调用子程序SUB3SUB谍调用子程序SUB4SUB4不再调用其他子程序了。图1.8主程序与子程序之间的调用关系图1.8中五个程序在执行过程中的调用顺序以及线性表中元素变化的情

27、况如下：(1)主程序开始执行前，建立一个空线性表。即线性表的状态为()o(2)开始执行主程序MAIN当要调用子程序SUB1时，先将本次调用的返回点地址A插入到线性表的末尾。此时，线性表的状态为(A)o(3)开始调用执行子程序SUB，当要调用子程序SUB2时，先将本次调用的返回点地址B插入到线性表的末尾。止匕时,线性表的X犬态为(A,B)。(4)开始调用执行子程序SUB2当要调用子程序SUB3时，先将本次调用的返回点地址C插入到线性表的末尾。此时，线性表的状态为(A,B,C)。(5)开始调用执行子程序SUB3当要调用子程序SUB4时，先将本次调用的返回点地址D插入到线性表的末尾。此时，线性表的状

28、态为(A,B,C,D)0由上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址插入到线性表的末尾，而这种对线性表的插入操作是不需要移动线性表中原有元素的。并且，各返回点地址在线性表中的存放顺序恰好是调用顺序。(6)开始调用执行子程序SUB4由于子程序SUB4不再调用其他子程序，执行完子程序SUB4后要返回到子程序SUB3的地址D处。其中返回点地址D取自线性表的最后一个元素。取出D后，线性表的状态为(A,B,C)0(7)返回到子程序SUB3的D处继续执行，执行完子程序SUB3后要返回到子程序SUB2的地址C处。其中返回点地址C取自线性表的最后一个元素。取出C后，线性表的状态为

29、(AB)。(8)返回到子程序SUB2的C处继续执行，执行完子程序SUB2后萋返回到子程序SUB1的地址B处。其中返回点地址、取自线性表的最后一个元素。取出B后，线性表的状态为(A)0(9)返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A取自线性表最后一个元素。取出A后，线性表变空，即线性表的状态为()o(10)返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完成。由上述逐步返回的过程可以看出，当由子程序返回到上一个调用程序时，需要从线性表的末尾取出返回点地址，即从线性表中删除最后一个元素，而这种对线性表的删除操作也是不需要移

30、动线性表中其他数据元素的。2 .栈的顺序存储及其运算图1.10(a)是容量为10的栈顺序存储空间，栈中已有6个元素；图1.10(b)与图1.10(c)分别为入栈与退栈后的状态。图1.10栈在顺序存储结构下的运算在栈的顺序存储空间S(1:成中，S(bottom)通常为栈底元素(在栈非空的情况下)，S(top)为栈顶元素。top=0表示栈空；top=m表示栈满。栈的基本运算有三种：入栈、退栈与读栈顶元素。(1)入栈运算入栈运算是指在栈顶位置插入一个新元素。操作过程如下：首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作(这种情况称为栈“上溢”错误)，

31、算法结束。然后将栈顶指针进一(即top加1)。最后将新元素x插入栈顶指针指向的位置。(2)退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为00如果是，则说明栈空，不可能进行退栈操作(这种情况称为栈“下溢”错误)，算法结束。然后将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量。最后将栈顶指针退一(即top减1)。(3)读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为00如果是，则说明栈空，读不到栈顶元素，算法结束。然后将栈顶元素赋给指定的变量yo必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，

32、在这个运算中栈顶指针不会改变。二、队列及其基本运算1 .什么是队列在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：初始时线性表为空；当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出(删除)元素。这种线性表称为队列。定义：队列(Queue是指允许在一端进行插入、而在另一端进行删除的线性表。* 允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的

33、元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（Front）指向排头元素的前一个位置。* 在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。* 在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。图1.11具有6个元素的队列示意图图1.12队列运算示意图2 .循环队列及其运算定义：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。* 在循环队列中，用队尾指针rear指向队列中

34、的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。* 循环队列的初始状态为空，即rear=front=m,如图1.13所示。图1.13循环队列存储空间示意图循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=10图1.14循环队列运算例* 当循环队列满时有front=rear,而当循环队列空时也有front=rear。即在

35、循环队列中，当front=rear时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s,s值的定义如下：由此可以得出队列空与队列满的条件如下：队列空的条件为s=0；队列满的条件为s=1且front=rear。假设循环队列的初始状态为空，即：s=0,且front=rear=m。（1）入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。然后将队尾指针进一（即rear=rear+1）,并当r

36、ear=m+1时置rear=1。最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。（2）退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。然后将排头指针进一（即front=front+1），并当front=m+1时置front=1再将排头指针指向的元素赋给指定的变量最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（即s=0）0第五节线性链表一、线性链表的基本概念*线性表的顺序存储结构具有简单、运算方便等优点，特别是对于

37、小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。*线性表的顺序存储结构存在的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。（2）当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。（3）线性表的顺序存储结构不便于对存储空间的动态分配。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。* 假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元

38、称为存储结点，简称结点。* 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。* 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。* 链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。1 .线性链表定义：线性表的链式存储结构称为线性链表。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方

39、面要存储各数据元素之间的前后件关系。图1.15线性链表的存储空间为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。图1.16线性链表的一个存储结点* 在线性链表中，用一个专门的指针HEADW向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL1或0表示），表示链表终止。图1.17线性链表的逻辑结构* 在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。* 当HEAD

40、=NULL（或0）时称为空表。图1.18线性链表例* 在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink）,用以指向其前件结点；另一个称为右指针（Rlink）,用以指向其后件结点。这样的线性链表称为双向链表。图1.19双向链表示意图2 .带链的栈栈也是线性表，也可以

41、采用链式存储结构。图1.20带链的栈在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。图1.21可利用栈及其运算与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化。即建立一个空栈的顺序存储空间。入栈运算。是指在栈顶位置插入一个新元素。退栈运算。是指取出栈顶元素并赋给一个指定的变量。读栈顶元素。是指将栈顶元素赋给一个指定的变量。3 .带链的队列队列也是线性表，也可以采用链式存储结构。图1.22带链的队列及其运算与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化。即建立一个空队列的顺序存储空间。入队运算。是指在循环队列的队尾加入一个新元素。退

42、队运算。是指在循环队列的排头位置退出一个元素并赋给指定的变量。二、线性链表的基本运算线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合并成一个线性链表将一个线性链表按要求进行分解。逆转线性链表。复制线性链表。线性链表的排序。线性链表的查找。1 .在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下:从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：*当线性链表中存在包含元素x的结点时，则找到的

43、p为第一次遇到的包含元素x的前一个结点序号；*当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。2 .线性链表的插入(1)定义在链式存储结构下的线性表中插入一个新元素。(2)插入过程从可利用栈取得一个结点，设该结点号为p(即取得结点的存储序号存放在变量p中)，并置结点p的数据域为插入的元素值bo在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：a.使结点P指向包含元素x的结点(即结点q的后件结点)。b.使结点q的指针域内容改为指向结点p。(a)原来的可利用栈与线性链表(b)从

44、可利用栈取得结点p,在线性链表中找到包含元素x的前一个结点q(c)p插入到q之后图1.23线性链表的插入* 只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。* 可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。* 线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。3.线性链表的删除(1)定义：在链式存储结构下的线性表中删除包含指定元素的结点。(2)删除过程在线性链表中寻找包含元素x的前一个结点，设该结点序号为q0将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的

45、结点p的指针指向的结点。将包含元素x的结点p送回可利用栈。此时，线性链表的删除运算完成。(c)将被删除的结点p送回可利用栈后图1.24线性链表的删除*在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。*当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将该空闲结点送回到可利用栈。三、循环链表前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。1 .循环链表的特点(1)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设

46、置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。2 .循环链表与线性单链表相比主要有以下两个方面的优点：(1)在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线性单链表做不到这一点。(2)由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。(a)非空循环链表(b)空循环链表图1.25循环链表的逻辑状态第六节树与二叉树一、树的基本概念定义：树(Tree)是一种简单的非

47、线性结构，树中所有数据元素之间的关系具有明显的层次特性。图1.26一般的树图1.27学校行政层次结构树图1.28书的层次结构树* 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。* 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。* 在树结构中，一个结点所拥有的后件个数称为该结点的度。* 在树中，所有结点中的最大的度称为树的度。* 树中的结点数=树中所有结点的度之和+10* 根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。在计算机中，可以用树结构来表示算术表达式。

48、用树来表示算术表达式的原则如下：表达式中的每一个运算符在树中对应一个结点，称为运算符结点。运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)。运算对象中的单变量均为叶子结点。* 表示一个表达式的表达式树是不唯一的。a*(b+e/d)+e*h-g*f(s,t,x+y)(a)表达式树之一(b)表达式树之二树在计算机中通常用多重链表表示。* 多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域(指针域)个数将随树中该结点的度而定。图1.30树链表中的结点结构二、二叉树及其基本性质1 .什么是二叉树二叉树具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两

49、棵子树，且分别称为该结点的左子树与右子树。*在二叉树中，每一个结点的度最大为2。图1.31二叉树例2 .二叉树的基本性质性质1在二叉树的第k层上，最多有2k-1(k>1)个结点。性质2深度为m的二叉树最多有2m-1个结点。211+22-1+2m-1=2m-1性质3在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。二叉树中总的结点数为n=no+n1+n2(1)进入分支的总数为mn=m+1(2)总的射出分支数应与总的进入分支数相等m=n+2n2(3)n=n1+2n2+1(4)n0+n1+n2=n1+2n2+1n0=n2+1性质4具有n个结点的二叉树，其深度至少为log2

50、n+1,其中log2n表示取log2n的整数部分。3 .满二叉树与完全二叉树(1)满二叉树定义：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。*在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。(a)深度为2的满二叉树(b)深度为3的满二叉树(c)深度为4的满二叉树图1.32满二叉树(2)完全二叉树定义：所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号

51、，则深度为mi且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。* 对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P,则其左分支下的子孙结点的最大层次或为P,或为P+1。图1.33完全二叉树* 满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下两个性质：性质5具有n个结点的完全二叉树的深度为log2n+1。性质6设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1,2,，n给结点进行编号，则对于编号为k(k=1,2,n

52、)的结点有以下结论：若k=1,则该结点为根结点，它没有父结点；若k>1,则该结点的父结点编号为INT(k/2)0若2k<n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。若2k+1&n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。三、二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。* 用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。* 用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树

53、的链式存储结构也称为二叉链表。图1.34二叉树存储结点的结构图1.35二叉树的链式存储结构* 对于满二叉树与完全二叉树来说，可以按层序进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。四、二叉树的遍历定义：二叉树的遍历是指不重复地访问二叉树中的所有结点。* 在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。1 .前序遍历(DLR定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，

54、最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。二叉树前序遍历的简单描述：若二叉树为空，则结束返回。否则：访问根结点；前序遍历左子树；前序遍历右子树。2 .中序遍历（LDR定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。下面是二叉树中序遍历的简单描述：若二叉树为空，则结束返回。否则：中序遍历左子树；访问根结点；中序遍历左子树。3 .后序遍历（LRD定义：所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左

55、子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。下面是二叉树后序遍历的简单描述：若二叉树为空，则结束返回。否则：后序遍历左子树；后序遍历右子树；访问根结点。前序序列：F,C,A,D,B,E,G,H,P中序序列：A,C,B,D,F,E,H,G,P后序序列：A,B,D,C,H,P,G,E,F* 如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。* 如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。* 但如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。例如，假设某二叉树的前序序列为DBACFEG中序序列为ABCDEF,G则二叉树的回复过程如下：图1.36二叉树的恢复过程第七节查找技术定义：查找是指在一个给定的数据结构中查找某个指定的元素。一、顺序查找顺序查找又称顺序搜索。其基本方法如下：（1）从线性表