Listy jednokierunkowe - remove all

0

Mam problem z funkcją removeAll w implementacji listy jednokierunkowej. Zalożenie jest takie, że tworzę wskaźnik tymczasowy, który wskazuje na początek listy. Potem przechodzę po kolejnych elementach i usuwam ostatni (następny wskaźnik powinien wynosić NULL). W pierwszej iteracji, usuwa mi ostatnią liczbę, ale w miejscu usunięcia pojawiają się jakieś śmieci i funkcja się zapętla w nieskończoność.

struct elem {
    int dane;
    elem * nast;
};

void removeAll(elem*& lista)
{
    while (lista != NULL) {
        elem* tmp = lista;
        while (true) {
          if (tmp->nast == NULL) {
                delete tmp;
                break;
            }
            else {
                tmp = tmp->nast;
            }
        }
    }
}
2

Zakładam, że to jakieś zadanie na studia, a o std::vector, std::list i std::forward_list wiesz.

Nie zerujesz wskaźnika na next w przedostatnim elemencie, wobec czego po usunięciu ostatniego wskazuje on na jakieś śmieci.

2

Usuwanie całej zawartości listy ogranicza się do kilku kroków:

  • dopóki głowa listy jest różna od NULL:
    • zachowaj głowę w pomocniczej zmiennej,
    • jako głowę ustaw element kolejny (drugi),
    • zwolnij węzeł z pomocniczej zmiennej,
  • ustaw NULL jako adres głowy.

Warunki nie są potrzebne.

Edit: nullowanie głowy dzieje się automatycznie w pętli, więc nie potrzeba dodatkowego przypisania poza nią.

0

Tak, zadanie na studia. Męczę się z tym od jakiegoś czasu.

Co znaczy, że nie zeruję wskaźnika na next w przedostatnim elemencie? Wydaje mi się, że jeżeli usunę ostatni wskaźnik w liście i potem będę jeszcze raz iterował po kolejnych wskaźnikach to rozmiar listy będzie mi się z każdą iteracją zmniejszał.

Edit: Dzięki furious programming, w sumie dużo łatwiejszy sposób.

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