Узел удаления связанного списка, Простой связанный список

Question

Я пытаюсь реализовать функцию, которая удаляет узлы из связанного списка. Пока что я могу удалить только первый узел списка (3).

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

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

typedef struct nod
{
    int key;
    struct nod *urm;
} NOD;

NOD *first=0,*last=0;

void add(int x)
{
    NOD *p=(NOD*)malloc(sizeof(NOD));
    p->key=x;
    p->urm=0;
    if(0==first)
    {
        first=p;
        last=p;
    }
    else{
        last->urm=p;
        last=p;
    }
}

void delete(int x)
{
    NOD *q,*p;
    if(first->key==x)
    {
        p=first;
        first=first->urm;
        free(p);

    }
    else{
        for(p=q=first;p=0;q=p,p=p->urm)
        {
            if(p->key==x)
            {
            q->urm=p->urm;
            if(p==last)
            {
                last=q;
            }
            free(p);
            }
        }
    }
}

void show()
{
    for(NOD *p=first;p!=0;p=p->urm)
    {
        printf("%d ",p->key);
    }
    printf("\n");
}
int main()
{
    add(3);
    add(1);
    add(2);
    add(5);
    show();

    delete(2);
    show();

    return 0;
}

Answer 1

Для начала код, который вы показали, не является кодом C ++. Это код C.

Это плохая идея определять глобальные переменные, такие как first и last, и когда функции зависят от глобальных переменных. В этом случае вы не можете создать более одного списка в программе.

Что касается функции delete, то в общем случае она имеет неопределенное поведение. Его можно вызвать для пустого списка.

Более того, в этом; l oop

for(p=q=first;p=0;q=p,p=p->urm)

в выражении условия есть опечатка. Вы используете оператор присваивания вместо оператора сравнения.

И функция игнорирует случай, когда список содержит только один узел, потому что в этом случае он не обновляет последний узел.

Тем не менее Используя ваш подход, функция удаления может выглядеть следующим образом.

void delete(int x)
{
    if ( first )
    {
        if ( first->key == x )
        {
            NOD *tmp = first;
            first = first->urm;

            free( tmp );

            if ( first == NULL ) last = NULL;
        }
        else
        {
            NOD *p = first;
            while ( p->urm != NULL && p->urm->key != x )
            {
                p = p->urm;
            }

            if ( p->urm != NULL )
            {
                NOD *tmp = p->urm;
                p->urm = p->urm->urm;

                free( tmp );

                if ( p->urm == NULL ) last = p;
            }
        }
    }
}     

Вот демонстрационная программа.

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

    typedef struct nod
    {

    int key;
    struct nod *urm;
    } NOD;

    NOD *first=0,*last=0;


    void add(int x)
    {

    NOD *p=(NOD*)malloc(sizeof(NOD));
    p->key=x;
    p->urm=0;
    if(0==first)
    {
        first=p;
        last=p;
    }
    else{
        last->urm=p;
        last=p;
    }

    }

void delete(int x)
{
    if ( first )
    {
        if ( first->key == x )
        {
            NOD *tmp = first;
            first = first->urm;

            free( tmp );

            if ( first == NULL ) last = NULL;
        }
        else
        {
            NOD *p = first;
            while ( p->urm != NULL && p->urm->key != x )
            {
                p = p->urm;
            }

            if ( p->urm != NULL )
            {
                NOD *tmp = p->urm;
                p->urm = p->urm->urm;

                free( tmp );

                if ( p->urm == NULL ) last = p;
            }
        }
    }
}  

    void show()
    {
        for(NOD *p=first;p!=0;p=p->urm)
        {
            printf("%d ",p->key);
        }
        printf("\n");
    }
    int main()
    {
        add(10);
        add(20);
        add(30);
        add(40);

        show();

        delete(30);
        show();

        add( 50 );
        add( 60 );
        add( 70 );
        add( 80 );
        show();

        delete(80);
        show();


    return 0;
    }

Ее вывод

10 20 30 40 
10 20 40 
10 20 40 50 60 70 80 
10 20 40 50 60 70 

Answer 2

Вы можете значительно упростить удаление узла из своего списка, используя указатель-указатель до NOD и указатель-указатель NOD для итерации по список. Это позволяет вам установить для узла по текущему адресу значение node->urm, что устраняет необходимость отслеживать предыдущий узел в списке, например

/** delete node with key v from list (for loop) */
void delete (int v)
{
    NOD **ppn = &first;        /* pointer to pointer to first*/
    NOD *pn = first;            /* pointer to first */

    for (; pn; ppn = &pn->urm, pn = pn->urm) {
        if (pn->key == v) {
            *ppn = pn->urm;     /* set node at address to next node */
            free (pn);          /* free deleted node */
            break;
        }
    }
}

См. Линус о понимании указателей для дальнейшего обсуждения преимуществ использования адреса узла в дополнение к указателю на узел.

Answer 3

Я думаю, что ваше условие для l oop неверно внутри функций удаления:

for(q=first, p=first->urm; p!=0; q=p, p=p->urm)

просто измените условие, тогда оно должно работать.