前言
🎬 个人主页：@ChenPi
🐻推荐专栏1: 《C++_@ChenPi的博客-CSDN博客》✨✨✨
🔥 推荐专栏2: 《Linux C应用编程（概念类）_@ChenPi的博客-CSDN博客》✨✨✨
📝推荐专栏3: 《 链表_@ChenPi的博客-CSDN博客》 ✨✨✨
🍉本篇简介 : 链表数据插入之尾插法
✨ 只有我努力了 才有机会接触成功✨
链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
作为有强大功能的链表，对他的操作当然有许多，比如：
- 链表的创建
- 链表的链表的遍历打印数据
- 链表里面的结构体数据的修改
- 链表节点的删除
- 链表插入新节点
- 链表的数据排序
- 链表的反序
- 清空链表的元素
- 求链表的长度等
在前面几章，我们学习了
- 链表的创建
- 链表的链表的遍历打印数据
- 链表里面的结构体数据的修改
- 求链表的长度等
- 还有链表结尾插入数据节点，非指定节点
- 链表指定节点后方插入数据
- 链表头插入新节点以及头插法创建链表
对链表的操作我们还差链表指定节点的删除，反序以及清空链表
这章我们学习链表指定节点删除
01 链表删除指定节点
首先，我们先确定函数的大致操作
我们定义一个函数名为deleteHeadLinkNode
有两参数，参数1为链表的头节点，参数2为一个整形变量的索引NodeIndex
索引值则是要删除的节点，如索引值等于1，择删除第一个节点
返回值则是一个结构体指针，返回值为链表头的地址
struct Link * deleteHeadLinkNode(struct Link *head,int NodeIndex)
{
}函数体大致这样，首先，我们要判断索引值是否越界
/*获取链表的节点数*/
int GetLinkNum(struct Link *head)
{
struct Link *prev = head;
int count = 0;
while (prev != NULL)
{
count++;
prev = prev->next;
}
return count;
}
struct Link * deleteHeadLinkNode(struct Link *head,int NodeIndex)
{
struct Link *prev = head; //保存头节点的地址
if(NodeIndex > GetLinkNum(prev)||(NodeIndex<0)) //判断是否越界
{
printf("ERROR: Link index out of range");
return NULL;
}
}
上面这段代码为检测索引值有没有越界，越界的意思是，比如我链表的长度为5，当传进来的索引值为7，那链表总共就5个节点，这么删除第七节点嘛，所以越界了
其实其中的每一部分都可以写成一个函数了，这样模块话，可以减少很多功夫，我们下一章在讲模块化的问题把
现在我们看上面图的第二个红框框，这部分就是删除链表的头节点了，我们分析下代码
当索引值为1的时候，我们让链表的头节点等于链表头的下一个节点就可以
然后释放prev
prev在第一个红框里已经被指向头节点
第三个红框框则是本章的重点了，因为我们创建链表是在堆中创建的，属于是动态创建的链表
所以我们释放要删除的节点要格外小心
不然就很容易出BUG
首先我们要定义一个结构体的指针prior，指向用于保存前节点的地址，然后就是遍历
定义整形变量记录目前遍历到第几节点，如果找到了目标节点，判断是否为链表尾
如果是，就让保存的前节点的next等于NULL就行，然后释放prev
正常节点也如此
我们测试一下，我们调用函数，删除第二节点，我们看下打印，从 4 2 5 3变为4 5 3了，第二节点已经被释放
测试代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Link
{
int data;
struct Link *next;
};
/*打印链表数据*/
void PrintLink(struct Link *head)
{
struct Link *prev = head;
while (NULL != prev)
{
printf("%d ", prev->data);
prev = prev->next;
}
printf("\n");
}
/*获取链表的节点数*/
int GetLinkNum(struct Link *head)
{
struct Link *prev = head;
int count = 0;
while (prev != NULL)
{
count++;
prev = prev->next;
}
return count;
}
struct Link *getHead(int data)
{
struct Link* head = (struct Link*)malloc(sizeof(struct Link));
head->data = data;
head->next = NULL;
return head;
}
/* 链表头插入数据，不指定位置*/
struct Link* frontInsertDataLink(struct Link *head, int data)
{
struct Link *prev = head;
struct Link *newLink = (struct Link *)malloc(sizeof(struct Link));
newLink->data = data;
newLink->next = prev;
return newLink;
}
struct Link *frontInsertNodeDataLink(struct Link *head,int NodeIndex,int data)
{
struct Link *prev = head;
int cnt = 1;
if(NodeIndex > GetLinkNum(prev)||(NodeIndex<0))
{
printf("ERROR: Link index out of range");
return NULL;
}
else if (NodeIndex == 1)
{
prev = frontInsertDataLink(prev,data);
return prev;
}
while (NULL != prev->next)
{
if(cnt == NodeIndex-1)
{
struct Link *newLink = (struct Link *)malloc(sizeof(struct Link));
newLink->data = data;
newLink->next = prev->next;
prev->next = newLink;
return head;
}
cnt++;
prev = prev->next;
}
return NULL;
}
struct Link * deleteHeadLinkNode(struct Link *head,int NodeIndex)
{
struct Link *prev = head; //保存头节点的地址
int cnt = 1;
if(NodeIndex > GetLinkNum(prev)||(NodeIndex<0)) //判断是否越界
{
printf("ERROR: Link index out of range");
return NULL;
}
if(1 == NodeIndex) //如果要删除头节点
{
head = head->next;
free(prev);
return head;
}
struct Link *prior = NULL; //遍历时用来保留前一个节点的状态
while (NULL != prev) //判断是不是最后一个节点
{
prior = prev;//用来保留前一个节点的状态
prev = prev->next; //走向下一个节点，也就是循环增量
if(cnt == NodeIndex-1) //找到需要删除的节点
{
if(NULL == prev->next) //1.如果找到的是尾节点
{
prior->next = NULL; //原来尾节点的前一个为节点变成了新尾节点
free(prev); //释放原来尾节点的内存
return head;
}
else //如果找到的是普通节点
{
prior->next = prev->next; //要删除的节点的前一个节点和后一个节点相连
free(prev);
return head;
}
}
cnt++;
}
return NULL; //没找到对应节点，操作失败，返回NULL
}
int main()
{
struct Link *head = getHead(3);
head = frontInsertDataLink(head, 5);
head = frontInsertDataLink(head, 2);
PrintLink(head);
head = frontInsertNodeDataLink(head, 1,4);
PrintLink(head);
head = deleteHeadLinkNode(head,2);
PrintLink(head);
return 0;
}
我们下一期写一下 清空链表吧
🌺对您有帮助的话记得点赞加关注
🌺如果有说的不对的欢迎指正
