Nađi grešku: brisanje svih pojavljivanja

Funkcija

void obrisi_sve(Cvor<int>*& pocetak, int x);

treba iz liste da obriše sve čvorove čiji je podatak jednak x. U postavci je data implementacija koja za listu 2 1 2 3 2 i x = 2 daje ispravan rezultat 1 3, ali ipak ima grešku.

Pronaći listu za koju funkcija daje pogrešan rezultat, objasniti zašto, a zatim je ispraviti. Da li sanitajzer prijavljuje ovu grešku?

Pitanje za razmišljanje: Zašto je parametar tipa Cvor<int>*&, a ne Cvor<int>*?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva. Nakon toga učitava se ceo broj x.

Izlaz

Ispisati elemente liste posle poziva obrisi_sve.

Primer

Ulaz

5
2 1 2 3 2
2

Izlaz

1 3

Postavka

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Brise iz liste sve cvorove ciji je podatak jednak x.
    void obrisi_sve(Cvor<int>*& pocetak, int x)
    {
        while (pocetak != nullptr && pocetak->podatak == x) {
            Cvor<int>* stari = pocetak;
            pocetak = pocetak->sledeci;
            delete stari;
        }
        for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci) {
            if (p->sledeci != nullptr && p->sledeci->podatak == x) {
                Cvor<int>* stari = p->sledeci;
                p->sledeci = stari->sledeci;
                delete stari;
            }
        }
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    int x;
    std::cin >> x;

    matf::obrisi_sve(lista, x);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Brise iz liste sve cvorove ciji je podatak jednak x.
    void obrisi_sve(Cvor<int>*& pocetak, int x)
    {
        while (pocetak != nullptr && pocetak->podatak == x) {
            Cvor<int>* stari = pocetak;
            pocetak = pocetak->sledeci;
            delete stari;
        }
        // Posle brisanja p ostaje na mestu: novi sledbenik jos nije ispitan,
        // a moze i on da bude jednak x. Pomeramo se samo ako nismo brisali.
        Cvor<int>* p = pocetak;
        while (p != nullptr && p->sledeci != nullptr) {
            if (p->sledeci->podatak == x) {
                Cvor<int>* stari = p->sledeci;
                p->sledeci = stari->sledeci;
                delete stari;
            } else {
                p = p->sledeci;
            }
        }
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    int x;
    std::cin >> x;

    matf::obrisi_sve(lista, x);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}