Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kruzne liste sa headerom

[es] :: Art of Programming :: Kruzne liste sa headerom

[ Pregleda: 2724 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Djordjevic
Nemanja Djordjevic
Beograd

Član broj: 81524
Poruke: 56
*.adsl-3.sezampro.yu.

Sajt: www.itradionica.com


Profil

icon Kruzne liste sa headerom20.03.2008. u 10:41 - pre 167 meseci
Moze li neko da mi objasni kako se implementiraju kruzne ulancane liste sa headerom. Problem je u tome sto pokazivac na header nije istog tipa kao na neki drugi clan liste, ili ja gresim, posto mi stvarno nije jasno kako bi moglo da je header istog tipa kao i drugi cvorovi, kad drze razlicite podatke. Ako bi neko mogao da mi malo pojasni ovo bio bih mu zahvalan.
---------------------------
IT Radionica
http://www.itradionica.com
---------------------------
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Kruzne liste sa headerom20.03.2008. u 11:46 - pre 167 meseci
Kako misliš drže različite podatke, i šta tačno podrazumevaš pod "headerom"? Pointer na "glavu" liste?
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6023



+4621 Profil

icon Re: Kruzne liste sa headerom20.03.2008. u 12:03 - pre 167 meseci
Pretpostavljam da pod headerom podrazumeva sentinel nod, koristi se u dvostruko uvezanim listama kao NULL node, tako da umesto da imas:

prvi.prev = null and zadnji.next = null

imas

prvi.prev = headerObj and zadnji.next = headerObj

Po teoriji omogucava lakse dodavanje novih elemenata na pocetak i kraj liste, i omogucava dvostruko uvezane liste sa nula elementata bez da pointer na listu bude null (lista pokazuje na samo header ciji prev i next pokazuju na samog sebe). Sam header se ne tretira kao node u listi i ne mora da bude istog tipa kao ostali nodovi (mada moze biti istog tipa sa odredjenom "nemogucom" kombinacijom elemenata noda koji ga cine headerom)

Downside je sto se dvostruko uvezana lista pretvara u cirkularnu jer prvi i zadnji element referenciraju header, tako da ako izgubis pointer na header GC nece moci da pocisti listu jer postoji kruzna referenca => memory leak.



Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Djordjevic
Nemanja Djordjevic
Beograd

Član broj: 81524
Poruke: 56
*.adsl-a-1.sezampro.yu.

Sajt: www.itradionica.com


Profil

icon Re: Kruzne liste sa headerom20.03.2008. u 23:49 - pre 167 meseci
mmix je otprilike objasnio o cemu se radi, mada nije apsolutno neophodno da lista bude dvostruko ulancana. Ali mi opet nije jasno ono glavno. Da li se header razlikuje po podacima koje drzi(sto je bezveze jer bi onda morao da provaram svaki cvor za tu neku "nemogucu kombinaciju" pri svakoj operaciji, ili je to stvarno drugi tip podatka?

Rasmisljajuci o ovome palo mi je na pamet kako bi se eventualno to moglo realizovati(ne od strane mene:)).
Da li je moguce to uraditi koriscenjem virtuelnih funkcija kao sto to radimo kod klasa derivata, da bismo mogli da razlucimo o kojoj strukturi se radi, prilikom samog izvrsavanja programa. ?
---------------------------
IT Radionica
http://www.itradionica.com
---------------------------
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6023



+4621 Profil

icon Re: Kruzne liste sa headerom21.03.2008. u 08:41 - pre 167 meseci
Header uopste ne nosi podatke, on je samo pozicioni objekat koji ti sluzi za ulazak u listu, nista vise. Provere mozes raditi po bilo kom osnovu npr ako je heder klase MojeHeader ovo ce proci kroz celu listu:

Code:

MojHeader lista = veckreiranalista;
Object el = lista.next;
while (not (el is Header)) { mojel = castuj el u MojElement i koristi; el = mojel.next; }



Eventualno heder moze da bude instanca klase u koju mozes da ubacis metode i implementiras interfejse za podrsku radu sa listom, npr da implementiras IEnumerable<T> i IList<T> ili da ubacis Count property ili ubacis indexer this[] itd.

Ono sto ne razumem je zasto ti uopste hoces da implementiras ovo (skolski zadatak?). U .NETu jednostavno nemas potrebe za ovime jer vec postoje implementacije koje mogu da zadovolje sve potrebe. Npr LinkedList<T> generic je dvostruko uvezana lista gde samu instancu liste mozes tretirati kao header (mada nije bas koser po definiciji, ne vaze oni uslovi koje sam naveo prosli put sa ciklicnoscu, sto su sigurno uradili da bi izbegli memory leak situacije).

[PS: sarry sad videh, ovo je tema u art-of-prog, ignorisi pitanje :), koji jezik bi ti koristio za implementaciju?]
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Djordjevic
Nemanja Djordjevic
Beograd

Član broj: 81524
Poruke: 56
*.adsl-a-1.sezampro.yu.

Sajt: www.itradionica.com


Profil

icon Re: Kruzne liste sa headerom21.03.2008. u 22:00 - pre 166 meseci
jeste skolski zadatak :)

Mislim iako to sustinski nije bitno ali bi mi svakako koristila implementacija u plain C.


---------------------------
IT Radionica
http://www.itradionica.com
---------------------------
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6023



+4621 Profil

icon Re: Kruzne liste sa headerom22.03.2008. u 08:32 - pre 166 meseci
Ako znas engleski, pogledaj sledecu lekciju sa stanforda, oni su bas lepo objasnili i koncep i sve moguce operacije nad linked listama zajedno sa C kodom:

Stanford Edu: Linked List Basics

Tvoja implementacija bi se utliko razlikovala sto ti head pointer ne pokazuje na prvi element niza, vec na tvoj header, koji moze biti drugacije strukture, ali treba da ima next, tako da sve funkcije modifikujes tako da umesto da koriste head kao pocetak liste, koriste head->next kao prvi element.


Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Djordjevic
Nemanja Djordjevic
Beograd

Član broj: 81524
Poruke: 56
*.adsl-1.sezampro.yu.

Sajt: www.itradionica.com


Profil

icon Re: Kruzne liste sa headerom24.03.2008. u 17:14 - pre 166 meseci
hvala puno na tekstu. samo sam preleteo, ali mislim da ce koristiti
---------------------------
IT Radionica
http://www.itradionica.com
---------------------------
 
Odgovor na temu

[es] :: Art of Programming :: Kruzne liste sa headerom

[ Pregleda: 2724 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.