Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <ctime>
- /* S obzirom da sam kako u pripremi, tako i na tutorijalu iamla jako veliki broj grešaka i autotestova
- koji nisu uspjeli, morala sam izmjeniti mnogo dijelova koda, ali mislim da se janso vidi da je sve nadograđivano
- na početni tj. da nisu vršene nikakve radikalne izmjene u klasama Niz i Lista koje sam i jedine djelomično implementirala
- do kraja Tutoriajla 2 */
- using namespace std;
- template <typename NekiTip>
- class Iterator;
- template <typename NekiTip>
- class Niz
- {
- int zauzeto, t, max;
- NekiTip* n;
- public:
- Niz() : zauzeto(0), t(-1)
- {
- max=1000;
- n=new NekiTip[max];
- }
- virtual ~Niz()
- {
- delete[] n;
- }
- Niz (const Niz &niz1)
- {
- zauzeto=niz1.zauzeto;
- t=niz1.t;
- max=niz1.max;
- n=new NekiTip[max];
- for(int i(0); i<zauzeto; i++) n[i]=niz1.n[i];
- }
- Niz &operator =(const Niz &niz1)
- {
- if(&niz1==this) return *this;
- delete[] n;
- zauzeto=niz1.zauzeto;
- t=niz1.t;
- max=niz1.max;
- n=new NekiTip[max];
- for(int i(0); i<zauzeto; i++) n[i]=niz1.n[i];
- return *this;
- }
- virtual int brojElemenata() const
- {
- return zauzeto;
- }
- virtual NekiTip trenutni() const
- {
- return n[t];
- }
- virtual bool prethodni()
- {
- if(zauzeto==0) throw "Prazan niz!";
- if (t==0) return false;
- t--;
- return true;
- }
- virtual bool sljedeci()
- {
- if (zauzeto==0) throw "Prazan niz!";
- if (t==zauzeto-1) return false;
- t++;
- return true;
- }
- virtual void pocetak()
- {
- if (zauzeto==0) throw "Prazan niz!";
- t=0;
- }
- virtual void kraj()
- {
- if (zauzeto==0) throw "Prazan niz!";
- t=zauzeto-1;
- }
- virtual void dodajIspred(const NekiTip &x)
- {
- if (zauzeto==max)
- {
- Niz privremeni(*this);
- delete[] n;
- max*=2;
- n=new NekiTip[max];
- for(int i(0); i<zauzeto; i++) n[i]=privremeni.n[i];
- }
- if (zauzeto==0) t=0;
- zauzeto++;
- for(int i(zauzeto-1); i>=t+1; i--) n[i]=n[i-1];
- n[t]=x;
- if (zauzeto!=1) t++;
- }
- virtual void dodajIza(const NekiTip &x)
- {
- if (zauzeto==max)
- {
- Niz privremeni(*this);
- delete[] n;
- max*=2;
- n=new NekiTip[max];
- for(int i(0); i<zauzeto; i++) n[i]=privremeni.n[i];
- }
- if(zauzeto==0) t=0;
- zauzeto++;
- for(int i(zauzeto-1); i>t+1; i--) n[i]=n[i-1];
- if (zauzeto==1) n[t]=x;
- else n[t+1]=x;
- }
- virtual void obrisi()
- {
- if(zauzeto==0) throw "Niz je prazan!";
- if(t==zauzeto-1)
- {
- zauzeto--;
- t--;
- }
- else
- {
- for(int i(t); i<zauzeto-1; i++) n[i]=n[i+1];
- zauzeto--;
- }
- }
- virtual NekiTip operator [](int x) const
- {
- if(x<0 || x>zauzeto) throw "Ulazite izvan opsega niza!";
- return n[x];
- }
- virtual NekiTip &operator [](int x)
- {
- if(x<0 || x>zauzeto) throw "Ulazite izvan opsega niza!";
- return n[x];
- }
- friend class Iterator<NekiTip>;
- };
- template <typename NekiTip>
- class Lista : public Niz<NekiTip>
- {
- struct Cvor
- {
- NekiTip element;
- Cvor* veza;
- };
- Cvor *pocetni, *krajnji, *trenutno;
- int br_clanova;
- public:
- Lista()
- {
- br_clanova=0;
- }
- int brojElemenata() const
- {
- return br_clanova;
- }
- NekiTip trenutni() const
- {
- return (trenutno->element);
- }
- ~Lista()
- {
- while(br_clanova!=0) obrisi();
- }
- Lista (const Lista &lista1)
- {
- br_clanova=lista1.br_clanova;
- pocetni=0;
- krajnji=0;
- trenutno=0;
- for(Cvor* p(lista1.pocetni); p!=0; p=p->veza)
- {
- Cvor *novi(new Cvor);
- novi->element=p->element;
- novi->veza=0;
- if(pocetni!=0) krajnji->veza=novi;
- else
- {
- pocetni=novi;
- krajnji=novi;
- }
- krajnji=novi;
- if(p==lista1.trenutno) trenutno=novi;
- }
- }
- Lista &operator =(const Lista &lista1)
- {
- while(br_clanova!=0) obrisi();
- pocetni=0;
- krajnji=0;
- trenutno=0;
- for(Cvor* p(lista1.pocetni); p!=0; p=p->veza)
- {
- Cvor *novi(new Cvor);
- novi->element=p->element;
- novi->veza=0;
- if(pocetni!=0) krajnji->veza=novi;
- else
- {
- pocetni=novi;
- krajnji=novi;
- }
- krajnji=novi;
- if(p==lista1.trenutno) trenutno=novi;
- }
- br_clanova=lista1.br_clanova;
- return *this;
- }
- bool prethodni()
- {
- if (br_clanova==0) throw "Lista je prazna!";
- if (trenutno==pocetni) return false;
- Cvor *pomocni(pocetni);
- while (pomocni->veza!=trenutno) pomocni=pomocni->veza;
- trenutno=pomocni;
- return true;
- }
- bool sljedeci()
- {
- if (br_clanova==0) throw "Lista je prazna!";
- if (trenutno->veza==0) return false;
- trenutno=trenutno->veza;
- return true;
- }
- void pocetak()
- {
- if (br_clanova==0) throw "Lista je prazna!";
- trenutno=pocetni;
- }
- void kraj()
- {
- if (br_clanova==0) throw "Lista je prazna!";
- trenutno=krajnji;
- }
- void dodajIspred(const NekiTip &x)
- {
- if (br_clanova==0)
- {
- Cvor *novi(new Cvor);
- novi->element=x;
- novi->veza=0;
- pocetni=novi;
- krajnji=novi;
- trenutno=novi;
- br_clanova++;
- }
- else
- {
- Cvor *novi(new Cvor);
- novi->element=x;
- novi->veza=trenutno;
- if (pocetni==trenutno) pocetni=novi;
- else
- {
- Cvor *pomocni(pocetni);
- while(pomocni->veza!=trenutno) pomocni=pomocni->veza;
- pomocni->veza=novi;
- }
- br_clanova++;
- }
- }
- void dodajIza(const NekiTip &x)
- {
- if (br_clanova==0)
- {
- Cvor *novi(new Cvor);
- novi->element=x;
- novi->veza=0;
- pocetni=novi;
- krajnji=novi;
- trenutno=novi;
- br_clanova++;
- }
- else
- {
- Cvor *novi(new Cvor),*pomocni(trenutno->veza);
- novi->element=x;
- novi->veza=pomocni;
- trenutno->veza=novi;
- if(novi->veza==0)
- {
- krajnji=novi;
- }
- br_clanova++;
- }
- }
- void obrisi()
- {
- if(br_clanova==0) throw "Niz je prazan!";
- if(trenutno==pocetni)
- {
- if(trenutno==krajnji) krajnji=krajnji->veza;
- pocetni=pocetni->veza;
- delete trenutno;
- trenutno=pocetni;
- br_clanova--;
- }
- else
- {
- Cvor* pomocni(pocetni), *pomocni2(trenutno->veza);
- while(pomocni->veza!=trenutno) pomocni=pomocni->veza;
- pomocni->veza=pomocni2;
- if(pomocni2==0) krajnji=pomocni;
- delete trenutno;
- if(pomocni2==0)
- {
- krajnji=pomocni;
- trenutno=pomocni;
- }
- else trenutno=pomocni2;
- br_clanova--;
- }
- }
- NekiTip operator [](int x) const
- {
- if(x<0 || x>br_clanova) throw "Ulazite izvan opsega niza!";
- Cvor* pomocni(pocetni);
- for (int i(0); i<x; i++) pomocni=pomocni->veza;
- return pomocni->element;
- }
- NekiTip &operator [](int x)
- {
- if(x<0 || x>br_clanova) throw "Ulazite izvan opsega niza!";
- Cvor* pomocni(pocetni);
- for (int i(0); i<x; i++) pomocni=pomocni->veza;
- return pomocni->element;
- }
- friend class Iterator<NekiTip>;
- };
- template <typename NekiTip>
- class DvostrukaLista : public Niz<NekiTip>
- {
- struct DCvor
- {
- NekiTip element;
- DCvor *veza_naprijed, *veza_nazad;
- };
- DCvor *pocetni, *krajnji, *trenutno;
- int br_elemenata;
- public:
- DvostrukaLista() : br_elemenata(0) {}
- int brojElemenata() const
- {
- return br_elemenata;
- }
- NekiTip trenutni() const
- {
- if(br_elemenata==0) throw "Dvostruka lista je prazna!";
- return (trenutno->element);
- }
- ~DvostrukaLista()
- {
- while(br_elemenata!=0) obrisi();
- }
- DvostrukaLista(const DvostrukaLista &l)
- {
- br_elemenata=l.br_elemenata;
- pocetni=trenutno=krajnji=0;
- for(DCvor *p(l.pocetni); p!=0; p=p->veza_naprijed)
- {
- DCvor *novi(new DCvor);
- novi->element=p->element;
- novi->veza_naprijed=0;
- novi->veza_nazad=0;
- if(pocetni!=0)
- {
- krajnji->veza_naprijed=novi;
- novi->veza_nazad=krajnji;
- }
- else
- {
- pocetni=novi;
- }
- krajnji=novi;
- if(p==l.trenutno) trenutno=novi;
- }
- }
- DvostrukaLista &operator=(const DvostrukaLista &l)
- {
- if(&l==this) return *this;
- while(br_elemenata!=0) obrisi();
- br_elemenata=l.br_elemenata;
- pocetni=trenutno=krajnji=0;
- for(DCvor *p(l.pocetni); p!=0; p=p->veza_naprijed)
- {
- DCvor *novi(new DCvor);
- novi->element=p->element;
- novi->veza_naprijed=0;
- novi->veza_nazad=0;
- if(pocetni!=0)
- {
- krajnji->veza_naprijed=novi;
- novi->veza_nazad=krajnji;
- }
- else
- {
- pocetni=novi;
- }
- krajnji=novi;
- if(p==l.trenutno) trenutno=novi;
- }
- return *this;
- }
- bool prethodni()
- {
- if(br_elemenata==0) throw "Dvostruka lista je prazna!";
- if(trenutno==pocetni) return false;
- trenutno=trenutno->veza_nazad;
- return true;
- }
- bool sljedeci()
- {
- if(br_elemenata==0) throw "Dvostruka lista je prazna!";
- if(trenutno==krajnji) return false;
- trenutno=trenutno->veza_naprijed;
- return true;
- }
- void pocetak()
- {
- if(br_elemenata==0) throw "Dvostruka lista je prazna!";
- trenutno=pocetni;
- }
- void kraj()
- {
- if(br_elemenata==0) throw "Dvostruka lista je prazna!";
- trenutno=krajnji;
- }
- void dodajIspred(const NekiTip &x)
- {
- if(br_elemenata==0)
- {
- DCvor *novi(new DCvor);
- novi->element=x;
- novi->veza_naprijed=0;
- novi->veza_nazad=0;
- pocetni=novi;
- krajnji=novi;
- trenutno=novi;
- br_elemenata++;
- }
- else
- {
- DCvor *novi(new DCvor);
- novi->element=x;
- novi->veza_naprijed=trenutno;
- novi->veza_nazad=(trenutno->veza_nazad);
- if(pocetni==trenutno) pocetni=novi;
- else trenutno->veza_nazad->veza_naprijed=novi;
- if(krajnji==trenutno) krajnji->veza_nazad=novi;
- trenutno->veza_nazad=novi;
- br_elemenata++;
- }
- }
- void dodajIza(const NekiTip &x)
- {
- if(br_elemenata==0)
- {
- DCvor *novi(new DCvor);
- novi->element=x;
- novi->veza_naprijed=0;
- novi->veza_nazad=0;
- pocetni=novi;
- krajnji=novi;
- trenutno=novi;
- br_elemenata++;
- }
- else
- {
- DCvor *novi(new DCvor);
- novi->element=x;
- novi->veza_nazad=trenutno;
- novi->veza_naprijed=trenutno->veza_naprijed;
- if(krajnji==trenutno) krajnji=novi;
- else trenutno->veza_naprijed->veza_nazad=novi;
- if(pocetni==trenutno) pocetni->veza_naprijed=novi;
- trenutno->veza_naprijed=novi;
- br_elemenata++;
- }
- }
- void obrisi()
- {
- if (br_elemenata==0) throw "Dvostruka lista je prazna!";
- if(br_elemenata==1)
- {
- delete trenutno;
- trenutno=pocetni=krajnji=0;
- br_elemenata--;
- }
- else if(trenutno!=krajnji)
- {
- DCvor *pomocni(trenutno);
- trenutno=trenutno->veza_naprijed;
- trenutno->veza_nazad=pomocni->veza_nazad;
- if(pomocni!=pocetni) pomocni->veza_nazad->veza_naprijed=trenutno;
- else pocetni=trenutno;
- if(pomocni->veza_naprijed==krajnji) krajnji->veza_nazad=pomocni->veza_nazad;
- delete pomocni;
- br_elemenata--;
- }
- else
- {
- DCvor *pomocni(trenutno);
- trenutno=trenutno->veza_nazad;
- trenutno->veza_naprijed=pomocni->veza_naprijed;
- krajnji=trenutno;
- delete pomocni;
- br_elemenata--;
- }
- }
- NekiTip operator [](int x) const
- {
- if(x<0 || x>br_elemenata) throw "Ulazite izvan opsega niza!";
- DCvor* pomocni(pocetni);
- for (int i(0); i<x; i++) pomocni=pomocni->veza_naprijed;
- return pomocni->element;
- }
- NekiTip &operator [](int x)
- {
- if(x<0 || x>br_elemenata) throw "Ulazite izvan opsega niza!";
- DCvor* pomocni(pocetni);
- for (int i(0); i<x; i++) pomocni=pomocni->veza_naprijed;
- return pomocni->element;
- }
- friend class Iterator<NekiTip>;
- };
- template <typename NekiTip>
- class Iterator
- {
- const Niz<NekiTip> *niz;
- const Lista<NekiTip> *lista;
- const DvostrukaLista<NekiTip> *Dlista;
- int trenutniNiz;
- typename Lista<NekiTip>::Cvor *trenutniLista;
- typename DvostrukaLista<NekiTip>::DCvor *trenutniDlista;
- public:
- Iterator(const Niz<NekiTip> &x) : niz(&x), lista(0), Dlista(0), trenutniNiz(0), trenutniLista(0), trenutniDlista(0) {}
- Iterator(const Lista<NekiTip> &x) : niz(0), lista(&x), Dlista(0), trenutniNiz(0), trenutniLista(lista->pocetni), trenutniDlista(0) {}
- Iterator(const DvostrukaLista<NekiTip> &x) : niz(0), lista(0), Dlista(&x), trenutniNiz(0), trenutniLista(0), trenutniDlista(Dlista->pocetni) {}
- NekiTip trenutni()
- {
- if(niz!=0)
- {
- if (niz->brojElemenata()==0) throw "Niz je prazan!";
- else return niz->n[trenutniNiz];
- }
- else if(lista!=0)
- {
- if (lista->brojElemenata()==0) throw "Lista je prazna";
- else return trenutniLista->element;
- }
- else if(Dlista!=0)
- {
- if(Dlista->brojElemenata()==0) throw "Dvostruka lista je prazna!";
- else return trenutniDlista->element;
- }
- }
- bool prethodni()
- {
- if(niz!=0)
- {
- if(niz->brojElemenata()==0) throw "Prazan niz!";
- if(trenutniNiz==0) return false;
- else
- {
- trenutniNiz--;
- return true;
- }
- }
- else if(lista!=0)
- {
- if(lista->brojElemenata()==0) throw "Prazna lista!";
- if(trenutniLista==lista) return false;
- else
- {
- typename Lista<NekiTip>::Cvor *pomocni(lista.pocetni);
- while(pomocni->veza!=trenutniLista) pomocni=pomocni->veza;
- trenutniLista=pomocni;
- return true;
- }
- }
- else if(Dlista!=0)
- {
- if(Dlista->brojElemenata()==0) throw "Dvostruka lista je prazna!";
- if(trenutniDlista==Dlista) return false;
- else
- {
- trenutniDlista=trenutniDlista->veza_nazad;
- return true;
- }
- }
- }
- bool sljedeci()
- {
- if(niz!=0)
- {
- if(niz->brojElemenata()==0) throw "Prazan niz!";
- if(trenutniNiz==(niz->brojElemenata()-1)) return false;
- else
- {
- trenutniNiz++;
- return true;
- }
- }
- else if(lista!=0)
- {
- if(lista->brojElemenata()==0) throw "Prazna lista!";
- if(trenutniLista->veza==0) return false;
- else
- {
- trenutniLista=trenutniLista->veza;
- return true;
- }
- }
- else if (Dlista!=0)
- {
- if(Dlista->brojElemenata()==0) throw "Prazna dvostruka lista!";
- if(trenutniDlista->veza_naprijed==0) return false;
- else
- {
- trenutniDlista=trenutniDlista->veza_naprijed;
- return true;
- }
- }
- }
- void pocetak()
- {
- if(niz!=0)
- {
- if(niz->brojElemenata()==0) throw "Prazan niz!";
- trenutniNiz=0;
- }
- else if(lista!=0)
- {
- if(lista->brojElemenata()==0) throw "Prazna lista!";
- while(prethodni());
- }
- else if(Dlista!=0)
- {
- if(Dlista->brojElemenata()==0) throw "Prazna dvostruka lista!";
- while(prethodni());
- }
- }
- void kraj()
- {
- if(niz!=0)
- {
- if(niz->brojElemenata()==0) throw "Prazan niz!";
- trenutniNiz=(niz->brojElemenata()-1);
- }
- else if(lista!=0)
- {
- if(lista->brojElemenata()==0) throw "Prazna lista!";
- while(sljedeci());
- }
- else if(Dlista!=0)
- {
- if(Dlista->brojElemenata()==0) throw "Prazna dvostruka lista";
- while(sljedeci());
- }
- }
- };
- template <typename NekiTip>
- NekiTip dajMaksimum(const Niz<NekiTip> &n)
- {
- Iterator<NekiTip> i(n);
- NekiTip max(i.trenutni());
- while(i.sljedeci())
- {
- if(i.trenutni()>max) max=i.trenutni();
- }
- return max;
- }
- template <typename NekiTip>
- NekiTip dajMaksimum(const Lista<NekiTip> &n)
- {
- Iterator<NekiTip> i(n);
- NekiTip max(i.trenutni());
- while(i.sljedeci())
- {
- if(i.trenutni()>max) max=i.trenutni();
- }
- return max;
- }
- template <typename NekiTip>
- NekiTip dajMaksimum(const DvostrukaLista<NekiTip> &n)
- {
- Iterator<NekiTip> i(n);
- NekiTip max(i.trenutni());
- while(i.sljedeci())
- {
- if(i.trenutni()>max) max=i.trenutni();
- }
- return max;
- }
- int main()
- {
- try
- {
- cout << "Ukoliko zelite koristiti niz unesite 1, za lisu unesite 2!";
- int opcija;
- cin >> opcija;
- clock_t vrijeme1 = clock();
- if(opcija==1)
- {
- Niz<int> *niz;
- niz=new Niz<int>;
- for (int i(1); i<=10; i++)
- niz->dodajIza(i);
- cout << dajMaksimum(*niz) << endl;
- delete niz;
- }
- if(opcija==2)
- {
- Lista<int> *niz;
- niz=new Lista<int>;
- for (int i(1); i<=10; i++)
- niz->dodajIza(i);
- cout << dajMaksimum(*niz) << endl;
- delete niz;
- }
- if(opcija==3)
- {
- DvostrukaLista<int> *niz;
- niz=new DvostrukaLista<int>;
- for (int i(1); i<=10; i++)
- niz->dodajIza(i);
- cout << dajMaksimum(*niz) << endl;
- delete niz;
- }
- clock_t vrijeme2 = clock();
- int ukvrijeme = (vrijeme2 - vrijeme1) / (CLOCKS_PER_SEC / 1000);
- cout << "Vrijeme izvrsenja: " << ukvrijeme << " ms." << endl;
- }
- catch (const char poruka[])
- {
- cout<<poruka;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment