C语言菜鸟入门·数据结构·链表超详细解析
目录
1. 单链表
1.1 什么是单链表
1.1.1 不带头节点的单链表
1.1.2 带头结点的单链表
1.2 单链表的插入
1.2.1 按位序插入
（1）带头结点
（2）不带头结点
1.2.2 指定结点的后插操作
1.2.3 指定结点的前插操作
1.3 单链表的删除
1.3.1 按位序删除
1.3.2 指定结点的删除
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;elsereturn 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的前驱。
C语言_时光の尘的博客-CSDN博客
