[全国计算机等级考试四级含金量]2017年全国计算机等级考试四级复习纲要：线性表

二、线性表

（1）线性表及其基本操作

线性表是n≥0个元素的一个有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，）表中元素的个数n称为表的长度，长度n=0的表称为空表。表元素又称为结点，线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若n≥1，则a 1 ，为第一个元素，a n 为最后一个元素。元素a i-1 先于a i ，我们称a i-1 为a i 的前驱;a i 在a i-1 之后，a 1 为a i-1 的后继。除第一个元素外，每个元素都有一个且仅有一个直接前驱;除最后一个元素外，每个元素都有一个且仅有一个直接后继，下面所列的是其中一些常用的运算。

①查找运算

查找线性表的第i（0≤i≤n-1）个表元;

在线性表中查找具有给定键值的表元;

②插入运算

把新表元插在线性表的第i（0≤i≤n）个位置上;

把新表元插在具有给定键值的表元的前面或后面;

③删除运算

删除线性表的第i（0≤i≤n-1）个表元;

删除线性表中具有给定键值的表元;

④其他运算

统计线性表元的个数;

输出线性表各表元的值;

复制线性表;

线性表分析;

线性表合并;

线性表排序;

按某种规则整理线性表。

（2）线性表的存储

有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。

①线性表的顺序存储

线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i（0≤i≤n-1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。用数组存储线性表的优点是能直接访问线性表中的任一结点。

用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和减少的要求相矛盾;二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便。

②线性表的链接存储

线性表链接存储是用链表存储线性表，最简单的用单链表。如从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。即线性表的第i个结点存储在链表的第i（0≤i≤n-1）个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是**链接指针来体现线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是线性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。

其缺点也主要有两条:一是每个表元增加了一个后继指针成分，要花费更多的存储空间;二是不便随机地直接访问线性表的任一结点。

（3）线性表上的查找

线性表上的查找运算是指在线性表中找某个链值的结点。根据线性表的存储形式和线性表本身的性质差异，有多种查找算法，如:顺序查找、二分法查找、分块查找、散列查找等。

（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） 删除栈顶元素。

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

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

（6）队列

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

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

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

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

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

本文来源：https://www.wddqw.com/V4oO.html