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

1.线性表的概念

线性表由一组数据元素构成，数据元素之间的相对位置是线性的。非空线性表L={a1，a2，a3…an}的结构特征有：

①有且只有一个根结点a1，它无前件。

②有且只有一个终端结点an，它无后件。

③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当结点个数为0时，称为空表。

2.线性表顺序存储结构的基本特点

①线性表中数据元素类型一致，只有数据域，存储空间利用率高。

②所有元素所占的存储空间是连续的。

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

④做插入、删除操作时需移动大量元素。

⑤空间估计不明时，按最大空间分配。

3.线性表的主要运算

在线性表的顺序存储结构下，可以对线性表进行各种处理。主要运算有：

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

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

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

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

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

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

【例1-1-4】线性表的插入运算，如图1-1-4所示。

【插入算法分析】假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：

【例1-1-5】线性表的删除运算，如图1-1-5所示。

【删除算法分析】在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：

由此可见，顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动一半的数据元素。