计算机二级C语言：公共基础知识Part2

干货分享，继续更新！计算机二级C新鲜知识点，内容包含算法、数据结构基本概念、线性表及其顺序储存结构、栈和队列、线性链表、树与二叉树、查找和排序顺序等七部分知识点。贴合考点，快来学习吧！

计算机二级C语言——公共基础知识Part2

二、数据结构与算法

2.1 算法

基本特征

在特定环境中执行，并保证每一个一个步骤能够实现，结果能达到预期目的：可行性（1）

算法中每一步描述都是明确的，无论执行多少遍，所得结果应该相同：确定性（2）

算法能够在有限时间内完成，即执行有限步骤后能够终止：有穷性（3）

即算法需要足够的输入信息和初始化信息才是有效的：拥有足够的情报（4）

两种基本要素

数据对象的运算和操作（1）

四种基本运算和操作

算数运算（1

逻辑运算（2

关系运算（3

数据传输（4

算法的结构控制，即运算或操作顺序（2）

顺序结构

选择结构（或分支结构）

循环结构

设计的基本方法

针对待解决的问题，列举所有可能的情况：列举法（1）

通过分析少量特殊情况，从而找出一般关系：归纳法（2）

本质上也属于归纳法，不过递推法是从已知的初始条件出发，：递推法（3） 逐条退出所要求的个中间结果和最后结果，就是一步一步归纳

“减半”是指在不改变问题性质前提下，将问题规模减半：减半递推法（4） “递推”则是不断重复减半的过程

将一个复杂问题逐层分解成若干个简单的问题，解决这些简单问题后，：递归法（5） 再按原来分解的层次逐层向上，把简单问题综合以解决复杂的问题

把一个问题逐层分析，从上到下逐步去“试”，若成功，则得到问题的解；：回溯法（6） 若失败，就逐步退回，换个路线再行试探，直到彻底解决问题

算法的复杂度

所需资源越高，算法复杂度越高

分类

执行算法所需要的计算工作量：时间复杂度

算法程序执行具体时间和算法的时间复杂度不一致，具体时间受到计算机、程序设计语言以及算法实现过程中许多细节所影响。而算法的时间复杂度与这些因素无关。

算法计算工作量是用算法所执行的基本运算次数来度量

指执行算法所需要的内存空间：空间复杂度

和时间复杂度为两个相互独立概念，二者没有直接或间接关系

储存空间包括3个部分

输入数据所占的存储空间（1）

程序本身所占的存储空间（2）

算法执行过程中所需要的额外空间（3）

包括算法程序执行过程中的工作单元，以及某种数据结构所需的附加存储空间

降低算法空间复杂度

主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术

2.2 数据结构基本概念

数据结构

互有关联的数据元素集合

数据处理领域中，通常把两两数据元素之间的关系用前后件关系来描述 （或直接前驱或直接后继关系）

例如“早餐”是“午餐”的前件，“午餐”是“早餐”的后件

前后件关系是数据元素之间最基本的关系，一般来说，数据元素之间任何关系都可以用前后件关系来描述

一个数据结构中没有数据元素，则称该数据结构为“空的数据结构”

2个要素

需要处理的数据元素集合，一般来说，这些数据元素具有某个共同特征：数据

结构

重要

线性结构

树形结构

网状结构

集合

数据逻辑结构

即反映数据元素之间逻辑关系（即前后件关系）的数据结构

2个要素

数据元素集合，通常记为D（1）

D上的关系，反映D中各数据元素之间前后件关系，通常记为R（2）

即一个数据结构可表示为，其中B表示数据结构

数据存储结构

数据的存储结构，又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式

一般来说，一种数据逻辑结构可以表示成多种存储结构； 采用不同存储结构，数据处理效率不同，因此进行数据处理时，要选择合适的存储结构很重要

图形表示

结点

根据前后件关系的复杂程度，分为2大类型

线性结构

非线性结构

注：一个空的数据结构需要根据具体情况确定；如果对该数据结构算法按线性结构规则处理，则属于线性结构；否则属于非线性结构

2.3 线性表及其顺序储存结构

基本理论

线性表是最简单也是最常用的一种数据结构

