考点3 线性表及其顺序存储结构

真考链接

在选择题中，考核概率为45%。该知识点属于了解性内容，考生需了解线性表的基本概念。

1.线性表的基本概念

在数据结构中，通常将线性结构习惯上称为线性表，线性表是最简单也是最常用的一种数据结构。

线性表是由n（n≥0）个数据元素a1，a2，…，an组成的一个有限序列。除了表中的第一个元素外，有且只有一个前件；除了最后一个元素外，有且只有一个后件。

线性表要么是一个空表，要么可以表示为：

（a1，a2，…，ai，…，an）

其中ai（i=1，2，…，n）是线性表的数据元素，也称为线性表的一个节点。

每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个字符，也可以是一个具体的事物，甚至其他更复杂的信息。但是需要注意的是：同一线性表中的数据元素必定具有相同的特性，即属于同一个数据对象。

小提示

非空线性表具有以下一些结构特征：

●只有一个根节点，即头节点，它无前件；

●有且只有一个终节点，即尾节点，它无后件；

●除了头节点与尾节点外，其他所有节点有且只有一个前件，也有且只有一个后件。节点个数n称为线性表的长度，当n=0时称为空表。

2.线性表的顺序存储结构

将线性表中的元素一个接一个地存储在一片相邻的存储区域中，这种顺序表示的线性表也称为顺序表。

线性表的顺序存储结构具有以下两个基本特点：

●元素所占的存储空间必须是连续的；

●元素在存储空间的位置是按逻辑顺序存放的。

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

3.线性表的插入运算

在线性表的插入运算中，若在第i个元素之前插入一个新元素，完成插入操作主要有以下3个步骤：

（1）把原来第i个节点至第n个节点依次往后移一个元素的位置；

（2）把新节点放在第i个位置上；

（3）修正线性表的节点个数。

小提示

一般会为线性表开辟一个大于线性表长度的存储空间，经过多次插入运算，可能出现存储空间已满的情况，如果此时仍继续进行插入运算，将会产生错误，此类错误称为“上溢”。

如果需要在线性表末尾进行插入运算，则只需要在表的末尾增加一个元素即可，而不需要移动线性表中的元素。

如果在第一个位置插入新的元素，则需要移动表中所有的数据。

4.线性表的删除运算

在线性表的删除运算中，若删除第i个位置的元素，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移一个位置。完成删除主要有以下几个步骤：

（1）把第i个元素之后（不包括第i个元素）的n-i个元素依次前移一个位置；

（2）修正线性表的节点个数。

显然，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动线性表中的元素。

如果要删除第1个元素，则需要移动表中所有的数据。

小提示

由线性表的以上性质可以看出，线性表的顺序存储结构适用于小线性表或者建立之后其中的元素不常变动的线性表，而不适用于需要经常进行插入和删除运算的线性表和长度较大的线性表。

真题新精选

【例1】下列有关顺序存储结构的叙述，不正确的是（ ）。

A）存储密度大

B）逻辑上相邻的节点物理上不必邻接

C）可以通过计算机直接确定第i个节点的存储地址

D）插入、删除操作不方便

【答案】B

【解析】顺序存储结构要求逻辑上相邻的元素物理上也相邻，所以只有选项B叙述错误。

【例2】在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次移动（ ）个元素。

A）n-i

B）i

C）n-i-1

D）n-i+1

【答案】D

【解析】根据顺序表的插入运算的定义知道，在第i个位置上插入x，从ai到an都要向后移动一个位置，共需要移动n-i+1个元素。