链表是一种常见的基础数据结构，是一种线性表，但与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针(或引用)将零散的内存块串联起来使用。
链表的基本特点
非连续存储：链表中的元素在内存中不是连续存放的
节点结构：每个节点包含数据和指向下一个节点的指针
动态大小：可以动态地增加或删除节点，不需要预先知道数据量
链表的类型
单链表：
每个节点包含数据和指向下一个节点的指针
只能单向遍历
双向链表：
每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针
可以双向遍历
循环链表：
单链表或双链表的变种
尾节点指向头节点，形成环状结构
链表的基本操作
插入操作：
在头部插入
在尾部插入
在指定位置插入
删除操作：
删除头节点
删除尾节点
删除指定节点
查找操作：
按值查找
按索引查找
遍历操作：
从头到尾遍历所有节点
如下代码实现上述操作：
*@file name:链表实现
*@brief :实现链表的创建、头插、尾插、指定插入、指定删除、遍历。
*@author :RISE_AND_GRIND@163.com
*@date :2025/01/07
*@version :1.0:版本
*@property :
*@note :
* CopyRight (c)2023-2024 RISE AND GRIND@163.com 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;
/*
@function name :*LList_Create(void)
@brief :创建一个空链表，空链表应该有一个头结点，并对链表进行初始化化
@param :
@retval :返回链表的头结点的地址
@date :2025/02/07
@version :1.0:版本
@note :
*/
LList_t *LList_Create(void)
{
LList_t *Head =(LList_t *)calloc(1,sizeof(LList_t));//创建一个头结点并为头结点申请内存
//创建头结点空间失败则打印并退出程序
if(Head == NULL)
{
perror("calloc failed");
exit(-1);
}
Head->next =NULL; //对头结点进行初始化，头结点是不存储有效内容
return Head; //把头结点的地址返回
}
/*
@function name :*LList_NewNode(Datatype_t data)
@brief :创建新的结点，并对新结点进行初始化（数据域+指针域）
@param :将数据存储到新结点的数据域
@retval :返回链表的头结点的地址
@date :2025/02/07
@version :1.0:版本
@note :
*/
LList_t *LList_NewNode(Datatype_t data)
{
LList_t *New =(LList_t *)calloc(1,sizeof(LList_t));//创建一个新结点并为新结点申请内存
//创建新结点空间失败则打印并返回空
if(New == NULL)
{
perror("calloc failed");
return NULL;
}
New->data = data; //对新结点的数据域进行初始化
New->next = NULL; //对新结点的指针域进行初始化
return New; //返回新结点的地址
}
/*
@function name :LList_HeadInsert(LList_t *Head,Datatype_t data)
@brief :对链表进行头插
@param :形参为链表的头结点、需要插入的数据
@retval :返回true表示插入成功，返回false表示返回失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_HeadInsert(LList_t *Head,Datatype_t data)
{
LList_t *New=LList_NewNode(data);//创建新的结点，并对新结点进行初始化（数据域+指针域）
//创建新结点空间失败则打印并返回空
if(New == NULL)
{
perror("creat new failed");
return false;
}
//判断链表是否为空，如果链表为空，则把新结点插入到链表的头部
if(Head->next == NULL)
{
Head->next ==New;
return true;
}
New->next = Head->next; //如果链表不为空，因为头结点没有数据域，Head->next指向首结点，
Head->next =New; //将结点插入到首结点处
return true;
}
/*
@function name :LList_TailInsert(LList_t *Head,Datatype_t data)
@brief :对链表进行尾插
@param :形参为链表的头结点、需要插入的数据
@retval :返回true表示插入成功，返回false表示返回失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_TailInsert(LList_t *Head,Datatype_t data)
{
LList_t *New=LList_NewNode(data); //创建新的结点，并对新结点进行初始化（数据域+指针域）
LList_t *Phead = Head; //对头结点进行备份
//创建新结点空间失败则打印并返回空
if(New == NULL)
{
perror("creat new failed");
return false;
}
//判断链表是否为空，为空就直接插到首部
if(Phead->next == NULL)
{
Phead->next ==New;
return true;
}
//如果链表不为空，则把新结点插入到链表的尾部
while(Phead->next)
{
Phead=Phead->next;
}
Phead->next=New; //上面这个循环结束后Phead就是尾节点，将新的结点插入到尾结点中
New->next=NULL; //将尾结点的指针域为空
return true;
}
/*
@function name :LList_DestInsert(LList_t *Head,Datatype_t dest,Datatype_t data)
@brief :中间指定插入，插入到指定元素的后面
@param :形参为链表的头结点、需要插入到指定的数据，需要插入的数据
@retval :返回true表示插入成功，返回false表示返回失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_DestInsert(LList_t *Head,Datatype_t dest,Datatype_t data)
{
LList_t *New=LList_NewNode(data); //创建新的结点，并对新结点进行初始化（数据域+指针域)
LList_t *Phead =Head->next; //进行结点备份
//创建新结点空间失败则打印并返回空
if(New == NULL)
{
perror("creat new failed");
return false;
}
//判断链表是否为空，不为空就插入首部
if(Phead == NULL)
{
Phead==New;
return true;
}
//如果链表不为空，则把新结点插入到指定的位置
while(Phead !=NULL && dest!=Phead->data)
{
Phead=Phead->next;
}
New->next = Phead->next;//说明找到目标结点，则把新结点加到目标的后面
Phead->next = New;
return true;
}
/*
@function name :LList_Print(LList_t *Head)
@brief :遍历链表
@param :形参为链表的头结点
@retval :
@date :2025/02/07
@version :1.0:版本
@note :
*/
void LList_Print(LList_t *Head)
{
LList_t *Phead =Head;//对链表的头结点的地址进行备份
//结点不为空则循环
while(Phead->next != NULL)
{
Phead=Phead->next; //把当前结点的直接后继作为新的头结点
printf("data =%d\n" ,Phead->data); //输出当前结点的数据域
}
}
/*
@function name :LList_HeadDel(LList_t *Head)
@brief :头删
@param :形参为链表的头结点
@retval :返回true表示插入成功，返回false表示返回失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_HeadDel(LList_t *Head)
{
LList_t * min = Head->next; //对首结点进行备份,对链表的头结点的地址进行备份
if(Head->next == NULL)
{
return false;
}
Head->next = Head->next->next; //链表是非空，则直接删除首结点
free(min); //释放掉结点1
return true;
}
/*
@function name :LList_TaiDel(LList_t *Head)
@brief :尾删
@param :形参为链表的头结点
@retval :返回true表示删除成功，返回false表示删除失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_TaiDel(LList_t *Head)
{
LList_t *pre = Head; //对链表的头结点的地址进行备份
if(Head->next == NULL)
{
return false;
}
//链表是非空，则删除尾结点
while(Head->next!= NULL)
{
pre=Head;
Head=Head->next;
}
pre->next = NULL;//尾结点指针域为空
return true;
}
/*
@function name :LList_Delmin(LList_t *Head)
@brief :删除单链表中的最小值
@param :形参为链表的头结点
@retval :返回true表示删除成功，返回false表示删除失败。
@date :2025/02/07
@version :1.0:版本
@note :
*/
bool LList_Delmin(LList_t *Head)
{
LList_t * min_prev ; //记录最小值直接前驱
LList_t * min = Head->next; //记录最小值结点的地址
LList_t * phead = Head->next; //记录当前结点的地址
LList_t * phead_prev =Head; //记录头结点的
if(Head->next == NULL)
{
return false;
}
//遍历找出最小值结点
while(phead->next!= NULL)
{
//比较数据域中结点的数据的大小
if(min->data > phead->next->data)
{
min_prev = phead;
min = phead->next;
phead=phead->next;
}
phead = phead->next;
}
min_prev->next = min->next;//删除当前最小值结点
return true;
}
//
/*
@function name :int main(char argc, char *argv[])
@brief :主函数
@param :
@retval :
@date :2025/02/07
@version :1.0:版本
@note :
*/
int main(char argc, char *argv[])
{
LList_t *new = LList_Create(); //创建链表
LList_t *head =new; //头结点备份
//向链表中写入数据
for(int i =0;i<10;i++)
{
new->next = LList_NewNode(i);
new=new->next;
}
LList_HeadInsert(head,0); //向链表头部插入0
LList_TailInsert(head,10); //向链表尾部插入10
LList_DestInsert(head,10,11); //向链表指定数据后面插入11
LList_HeadDel(head); //删除链表首结点
LList_TaiDel(head); //删除链表尾结点
LList_Delmin(head); //删除链表中最小值
LList_Print(head); //遍历输出显示链表
}
调试结果：
评论区