:定义为表的长度，n=0时称为空表，记作（）或？

非空线性表特征

有且只有一个根结点，它无前件

有且只有一个终端结点，它无后件

除根结点与终端结点外，其他结点有且只有一个前件、后件

结点个数n称为线性表的长度，n=0时称为空表

线性表相邻元素存在前后顺序关系，第一个元素无前驱，最后一个无后继， 其他元素有且仅有一个直接前驱和一个直接后继，因此线性表是一种线性结构

矩阵是一中比较复杂的线性表

矩阵中每一行看成一个元素，也可以把每一列看成一个数据元素。其中每一个数据元素实际上又是一个简单的线性表

复杂线性表中，一个数据元素由若干数据项组成，此时，把数据元素称为记录(record) 由多个记录构成的线性表又称为文件（file）

顺序存储结构（也称为顺序分配）

特征

所有元素所占空间连续（1）

各数据元素在存储空间中是按照逻辑顺序依次存放（2）

这样可以看出，它是用计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。

插入运算

一般线性表会开辟一个大于线性表长度的存储空间，若存储空间已满，仍继续插入会导致错误，这类错误称为“上溢”

2.4 栈和队列

栈和队列属于两种特殊的线性表

他们逻辑结构和线性表相同，只是其运算规则较线性表有一些限制，故又称为运算受限的线性表

栈及其基本运算

栈（Stack）

定义

一种特殊的线性表，其插入与删除都限定在线性表的同一端进行

栈的一端封闭，既不允许插入，也不允许删除；仅可以从另一端进行操作

术语

允许插入与删除的一端，通常用指针top指示栈顶位置：栈顶

不允许插入与删除的另一端，通常用指针bottom来指向栈底：栈底

没有任何元素的栈：空栈

插入、删除方式

栈的修改原则是“后进先出”或“先进后出”，因此栈也称为“后进先出”表或“先进后出”表

类似弹夹装子弹，最后压入的子弹总是第一个被射出，第一个压入的子弹最后被射出

特点

栈顶元素总是最后被插入的元素，也是最早被删除的元素(1)

栈底元素总是最早被插入的元素，也是最晚被删除的元素（2）

栈具有记忆作用（3）

在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他元素（4）

栈顶指针top动态反映了栈中元素的变化情况（5）

3种栈的顺序存储结构基本运算

入栈（1）

栈的插入，在栈顶插入一个新元素

退栈（2）

栈的删除，取出栈顶元素赋予指定变量

读栈顶元素（3）

将栈顶元素（即栈顶指针top指向的元素）的值赋给一个指定变量

队列及其基本运算

队列（Queue）

定义

指允许在一段进行插入，另一端进行删除的线性表

术语

允许插入的一端，通常用一个成为尾指针（rear）的指针指向队尾元素：队尾

允许删除的一端，通常用一个成为头指针（front）的指针指向头元素的前一个位置：队头（或排头）

插入、删除方式

队列为“先进先出”或“后进后出”，队尾指针和头指针共同反映队列中元素动态变化的情况

2种运算

入队运算（1）

往队列队尾插入一个元素

退队运算（2）

从队列排头删除一个元素

循环队列及其运算

循环队列

队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间

队列的顺序存储结构一般采用循环队列的形式，当存储空间最后一个位置被使用，但还需要入队运算时，只要存储空间第一个位置空闲，便可将元素加入到第一个位置，即将存储空间第一个位置作为队尾

方式

用队尾指针rear指向队列中队尾元素，用排头指针指向排头元素的前一个位置

3种益处现象

下溢（1）

队列为空时，继续做出队运算产生的溢出现象； 下溢是正常现象，常用作程序控制转移的条件

真上溢（2）

队列满时，继续做进栈运算； 真上溢是一种出错状态，应设法避免

假上溢（3）

入队和出队时，头尾指针只增不减，使被删除的元素空间永远无法重新利用。当队列中实际元素个数远远小于向量空间规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作

2.5 线性链表

基本概念

顺序存储线性表缺点

为保证插入值两侧数据存储仍顺序存储，需要移动大量数据元素（1）

