usuwanie elementu z listy jednokierunkowej

typedef struct Node
{
    int Value;              //wartosc przechowywana
    struct Node *Next;      //wartosc na nastepny element
} Node;

/* deklaracja typu klasy listy jednokierunkowej */
typedef struct List
{
    unsigned int Size;
    Node *back; // front
} List;

int main(void)
{
    List lista1;

    ListInit(&lista1);

    ListAdd(&lista1, 1);
    ListAdd(&lista1, 2);
    ListAdd(&lista1, 3);

    showList(&lista1);
    ListAdd(&lista1, 4);

    DelElement(&lista1, 4);
    showList(&lista1);


    ListClear(&lista1);

    return 0;
}

 int DelElement(List* list, int value)
{
    Node* tmp = NULL;

    tmp = list->back;

    if(!list)
        return -1;

    while(tmp != NULL)
    {
        if(tmp->Value == value)
        {
            if(tmp->Next == NULL)
            {
                free(tmp);

                //tmp == NULL;
                --(list->Size);
                //tmp = NULL;
                break;

            }
            //free(tmp);
            //tmp->Next;

        }

        tmp = tmp->Next;
    }

void showList(List* list)    // wyświetla wszystkie elementy listy
{
    Node* tmp = list->back;

    while(tmp)
    {
        printf("%d ", tmp->Value);

        tmp = tmp->Next;
    }

    printf("\n");
}

Dlaczego po usunięciu jednego elementu przy wyswietlaniu wszystkich elementów z listy w miejsce usuniętego pojawia się wartość 0. Rekord chyba powinien zostać pominięty.

A dlaczego rekord, który istnieje ma być pominięty? Przecież go nie usuwasz. Funkcja DelElement() zwalnia pamięć przydzieloną dla rekordu, gdy jest on ostatnim na liście i przechowywana wartość jest równa przekazanej. Poprzedni element w liście wtedy zaczyna wskazywać "w kosmos", bo nawet nie aktualizujesz jego Next. Zastanów się uważnie nad tym kodem, bo są w nim poważne błędy.

int DelElement(List* list, int value)
{
    Node* tmp = NULL;
    Node* tmp1 = NULL;

    if(!list)
        return -1;

    tmp = tmp1 = list->back;

    if(tmp->Value==value)           /* Sprawdzamy czy nie usywamy 1 element z listy */
    {
        free(tmp);
        list->back = tmp->Next;

        return 0;
    }

    tmp1 = tmp1->Next;

    while(tmp)
    {
        if(tmp1->Value == value)
        {
            tmp->Next = tmp1->Next;
            break;
        }
        tmp = tmp->Next;
        tmp1 = tmp1->Next;
    }

    free(tmp1);
    --(list->Size);

    return 0;
}

Czyli coś takiego ...

1. Czy nie ma w kodzie żadnego błędu
2. Czy nie da się tego zapisać w jakiś lepszy sposób

Wciąż masz błędy.

1. Pomyśl co się stanie, gdy zechcesz tą funkcją usunąć element przechowujący wartość X, lecz takiego elementu nie będzie.
2. Pomyśl co się dzieje przy wywołaniu free(tmp1).
3. Przypisanie do tmp1 w tmp = tmp1 = list->back jest niepotrzebne, gdyż w kolejnej instrukcji nadpisujesz wartość.
4. back to nie jest dobra nazwa na określenie początku listy (zazwyczaj używa się front, head czy first). Wprowadza w błąd gdyż sugeruje, iż wskazuje na ostatni element.
5. Jako wartość zwracaną używasz -1 lub 0, co uniemożliwia użycie funkcji np. w if (DelElement(...)).
6. Węzeł tmp1 jest wyprzedzający. Pomyśl co się stanie, gdy tmp dojdzie do ostatniego elementu w liście.
7. W list->back = tmp->Next próbujesz pobrać wartość ze struktury, która została zdealokowana w poprzedniej instrukcji.
8. Pomyśl co się stanie, gdy struktura listy będzie istniała, lecz nie będzie zawierała żadnego elementu, a Ty wywołasz na niej tę funkcję.

Ogólnie idziesz w dobrym kierunku, ale musisz dopracować kod i zwracać większą uwagę na różne przypadki, w jakich ta funkcja może działać. Jeśli czegoś nie rozumiesz, pytaj śmiało. Spróbuj jednak najpierw sam sam przeanalizować kod i moje uwagi.

int DelElement(List* list, int value)
{
    Node* tmp = NULL;
    Node* tmp1 = NULL;

    if(!list || list->Size == 0)      /* Lista jest nie zainicjowana lub pusta*/
        return -1;

    tmp =list->front;

    if(tmp->Value==value)            /* Sprawdzamy czy nie usywamy 1 element z listy */
    {
        tmp = tmp->Next;
        free(tmp);
        --(list->Size);

        return 0;
    }

    while(tmp)
    {
        if((tmp1 = tmp->Next) == NULL)      /* brak takiego rekordu */
            return -2;

        if(tmp1->Value == value)
        {
            tmp->Next = tmp1->Next;
            break;
        }
        tmp = tmp->Next;
    }

    free(tmp1);
    --(list->Size);

    return 0;
} 

Poprawione... Niestety punkt 3 był wymagany z poprzedniego programu.
Nie wiem dlaczego zwracanie wartości -1 czy 0 może wpłynąć na uniemożliwienie użycia funkcji z punktu 5.

Wprowadziłem małe poprawki. Teraz jakieś błędy?
Jeśli nie czy można to zapisać w bardziej lukratywny sposób?

Kumashiro dzięki za przedstawienie moich błędów... zaczynam dopiero uczyć się struktury danych skąd takie bezmyślne podejście.

goransol napisał(a)

    if(tmp->Value==value)            /* Sprawdzamy czy nie usywamy 1 element z listy */
    {
        tmp = tmp->Next;
        free(tmp);
        --(list->Size);

        return 0;
    }

To też niestety jest źle. Powiedzmy, że element A ma jako następnik element B. Chcesz usunąć A, przesuwając wcześniej B, jednakże w rzeczywistości nadpisujesz A i usuwasz B, w rezultacie otrzymując memory leak i utratę danych. Chodzi o to, że w momencie wywołania free(), zmienna tmp wskazuje już na co innego niż to, co chcesz usunąć.

Co do pętli while()... Jest lepiej, ale nie sprawdzasz ostatniego elementu. Problemem jest tutaj warunek (tmp1 = tmp->Next) == NULL, który powoduje zakończenie funkcji zanim sprawdzisz zawartość tmp1. Popracuj jeszcze nad tym.

goransol napisał(a)

Nie wiem dlaczego zwracanie wartości -1 czy 0 może wpłynąć na uniemożliwienie użycia funkcji z punktu 5.

Powód jest bardzo prosty. W poprzedniej wersji używałeś -1 do zwrócenia błędu i 0 jeśli wszystko było OK. Problem w tym, że if ( -1 ) daje logiczną prawdę, co staje się bez sensu przy zapisie if (DelElement()) (warunek byłby prawdziwy tylko w przypadku błędu, co źle się odczytuje). Kiedy jednak dodałeś jeszcze -2, przestało to mieć znaczenie. Jeśli funkcja może zwrócić jedną z dwóch wartości, lepiej jest użyć 0 w przypadku błędów i/lub nieudanej operacji oraz 1 jeśli wszystko poszło dobrze.

goransol napisał(a)

Jeśli nie czy można to zapisać w bardziej lukratywny sposób?

Nie rozumiem co masz na myśli pisząc "lukratywny", bo chyba nie pytasz czy da się na nim więcej zarobić? ;)
Jeśli chcesz żeby ten kod był wydajniejszy to da się, ale o ile nie będziesz wykonywał milionów operacji na sekundę na tej liście, nie będzie to miało większego znaczenia. Kompilator pewnie i tak to zoptymalizuje.
Jeśli pytasz czy da się go napisać ładniej, to tutaj nie jest już tak różowo. Z listami powiązanymi jest ten problem, że albo pisze się przejrzysty lecz dość rozwlekły kod ze zmiennymi pomocniczymi, albo tworzy się zwięzłego, semantycznego potworka, omijanego szerokim łukiem przez wszystkich... łącznie z twórcą.

