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

一：为什么要删除节点

        （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 
#include 
#include 
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;
}

运行结果：

五：注意堆内存的释放

        （1）当程序运行结束时堆内存就会被释放，在结束之前没有free释放掉的堆内存也会被释放掉

        （2）有时候程序运行时间久，这时候malloc的内存没有free会一直被占用直到free释放或程序终止