2017年全国计算机等级考试四级复习辅导6

设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。完成插入主要有以下几个步骤:
检查插入要求的有关参数的合理性;

把原来第n-1个结点至第i个结点依次往后移一个数组元素位置;

把新结点放在第i个位置上;

修正线性表的结点个数。

（5）栈

堆栈的工作原理是采用后进先出（LIFO）技术，栈顶由中央处理器中的堆栈指示器（SP）指出。在执行PUSH操作中SP减量，而在POP操作中SP增量。

下面从数据结构的角度，进一步说明堆栈的基本概念与操作。需要说明的是，其工作原理与前面所介绍的是一致的，不同的是脱离了硬件背景，例如，栈顶指针不是中央处理器的某个寄存器的内容，而是一个抽象的数据结构。来源：www.examda

栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。由于元素是按后进先出的次序入栈和出栈的，所以栈又称后进先出表（Last In First Out），简称LIFO表。栈的基本操作有:

①create（s） 建立一个空栈s。

②empty（s） 测试栈是否为空栈。

③full（s） 测试栈是否满。

④push（x，s） 将元素x插入栈s的栈顶。

⑤top（s） 取栈顶元素。

⑥pop（s） 删除栈顶元素。

由于栈是一种特殊的线性表，栈的各种操

作实际上是线性表的操作的特殊情形，所以表示线性表的方法同样可以用来表示栈。

（6）队列

队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素。队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表（First-In-First-Out）。

日常生活中排队购物就是队列应用的例子:新来的顾客排在队尾等待，排在队头的顾客购物后离开队伍。队列的基本操作有:

①create（Q）建立一个空队列。

②empty（Q）测试队列是否为空队列。③full（Q）测试队列是否为满。④front（Q）取队头元素。

⑤enq（X，Q）向队列中插入一个元素X。⑥enq（Q）删除队头元素。

三、数组

线性表（包括栈和队列）都是线性结构，结构中的每个元素只是无结构的数据元素。我们对线性表作进一步的推广，使结构中的元素本身也可以是具有某种结构（如向量）的数据，从而引出了数组这一种新的数据结构。

（1）数组的定义和运算

类似于线性表，一个二维数组（或称矩阵）可以看成是由m个行向量所组成的向量，也可以看成是由n个列向量所组成的向量。

对于数组的运算，主要有检索或存取数组中某个元素。

（2）数组的顺序存储结构

由于对数组一般不作插入或删除运算，因此，一旦数组被建立，则结构中的元素个数和元素之间的关系就不再发生变动。对这种情况采用顺序存储结构表示数组是比较恰当的。来源：www.examda

由于计算机存储单元是一维的结构，而数组是多维的结构，因此就必须把多维结构映射为一维的结构，即把多维结构按一定次序排列成一维的。

四、树型结构

线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。然而，在计算机科学和计算机应用的各个领域中，存在着大量需要用更复杂的逻辑结构加以表示的问题。因此必须研究更复杂的逻辑结构及相应的数据结构。树形结构就是这些更复杂的结构中最重要的一类。

1.树的基本概念

树是一类重要的树形结构，其定义如下:树是n（n>0）个结点的有穷集合，满足:

（1）有且仅有一个称为根的结点;

（2）其余结点分为m（m≥0）个互不相交的非空集合，T 1 ，T 2 ，…，T m ，这些集合中的每一个都是一棵树，称为根的子树。

在树上，根结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的直接前趋。为了讨论方便，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子（即“子女”）或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点相同的结点互称为兄弟。一棵树上的任何结点（不包括根本身）称为根的子孙。反之若B是A的子孙，则称A是B的祖先，结点的层数（或深度）从根开始算起:根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。

树（及一切树形结构）是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系（即父结点与子结点之间的邻接关系）往往用来表示数据元素之间的某种重要的、必须加以表达的关系。

用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。

2.树的基本运算包括:

①求根ROOT（T），引用型运算，其结果是结点X在树T的根结点。

②求双亲PARENT（T，X），引用型运算，其结果是结点X在树T上的双亲结点;若X是树T的根或X不在T上，则结果为一特殊标志。

③求孩子CHILD（T，X，i），引用型运算，其结果是树T上的结点X的第i个孩子;若X不在T上或X没有第i个孩子，则结果为一特殊标志。

④建树CREATE（X，T 1 ，…，T k ）k≥1，加工型运算，其作用是建立一棵以X为根，以T 1 ，…，T k 为第1，…k棵子树的树。

⑤剪枝DELETE（T，X，i），加工型运算，其作用是删除树T上结点X的第i棵子树;若T无第i棵子树，则为空操作。

3.二叉树

（1）二叉树的基本概念

二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件:（1）有且仅有一个称为根的结点:

（2）其余结点分为两个互不相交的集合T 1 、T 2 ，T 1 与T 2 都是二叉树，并且T 1 与T 2 有顺序关系（T 1 在T 2 之前），它们分别称为根的左子树和右子树。

二叉树是一类与树不同的树形结构。它们的区别是:第一，二叉树可以是空集，这种二叉树称为空二叉树。第二，二叉树的任一结点都有两棵子树（当然，它们中的任何一个可以是空子树），并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二叉树上任一结点的度定义为该结点的孩子数（即非空子树数）。除这个几个术语之外，树的其它术语也适用于二叉树。

特别值得注意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。

（2）二叉树的性质

在某些情况下，了解二叉树的下列性质是有帮助的。

4.二叉树的存储结构

二叉树通常有两类存储结构，顺序存储结构和链式存储结构。

（1）二叉树的链式存储结构

二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。
计算机等级考试