写在前面的：
数据结构的学习是从线性表开始的，由于我们对新知识的很多概念并不是很清除，因此入门的List学习起来会十分困难。
当我们学会了List之后，就搭建好了数据结构的基本思维模式，往后学习便会比较轻松。而且栈和队列其本质都是List，只是有某些特殊性质而已。
综上所述，List这块的内容值得你花比较多的时间来啃，性价比较高。
线性表的顺序存储结构操作：
初、创、销、增、删、清、查、判——初始化、创建、销毁、增加、删除、清空、查询、判断是否为空（所有的数据结构都需要这几种操作）——任何操作在执行之前都要先区分它所处的不同条件。例如：如果要删除线性表的元素，首先要保证线性表不为空，否则删除元素的操作不成立
形参：
1、当参数需要被改动时，则使用指针（或引用）作为形参
2、当参数不需要被改动时，则使用普通的变量作为形参
//将属于Lb但不属于La的元素插入La中 //List* La————>La是个指针，它指向一个类型为List的变量；*La表示它指向的变量，该变量类型为List void umion(List* La,List Lb){//数组La需要被改变内容，而数组Lb不需要被改变内容 int La_len,Lb_len,i; //La_len表示数组La的长度，Lb_len表示数组Lb的长度 ElemType e;//数据元素e的类型与La和Lb中存放的数据元素的类型一致 La_len=ListLength(*La); Lb_len=ListLength(Lb);//求线性表La和Lb的长度，即给La_len和Lb_len赋值；此处La是个指针，长度为4字节，*La才是我们关注的数组 for(i=1;i<=Lb_len;++i){//遍历Lb GetElem(Lb,i,&e);//将Lb第i个元素返回给e；函数声明：GetElem(L,i,*e) if(!LocateElem(*La,e))//判断La中是否存在于e相等的元素；函数声明：LocateElem（L，e） ListInsert(La,++La_len,e);//将e插入到la中，并将La的长度加一 }
用静态数组（固定长度的数组）来存储线性表中的数据信息。其本质就是对定长数组的一种应用，故在使用前，必须要能预估数组的大概长度；当数组的长度不确定时，不能使用循序存储结构
属性：1、存储空间的起始位置：数组名data（data[0]的位置）
2、线性表的最大存储容量：数组长度MaxSize，是个定值
3、线性表的当前长度：length（表中数组元素的个数，随着插入和删除操作，该值会改变）
优点：1、无需为表示元素间的逻辑关系而增加额外的存储空间，存储密度高
2、可快速读取任何位置的元素
缺点：1、插入和删除操作较慢
2、需要大片连续空间；当线性表长度变化较大时，难以确定其存储空间
3、造成存储空间的“碎片”
碎片的产生：
顺序表占用一整块连续的存储空间。若10个不同大小的顺序表L1~L9按从左到右的顺序排列；假设L5占10个字节，当L5被释放掉，且L4和L6始终驻留，L5中只能存放小于或等于10个字节的数据。这样必然会留下更小的缝隙，而这种更小的缝隙是可以在程序运行时逐渐积累数量的。如果一个程序长时间运行，并且以一定频率产生这种缝隙，久而久之，这类缝隙越来越多，且所有缝隙无法被使用。这就是所谓的碎片。
//线性表的顺序存储结构
#define MAXSIZE 20
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];//数组中存放的元素为int型，ElemType代表该数组是个数据类型
int length;
}SqList;//SqList是匿名结构体的别名
//返回第i个位置的元素
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
Status GetElem(SqList L, int i, ElemType* e) {//返回值为int类型，Status代表返回值表状态；不改变L的值，但改变e的值
if (L.length == 0 || i<1 || i>L.length)
return ERROR;//表为空、数组中没有位置i
*e = L.data[i - 1];//用数组的下标[]来访问数组
return OK;
}//运行结果：函数回0，代表查找错误；函数返回1，代表查找成功
//在第i个位置插入元素e
Status ListInsert(SqList* L, int i, ElemType e) {//改变L的值，但不改变e的值
if (L->length == MAXSIZE) return ERROR;
if (i<1 || i>L->length + 1) return ERROR;
if (i <= L->length) {
for (int k = L->length - 1; k >= i - 1; --k)
L->data[k + 1] = L->data[k];//从后往前，将每个元素后移一位
}
L->data[i - 1] = e;//将e插入下标i-1处
L->length++;//数组长度加1
return OK;
}
//删除第i个位置的元素
Status ListDelete(SqList* L, int i, ElemType* e) {//改变L和e的值
if (L->length == 0) return ERROR;
if (i<1 || i>L->length ) return ERROR;
*e = L->data[i - 1];
if (i <= L->length) {
for (int k = i; k length; ++k)
L->data[k - 1] = L->data[k];//从前往后，将每个元素前移一位
}
L->length--;//数组长度减1
return OK;
}
线性表的链式存储结构
typedef struct Node { //定义单链表结点类型，即定义一个单链表；因为要指向结构体本身，所以结构名“Node”不能省略 ElemType data; //定义一个数据域 struct Node* next; //定义了一个指向自身结构类型的指针 }Node, *LinkList; //LinkList=struct Node*；next域中存储的值的类型为LinkList //初始化一个单链表(不带头结点） bool InitList(LinkList* L){ //要传入头指针L的地址，否则函数不能对头指针L本身进行修改 L=NULL; //空表，暂时没有任何结点（防止有遗留的脏数据）；头指针指向NULL说明即使第一个结点也不存在；链表的总长度为4字节 return true; } void test(){ LinkList L; //定义了一个头指针L（等价于定义了一个链表L），该头指针指向一个类型为Node结点 InitList(&L); cout << sizeof(L) << endl; //输出为：4 }链式存储结构是指针和数据结构的的一种使用场景
此链表结点的名称为Node，第1~n个结点的名称分别为S1~Sn；头指针只占4字节，存放链表S1的地址；链表S1所占的空间为sizeof(ElemType)+4字节，sizeof(ElemType)中存放S1中的数据，余下的4字节存放结点S2的地址；……
因此只需要知道头指针的值，就可依次找到链表的所有结点。因此定义一个头指针就等价于定了一个链表；此后当存放第一个数据时，再去定义第一个结点S1，存放第二个数据时，再去定义第二个结点S2，…….
若链表中有n个元素，则它所占的内存空间为：4+n*(sizeof(ElemType)+4)——第一个4为头指针所占的空间，第二个4为每个结点中指针域所占的空间
要存储一个链式的线性表 ，只需要存储这个单链表的头指针；只需要知道了头指针，便能顺着头指针知道链式存储结构剩下的全部内容。
属性结点=数据域+指针域
结点：数据元素ai的存储映像。数据域：存储数据元素信息的域。指针域：存储直接后继位置的域（其中存储的链指向数据结构本身）
单链表：此链表的每个结点中只包含一个指针域
最后一个结点的指针：为空；常用NULL或 ^ 符号来表示
头指针：1、指向第一个结点的指针；若头结点存在，则其指向头结点的指针（整个链表的存取就必须是从头指针开始进行）
2、头指针具有标识作用，所以常用头指针冠以链表的名字
3、无论链表是否为空，头指针均不为空
头结点：1、是为了操作统一和方便而设立的，放在第一个元素的结点之前。其数据域一般无意义，也可存放链表的长度
2、使得在第一个元素结点前插入、删除第一个结点的操作，与其它结点的操作统一
3、头结点可以不存在
注：不带头结点，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。带头结点，写代码更方便，用过的都说好。
线性表为空表：头结点的指针域为“空”
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费空间存放指针
基本概念（这几个我感觉比较绕，当时理了好长时间）：
LinkList L：并没有创建一个结点，只是声明了一个指向单链表/结点的指针，即头指针。想要存储一个单链表，只需要存储它的头结点就可以了；通过头结点就可知道单链表剩下的所有内容
p：存放在结点ai-1的指针域中，类型为LinkList，代表结点ai（可视为结点ai的别名）；即指向第i个结点的指针
p->data：结点ai的数据域
p->next：存放在结点ai的指针域中，类型为LinkList，代表结点ai+1（可视为结点ai+1的别名）。即指向第i+1个结点的指针
p->next->data：结点ai+1的数据域p->next->next：结点ai+1的指针域
初始化一个不带头结点的单链表，并判断其是否为空typedef struct Node { //定义单链表结点类型，即定义一个单链表；因为要指向结构体本身，所以结构名“Node”不能省略 ElemType data; //定义一个数据域 struct Node* next; //定义了一个指向自身结构类型的指针 }Node, *LinkList; //LinkList=struct Node*；next域中存储的值的类型为LinkListNode是定义的结点类型，而LinkList的变量指向Node这种结构类型
Node*==LinkList==struct Node*：为了提高程序的可读性，二者经常在程序中混用，选择依据是所要表示的含义：
1、强调这是一个结点，使用Node*；2、强调这是一个单链表，使用LinkList
链表一定是从头指针（LinkList L）开始的：头指针是单链表的唯一表示，只要有了头指针，线性表的链式存储结构就已经成立
//初始化一个单链表(不带头结点）
bool InitList(LinkList* L){ //要传入头指针L的地址，否则函数不能对头指针L本身进行修改
L=NULL; //空表，暂时没有任何结点（防止有遗留的脏数据）
return true;
}
bool Empty(LinkList){//判断链表是否为空
if(L==NULL) //判断头指针的内容是否为NULL
return true;
else
return false;
}
void test(){
LinkList L; //声明一个指向单链表的指针
InitList(&L);
}
初始化一个带头结点的单链表，并判断其是否为空
//初始化一个单链表(带头结点）
bool InitList(LinkList* L){ //此处的L为头指针中的值，传入的是头指针的地址&L
L=(Node*)malloc(sizeof(Node)); //分配一个名为L的头结点，其内存地址存放在头指针里；L->data是头结点L的数据域，L->next是头结点L的指针域
if(L=NULL) //内存不足，分配失败
return false;
L->next=NULL; //头结点之后暂时还没有结点
return true;
}
//判断单链表是否为空（带头结点）
bool Empty(LinkList L){
if(L->next==NULL) //判断头结点的指针域是否为NULL
return true;
else
return false;
}
void test(){
LinkList L; //声明一个指向单链表的指针
InitList(&L);
}
LinkList L = (Linklist)malloc(sizeof(Node));
LinkList L一般指一个头指针
申请一块长度为sizeof（Node）的内存空间，该内存空间的数据类型为struct Node*（此处用ListLink代替，用于强调这片内存空间是一个单链表）
增加一个新的结点：在内存中申请一个结点所需空间，并用指针L指向这个结点；要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始条件：顺序线性表L已经存在，且1≤i≤ListLength（L）
//操作结果：用e返回L中第i个数据元素的值（对链表的查找操作需要从头结点开始）
#define ERROR 0
#define OK 1
typedef int Status;
Status GetElem(LinkList L, int i; ElemType* e) {//传送一个链表的头指针==传送一个链表（知道了头指针，就等于知道了整个单链表的信息）
int j=1;
LinkList p = L->next; //创建一个指向结点的指针p，让p指向L的第一个结点
while (p && j < i) { //寻找第i-1个结点
p = p->next; //指针p的后移，即让p指向下一个结点
++j;
}
if (!p || j > i) //判断第i个结点是否存在
return ERROR;
*e = p->data;
return OK;
}
//操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1（需要分配新的结点内存）
Status ListInsert(LinkList* L, int i, ElemType e) {
int j = 1;
LinkList p = *L, s;
while (p && j < i) { //寻找第i-1个结点
p = p->next; //指针p的后移，即让p指向下一个结点
++j;
}
if (!p || j > i)//判断第i个结点是否存在
return ERROR;
s = (LinkList)malloc(sizeof(Node)); //生成新结点，s指向这个新的结点
s->data = e;
s->next = p->next;//将p的后继结点赋值给s的后继
p->next = s;//将s赋值给p的后继
return OK;
}
//操作结果：删除L的第i个结点，并用e返回其值，L的长度减1（需要回收结点内存）
Status ListDelete(LinkList* L, int i; ElemType* e) {
int j = 1;
LinkList p = *L， q;
while (p->next && j < 1) { //遍历寻找第i-1个结点
p = p->next; //指针p的后移，即让p指向下一个结点
++j;
}
if (!(p->next) || j > 1)//第i个结点不存在
return ERROR;
q = p->next;
p->next = q->next;//将q的后继赋值给p的后继
*e = q->data;//将q结点中的数据给e
free(q);//让系统回收此结点，释放内存
return OK;
}
//随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）
void CreateListHead(LinkList* L, int n) {
LinkList p;
int i;
srand(time(0));//初始化随机种子
*L = (LinkList)malloc(sizeof(Node)); //*L与p是同一中结构类型
(*L)->next = NULL;//先建立一个带头结点的单链表
for (i = 0; i < n; ++i) {
p = (LinkList)malloc(sizeof(Node));//生成新结点
p->data = rand() % 100 + 1;//随机生成100以内的数字
p->next = (*L)->next;
(*L)->next = p;//插入到表头
}
}
//随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）
void CreateListTail(LinkList* L, int n) {
LinkList p, r;
int i;
srand(time(0));//初始化随机种子
*L = (LinkList)malloc(sizeof(Node));//为整个线性表
r = *L;//r为指向尾部的结点
for (i = 0; i < n; ++i) {
p = (Node*)malloc(sizeof(Node));//生成新结点
p->data = rand() % 100 + 1;//随机生成100以内的数字
r->next = p;//将表尾终端结点的指针指向新结点
r = p;//将当前的新结点定义为表尾终端结点
}
r->next = NULL;//表示当前链表结束
}
//操作结果：将L重置为空表
Status ClearList(LinkList* L) {
LinkList p, q;
p = (*L)->next;//p指向第一个结点
while (p) {//没到表尾
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;//头结点指针域为空
return OK;
}
//静态链表
#define ERROR 1
#define OK 1
#define MAXSIZE 1000
typedef struct {
ElemType data;
int cur;
}Component;
StaticLinkList[MAXSIZE];
//将一维数组space中各分量链成一备用链表
Status InitList(StaticLinkList space) {
int i;
for (i = 0; i < MAXSIZE - 1; ++i)
space[i].cur = i + 1;
space[MAXSIZE - 1].cur = 0;
return OK;
}
//若备用空间链表非空，则返回分配的节点下标，否则返回0
int Malloc_SLL(StaticLinkList space) {
int i = space[0].cur;
if (space[0].cur)
space[0].cur = space[i].cur;
return i;
}
//在L中第i个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L, int i, ElemType e) {
int j, k, l;
k = MAX_SIZE - 1;
if (i<1 || i>ListLength(L) + 1)
return ERROR;
j = Malloc_SLL(L);
if (j) {
L[j].data = e;
for (l = 1; l <= i - 1; ++l)
k = L[k].cur;
l[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
//删除在L中第i个数据元素e
Status ListDelete(StaticLinkList L, int i) {
int j, k;
if (i<1 || i>ListLength(L))
return ERROR;
k = MAX_SIZE - 1;
for (j = 1; j <= i - 1; ++j)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
//将下标为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space, int k) {
space[k].cur = space[0].cur;
space[0].cur = k;
}
//初始条件：静态链表L已存在。操作结果：返回L中数据元素个数
int ListLength(StaticLinkList L) {
int j = 0;
int i = L[MAXSIZE - 1].cur;
while (i) {
i = L[i].cur;
++j;
}
return j;
}
//保存A表的头节点
p = rearA->next;
rearA->next = rearB->next->next;
q = rearB->next;
rearB->next = p;
free(q);
//线性表的双向链表存储结构
typedef struct DulNode {
ElemType data;
struct DulNode* prior;
struct DulNode* next;
}DulNode,*DuLinkList;
//把p赋值给s的前驱
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
//把p->next赋值给p->prior的后继
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