goransol napisał(a)

Kumashiro dzięki za przedstawienie moich błędów... zaczynam dopiero uczyć się struktury danych skąd takie bezmyślne podejście.

Nie nazwałbym tego bezmyślnym podejściem. Nieuważnym, już bardziej. Trudno jednak wymagać pamiętania o wszystkim od kogoś, kto dopiero się uczy. Lista powiązana to nie jest łatwy temat (na początku) i jej tworzenie wymaga dużo skupienia, albo w którymś momencie skończy się to katastrofą. Zapewne dlatego ten temat jest często wykorzystywany na uczelniach jako ćwiczenie. Staraj się analizować dokładnie działanie algorytmu w różnych przypadkach, rób testy, używaj programu typu valgrind do znajdowania wycieków pamięci i będzie OK. No i przede wszystkim nie bój się eksperymentować. Komputer Ci nie wybuchnie jak zrobisz jakiś błąd w kodzie... najwyżej Ci program zeżre cały RAM ;)

    if(tmp->Value==value)                   /* Sprawdzamy czy nie usywamy 1 element z listy */
    {
        free(tmp);
        list -> front = tmp->Next;
        --(list->Size);

        return 0;
    } 

Dealokacja na rekordzie A. Następnie zmieniamy początkowy rekord na B. Dobrze to rozumiem czy jednak do tego źle podchodzę?

