Ponavljanja u sortiranoj listi

Data je lista sortirana neopadajuće. Napisati funkcije

void ostavi_po_jedan(Cvor<int>* pocetak);
void ostavi_jedinstvene(Cvor<int>*& pocetak);

Funkcija ostavi_po_jedan ostavlja tačno jedan čvor od svake vrednosti. Funkcija ostavi_jedinstvene ostavlja samo vrednosti koje se u polaznoj listi pojavljuju tačno jednom. Suvišni čvorovi se oslobađaju; jedan prolaz, dodatna memorija $O(1)$.

Pitanja za razmišljanje: Zašto druga funkcija prima pokazivač po referenci, a prva ne? Zašto je druga funkcija teža nego što izgleda?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva u neopadajućem poretku.

Izlaz

U prvom redu ispisati listu posle ostavi_po_jedan, a u drugom listu posle ostavi_jedinstvene. Obe funkcije se pozivaju nad polaznom listom.

Primer

Ulaz

7
1 2 3 3 4 4 5

Izlaz

1 2 3 4 5
1 2 5

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Ostavlja po jedan cvor od svake vrednosti sortirane liste.
    void ostavi_po_jedan(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
    }

    // Ostavlja samo vrednosti koje se u sortiranoj listi javljaju tacno jednom.
    void ostavi_jedinstvene(Cvor<int>*& pocetak)
    {
        // Ovde ide vasa implementacija
    }

} // 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;
}

Cvor<int>* kopiraj(Cvor<int>* pocetak)
{
    Cvor<int>* kopija = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci) {
        Cvor<int>* novi = new Cvor<int>(p->podatak, nullptr);
        if (poslednji == nullptr)
            kopija = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return kopija;
}

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>* a = ucitaj();
    Cvor<int>* b = kopiraj(a);

    matf::ostavi_po_jedan(a);
    ispisi(a);

    matf::ostavi_jedinstvene(b);
    ispisi(b);

    oslobodi(a);
    oslobodi(b);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Ostavlja po jedan cvor od svake vrednosti sortirane liste.
    void ostavi_po_jedan(Cvor<int>* pocetak)
    {
        Cvor<int>* p = pocetak;
        while (p != nullptr && p->sledeci != nullptr) {
            if (p->sledeci->podatak == p->podatak) {
                Cvor<int>* stari = p->sledeci;
                p->sledeci = stari->sledeci;
                delete stari;
            } else {
                p = p->sledeci;
            }
        }
    }

    // Ostavlja samo vrednosti koje se u sortiranoj listi javljaju tacno jednom.
    void ostavi_jedinstvene(Cvor<int>*& pocetak)
    {
        // I prvi cvor moze da nestane, pa privremeni cvor daje prethodnika
        // i njemu. Pokazivac poslednji je kraj liste koja ostaje.
        Cvor<int> privremeni(0, pocetak);
        Cvor<int>* poslednji = &privremeni;

        Cvor<int>* p = pocetak;
        while (p != nullptr) {
            // Nalazimo prvi cvor iza grupe jednakih podataka.
            Cvor<int>* iza = p->sledeci;
            while (iza != nullptr && iza->podatak == p->podatak)
                iza = iza->sledeci;

            if (p->sledeci == iza) {
                poslednji = p;
            } else {
                while (p != iza) {
                    Cvor<int>* stari = p;
                    p = p->sledeci;
                    delete stari;
                }
                poslednji->sledeci = iza;
            }
            p = iza;
        }

        pocetak = privremeni.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;
}

Cvor<int>* kopiraj(Cvor<int>* pocetak)
{
    Cvor<int>* kopija = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci) {
        Cvor<int>* novi = new Cvor<int>(p->podatak, nullptr);
        if (poslednji == nullptr)
            kopija = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return kopija;
}

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>* a = ucitaj();
    Cvor<int>* b = kopiraj(a);

    matf::ostavi_po_jedan(a);
    ispisi(a);

    matf::ostavi_jedinstvene(b);
    ispisi(b);

    oslobodi(a);
    oslobodi(b);
    return 0;
}