C语言使用二级指针借助递归工作栈删除单链表中所有值为x的元素

在我的上一篇随笔中，介绍了单链表的增删查改清空等操作，在实现按值删除的功能时，只能删除第一个目标元素，或者只能删除部分目标元素；

我参考了王道的《数据结构》考研复习指导书（2021年）中的代码（P47），实现了在C语言中，借助一个递归工作栈，删除单链表中所有值为x的元素的功能，由于C语言中没有引用（&）传参这个概念，故需借助二级指针来实现。

代码运行结果如下图所示：

代码如下：

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>
//定义结点
typedef struct _node {
    int value;
    struct _node * next;
} Node;

//定义结构体List存放链表的信息，如：头结点（如果有的话）或首结点、尾结点、链表长度等等
typedef struct _list
{
    Node* head;//始终指向首结点
    Node* tail;//始终指向尾结点
} List;
//初始化
bool InitList(List* pList)
{
    pList->head = pList->tail = NULL;
    return true;
}
//判空
bool Empty(List* pList)
{
    return (pList->head==NULL);
}

//结点添加（尾添加）
Node* List_AddOnTail(List* pList, int number)//传入指针的指针
{
    //分配结点空间，并写入p->value
    Node* p = (Node*)malloc(sizeof(Node));
    p->value = number;
    p->next = NULL;
    if(pList->head == NULL)//如果链表是空的，最新分配的结点（p）既是head，也是tail
    {
        pList->head = p;
        pList->tail = p;
    }
    else//如果链表不是空的，只需要处理tail
    {
        pList->tail->next = p;//此时链表的尾结点要指向新分配的结点
        pList->tail = p;//新分配的结点成为链表的tail
    }
    pList->tail->next = NULL;//tail的后继指针必须是NULL

    return pList->head;
}

//遍历输出链表
void List_Print(List* pList)
{
    Node* p;
    for(p=pList->head; p; p=p->next)
    {
        printf("%-6d", p->value);
    }
    printf("\n");
}
/*
删除链表中所有值为x的结点
借助一个递归工作栈 O(n)
需要使用二级指针Node** L
    第1层递归中*L是链表list的头指针，即*L==list.head；
    第n（n>1）层递归中*L指向的是第n-1层递归中的*L指向的结点的后继结点，即*L(n)==*L(n-1)->next
*/
void List_Delete_AllTargetNode_ByValue(Node** L, int x)//形参L是结点的指针的指针
{
    Node* p;
    if(*L == NULL)//终止条件是指针为空，尾结点的next指针为NULL
        return;
    if((*L)->value == x)//当前结点的元素为x，为要删除的目标结点
    {
        //删除当前（目标）结点
        p = *L;//临时指针p指向当前结点
        *L = (*L)->next;//*L指向下一个结点
        free(p);//释放当前结点所占的内存空间
        List_Delete_AllTargetNode_ByValue(L, x);//递归，进行下一个结点的处理
    }
    else//当前结点不是目标结点，则处理后继结点，这里后继结点的表示方法有点绕
    {
        List_Delete_AllTargetNode_ByValue(&((*L)->next), x);//(*L)->next是指向后继结点的指针，需要对其取地址后传回
    }
}

int main(void)
{
//创建并初始化，输入元素
    List list;
    InitList(&list);
    int number;
    printf("请输入整数（输入-1结束）：\n");
    do
    {
         scanf("%d", &number);
        if(number != -1)
        {
            list.head = List_AddOnTail(&list, number);//注意这里要传入head的地址
            //list.head = List_AddOnHead(&list, number);
        }
    }while(number != -1);
//遍历并输出链表
    printf("链表中的元素为：");
    List_Print(&list);

    int x;
    printf("请输入您要删除的元素：");
    scanf("%d", &x);
    List_Delete_AllTargetNode_ByValue(&(list.head), x);//list.head是头指针，这里传入其地址

    printf("当前链表中的元素是：\n");
    List_Print(&list);

    return 0;
}

欢迎各位朋友与我探讨交流，帮助指出我的错误或不妥之处，给出您宝贵的意见或者建议！谢谢！

【本文来源：美国服务器 https://www.68idc.cn 复制请保留原URL】