一、线性表（一对一）
由零个或者多个数据元素组成的有限序列。（首先线性表是一个序列，元素之间有先来后到的关系，若元素有多个，则第一个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继）。线性表的个数为n，n>=0,当n=0时，为空表
例：
a——a1——a2
a1的前驱是a，后驱是a2.
二、数据类型
（一）数据类型（按取值不同）可以分为两类：
1、原子类型：不可以再分解的基本类型，如整型，浮点型，字符型
2、结构类型：由若干个类型组合而成，可以再分解，例如整型数组是由若干整型数据组成。
（二）抽象数据类型
把数据类型和相关的操作捆绑在一起
（三）线性表的抽象数据类型
线性表的数据对象集合为{A,A1,A2,......An}，每个元素的类型均为datatype。其中，除了第一个元素外，每个元素有且只有一个直接前驱，除了最后一个元素外，每个元素有且只有一个直接后继。数据元素之间的关系是一对一。
Operation：
1、 Initlist(*L):初始化操作，建立一个空的线性表L。
2、 ListEmpty(L):判断线性表是否为空表，若为空，返回true，否则返回false。
3、 ClearList(*L):将线性表清空。
4、 GetElem(L,i,*e):将线性表L中的第i个位置元素返回给e。
5、 LocateElem(L,e):在线性表L中查找与给定值e相等的元素，查找成功，返回该元素在表中序号 表示成功，否则返回0表示失败。
6、LiseInsert(*L,i,e):在线性表L中第i个位置插入新元素e。
7、ListDelete(*L,i,*e):删除线性表L中第i个位置的元素，并返回e值。
8、ListLength(L):返回线性表L的元素个数。
//算并集的代码
//La表示A集合，Lb表示B集合
void unionL(List *La,list Lb)
{
int La_len,Lb_len,i;
ElemType 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);//在La中第++La_len个位置插入新元素e
}
}
}
三、线性表的顺序存储结构
（一）顺序存储结构封装需要三个属性
1、存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
2、线性表的最大存储容量：数组的长度MaxSize。
3、线性表的当前长度：Length。
数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。线性表的当前长度是线性表中元素的个数，是会变化的。
（二）地址计算方法
1、从1开始,公式：LOC(ai)=LOC(a1)+(i-1)*c
2、代码操作（GetElem)：（只需要把数组第i-1下标的值返回即可），返回值status是一个整型，约定返回1代表ok，返回0代表error。
#define ok 1
#define error 0
#define true 1
#define false 0
//初始条件：顺序线性表L已经存在，1<=i<=listlength(L)
//操作结果：用e返回L中第i个数据元素的值
typedef int status;
//status是函数的类型，其值是函数结果状态代码，如ok
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;
}（三）插入操作
1、思路：
——如果插入位置不合理，抛出异常
——如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量
——从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
——将要插入元素填入位置i处
——线性表长+1
//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1
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-1;k--)
{
L->data[k+1]=L->data[k];
}
}
L->data[i-1]=e;//将新元素插入
L->length++;
return ok;
}（四）删除操作
思路：
——如果删除位置不合理，抛出异常
——取出删除元素
——从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移一个位置
——线性表表长-1
//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个元素，并用e返回其值，L长度-1
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--;//线性表表长-1
return ok;
}时间复杂度：
1、（最好的情况）删除和插入操作刚好在最后一个位置，不需要移动任何元素，时间复杂度为O（1）
2、（最坏的情况）插入和删除的位置是第一个位置，所有元素都要移动，时间复杂度O(n)
3、（平均的情况）O((n-1)/2)
4、综上：线性表的顺序存储结构在存、读数据时，不管在什么位置，时间复杂度都为O(1)。在插入和删除时，时间复杂度都是O(n)。
5、线性表顺序存储结构适合不经常插入和删除元素时使用，更多的操作是存取数据
四、线性表的链式存储结构
（一）定义
1、我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针 域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（Node）。
2、n个结点链接成为一个链表，即为线性表（a1,a2,a3,.....an)的链式存储结构。
3、因为链表的每个结点中只包含一个指针域，所有叫做单链表。
4、把链表中第一个结点的存储位置叫头指针（头结点不用存储任何信息），最后一个结点指针为空（NULL）。
头指针：
——指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
——头指针具有标识作业，所有常用头指针冠以链表的名字（指针变量的名字），无论链表是否为空，头指针都不为空。
——头指针是链表的必要元素。
头结点：
——为了操作的统一和方便设立，放在第一个元素结点之前，数据域无意义（但也可以用来存放链表长度）。
——有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
——头结点不一定是链表的必要元素。
//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p;//LinkList=链表
p=L->next;//p指向链表的第一个结点
j=1;
while(p && j<i)//p不能为空且j<i
{
p=p->next;
++j;
}
if(!p || j>i)
{
return error;
}
*e=p->data;
return ok;
}时间复杂度取决于i。当i为1，时间复杂度为O(1)，当i=n，时间复杂度为O(n）
（二）单链表的插入
思路：
——声明一个结点p指向链表头结点，初始化j从1开始
——当j<1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
——若到链表末尾p为空，说明第i个元素不存在
——否则查找成功，在系统上生成一个空结点s
——将数据元素e赋值给s->data
——单链表的插入刚才两个标准语句
——返回成功
//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p,s;
p=*L;
j=1;
while(p && j<i)//寻找第i个结点
{
p=p->next;
j++;
}
if(!p || j>i)//
{
return error;
}
s=(LinkList)malloc(sizeof(Node));
s->data=e;
//后两句顺序不能变
s->next=p->next;
p->next=s;
return ok;
}
（三）单链表的删除
单链表的删除操作图示：
思路：
——声明结点p指向链表的第一个结点，初始化j=1
——当j<1时，遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
——若到链表末尾p为空，说明第i个元素不存在
——否则查找成功，将想删除结点p->next赋值给q
——单链表的删除标准语句p->next=1->next
——将q结点中的数据赋值给e，作为返回
——释放q结点
//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值,L的长度-1
Status LisDelete(LinkList *L, int i, ElemType e)
{
int j;
LinkList p,q;
p=*L;
j=1;
while(p->next && j<i)//寻找
{
p=p->next;
++j;
}
if(!(p->next) || j>i)//
{
return error;
}
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return ok;
}