线性表是指具有相同数据类型的n(n>=0)个数据元素的有限序列，它具有一个表头元素和一个表尾元素，并且每一个数据元素最多只有一个直接前驱和一个直接后继。
线性表的顺序存储也叫作顺序表，它的特性是地址连接、依次存储。
顺序表的定义有静态建表和动态建表两种。
静态建表的实现方法为：
#define MaxSize 50 //定义线性表的最大长度
typedef int ElemType; //假定表中元素类型是int
typedef struct{
ElemType data[MaxSize]; //顺序表的元素（数组）
int length; //顺序表的当前长度
}SqList;
动态建表的实现方法为：
typedef int ElemType;
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length; //数组的最大容量个当前个数
}SeqList;
在动态建表中，内存的分配语句为：
#define InitSize 100
SeqList L;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
描述或定义一个顺序表需要：①存储空间的起始位置；②顺序表的最大存储量；③顺序表当前的长度。
对于顺序表第i位置插入值e操作实现：
bool ListInsert(SqList&L,int i,ElemType e){
if(i<||i>L.length+) return false; //判断i的范围是否有效
if(L.length>=MaxSize) return false; //当前存储空间已满，不能插入
for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-]; //将第i个元素及之后的元素后移
L.data[i-]=e;
L.length++;
return true;
}
对于顺序表第i位置删除值操作实现：
bool ListDel(SqList &L,int i,ElemType &e){
if(i<||i>L.length) return false; //判断i的范围是否有效
e=L.data[i-]; //将被删除的元素赋值给e
for(int j=i;j<L.length;j++) L.data[j-i]=L.data[j]; //将第i个位置之后的元素前移
L.length--;
return true;
}
根据数组的特性，如果想向顺序表中进行插入和删除的操作时需要移动插入/删除点后的所有值，浪费了很多的系统资源。同时，存储顺序表需要一大块连续的地址空间，使得空间利用率下降。因此，我们引入链式存储的线性表，也叫作链表。
对于链表中最简单的单链表，其定义为：
typedef struct LNode{ //定义单链表节点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
对于一个新建立的单链表，向其中加入结点有两种方法：
①头插法建立单链表：将新结点插入到当前链表的表头（向前建表）；
LinkList CreatList1(LinkList &L){
LNode *s; //辅助指针
int x; //存储插入结点数据的值
L=(LinkList)malloc(sizrof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新的结点
s->data=x; //对新结点的数据赋值
s->next=L->next; //新结点的后继指向第一个结点
L->next=s; //头结点的后继指向新结点
scanf("%d",&x); //读入下一个结点值
}
return L;
}
②尾插法建立单链表：将新结点插入到当前链表的表尾（向后建表）；
LinkList CreatList1(LinkList &L){
int x; //存储插入结点数据的值
L=(LinkList)malloc(sizrof(LNode)); //创建头结点
LNode *s,*r=L; //辅助指针,r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新的结点
s->data=x; //对新结点的数据赋值
r->next=s; //新结点在尾结点的后面
r=s; //r指向新的表尾结点
scanf("%d",&x); //读入下一个结点值
}
r->next=NULL; //尾结点指针置空
return L;
}
对于单链表的查找也有两种方法：
①按序号查找结点：在单链表中从第一个结点出发，顺指针next域逐个往下搜索，知道找到第i个结点为止，否则返回最后一个结点指针域NULL；
LNode *GetElem(LinkList L,int i){
int j=; //计数，初始为1
LNode *p=L->next; //第一个结点指针赋值给p
if(i==) return L; //若i等于0，则返回头结点
if(i<) return NULL; //若i无效，则返回NULL
while(p&&j<i){ //从第1个结点开始找，查找第i个结点
p=p->next;
j++;
}
return p;
}
②按值查找结点：从单链表的第一个结点开始，由前向后依次比较表中各结点数据域的值，若结点数据域的值等于给定值e，则返回该结点的指针，若没有则返回NULL。
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
}
单链表的插入操作：
①取指向插入位置的前驱结点的指针 p=GetElem(L,i-1);
②令新结点*s的指针域指向*p的后继结点 s->next=p->next;
③令新结点*p的指针域指向新插入的结点*s p->next=s。
单链表的删除操作：
①p=GetElem(L,i-1);
②q=p->next;
③p->next=q->next;
④free(q).
对于单链表，对数据结点的前驱访问比较困难，所以我们引入双链表，其定义为：
typedef struct DNode{ //定义双链表节点类型
ElemType data; //数据域
struct DNode *prior,*next; //指针域 （前驱+后继）
}DNode,*DLinkList;
双链表的插入操作：
①s->next=p->next;
②p->next->prior=s;
③s->prior=p;
④p->next=s.
双链表的删除操作：
①p->next=q->next;
②q->next->prior=p;
③free(q).
循环单链表：①最后一个结点的指针指向头结点；②从任何一个结点出发都能访问到链表的每一个元素；③判空的条件是头结点的后继为头指针；④对循环单链表仅设置尾指针使得操作效率更高。
循环双链表：①尾结点的后继指向头结点，头结点前驱指向尾结点；②当循环双链表为空表时，其头结点的前驱和后继都为头结点。
静态链表：是借助数组来描述线性表链式存储结构的一种链表，结点中也包含数据域data和指针next，与前面链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。
对于一个a->b->c->d的数据链表，它的静态链表的表示形式为：
| 数组下标 | data | next |
| 0 | 头 | 2 |
| 1 | b | 6 |
| 2 | a | 1 |
| 3 | d | -1（结束） |
| 4 | ||
| 5 | ||
| 6 | c | 3 |
对静态链表的插入、删除操作与动态链表一样，只需要修改指针，而不需要移动元素。
静态链表的定义为：
#define MaxSize 50 //定义静态链表的最大长度
typedef int ElemType //假定表中元素类型是int
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