线性表以分配空间且存储空间已满，仍插入新元素时，会发生“上溢”错误（2）

线性表顺序存储结构不便于对存储空间的动态分配（3）

线性链表(即链式存储结构的线性表)简称链表

这种链表每个结点只有一个指针域：单链表

线性链表存储结构特点

用一组不连续的存储单元存储线性表中的各个元素

因为存储单元不连续，数据元素间的逻辑关系，不能依靠存储单元间的物理关系表示；此时存储空间被划分为一个个小块，每个小块占若干字节，通常称这些小块为存储结点

既可表示线性结构，也可以表示非线性结构

存储单元任意，可连续也可以不连续

只能顺着指针向链尾方向进行扫描，由某一结点出发只能找到它的后件，若要找出前件，必须从头指针开始重新寻找

结构

存储空间的每一个存储结点分为两部分

存储数据元素的值：数据域（1）

存放下一个元素的存储符号（即存储结点的地址，指向后件结点）：指针域（2）

因为增加了指针域，故存储相同的非空线性表，链表用的空间大于顺序表用的空间

术语

指向链表中的第一个结点的指针：头指针HEAD

第一个元素没有前件

最后一个元素没有后件，因此最后一个结点指针域为空，用NULL或0表示

例如，设线性表（A,B,C,D,E,F）在存储空间中的存储情况如图1所示，头指针HEAD中存放的是第一个元素A的存储地址（即存储序号）。为了直观表示该线性链表中各个元素之间前后件关系，还可以用图2所示逻辑状态表示，其中每一个结点的数字表示该节点的存储序号（即结点号）

带链的栈

带链的队列

每个存储结点有两个指针域的链表：双向链表

机构

存放前件的地址：左指针（Llink）

第一个元素的左指针为空

存放后件的地址：右指针（Rlink）

最后一个元素的右指针为空

特点

因为每个结点有两个指针，从某一结点出发，可以方便找到其他任意一个结点

顺序表和链表的比较

线性链表基本运算

运算方式

查找、插入、删除、（这三个是考查重点）合并、分解、逆转、复制和排序

查找（1）

线性链表中查找指定元素必须从队头指针出发，沿指针域中的Next指针逐个结点搜索，直到找到指定元素或链尾为止，因此线性链表不是随机存储结构

链表中，扫描到指定元素值的结点时，返回该结点位置，如果链表中没有元素的值等于指定元素，则扫描完返回值为空

插入（2）

插入新元素之前，首先要给该元素分配一个新结点，用来存储，然后将新元素的值的结点连接到线性链表中指定位置。新结点可利用栈中取得

在线性链表中数据域为M的结点前插入一个新元素n的插入过程

取可利用栈的栈顶空闲结点，生成一个数据域为n的结点，将新结点的存储序号存放在指针变量p中（1）

在线性链表中查找数据域为M的结点，将其前件的存储号存放在变量q中（2）

将新结点p的指针域内容设置为指向数据域M的结点（3）

将结点q的指针域内容改为指向新结点p（4）

插入过程

特点

（1）插入运算时，新结点的存储单元取自可利用栈，因此只要可利用栈非空，总能找到可插入的新结点，因此不需要规定最大的存储空间，也不会发生“上溢”的错误

（2）线性链表在执行插入运算时，不需要移动数据元素，插入运算效率大大提高

删除（3）

在线性链表中删除数据域为M的结点过程

查找出元素M的结点，将该节点存储序号存放在p中（1）

把p结点的前件存储序号存放在变量q中，将q结点的指针修改为指向p结点的指针所指向的结点（即p结点的后件）（2）

把数据域为M的结点“回收”到可利用栈（3）

特点

（1）不需要移动元素

（2）删除的结点回收到可利用栈中，可供线性链表插入使用

循环链表

定义

在单链表第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值有NULL改为指向表头结点

循环链表中，所有结点指针构成了一个环状链

与单链表比较

单链表

顺序访问，即从一各结点出发，找到后件，但无法找到它的前件；且对于空表和第一个结点的处理必须单独考虑，空表与非空表运算不统一

循环链表

得到表中任意一个结点位置，就可以从它出发访问到全表所有的结点

