Liste

Uvod

Pri rešavanju mnogih problema potrebne su nam dinamičke liste, čiju veličinu ne moramo znati u trenutku kompajliranja, već je možemo definisati i u toku rada programa. Povezana lista je struktura podataka koja se koristi za modeliranje ovakvih dinamičkih lista.

Koncept

Nizovi su u memoriji predstavljeni korišćenjem sekvencijalnog mapiranja, tako da su elementi niza podjednako udaljeni jedan od drugog. Međutim, ovakav pristup ima sledeće nedostatke:

  • Umetanje novog ili brisanje postojećeg elementa iz niza je vremenski veoma skupa operacija, jer zahteva pomeranje određenog broja postojećih elemenata.
  • U slučaju korišćenja statičkih nizova neophodno je poznavanje maksimalnog broja elemenata još u trenutku pisanja programa. Pored ovog nedostatka, dodatni problem je i to što bez obzira na stvaran broj elemenata koji će biti smešten u niz, program uvek alocira maksimalnu veličinu niza, što dovodi do bespotrebnog trošenja memorije.
  • Korišćenje dinamičkih nizova rešava problem poznavanja maksimalnog broja elemenata u trenutku pisanja programa, ali uvodi i neke nove probleme. Svaka promena veličine niza zahteva dodatnu alokaciju i dealokaciju memorije, kao i kopiranje sadržaja elemenata u novi memorijski prostor, što drastično pogoršava performanse programa.

Da bi se prevazišli navedeni problemi uvodi se koncept povezanih elemenata. U ovakvom pristupu nije neophodno da elementi budu međusobno na podjednakom rastojanju. Umesto toga elemente možemo smestiti bilo gde u memoriji, a zatim ih povezati tako da svaki element (osim prvog) bude povezan sa prethodnim elementom u listi. To se može postići tako što se u svaki element upiše i adresa njegovog sledbenika, što zahteva da svaki element bude u mogućnosti da pored svojih podataka čuva i adresu sledećeg elementa. Zbog toga svaki element mora biti struktura koja sadrži dva dela: jedan koji čuva neophodne podatke (nazovimo ga podatak1) ili data field) i drugi koji čuva adresu sledbenika (veza ili link). Dakle, povezana lista je lista elemenata koji su proizvoljno raspoređeni u memoriji i koji su međusobno povezani linkom, tj. smeštanjem adrese svakog elementa (osim prvog) u njegovog prethodnika.

Definisanje

Za realizaciju koncepta povezanih lista u programskom jeziku C koriste se slogovi (strukture) i pokazivači (pointeri). Element liste koja će sadržati celobrojne podatke se definiše na sledeći način:

struct element 
{ 
  int podatak; 
  struct element *sledeci; 
};

Prethodne linije koda definišu strukturni tip element koji će predstavljati element liste. Svaki element liste sadrži celobrojni podatak i pokazivač na sledeći element liste. Podatak unutar liste može biti i bilo kog drugog prostog ili složenog tipa.

Prolazak kroz listu

U radu sa listama je često potrebno kretati se kroz listu, od elementa do elementa. Najčešće je u pitanju obrada podataka u listi, pretraga liste kako bi se našao odgovarajući element ili traženje kraja liste. U svim ovim slučajevima algoritam je sličan. Uvodi se pomoćni pokazivač koji je inicijalno jednak glavi liste, odnosno pokazuje na prvi element liste ukoliko ona nije prazna. Nakon provere da li pokazivač pokazuje na neki element (ima vrednost različitu od NULL) vrši se obrada podatka u tom element (štampa, upoređivanje, račun…). Po završetku obrade podatka, pomoćni pokazivač dobija vrednost pokazivača na sledeći element, a čitav postupak se ponavlja sve dok pomoćni pokazivač ima nenultu vrednost, tj. dok pokazuje na neki element. Kada pomoćni pokazivač dobije vrednost NULL, to znači da smo došli do kraja liste. Sledeći isečak koda pokazuje prolazak kroz listu čiji je početak definisan pokazivačem glava i štampanje podataka zapisanih u svim njenim elementima: struct element *pom;

pom=glava; 
while(pom!=NULL) 
{ 
  printf("%d\t",pom‐>podatak); 
  pom=pom‐>sledeci; 
}; 

Primer:

Literatura:

1) Podatak u bukvalnom prevodu sa latinskog jezika znači “nešto što je dato”.
 
liste.txt · Last modified: 2012/02/29 19:57 by tomislav.mrda
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki