c - C中递归的单链表删除函数

Question

我正在尝试为 c 语言项目制作学生名单程序内部的函数有3个 insert = 将学生插入列表中 print = 打印出可用的学生 删除 = 从列表中删除学生

我已经创建了该程序，并且使用所有三个函数都可以正常工作现在我想使用递归来制作相同的列表。

我已经使打印功能递归并且它正在工作现在我试图让删除功能以同样的方式工作不幸的是我没能让它发挥作用

在下面的代码中，如果您运行它，您将看到它仅在您不尝试删除列表中的最后一个节点并且不告诉它删除不存在的节点时才有效。

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct tf *tp;
            struct tf{
            int am;
            double gr;
            tp next;
            };

        tp head, tail, temp, aux;

    void insert1 (tp *h, tp t);
    void print1(tp h);
    void delete1(tp *h,int da);



    int main()
    {
        char fry, fry2;
        int am;
        fry = 'a';
        head = NULL;
        tail = NULL;

        while (fry != 'q')
        {
            printf("\n character given is %c\n", fry);
            if (fry != 'q')
            {
                printf("new choice\n");
                fry = 'a';
                fflush(stdin);
                fry = getchar();
                getchar();
                if (fry == 'q')
                    printf("quit\n");
                if (fry == 'i')
                {
                    fry2 = fry;
                    printf(" insert new student number am\n");
                    insert1(&head,tail);
                    fry = fry2;
                }
                if (fry == 'd')
                    {printf(" delete \n");
                    printf(" am number of student to be deleted\n");
                    scanf("%d", &am);
                    delete1(&head,am);
                    }

                if (fry == 'p')
                {
                    printf("\n printing\n");
                    print1(head);
                }
            }
        }
    }

    void insert1 (tp *h, tp t)
    {
        tp te, a;
        int da;
            te = (tp)malloc(sizeof(struct tf));
            printf(" am number for the new insert\n");
            scanf("%d", &da);
            getchar();
            te->am = da;
            te->next = NULL;
                printf("am number is %d",te->am);
                if ((*h != NULL) && (te->am < (*h)->am))
                {
                    te->next = *h;
                    *h = te;
                }

             if((*h != NULL) && ((*h)->next != NULL) && (te->am > (*h)->am))
             {
                 a=*h;
                 while((a->next != NULL) && (a->next->am < te->am))
                 {
                     a= a->next;
                 }
                 te->next = a->next;
                 a->next = te;
             }

             if((*h != NULL) && ((*h)->next == NULL) && (te->am > (*h)->am))
             {
                 (*h)->next = te;
             }

             if(*h == NULL)
             {
                 printf("\n head is null");
                 *h = te;
                 t = te;
             }
    }



    void print1(tp h)
    {
        tp a;
        a=h;
        if (a==NULL)
            return;
        printf("%d\n",a->am);
        print1(a->next);
    }




    void delete1(tp *h,int da)
    {
        tp a= *h,t= *h,temp = NULL;
        if ((*h) != NULL)
        {
            if ((*h)->am!=da)
            {
                if (a->next->am != da && a->next!=NULL)
                {
                    delete1(a->next,da);
                }
                else
                {
                    if (a->next==NULL)
                    {
                        printf("am not found\n");
                        return;
                    }
                    else
                    {
                        temp = a->next;
                        a->next = a->next->next;
                        free(temp);
                    }
                }
            }
            else
            {
                a = (*h);
                (*h)= (*h)->next;
                free(a);
            }
        }
        else
        {
            printf("empty list");
        }


    }

如您所见，我希望删除函数通过查找给定的 am 编号来删除节点，因此它将首先搜索列表以查找 am 编号是否存在。

如果有人能给我一些关于如何使删除功能发挥作用的提示，我将不胜感激。

Answer 1

有几件事正在发生。这一行:

if (a->next->am != da && a->next!=NULL) ...

应该交换条件，否则您可能会访问a->next而不首先验证它不是NULL。辅助变量a和其他临时变量令人困惑而不是有帮助。

您将 head 作为指针传递给 delete1 函数，以便可以更新 head。但这不仅仅影响头部:这在整个迭代过程中增加了一定程度的间接性。

对于迭代调用，这意味着您必须传递存储当前节点引用的指针的地址，(*h)->next。一开始，这是头部的地址。在后续迭代中，这是前一个节点的 next 指针的地址。

也无需考虑各种情况。代码可以很简单:

void delete1(tp *h, int da)
{
    if (*h != NULL) {
        if ((*h)->am == da) {
            tp next = (*h)->next;

            free(*h);
            *h = next;
            return;
        }

        delete1(&(*h)->next, da);
    }
}

递归调用发生在函数末尾，或者根本不发生。这意味着您可以将代码重写为循环:

void delete1(tp *h, int da)
{
    while (*h != NULL) {
        if ((*h)->am == da) {
            tp next = (*h)->next;

            free(*h);
            *h = next;
            return;
        }

        h = &(*h)->next;
    }
}

这将为您节省大型列表上的一些堆栈空间。您的 insert1 函数也可以得到清理和简化。