Učešljavanje dve dvostruke liste

Klasi DvostrukaLista dodati funkciju članicu

void ucesljaj(DvostrukaLista& druga);

koja čvorove liste druga umeće naizmenično između čvorova ove liste: prvi čvor ove liste, prvi čvor druge, drugi čvor ove, drugi čvor druge, i tako redom. Kada jedna lista ostane bez čvorova, preostali čvorovi druge idu na kraj. Posle poziva lista druga je prazna.

Funkcija ne sme da pravi ni da briše čvorove, niti da prepisuje podatke: menjaju se samo pokazivači. Ako ova lista ima $n$, a druga $m$ elemenata, složenost mora da bude $O(\min(n, m))$.

Funkcija proveri_invarijantu iz zadatka 1 već je data u postavci.

Pitanja za razmišljanje: Kako se postiže složenost $O(\min(n, m))$ kada je druga lista mnogo duža? Zašto je obavezno ažurirati i druga.velicina_, iako se ona ne koristi pri obilasku?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva prve liste. Zatim se na isti način učitava broj m $(0 \le m \le 10^5)$ i m celih brojeva druge liste.

Izlaz

U prvom redu ispisati elemente prve liste posle učešljavanja unapred, u drugom unazad, a u trećem njenu veličinu. U četvrtom redu program ispisuje da ako je invarijanta obe liste očuvana i druga lista prazna, a ne inače.

Primer

Ulaz

4
1 3 5 7
6
2 4 6 8 10 12

Izlaz

1 2 3 4 5 6 7 8 10 12
12 10 8 7 6 5 4 3 2 1
10
da

Primer

Ulaz

0
4
5 6 7 8

Izlaz

5 6 7 8
8 7 6 5
4
da

Postavka

dvostruka_lista.h

#ifndef DVOSTRUKA_LISTA_H
#define DVOSTRUKA_LISTA_H

#include <cassert>
#include <cstddef>

// Dvostruko povezana lista sa sentinel-cvorom iz glave 4.
//
// Sentinel-cvor stoji izmedju poslednjeg i prvog elementa, pa cvorovi
// cine krug. U praznoj listi sentinel pokazuje sam na sebe. Zahvaljujuci
// tome nijedan pokazivac nije nullptr i umetanje i brisanje nemaju
// posebnih slucajeva.
//
// Pored operacija iz knjige, klasa ima i nekoliko koje se iz njih lako
// izvode, kao i iterator (vidi odeljak o iteratorima u glavi i README).
//
// Tip T mora da podrzava kopiranje i podrazumevano konstruisanje (zbog
// polja podatak u sentinel-cvoru). Funkcija pronadji zahteva operator ==.
//
// Invarijanta:
//   Za svaki cvor c, ukljucujuci i sentinel, vazi
//   c->sledeci->prethodni == c i c->prethodni->sledeci == c.
//   Izmedju dva prolaska kroz sentinel nalazi se tacno velicina_ cvorova.

template <typename T>
class DvostrukaLista {
public:
    struct Cvor {
        T podatak;
        Cvor* prethodni;
        Cvor* sledeci;

        Cvor() : podatak(), prethodni(this), sledeci(this) {}
        Cvor(const T& p, Cvor* pre, Cvor* sl)
            : podatak(p), prethodni(pre), sledeci(sl) {}
    };

    class Iterator;

    DvostrukaLista() : sentinel(new Cvor()), velicina_(0) {}

    ~DvostrukaLista()
    {
        isprazni();
        delete sentinel;
    }

    DvostrukaLista(const DvostrukaLista&) = delete;
    DvostrukaLista& operator=(const DvostrukaLista&) = delete;

    bool prazna() const { return sentinel->sledeci == sentinel; }
    std::size_t velicina() const { return velicina_; }

    Cvor* prvi() const { return sentinel->sledeci; }
    Cvor* poslednji() const { return sentinel->prethodni; }
    Cvor* kraj() const { return sentinel; }

    void umetni_ispred(Cvor* c, const T& x);
    void obrisi(Cvor* c);

    void dodaj_na_pocetak(const T& x) { umetni_ispred(prvi(), x); }
    void dodaj_na_kraj(const T& x) { umetni_ispred(kraj(), x); }
    void umetni_iza(Cvor* c, const T& x) { umetni_ispred(c->sledeci, x); }

    void obrisi_sa_pocetka() { obrisi(prvi()); }
    void obrisi_sa_kraja() { obrisi(poslednji()); }
    void isprazni();

    void ucesljaj(DvostrukaLista& druga);

    Cvor* pronadji(const T& x) const;

    bool proveri_invarijantu() const;

    Iterator begin() const { return Iterator(prvi()); }
    Iterator end() const { return Iterator(kraj()); }

private:
    Cvor* sentinel;
    std::size_t velicina_;
};


// -----------------------------------------------------------------------------
// Iterator
//
// Iterator cuva pokazivac na cvor, ali ga ne otkriva korisniku: dozvoljava
// samo pristup podatku i prelazak na susedni cvor. Zahvaljujuci funkcijama
// begin() i end(), lista moze da se obilazi i petljom
//     for (int x : lista) ...
// Kao i kod std::list, end() je pozicija sentinel-cvora.
// -----------------------------------------------------------------------------

template <typename T>
class DvostrukaLista<T>::Iterator {
public:
    explicit Iterator(Cvor* c) : trenutni(c) {}

    T& operator*() const { return trenutni->podatak; }

    Iterator& operator++()
    {
        trenutni = trenutni->sledeci;
        return *this;
    }

    Iterator& operator--()
    {
        trenutni = trenutni->prethodni;
        return *this;
    }

    bool operator==(const Iterator& drugi) const { return trenutni == drugi.trenutni; }
    bool operator!=(const Iterator& drugi) const { return trenutni != drugi.trenutni; }

private:
    Cvor* trenutni;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------

template <typename T>
void DvostrukaLista<T>::umetni_ispred(Cvor* c, const T& x)
{
    Cvor* novi = new Cvor(x, c->prethodni, c);
    c->prethodni->sledeci = novi;   // jos se koristi stara vrednost c->prethodni
    c->prethodni = novi;
    ++velicina_;
}

template <typename T>
void DvostrukaLista<T>::obrisi(Cvor* c)
{
    assert(c != sentinel);
    c->prethodni->sledeci = c->sledeci;
    c->sledeci->prethodni = c->prethodni;
    delete c;
    --velicina_;
}

template <typename T>
void DvostrukaLista<T>::isprazni()
{
    while (!prazna())
        obrisi(prvi());
}

// Cvor je tip definisan unutar sablona, pa se van klase njegovo ime pise
// kao typename DvostrukaLista<T>::Cvor. Rec typename kaze prevodiocu da je
// to ime tipa.
template <typename T>
typename DvostrukaLista<T>::Cvor* DvostrukaLista<T>::pronadji(const T& x) const
{
    for (Cvor* p = prvi(); p != kraj(); p = p->sledeci)
        if (p->podatak == x)
            return p;
    return nullptr;
}


// TODO: Cvorove liste druga umece naizmenicno izmedju cvorova ove liste,
// pocevsi od prvog cvora ove liste, u vremenu O(min(n, m)). Posle poziva
// druga je prazna.
template <typename T>
void DvostrukaLista<T>::ucesljaj(DvostrukaLista& druga)
{
    // Ovde ide vasa implementacija
}

// Obilazi listu od sentinela, proverava obe veze svakog cvora i broji cvorove.
// Obilazak je ogranicen sa velicina_, pa se zavrsava i kada je lanac sledeci
// pokvaren.
template <typename T>
bool DvostrukaLista<T>::proveri_invarijantu() const
{
    Cvor* c = sentinel;
    std::size_t broj = 0;
    do {
        if (c->sledeci->prethodni != c || c->prethodni->sledeci != c)
            return false;
        c = c->sledeci;
        ++broj;
    } while (c != sentinel && broj <= velicina_);

    return c == sentinel && broj == velicina_ + 1;
}

#endif

main.cpp

#include <iostream>

#include "dvostruka_lista.h"

template <typename T>
void ispisi_unapred(const DvostrukaLista<T>& l)
{
    for (auto p = l.prvi(); p != l.kraj(); p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

template <typename T>
void ispisi_unazad(const DvostrukaLista<T>& l)
{
    for (auto p = l.poslednji(); p != l.kraj(); p = p->prethodni)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void ucitaj(DvostrukaLista<int>& l)
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        l.dodaj_na_kraj(x);
    }
}

int main()
{
    DvostrukaLista<int> a, b;
    ucitaj(a);
    ucitaj(b);

    a.ucesljaj(b);

    ispisi_unapred(a);
    ispisi_unazad(a);
    std::cout << a.velicina() << std::endl;

    bool ispravno = a.proveri_invarijantu()
                    && b.prazna() && b.velicina() == 0 && b.proveri_invarijantu();
    std::cout << (ispravno ? "da" : "ne") << std::endl;

    return 0;
}