因为循环链表中设置了一个表头结点，因此任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一

二者插入和删除方法基本相同

二、数据结构与算法

2.6 树与二叉树

树

基本概念

一种简单的非线性结构，它呈现出与自然界的树类似的结构形式，故称其为树

例如一个家族中，A有后代B、C；B有后代D、E、F；C有后代G；F有后代H、I，则可用一个倒置的树来表示

因为树形结构前后件关系清楚，故画图时可以去掉箭头

术语

父结点（1）

树结构中每一个结点只有一个前件，这个前件成为该结点的父结点

没有前件的结点只有一个，称为根结点（2）

树结构中，每一个结点可以有多个后件，这些后件即为该结点的子结点：子结点（3）

没有后件的结点：叶子结点（4）

树结构中，一个结点所拥有的后件个数称为该结点的度：度（5）

所有结点中最大的度称为树的度

定义一棵树的根结点所在层次为1，其他结点所在层次等于它的父结点所在的层次加1，：深度（6） 树的最大层次称为树的深度

树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树：（7）

有序树

树中任意结点的子树均看成从左到右有次序，不能随意交换的树

无序树

同有序树相反，子树可以随意交换位置

二叉树

定义

一个有限的结点集合，该集合或为空，或由一个根结点及其两棵互不相交的左、右二叉子树组成

特点

二叉树可以为空，空的二叉树没有结点，非空二叉树有且仅有一个根结点（1）

二叉树中一个结点可以只有左子树或仅有右子树

当一个结点既无左子树也无右子树时，该结点为叶子结点

每个结点最多有两棵子树，且分别称为该结点的左子树和右子树，故每个结点度最大为2（2）

二叉树的子树有左右之分，其次序不能任意颠倒，因此二叉树为有序树（3）

特殊形态

满二叉树

除最后一层外，每一层上所有结点都有两个子结点的二叉树

在满二叉树中，只有度为2和度为0的结点，没有度为1的结点

所有度为0的结点，即叶子结点都在最后一层

完全二叉树

除最后一层外，每一层的结点数均达到最大值，在最后一层只缺少右边的若干结点

也可以这样描述：如果对满二叉树结点连续编号，从根结点开始，自上而下，自左至右进行编号，则深度为K的有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时称之为完全二叉树

特点

叶子结点只可能出现在层次最大的两层上，即倒数两层（1）

任何一个结点，其右分支下的子孙结点最大层次为m，则其左分支下的子孙结点最大层次为m或m+1（2）

由上可知，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

基本性质

存储结构

采用链式存储结构，且存储结点由数据域和指针域两部分构成

因为每一个元素可以有两个后件，故指针域有左右两个，一个为左指针域指向左子结点，另一个右指针域指向右子结点

因为一个一个存储结点由两个指针域，因此二叉树的链式存储结构也称为二叉链表

二叉树遍历

定义

不重复地访问二叉树中所有结点

分类

前序遍历DLR（1）

在访问根结点、遍历左子树与遍历右子树三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；且遍历左子树和右子树时，仍按照根、左、右的顺序

简单描述

若二叉树为空，则结束返回

若二叉树非空

访问根结点（1

前序遍历左子树（2

前序遍历右子树（3

例如右图二叉树遍历结果为：A,B,D,H,E,I,C,F,G（称为二叉树前序序列）

中序遍历LDR（2）

简单描述

若二叉树为空，则结束返回

若二叉树非空

中序遍历左子树（1

访问根结点（2

中序遍历右子树（3

上个例子的遍历结果发生改变，为：H,D,B,E,I,A,C,G,F,（称为二叉树的中序序列）

后序遍历LRD（3）

简单描述

若二叉树为空，则结束返回

若二叉树非空

后序遍历左子树（1

后序遍历右子树（2

访问根结点（3

上个例子的遍历结果发生改变，为：H,D,I,E,B,G,F,C,A,（称为二叉树的后序序列）

注

已知前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树（1）

已知后序遍历序列和中序遍历序列，也可以唯一确定这棵二叉树（2）

但，已知前序遍历序列和后序遍历序列，不能唯一确定这棵二叉树（3）

2.7 查找和排序顺序

