Lista liczb na podstawie struktur - problem z usuwaniem

0

Witam serdecznie,

Mam sobie taką listę (strukturę), która działa jako globalna (przynajmniej taki był mój cel):

struct element {
    int data;
    struct element *next;
} list;

struct element *ptr = &list;

Funkcja, która pozwala umieszczać na liście różne liczby wygląda tak:

int insert(struct element **begin, int x) {

    struct element *ntr;
    ntr =  (struct element *)malloc(sizeof(struct element));
    if (!ntr) {
        printf("Memory allocation failure!\n");
        return 0;
    }

    ntr->data = x;

    ntr->next = *begin;
    *begin = ntr;

    return 1;
}

Czyli każdy kolejny element umieszczany jest na górze listy. I teraz 2 problemy:

  1. Dodałem 3 liczby. Kiedy je wypisuje rekurencyjnie na końcu zawsze pojawia się też 0. Z czego to wynika?
  2. Zrobiłem funkcję, która ma za zadanie usuwać z listy pozycję z daną liczbą. Czyli przykładowo remove(6) ma usunąć pozycję z 6 i przesunąć wszystkie kolejne o jeden od tyłu (żeby nie było przerw). Wygląda to tak:
int remove(int x) {

    int i = 0;

    while(ptr) {

        if(ptr->data == x) {
            i = 1;
        }

        if (i == 1) {
            ptr->data = ptr->next->data;
        }

        ptr = ptr->next;

    }

    if (i == 1)
        return 1;

    return 0;

}

Problem w tym, że program się kompiluje, ale potem nagle wywala. Błąd jest w tej linii:

ptr->data = ptr->next->data;

Co robię źle?

0
  1. Wypisuje ci 0 bo stworzyłeś sobie pierwszy element listy (Bóg wie po co...) i ten element jest globalny więc automatycznie zerowany.
  2. Kod to sieczka i nie chce mi sie w niego zagłębiać ale to:
    ptr->data = ptr->next->data;

    Woła o pomstę do nieba. W pętli sprawdziłeś TYLKO czy ptr nie jest nullem. Czemu zakładasz ze ptr->next też nim nie jest?
    Poza tym MYŚL! Usuwanie powinno:

  3. Znaleźć element do usunięcia oraz jego poprzednika (!)
  4. Przepiąć wskaźniki (! a nie przepisywać dane!) tak zeby poprzednik->next = doUsuniecia->next czyli żeby wypiąć element do usunięcia z listy (od razu podpowiem że istnieje tu przypadek szczególny kiedy usuwasz pierwszy element...)
  5. zwolnić pamięć zaalokowaną na usuwany element (!)
    Wiec podsumowując: trudno znaleźć w tym kodzie coś co byś robił dobrze...
0

Dzięki za konstruktywną krytykę. W oparciu o Twoje wskazówki udało mi się napisać coś takiego:

int remove(int x) {

    if (ptr->data == x) {
        struct element *tmp = ptr->next;
        free(ptr);
        ptr = tmp;
        return 1;
    }

    while (ptr) {
        if (ptr->next->data == x) {
            struct element *tmp = ptr->next->next;
            free(ptr->next);
            ptr->next = tmp;            
            return 1;
        }
        ptr = ptr->next;
    }

    return 0;

}

Wygląda na to, że działa idealnie. To rozwiązanie z przepięciem wskaźników jest o wiele prostsze, niepotrzebnie kombinowałem. Mam nadzieję, że pamięć też zwalniam prawidłowo. Zastosowałem zmienną tymczasową, bo bez niej nie mogłem sobie poradzić ze zwolnieniem pamięci (da się? bo jeśli zwolnię pamięć, to już potem nie mogę wykorzystać tego wskaźnika).

Mam jeszcze pytanie odnośnie pierwszego zagadnienia i tego 0, które się pojawia. Jak rozumiem jest to spowodowane przez tę linijkę:

struct element *ptr = &list;

Jak rozumiem powinienem gdzieś umieścić tam NULL-a, ale gdzie?

Dzięki za pomoc! :)

0
struct element *ptr = NULL;

A twój remove nie do końca jest dobry. Wyłoży się na argumencie ktory jest NULLem bo robisz:

 if (ptr->data == x)

nie wiedząc czy ptr nie jest NULLem

0

Czyli właściwie przypisywanie wskaźnikowi ptr adresu zmiennej list jest niepotrzebne? Samo deklarowanie zmiennej list typu struct element w tym przypadku jest zbędne? Odnośnie tego NULLa, to rzeczywiście masz rację - już poprawiam :)

Mam jeszcze jedną funkcję, która ma umieszczać drugą liczbę po pozycji z tą pierwszą. Wygląda u mnie tak:

int insert_2(int after, int what) {

    while(ptr) {

        if (ptr->data == after) {
            struct element *ntr;
            ntr = (struct element*)malloc(sizeof(struct element));
            ntr->data = what;
            ntr->next = ptr->next;
            ptr->next = ntr;
            return 1;
        }

        ptr = ptr->next;

    }

    return 0;

}

Działa dobrze poza przypadkiem, gdy chcę coś umieścić po ostatniej pozycji na liczbie - w takim przypadku znikają poprzednie. Z czego to wynika?

0

Musisz gdzieś źle przepinać wskaźniki. Na oko wygląda ok. Przeleć pod debuggerem i zobacz co sie dzieje :)

0

Może to głupie pytanie, ale... jak się przelatuje pod debuggerem i na czym to polega? Mam Visual Studio 2010 jakby co. Dzięki za pomoc w całym temacie tak w ogóle.

0

Polega to na tym że klikasz sobie na jakąś linię w kodzie i dajesz "breakpoint" a następnie uruchamiasz program w trybie debug i program zatrzyma sie w miejscu gdzie masz breakpointa. Następnie masz możliwość między innymi:

  • przejścia o jedna instrukcje do przodu
  • wznowienia pracy programu aż do następnego breakpointa
    Dodatkowo mozesz wyświetlić sobie stan zmiennych w chwili kiedy program jest zatrzymany.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0