On-line učionica

6. februar 2012.

Povezane liste

Filed under: Pascal,Programiranje — jelena100janovic @ 11:11 am

Povezana lista liči na niz sem što se broj elemenata u povezanoj listi može promeniti. Povezana lista koristi pokazivače koji pokazuju na sledeći ili prethodni element.

Jednostruko povezane liste

Postoje dve vrste jednostruko povezanih listi, a to su redovi i stekovi.

Redovi

Red liči na stajanje u redu u prodavnici. Prva osoba koja je stala u red je prva osoba koju će uslužiti. U red se staje na kraju reda jer ako stanete na početak, drugi ljudi će se ljutiti. Ovo se zove FIFO (First In First Out – prvi u prvi van).

Stavka 1 –> Stavka 2 –> Stavka 3 –> (Do poslednje stavke)

Svaka stavka povezane liste je slog koji se sastoji od podatka i pokazivača na sledeću ili prethodnu stavku. Evo primera kako se deklariše slog za red i pokazivač na podatak iz reda kao i potrebne promenljive:

program red;
type
   pRed=^tRed;
   tRed=record
      podatak:integer;
      sled:pRed;
   end;
var
   glava,rep,tren:pRed;
begin
end.

Sada ćemo napraviti tri procedure. Prva procedura će dodavati stavke u listu, druga će pregledati listu i treća će oslobađati memoriju koju koristi red. Pre nego što napravimo procedure, zavirimo u glavni program.

begin
   glava:=nil; {Postavlja glavu na nil jer je red prazan}
   dodaj(1); {Dodaje 1 u red}
   dodaj(2);
   dodaj(3);
   vidi; {Pregleda red}
   unisti; {Oslobadja memoriju koju je koristio red}
end.

Procedura dodaj će imati integer kao parametar i dodaće ga na kraj reda.

procedure dodaj(i:integer);
begin
   new(tren); {Kreira novu stavku za listu}
   tren^.podatak:=i; {Postavlja vrednost stavke reda na i}
   tren^.sled:=nil; {Zavrsava red posle stavke}
   if glava=nil then {Ako nema glave reda}
      glava:=tren {Trenutna stavka postaje glava}
   else
      rep^.sled:=tren; {Postavlja trenutnu stavku na kraj}
   rep:=tren; {Obelezava trenutnu stavku kao poslednju}
end;

Procedura vidi koristi petlju da bi prikazala podatke od prve stavke do poslednje stavke reda.

procedure vidi;
begin
   tren:=glava; {Postavlja trenutnu stavku na pocetak reda}
   while tren<>nil do {Sve dok postoji trenutna stavka}
      begin
         writeln(tren^.podatak); {Ispisuje trenutnu stavku}
         tren:=tren^.sled; {Postavlja trenutnu na sledecu}
      end;
end;

Procedura unisti će osloboditi memoriju koju je koristio red.

procedure unisti;
begin
   tren:=glava; {Postavlja trenutnu stavku na pocetak reda}
   while tren<>nil do {Sve dok postoji trenutna stavka}
      begin
         tren:=tren^.sled; {Postavlja trenutnu na sledecu}
         dispose(glava); {Oslobadja memoriju glave}
         glava:=tren; {Postavlja novu glavu reda}
      end;
end;

Stekovi

Da biste razumeli stek, zamislite gomilu tanjira. Možete dodati tanjir na vrh gomile i uzeti jedan sa vrha, ali ne možete dodati ili uzeti tanjir sa dna bez da svi tanjiri popadaju. Ovo se zove LIFO (Last In First Out – poslednji u prvi van).

Stavka 1 <– Stavka 2 <– Stavka 3 <– (Do poslednje stavke)

Kada deklarišete slog za stavku u steku koristite prethodni umesto sledećeg. Evo primera.

program stek;
type
   pStek=^tStek;
   tStek=record
      podatak:integer;
      pret:pStek;
   end;
var
   rep,tren:pStek;
begin
   rep:=nil;
   dodaj(3);
   dodaj(2);
   dodaj(1);
   vidi;
   unisti;
end.

Primetićete da su brojevi dodavani od 3 do 1 na stek umesto od 1 do 3. To je zato što skidamo stvari sa vrha steka, umesto od glave reda.

Procedura dodaj će dodati stavku posle poslednje stavke u steku.

procedure dodaj(i:integer);
begin
   new(tren); {Pravi novu stavku za stek}
   tren^.podatak:=i; {Postavlja vrednost stavke steka na i}
   tren^.pret:=rep; {Postavlja prethodnu stavku na kraj}
   rep:=tren; {Trenutna stavka postaje rep}
end;

Procedure vidi i unisti su skoro iste kao kod reda, pa nema potrebe da ih objašnjavamo.

procedure vidi;
begin
   tren:=rep;
   while tren<>nil do
      begin
         writeln(tren^.podatak);
         tren:=tren^.pret;
      end;
end;

procedure unisti;
begin
   while rep<>nil do
      begin
         tren:=rep^.pret;
         dispose(rep);
         rep:=tren;
      end;
end;

Zadaci za vežbanje:

  1. Napišite procedure za ubacivanje nove stavke u sortiran red, učitavanje sortiranog reda i program koji učitava 100 podataka u sortiran red i ispisuje ih sortirane.
  2. Napišite procedure za ubacivanje nove stavke u sortiran stek, učitavanje sortiranog steka i program koji učitava 100 podataka u sortiran stek i ispisuje ih sortirane.

Ostavite komentar »

Nema komentara.

RSS feed for comments on this post. TrackBack URI

Ostavite odgovor

Popunite detalje ispod ili pritisnite na ikonicu da biste se prijavili:

WordPress.com logo

Komentarišet koristeći svoj WordPress.com nalog. Odjavite se / Promeni )

Slika na Tviteru

Komentarišet koristeći svoj Twitter nalog. Odjavite se / Promeni )

Fejsbukova fotografija

Komentarišet koristeći svoj Facebook nalog. Odjavite se / Promeni )

Google+ photo

Komentarišet koristeći svoj Google+ nalog. Odjavite se / Promeni )

Povezivanje sa %s

Create a free website or blog at WordPress.com.

%d bloggers like this: