Lista sa pokazivačem na poslednji čvor
Klasa Lista iz zaglavlja lista.h dodaje element na kraj u vremenu pocetak_ čuva i pokazivač kraj_ na poslednji čvor, i dodati funkciju
void dodaj_na_kraj(const T& x);složenosti
U postavci su već dodati polje kraj_ i funkcija kraj(). Pre kucanja proći kroz sve postojeće funkcije klase i za svaku odgovoriti: da li ona može da promeni koji čvor je poslednji?
Pitanja za razmišljanje: Zašto bi funkcija obrisi_sa_kraja ostala kraj_? Šta tačno treba da važi za kraj_ kada je lista prazna?
Ulaz
U prvom redu učitava se broj komandi q q komandi:
| Komanda | Značenje |
|---|---|
K x |
dodaj_na_kraj(x) |
P x |
dodaj_na_pocetak(x) |
O |
obrisi_sa_pocetka(), ako lista nije prazna |
B x |
obrisi(x) |
S x |
umetni_sortirano(x) |
I y x |
umetni_iza(pronadji(y), x); y je sigurno u listi |
E y x |
umetni_ispred(pronadji(y), x); y je sigurno u listi |
R y |
obrisi_iza(pronadji(y)); y je u listi i njegov prvi čvor nije poslednji |
U m a1 ... am |
pravi novu listu sa m elemenata i poziva ucesljaj nad njom |
C |
isprazni() |
Program main.cpp posle svake komande proverava da li kraj() zaista pokazuje na poslednji čvor (u praznoj listi to je nullptr) i na prvu grešku ispisuje redni broj komande. Provera se radi samo za m je najviše umetni_sortirano i ucesljaj se izvršavaju kako su napisane u klasi.
Izlaz
U prvom redu ispisati elemente liste, u drugom njenu veličinu, a u trećem podatak poslednjeg čvora, odnosno - ako je lista prazna.
Primer
Ulaz
6
K 1
K 2
P 0
R 1
K 3
I 3 4
Izlaz
0 1 3 4
4
4
Postavka
lista.h
#ifndef LISTA_H
#define LISTA_H
#include <cassert>
#include <cstddef>
// Jednostruko povezana lista iz glave 4.
//
// Lista je vlasnik svojih cvorova: alocira ih sa new, a oslobadja ih
// destruktor. Kopiranje je zabranjeno; duboko kopiranje prikazano je samo
// u glavi 3, na primeru dinamickog niza.
//
// Tip T mora da podrzava kopiranje. Funkcije pronadji i obrisi(x) dodatno
// zahtevaju operatore == i !=, a umetni_sortirano i ucesljaj operatore
// < i <=.
//
// Invarijanta:
// Ako se krene od pocetak_ i prate pokazivaci sledeci, posle tacno
// velicina_ cvorova stize se do nullptr. Svaki cvor na tom putu alocirala
// je lista i nijedan se ne pojavljuje dva puta.
template <typename T>
struct Cvor {
T podatak;
Cvor* sledeci;
Cvor(const T& p, Cvor* s) : podatak(p), sledeci(s) {}
};
template <typename T>
class Lista {
public:
Lista() : pocetak_(nullptr), kraj_(nullptr), velicina_(0) {}
~Lista();
Lista(const Lista&) = delete;
Lista& operator=(const Lista&) = delete;
bool prazna() const { return pocetak_ == nullptr; }
std::size_t velicina() const { return velicina_; }
Cvor<T>* pocetak() const { return pocetak_; }
Cvor<T>* kraj() const { return kraj_; }
void dodaj_na_pocetak(const T& x);
void dodaj_na_kraj(const T& x);
void umetni_iza(Cvor<T>* c, const T& x);
void umetni_ispred(Cvor<T>* c, const T& x);
void umetni_sortirano(const T& x);
void obrisi_sa_pocetka();
void obrisi_iza(Cvor<T>* c);
bool obrisi(const T& x);
void isprazni();
Cvor<T>* pronadji(const T& x) const;
void ucesljaj(Lista& druga);
private:
// TODO: Pokazivac na poslednji cvor; dopuniti invarijantu i sve funkcije
// koje treba da ga odrzavaju.
Cvor<T>* pocetak_;
Cvor<T>* kraj_;
std::size_t velicina_;
};
// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------
template <typename T>
Lista<T>::~Lista()
{
isprazni();
}
template <typename T>
void Lista<T>::dodaj_na_pocetak(const T& x)
{
Cvor<T>* novi = new Cvor<T>(x, pocetak_);
pocetak_ = novi;
++velicina_;
}
// TODO: Dodaje novi element na kraj liste, u vremenu O(1).
template <typename T>
void Lista<T>::dodaj_na_kraj(const T& x)
{
// Ovde ide vasa implementacija
}
// c mora da pokazuje na cvor ove liste.
template <typename T>
void Lista<T>::umetni_iza(Cvor<T>* c, const T& x)
{
assert(c != nullptr);
Cvor<T>* novi = new Cvor<T>(x, c->sledeci);
c->sledeci = novi;
++velicina_;
}
// Novi cvor se umece iza c, a podaci se rasporede tako da redosled bude
// kao da je umetnut ispred c. Posle poziva c pokazuje na novi element.
template <typename T>
void Lista<T>::umetni_ispred(Cvor<T>* c, const T& x)
{
assert(c != nullptr);
umetni_iza(c, c->podatak);
c->podatak = x;
}
// Ako je lista bila sortirana, ostaje sortirana.
template <typename T>
void Lista<T>::umetni_sortirano(const T& x)
{
if (prazna() || x <= pocetak_->podatak) {
dodaj_na_pocetak(x);
return;
}
Cvor<T>* prethodni = pocetak_;
while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak < x)
prethodni = prethodni->sledeci;
umetni_iza(prethodni, x);
}
template <typename T>
void Lista<T>::obrisi_sa_pocetka()
{
assert(!prazna());
Cvor<T>* stari = pocetak_;
pocetak_ = stari->sledeci; // pre delete, dok je stari jos ispravan
delete stari;
--velicina_;
}
template <typename T>
void Lista<T>::obrisi_iza(Cvor<T>* c)
{
assert(c != nullptr);
Cvor<T>* stari = c->sledeci;
assert(stari != nullptr);
c->sledeci = stari->sledeci;
delete stari;
--velicina_;
}
// Brise prvo pojavljivanje x. Vraca false ako x nije u listi.
template <typename T>
bool Lista<T>::obrisi(const T& x)
{
if (prazna())
return false;
if (pocetak_->podatak == x) {
obrisi_sa_pocetka();
return true;
}
Cvor<T>* prethodni = pocetak_;
while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak != x)
prethodni = prethodni->sledeci;
if (prethodni->sledeci == nullptr)
return false;
obrisi_iza(prethodni);
return true;
}
template <typename T>
void Lista<T>::isprazni()
{
while (!prazna())
obrisi_sa_pocetka();
}
template <typename T>
Cvor<T>* Lista<T>::pronadji(const T& x) const
{
for (Cvor<T>* p = pocetak_; p != nullptr; p = p->sledeci)
if (p->podatak == x)
return p;
return nullptr;
}
// Ucesljava dve sortirane liste. Posle poziva ova lista sadrzi sve
// elemente, a druga je prazna. Cvorovi se ne kopiraju, samo se drugacije
// povezuju.
template <typename T>
void Lista<T>::ucesljaj(Lista& druga)
{
Cvor<T>* a = pocetak_;
Cvor<T>* b = druga.pocetak_;
Cvor<T>* poslednji = nullptr; // poslednji cvor rezultata
while (a != nullptr && b != nullptr) {
Cvor<T>* manji;
if (a->podatak <= b->podatak) {
manji = a;
a = a->sledeci;
} else {
manji = b;
b = b->sledeci;
}
// Prvi cvor rezultata nema prethodnika, pa se menja pocetak_.
if (poslednji == nullptr)
pocetak_ = manji;
else
poslednji->sledeci = manji;
poslednji = manji;
}
Cvor<T>* ostatak = (a != nullptr) ? a : b;
if (poslednji == nullptr)
pocetak_ = ostatak;
else
poslednji->sledeci = ostatak;
// Svaki cvor sme da pripada samo jednoj listi, inace bi ga oba
// destruktora oslobodila.
velicina_ += druga.velicina_;
druga.pocetak_ = nullptr;
druga.velicina_ = 0;
}
#endif
main.cpp
#include <iostream>
#include "lista.h"
// Proverava da li kraj() pokazuje na poslednji cvor liste.
template <typename T>
bool kraj_ispravan(const Lista<T>& l)
{
Cvor<T>* poslednji = nullptr;
for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
poslednji = p;
return l.kraj() == poslednji;
}
template <typename T>
void ispisi(const Lista<T>& l)
{
for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
std::cout << p->podatak << " ";
std::cout << std::endl;
std::cout << l.velicina() << std::endl;
if (l.prazna())
std::cout << "-" << std::endl;
else
std::cout << l.kraj()->podatak << std::endl;
}
int main()
{
int q;
std::cin >> q;
Lista<int> l;
// Provera je O(n), pa bi na velikom ulazu sama pokvarila slozenost.
bool proveravaj = q <= 1000;
for (int i = 1; i <= q; ++i) {
char komanda;
std::cin >> komanda;
int x, y, m;
bool ispravno = true;
if (komanda == 'K') {
std::cin >> x;
l.dodaj_na_kraj(x);
} else if (komanda == 'P') {
std::cin >> x;
l.dodaj_na_pocetak(x);
} else if (komanda == 'O') {
if (!l.prazna())
l.obrisi_sa_pocetka();
} else if (komanda == 'B') {
std::cin >> x;
l.obrisi(x);
} else if (komanda == 'S') {
std::cin >> x;
l.umetni_sortirano(x);
} else if (komanda == 'I') {
std::cin >> y >> x;
l.umetni_iza(l.pronadji(y), x);
} else if (komanda == 'E') {
std::cin >> y >> x;
l.umetni_ispred(l.pronadji(y), x);
} else if (komanda == 'R') {
std::cin >> y;
l.obrisi_iza(l.pronadji(y));
} else if (komanda == 'U') {
std::cin >> m;
Lista<int> druga;
for (int j = 0; j < m; ++j) {
std::cin >> x;
druga.dodaj_na_kraj(x);
}
l.ucesljaj(druga);
ispravno = kraj_ispravan(druga);
} else if (komanda == 'C') {
l.isprazni();
}
if (proveravaj && !(ispravno && kraj_ispravan(l))) {
std::cout << "kraj_ nije ispravan posle komande " << i << std::endl;
return 0;
}
}
ispisi(l);
return 0;
}
Rešenje
lista.h
#ifndef LISTA_H
#define LISTA_H
#include <cassert>
#include <cstddef>
// Jednostruko povezana lista iz glave 4.
//
// Lista je vlasnik svojih cvorova: alocira ih sa new, a oslobadja ih
// destruktor. Kopiranje je zabranjeno; duboko kopiranje prikazano je samo
// u glavi 3, na primeru dinamickog niza.
//
// Tip T mora da podrzava kopiranje. Funkcije pronadji i obrisi(x) dodatno
// zahtevaju operatore == i !=, a umetni_sortirano i ucesljaj operatore
// < i <=.
//
// Invarijanta:
// Ako se krene od pocetak_ i prate pokazivaci sledeci, posle tacno
// velicina_ cvorova stize se do nullptr. Svaki cvor na tom putu alocirala
// je lista i nijedan se ne pojavljuje dva puta. Ako je lista prazna,
// kraj_ je nullptr; inace kraj_ pokazuje na poslednji cvor tog lanca, pa
// vazi kraj_->sledeci == nullptr.
template <typename T>
struct Cvor {
T podatak;
Cvor* sledeci;
Cvor(const T& p, Cvor* s) : podatak(p), sledeci(s) {}
};
template <typename T>
class Lista {
public:
Lista() : pocetak_(nullptr), kraj_(nullptr), velicina_(0) {}
~Lista();
Lista(const Lista&) = delete;
Lista& operator=(const Lista&) = delete;
bool prazna() const { return pocetak_ == nullptr; }
std::size_t velicina() const { return velicina_; }
Cvor<T>* pocetak() const { return pocetak_; }
Cvor<T>* kraj() const { return kraj_; }
void dodaj_na_pocetak(const T& x);
void dodaj_na_kraj(const T& x);
void umetni_iza(Cvor<T>* c, const T& x);
void umetni_ispred(Cvor<T>* c, const T& x);
void umetni_sortirano(const T& x);
void obrisi_sa_pocetka();
void obrisi_iza(Cvor<T>* c);
bool obrisi(const T& x);
void isprazni();
Cvor<T>* pronadji(const T& x) const;
void ucesljaj(Lista& druga);
private:
Cvor<T>* pocetak_;
Cvor<T>* kraj_;
std::size_t velicina_;
};
// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------
template <typename T>
Lista<T>::~Lista()
{
isprazni();
}
template <typename T>
void Lista<T>::dodaj_na_pocetak(const T& x)
{
Cvor<T>* novi = new Cvor<T>(x, pocetak_);
pocetak_ = novi;
if (kraj_ == nullptr)
kraj_ = novi;
++velicina_;
}
// Dodaje novi element na kraj liste, u vremenu O(1).
template <typename T>
void Lista<T>::dodaj_na_kraj(const T& x)
{
Cvor<T>* novi = new Cvor<T>(x, nullptr);
if (prazna())
pocetak_ = novi;
else
kraj_->sledeci = novi;
kraj_ = novi;
++velicina_;
}
// c mora da pokazuje na cvor ove liste.
template <typename T>
void Lista<T>::umetni_iza(Cvor<T>* c, const T& x)
{
assert(c != nullptr);
Cvor<T>* novi = new Cvor<T>(x, c->sledeci);
c->sledeci = novi;
if (c == kraj_)
kraj_ = novi;
++velicina_;
}
// Novi cvor se umece iza c, a podaci se rasporede tako da redosled bude
// kao da je umetnut ispred c. Posle poziva c pokazuje na novi element.
template <typename T>
void Lista<T>::umetni_ispred(Cvor<T>* c, const T& x)
{
assert(c != nullptr);
umetni_iza(c, c->podatak);
c->podatak = x;
}
// Ako je lista bila sortirana, ostaje sortirana.
template <typename T>
void Lista<T>::umetni_sortirano(const T& x)
{
if (prazna() || x <= pocetak_->podatak) {
dodaj_na_pocetak(x);
return;
}
Cvor<T>* prethodni = pocetak_;
while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak < x)
prethodni = prethodni->sledeci;
umetni_iza(prethodni, x);
}
template <typename T>
void Lista<T>::obrisi_sa_pocetka()
{
assert(!prazna());
Cvor<T>* stari = pocetak_;
pocetak_ = stari->sledeci; // pre delete, dok je stari jos ispravan
if (pocetak_ == nullptr)
kraj_ = nullptr;
delete stari;
--velicina_;
}
template <typename T>
void Lista<T>::obrisi_iza(Cvor<T>* c)
{
assert(c != nullptr);
Cvor<T>* stari = c->sledeci;
assert(stari != nullptr);
c->sledeci = stari->sledeci;
if (stari == kraj_)
kraj_ = c;
delete stari;
--velicina_;
}
// Brise prvo pojavljivanje x. Vraca false ako x nije u listi.
template <typename T>
bool Lista<T>::obrisi(const T& x)
{
if (prazna())
return false;
if (pocetak_->podatak == x) {
obrisi_sa_pocetka();
return true;
}
Cvor<T>* prethodni = pocetak_;
while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak != x)
prethodni = prethodni->sledeci;
if (prethodni->sledeci == nullptr)
return false;
obrisi_iza(prethodni);
return true;
}
template <typename T>
void Lista<T>::isprazni()
{
while (!prazna())
obrisi_sa_pocetka();
}
template <typename T>
Cvor<T>* Lista<T>::pronadji(const T& x) const
{
for (Cvor<T>* p = pocetak_; p != nullptr; p = p->sledeci)
if (p->podatak == x)
return p;
return nullptr;
}
// Ucesljava dve sortirane liste. Posle poziva ova lista sadrzi sve
// elemente, a druga je prazna. Cvorovi se ne kopiraju, samo se drugacije
// povezuju.
template <typename T>
void Lista<T>::ucesljaj(Lista& druga)
{
Cvor<T>* a = pocetak_;
Cvor<T>* b = druga.pocetak_;
Cvor<T>* poslednji = nullptr; // poslednji cvor rezultata
while (a != nullptr && b != nullptr) {
Cvor<T>* manji;
if (a->podatak <= b->podatak) {
manji = a;
a = a->sledeci;
} else {
manji = b;
b = b->sledeci;
}
// Prvi cvor rezultata nema prethodnika, pa se menja pocetak_.
if (poslednji == nullptr)
pocetak_ = manji;
else
poslednji->sledeci = manji;
poslednji = manji;
}
Cvor<T>* ostatak = (a != nullptr) ? a : b;
if (poslednji == nullptr)
pocetak_ = ostatak;
else
poslednji->sledeci = ostatak;
// Ako je ostatak iz druge liste, njen poslednji cvor je i poslednji
// cvor rezultata. Inace je poslednji cvor ove liste i dalje poslednji.
if (b != nullptr)
kraj_ = druga.kraj_;
// Svaki cvor sme da pripada samo jednoj listi, inace bi ga oba
// destruktora oslobodila.
velicina_ += druga.velicina_;
druga.pocetak_ = nullptr;
druga.kraj_ = nullptr;
druga.velicina_ = 0;
}
#endif
main.cpp
#include <iostream>
#include "lista.h"
// Proverava da li kraj() pokazuje na poslednji cvor liste.
template <typename T>
bool kraj_ispravan(const Lista<T>& l)
{
Cvor<T>* poslednji = nullptr;
for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
poslednji = p;
return l.kraj() == poslednji;
}
template <typename T>
void ispisi(const Lista<T>& l)
{
for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
std::cout << p->podatak << " ";
std::cout << std::endl;
std::cout << l.velicina() << std::endl;
if (l.prazna())
std::cout << "-" << std::endl;
else
std::cout << l.kraj()->podatak << std::endl;
}
int main()
{
int q;
std::cin >> q;
Lista<int> l;
// Provera je O(n), pa bi na velikom ulazu sama pokvarila slozenost.
bool proveravaj = q <= 1000;
for (int i = 1; i <= q; ++i) {
char komanda;
std::cin >> komanda;
int x, y, m;
bool ispravno = true;
if (komanda == 'K') {
std::cin >> x;
l.dodaj_na_kraj(x);
} else if (komanda == 'P') {
std::cin >> x;
l.dodaj_na_pocetak(x);
} else if (komanda == 'O') {
if (!l.prazna())
l.obrisi_sa_pocetka();
} else if (komanda == 'B') {
std::cin >> x;
l.obrisi(x);
} else if (komanda == 'S') {
std::cin >> x;
l.umetni_sortirano(x);
} else if (komanda == 'I') {
std::cin >> y >> x;
l.umetni_iza(l.pronadji(y), x);
} else if (komanda == 'E') {
std::cin >> y >> x;
l.umetni_ispred(l.pronadji(y), x);
} else if (komanda == 'R') {
std::cin >> y;
l.obrisi_iza(l.pronadji(y));
} else if (komanda == 'U') {
std::cin >> m;
Lista<int> druga;
for (int j = 0; j < m; ++j) {
std::cin >> x;
druga.dodaj_na_kraj(x);
}
l.ucesljaj(druga);
ispravno = kraj_ispravan(druga);
} else if (komanda == 'C') {
l.isprazni();
}
if (proveravaj && !(ispravno && kraj_ispravan(l))) {
std::cout << "kraj_ nije ispravan posle komande " << i << std::endl;
return 0;
}
}
ispisi(l);
return 0;
}