Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- template <typename Tip>
- class Iterator;
- template<typename tip>
- class Niz
- {
- int tren, broj_el, kapacitet, prati;
- tip *niz;
- public:
- Niz(): tren(0), broj_el(0), kapacitet(1), prati(0), niz(new tip[kapacitet]) {}
- virtual int brojElemenata() const
- {
- return broj_el;
- }
- virtual ~Niz()
- {
- if(broj_el>0)
- {
- delete[] niz;
- }
- }
- Niz (const Niz &n);
- Niz &operator=(const Niz &n);
- virtual tip trenutni();
- virtual bool prethodni();
- virtual bool sljedeci();
- virtual void pocetak();
- virtual void kraj();
- virtual void dodajIspred(const tip &element);
- virtual void dodajIza(const tip &element);
- virtual void obrisi();
- virtual tip operator[](int n) const;
- friend class Iterator<tip>;
- };
- template<typename tip>
- class Lista : public Niz<tip>
- {
- struct Cvor
- {
- tip element;
- Cvor *sljedeci;
- };
- Cvor *poc, *kr, *tren;
- int broj_el;
- public:
- Lista():
- poc(0), kr(0), tren(0), broj_el(0) {}
- ~Lista();
- Lista (const Lista &l);
- Lista &operator=(const Lista &l);
- int brojElemenata() const;
- tip trenutni() const;
- bool prethodni();
- bool sljedeci();
- void pocetak();
- void kraj();
- void dodajIspred(const tip &element);
- void dodajIza(const tip &element);
- void obrisi();
- tip operator[](int n) const;
- friend class Iterator<tip>;
- };
- //Klasa DvostrukaLista - zadaca.
- template<typename tip>
- class DvostrukaLista : public Niz<tip>
- {
- struct DupliCvor
- {
- tip element;
- DupliCvor *sljedeci;
- DupliCvor *prethodni;
- };
- DupliCvor *poc, *kr, *tren;
- int broj_el;
- public:
- DvostrukaLista(): poc(0), kr(0), tren(0), broj_el(0) {}
- ~DvostrukaLista();
- DvostrukaLista (const DvostrukaLista &dl);
- DvostrukaLista &operator=(const DvostrukaLista &dl);
- int brojElemenata() const;
- tip trenutni() const;
- bool prethodni();
- bool sljedeci();
- void pocetak();
- void kraj();
- void dodajIspred(const tip &element);
- void dodajIza(const tip &element);
- void obrisi();
- tip operator[](int n) const;
- friend class Iterator<tip>;
- };
- //Klasa iterator, nisam je ni poceo na tutorijalu zbog ispravljanja greski sa pripreme za tutorijal.
- template<typename tip>
- class Iterator
- {
- const Niz<tip> *niz;
- const Lista<tip> *lista;
- const DvostrukaLista<tip> *dvostruka;
- int trenutniNiz;
- typename Lista<tip>::Cvor *trenutniLista;
- typename DvostrukaLista<tip>::DupliCvor *trenutniDvostrukaLista;
- public:
- Iterator(const Niz<tip> &n) : niz(&n), lista(0), dvostruka(0), trenutniNiz(0), trenutniLista(0), trenutniDvostrukaLista(0) {}
- Iterator (const Lista<tip> &l) : lista(&l), niz(0), dvostruka(0), trenutniNiz(0), trenutniLista(l.poc), trenutniDvostrukaLista(0) {}
- Iterator (const DvostrukaLista<tip> &dl) : dvostruka(&dl), niz(0), lista(0), trenutniNiz(0), trenutniLista(0), trenutniDvostrukaLista(dl.poc) {}
- tip trenutni() const;
- bool prethodni();
- bool sljedeci ();
- void pocetak();
- void kraj();
- };
- template<typename tip>
- Niz<tip>::Niz (const Niz<tip> &n)
- {
- niz=new tip[n.broj_el];
- broj_el=n.broj_el;
- kapacitet=n.kapacitet;
- tren=n.tren;
- prati=n.prati;
- for(int i=0; i<broj_el; i++)
- {
- niz[i]=n.niz[i];
- }
- }
- template<typename tip>
- Niz<tip> &Niz<tip>::operator=(const Niz<tip> &n)
- {
- if(broj_el>0)
- {
- delete[] niz;
- }
- niz=new tip[n.broj_el];
- broj_el=n.broj_el;
- kapacitet=n.kapacitet;
- tren=n.tren;
- prati=n.prati;
- for(int i=0; i<broj_el; i++)
- {
- niz[i]=n.niz[i];
- }
- return *this;
- }
- template<typename tip>
- tip Niz<tip>::trenutni()
- {
- if (broj_el==0) throw "Nema elemenata u nizu";
- return niz[tren];
- }
- template<typename tip>
- bool Niz<tip>::prethodni()
- {
- if (tren==0) return false;
- tren--;
- return true;
- }
- template<typename tip>
- bool Niz<tip>::sljedeci()
- {
- if (tren==broj_el-1) return false;
- tren++;
- return true;
- }
- template<typename tip>
- void Niz<tip>::pocetak()
- {
- tren=0;
- }
- template<typename tip>
- void Niz<tip>::kraj()
- {
- tren=broj_el-1;
- }
- template<typename tip>
- void Niz<tip>::dodajIspred(const tip &element)
- {
- if (broj_el==0)
- {
- if(prati!=0)
- {
- niz=new tip[kapacitet];
- }
- niz[broj_el]=element;
- broj_el++;
- }
- else
- {
- niz[broj_el]=element;
- broj_el++;
- for (int i=broj_el-1; i>tren; i--)
- {
- tip pom=niz[i];
- niz[i]=niz[i-1];
- niz[i-1]=pom;
- }
- tren++;
- }
- if(broj_el==kapacitet)
- {
- kapacitet*=2;
- tip *pom=new tip[kapacitet];
- for(int i=0; i<broj_el; i++)
- {
- pom[i]=niz[i];
- }
- delete[] niz;
- niz=pom;
- }
- }
- template<typename tip>
- void Niz<tip>::dodajIza(const tip &element)
- {
- if (broj_el==0)
- {
- if(prati!=0)
- {
- niz=new tip[kapacitet];
- }
- niz[broj_el]=element;
- broj_el++;
- }
- else
- {
- niz[broj_el]=element;
- broj_el++;
- for (int i=broj_el-1; i>tren; i--)
- {
- tip pom=niz[i];
- niz[i]=niz[i-1];
- niz[i-1]=pom;
- }
- }
- if(broj_el==kapacitet)
- {
- kapacitet*=2;
- tip *pom=new tip[kapacitet];
- for(int i=0; i<broj_el; i++)
- {
- pom[i]=niz[i];
- }
- delete[] niz;
- niz=pom;
- }
- }
- template<typename tip>
- void Niz<tip>::obrisi()
- {
- if (broj_el==0) throw "Niz je prazan.\n";
- if(broj_el==1)
- {
- broj_el=0;
- delete[] niz;
- niz=0;
- if(prati==0) prati=1;
- }
- else
- {
- broj_el--;
- if(broj_el>0 && broj_el==kapacitet/4)
- {
- kapacitet/=2;
- tip *pom=new tip[kapacitet];
- for(int i=0; i<broj_el; i++)
- {
- if(i<tren) pom[i]=niz[i];
- else pom[i]=niz[i+1];
- }
- delete[] niz;
- niz=pom;
- }
- else
- {
- tip *pom=new tip[broj_el];
- for(int i=0; i<broj_el; i++)
- {
- if(i<tren) pom[i]=niz[i];
- else pom[i]=niz[i+1];
- }
- delete[] niz;
- niz=pom;
- }
- }
- }
- template<typename tip>
- tip Niz<tip>::operator[](int n) const
- {
- if (n<0 || n>broj_el-1) throw "Pogresan indeks";
- //tren=n-1;
- return niz[n];
- }
- template<typename tip>
- Lista<tip>::~Lista() {
- Cvor *pom=poc;
- while(pom!=0){
- pom=pom->sljedeci;
- delete poc;
- poc=pom;
- }
- broj_el=0;
- poc=kr=tren=0;
- }
- //URADI KOPIJU I OPERATOR DODJELE!!!
- template<typename tip>
- int Lista<tip>::brojElemenata() const
- {
- return broj_el;
- }
- template<typename tip>
- tip Lista<tip>::trenutni() const
- {
- if (poc==0) throw "Nema elemenata u nizu";
- return tren->element;
- }
- template<typename tip>
- bool Lista<tip>::prethodni()
- {
- if (tren==poc) return false;
- else
- {
- Cvor *p=poc;
- while (p->sljedeci!=tren)
- {
- p=p->sljedeci;
- }
- tren=p;
- return true;
- }
- }
- template<typename tip>
- bool Lista<tip>::sljedeci()
- {
- if (tren==kr) return false;
- else
- {
- tren=tren->sljedeci;
- return true;
- }
- }
- template<typename tip>
- void Lista<tip>::pocetak()
- {
- tren=poc;
- }
- template<typename tip>
- void Lista<tip>::kraj()
- {
- tren=kr;
- }
- template<typename tip>
- void Lista<tip>::dodajIspred(const tip &element)
- {
- Cvor *novi=new Cvor;
- novi->element=element;
- novi->sljedeci=0;
- if (poc==0)
- {
- poc=kr=tren=novi;
- }
- else if (tren==poc)
- {
- novi->sljedeci=poc;
- poc=novi;
- }
- else
- {
- Cvor *prethodni=poc;
- novi->sljedeci=tren;
- while (prethodni->sljedeci != tren)
- prethodni=prethodni->sljedeci;
- prethodni->sljedeci=novi;
- }
- broj_el++;
- }
- template<typename tip>
- void Lista<tip>::dodajIza(const tip &element)
- {
- Cvor *novi=new Cvor;
- novi->element=element;
- novi->sljedeci=0;
- if (brojElemenata()==0)
- {
- poc=tren=kr=novi;
- }
- else
- {
- if(tren->sljedeci!=0)
- {
- novi->sljedeci=tren->sljedeci;
- }
- tren->sljedeci=novi;
- }
- broj_el++;
- }
- template<typename tip>
- void Lista<tip>::obrisi()
- {
- if (broj_el==0) throw "Lista je prazna";
- if(tren==poc)
- {
- poc=poc->sljedeci;
- delete tren;
- tren=poc;
- }
- else
- {
- Cvor *prethodni;
- prethodni=poc;
- while (prethodni->sljedeci != tren)
- {
- prethodni=prethodni->sljedeci;
- }
- if(tren->sljedeci!=0)
- {
- prethodni->sljedeci=tren->sljedeci;
- delete tren;
- tren=prethodni->sljedeci;
- }
- else
- {
- prethodni->sljedeci=0;
- delete tren;
- tren=prethodni;
- }
- }
- broj_el--;
- }
- template<typename tip>
- tip Lista<tip>::operator[](int n) const
- {
- if (n<0 || n>=brojElemenata()) throw "Pogresan indeks";
- Cvor *p=poc;
- int br(0);
- while (br<n)
- {
- p=p->sljedeci;
- br++;
- }
- return p->element;
- }
- template<typename tip>
- DvostrukaLista<tip>::~DvostrukaLista() {
- DupliCvor *pom=poc;
- while(pom!=0){
- pom=pom->sljedeci;
- delete poc;
- poc=pom;
- }
- broj_el=0;
- poc=kraj=tren=0;
- }
- //URADI KOPIJU I OPERATOR DODJELE!!!
- template<typename tip>
- int DvostrukaLista<tip>::brojElemenata() const
- {
- return broj_el;
- }
- template<typename tip>
- tip DvostrukaLista<tip>::trenutni() const
- {
- if (poc==0) throw "Nema elemenata u nizu";
- return tren->element;
- }
- template<typename tip>
- bool DvostrukaLista<tip>::prethodni()
- {
- if (tren==poc) return false;
- else
- {
- tren=tren->prethodni;
- return true;
- }
- }
- template<typename tip>
- bool DvostrukaLista<tip>::sljedeci()
- {
- if (tren==kr) return false;
- else
- {
- tren=tren->sljedeci;
- return true;
- }
- }
- template<typename tip>
- void DvostrukaLista<tip>::pocetak()
- {
- tren=poc;
- }
- template<typename tip>
- void DvostrukaLista<tip>::kraj()
- {
- tren=kr;
- }
- template<typename tip>
- void DvostrukaLista<tip>::dodajIspred(const tip &element)
- {
- DupliCvor *novi=new DupliCvor;
- novi->element=element;
- novi->sljedeci=0;
- novi->prethodni=0;
- if (brojElemenata()==0)
- {
- poc=kr=tren=novi;
- }
- else if (tren==poc)
- {
- tren->prethodni=novi;
- novi->sljedeci=tren;
- poc=novi;
- }
- else
- {
- tren->prethodni->sljedeci=novi;
- novi->prethodni=tren->prethodni;
- tren->prethodni=novi;
- novi->sljedeci=tren;
- }
- broj_el++;
- }
- template<typename tip>
- void DvostrukaLista<tip>::dodajIza(const tip &element)
- {
- DupliCvor *novi=new DupliCvor;
- novi->element=element;
- novi->sljedeci=0;
- novi->prethodni=0;
- if (brojElemenata()==0)
- {
- poc=tren=kr=novi;
- }
- else
- {
- if(tren->sljedeci!=0)
- {
- novi->sljedeci=tren->sljedeci;
- }
- tren->sljedeci->prethodni=novi;
- tren->sljedeci=novi;
- novi->prethodni=tren;
- }
- broj_el++;
- }
- template<typename tip>
- void DvostrukaLista<tip>::obrisi()
- {
- if (broj_el==0) throw "Lista je prazna";
- else if(broj_el==1)
- {
- delete tren;
- broj_el--;
- sljedeci=0;
- prethodni=0;
- }
- else if(tren==poc)
- {
- poc=poc->sljedeci;
- delete tren;
- tren=poc;
- tren->prethodni=0;
- broj_el--;
- }
- else
- {
- if(tren->sljedeci==0)
- {
- DupliCvor *pom=tren->prethodni;
- pom->sljedeci=0;
- delete tren;
- tren=pom->sljedeci;
- }
- else
- {
- DupliCvor *pom=tren->prethodni;
- pom->sljedeci=tren->sljedeci;
- delete tren;
- tren=pom->sljedeci;
- tren->prethodni=pom;
- }
- broj_el--;
- }
- }
- template<typename tip>
- tip DvostrukaLista<tip>::operator[](int n) const
- {
- if (n<0 || n>=brojElemenata()) throw "Pogresan indeks";
- DupliCvor *p=poc;
- int br(0);
- while (br<n)
- {
- p=p->sljedeci;
- br++;
- }
- return p->element;
- }
- template<typename tip>
- tip Iterator<tip>::trenutni() const
- {
- if(niz!=0)
- {
- if(niz->brojElemenata()==0) throw "Niz je prazan.\n";
- return niz->niz[trenutniNiz];
- }
- if(lista!=0)
- {
- if(lista->brojElemenata()==0) throw "Lista je prazna.\n";
- return trenutniLista->element;
- }
- if(dvostruka!=0)
- {
- if(dvostruka->brojElemenata()==0) throw "Lista je prazna.\n";
- return trenutniDvostrukaLista->element;
- }
- }
- template<typename tip>
- bool Iterator<tip>::prethodni()
- {
- if(niz!=0)
- {
- if(trenutniNiz==0)
- {
- return false;
- }
- else
- {
- trenutniNiz--;
- return true;
- }
- }
- if(lista!=0)
- {
- if(trenutniLista==lista) return false;
- else
- {
- typename Lista<tip>::Cvor *p=lista;
- while (p->sljedeci!=trenutniLista)
- {
- p=p->sljedeci;
- }
- trenutniLista=p;
- return true;
- }
- }
- if(dvostruka!=0)
- {
- if(trenutniDvostrukaLista->prethodni==0)
- {
- return false;
- }
- else
- {
- trenutniDvostrukaLista=trenutniDvostrukaLista->prethodni;
- return true;
- }
- }
- }
- template<typename tip>
- bool Iterator<tip>::sljedeci()
- {
- if(niz!=0)
- {
- if (trenutniNiz==niz->brojElemenata()-1) return false;
- trenutniNiz++;
- return true;
- }
- if(lista!=0)
- {
- if (trenutniLista->sljedeci==0) return false;
- else
- {
- trenutniLista=trenutniLista->sljedeci;
- return true;
- }
- }
- if(dvostruka!=0)
- {
- if(trenutniDvostrukaLista->sljedeci==0)
- {
- return false;
- }
- else
- {
- trenutniDvostrukaLista=trenutniDvostrukaLista->sljedeci;
- return true;
- }
- }
- }
- template<typename tip>
- void Iterator<tip>::pocetak()
- {
- while(prethodni());
- }
- template<typename tip>
- void Iterator<tip>::kraj()
- {
- while(sljedeci());
- }
- template<typename tip>
- tip dajMaksimum(const Niz<tip>& n)
- {
- if(n.brojElemenata()==0) throw "Niz je prazan.\n";
- else
- {
- tip max=n.niz[0];
- for(int i=0; i<int(n.brojElemenata()); i++)
- {
- if(n[i]>max)
- {
- max=n[i];
- }
- }
- }
- return max;
- }
- template<typename tip>
- tip dajMaksimum(const Lista<tip>& l)
- {
- if(l.poc==0) throw "Lista je prazna.\n";
- Iterator<tip> pom(l);
- tip max=pom.pocetak();
- while(pom.sljedeci())
- {
- if(pom.trenutni()>max)
- {
- max=pom.trenutni();
- }
- }
- return max;
- }
- template<typename tip>
- tip dajMaksimum(const DvostrukaLista<tip>& dl)
- {
- if(dl.poc==0) throw "Lista je prazna.\n";
- Iterator<tip> pom(dl);
- tip max=pom.pocetak();
- while(pom.sljedeci())
- {
- if(pom.trenutni()>max)
- {
- max=pom.trenutni();
- }
- }
- return max;
- }
- int main()
- {
- Niz<int> niz;
- int a(5), c(10), d(1);
- niz.dodajIspred(a);
- niz.dodajIspred(c);
- cout<<niz.trenutni()<<endl;
- niz.obrisi();
- cout<<niz.trenutni()<<endl;
- niz.dodajIza(c);
- cout<<"Trenutno ima: "<<niz.brojElemenata()<<" clanova.\n";
- niz.dodajIza(d);
- cout<<endl;
- for (int i=0; i<int(niz.brojElemenata()); i++)
- cout<<niz[i]<<endl;
- Lista <int> l;
- l.dodajIspred(1);
- l.dodajIspred(5);
- l.dodajIspred(10);
- l.dodajIza(10);
- l.dodajIza(5);
- l.dodajIza(1);
- cout<<l.trenutni()<<endl;
- for (int i=0; i<6; i++)
- {
- cout<<l[i]<<",";
- }
- cout<<endl;
- l.obrisi();
- cout<<l.trenutni()<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment