作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
2017年9月全国计算机等级考试《二级C＋＋语言程序设计》【教材精讲＋真题解析】讲义与视频课程【42小时高清视频】试读：
视频讲解教师简介
白香君，北京航空航天大学数学与系统科学学院信息与计算科学专业硕士，在校期间多次参与重大课题的研究，并曾先后在中科院软件所、联想研究院、中科院自动化所、中科曙光从事软件开发相关的实习工作，具有丰富的计算机理论基础知识和软件开发经验。
授课特点：思路清晰，基础知识扎实，讲解生动丰富。
张凯，计算机应用技术专业讲师，信息与通信处理专业硕士，主要担任计算机编程语言(C、C++、Java、SQL)、网站开发(ASP.NET)、软件开发(MFC)、网络技术方向的研究。现执教于北京科技职业学院，高校教龄6年，并在多家辅导机构、高等院校讲述计算机应用相关课程，教学经验丰富，理论及实践功底雄厚。所授课程主要有：计算机高级职称系列课程、《程序设计导论》、《C++面向对象程序设计》、《MFC开发》、《多媒体通信技术》、《SQL数据库开发》、《软件测试》等。
授课特点：讲课情绪饱满，在教学中善于利用教学技巧，课堂教学结构组织严密、搭配合理，有条不紊。
视频讲解教师简介
教材精讲部分[视频讲解]
第一部分 公共基础知识[视频讲解]
考试形式1．公共基础知识不单独考试，与其他二级科目组合在一起,作为二级科目考核内容的一部分。
2．考试方式为上机考试，10道选择题，占10分。大纲基本要求
1．掌握算法的基本概念。
2．掌握基本数据结构及其操作。
3．掌握基本排序和查找算法。
4．掌握逐步求精的结构化程序设计方法。
5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。
6．掌握数据库的基本知识，了解关系数据库的设计。知识点分布
1．数据结构与算法
2．程序设计基础
3．软件工程基础
4．数据库设计基础
第1章 数据结构与算法[视频讲解]
本章考点
1．算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5．线性单链表、双向链表与循环链表的结构及其基本运算。
6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7．顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。第一节 算 法
一、算法的基本概念
1．算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。
*算法不等于程序，也不等于计算方法。
2．算法的基本特征（1）可行性（Effectiveness）
①算法中的每一个步骤必须能够实现。
②算法执行的结果要能够达到预期的目的。（2）确定性（Definiteness）
算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性（Finiteness）
算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
*算法的有穷性还应包括合理的执行时间（4）拥有足够的情报
①输入是否足够并正确，输出是否合理。
②初始状态是否正确。
二、算法设计基本方法
1．列举法（1）基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）特点
简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。（3）使用
将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。
例1.1 今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？
假设买母鸡I只、公鸡J只、小鸡K只。根据题意，粗略的列举算法描述如下：
FOR I=0 TO 100 STEP 1 DO
FOR J=0 TO 100 STEP 1 DO
FOR K=0 TO 100 STEP 1 DO
{
IF（（I+J+K==100）AND（ 3*I+2*J+0.5*K==100.0））THEN
PRINT I，J，K
}
END
共有三层循环，每层循环各需要循环101次，大约为100万次。
优化后的算法
FOR I=0 TO 33 STEP 1DO
FOR J=0 TO 50-1.5*I STEP 1 DO
{
K=100-I-J
IF（3*I+2*J+0.5*K==100.0）THEN
PRINT I，J，K
}
END
共有两层循环，循环次数为
2．归纳法（1）基本思想
通过列举少量的特殊情况，经过分析最后找出一般的关系。（2）特点
归纳是一种抽象，即从特殊现象中找出一般关系。（3）使用
由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
3．递推（1）基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（2）特点
本质上属于归纳法，递推关系式往往是归纳的结果。（3）使用
递推算法在数值计算中是极为常见的。但
是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
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 PRINT k
RETURN
}
递归算法：
wrt1（int n）
{
IF（n≠0）THEN
{
wrt1（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）是否为0。
若f（c）=0，则说明C即为所求的根，求解过程结束；
如果f（c）≠0，则根据以下原则将原区间减半：
若f（a）f（c）<0，则取原区间的前半部分；
若f（b）f（c）<0，则取原区间的后半部分。
最后判断减半后的区间长度是否已经很小：
若|a-b|<ε，则过程结束，取（a+b）／2为根的近似值；
若|a-b|≥ε，则重复上述的减半过程。
6．回溯法（1）基本思想
通过对问题的分析，找出一个解决问题的线
索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。（2）特点
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤,并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。
三、算法复杂度
主要包括时间复杂度和空间复杂度。
1．算法的时间复杂度（1）定义
执行算法所需要的计算工作量。（2）衡量标准
通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
算法所执行的基本运算次数还与问题的规模有关。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n）。（3）存在问题
算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。（4）解决方法
①平均性态（Average Behavior）
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
②最坏情况复杂性(Worst-Case Complexity)
规模为n时，算法所执行的基本运算的最大次数。W（n）={t（x）}
例1.4 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。（1）平均性态分析
设被查项x在数组中出现的概率为q，i=n+1表示x不在数组中的情况 （2）最坏性态分析W（n）=max{t | l≤i≤n+1}=ni
注：当算法的计算工作量与输入无关时，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n)=W(n)。
2．算法的空间复杂度
定义：执行这个算法所需要的内存空间。（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中所需要的额外空间。
*如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。
*在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。第二节 数据结构的基本概念
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
讨论以上问题的目的：（1）提高数据处理的速度；（2）尽量节省在数据处理过程中所占用的计算机存储空间。
一、什么是数据结构
定义：数据结构是指相互有关联的数据元素的集合。
数据元素具有广泛的含义：
描述一年四季的季节名：春、夏、秋、冬
表示数值的各个数：18、11、35、23、16…
表示家庭成员的各成员名：父亲、儿子、女儿
数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
*作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。
1．数据的逻辑结构（1）定义
反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：
①表示数据元素的信息；
②表示各数据元素之间的前后件关系。（2）数据的逻辑结构有两个要素：
一是数据元素的集合，通常记为D；
二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R；
即一个数据结构可以表示成B=（D，R）。
例1.5 一年四季的数据结构可以表示成
B=（D，R）
D={春，夏，秋，冬}
R={（春，夏），（夏，秋），（秋，冬）}
例1.6 家庭成员数据结构可以表示成
B=（D，R）
D={父亲，儿子，女儿}
R={（父亲，儿子），（父亲，女儿）}
例1.7 n维向量X=（x，x，…，x）也是一种数据结构。即12nX=（D，R），
其中数据元素的集合为：D={x1，x2，…，xn}
关系为：R={（x1，x2），（x2，x3），…，（xn-1，xn）}
*对于一些复杂的数据结构来说，它的数据元素可以是另一种数据结构。
例如，m×n的矩阵
是一个数据结构。在这个数据结构中，矩阵的每一行Ai=（a，a，…，a），i=1，2，…，mi1i2in
可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为D={A1，A2，…，Am}
D上的一个关系为R={（A，A），（A，A），…，（A，A），…，（A，A）}1223ii+1m-1m
显然，数据结构A中的每一个数据元素：
A（i=1，2，…，m）i
又是另一个数据结构,即数据元素的集合为：D={a，a，…，a}ii1i2in
D上的一个关系为：iR={（a，a），（a，a），…，（a，a），…，（a，a）}ii1i2i2i3iji，j+1i，n-1in
2．数据的存储结构
定义：数据的逻辑结构在计算机存储空间中的存放形式。
*各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
*在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
*常用的存储结构有顺序、链接、索引等存储结构。
*采用不同的存储结构，其数据处理的效率是不同的。
二、数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。图1-1一年四季数据结构的图形表示图 1-2家庭成员间辈分关系数据结构的图形表示
例1.8 用图形表示数据结构B=(D，R)，其中D={d|1≤i≤7}_{d，d，d，d，d，d，d}i1234567R={（d，d），（d，d），（d，d），（d，d），（d，d）}1317243645
在数据结构中，没有前件的结点称为根结
点；没有后件的结点称为终端结点（也称为叶子结点）。
图1.3 例1.8数据结构的图形表示
三、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。
*在一个线性结构中插入或删除任何一个结点后还应是线性结构。图1.4 不是线性结构的数据结构特例
如果一个数据结构不是线性结构，则称之为非线性结构。
*线性结构与非线性结构都可以是空的数据结构。
*一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。
*如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。第三节 线性表及其顺序存储结构
一、线性表的基本概念
线性表（Linear List）是最简单、最常用的一种数据结构。
如：一个n维向量、矩阵，学生情况登记表；
综上所述，线性表是由n（n≥0）个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a1，a2，…，ai，…，an）其中ai（i=1，2，…，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些结构特征：（1）有且只有一个根结点a它无前件；1（2）有且只有一个终端结点a，它无后件；n（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
*线性表中结点的个数n称为线性表的长度。
*当n=0时，称为空表。
二、线性表的顺序存储结构
1．特点（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
图1.5 线性表的顺序存储结构
*在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
*在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
2．在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几种：（1）在线性表的指定位置处加入一个新的元素（即线性表的插入）；（2）在线性表中删除指定的元素（即线性表的删除）；（3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）；（4）对线性表中的元素进行整序（即线性表的排序）；（5）按要求将一个线性表分解成多个线性表（即线性表的分解）；（6）按要求将多个线性表合并成一个线性表（即线性表的合并）；（7）复制一个线性表（即线性表的复制）；（8）逆转一个线性表(即线性表的逆转)等。
三、顺序表的插入运算
例1.9 图1.6（a）为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素（即18）之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。图1.6 线性表在顺序存储结构下的插入
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（i表示在第i个元素之前插入），插入新元素。则插入的过程如下：（1）首先处理以下三种异常情况：
*当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束；
*当i>n时，认为在最后一个元素之后（第n+1个元素之前）插入；
*当i<1时，认为在第1个元素之前插入。（2）然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。
*由于大多数情况下需要移动数据元素，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。
四、顺序表的删除运算
例1.10 图1.7（a）为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素（即删除元素29）。再删除线性表中的第6个元素。
图1.7 线性表在顺序存储结构下的删除
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素）。则删除的过程如下：（1）首先处理以下两种异常情况：
*当线性表为空（即n=0）时错误，不能进行删除，算法结束；
*当i<1或i>n时，错误，不能进行删除，算法结束；（2）删除线性表中的第i个元素；（3）然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置；（4）最后将线性表的长度减小1。
*由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适
的，因为顺序存储的结构比较简单。
*但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。第四节 栈和队列
一、栈及其基本运算
1．什么是栈
定义：限定在一端进行插入与删除的线性表
*在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。用指针top来指示栈顶的位置，用指针bottom指向栈底。
*栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
*栈具有记忆作用。
*往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。
计算机系统在处理时要用一个线性表来动态记忆调用过程中的路径，其基本原则如下：（1）在开始执行程序前，建立一个线性表，初始状态为空；（2）发生调用时，将当前调用的返回点地址插入到线性表的末尾；（3）当遇到从某个子程序返回时，其返回点地址从线性表的末尾取出（即删除线性表的最后一个元素）。图1.9 栈示意图
图1.8中给出了具有嵌套调用关系的五个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序了。
图1.8 主程序与子程序之间的调用关系
图1.8中五个程序在执行过程中的调用顺序以及线性表中元素变化的情况如下：（1）主程序开始执行前，建立一个空线性表。即线性表的状态为（）。（2）开始执行主程序MAIN。当要调用子程序SUB1时，先将本次调用的返回点地址A插入到线性表的末尾。此时，线性表的状态为（A）。（3）开始调用执行子程序SUB1。当要调用子程序SUB2时，先将本次调用的返回点地址B插入到线性表的末尾。此时,线性表的状态为（A，B）。（4）开始调用执行子程序SUB2。当要调用子程序SUB3时，先将本次调用的返回点地址C插入到线性表的末尾。此时，线性表的状态为(A,B,C)。（5）开始调用执行子程序SUB3。当要调用子程序SUB4时，先将本次调用的返回点地址D插入到线性表的末尾。此时，线性表的状态为（A，B，C，D）。
由上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址插入到线性表的末尾，而这种对线性表的插入操作是不需要移动线性表中原有元素的。并且，各返回点地址在线性表中的存放顺序恰好是调用顺序。（6）开始调用执行子程序SUB4。由于子程序SUB4不再调用其他子程序，执行完子程序SUB4后要返回到子程序SUB3的地址D处。其中返回点地址D取自线性表的最后一个元素。取出D后，线性表的状态为（A，B，C）。（7）返回到子程序SUB3的D处继续执行，执行完子程序SUB3后要返回到子程序SUB2的地址C处。其中返回点地址C取自线性表的最后一个元素。取出C后，线性表的状态为（A，B）。（8）返回到子程序SUB2的C处继续执行，执行完子程序SUB2后萋返回到子程序SUB1的地址B处。其中返回点地址、取自线性表的最后一个元素。取出B后，线性表的状态为（A）。（9）返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A取自线性表最后一个元素。取出A后，线性表变空，即线性表的状态为（）。（10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完成。
由上述逐步返回的过程可以看出，当由子程序返回到上一个调用程序时，需要从线性表的末尾取出返回点地址，即从线性表中删除最后一个元素，而这种对线性表的删除操作也是不需要移动线性表中其他数据元素的。
2．栈的顺序存储及其运算
图1.10（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1.10（b）与图1.10（c）分别为入栈与退栈后的状态。
图1.10 栈在顺序存储结构下的运算
在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素(在栈非空的情况下)，S（top）为栈顶元素。
top=0表示栈空；top=m表示栈满。
栈的基本运算有三种：入栈、退栈与读栈顶元素。（1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
①首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
②然后将栈顶指针进一（即top加1）。
③最后将新元素x插入栈顶指针指向的位置。（2）退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
③最后将栈顶指针退一（即top减1）。（3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
②然后将栈顶元素赋给指定的变量y。
必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。
二、队列及其基本运算
1．什么是队列
在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：
①初始时线性表为空；
②当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；
③当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。
由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。
定义：队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。
*允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（Front）指向排头元素的前一个位置。
*在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。
*在队列中，队尾指针 rear与排头指针front共同反映了队列中元素动态变化的情况。
图1.11 具有6个元素的队列示意图图1.12 队列运算示意图
2．循环队列及其运算
定义：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
*在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
*循环队列的初始状态为空，即rear=front=m，如图1.13所示。
图1.13 循环队列存储空间示意图
循环队列主要有两种基本运算：入队运算与退队运算。
每进行一次入队运算，队尾指针就进一。当队尾指针 rear=m+1时，则置rear=1。
每进行一次退队运算，排头指针就进一。当排头指针 front=m+1时，则置front=1。
图1.14 循环队列运算例
*当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。
在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：
由此可以得出队列空与队列满的条件如下：
队列空的条件为s=0；
队列满的条件为s=1且front=rear。
假设循环队列的初始状态为空，即：s=0，且front=rear=m。（1）入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
①首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
②然后将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1。
③最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。（2）退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
①首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
②然后将排头指针进一（即front=front+1），并当front=m+1时置front=1。
③再将排头指针指向的元素赋给指定的变量
④最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（即s=0）。第五节 线性链表
一、线性链表的基本概念
*线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。
*线性表的顺序存储结构存在的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。（2）当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。（3）线性表的顺序存储结构不便于对存储空间的动态分配。
因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。
*假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
*在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
*在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
*链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。
1．线性链表
定义：线性表的链式存储结构称为线性链表。
为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。
图1.15 线性链表的存储空间
为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。图1.16 线性链表的一个存储结点
*在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。
图1.17 线性链表的逻辑结构
*在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。
*当HEAD= NULL（或0）时称为空表。
图1.18 线性链表例
*在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。
因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。
为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为双向链表。图1.19 双向链表示意图
2．带链的栈
栈也是线性表，也可以采用链式存储结构。图1.20 带链的栈
在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。图1.21 可利用栈及其运算
与顺序栈一样，带链栈的基本操作有以下几个：
试读结束[说明：试读内容隐藏了图片]