Napisałeś:

Co do pętli while()... Jest lepiej, ale nie sprawdzasz ostatniego elementu. Problemem jest tutaj warunek (tmp1 = tmp->Next) == NULL, który powoduje zakończenie funkcji zanim sprawdzisz zawartość tmp1. Popracuj jeszcze nad tym.

Rzuć okiem moim zdaniem program sprawdza (nawet przetestowałem dla upewnienia). Trochę poplątane z tym tmp1 i tmp.

goransol napisał(a)

Dealokacja na rekordzie A. Następnie zmieniamy początkowy rekord na B. Dobrze to rozumiem czy jednak do tego źle podchodzę?

Odwołujesz się do czegoś, co już nie istnieje. Obszar pamięci wskazywany przez tmp został zdealokowany funkcją free(), a Ty próbujesz z niego jeszcze coś wyciągać. Zróbmy eksperyment (typy nie maja tu większego znaczenia):

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


struct Test {
    int     Next;
};


int  main(void)
{
    struct Test     *test;


    test = (struct Test*)malloc(sizeof(struct Test));
    test->Next = 1;
    printf("Przed free(): %d\n", test->Next);
    free(test);
    printf("Po free(): %d\n", test->Next);

    return 0;
}

Wynikiem działania u mnie jest:

Przed free(): 1
Po free(): 0

goransol napisał(a)

Rzuć okiem moim zdaniem program sprawdza (nawet przetestowałem dla upewnienia). Trochę poplątane z tym tmp1 i tmp.

A, możliwe. Przed szóstą kawą mogę nie widzieć niektórych rzeczy...

EDIT: może rozbuduję przykład, żeby było widać lepiej czym jest dealokacja:

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


struct Test {
    long     Next;
};


int  main(void)
{
    struct Test     *test;
    long            *foo;


    test = (struct Test*)malloc(sizeof(struct Test)); /* Alokujemy strukturę */
    test->Next = 1;
    printf("Przed free(): %li\n", test->Next); /* Drukujemy wartość w strukturze */
    free(test); /* Dealokujemy strukturę */

    foo = (long*)malloc(sizeof(long)); /* Alokujemy long */
    *foo = 42;
    printf("Po free(): %li\n", test->Next); /* Drukujemy ponownie wartość w strukturze */

    return 0;
}

Wynik działania u mnie:

Przed free(): 1
Po free(): 42

Widać wyraźnie, że system wykorzystał zwolnioną pamięć na alokację miejsca pod nowe dane (podpasowało mu rozmiarowo). Drugie odwołanie do struktury (która już nie istnieje) zwraca nam wartość nowej zmiennej, nawet mimo tego, że nazywają się inaczej.
Język C daje względnie dużą swobodę w pałętaniu się po pamięci, ale nie oznacza to, że należy jej nadużywać.

int DelElement(List* list, int value)
{
    Node* tmp = NULL;
    Node* tmp1 = NULL;
    Node* del = NULL;

    if(!list || list->Size == 0)            /* Lista jest nie zainicjowana lub pusta */
        return -1;

    del= tmp =list->front;

    if(del->Value==value)                   /* Sprawdzamy czy nie usywamy 1 element z listy */
    {
        tmp = del->Next;
        free(del);
        list->front = tmp;

        --(list->Size);

        return 0;
    }

    while(tmp)
    {
        if((tmp1 = tmp->Next) == NULL)      /* brak takiego rekordu */
            return -2;

        if(tmp1->Value == value)
        {
            tmp->Next = tmp1->Next;
            break;
        }
        tmp = tmp->Next;
    }

    free(tmp1);
    --(list->Size);

    return 0;
}

Teraz wiem o co chodzi... Dzięki. No chyba że mózg pracuje na zwolnionych obrotach i dalej coś nie tak.

Jak na pierwszy raz wygląda ok (jeśli działa). No to Ci zostało jeszcze dodawanie elementów na końcu, na początku, wstawianie, przeszukiwanie, transformacja do tablicy, ...
Have fun :)

EDIT: jeszcze tylko się upewnij czy wiesz dlaczego jest --(list->Size) i czy można zastosować tutaj list->Size--... Takie małe ćwiczonko ;)

Kumashiro napisał(a)

EDIT: jeszcze tylko się upewnij czy wiesz dlaczego jest --(list->Size) i czy można zastosować tutaj list->Size--... Takie małe ćwiczonko ;)

No właśnie... te 2 zapisy są równoważne w miejscach gdzie są wykorzystywane.