目录
1. 单链表
1.1 什么是单链表
对比于顺序表的每个节点只存放数据元素，单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。
顺序表：
优点：可随机存储，存储密度较高；
缺点：要求大片连续空间，改变容量不方便。
单链表：
优点：不要求大片连续空间，改变容量方便；
缺点：不可随机存取，要耗费一定空间存放指针。
对于单链表的每一个结点，都需要有一个数据域用于存放节点的数据元素，需要一个指针域用于指向下一个结点。
struct LNode{
ElemType data;
struct LNode *next;
};
对于struct关键字的用法可参考：C语言菜鸟入门·结构体·struct用法超详细解析_c语言数据结构菜鸟-CSDN博客
而若是我们想要增加一个新的结点，我们可以使用malloc关键字，例如：
首先，我们先声明一个指向struct LNode类型的对象p，通过malloc函数动态分配内存大小为struct LNode类型大小的内存。
struct LNode* p=(struct LNode*)malloc(sizeof(struct LNode));
对于每次增加一个新的结点，我们每次都需要加上struct LNode这样声明起来有些太麻烦了。那么要怎么简单点呢？我们可以使用typedef进行重命名操作，那么就可以写为：
struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;其中对于typedef的操作可以参考：C语言菜鸟入门·各种typedef用法超详细解析-CSDN博客中的结构体介绍。
1.1.1 不带头节点的单链表
我们使用typedef后，可以开始创建一个不带头节点的单链表：
struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个空链表
bool InitList(LinkList &L)
{
L = NULL; //空表，按时还没任何结点，防止脏数据
return trun;
}
void test()
{
Linklist L;//声明一个指向单链表的指针，注意此处没有创建一个结点
//初始化一个空表
InitList(L);
//····后续代码····
}其作用是判断单链表是否为空，通过头指针L，初始化一个空表，防止脏数据：
其中初始化一个空链表的代码也可以写为：
bool Empty(LinkList L)
{
if(L==NULL)
return true;
else
return true;
}或者：
bool Empty(LinkList L)
{
return (L==NULL);
}1.1.2 带头结点的单链表
struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个空链表
bool InitList(LinkList &L)
{
L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
if(L == NULL)//内存不足，分配失败
return false;
L->next = NULL;//头结点之后暂时还没有结点
return true;
}
void test()
{
Linklist L;//声明一个指向单链表的指针
//初始化一个空表
InitList(L);
//····后续代码····
}
不带头结点的头指针指向的下一个结点，这个结点就是实际用于存放数据的结点，
带头节点的头指针指向的下一个结点，这个结点不用来存放实际的数据元素的，只有这个结点的下一个结点才会用来存放数据。
1.2 单链表的插入
1.2.1 按位序插入
（1）带头结点
插入操作，例如在表L中的第i个位置上插入指定元素e：
Listlnsrrt(&L,i,e);
我们要如何来实现插入操作呢？我们要想在i个位置上插入，那么我们就需要找到第i-1个结点，将新的节点插入其后，假设我们的i=2的话（a2），那么我们就需要找到其前一个结点（a1）的结点，然后我们使用malloc函数，申请一个新的结点，往这个结点存入指针e，然后修改指针，就可以得到：
struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
//在第i个位置上插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i<1)
return false;
LNode* p;//指针p指向当前扫描到的结点
int j = 0;//指针p指向第几个结点
p = L;//L指向头结点，头结点是第0个结点（不存数据）
while (p != NULL && j < i - 1)//循环找到第i-1个结点
{
p = p->next;
j++;
}
if(p==NULL)//i值不合法
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->date = e;
s -> next = p->next;//将结点s连接到p之后
p -> next = s;//插入成功
return true;
}
s->date = e;
s -> next = p->next;//将结点s连接到p之后
p -> next = s;//插入成功
（2）不带头结点
由于不带头结点，所以不存在头结点是0的情况，那么数据处理为：
struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
//在第i个位置上插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i<1)
return false;
if (i == 1)//插入第1个节点的操作与其他结点操作不同
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->date = e;
s - next = L;
L = s;
return true;
}
LNode* p;//指针p指向当前扫描到的结点
int j = 1;//指针p指向第几个结点
p = L;//L指向头结点，头结点是第0个结点（不存数据）
while (p != NULL && j < i - 1)//循环找到第i-1个结点
{
p = p->next;
j++;
}
if(p==NULL)//i值不合法
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->date = e;
s -> next = p->next;//将结点s连接到p之后
p -> next = s;//插入成功
return true;
}
1.2.2 指定结点的后插操作
后插操作比较简单，对比按位序插入，仅仅将其改为指定插入，就明确告诉你我要插哪里：
struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
bool InsertNextNode(LinkList* p, ElemType e)
{
if(p==NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s==NULL)
return false;
s->date = e;
s -> next = p->next;
p -> next = s;
return true;
}
1.2.3 指定结点的前插操作
在链表中，我们并不能通过后一节点的数据data找到，前一个结点的指针域next，那我们要如何实现前插操作呢？
例如：我们想在结点1之前插入一个结点：
首先，我们先创建一个结点：
然后，我们既然找不到前驱结点，干脆不找了，直接将结点1的数据data1以及指针域next1复制到新建的结点，这样复制的结点数据就和结点1的数据相同：
然后我们在将想要插入的结点赋值给结点1：
然后将插入结点的next指向复制的结点1的data，让复制的结点1的next指向结点2的data，此时的复制结点1和结点1是相同的，结点插在复制的结点1之前，等价于结点插，插入到结点1之前：
struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
bool InsertNextNode(LinkList* p, ElemType e)
{
if(p==NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s==NULL)
return false;
s -> next = p->next;
p -> next = s;
s->date = p->data;
p->data = e;
return true;
}
1.3 单链表的删除
1.3.1 按位序删除
删除操作，删除表L中的第i个位置的元素，并用e返回删除元素的值：
ListDelete(&L,i,&e);简单来说就是找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。
struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
bool ListDelete(LinkList& L, int i, ElemType &e)
{
if (i<1)
return false;
LNode* p;//指针p指向当前扫描到的结点
int j = 0;//指针p指向第几个结点
p = L;//L指向头结点，头结点是第0个结点（不存数据）
while (p != NULL && j < i - 1)//循环找到第i-1个结点
{
p = p->next;
j++;
}
if(p==NULL)//i值不合法
return false;
if (p->next == NULL)//第i-1个结点之后已无其他结点
return false;
LNode* q = p->next;//令q指向被删除的结点
e = q->date;//用e返回元素的值
p - next = q->next;//将*q结点从链中“断开”
free(q);//释放结点的存储空间
return true;
}
1.3.2 指定结点的删除
指定结点的删除，删除结点p，需要修改其前驱节点的next指针。有两种方法：
方法1：传入头指针，循环寻找p的前驱结点；
方法2：类似于结点前插的实现方式。
bool DeleteNode(LNode *p)
{
if(p==NULL)//i值不合法
return false;
LNode* q = p->next;//令q指向*p的后续结点
p->date = p -> next->date;//和后续结点交换数据域
p -> next = q->next;//将*q结点从链中“断开”
free(q);//释放结点的存储空间
return true;
}
但是以上代码，若是p是最后一个节点，那么代码：
p->date = p -> next->date;//和后续结点交换数据域就会发生错误，解决方法：我们就只能从表头开始一次寻找p的前驱。
