1.3　线性表及其顺序存储结构

【考点1】线性表的基本概念

（1）线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。

（2）非空线性表的结构特征：

①有且只有一个根结点a₁，它无前件；

②有且只有一个终端结点a_n，它无后件；

③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

【说明】

①线性表中结点的个数n称为线性表的长度。

②当n＝0时，称为空表。

【真题演练】

下列叙述中正确的是（　　）。[2014年9月真题]

A．结点中具有两个指针域的链表一定是二叉链表

B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构

C．二叉树只能采用链式存储结构

D．循环链表是非线性结构

【答案】B

【解析】A项错误，具有两个指针域的链表可能是双向链表，也可能是二叉链表，其中双向链表是线性结构，二叉树为非线性结构；B项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。答案选择B选项。

【考点2】线性表的顺序存储结构

（1）概述

顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。

（2）特点

①线性表中所有元素所占的存储空间是连续的；

②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

（3）运算

在线性表的顺序存储结构下，可对线性表进行以下运算：

①插入：在线性表的指定位置处加入一个新的元素；

②删除：在线性表中删除指定的元素；

③查找：在线性表中查找某个（或某些）特定的元素；

④排序：对线性表中的元素进行整序；

⑤分解：按要求将一个线性表分解成多个线性表；

⑥合并：按要求将多个线性表合并成一个线性表；

⑦复制：复制一个线性表；

⑧逆转：逆转一个线性表等。

【真题演练】

在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（　　）。[2014年3月真题]

A．相同，元素的存储顺序与逻辑顺序一致

B．相同，但其元素的存储顺序可以与逻辑顺序不一致

C．不同，但元素的存储顺序与逻辑顺序一致

D．不同，且其元素的存储顺序可以与逻辑顺序不一致

【答案】A

【解析】在顺序表中，每个元素占有相同的存储单元。顺序表具有特征：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。答案选择A选项。

【考点3】顺序表的插入运算

假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：

（1）首先处理以下三种异常情况：

①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；

②当i＞n时，认为在最后一个元素之后（即第n＋1个元素之前）插入；

③当i＜1时，认为在第1个元素之前插入。

（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。

（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。

【考点4】顺序表的删除运算

假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：

（1）首先处理以下两种异常情况：

①当线性表为空（即n＝0）时为“下溢”错误，不能进行删除，算法结束；

②当i＜1或i＞n时，认为将第一个或者最后一个元素删除。

（2）然后从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。

（3）最后将线性表的长度减小1。