一、线性表

1.线性表（List）：零个或多个数据元素的有限序列。
2.分类

3.线性表的抽象数据类型

对于一个线性表来说，插入或者删除数据都是必须的操作，因此线性表的抽象数据类型定义如下：

ADT线性表(List)
Data
线性表的数据对象集合为 (a1, a2, a3, ……, an)， 每个元素的类型均为 DataType。其中，除第一个元素外，每个元素有且只有一个直接前驱元素；除了最后一个元素外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList (*L) : 初始化操作，建立一个空的线性表L。
ListEmpty (L): 若线性表为空，返回 true，否则返回 false。
ClearList (*L): 将线性表清空。
GetElem (L, i, *e): 将线性表 L 中的第 i 个元素值返回给 e。
LocateElem (L, e): 在线性表 L 中查找与给定值 e 相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回 0 表示失败。
ListInsert (*L, i, e):  在线性表 L 中的第 i 个位置插入新元素 e。
ListDelete (*L, i, *e): 删除线性表 L 中第 i 个位置元素，并用 e 返回其值。
ListLength (L): 返回线性表 L 的元素个数。

endADT

二、顺序存储结构

1.线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表（ $a_1，a_2,·····，a_n$ ）的顺序存储示意图如下所示：

线性表的顺序存储结构，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用 C 语言（其它语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为 0 的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

线性表顺序存储的结构代码：

/* 存储空间初始分配量 */
#define MAXSIZE 20 

/* ElemType 类型根据实际情况而定，这里假设为 int */
typedef int ElemType;

typedef struct {
    /* 数组存储数据元素，最大值为 MAXSIZE */
    ElemType data [MAXSIZE];
    /* 线性表当前长度 */
    int length;
}SqList;