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

1.线性表的基本概念

数据结构中，线性结构又称为线性表，线性表是最简单也是最常用的一种数据结构。

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

线性表或者是个空表，或者可以表示为：

（a1,a2,…,ai,…,an）

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

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

真考链接

考核概率为45%。考生要熟记该知识点属于了解性内容，主要是线性表的基本概念。

小提示

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

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

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

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

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

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

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

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

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

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

3.线性表的插入运算

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

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

（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个元素。