单向链表的学习
链表：链式存储的线性表。
单向链表的优缺点
- 优点
- 插入、删除时只需要调整几个指针，无需移动任何数据
- 当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存
- 当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快
- 缺点
- 在节点中，需要多余的指针来记录节点之间的关联。
- 所有数据都是随机存储的，不支持立即访问任意一个随机数据。
习题练习
设计一个算法删除单链表L(有头结点)中的最小值结点
/*****************************************************
* @function_name : LList_DelMin
* @brief_ : 删除单向链表中的最小值结点
* @param_ :
* LList_t *Head --> 链表头结点的地址
*
* @retval_ : 空
* @date_ : 2024/04/22
* @version_ : v1.1
* @note_ : None
*******************************************************/
void LList_DelMin (LList_t *Head)
{
LList_t *min_prev; //记录最小值结点的前驱结点
LList_t *min= Head->Next; //记录最小值结点
LList_t *phead=Head->Next; //记录当前结点的地址
LList_t *pnead_prev=Head; //记录当前结点的前驱结点的地址
//1.遍历链表找到最小值结点
while(phead->Next)
{
//比较链表中的结点，找到最小值结点
if(phead->Data < min->Data)
{
min = phead;
min_prev = pnead_prev;
}
//更新当前结点的前驱结点的地址
pnead_prev = phead;
phead = phead->Next;
}
//2.删除最小值结点
min_prev->Next = min->Next;
min->Next = NULL;
free(min);
return;
}
查找单向链表中倒数第K个结点的数据并输出
/*****************************************************
* @function_name : OutLast
* @brief_ : 查找链表倒数第K个结点输出data值
* @param_ :
* LList_t *Head --> 链表头结点的地址
* int k --> 倒数第k个结点
* @retval_ : 空
* @date_ : 2024/04/22
* @version_ : v1.1
* @note_ : None
*******************************************************/
//查找倒数第k个结点，查找成功输出data值，并返回1，输出不成功 返回0
int OutLastK(LList_t *Head,int k)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
return 0;
}
//2.遍历链表找到要删除的结点
LList_t *Tel = Head; //移动节点 判断结束
LList_t *Mel = Head; //记录倒数第k个结点
//移动节点先移动k-1个节点
for (int i = 0; i < k-1; i++)
{
Tel = Tel->Next;
if(Tel->Next == NULL)
return 0;
}
while(Tel->Next != NULL)
{
Tel = Tel->Next;
Mel = Mel->Next;
}
printf("data=%d\n",Mel->Data);
return 1;
}
单向链表的增删改查实现
初始化单向链表
//指的是单向链表中的节点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造链表的结点，链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
DataType_t Data; //结点的数据域
struct LinkedList *Next; //结点的指针域
}LList_t;
//创建一个空链表，空链表应该有一个头结点,对链表进行初始化
LList_t *CreateEmptyLinkedList(void)
{
//1.创建一个头结点并为头结点申请内存
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if(Head == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对头结点进行初始化，头节点是不存储有效内容的
Head->Next = NULL;
//3.把头结点的地址返回即可
return Head;
}
//创建新的结点，并对新结点进行初始化(数据域+指针域)
LList_t *CreateNewLinkedList(DataType_t Data)
{
//1.申请一个结点的内存空间
LList_t *NewNode = (LList_t *)calloc(1,sizeof(LList_t));
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对新结点的数据域和指针域进行初始化
NewNode->Data = Data;
NewNode->Next = NULL;
//3.返回新结点的地址
return NewNode;
}
插入结点
头插
/*****************************************************
* @function_name : InsertLinkedList
* @brief_ : 将新结点插入链表中的头结点的Next
* @param_ :
* LList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头插
bool InsertLinkedList(LList_t *Head,DataType_t Data)
{
//1.创建一个新结点
LList_t *NewNode = CreateNewLinkedList(Data);
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
return false;
}
//2.判断链表是否为空，如果为空，则新结点直接插入到链表的头部
if(Head->Next == NULL)
{
Head->Next = NewNode;
return true;
}
//3.如果链表不为空，则新结点插入到链表的头部
NewNode->Next = Head->Next;
Head->Next = NewNode;
return true;
}
尾插
/*****************************************************
* @function_name : InsertTailLinkedList
* @brief_ : 将新结点插入链表中的尾结点的Next
* @param_ :
* LList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾插
bool InsertTailLinkedList(LList_t *Head,DataType_t Data)
{
//1.创建一个新结点
LList_t *NewNode = CreateNewLinkedList(Data);
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
return false;
}
//2.判断链表是否为空，如果为空，则新结点直接插入到链表的尾部
if(Head->Next == NULL)
{
Head->Next = NewNode;
return true;
}
//3.如果链表不为空，则新结点插入到链表的尾部
LList_t *Tail = Head->Next;
while(Tail->Next != NULL)
{
Tail = Tail->Next;
}
Tail->Next = NewNode;
return true;
}
指定插
/*****************************************************
* @function_name : InsertDestProList
* @brief_ : 指定结点数据域，将新结点插到目标结点的Next
* @param_ :
* LList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* DataType_t dest --> 目标结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//找到目标值插入
bool InsertDestProList(LList_t *Head,DataType_t dest,DataType_t Data)
{
//1.创建一个新结点
LList_t *New = CreateNewLinkedList(Data);
if(New == NULL)
{
perror("Calloc memory for Head is Failed");
return false;
}
//2.判断链表是否为空，如果为空，输出错误信息
if(Head->Next == NULL)
{
perror("InsertDestList is Failed");
return true;
}
LList_t *Phead = Head->Next;//备份首节点的地址
//3.遍历, 先找到目标结点
while(NULL != Phead && dest != Phead->Data)
//查找data值为dest的结点
{
Phead = Phead->Next;//把头的直接后继作为新的头结点
}
//4.若目标结点不存在
if (NULL == Phead)
return false;//不存在元素为dest的结点, 返回false
//5.若目标结点存在且只存在一个结点
if (NULL == Phead->Next)
{
Phead->Next = New;//让头结点链接新结点
return true;
}
//6.若目标结点存在且存在多个结点
else
{ New->Next = Phead->Next;//新结点先链接后面的结点
Phead->Next = New;//让目标元素结点链接新结点
return true;
}
}
删除结点
头删
/*****************************************************
* @function_name : DeleteHeadLinkedList
* @brief_ : 将链表的首结点删除
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头删
bool DeleteHeadLinkedList(LList_t *Head)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
return false;
}
//2.判断链表是否只有一个结点，如果只有一个结点，则直接删除该结点
if(Head->Next->Next == NULL)
{
free(Head->Next);
Head->Next = NULL;
return true;
}
//3.如果链表有多个结点，则删除第一个结点
LList_t *Phead = Head->Next;
Head->Next = Phead->Next;
Phead->Next = NULL;
}
尾删
/*****************************************************
* @function_name : DeleteTailLinkedList
* @brief_ : 将链表的尾结点删除
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾删
bool DeleteTailLinkedList(LList_t *Head)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
return false;
}
//2.判断链表是否只有一个结点，如果只有一个结点，则直接删除该结点
if(Head->Next->Next == NULL)
{
free(Head->Next);
Head->Next = NULL;
return true;
}
//3.如果链表有多个结点，则删除最后一个结点
LList_t *Del= Head;
LList_t *Phead = Head->Next;
while(Del->Next != NULL)
{
Del = Del->Next;
Phead = Phead->Next;
}
Del->Next = NULL;
free(Phead);
return true;
}
指定删
/*****************************************************
* @function_name : DeleteLinkedList
* @brief_ : 指定结点数据域，将目标结点删除(只删除第一个目标结点)
* @param_ :
* LList_t *Head --> 链表头结点的地址
* DataType_t Data --> 目标结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//删除链表中的结点
bool DeleteLinkedList(LList_t *Head,DataType_t Data)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
return false;
}
//2.遍历链表找到要删除的结点
LList_t *Tel = Head;
LList_t *Del = Head->Next;
while(Del -> Data != Data )
{
Del = Del->Next;
Tel = Tel->Next;
}
//3.如果只有一个首元结点且该结点需要删除
if(Del->Data == Data && Del->Next == NULL)
{
Head->Next = Del->Next;
free(Del);
return true;
}
//4.如果删除结点在中间，则删除该结点
if(Del->Data == Data && Del->Next != NULL)
{
LList_t *Tmp = Del -> Next;
Del->Data = Tmp->Data;
Del->Next = Tmp->Next;
Tmp->Next = NULL; //释放内存,防止内存泄漏
free(Tmp);
return true;
}
//5.如果删除结点是尾结点，则删除该结点
if(Del->Data == Data && Del->Next == NULL)
{
Tel->Next = NULL;
free(Del);
return true;
}
//6.如果没找到要删除的结点，则直接返回
perror("Delete LinkedList is Failed");
return true;
}
遍历链表
/*****************************************************
* @function_name : PrintLinkedList
* @brief_ : 将链表的数据域输出打印
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//遍历链表
bool PrintLinkedList(LList_t *Head)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
printf("LinkedList is Empty\n");
return false;
}
//对链表头文件的地址进行备份
LList_t *Phead = Head;
//遍历链表
while(Phead -> Next)
{
//把头的直接后继作为新的头结点
Phead = Phead->Next;
//打印有效数据
printf("data=%d\n",Phead->Data);
}
return true;
}
摧毁链表
/*****************************************************
* @function_name : DestroyLinkedList
* @brief_ : 摧毁链表，释放空间
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : 空
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//摧毁单向链表
void DestroyLinkedList(LList_t *Head)
{
//1.判断链表是否为空，如果为空，直接返回
if(Head->Next == NULL)
{
return;
}
//2.遍历单向链表找到要删除的结点
LList_t *Tel = Head;
LList_t *Del = Head->Next;
while(Del != NULL)
{
Tel = Del;
Del = Del->Next;
Tel->Next = NULL;
free(Tel);
}
//3.释放链表头结点的地址
Head->Next = NULL;
free(Head);
return;
}
单向循环链表的增删改查实现
初始化单向循环链表
//指的是单向循环链表中的节点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造链表的结点，链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
DataType_t Data; //结点的数据域
struct LinkedList *Next; //结点的指针域
}LList_t;
//创建一个空链表，空链表应该有一个头结点,对链表进行初始化
LList_t *CreateEmptyLinkedList(void)
{
//1.创建一个头结点并为头结点申请内存
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if(Head == NULL)
{
perror("Calloc memory for Head is Failed");
return NULL;
}
//2.对头结点进行初始化，头节点是不存储有效内容的
Head->Next = NULL;
//3.把头结点的地址返回即可
return Head;
}
//创建新的结点，并对新结点进行初始化(数据域+指针域)
LList_t *CreateNewLinkedList(DataType_t Data)
{
//1.申请一个结点的内存空间
LList_t *NewNode = (LList_t *)calloc(1,sizeof(LList_t));
if(NewNode == NULL)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对新结点的数据域和指针域进行初始化
NewNode->Data = Data;
NewNode->Next = NULL;
//3.返回新结点的地址
return NewNode;
}
插入结点
头插
/*****************************************************
* @function_name : InsertCList
* @brief_ : 将新结点插入链表中的头结点的Next
* @param_ :
* CList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头插
bool InsertCList(CList_t *Head, DataType_t Data)
{
//1.创建一个新结点，并对新结点进行初始化
CList_t *new = CreateNewCLinkedList(Data);
//2.判断当前链表是否为空，为空则插入头结点之后
if (Head->Next == Head)
{
Head->Next = new;
new->Next = new;
}
else //链表非空，需要对尾结点的Next指针指向新的首结点
{
CList_t *Phead = Head->Next;
while (Phead->Next != Head->Next)
{
Phead = Phead->Next;
}
new->Next = Head->Next;
Head->Next = new; //头结点指向新结点
Phead->Next = new; //尾结点指向新结点
}
return true;
}
尾插
/*****************************************************
* @function_name : InsertTailCList
* @brief_ : 将新结点插入链表中的尾结点的Next
* @param_ :
* CList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾插
bool InsertTailCList(CList_t *Head, DataType_t Data)
{
//1.创建新的结点，并对新结点进行初始化
CList_t *new = CreateNewCLinkedList(Data);
//2.判断当前链表是否为空，为空则插入头结点之后
if (Head->Next == Head)
{
Head->Next = new;
new->Next = new;
}
//3.如果链表非空，需要对旧尾结点的Next指针指向新的尾结点
else
{
CList_t *Phead = Head->Next; //备份首结点地址
while (Phead->Next != Head->Next) //遍历链表，找到尾结点
{
Phead = Phead->Next;
}
Phead->Next = new; //尾结点指向新结点
new->Next = Head->Next; //新结点的Next指针指向首结点
}
return true;
}
指定插
/*****************************************************
* @function_name : InsertPosCList
* @brief_ : 指定结点数据域，将新结点插到目标结点的Next
* @param_ :
* CList_t *Head --> 链表头结点的地址
* DataType_t Data --> 新结点的有效数据
* DataType_t Dest --> 目标结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.1
* @note_ : None
*******************************************************/
//指定目标位置插入
bool InsertPosCList(CList_t *Head, DataType_t Data,DataType_t Dest)
{
//如果是空链表
if(Head->Next == Head)
{
return false;
}
//创建新结点
CList_t *new = CreateNewCLinkedList(Data);
//创建一个指针，指向头结点
CList_t *Pre = Head;
CList_t *Phead = Head->Next;
//遍历链表，找到目标结点
while(Phead->Next != Head->Next)
{
if(Phead->Data == Dest)
{
break;
}
Pre=Pre->Next;
Phead = Phead->Next;
}
//如果目标结点存在且是第一个
if(Phead->Data==Dest && Phead == Head->Next)
{
InsertCList(Head, Data);
}
//如果目标结点存在且不是第一个
else if(Phead->Data == Dest && Phead != Head->Next)
{
new->Next = Phead;
Pre->Next = new;
}
else
{
perror("not found dest");
}
return true;
}
删除结点
头删
/*****************************************************
* @function_name : DeleteCList
* @brief_ : 将链表的首结点删除
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/23
* @version_ : v1.0
* @note_ : None
*******************************************************/
//头部删除
bool DeleteCList(CList_t *Head)
{
if(Head->Next == Head)
{
return false;
}
CList_t *Phead = Head->Next;
CList_t *Ptail = Head->Next;
while(Ptail->Next != Head->Next)
{
Ptail = Ptail->Next;
}
//如果链表中只有一个结点
if(Phead == Ptail)
{
Head->Next = Head; //头结点的Next指针指向头结点，体现循环
Phead->Next = NULL; //首结点的Next指针指向NULL
free(Phead);
return true;
}
//如果链表中不止一个结点
Ptail->Next = Head->Next->Next; //让尾结点的Next指针指向首结点
Head->Next= Head->Next->Next; //更新首结点，让头结点的Next指针指向首结点
Phead->Next = NULL; //让被删除的结点的Next指针指向NULL
free(Phead); //释放被删除的结点的内存空间
return true;
}
尾删
/*****************************************************
* @function_name : DeleteTailCList
* @brief_ : 将链表的尾结点删除
* @param_ :
* LList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//尾部删除
bool DeleteTailCList(CList_t *Head)
{
if(Head->Next == Head)
{
return false;
}
CList_t *Pre = Head;
CList_t *Ptail = Head->Next;
//遍历链表，找到尾结点
while(Ptail->Next != Head->Next)
{
Pre = Pre->Next;
Ptail = Ptail->Next;
}
//如果链表中只有一个结点
if(Pre == Ptail)
{
Head->Next = Head;
Ptail->Next = NULL;
free(Ptail);
return true;
}
Pre->Next = Head->Next;
Ptail->Next = NULL;
free(Ptail);
return true;
}
指定删
/*****************************************************
* @function_name : DeletePosCList
* @brief_ : 指定结点数据域，将目标结点删除(只删除第一个目标结点)
* @param_ :
* LList_t *Head --> 链表头结点的地址
* DataType_t Dest --> 目标结点的有效数据
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//指定目标删除
bool DeletePosCList(CList_t *Head, DataType_t Dest)
{
if(Head->Next == Head)
{
return false;
}
CList_t *Pre = Head;
CList_t *Phead = Head->Next;
while(Phead->Next != Head->Next)
{
if(Phead->Data == Dest)
{
break;
}
Phead = Phead->Next;
Pre = Pre->Next;
}
//如果目标结点存在且是唯一一个
if(Phead->Data == Dest && Phead == Phead->Next)
{
Head->Next = Head;
Phead->Next = NULL;
free(Phead);
return true;
}
//如果目标结点存在且是第一个
else if(Phead->Data == Dest && Pre == Head)
{
DeleteCList(Head);
return true;
}
//如果目标结点存在且是最后一个
else if(Phead->Data == Dest && Phead == Head->Next && Pre != Head)
{
DeleteTailCList(Head);
return true;
}
//如果目标结点存在且不是第一个
else if(Phead->Data == Dest && Phead != Head->Next)
{
Pre->Next = Phead->Next;
Phead->Next = NULL;
free(Phead);
return true;
}
//目标结点不存在
else
{
perror("not found dest");
}
return true;
}
遍历链表
/*****************************************************
* @function_name : CirCLList_Print
* @brief_ : 将链表的数据域输出打印
* @param_ :
* CList_t *Head --> 链表头结点的地址
* @retval_ : bool
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//遍历链表
bool CirCLList_Print(CList_t *Head)
{
//对单向循环链表的头结点的地址进行备份
CList_t *Phead = Head;
//判断当前链表是否为空，为空则直接退出
if (Head->Next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//从首结点开始遍历
while(Phead->Next)
{
//把头结点的直接后继作为新的头结点
Phead = Phead->Next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->Data);
//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->Next == Head->Next)
{
break;
}
}
return true;
}
摧毁链表
/*****************************************************
* @function_name : DestroyLinkedList
* @brief_ : 摧毁链表，释放空间
* @param_ :
* CList_t *Head --> 链表头结点的地址
* @retval_ : 空
* @date_ : 2024/04/22
* @version_ : v1.0
* @note_ : None
*******************************************************/
//摧毁链表，释放空间
void DestroyLinkedList(CList_t *Head)
{
while(Head->Next != Head)
{
DeleteCList(Head);
}
Head->Next = NULL;
free(Head);
}