全国计算机等级考试四级复习纲要二[2]

文章作者 100test 发表时间 2007:03:10 18:40:53
来源 100Test.Com百考试题网

（4）线性表的新结点插入顺序存储线性表的插入:

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

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

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

修正线性表的结点个数。

（5）栈

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

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

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

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

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

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

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

⑤top（s） 取栈顶元素。

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

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

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