1-1　顺序表示的线性表——顺序表

【定义】

线性表是由n个类型相同的数据元素组成的有限序列，记为（a1，a2，…，ai-1，ai，ai+1，…，an）。线性表的数据元素存在着序偶关系，即数据元素之间具有一定的次序。在线性表中，数据元素ai-1位于ai的前面，ai又在ai+1的前面，我们把ai-1称为ai的直接前驱元素，ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素，ai+1称为ai的直接后继元素。

线性表的逻辑结构如图1.1所示。

线性表按照存储方式可以分为顺序存储和链式存储。线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。

线性表中第i个元素的存储位置与第一个元素a1的存储位置满足以下关系：

LOC（ai）=LOC（a1）+（i-1）*m

其中，第一个元素的位置LOC（a1）称为起始地址或基地址。

线性表的这种机内表示称为线性表的顺序存储结构或顺序映像，通常将这种方法存储的线性表称为顺序表。

【特点】

顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。只要确定了第一个元素的起始位置，线性表中的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。

【存储结构】

其中，DataType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。

如果要定义一个顺序表，则代码如下：

SeqList L；

如果要定义一个指向顺序表的指针，则代码如下：

SeqList *L；

【基本运算】

（1）初始化线性表。

（2）判断线性表是否为空。

（3）按照序号查找。

（4）按内容查找。

（5）插入操作。要在顺序表中的第i个位置上插入元素e，首先将第i个位置以后的元素依次向后移动1个位置，其次把元素e插入第i个位置。

例如，要在顺序表{3，15，49，20，23，44，18，36}的第5个元素之前插入一个元素22，需要将序号为8，7，6，5的元素依次向后移动一个位置，然后在第5号位置插入元素22，顺序表就变成{3，15，49，20，22，23，44，18，36}，如图1.2所示。

（6）删除第i个元素。在进行删除操作时，先判断顺序表是否为空，如果不空，接着判断序号是否合法，如果不空且合法，则将要删除的元素赋给e，并把该元素删除，将表长减1。

例如，要删除顺序表{3，15，49，20，22，23，44，18，36}的第4个元素，需要将序号为5，6，7，8，9的元素依次向前移动一个位置，这样就删除了第4个元素，最后将表长减1，如图1.3所示。

（7）求线性表的长度。

（8）清空顺序表。

将上述顺序表存储结构的定义及基本运算保存在SeqList.h文件中，在使用时通过#include"SeqList.h"引用这些基本运算。