查找

顺序查找 1

从线性表第一个元素开始，逐个将线性表中元素与被查元素比较

若二者相等，则查找成功，停止查找

若扫描完毕没有匹配元素，则查找失败

特点

对于大的线性表来说效率低（1）

有2中情况只能用顺序查找（2）

线性表为无序表（即表中元素无序），无论顺序存储还是链式存储，都必须顺序查找（1

线性表有序，但采用链式存储结构，也只能用顺序查找（2

二分法查找 2

也称拆半查找

2个使用条件

顺序存储结构（1）

线性表是有序表（2）

此处的有序表指的是线性表中元素按照非递减排列（即从小到大，但允许相邻元素值相等）

对于长度为n的有序线性表，利用二分法查找元素X过程

将X与线性表中间项比较

若X值等于中间项的值，则查找成功，结束查找（1

若X小于中间项的值，则在线性表前半部分继续以二分法查找（2

若X大于中间项的值，则在后半部分继续以二分法查找（3

与顺序查找法比较

顺序查找法每一次比较，只将查找范围减1

二分法查找，每比较一次，可将查找范围减少为原来一半

排序

定义

将无序序列整理成按值非递减顺序排列的有序序列

交换类排序法 1

冒泡排序法（1）

两两相邻元素交换逐步将线性表变成有序的

过程

从表头开始往后扫描线性表（1）

若相邻两元素，前面大于后面，则二者交换，并称为消去一个逆序

此时线性表中最大的元素不断往后移动，最后直到被交换到队尾

从后到前扫描剩下的线性表（2）

若相邻两元素，后面小于前面，则二者交换，这样又消去一个逆序

扫描过程中，最小的元素不断往前移动，直到第一个位置，则认为该元素已经排序好了

对剩下线性表重复（1）（2）两个过程，直到线性表变空为止，表示排序完成（3）

快速排序法（2）

两个（不相邻）元素交换，能够消除线性表中多个逆序，会大大加快排序速度

原理

一趟排序（1）

待排序的n个元素中取一个元素K（通常取第一个元素），以元素K为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K的元素数据移到K后面。这样，以K为分界线，把线性表分割为两个子表，这成为一趟排序

一趟排序之后，对两个子表分别进行上述过程，继续下去，直到分割的子表长度为1为止，此时，线性表已经排好序了（2）

第一趟排序具体做法

附设两个指针low和high，它们初值分别指向线性表第一个元素（K元素）和最后一个元素（1）

从high所指的位置向前扫描，找到第一个小于K元素的元素，并交换（2）

然后从low所指位置向后扫描，找到第一个大于K元素的数据，互相交换（3）

重复（2）（3）直到low=high为止

插入类排序法 2

定义

将无序序列各元素一次插入到有序的线性表中

简单插入排序法（1）

过程

把n个待排序元素看成一个有序表和一个无序表（1）

开始时，有序表只包含一个元素，而无序表包含另外n-1个元素（2）

每次取无序表中第一个元素插入到有序表中正确位置，使之成为增加一个元素的新的有序表（3）

插入元素时，插入位置及其后的记录一次向后移动（4）

最后有序表的长度为n，为无序表为空，排序完成（5）

每次比较后最多移掉一个逆序，因此效率和冒泡排序法相同

希尔排序法（2）

时间效率高于简单插入排序

基本思想

整个无序序列分割成若干个小子序列分别进行插入排序

方法

将相隔某个增量d的元素构成一个子序列，在排序过程中，逐渐减小这个增量，最后d减至1时，进行一次插入排序，排序就完成

选择类排序法 3

简单选择排序（1）

基本思想

从所有n个待排序数据元素中选择最小的元素（1）

将该元素与第一个元素交换（2）

再从剩下n-1个元素中选出最小的元素与第二个元素交换（3）

重复操作，直到排序完成（4）

堆排序法（2）

定义

调整建堆

堆排序

方法

将一个无序序列建成堆（1）

将堆顶元素（序列中最大项）与堆中最后一个元素交换（2）

不考虑已经换到最后的那个元素，将剩下的n-1个元素重新调整为堆（3）

排序方法比较 4