全国计算机等级考试四级复习纲要：线性表

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

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

　　修正线性表的结点个数。

　　(5)栈

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

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

　　(6)队列

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

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

　　①create(Q)建立一个空队列。

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

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

　　三、数组

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

　　(1)数组的定义和运算

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

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

　　(2)数组的顺序存储结构

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

　　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)二叉树的链式存储结构

　　二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。