Pocetnicki nivo: povezane liste

E, ovako. Pokusacu da ti razjasnim jer sam i ja lupao glavu oko toga. NAJVAZNIJE od svega je da shvatis kako pointeri rade, jer bez njih ovo 'kompleksno' upravljanje memorijom nije lako dokuciti.

Lista radi na taj nacin sto svaki cvor sadrzi macku ( itsCat ), i sadrzi memorijsku adresu sledeceg cvora ( itsNext ), koji opet sadrzi drugu macku i ukazuje na sledeci cvor ...

Head: macka i sledeciCvor1
|
sledeciCvor1: macka1 i sledeciCvor2
|
sledeciCvor2: macka2 i sledeciCvor3
...

U sustini, nama su potrebne samo informacije o mackama ali cvorovi su tu da macke poredjaju po nekom redosledu u zavisnosti od nekog parametra ( npr. ovde je to zavisnost od broja godina i sortiramo listu po tom parametru).

Malo objasnjenja sta linije rade ( mada je to vec objasnjeno ):


#include<iostream.h>

// ovo necu da objasnjavam

class Cat
{
public:
Cat():
itsAge(1)
{};
Cat(int age):
itsAge(age)
{};
~Cat() {}
int GetAge() const {return itsAge;}
private:
int itsAge;
};

// klasa cvora: sadrzi macku i cuva adresu sledece macke (itsNext)

class Node
{
public:
Node(Cat*);
~Node();

void SetNext(Node * node) {itsNext = node;} // postavljanje informacije o sledecem cvoru
Node * GetNext() const {return itsNext;} // vracanje informacije o sledecem cvoru
Cat * GetCat() const {return itsCat;} // vracanje informacije o macki koja se nalazi u OVOM cvoru

void Insert(Node *); // najkompleksniji deo ( objasnjen posle )
void Display(); // prikazivanje u zadatom redosledu ( zavisi od godista )

private:
Cat * itsCat; // macka u ovom cvoru
Node * itsNext; // adresa sledeceg cvora
};

Node::Node(Cat * pCat):
itsCat(pCat), itsNext(0)
{};
Node::~Node()
{
cout<<"Deleting mode...\n";
delete itsCat;
itsCat = 0;
delete itsNext; // veoma vazno: Ako obrisemo head koji ukazuje na sledeci itsNext = 0; cvor koji takodje ukazuje na sledeci itd. mi brisemo celu listu, jer komanda 'delete' poziva dekonstruktor (ili destruktor, kako vec) sledeceg nodea! Takodje, ako u listi imamo 5 cvorova i obrisemo 3. brisu se i 4. i 5. posto 3. ukazuje na njih


}

// funkcija Insert.
Evo primera:

deklarisali smo sledece macke:

Cat * PrvaMackaUListi = new Cat(0); // macka koja je Head i koja se ne prikazuje mada je mogao i tom da bude Head ali je programer hteo to na ovaj nacin.

Cat * Tom = new Cat(3); // tri godine
Cat * Silvester = new Cat(5); // pet godina
Cat * Mile = new Cat(4); // cetiri godine

Node * pHead = new Node(PrvaMackaUListi );

pHead->Insert(Tom); // 3 godine
pHead->Insert(Silvester ); // 5 godina
pHead->Insert(Mile); // 4 godine

Funkcija prvo ubacuje u listu Toma-a, koji je itsNext za PrvaMackaUListi ( cija macka se ne koristi ali ukazuje na sledecu macku koja je u ovom slucaju Tom).

Sledeci je Silvester koji se ubacuje posle Toma i to radi deo koda Insert funkcije oznacen sa (1).

Ubacujemo Mileta. On ima 4 godine pa mora ici odmah iza Toma i iz toga sledi da mora ici pre Silvestera. 3 < 4 < 5. Ovo radi kod funkcije Insert oznacen sa (2)

I sada je poredak Tom->Mile->Silvester tj oni sada tako stoje u memoriji jedan pored drugog i svaki ukazuje na sledeceg

void Node::Insert(Node * newNode)
{
if(!itsNext)
itsNext = newNode;
else
{
int nextCatsAge = itsNext->GetCat()->GetAge(); // godine sledece macke u listi itsNext
int newAge = newNode->GetCat()->GetAge(); // godine macke koja se ubacuje u listu
int thisNodeAge = itsCat->GetAge(); // godine macke koju ovaj node sadrzi

(2) ----- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

if(newAge >= thisNodeAge && newAge < nextCatsAge) // uporedjuje godiste macke koja se UBACUJE, sa godistima macaka OVOG nodea i nodea na koji ovaj UKAZUJE (tj. sledeceg)
[ ne verujem da ces ovo skapirati iz prve ali pokusavaj, probaj sam da otkucas npr. za Doga ]
{
newNode->SetNext(itsNext); // e sada node koji je itsNext ovom nodeo postavlja se kao itsNext novom nodeu

itsNext = newNode; // sledeci nod ovom nodeu je novi node tako da sada imamo ovakav poredak:
thisNode -> newNode -> itsNext
a pre je bilo
thisNode -> itsNext.
(this node se ne vidi ali on je predstavljen pokazivacem this pa ako razumes pokazivac this bice ti malo jasnije)

// zavrsava se (2) /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
else
itsNext->Insert(newNode); (1)
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// funkcija Display(): PrvaMackaUListi se ne prikazuje jer je njeno godiste 0 i to funkcija proverava.

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Node::Display()
{
if(itsCat->GetAge() > 0)
{
cout<<"My cat is ";
cout<<itsCat->GetAge()<<" yrs. old\n";
}
if(itsNext) // ako imamo itsNext posmatrajuci PrvaMackaUListi to je Tom, posmatrajuci Toma-a to je posle insertovanja Mile ...
itsNext->Display();
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

evo i ovde slicnog primera sa mackama

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
Node *pNode = 0;
Cat * pCat = new Cat(0); // 'nulta' macka
int age;

Node * pHead = new Node(pCat); // 'nulti' node: GLAVA

while(1)
{
cout<<"New Cat's age? (0 to quit): ";
cin>>age;
if(!age)
break;
pCat = new Cat(age); // pavimo macku
pNode = new Node(pCat); // pravimo node
pHead->Insert(pNode); // insertujemo macku u listu
}
pHead->Display(); // prikaz
delete pHead; // brisu se sve macke !!!!!!!!
cout<<"Exiting...\n";
return 0;
}

Potpis

EOF