线性表，顾名思义，是具有像线一样的性质的表。如同学生们在操场上排队，一个跟着一个排队，有一个打头，有一个收尾，在其中的学生都知道前一个是谁，后一个是谁，这样就像一根线将他们都串联起来了。这样就可以称之为线性表。

线性表（List）：零个或多个数据元素的有限序列

若将线性表记为（a1,...,ai-1,ai,ai+1,...,an），则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，...，n-1时，ai有且仅有一个直接后继，当i=2,3,...,n时，ai有且仅有一个直接前驱 

所以线性表元素个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。

然后，在比较复杂的线性表中，一个数据元素可以由若干个数据项组成。

如果我们想要实现两个线性表集合A和B的并集操作。我们可以假设La表示集合A，Lb表示集合B

void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;                //声明与La和Lb相同的数据元素e
    La_len = ListLength(*La);  //求线性表的长度
    Lb_len = ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);      //取Lb中第i个数据元素赋给e
        if(!LocateElem(*La,e)  //La中不存在和e相同的数据元素
            ListInsert(La,++La_len,e);//插入
    }
}

顺序存储结构

线性表有两种物理结构，顺序存储结构就是其中一种。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

 

我们也可以用一维数组来实现顺序存储结构。

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

#define MAXSIZE 20            //存储结构初始分配量
typedef int ElemType;         //ElemType类型根据实际需要情况而定，这里为int
typedef struct
{
    ElemType data[MAXSIZE];   //数组，存储数据元素
    int length;               //线性表当前长度
}SqList;

地址计算方法

我们数数都是从1开始，那么线性表的定义也不能免俗，起始也是1，这个要跟数组的第一个下标是0区分好，于是线性表的第i个元素是要存储在数组下标为i-1的位置。

内存中的地址，其实跟图书馆或者电影院中的座位一样，都是有着自己的编号的。存储器中的每个存储单元都有着自己的编号，这个编号就称为地址。

 插入与删除操作

获得元素操作

#define OK 1
#define ERROR 0

typedef int Status;

Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 ||i<1 ||i>L.length)
        return ERROR；
    *e=L.data[i-1];

    return OK;
}
    

插入操作

Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length==MAXSIZE)            //线性表已满
        return ERROR;
    if(i<1 ||i>L->length+1)           //当i位置不对时
        return ERROR;
    if(i<=L->length)                  //插入位置不在标尾
    {
        for(k=L->length-1;k>=i;k--)   //将要插入位置后的元素向后移一位
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;                   //将新元素插入
    L->length++;

    return OK;
}

删除操作

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length==0)                //线性表为空
        return ERROR;
    if(i<1 ||i>L->length)           //删除位置不正确
        return ERROR;
    *e=L->data[i-1];
    if(i<L->length)                 //如果删除不是最后位置
    {
        for(k=i;k<L->length;k++)    //将删除位置后继元素前移
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}