удалить элементы в единственном связанном списке

Question

в этом коде я удаляю элемент в связанном списке

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

, если я хочуdelete 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

Я думаю, что здесь prev->link=temp->link prev - это свисает.Если это первый узел, просто переместите указатель и освободите

Answer 2

Проблема в 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 3

Если вы удаляете первый элемент, то здесь никогда не вводите while(temp->info!=key&&temp->link!=NULL), и prev неинициализирован, а prev->link вызовет ошибку segf (поскольку вы разыменовываете неинициализированный указатель).

Так что вы, вероятно, получите это здесь: prev->link=temp->link;

Answer 4

Я могу найти две проблемы с вашим кодом, но ни одна из них не будет иметь проблемы с вашим примером ввода.

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 5

Основная проблема с вашим кодом удаления состоит в том, что первый элемент должен рассматриваться как особый случай, поскольку первым может быть узел, который должен быть удален, и поэтому сначала может потребоваться обновить новый узел. Это может быть решено с помощью двойного указателя, такого как 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 не требуется.

Answer 6

И, наконец,

Разве ранее не нужно присваивать?

Я вижу его назначенным в закомментированном разделе, но больше нигде.И, очевидно, нужно проверить его на нулевое значение в случае, если первый элемент соответствует ключу.

Answer 7

Удалите галочку temp->info!=key из файла и сделайте это, если внутри тела while будет стартер.