线性表的逻辑结构
定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长。当n=0时 线性表是一个空表
特点：线性表中第一个元素称为表头元素；最后一个元素称为表尾元素
除第一个元素外，每个元素有且仅有一个直接前驱
除最后一个元素外，每个元素有且仅有一个直接后继

线性表的顺序存储结构
线性表的顺序存储又称为顺序表
它是用一组地址连续的存储单元（比如数组），依次存储线性表中的数据元素，
从而使得逻辑上相邻的两个元素在物理位置上也相邻

建立顺序表的三个属性
1.存储空间的起始位置（数组名data）
2.顺序表最大存储容量（MaxSize）
3.顺序表当前的长度（length）

顺序表特点
支持随机访问 
存储密度高，每个结点只存储数据元素 
逻辑上相邻的元素物理上也相邻，插入和删除操作需要移动大量元素

顺序表的操作
插入
1.判断i的值是否正确
2.判断表长是否超过数组长度
3.从后向前到第i个位置，分别将这些元素都向后移动一位
4.将该元素插入位置i 并修改表长

最好情况
在表尾插入（i=n+1），不需要移动元素，时间复杂度为O(1)

最坏情况
在表头插入（即i=1），移动元素n次，时间复杂度为O(n)

平均情况

删除
1.判断i的值是否正确
2.取删除的元素
3.将被删元素后面的所有元素都依次向前移动一位
4.修改表长

最好情况
删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)

最坏情况
删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)

平均情况




线性表的链式存储结构

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素
头结点和头指针的区别？
不管带不带头结点，头指针始终指向链表的第一个结点，
而头结点是带头结点链表中的第一个结点，结点内通常不存储信息

为什么要设置头结点？
1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

单链表的操作
1.头插法建立单链表：
建立新的结点分配内存空间，将新结点插入到当前链表的表头
2.尾插法建立单链表：
建立新的结点分配内存空间，将新结点插入到当前链表的表尾

3.按序号查找结点
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL

4.按值查找结点
从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。

5．插入
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。
算法思路
取指向插入位置的前驱结点的指针
p=GetElem(L,i-1);
令新结点s的指针域指向p的后继结点
s->next=p->next;
令结点p的指针域指向新插入的结点s
p->next=s;

6．删除
删除操作是将单链表的第i个结点删除
先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。
算法思路：
1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1);
2.取指向删除位置的指针 q=p->next;
3.p指向结点的后继指向被删除结点的后继 p->next=q->next
4.释放删除结点 free(q);



双链表
1.插入 
① s->next=p->next;
② p->next->prior=s;
③ s->prior=p;
④ p->next=s;

2.删除 
① p->next=q->next;
② q->next->prior=p;
③ free(q);


循环链表&&静态链表
循环单链表  最后一个结点的指针不是NULL，而是指向头结点，从而整个链表形成一个环
循环双链表 
当循环双链表为空表时，其头结点的prior域和next域都等于Head

静态链表 
用数组来描述线性表的链式存储结构
数组第一个元素不存储数据，指针域存储第一个元素所在的数组下标
链表最后一个元素的指针域值为-1