全国计算机等级考试二级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)有穷性(Finitenes

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

6、几何？假设买母鸡I只、公鸡J只、小鸡KN。根据题意，粗略的列举算法描述 如下：FOR I=0 TO 100 STEP 1 DOFOR J=0 TO 100 STEP 1 DOFOR K=0 TO 100 STEP 1 DO IF ( (I+J+K=100) AND(3*I+2*J+0.5*K=100.0 ) ) THENPRINT I , J, K END共有三层循环，每层循环各需要循环101次，大约为100万次。优化后的算法FOR I=0 TO 33 STEP 1DOFOR J=0 TO 50-1.5*I STEP 1 DO K=100-I-J IF (3*I+2*J+0.5*K=100.0

7、 ) THEN PRINT I , J, K END共有两层循环，循环次数为2 .归纳法(1)基本思想通过列举少量的特殊情况，经过分析最后找出一般的关系。(2)特点归纳是一种抽象，即从特殊现象中找出一般关系。(3)使用由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得 到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过 精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。3 .递推(1)基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。(2)特点本质上属于归纳法，递推关系式往往是归纳的结果。(3)使用递推算法在数值计算中是极为常见

8、的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。4 .递归*(1)基本思想为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问 题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解 决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。(2)特点结构清晰，可读性强。(3)使用递归在可计算性理论和算法设计中占有很重要的地位。(4)分类直接递归(自己调用自己)和间接递归( P调用Q Q又调用P)。例1.2 编写一个过程，对于输入的参数 n,依次打印输出自然数1到n 非递归算法：wrt (int n )(FOR k=1 TO n STEP 1 DO

9、 PRINT kRETURN递归算法：wrt1 (int n )(IF (n乎0) THEN(wrtl (n-1 ) PRINT n)RETURN)5 .减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”， 是指重复“减半”的过程。例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,则根据以下原则

10、将原区间减半：若f (a) f (c) <0,则取原区间的前半部分；若f (b) f (c) <0,则取原区间的后半部分。最后判断减半后的区间长度是否已经很小：若|a- b卜£ ,则过程结束，取(a+b) /2为根的近似值；若|a- b| e ,则重复上述的减半过程。6 .回溯法(1)基本思想通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得 到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称 为回溯法。(2)特点在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列

11、举。对于这类问题，一种有效的方法是“试”。三、算法复杂度主要包括时间复杂度和空间复杂度。7 .算法的时间复杂度(1)定义执行算法所需要的计算工作量。(2)衡量标准通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关。综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量 =f (n)。(3)存在问题算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能 将所有可能情况下算法所执行的基本运算次数都列举出来。(4)解决方法平均性态(Average Behavior )用各种特

12、定输入下的基本运算次数的加权平均值来度量算法的工作量。最坏情况复杂性(Worst-Case Complexity)规模为n时，算法所执行的基本运算的最大次数。w)=max«(X)x D n例1.4 采用顺序搜索法，在长度为n的一维数组中查找值为 x的元素。即 从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为 x与数组元素的比较。(1)平均性态分析设被查项x在数组中出现的概率为 q, i=n+1表示x不在数组中的情况(2)最坏性态分析W(n) =maxti | l <i <n+1=n注：当算法的计算工作量与输入无关时，即当规模为n时，在所有可能的输入下，算法所执行

13、的基本运算次数是一定的，此时有 A(n)=W(n) 08 .算法的空间复杂度定义：执行这个算法所需要的内存空间。(1)算法程序所占的空间；(2)输入的初始数据所占的存储空间；(3)算法执行过程中所需要的额外空间。*如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。*在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技 术，以便尽量减少不必要的额外空间。第二节数据结构的基本概念数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；(2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的

14、 存储结构；(3)对各种数据结构进行的运算。讨论以上问题的目的：(1)提高数据处理的速度；(2)尽量节省在数据处理过程中所占用的计算机存储空间。一、什么是数据结构定义：数据结构是指相互有关联的数据元素的集合。数据元素具有广泛的含义：描述一年四季的季节名：春、夏、秋、冬表示数值的各个数：18、11、35、23、16表示家庭成员的各成员名：父亲、儿子、女儿数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、 查找、更改等运算，也包括对数据元素进行分析。*作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在 具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种

15、关 系反映了该集合中的数据元素所固有的一种结构。1 .数据的逻辑结构(1)定义反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系。(2)数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D;二是D上的关系，它反映了 D中各数据元素之间的前后件关系，通常记为R;即一个数据结构可以表示成 B= ( D, R)。例1.5 一年四季的数据结构可以表示成B= (D, R)D=春，夏，秋，冬R=(春，夏)，(夏，秋)，(秋，冬) 例1.6 家庭成员数据结构可以表示成B= (D, R)D=父亲，儿子，女儿R=(父亲，儿子)，(父亲，

16、女儿) 例1.7 n 维向量X= (x% X2,，xn)也是一种数据结构。即 X= (D, R),其中数据元素的集合为：D=x1, x2,，xn关系为：R= (x1, x2) , (x2, x3),，(xn-1 , xn) * 对于一些复杂的数据结构来说，它的数据元素可以是另一种数据结构。例如，mXn的矩阵是一个数据结构。在这个数据结构中，矩阵的每一行Ai= (an , ai2,，an) , i=1 , 2,，m可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为D=A1, A2,，AmD上的一个关系为R= (Ai, A) ,(A2, A),，(A, A+1),，(Am-1, Am)

17、显然，数据结构A中的每一个数据元素：又是另一个数据结构D上的一个关系为：R=，ai2),2.数据的存储结构A (i=1 , 2,，m),即数据元素的集合为：D=ai1 , ai2,，ainai2, ai3) , ,，(aj , ai, j+1) , ,，(ai, n-1, a) 定义：数据的逻辑结构在计算机存储空间中的存放形式。* 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。* 在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据 元素之间的前后件关系的信息。* 常用的存储结构有顺序、链接、索引等存储结构。* 采用不同的存储结构，其数

