Nadam se da sam lepo iskomentarisao kod. Ako ne razumes neke stvari, zamolio bih te da prvo potrazis po net-u neki tutor o povezanoj listi(linked list). Bice mi drago ako budem cuo neka pitanja ili komentare. Mislim da ce ovaj kod biti konacan, osim ako neko ne pronadje neko gresku ili smatra da treba jos nesto da se ubaci.
Code:
class CDLista
{
private:
static const int velicinaNiza=20; // velicina niza, tj. koliko ce elemenata da sadrzi jedan node
struct node // node, u njemu se nalaze podaci koje dinamicki niz sadrzi i pokazivac na sledeci node
{ // koristi se trik da struktura moze sadrzati pokazivac na objekat iste strukture
int lista[velicinaNiza]; //taj pokazivac(next) ima vrednost 0 ako next pokazuje na nista, tj ne pokazuje na objekat klase node
node *next; // u tom slucaju to je kraj niza
~node() // destruktor, jer treba obristi i sledece strukture na koje ukazuje next
{ // u suprotnom slucaju, program bi opet raio ali doslo bi do curenja memorije
if (next!=0) // ako next nije nula, onda next ukazuje na objekat klase node koga treba obrisati
delete next; // ovaj destruktor je rekurzivan pa ce se primenjivati dok ne dodje to kraja povezane liste node-ova
}
node() // konstruktor bez argumenata
{
next=0; // osigurano je da ce next biti 0, tj da nece pokazivati na objekat
}
node(node& osnova) // ovaj konstruktor kopira jedan u drugi node, sto se koristi prilikom kopiranja celog
{ // objekta klase u drugi.
for (int i=0;i<velicinaNiza;i++) // u svakom nodu se kopiraju clanovi manje liste(od 20 clanova)
{
lista[i]=osnova.lista[i];
}
if (osnova.next!=0) // da li je u pitanju kraj povezane liste
{
next=new node(*osnova.next); // ako nije, poziva se rekurzivna funkcija
}
else next=0; // kraj povezane liste node-ova;
}
} ;
node *prvi; // ovde cemo drzati pokazivac na prvi node, preko kojeg cemo moci da dodjemo
// do ostalih node-ova preko pokazivaca *next
int _size; // velicina niza
public:
CDLista() // konstruktor
{ //treba inicijalizovati pocetne vrednosti
prvi=new node();
_size=0;
}
CDLista(CDLista& lista) // konstruktor sa parametrom iste klase
{ // ovde treba kopirati podatke iz lista u trenutni objekat klase(u *this)
_size=lista._size; // prvo kopiramo velicinu
prvi=new node(*lista.prvi); // pa i prvi node, ali pritom pazimo da kopiramo sadrzaj, a ne adresu
// zbog toga ne treba napisati prvi=lista.prvi, jer bi se promenom nekog clana
// jednog objekta promenio i drugi
}
bool change(unsigned int index, int broj) // funkcija koja menja neki clan lista
{ // ili unosi novi. Treba je koristiti za vec inicijalizovane clanove
// ili da bi se inicijalizovao prvi neinicijalizovani clan, jer ako
// bi se inicijalizovao clan recimo rbr. 50, a lista je do tada imala
// 20 clanova, clanovi od 21 do 50 bi imali neodredjene vrednosti
if (index>_size) // ovde se osiguravamo da se nece desiti malopre pomenuta situacija
return false;
int koraci=index/velicinaNiza; // u kom po redu node-u se nalazi element
int element=index%velicinaNiza; // koji po redu element je u listi u node-u(moze biti od 0 do velicinaNiza=20)
node *xnode=prvi; // xnode sluzi za kretanje kroz povezanu listu, preko xnode->next dolazimo do sledeceg
for (int i=0; i<koraci; i++) // node-a. Ova petlja pronalazi adresu i-tog noda, u kome se nalazi element koga trazimo
{
if (xnode->next==0) // ako je kraj node, uzimamo novi. Ovo ce se desiti samo ako je element prvi
xnode->next=new node(); // neinicijalizovan, i prvi je u listi node-a
xnode=xnode->next; // prenosimo adresu xnode-a dalje, da bi se petlja izvrsila na sledecem node-u
}
if (index==_size) // ako je index==_size, to je slucaj sa prvim neinicijalizovanim brojem,
_size++; // pa moramo povecati velicinu celog objekta
xnode->lista[element]=broj; // dodela broja
return true; // posto je broj dodeljen, vracamo vrednost true
}
int size() // jednostavna funkcija koja vraca trenutnu velicinu niza
{
return _size;
}
int& operator[](int index) // funkcija dosta slicna funkciji change, samo sto ne proveravamo
{ // _size, i ne vrsimo dodelu.
int koraci=index/velicinaNiza; // Vazno je da ova funkcija vraca referencu na element objekta,
int element=index%velicinaNiza; // da bi mogli da ga promenimo(kao lista[0]=3);
node *xnode=prvi;
for (int i=0; i<koraci; i++)
xnode=xnode->next;
return xnode->lista[element]; // vraca element(tipa int)
}
void operator= (CDLista& lista) // kopira elemente lista u elemente niz, pri cemo je vazno
{ // da ne kopiramo pokazivace u pokazivace sa istom adresom
delete prvi; // brisemo prvi node, da ne bi doslo do curenja memorije
// naravno ovo brise(rekurzivno) i sve ostale node-ove
_size=lista.size(); // ista velicina
prvi=new node(*lista.prvi); // opet se rekurzivno preslikava reprezentacija cele liste
// pri cemu prvi i lista.prvi nemaju iste adrese,
// a razlicite adrese imaju i pokazivaci koji oni sadrze
// zbog rekurzivne funkcije node(const node& osnova)
}
void append(int broj) // funkcija za dodavanje elementa
{
change(_size, broj); // poziva change za index na poslednjem mestu
} // nema potrebe da pisemo _size++ jer ce to funkcija change
// sama uraditi
void pop() // brise poslednji element
{ // pri tom brise i node ako je u pitanju element na mestu 0 tog node-a.
if (_size!=0) // ako je objekat nema elemente onda nema sta izbrisati
{
_size--; // smanjuje se velicina niza
if (_size%velicinaNiza==0 && _size!=0) // brisemo poslednji node, ako je element prvi u node-ovoj listi, i naravno
{ // nije prvi u prvom node-u, jer bi to bila greska, jer bi posle isti morali da inicijalizujemo
int koraci=((_size)/velicinaNiza)-1; // opet slicno funkciji change, samo razlika je sto su koraci za jedan manji,
node *xnode=prvi; // jer trebamo ne samo da obrisemo poslednji node, vec i da u pretposlednjem
for (int i=0; i<koraci; i++) // poslednji node (next) oznacimo kao kraj povezane liste node-ova
{ // takodje treba paziti da je _size vec smanjen, pa prilikom racunanja index poslednjeg
xnode=xnode->next; // elementa je _size, a ne _size-1
}
delete xnode->next; // sustina funkcije, brisanje poslednjeg node-a, ako su se za
xnode->next=0; // to stekli uslovi
}
}
}
void empty() // brise sve elemente
{
if (_size!=0) // ako je objekat nema elemente onda nema sta izbrisati
{
delete prvi; // brisemo sve podatke objekta pa ih opet inicijalizujemo
prvi=new node()
_size=0;
}
}
};
[Zadatak] Dinamicki Array
