/**********************************************************************************
*
-
file name: 002_单向链表.c -
author : [email protected] -
date : 2024/04/22 -
function : 单向链表的遍历插入和删除功能的完善 -
note : None -
CopyRight (c) 2024-2024 [email protected] All Right Reseverd - *******************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.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;
}
//尾插
bool LList_TailInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
LList_t *tmp = Head;
while (tmp->next)
{
tmp = tmp->next;
}
//将新节点的后继节点指向NULL，尾节点的后继指针指向新指针
New->next = NULL;
tmp->next = New;
return true;
}
//找到某个特定的位置做插入
bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
{
//创建新的节点，初始化新数据
LList_t *New = LList_NewNode(data);
//定义一个临时指针变量存储首节点
LList_t *tmp = Head;
//定义一个变量i，充当下标查找节点
int i = 0;
//当下标在插入目标位置跳出循环
while (i != dest)
{
//下标在前一个位置跳出循环，所以tmp当前位置在目标节点的直接前继节点
tmp = tmp->next;
//为了遍历到目标位置，所以i自加让循环遍历到目标位置
i++;
//如果传进来的下标大于链表的长度，输入这句话并返回false
if (tmp->next == NULL)
{
printf("需要插入的位置大于链表的长度了！\n");
return false;
}
}
//插入到指定位置操作
New->next = tmp->next;
tmp->next = New;
return true;
}
//头删
bool HeadDel(LList_t *head)
{
if (head->next == NULL)
{
printf("此链表为空！做不了删除动作!\n");
return false;
}
//定义一个变量存储首节点
LList_t *tmp = head->next;
head->next = tmp->next;
tmp->next = NULL;
free(tmp);
return true;
}
//尾删
void TailDel(LList_t *head)
{
if (head->next == NULL)
{
printf("此链表为空！做不了删除动作!\n");
return;
}
//定义一个变量存储首节点
LList_t *tmp1 = head;
//当tmp1(倒数第二个节点)的下下个节点指向NULL时，就说明tmp1的下个节点就是尾节点，需要删除的节点
while (tmp1->next->next != NULL)
{
tmp1 = tmp1->next;
}
//释放掉尾节点
free(tmp1->next);
tmp1->next = NULL;
}
//通过下标删除节点
bool DelNode_index(LList_t *head,DataType_t dest)
{
if (head->next == NULL)
{
printf("此链表为空！做不了删除动作!\n");
return false;
}
//定义两个指针变量存储头节点和首节点
LList_t *tmp1 = head;
LList_t *tmp2 = head->next;
//定义一个下标，方便后面查找
int i = 1;
//当下标不等于目标下表时进入循环
while (i != dest)
{
//向后遍历，然后一遍一遍判断
tmp1 = tmp2;
tmp2 = tmp2->next;
i++;
if (tmp2->next == NULL)
{
printf("已经到最后一个元素了，没有找到需要删除的元素\n");
return false;
}
}
tmp1->next = tmp2->next;
tmp2->next = NULL;
free(tmp2);
return true;
}
// //通过数据删除节点
bool DelNode_Data(LList_t *head,DataType_t data)
{
LList_t *tmp1 = head;
LList_t *tmp2 = head->next;
//判断条件改成对比数据是否相等，不相等进去循环，往后遍历，相等跳出循环，删掉数据
while(tmp2->data != data)
{
tmp1 = tmp2;
tmp2 = tmp2->next;
//判断链表中是否有匹配的数据，没有打印printf("链表中没有你要删除的数据!\n")
if (tmp2->next == NULL)
{
printf("链表中没有你要删除的数据!\n");
return false;
}
}
tmp1->next = tmp2->next;
tmp2->next = NULL;
free(tmp2);
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[])
{
//创建了一个空链表,定义了head指针变量接受返回值头节点
LList_t *head = LList_Create();
//头插插入链表
LList_HeadInsert(head,1);
LList_HeadInsert(head,2);
LList_HeadInsert(head,3);
LList_HeadInsert(head,4);
LList_HeadInsert(head,5);
LList_HeadInsert(head,6);
LList_Print(head);
printf("\n");
//尾插
printf("尾插发:\n");
LList_TailInsert(head,10);
LList_TailInsert(head,100);
LList_Print(head);
printf("\n");
//向某个位置插入
printf("向某个位置插入:\n");
LList_DestInsert(head,4,255);
LList_DestInsert(head,6,1000);
// LList_DestInsert(head,15,255);
LList_Print(head);
printf("删除完后的链表:\n");
// DelNode(head,7);
// DelNode(head,15);
HeadDel(head);
TailDel(head);
DelNode_Data(head,1000);
LList_Print(head);
return 0;
}