18、据处理的效率是不同的。二、数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。(1)对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；(2)对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件 结点，有时箭头可省去。图1-1 一年四季数据结构的图形表示图1-2家庭成员间辈分关系数据结构的图形表示例1.8 用图形表示数据结构 B=(D, R),其中D=di | 1< i <7_d 1, cb, da, ch, ck, de, cbR= (d1,da),(d1,d7),( d2,&) ,(da,de),

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

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

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

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

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

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

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

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

27、有记忆作用。* 往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元 素)称为退栈运算。计算机系统在处理时要用一个线性表来动态记忆调用过程中的路径，其基 本原则如下：(1)在开始执行程序前，建立一个线性表，初始状态为空；(2)发生调用时，将当前调用的返回点地址插入到线性表的末尾；(3)当遇到从某个子程序返回时，其返回点地址从线性表的末尾取出(即 删除线性表的最后一个元素)。图1.9 栈不'意图图1.8中给出了具有嵌套调用关系的五个程序，其中主程序要调用子程序SUB1 SUB1要调用子程序SUB2 SUB2要调用子程序SUB3 SUB谍调用子程序 SUB4 SUB4不再调用其

28、他子程序了。图1.8 主程序与子程序之间的调用关系图1.8中五个程序在执行过程中的调用顺序以及线性表中元素变化的情况 如下：(1)主程序开始执行前，建立一个空线性表。即线性表的状态为()o(2)开始执行主程序MAIN当要调用子程序SUB1时，先将本次调用的返回点地址A插入到线性表的末尾。此时，线性表的状态为(A) o(3)开始调用执行子程序 SUB1当要调用子程序 SUB2时，先将本次调用 的返回点地址B插入到线性表的末尾。止匕时,线性表的X犬态为(A, B)。(4)开始调用执行子程序 SUB2当要调用子程序 SUB3时，先将本次调用的返回点地址C插入到线性表的末尾。此时，线性表的状态为(A,

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

30、0(7)返回到子程序SUB3的D处继续执行，执行完子程序 SUB3后要返回到 子程序SUB2的地址C处。其中返回点地址 C取自线性表的最后一个元素。取出 C后，线性表的状态为(A, B)。(8)返回到子程序SUB2的C处继续执行，执行完子程序 SUB2后萋返回到 子程序SUB1的地址B处。其中返回点地址、取自线性表的最后一个元素。取出 B后，线性表的状态为(A) 0(9)返回到子程序SUB1的B处继续执行，执行完子程序 SUB1后要返回到 主程序MAIN的地址A处。其中返回点地址 A取自线性表最后一个元素。取出 A 后，线性表变空，即线性表的状态为()o(10)返回到主程序 MAIN的A处继续

31、执行，直到主程序 MAIN执行完成。由上述逐步返回的过程可以看出，当由子程序返回到上一个调用程序时， 需要从线性表的末尾取出返回点地址，即从线性表中删除最后一个元素，而这 种对线性表的删除操作也是不需要移动线性表中其他数据元素的。2 .栈的顺序存储及其运算图1.10 (a)是容量为10的栈顺序存储空间，栈中已有 6个元素；图1.10 (b)与图1.10 (c)分别为入栈与退栈后的状态。图1.10 栈在顺序存储结构下的运算在栈的顺序存储空间 S (1:成中，S ( bottom )通常为栈底元素(在栈非空 的情况下)，S (top )为栈顶元素。top=0表示栈空；top=m表示栈满。栈的基本运

32、算有三种：入栈、退栈与读栈顶元素。(1)入栈运算入栈运算是指在栈顶位置插入一个新元素。操作过程如下：首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则 说明栈空间已满，不可能再进行入栈操作(这种情况称为栈“上溢”错误)， 算法结束。然后将栈顶指针进一(即top加1)。最后将新元素x插入栈顶指针指向的位置。(2)退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为 00如果是，则说明栈空，不可能进行退栈操作(这种情况称为栈“下溢”错误)，算法结束。然后将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量。最后将栈顶指针退一(即 top减1)。(3)

33、读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为 00如果是，则说明栈空，读不到栈顶元素，算 法结束。然后将栈顶元素赋给指定的变量 y o必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此， 在这个运算中栈顶指针不会改变。二、队列及其基本运算1 .什么是队列在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：初始时线性表为空；当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用 户程序执行。由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性 表

34、的末尾，并且又总是从线性表的头部取出(删除)元素。这种线性表称为队 列。定义：队列(Queue是指允许在一端进行插入、而在另一端进行删除的线 性表。* 允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也 称为队头），通常也用一个排头指针（Front ）指向排头元素的前一个位置。* 在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后 插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表，它体现了 “先来先服务”的原则。* 在队列中，队尾指针rear与排头指针front共同

35、反映了队列中元素动态 变化的情况。图1.11 具有6个元素的队列示意图图1.12 队列运算示意图2 .循环队列及其运算定义：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位 置，形成逻辑上的环状空间，供队列循环使用。* 在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front 指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。* 循环队列的初始状态为空，即rear=front=m ,如图1.13所示。图1.13 循环队列存储空间示意图循环队列主要有两种基本运算：入队运算与退队运算。每进行

36、一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=1 0图1.14 循环队列运算例* 当循环队列满时有front=rear ,而当循环队列空时也有 front=rear 。即 在循环队列中，当front=rear 时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一 个标志s, s值的定义如下：由此可以得出队列空与队列满的条件如下：队列空的条件为s=0；队列满的条件为s=1且front=rear 。假设循环队列的初始状态为空，即：s=0,且

37、front=rear=m。（1）入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此 时算法结束。然后将队尾指针进一（即 rear=rear+1 ）,并当rear=m+1时置rear=1 。最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。（2）退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操 作过程如下：首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。

38、然后将排头指针进一 （即front=front+1 ），并当front=m+1时置front=1再将排头指针指向的元素赋给指定的变量最后判断退队后循环队列是否为空。当front=rear 时置循环队列空标志（即 s=0） 0第五节线性链表一、线性链表的基本概念*线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表 或长度固定的线性表，采用顺序存储结构的优越性更为突出。*线性表的顺序存储结构存在的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个 元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过 程中需要移动大量的数据元素。（2）当为一个线性

39、表分配顺序存储空间后，如果出现线性表的存储空间已 满，但还需要插入新的元素时，就会发生“上溢”错误。（3）线性表的顺序存储结构不便于对存储空间的动态分配。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存 储结构，而是采用下面要介绍的链式存储结构。* 假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称 为存储结点，简称结点。* 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元 素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向 该结点的前一个或后一个结点（即前件或后件）。* 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据

40、结点的 存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系 是由指针域来确定的。* 链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链 式结构表示较复杂的非线性结构时，其指针域的个数要多一些。1 .线性链表定义：线性表的链式存储结构称为线性链表。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面 要存储各数据元素之间的前后件关系。图1.15 线性链表的存储空间为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块， 每一小块占若干字节，通常称这些小块为存储结点。图1.16 线性链表的一个存储结点* 在线性链表中，用一个专门的指针HEA讨旨

41、向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。图1.17 线性链表的逻辑结构* 在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各 结点在存储空间中的位置关系与逻辑关系也不一致。* 当HEAD= NULL（或0）时称为空表。图1.18 线性链表例* 在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结 点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些 问题的处理会带来不便，因为在这种链接

42、方式下，由某一个结点出发，只能找 到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结 点设置两个指针，一个称为左指针（Llink ）,用以指向其前件结点；另一个称 为右指针（Rlink ）,用以指向其后件结点。这样的线性链表称为双向链表。图1.19 双向链表示意图2 .带链的栈栈也是线性表，也可以采用链式存储结构。图1.20 带链的栈在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储 结点，这种带链的栈称为可利用栈。图1.21 可利用栈及其运算与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化。即建立一个空

43、栈的顺序存储空间。入栈运算。是指在栈顶位置插入一个新元素。退栈运算。是指取出栈顶元素并赋给一个指定的变量。读栈顶元素。是指将栈顶元素赋给一个指定的变量。3 .带链的队列队列也是线性表，也可以采用链式存储结构。图1.22 带链的队列及其运算与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化。即建立一个空队列的顺序存储空间。入队运算。是指在循环队列的队尾加入一个新元素。退队运算。是指在循环队列的排头位置退出一个元素并赋给指定的变量。二、线性链表的基本运算线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合

44、并成一个线性链表将一个线性链表按要求进行分解。逆转线性链表。复制线性链表。线性链表的排序。线性链表的查找。1 .在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值 x的前一个结点p的基本方法如下:从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下 一个结点的数据域为x为止。因此，由这种方法找到的结点 p有两种可能：*当线性链表中存在包含元素 x的结点时，则找到的p为第一次遇到的包含 元素x的前一个结点序号；*当线性链表中不存在包含元素 x的结点时，则找到的p为线性链表中的最 后一个结点号。2 .线性链表的插入(1)定义在链式存储结构下的线性表中插入一个新元素。(2)插入过

45、程从可利用栈取得一个结点， 设该结点号为p (即取得结点的存储序号存放在变量p中)，并置结点p的数据域为插入的元素值 b0在线性链表中寻找包含元素 x的前一个结点，设该结点的存储序号为 q最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个 结点的指针域内容：a.使结点P指向包含元素x的结点(即结点q的后件结点)。b.使结点q的指针域内容改为指向结点 p。(a)原来的可利用栈与线性链表(b)从可利用栈取得结点 p,在线性链表中找到包含元素 x的前一个结点q(c) p插入到q之后图1.23 线性链表的插入* 只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点， 不会发生“上

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

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

48、的指针构成了一个环状链。2 .循环链表与线性单链表相比主要有以下两个方面的优点：(1)在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发 访问到表中其他所有的结点。线性单链表做不到这一点。(2)由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链 表中至少有一个结点存在，从而使空表与非空表的运算统一。(a)非空循环链表(b)空循环链表图1.25 循环链表的逻辑状态第六节树与二叉树一、树的基本概念定义：树(Tree)是一种简单的非线性结构，树中所有数据元素之间的关 系具有明显的层次特性。图1.26 一般的树图1.27 学校行政层次结构树图1.28 书的层次结构树* 在树结构中，

49、每一个结点只有一个前件，称为父结点，没有前件的结点只 有一个，称为树的根结点，简称为树的根。* 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。 没有后件的结点称为叶子结点。* 在树结构中，一个结点所拥有的后件个数称为该结点的度。* 在树中，所有结点中的最大的度称为树的度。* 树中的结点数=树中所有结点的度之和+1 0* 根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大 层次称为树的深度。在计算机中，可以用树结构来表示算术表达式。用树来表示算术表达式的原则如下：表达式中的每一个运算符在树中对应一个结点，称为运算符结点。运算符的每一个运算对象在树中为该运算符结点的

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

51、树的基本性质性质1在二叉树的第k层上，最多有2k-1 (k>1)个结点。性质2深度为m的二叉树最多有2m-1个结点。21-1+22-1+2m-1=221性质3在任意一棵二叉树中，度为 0的结点(即叶子结点)总是比度为 2 的结点多一个。二叉树中总的结点数为n=n 0+n1+n2 (1)进入分支的总数为 m n=m+1 (2)总的射出分支数应与总的进入分支数相等m=n+2n2 (3)n=n1+2n2+1 (4)n0+n1+n2=n1+2n2+1n0=1+1性质4具有n个结点的二叉树，其深度至少为log 2n+1 ,其中log 2n表 示取log 2n的整数部分。3 .满二叉树与完全二叉树(

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

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

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

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