线性表

定义

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

顺序存储

线性表的顺序存储又称为顺序表。
它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表任意元素可以在单位时间内找到存储位置。

如何建立顺序表的结构？
首先我们要在内存中“找块地”，而且是连续的，那么我们可以先确定存储空间的起始位置；然后还要知道这块地有多大，那么这块地的大小我们也要确定；最后我们要将表中各个元素对号入座，那就要知道有多少元素，也就是表的长度。
建立顺序表的三个属性:
1.存储空间的起始位置（数组名data）
2.顺序表最大存储容量（MaxSize）
3.顺序表当前的长度（length）

# define MaxSize 50 //定义线性表的最大长度
typedef int Elemtype //假定表中元素类型是int
typedef struct{
ElemType data [MaxSize]; //顺序表的元素(数组)
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

这里线性表的数组data是静态分配（开数组)的，大小固定,一旦满了就溢出
其实数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配
总结：
1.顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指
定的元素。
2.顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为
物理位置相邻特性决定）
3.顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

链式存储

顺序结构需要一块连续的存储空间，那如果我们只有零散的空间呢？
线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。
为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要
存放一个指向其后继的指针。
因为每个结点只有一个指针指向下一个结点，故又称单链表
通常用“头指针”来标识一个单链表， 例如Linklist L 那么头指针L就代指一个单链表，头指针为
“NULL”时则表示一个空表。
单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以
记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。
头结点和头指针的区别？
不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的
第一个结点，结点内通常不存储信息
为什么要设置头结点？
1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结
点的操作就统一了
2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就
统一了。
单链表的操作：头插法，尾插法
双链表
循环链表和静态链表

前面我们学习的链表大多是指针来实现的，对于一些语言，如Basic，由于没有指针，
那链表结构是不是就无法实现了呢？
静态链表：静态链表是用数组来描述线性表的链式存储结构。