删除单链表中的元素

Question

在此代码中，我正在删除链表

11->12->13->14->15->12->16

中的元素，如果我想删除 12，它仅删除第一次出现的元素元素即o/p将是

11->13->14->15->12->16，

但我想删除所有出现的12，该怎么做？

谁能给我一些意见吗？

    #include<stdio.h>
    #include<stdlib.h>
    void insertbeg();
    void delpos();
    void display();
    struct node
    {
            int info;
            struct node *link;
    }*first=NULL;

    struct node *create();
    int item,key;
    main()
    {
            int choice;
            while(1)
            {
                            printf("\nchoices are:\n");
                            printf("\n1.Insertbeg\n 2.delpos\n 3.display\n 4.exit\n");
                            printf("Enter U'r choice: ");
                            scanf("%d",&choice);
                            switch(choice)

                            {
                                            case 1: insertbeg(); break;
                                            case 2: delpos(); break;
                                            case 3: display(); break;
                                            case 4: exit(1);
                          default: printf("INVALID CHOICE TRY AGAIN\n");
                           }
            }
    }
    struct node *create()
    {
            struct node *new;
            new=(struct node*)malloc(sizeof(struct node));
            return(new);
    }
    void insertbeg()
    {
            struct node *new;
            new=create();
            printf("Enter element to be inserted: ");
            scanf("%d",&item);
            if(first==NULL)
            {
                            new->info=item;
                            new->link=NULL;
                            first=new;
            }
            else
            {
                            new->info=item;
                            new->link=first;
                            first=new;
            }
    }


    void delpos()
    {
            int key;
            struct node *temp,*prev;
            if(first==NULL)
            {
            printf("LIST IS EMPTY\n");
                            return;
            }
            else
            {
                            temp=first;
                            printf("Enter the KEY element which is to be deleted: ");
                            scanf("%d",&key);
                       /*     while(temp->info!=key&&temp->link!=NULL)
                    {
                                            prev=temp;
                                            temp=temp->link;
                            }
                            if(temp->info==key)
                     {
                                            prev->link=temp->link;
                                            free(temp);
                            }
                            else
                                          printf("key element not found in the list\n");
            */

                while(temp->link != NULL)
                    {
                        if(temp->info == key)
                        {
                        prev->link = temp->link;
                        free(temp);
                        temp = prev->link;
                        temp = temp->link; 
                        }
                        else
                            temp = temp->link;
                    }
            }
    }

    void display()
    {
            struct node *temp;
            temp=first;
            if(temp==NULL)
            {
                            printf("LIST IS EMPTY\n");
                            return;
            }
            else
            {
                            printf("Elements in Linked Lists: ");       

            while(temp!=NULL)
                            {
                                           printf("%d->",temp->info);
                                            temp=temp->link;
                            }
            }
    }

Answer 1

我可以发现您的代码有两个问题，但它们都不会显示您的示例输入存在问题。

1-

while(temp->link != NULL)

应该是

while(temp!=NULL)

2- temp = temp->link; 在 中是多余的

if(temp->info == key)
{
   prev->link = temp->link;
   free(temp);
   temp = prev->link;
   temp = temp->link; 
}

，会跳过一个元素。

Answer 2

如果删除第一个元素，则永远不会在此处输入 while(temp->info!=key&&temp->link!=NULL) 和 prev未初始化，并且 prev->link 将导致段错误（因为您取消引用未初始化的指针）。

所以你可能会在这里得到它：prev->link=temp->link;

Answer 3

我认为这里 prev->link=temp->link prev 是悬空的。
如果是第一个节点，只需移动指针并释放

Answer 4

问题出在 delpos 中：

prev->link=temp->link;

当您位于列表的第一个元素（即 11）时，prev 尚未设置为任何内容。 在这种情况下， while 循环

while(temp->info!=key&&temp->link!=NULL)

永远不会执行，因此 prev 保持未设置状态。

另一个问题是，当删除列表的第一个元素时，变量first仍将指向列表的原始第一个元素，而不是第二个元素。

一种解决方案是这样的

 ...

 temp=first;
 prev=NULL;                  /* Added */
 printf("Enter the KEY element which is to be deleted: ");
 scanf("%d",&key);
 while(temp->info!=key&&temp->link!=NULL)
 {
     prev=temp;
     temp=temp->link;
 }
 if(temp->info==key)
 {
     if (prev==NULL)         /* Added */      
         first=temp->link;   /* Added */
     else                    /* Added */
         prev->link=temp->link;
     free(temp);
 }

 ...

Answer 5

从文件中删除检查 temp->info!=key 并在 while 主体内使用 if 来执行此操作将是一个启动器。

Answer 6

最后，

prev 不需要分配吗？

我可以在注释掉的部分看到它的分配，但在其他地方看不到它。显然，如果第一个元素与键匹配，则需要对其进行空检查。

Answer 7

删除代码的主要问题是第一个元素需要被视为特殊情况，因为第一个元素可能是即将删除的节点，因此第一个元素可能需要使用新节点进行更新。这个可以通过使用像struct node ** temp = &first; 这样的双指针来解决。不过，我试图接近你原来的帖子。

    // special condition if first should be removed.
    temp = first;
    while ( temp != NULL && temp->info == key ){
        first = temp->link;
        free(temp);
        temp = first;
    }

    // Here temp->info should not be removed(or it is NULL)
    // lets look at temp->link->info and remove temp->link
    while (temp!=NULL && temp->link != NULL) {
        if (temp->link->info == key) {

            struct node *to_free = temp->link;
            // temp checks the next node.
            temp->link = temp->link->link;
            free(to_free);
        } else {
            // next link
            temp = temp->link;
        }
    }

请注意，prev 是不必要的。