当前位置：首页 > news >正文

C语言单链表的算法之删除节点

news 来源：原创 2024/7/7 22:33:37

一：为什么要删除节点

（1）有时候链表中节点的数据不想要了，就要删除这个节点

二：删除节点的两个步骤

（1）第一步：找到这个节点

（2）第二步：删除这个节点

三：如何找到待删除的节点

（1）通过遍历来查找节点1.从头指针+头节点开始，顺着链表依次将各个节点拿出来，按照一定的方法对比，找到要删除的那个节点

四：如何删除一个节点

1：待删除的节点不是尾节点的情况

（1）第一步：把待删除的节点的前一个节点的pnext指针指向待删除节点的下一个节点的首地址（这样就把要删除的那个节点从链表中摘出来了）

（2）第二步：把这个摘出来的节点free掉

2：待删除的节点是尾节点的情况

（1）第一步：把待删除的尾节点前一个节点的pnext指针指向null（相当于原来尾节点的前一个节点变成了尾节点）

（2）第二步将之前的尾节点free掉

函数实现代码：

/*****************************************
函数名：delete
返回值：0 或 -1 返回0表示删除成功 -1 表示删除失败
参数：ph：单链表的头指针 data：需要删除的节点的数据区存放的数据（通过数据找到对应的节点来删除这个节点）
作用：通过头指针访问单链表，对链表的各个节点进行遍历，当找到某个节点的有效数据区的数据是指定的那个时，删除那个对应的节点
*****************************************/
int delete(struct node *ph,int data)    
{struct node *p = ph;        //定义一个临时指针变量，将它执行头指针struct node *prev = NULL;   //再定义一个临时指针变量用来存放要删除的节点的上一个节点//的位置，因为进行遍历时指针已经指向后面返回不了前面//而要为了实现只是删除某个节点，并且保证链表还是能正常//访问，需要要删除的前一个节点的pnext执行要删除的节点//的后一个节点的首地址，所以需要留有要删除的节点的前一个//节点的位置  int cat = 0;                //用来修改节点计数区while(NULL !=  p->pNEXT)    //判断是否指针NULL    {prev = p;       p = p->pNEXT;   if(p->datas == data)  //判断当前节点是不是要删除的那个节点{//进入即说明这个节点是要删除的节点if(NULL == p->pNEXT)    //再次进行判断这个节点是不是尾节点{       prev->pNEXT  = NULL;   //是尾节点就将要删除的前一个节点//指向NULL让前一个节点变成尾部free(p);               //删除节点 cat = ph->datas;       //临时变量读取头指针数据区存放的//节点数ph->datas = cat -1;    //将之前头指针存放的数据进行-1//再赋值给头指针的有效数据区}else{prev->pNEXT  = p->pNEXT;free(p);cat = ph->datas;ph->datas = cat -1;}   return 0;}    }return -1;}

完整程序代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct node
{int datas;struct node *pNEXT;};struct node *create(int a)
{struct node *p = (struct node *)malloc(sizeof(struct node));if(NULL == p){printf("malloc error!\n");return NULL;}memset(p,0,sizeof(struct node));  //bzero(p,sizeof(struct node));p->datas = a;p->pNEXT = NULL;return p;}void insert_tail(struct node *phead,struct node *new)
{struct node *p = phead;int cat = 0;while(NULL !=  p->pNEXT){p = p->pNEXT;cat++;}p->pNEXT = new;phead->datas = cat +1;}void insert_head(struct node *head,struct node *new)
{new->pNEXT =  head->pNEXT;head->pNEXT = new;head->datas += 1;}void ergodic(struct node *ph)
{struct node *p = ph;int cat = 0;printf("datas number is a: %d\n",p->datas);while(NULL !=  p->pNEXT){cat++;printf("datas number is :%d\n",cat);  p = p->pNEXT;  printf("datas is: %d\n",p->datas);    }}int delete(struct node *ph,int data)
{struct node *p = ph;struct node *prev = NULL;int cat = 0;while(NULL !=  p->pNEXT){prev = p;p = p->pNEXT; if(p->datas == data){if(NULL == p->pNEXT){       prev->pNEXT  = NULL;free(p);cat = ph->datas;ph->datas = cat -1;}else{prev->pNEXT  = p->pNEXT;free(p);cat = ph->datas;ph->datas = cat -1;}   return 0;}    }return -1;}int main(void)
{struct node *phead = create(0);insert_tail(phead,create(12));   insert_tail(phead,create(13));insert_tail(phead,create(14));ergodic(phead);     //遍历打印各个节点数据区delete(phead,13);   //删除数据区为13的节点ergodic(phead);    //再次遍历打印各个节点数据区return 0;}

运行结果：