Rekurzija nad listom

Napisati rekurzivne funkcije

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

Funkcija oslobodi oslobađa sve čvorove liste. Funkcija umetni_sortirano umeće x u sortiranu listu tako da lista ostane sortirana. Nijedna funkcija ne sme da sadrži petlju.

Program redom umeće učitane brojeve u početno praznu listu i ispisuje je.

Pitanja za razmišljanje: Zašto u umetni_sortirano nema posebnog slučaja za umetanje na početak, kakav postoji u klasi Lista? Šta tačno menja dodela nad parametrom pocetak u rekurzivnom pozivu? Da li u oslobodi čvor sme da se obriše pre rekurzivnog poziva? Zašto ove funkcije ne koristimo za listu od milion elemenata?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 2000)$, a zatim n celih brojeva.

Izlaz

Ispisati elemente sortirane liste.

Primer

Ulaz

5
3 1 2 5 4

Izlaz

1 2 3 4 5

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Oslobadja sve cvorove liste.
    void oslobodi(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
    }

    // Umece x u sortiranu listu tako da ostane sortirana.
    void umetni_sortirano(Cvor<int>*& pocetak, int x)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

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

int main()
{
    int n;
    std::cin >> n;

    Cvor<int>* lista = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        matf::umetni_sortirano(lista, x);
    }

    ispisi(lista);

    matf::oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Oslobadja sve cvorove liste.
    void oslobodi(Cvor<int>* pocetak)
    {
        if (pocetak == nullptr)
            return;

        // Ostatak se oslobadja prvi, dok je cvor jos ispravan.
        oslobodi(pocetak->sledeci);
        delete pocetak;
    }

    // Umece x u sortiranu listu tako da ostane sortirana.
    void umetni_sortirano(Cvor<int>*& pocetak, int x)
    {
        // pocetak je referenca na pokazivac koji pokazuje na tekuci ostatak:
        // u prvom pozivu to je glava liste, a kasnije polje sledeci prethodnika.
        if (pocetak == nullptr || x <= pocetak->podatak)
            pocetak = new Cvor<int>(x, pocetak);
        else
            umetni_sortirano(pocetak->sledeci, x);
    }

} // namespace matf

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

int main()
{
    int n;
    std::cin >> n;

    Cvor<int>* lista = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        matf::umetni_sortirano(lista, x);
    }

    ispisi(lista);

    matf::oslobodi(lista);
    return 0;
}