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

视频二维码（扫码观看）

一、线性表的基本概念

线性表（Linear List）是最简单、最常用的一种数据结构。如：一个n维向量、矩阵，学生情况登记表。

线性表是由n（n≥0）个数据元素a₁，a₂，…，a_n组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a₁，a₂，…，a_i，…，a_n），其中a_i（i＝1，2，…，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。

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

（1）有且只有一个根结点a₁它无前件；

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

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

【说明】

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

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

二、线性表的顺序存储结构

1特点

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

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

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

图1-3　线性表的顺序存储结构

【注意】

①在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。

②在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

2线性表的相关操作

（1）插入：在线性表的指定位置处加入一个新的元素。

（2）删除：在线性表中删除指定的元素。

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

（4）排序：对线性表中的元素进行整序（即线性表的）。

（5）分解：按要求将一个线性表分解成多个线性表。

（6）合并：按要求将多个线性表合并成一个线性表。

（7）复制：复制一个线性表。

（8）逆转：逆转一个线性表。

三、顺序表的插入运算

【例5】长度为8的线性表顺序存储在长度为10的存储空间中。在第2个元素之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。

图1-4　线性表在顺序存储结构下的插入

线性表的存储空间从1到m，线性表的长度为n（n≤m），插入的位置为i（i表示在第i个元素之前插入）。线性表的插入操作如下：

第一步首先处理以下三种异常情况：

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

②当i＞n时，认为在最后一个元素之后插入；

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

第二步从最后一个元素开始，直到第i个元素，每一个元素往后移动一个位置。

第三步将新元素插入到第i个位置，线性表的长度加1。

四、顺序表的删除运算

【例6】长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素。再删除线性表中的第6个元素。

图1-5　线性表在顺序存储结构下的删除

线性表的存储空间从1到m，线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素）。线性表的删除操作如下：

第一步首先处理以下两种异常情况：

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

②当i＜1或i＞n时，错误，不能进行删除，算法结束。

第二步删除线性表中的第i个元素。

第三步从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。线性表的长度减小1。