链表
在C语言中，链表是一种常用的数据结构，它可以用来存储一系列的元素。链表中的每个元素都存储了下一个元素的地址，从而形成了一条链。这种结构使得在插入和删除元素时不需要像数组那样移动大量元素，因此它在插入和删除操作多的情况下有很大的优势。
在C语言中，链表可以有多种实现方式，最常见的是使用结构体和指针来实现。
以下是一个简单的单向链表的头插、尾插、指定部分插入、及遍历的实现：
单向链表
创建一个空链表及结点
//构造链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
DataType_t data; //结点的数据域
struct LinkedList *next; //结点的指针域
}LList_t;
/*******************************************************************
*
* 函数名称: LList_Create
* 函数功能: 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
* 函数参数: None
*
*
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/02
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
LList_t * LList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储有效内容的！！！
Head->next = NULL;
//3.把头结点的地址返回即可
return Head;
}
单向链表头部插入
/*******************************************************************
*
* 函数名称: LList_HeadInsert
* 函数功能: 在链表头部插入新的结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t data 新结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
//2.判断链表是否为空，如果为空，则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
//3.如果链表为非空，则把新结点插入到链表的头部
New->next = Head->next;
Head->next = New;
return true;
}
单向链表尾部插入
/*******************************************************************
*
* 函数名称: LList_TailInsert
* 函数功能: 在链表尾部插入新的结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t data 新结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_TailInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
LList_t *Phead = Head;
if (NULL == New)
{
printf("can not tail insert new node\n");
return false;
}
//2.先将新结点指向NULL
New->next=NULL;
//3.先遍历到原末尾结点，再将原来尾部指向该结点
while(Phead->next)
{
//此时已经遍历到尾结点
Phead = Phead->next;
}
Phead->next=New;
return true;
}
单向链表指定部位插入
/*******************************************************************
*
* 函数名称: LList_TailInsert
* 函数功能: 在链表指定部位插入新的结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t data 新结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
{
//1.创建新的结点
LList_t *New = LList_NewNode(data);
LList_t *Phead= Head;
if (NULL == New)
{
printf("can not dest insert new node\n");
return false;
}
//2.找到指定的结点
while (Phead->next)
{
Phead = Phead->next;
if (Phead->data==dest)
{
break;
}
}
//3.找到指定位置，先指向指定位置的后一个结点
New->next=Phead->next;
//4.然后让指定位置的前一个结点指向该结点
Phead->next=New;
return true;
}
单向链表的头部删除
/*******************************************************************
*
* 函数名称: LList_DestDel
* 函数功能: 在链表头部删除结点
* 函数参数:
* @a :LList_t *Head 头结点
*
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_HeadDel(LList_t *Head)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
Head->next= Head->next->next;
//3.头结点指向下个结点的下一个
Temp->next=NULL;
free(Temp);
return true;
}
单向链表的尾部删除
/*******************************************************************
*
* 函数名称: LList_TailDel
* 函数功能: 在链表尾部删除结点
* 函数参数:
* @a :LList_t *Head 头结点
*
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_TailDel(LList_t *Head)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
while(Temp->next)
{
Head=Head->next;
Temp=Temp->next;
}
Head->next=NULL;
free(Temp);
return true;
}
单向链表的指定删除
/*******************************************************************
*
* 函数名称: LList_DestDel
* 函数功能: 在链表指定部位删除结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t dest 目标结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_DestDel(LList_t *Head,DataType_t dest)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
while(Temp->next)
{
Head=Head->next;
Temp=Temp->next;
printf("1");
if(Temp->data==dest)
{
break;
}
}
Head->next=Head->next->next;
Temp->next=NULL;
free(Temp);
return true;
}
单向链表遍历
/*******************************************************************
*
* 函数名称: LList_Print
* 函数功能: 遍历链表，并将所数据进行打印
* 函数参数:
* @a :LList_t *Head 头结点
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//遍历
void LList_Print(LList_t *Head)
{
//对链表的头文件的地址进行备份
LList_t *Phead = Head;
//首结点
while(Phead->next)
{
//把头的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
}
}
完整代码（可运行）
/*******************************************************************
*
* file name: linkedlist.c
* author : [email protected]
* date : 2024/04/22
* function :
* note : None
*
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*
* *****************************************************************/
#include<stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
DataType_t data; //结点的数据域
struct LinkedList *next; //结点的指针域
}LList_t;
//创建一个空链表，空链表应该有一个头结点，对链表进行初始化
LList_t * LList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储有效内容的！！！
Head->next = NULL;
//3.把头结点的地址返回即可
return Head;
}
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
LList_t * LList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
//头插
bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
//2.判断链表是否为空，如果为空，则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
//3.如果链表为非空，则把新结点插入到链表的头部
New->next = Head->next;
Head->next = New;
return true;
}
//尾插
/*******************************************************************
*
* 函数名称: LList_TailInsert
* 函数功能: 在链表尾部插入新的结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t data 新结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_TailInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
LList_t *Phead = Head;
if (NULL == New)
{
printf("can not tail insert new node\n");
return false;
}
//2.先将新结点指向NULL
New->next=NULL;
//3.先遍历到原末尾结点，再将原来尾部指向该结点
while(Phead->next)
{
//此时已经遍历到尾结点
Phead = Phead->next;
}
Phead->next=New;
return true;
}
//指定插入
/*******************************************************************
*
* 函数名称: LList_TailInsert
* 函数功能: 在链表指定部位插入新的结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t data 新结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
{
//1.创建新的结点
LList_t *New = LList_NewNode(data);
LList_t *Phead= Head;
if (NULL == New)
{
printf("can not dest insert new node\n");
return false;
}
//2.找到指定的结点
while (Phead->next)
{
Phead = Phead->next;
if (Phead->data==dest)
{
break;
}
}
//3.找到指定位置，先指向指定位置的后一个结点
New->next=Phead->next;
//4.然后让指定位置的前一个结点指向该结点
Phead->next=New;
return true;
}
/*******************************************************************
*
* 函数名称: LList_DestDel
* 函数功能: 在链表头部删除结点
* 函数参数:
* @a :LList_t *Head 头结点
*
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_HeadDel(LList_t *Head)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
Head->next= Head->next->next;
//3.头结点指向下个结点的下一个
Temp->next=NULL;
free(Temp);
return true;
}
/*******************************************************************
*
* 函数名称: LList_TailDel
* 函数功能: 在链表尾部删除结点
* 函数参数:
* @a :LList_t *Head 头结点
*
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_TailDel(LList_t *Head)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
while(Temp->next)
{
Head=Head->next;
Temp=Temp->next;
}
Head->next=NULL;
free(Temp);
return true;
}
/*******************************************************************
*
* 函数名称: LList_DestDel
* 函数功能: 在链表指定部位删除结点
* 函数参数:
* @a :LList_t *Head 头结点
* @b :DataType_t dest 目标结点的数据域
* 返回结果:
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/22
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool LList_DestDel(LList_t *Head,DataType_t dest)
{
LList_t *Temp=Head->next;
//2.判断链表是否为空，如果为空，则删除没有意义
if (NULL == Temp)
{
printf("can not delent head node\n");
return false;
}
while(Temp->next)
{
Head=Head->next;
Temp=Temp->next;
printf("1");
if(Temp->data==dest)
{
break;
}
}
Head->next=Head->next->next;
Temp->next=NULL;
free(Temp);
return true;
}
//遍历
void LList_Print(LList_t *Head)
{
//对链表的头文件的地址进行备份
LList_t *Phead = Head;
//首结点
while(Phead->next)
{
//把头的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
}
}
int main(int argc, char const *argv[])
{
LList_t *phe=LList_Create();
LList_HeadInsert(phe,20);
LList_HeadInsert(phe,10);
LList_TailInsert(phe,30);
LList_DestInsert(phe,30,40);
LList_TailInsert(phe,50);
//LList_HeadDel(phe);
//LList_TailDel(phe);
//LList_DestDel(phe,40);
LList_Print(phe);
return 0;
}
代码运行完后，可以在终端显示data的值为20和30，而在写链表需要遍历到尾结点时可以运用printf函数进行调试验证，看是否遍历到自己所指定的结点，以免代码编写保质期出现段错误。
如果代码单向链表的代码有什么问题，请将问题发至网易邮箱 [email protected]，作者将及时改正，欢迎各位老爷提出意见。
麻烦三连加关注！！！！
比心！
标签：结点,Temp,LList,单向,Head,next,链表,插入 From： https://www.cnblogs.com/zkbklink/p/18156233