《二年级公共基础知识教材精讲完整版.pdf》由会员分享，可在线阅读，更多相关《二年级公共基础知识教材精讲完整版.pdf（243页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 二年级公共基础知识教材精讲 HUA system office room【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】目 录 视频讲解教师简介.教材精讲部分视频讲解.第 1 章 数据结构与算法视频讲解.1.1 算 法.1.2 数据结构的基本概念.1.3 线性表及其顺序存储结构.1.4 栈和队列.1.5 线性链表.1.6 树与二叉树.1.7 查找技术.2018 年 9 月全国计算机等级考试二级公共基础知识【教材精讲真题解析】讲义与视频课程 最新资料，WORD 格式，可编辑修改！1.8 排序技术.第 2 章 程序设计基础视频讲解.2.1 程序设计方法与风格.2.2 结构化程序设
2、计.2.3 面向对象的程序设计.第 3 章 软件工程基础视频讲解.3.1 软件工程基本概念.3.2 结构化分析方法.3.3 结构化设计方法.3.4 软件测试.3.5 程序的调试.第 4 章 数据库设计基础视频讲解.4.1 数据库系统的基本概念.4.2 数据模型.4.3 关系代数.4.4 数据库设计与管理.真题解析部分.全国计算机等级考试二级公共基础知识真题精选（一）.全国计算机等级考试二级公共基础知识真题精选（二）.考试形式 1公共基础知识不单独考试，与其他二级科目组合在一起,作为二级科目考核内容的一部分。2考试方式为上机考试，10 道选择题，占 10 分。大纲基本要求 1掌握算法的基本概念。
3、2掌握基本数据结构及其操作。3掌握基本排序和查找算法。4掌握逐步求精的结构化程序设计方法。5掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6掌握数据库的基本知识，了解关系数据库的设计。知识点分布 1数据结构与算法 2程序设计基础 3软件工程基础 4数据库设计基础 第 1 章 数据结构与算法视频讲解 1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树与二叉树 1.7 查找技术 1.8 排序技术 本章考点 1算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2数据结构的定义；数据的逻辑结构与存储
4、结构；数据结构的图形表示；线性结构与非线性结构的概念。3线性表的定义；线性表的顺序存储结构及其插入与删除运算。4栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5线性单链表、双向链表与循环链表的结构及其基本运算。6树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。1.1 算 法 一、算法的基本概念 1算法的定义 算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。*算法不等于程序，也不等于计算方法。2算法的基本特征 （1）可行性（Effectiveness）算法中的每一
5、个步骤必须能够实现。算法执行的结果要能够达到预期的目的。（2）确定性（Definiteness）算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性（Finiteness）算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。*算法的有穷性还应包括合理的执行时间 （4）拥有足够的情报 输入是否足够并正确，输出是否合理。初始状态是否正确。二、算法设计基本方法 1列举法 （1）基本思想 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）特点 简单，方便用计算机进行
6、大量列举；情况较多时，工作量将会很大。（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 共有三层循环，每层循
7、环各需要循环 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）使用 由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测
8、得不到证实或最后证明猜测是错的，也是常有的事。3递推 （1）基本思想 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（2）特点 本质上属于归纳法，递推关系式往往是归纳的结果。（3）使用 递推算法在数值计算中是极为常见的。但 是，对于数值型的递推算法必须要注意数值计算的稳定性问题。4递归*（1）基本思想 为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。（2）特点 结构清晰，可读性强。（3）使用 递归在可计算性理论和算法设计中占有很重要的
9、地位。（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（n0）THEN wrt1（n-1）PRINT n RETURN 5减半递推技术 所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。例 1.3 设方程 f（x）=0 在区间a，b上有实根，且 f（a）与 f（b）异号。利用二分法求该方程在区间a，b上
10、的一个实根。用二分法求方程实根的减半递推过程如下：首先取给定区间的中点 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|n 时，认为在最后一个元素之后（第 n+1 个元素之前）插入；*当 i1 时，认为在第 1 个元素之前插入。（2）然后从最后一个元素开始，直到第 i 个元素，其中每一个元素均往后移动一个位置。（3）最后将新元素插入到第 i 个位置，并
11、且将线性表的长度增加 1。*由于大多数情况下需要移动数据元素，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。四、顺序表的删除运算 例 1.10 图 1.7（a）为一个长度为 8 的线性表顺序存储在长度为 10 的存储空间中。现在要求删除线性表中的第 1 个元素（即删除元素 29）。再删除线性表中的第 6 个元素。图 1.7 线性表在顺序存储结构下的删除 假设线性表的存储空间为 V（1：m），线性表的长度为 n（nm），删除的位置为 i（表示删除第 i 个元素）。则删除的过程如下：（1）首先处理以下两种异常情况：*当线性表为空（即 n=0）时错误，不能进行删除，算法结束；*当 in
12、 时，错误，不能进行删除，算法结束；（2）删除线性表中的第 i 个元素；（3）然后从第 i+1 个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置；（4）最后将线性表的长度减小 1。*由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适 的，因为顺序存储的结构比较简单。*但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。1.4 栈和队列 一、栈及其基本运算 1什么是栈 定义：限定在一端进行插入与删除的线性表 *在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另
13、一端称为栈底。用指针 top 来指示栈顶的位置，用指针 bottom 指向栈底。*栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。*栈具有记忆作用。*往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。计算机系统在处理时要用一个线性表来动态记忆调用过程中的路径，其基本原则如下：（1）在开始执行程序前，建立一个线性表，初始状态为空；（2）发生调用时，将当前调用的返回点地址插入到线性表的末尾；（3）
14、当遇到从某个子程序返回时，其返回点地址从线性表的末尾取出（即删除线性表的最后一个元素）。图 1.9 栈示意图 图 1.8 中给出了具有嵌套调用关系的五个程序，其中主程序要调用子程序 SUB1，SUB1 要调用子程序 SUB2，SUB2 要调用子程序 SUB3，SUB3 要调用子程序 SUB4，SUB4 不再调用其他子程序了。图 1.8 主程序与子程序之间的调用关系 图 1.8 中五个程序在执行过程中的调用顺序以及线性表中元素变化的情况如下：（1）主程序开始执行前，建立一个空线性表。即线性表的状态为（）。（2）开始执行主程序 MAIN。当要调用子程序 SUB1 时，先将本次调用的返回点地址 A
15、插入到线性表的末尾。此时，线性表的状态为（A）。（3）开始调用执行子程序 SUB1。当要调用子程序 SUB2 时，先将本次调用的返回点地址B 插入到线性表的末尾。此时,线性表的状态为（A，B）。（4）开始调用执行子程序 SUB2。当要调用子程序 SUB3 时，先将本次调用的返回点地址C 插入到线性表的末尾。此时，线性表的状态为(A,B,C)。（5）开始调用执行子程序 SUB3。当要调用子程序 SUB4 时，先将本次调用的返回点地址D 插入到线性表的末尾。此时，线性表的状态为（A，B，C，D）。由上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址插入到线性表的末尾，而这种对
16、线性表的插入操作是不需要移动线性表中原有元素的。并且，各返回点地址在线性表中的存放顺序恰好是调用顺序。（6）开始调用执行子程序 SUB4。由于子程序 SUB4 不再调用其他子程序，执行完子程序SUB4 后要返回到子程序 SUB3 的地址 D 处。其中返回点地址 D 取自线性表的最后一个元素。取出 D 后，线性表的状态为（A，B，C）。（7）返回到子程序 SUB3 的 D 处继续执行，执行完子程序 SUB3 后要返回到子程序 SUB2的地址 C 处。其中返回点地址 C 取自线性表的最后一个元素。取出 C 后，线性表的状态为（A，B）。（8）返回到子程序 SUB2 的 C 处继续执行，执行完子程序
17、 SUB2 后萋返回到子程序 SUB1的地址 B 处。其中返回点地址、取自线性表的最后一个元素。取出 B 后，线性表的状态为（A）。（9）返回到子程序 SUB1 的 B 处继续执行，执行完子程序 SUB1 后要返回到主程序 MAIN的地址 A 处。其中返回点地址 A 取自线性表最后一个元素。取出 A 后，线性表变空，即线性表的状态为（）。（10）返回到主程序 MAIN 的 A 处继续执行，直到主程序 MAIN 执行完成。由上述逐步返回的过程可以看出，当由子程序返回到上一个调用程序时，需要从线性表的末尾取出返回点地址，即从线性表中删除最后一个元素，而这种对线性表的删除操作也是不需要移动线性表中其
18、他数据元素的。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）入栈运算 入栈运算是指在栈顶位置插入一个新元素。操作过程如下：首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“
19、上溢”错误），算法结束。然后将栈顶指针进一（即 top 加 1）。最后将新元素 x 插入栈顶指针指向的位置。（2）退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为 0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。最后将栈顶指针退一（即 top 减 1）。（3）读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：首先判断栈顶指针是否为 0。如果是，则说明栈空，读不到栈顶元素，算法结束。然后将栈顶元素赋给指定的变量 y。必须注意，这个运算不删除栈
20、顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。二、队列及其基本运算 1什么是队列 在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：初始时线性表为空；当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。定义：队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。*允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指
21、向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（Front）指向排头元素的前一个位置。*在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。*在队列中，队尾指针 rear 与排头指针 front 共同反映了队列中元素动态变化的情况。图 1.11 具有 6 个元素的队列示意图 图 1.12 队列运算示意图 2循环队列及其运算 定义：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队
22、列循环使用。*在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置，因此，从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列中的元素。*循环队列的初始状态为空，即 rear=front=m，如图 1.13 所示。图 1.13 循环队列存储空间示意图 循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针 rear=m+1 时，则置 rear=1。每进行一次退队运算，排头指针就进一。当排头指针 front=m+1 时，则置 front=1。图 1.14 循环
23、队列运算例 *当循环队列满时有 front=rear，而当循环队列空时也有 front=rear。即在循环队列中，当 front=rear 时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志 s，s 值的定义如下：由此可以得出队列空与队列满的条件如下：队列空的条件为 s=0；队列满的条件为 s=1 且 front=rear。假设循环队列的初始状态为空，即：s=0，且 front=rear=m。（1）入队运算 入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明
24、循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。然后将队尾指针进一（即 rear=rear+1），并当 rear=m+1 时置 rear=1。最后将新元素 x 插入队尾指针指向的位置，并且置循环队列非空标志。（2）退队运算 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。然后将排头指针进一（即 front=front+1），并当 front=m+1 时置 front=1。再将排头指针指向的元素赋给指定的变量 最后判断退队后循环队列是否为空。
25、当 front=rear 时置循环队列空标志（即 s=0）。1.5 线性链表 一、线性链表的基本概念 *线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。*线性表的顺序存储结构存在的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。（2）当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。（3）线性表的顺序存储结构不便于对存储空间的动态分配。因此，对于大
26、的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。*假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。*在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。*在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。*链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非
27、线性结构时，其指针域的个数要多一些。1线性链表 定义：线性表的链式存储结构称为线性链表。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。图 1.15 线性链表的存储空间 为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。图 1.16 线性链表的一个存储结点 *在线性链表中，用一个专门的指针 HEAD 指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用 NULL 或 0 表示），
28、表示链表终止。图 1.17 线性链表的逻辑结构 *在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。*当 HEAD=NULL（或 0）时称为空表。图 1.18 线性链表例 *在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为
29、左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为双向链表。图 1.19 双向链表示意图 2带链的栈 栈也是线性表，也可以采用链式存储结构。图 1.20 带链的栈 在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。图 1.21 可利用栈及其运算 与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化。即建立一个空栈的顺序存储空间。入栈运算。是指在栈顶位置插入一个新元素。退栈运算。是指取出栈顶元素并赋给一个指定的变量。读栈顶元素。是指将栈顶元素赋给一个指定的变量。3带链的队列 队列也是线性表
30、,也可以采用链式存储结构。图 1.22 带链的队列及其运算 与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化。即建立一个空队列的顺序存储空间。入队运算。是指在循环队列的队尾加入一个新元素。退队运算。是指在循环队列的排头位置退出一个元素并赋给指定的变量。二、线性链表的基本运算 线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合并成一个线性链表 将一个线性链表按要求进行分解。逆转线性链表。复制线性链表。线性链表的排序。线性链表的查找。1在线性链表中查找指定元素 在非空线性链表中寻找包含指定元素值 x
31、的前一个结点 p 的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为 x 为止。因此，由这种方法找到的结点 p 有两种可能：*当线性链表中存在包含元素 x 的结点时，则找到的 p 为第一次遇到的包含元素 x 的前一个结点序号；*当线性链表中不存在包含元素 x 的结点时，则找到的 p 为线性链表中的最后一个结点号。2线性链表的插入 （1）定义 在链式存储结构下的线性表中插入一个新元素。（2）插入过程 从可利用栈取得一个结点，设该结点号为 p（即取得结点的存储序号存放在变量 p中），并置结点 p 的数据域为插入的元素值 b。在线性链表中寻找包含元素
32、x 的前一个结点，设该结点的存储序号为 q。最后将结点 p 插入到结点 q 之后。为了实现这一步，只要改变以下两个结点的指针域内容：a使结点 P 指向包含元素 x 的结点（即结点 q 的后件结点）。b使结点 q 的指针域内容改为指向结点 p。（a）原来的可利用栈与线性链表 （b）从可利用栈取得结点 p，在线性链表中找到包含元素 x 的前一个结点 q（c）p 插入到 q 之后 图 1.23 线性链表的插入 *只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。*可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。*线性链表在插入过程
33、中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。3线性链表的删除 （1）定义：在链式存储结构下的线性表中删除包含指定元素的结点。（2）删除过程 在线性链表中寻找包含元素 x 的前一个结点，设该结点序号为 q。将结点 q 后的结点 p 从线性链表中删除，即让结点 q 的指针指向包含元素 x 的结点 p的指针指向的结点。将包含元素 x 的结点 p 送回可利用栈。此时，线性链表的删除运算完成。（c）将被删除的结点 p 送回可利用栈后 图 1.24 线性链表的删除 *在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。*
34、当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将该空闲结点送回到可利用栈。三、循环链表 前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。1循环链表的特点 （1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。2循环链表与线性单链表相比主要有以下两个方面的优点：（1）在循环链表中，只要
35、指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线性单链表做不到这一点。（2）由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。（a）非空循环链表（b）空循环链表 图 1.25 循环链表的逻辑状态 1.6 树与二叉树 一、树的基本概念 定义：树（Tree）是一种简单的非线性结构，树中所有数据元素之间的关系具有明显的层次特性。图 1.26 一般的树 图 1.27 学校行政层次结构树 图 1.28 书的层次结构树 *在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根
36、。*在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。*在树结构中，一个结点所拥有的后件个数称为该结点的度。*在树中，所有结点中的最大的度称为树的度。*树中的结点数=树中所有结点的度之和+1。*根结点在第 1 层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。在计算机中，可以用树结构来表示算术表达式。用树来表示算术表达式的原则如下：表达式中的每一个运算符在树中对应一个结点，称为运算符结点。运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。运算对象中的单变量均为叶子结点。*表示一个表达式的表达式树是不唯一的。
37、a*（b+ed）+e*h-g*f（s，t，x+y）（a）表达式树之一（b）表达式树之二 树在计算机中通常用多重链表表示。*多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（指针域）个数将随树中该结点的度而定。图 1.30 树链表中的结点结构 二、二叉树及其基本性质 1什么是二叉树 二叉树具有以下两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。*在二叉树中，每一个结点的度最大为 2。图 1.31 二叉树例 2二叉树的基本性质 性质 1 在二叉树的第 k 层上，最多有 2k-1（k1）个结点。性质 2 深度为 m 的二叉树最多有 2m
38、-1 个结点。21-1+22-1+2m-1=2m-1 性质 3 在任意一棵二叉树中，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个。二叉树中总的结点数为 n=n0+n1+n2（1）进入分支的总数为 m n=m+1（2）总的射出分支数应与总的进入分支数相等 m=n1+2n2（3）n=n1+2n2+1（4）n0+n1+n2=n1+2n2+1 n0=n2+1 性质 4 具有 n 个结点的二叉树，其深度至少为log2n+1，其中log2n表示取 log2n 的整数部分。3满二叉树与完全二叉树 （1）满二叉树 定义：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点
39、。*在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第 k 层上有 2k-1个结点，且深度为 m 的满二叉树有 2m-1 个结点。（a）深度为 2 的满二叉树（b）深度为 3 的满二叉树（c）深度为 4 的满二叉树 图 1.32 满二叉树 （2）完全二叉树 定义：所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为 m、且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 m 的满二叉树中编号从 1 到 n 的结点一一对应时，称之为完
40、全二叉树。*对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为 P，则其左分支下的子孙结点的最大层次或为 P，或为P+1。图 1.33 完全二叉树 *满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下两个性质：性质 5 具有 n 个结点的完全二叉树的深度为log2n+1。性质 6 设完全二叉树共有 n 个结点。如果从根结点开始，按层序（每一层从左到右）用自然数 1，2，n 给结点进行编号，则对于编号为 k（k=1，2，n）的结点有以下结论：若 k=1，则该结点为根结点，它没有父结点；若 k1，则该结点的父结点编
41、号为 INT（k2）。若 2kn，则编号为 k 的结点的左子结点编号为 2k；否则该结点无左子结点（显然也没有右子结点）。若 2k+1n，则编号为 k 的结点的右子结点编号为 2k+1；否则该结点无右子结点。三、二叉树的存储结构 在计算机中,二叉树通常采用链式存储结构。*用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。*用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。图 1.34 二叉树存储结点的结构 图 1.35 二叉树的链式存储结构
42、*对于满二叉树与完全二叉树来说，可以按层序进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。四、二叉树的遍历 定义：二叉树的遍历是指不重复地访问二叉树中的所有结点。*在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。1前序遍历（DLR）定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。二
43、叉树前序遍历的简单描述：若二叉树为空，则结束返回。否则：访问根结点；前序遍历左子树；前序遍历右子树。2中序遍历（LDR）定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。下面是二叉树中序遍历的简单描述：若二叉树为空，则结束返回。否则：中序遍历左子树；访问根结点；中序遍历左子树。3后序遍历（LRD）定义：所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，
44、最后访问根结点。下面是二叉树后序遍历的简单描述：若二叉树为空，则结束返回。否则：后序遍历左子树；后序遍历右子树；访问根结点。前序序列：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，中序序列为 ABCDEFG，则二叉树的回复过程如下：图 1.36 二叉树的恢复过程
45、 1.7 查找技术 定义：查找是指在一个给定的数据结构中查找某个指定的元素。一、顺序查找 顺序查找又称顺序搜索。其基本方法如下：（1）从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；（2）若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。比较次数(假设线性表的长度为 n)：最好情况：第一个元素即是要查找的元素，比较一次；最坏情况：被查找元素是线性表中的最后一个元素或者不在线性表中，比较n 次；平均情况：大约与线性表中的一半元素进行比较。*虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找
46、：如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。二、二分法查找 二分法查找（又称对分查找）只适用于顺序存储的有序表。设有序线性表的长度为 n，被查元素为 x，则二分查找的方法如下：（1）将 x 与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束。（2）若 x 小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。（3）若 x 大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。（4）这个过程一直进行到查找成功或
47、子表长度为 0（说明线性表中没有这个元素）为止。*显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较log2n+1次，而顺序查找需要比较 n 次。1.8 排序技术 定义：将一个无序序列整理成按值非递减顺序排列的有序序列。在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。一、交换类排序法 定义：借助数据元素之间的互相交换进行排序的一种方法。*冒泡排序法与快速排序法都属于交换类的排序方法。1冒泡排序法 （1）定义 冒泡排序法是一种最简单的交换类
48、排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。（2）排序过程 首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。然后，从后到前扫描剩下的线性表,同样,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有 序。*在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且
49、冒泡排序又称下沉排序。图 1.37 冒泡排序过程示意图 （3）性能分析 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n2 遍的从前往后的扫描和 n2 遍的从后往前的扫描，需要的比较次数为 n（n-1）2。但这拿工作量不是必需的，一般情况下要小于这个工作量。2快速排序法 （1）定义 快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。（2）基本思想 从线性表中选取一个元素，设为 T，将线性表后面小于 T 的元素移到前面，而前面大于 T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T 插入到其分界线的位置处，这个过程称为线性表的分割。
50、通过对线性表的一次分割，就以 T 为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于 T，而后面子表中的所有元素均不小于 T。图 1.38 快速排序示意图 （3）排序过程 首先，在表的第一个、中间一个与最后一个元素中选取中项，设为 P（k），并将 P（k）赋给 T，再将表中的第一个元素移到 P（k）的位置上。然后设置两个指针 i 和 i 分别指向表的起始与最后的位置。反复操作以下两步：a将 j 逐渐减小，并逐次比较 P（j）与 T，直到发现一个 P（j）T 为止，将 P（i）移到 P（j）的位置上。上述两个操作交替进行，直到指针 i 与 j 指向同一个位置（即 i=j）为止，