bt_bb_section_bottom_section_coverage_image

Stek i red – zadaci

Zadatak 1

Napisati procedure za dodavanje elementa na početak jednostruko povezane liste, kao i za brisanje elementa sa početka. U glavnom programu učitati listu u obrnutom poretku, ispisati prvi i poslednji element liste i obrisati listu.

program zad1;
type pok =^slog;
    slog = record
            vrednost :integer;
            sledeci :pok;
            end;
            
procedure push(var vrh :pok; x :integer);
var p :pok;
begin
new(p);
p^.vrednost := x;
p^.sledeci := vrh;
vrh := p;
end;

procedure pop(var vrh :pok; var x :integer);
var p :pok;
begin
if vrh = nil then x := -1;
p := vrh;
x := vrh^.vrednost;
vrh := vrh^.sledeci;
dispose(p);
end;

var s :pok;
    x,n,i:integer;

begin
readln(n);
for i := 1 to n do
    begin
    readln(x);
    push(s, x);
    end;
for i := 1 to n do
    begin
    pop(s, x);
    if (i = 1) or (i = n) then
	    writeln(x);
    end;
end

Zadatak 2

Napisati proceduru za dodavanje elementa na kraj dvostruko povezane liste. U glavnom programu učitati jednu dvostruko povezanu listu, ispisati njene elemente i obrisati listu.

program zad2;
type pokelement = ^element;
    element = record
            vr :integer;
            sl :pokelement;
            pr :pokelement;
            end;
           
function dodaj(p :pokelement; n :integer) :pokelement;
var pom1, pom2 :pokelement;
begin
if p = nil then
    begin
    new(p);
    p^.vr := n;
    p^.sl := nil;
    p^.pr := nil;
    end
else
    begin
    pom1 := p;
    while pom1^.sl <> nil do
        begin
        pom2 := pom1;
        pom1 := pom1^.sl;
        end;
    new(pom1^.sl);
    pom1 := pom1^.sl;
    pom1^.vr := n;
    pom1^.sl := nil;
    pom1^.pr := pom2;
    end;
dodaj := p;
end;

procedure stampaj(p :pokelement);
var pom :pokelement;
begin
pom := p;
if p <> NIL then
	begin
	repeat
		write(pom^.vr,' ');
		pom:=pom^.sl;
	until pom = NIL;
	writeln;
	end
else
	writeln('Lista je prazna.');
writeln;
end;

var n,i,x:integer;
    glava:pokelement;
begin
glava := NIL;
writeln('Unesi broj elemenata u listi:');
readln(n);
for i:=1 to n do
	begin
	writeln('Unesi ',i,'. element:');
    readln(x);
	glava := dodaj(glava, x);
	end;
writeln('Unesite broj koji hocete da dodate na kraj liste: ');
read(x);
glava := dodaj(glava, x);
writeln('Kreirana lista je: ');
stampaj( glava );
end
Kako funkcioniše

1. Deklaracija funkcije

function dodaj(p: pokelement; n: integer): pokelement;
  • p: Pokazivač na prvi čvor liste. Ako je lista prazna, p je nil.
  • n: Vrednost tipa integer koju želimo da dodamo u listu.
  • Funkcija vraća pokazivač na prvi čvor liste nakon dodavanja novog elementa.

2. Deklaracija pomoćnih promenljivih

var pom1, pom2: pokelement;
  • pom1: Privremena promenljiva koja se koristi za iteraciju kroz listu.
  • pom2: Privremena promenljiva koja se koristi za čuvanje pokazivača na prethodni čvor tokom iteracije.

3. Provera da li je lista prazna

if p = nil then
begin
    new(p);
    p^.vr := n;
    p^.sl := nil;
    p^.pr := nil;
end
  • Ako je p = nil, lista je prazna:
    • Kreira se novi čvor pomoću new(p).
    • p^.vr := n: Dodeljuje se vrednost novog čvora.
    • p^.sl := nil i p^.pr := nil: Novi čvor nema ni sledeći ni prethodni element, jer je jedini u listi.

4. Ako lista nije prazna

else
begin
    pom1 := p;
    while pom1^.sl <> nil do
    begin
        pom2 := pom1;
        pom1 := pom1^.sl;
    end;
  • Ako lista nije prazna:
    • pom1 := p;: Iteracija kroz listu počinje od prvog čvora.
    • while pom1^.sl <> nil: Petlja ide do poslednjeg čvora (dok pom1^.sl nije nil).
    • pom2 := pom1;: pom2 čuva trenutni čvor kao prethodni čvor za budući novi element.

5. Dodavanje novog elementa na kraj liste

new(pom1^.sl);
pom1 := pom1^.sl;
pom1^.vr := n;
pom1^.sl := nil;
pom1^.pr := pom2;
  • new(pom1^.sl);: Kreira se novi čvor na kraju liste.
  • pom1 := pom1^.sl;: pom1 sada pokazuje na novokreirani čvor.
  • pom1^.vr := n;: Dodeljuje se vrednost novom čvoru.
  • pom1^.sl := nil;: Novi čvor nema sledeći element, jer je poslednji.
  • pom1^.pr := pom2;: Pokazivač na prethodni element postavlja se na poslednji čvor pre dodavanja.

6. Vraćanje pokazivača na početak liste

dodaj := p;
  • Funkcija vraća pokazivač na prvi čvor liste (p), koji nije promenjen.

image

Zadatak 3

Napisati program koji učitava niz karaktera koji se sastoji od otvorenih i zatvorenih, malih, srednjih i velikih zagrada i proverava da li su zagrade korektno zapisane u unetom nizu.

ideja je da kad naidje na otvorenu zagradu stavi je na vrh novog steka
a kad naidje na zatvorenu zagradu proverava da li je na vrhu otvorena zagrada koja odgovara toj, a ukoliko se to ne desi onda prekida proceduru i ispisuje nij
u slucaju da je to tacno brise tu zagradu iz steka
na kraju proverava da li je stek prazan jer ako nije onda je ostala zagrada koja nema svog para
program zad3;
type stek=^slog;
    slog=record 
        vr:char;
        sl:stek;
        end;

procedure pop(var vrh:stek);
var p:stek;
begin
if vrh=nil then
    exit;
p:=vrh;
vrh:=vrh^.sl;
dispose(p);
end;

procedure push(var vrh:stek; x :char);
var p:stek;
begin
new(p);
p^.vr:=x;
p^.sl:=vrh;
vrh:=p;
end; 

procedure TacneZagrade(str :string);
var noviStek :stek;
    x :char;
    i :integer;
begin
noviStek := nil;
for i := 1 to length(str) do 
    begin
    if (str[i] = '(') or (str[i] = '{') or (str[i] = '[') then
        push(noviStek, str[i])
    else
        if (str[i] = ')') or (str[i] = '}') or (str[i] = ']') then
            begin
            if (noviStek = nil) then
                begin
                writeln('Nije');
                exit;
                end;
            x := noviStek^.vr;
            pop(noviStek);
            if ((str[i] = ')') and (x <> '(')) or ((str[i] = '}') and (x <> '{')) or ((str[i] = ']') and (x <> '[')) then
                begin
                writeln('Nije');
                exit;
                end;
            end;
    end;
if noviStek = nil then
    writeln('Jeste')
else
    writeln('Nije');
end;

var str :string;
begin
readln(str);
TacneZagrade(str)
end.
Kako funkcioniše

1. Ulazni parametar

procedure TacneZagrade(str: string);
  • str: Ulazni string koji sadrži zagrade koje treba proveriti.

2. Deklaracija pomoćnih promenljivih

var noviStek: stek;
    x: char;
    i: integer;
  • noviStek: Pomoćni stek koji se koristi za praćenje otvarajućih zagrada.
  • x: Privremena promenljiva koja čuva vrednost skinutu sa steka.
  • i: Brojač za iteraciju kroz string.

3. Inicijalizacija steka

noviStek := nil;
  • Stek je inicijalno prazan jer još nisu obrađene zagrade.

4. Iteracija kroz string

for i := 1 to length(str) do
  • Iterira kroz svaki karakter u stringu str.

5. Provera otvarajućih zagrada

if (str[i] = '(') or (str[i] = '{') or (str[i] = '[') then
    push(noviStek, str[i]);
  • Ako je trenutni karakter otvarajuća zagrada (, {, ili [, dodaje se na stek pomoću funkcije push.

6. Provera zatvarajućih zagrada

if (str[i] = ')') or (str[i] = '}') or (str[i] = ']') the
  • Ako je trenutni karakter zatvarajuća zagrada ), }, ili ], radi se sledeće:
    • Provera da li je stek prazan
if (noviStek = nil) then
begin
    writeln('Nije');
    exit;
end;
      1. Ako je stek prazan, to znači da nema odgovarajuće otvarajuće zagrade, pa je string neispravan. Ispisuje Nije i završava izvršavanje.
    • Skidanje poslednje otvarajuće zagrade
x := noviStek^.vr;
pop(noviStek);
      1. Skida se poslednja otvarajuća zagrada sa steka pomoću pop i čuva se u promenljivoj x.
    • Provera da li se zagrade podudaraju
if ((str[i] = ')') and (x <> '(')) or ((str[i] = '}') and (x <> '{')) or ((str[i] = ']') and (x <> '[')) then
begin
    writeln('Nije');
    exit;
end;
    1. Proverava se da li se trenutna zatvarajuća zagrada str[i] podudara sa otvarajućom zagradom x:
      • ) mora da odgovara (.
      • } mora da odgovara {.
      • ] mora da odgovara [.
    2. Ako se ne podudaraju, string je neispravan. Ispisuje Nije i završava izvršavanje.

 

7. Provera steka nakon obrade svih zagrada

if noviStek = nil then
    writeln('Jeste')
else
    writeln('Nije');
  • Ako je stek prazan nakon obrade svih karaktera u stringu, sve otvarajuće zagrade su uparene i string je ispravan. Ispisuje Jeste.
  • Ako stek nije prazan, ostale su neparne otvarajuće zagrade, pa string nije ispravan. Ispisuje Nije.

image

Zadatak 4

Napisati proceduru za sortiranje elemenata jednostruko povezane liste u rastućem poretku. U glavnom programu učitati listu u obrnutom poretku, sortirati je, ispisati elemente sortirane liste i obrisati listu.

ideja je da napravimo novi stek gde smestamo elemente po sortiranom redosledu
da bi nam izbacivao u rastucem redosledu veci elementi moraju da idu na dno
da bi nam elementi isli na dno moramo sve prethodne elemente da vratimo u pocetni stek (ostace sortirani jer ih ubacujemo redom) i da kada naidjemo na elementi od kojeg trenutni nije veci smestimo taj element i krenemo da vracamo elemente iz starog steka onoliko puta koliko smo ih vratili nazad (tome sluzi brojac)
da bi sortirali u opadajucem poretku samo treba promeniti:
while (noviStek <> nil) and (x > noviStek^.vr) do u
while (noviStek <> nil) and (x < noviStek^.vr) do
program zad4;
type stek=^slog;
    slog=record 
        vr:integer;
        sl:stek;
        end;

procedure push(var vrh:stek; x :integer);
var p:stek;
begin
new(p);
p^.vr:=x;
p^.sl:=vrh;
vrh:=p;
end;

procedure pop(var vrh:stek; var x :integer);
var p:stek;
begin
if vrh=nil then
    begin
    x:=-1;
    exit;
    end;
p:=vrh;
x := vrh^.vr;
vrh:=vrh^.sl;
dispose(p);
end;

function sortiraj(vrh :stek) :stek;
var noviStek :stek;
    x, y, i, brojac :integer;
begin
noviStek := nil;
while vrh <> nil do
    begin
    pop(vrh, x);
    brojac := 0;
    while (noviStek <> nil) and (x > noviStek^.vr) do
        begin
        pop(noviStek, y);
        push(vrh, y);
        inc(brojac);
        end;
    push(noviStek, x);
    for i := 1 to brojac do
        begin
        pop(vrh, y);
        push(noviStek, y);
        end;
    end;
sortiraj := noviStek;
end;

var i, x, n :integer;
	s :stek;
begin
s:=nil;
readln(n);
for i := 1 to n do
    begin
    readln(x);
    push(s, x);
    end;
s := sortiraj(s);
writeln;
for i := 1 to n do
    begin
    pop(s, x);
    writeln(x);
    end;
end.
Kako funkcioniše

1. Deklaracija funkcije i promenljivih

function sortiraj(vrh: stek): stek;
var noviStek: stek;
    x, y, i, brojac: integer;
  • vrh: Pokazivač na prvi čvor početnog steka koji treba da bude sortiran.
  • noviStek: Pomoćni stek u koji će se postepeno smestiti sortirani elementi.
  • x, y: Privremene promenljive za skladištenje vrednosti tokom operacija sa stekom.
  • i, brojac: Brojači za iteraciju i praćenje broja pomerenih elemenata prilikom svakog ubacivanja elementa u noviStek.

2. Inicijalizacija pomoćnog steka

noviStek := nil;
  • noviStek je inicijalno prazan, jer će u njega biti smeštani sortirani elementi.

3. Glavna petlja (dokle god stek nije prazan)

while vrh <> nil do
begin
    pop(vrh, x);
    brojac := 0;
  • Ova petlja se ponavlja dokle god stek vrh nije prazan.
  • pop(vrh, x): Skida vrh steka vrh i smešta njegovu vrednost u promenljivu x.
  • brojac := 0;: Postavlja se brojčanik za praćenje broja pomerenih elemenata.

4. Unutrašnja petlja za premještanje elemenata u stek dok se ne nađe odgovarajuće mesto za x

while (noviStek <> nil) and (x > noviStek^.vr) do
begin
    pop(noviStek, y);
    push(vrh, y);
    inc(brojac);
end;
  • (noviStek <> nil) and (x > noviStek^.vr): Dokle god noviStek nije prazan i dok je trenutna vrednost x veća od vrha noviStek:
    • Skida se element y sa noviStek i smešta se u vrh.
    • inc(brojac): Povećava se brojčanik za pomerene elemente.
  • Ova petlja omogućava da se premeste svi elementi sa noviStek koji su manji od x u vrh, sve dok se ne nađe odgovarajuće mesto za x u noviStek.

5. Ubacivanje elementa x u noviStek

push(noviStek, x);
  • Nakon što je pronađeno odgovarajuće mesto, x se stavlja na vrh noviStek.

6. Vraćanje pomerenih elemenata nazad u noviStek

for i := 1 to brojac do
begin
    pop(vrh, y);
    push(noviStek, y);
end
  • Ova petlja vraća sve elemente koje smo prethodno premestili iz noviStek nazad u noviStek, čime se obezbeđuje da redosled elemenata bude očuvan, ali i dalje sortiran.

7. Vraćanje sortirane liste

sortiraj := noviStek;
  • Na kraju, funkcija vraća noviStek, koji sada sadrži sve elemente iz originalnog steka, ali sortirane.

image

Zadatak 6

Napisati funkciju koja izračunava zbir elemenata na parnim pozicijama date linearne liste. U glavnom programu, učitati elemente liste (u obrnutom poretku) ispisati zbir elemenata na parnim pozicijama i obrisati listu.

program zad6č
type stek=^slog;
    slog=record 
        vr:integer;
        sl:stek;
        end;

procedure push(var vrh:stek; x :integer);
var p:stek;
begin
new(p);
p^.vr:=x;
p^.sl:=vrh;
vrh:=p;
end;

procedure pop(var vrh:stek; var x :integer);
var p:stek;
begin
if vrh=nil then
    begin
    x:=-1;
    exit;
    end;
p:=vrh;
x := vrh^.vr;
vrh:=vrh^.sl;
dispose(p);
end;

procedure zbirParnih(var s :stek; n :integer);
var zbir, x, i :integer;
begin
zbir := 0;
for i := 1 to n do
    begin
    pop(s, x);
    if i mod 2 = 0 then
        zbir := zbir + x;
    end;
writeln(zbir);
end;

var i, x, n :integer;
	s :stek;
begin
s:=nil;
readln(n);
for i := 1 to n do
    begin
    readln(x);
    push(s, x);
    end;
zbirParnih(s, n);
end.
Kako funkcioniše

1. Inicijalizacija promenljivih

zbir := 0;
  • zbir je promenljiva koja čuva zbir parnih brojeva na parnim pozicijama.

2. Prolazak kroz stek

i := 1 to n do
begin
    pop(s, x);
    if i mod 2 = 0 then
        zbir := zbir + x;
end;
  • for i := 1 to n do: Petlja se pokreće n puta, gde n označava broj elemenata koje treba obraditi u steku.
  • pop(s, x): Funkcija pop uklanja gornji element iz steka s i dodeljuje njegovu vrednost promenljivoj x.
  • if i mod 2 = 0 then zbir := zbir + x;: Ako je pozicija i parna (kroz uslov i mod 2 = 0), vrednost x (koja predstavlja element sa steka) se dodaje u zbir.

3. Ispis rezultata

writeln(zbir);
  • Na kraju, writeln(zbir) ispisuje zbir parnih brojeva sa parnih pozicija.

image

Zadatak 7

Napisati funkciju koja izbacuje sve elemente liste koji su prosti brojevi.

program zad7;
type stek=^slog;
    slog=record 
        vr:integer;
        sl:stek;
        end;

function prostBroj(x :integer) :boolean;
var i :integer;
begin
if x <= 1 then
    begin
    prostBroj := False;
    exit;
    end;
for i := 2 to x-1 do
    begin
    if x mod i = 0 then
        begin
        prostBroj := False;
        exit;
        end;
    end;
prostBroj := True;
end;

procedure push(var vrh:stek; x :integer);
var p:stek;
begin
new(p);
p^.vr:=x;
p^.sl:=vrh;
vrh:=p;
end;

procedure pop(var vrh:stek; var x :integer);
var p:stek;
begin
if vrh=nil then
    begin
    x:=-1;
    exit;
    end;
p:=vrh;
x := vrh^.vr;
vrh:=vrh^.sl;
dispose(p);
end;

function izabciProste(var s :stek; n :integer) :stek;
var i, x :integer;
    r :boolean;
    stekBezProstih :stek;
begin
stekBezProstih := nil;
for i := 1 to n do
    begin
    pop(s, x);
    r := prostBroj(x);
    if r = False then
        push(stekBezProstih, x)
    end;
izabciProste := stekBezProstih;
end;

var i, x, n :integer;
	s :stek;
begin
s:=nil;
readln(n);
for i := 1 to n do
    begin
    readln(x);
    push(s, x);
    end;
s := izabciProste(s, n);
while s <> nil do
    begin
    pop(s, x);
    writeln(x);
    end;
end.
Kako funkcioniše

1. Inicijalizacija

stekBezProstih := nil;
  • stekBezProstih: Novi stek u koji ćemo smeštati sve brojeve koji nisu prosti.

2. Petlja za prolazak kroz stek

for i := 1 to n do
begin
    pop(s, x);
    r := prostBroj(x);
    if r = False then
        push(stekBezProstih, x);
end;
  • for i := 1 to n do: Petlja prolazi kroz sve elemente steka. n označava ukupan broj elemenata u steku.
  • pop(s, x): Skidamo element sa vrha originalnog steka s i smeštamo njegovu vrednost u promenljivu x.
  • r := prostBroj(x): Poziv funkcije prostBroj, koja proverava da li je broj x prost. Rezultat je logička vrednost: True (prost broj) ili False (nije prost).
  • if r = False then push(stekBezProstih, x);: Ako broj x nije prost, dodajemo ga u novi stek stekBezProstih.

3. Vraćanje rezultata

izabciProste := stekBezProstih;
  • Na kraju, funkcija vraća stekBezProstih, koji sadrži samo neproste brojeve.

image

Zadatak 8

Napisati funkciju koja testerasto uređuje datu linearnu listu.

(Testerasto uređivanje linearne liste podrazumeva transformaciju elemenata liste tako da se raspoređuju u obrascu “manje-veće-manje-veće” ili “veće-manje-veće-manje”)

Prolazi kroz elemente liste po indeksima.
Ako si na neparnom mestu u listi (prvi, treći, peti element itd.):
Proveri da li je trenutni broj manji od prethodnog. Ako jeste, zameni mesta ta dva broja.
Ako si na parnom mestu u listi (drugi, četvrti, šesti element itd.):
Proveri da li je trenutni broj veći od prethodnog. Ako jeste, zameni mesta ta dva broja.
program zad8;
type pokelement = ^element;
    element = record
            vr :integer;
            sl :pokelement;
            pr :pokelement;
            end;
           
function dodaj(p :pokelement; n :integer) :pokelement;
var pom1, pom2 :pokelement;
begin
if p = nil then
    begin
    new(p);
    p^.vr := n;
    p^.sl := nil;
    p^.pr := nil;
    end
else
    begin
    pom1 := p;
    while pom1^.sl <> nil do
        begin
        pom2 := pom1;
        pom1 := pom1^.sl;
        end;
    new(pom1^.sl);
    pom1 := pom1^.sl;
    pom1^.vr := n;
    pom1^.sl := nil;
    pom1^.pr := pom2;
    end;
dodaj := p;
end;

function napraviTesterasto(p: pokelement): pokelement;
var pom: pokelement;
    index, pomVrednost: integer;
begin
if p = nil then
    begin
    napraviTesterasto := nil;
    Exit;
    end;
pom := p;
index := 0;
while pom^.sl <> nil do
    begin
    if (index mod 2 = 0) and (pom^.vr > pom^.sl^.vr) then
        begin
        pomVrednost := pom^.vr;
        pom^.vr := pom^.sl^.vr;
        pom^.sl^.vr := pomVrednost;
        end
    else
        if (index mod 2 = 1) and (pom^.vr < pom^.sl^.vr) then
            begin
            pomVrednost := pom^.vr;
            pom^.vr := pom^.sl^.vr;
            pom^.sl^.vr := pomVrednost;
            end;
    pom := pom^.sl;
    inc(index);
    end;
napraviTesterasto := p;
end;

procedure stampaj(p :pokelement);
var pom :pokelement;
begin
pom := p;
if p <> NIL then
	begin
	repeat
		write(pom^.vr,' ');
		pom:=pom^.sl;
	until pom = NIL;
	writeln;
	end
else
	writeln('Lista je prazna.');
writeln;
end;

var n,i,x:integer;
    glava:pokelement;
begin
glava := NIL;
writeln('Unesi broj elemenata u listi:');
readln(n);
for i:=1 to n do
	begin
	writeln('Unesi ',i,'. element:');
    readln(x);
	glava := dodaj(glava, x);
	end;
glava := napraviTesterasto(glava);
writeln('Kreirana lista je: ');
stampaj( glava );
end.
Kako funkcioniše

1. Prazna lista

if p = nil then
begin
    napraviTesterasto := nil;
    Exit;
end;
  • Ako je ulazna lista prazna (p = nil), funkcija odmah vraća nil, jer nema elemenata za preuređivanje.

2. Inicijalizacija promenljivih

pom := p;
index := 0;
  • pom pokazuje na trenutni element liste tokom prolaska kroz listu.
  • index prati indeks trenutnog elementa (paran ili neparan).

3. Prolazak kroz listu

while pom^.sl <> nil do
begin
    ...
    pom := pom^.sl;
    inc(index);
end;
  • Petlja se izvršava dok postoji sledeći element u listi (pom^.sl <> nil).
  • Na kraju svake iteracije, prelazimo na sledeći element u listi (pom := pom^.sl) i povećavamo indeks (inc(index)).

4. Provera i zamena vrednosti

Unutar petlje se proverava da li trenutni i sledeći element ispunjavaju uslove za “testerasti” niz.

Za parne pozicije (index mod 2 = 0):

if (index mod 2 = 0) and (pom^.vr > pom^.sl^.vr) then
begin
    pomVrednost := pom^.vr;
    pom^.vr := pom^.sl^.vr;
    pom^.sl^.vr := pomVrednost;
end;
  • Ako je trenutni indeks paran (index mod 2 = 0) i trenutna vrednost (pom^.vr) veća od sledeće vrednosti (pom^.sl^.vr), zamene se vrednosti ova dva elementa.

Za neparne pozicije (index mod 2 = 1):

if (index mod 2 = 1) and (pom^.vr < pom^.sl^.vr) then
begin
    pomVrednost := pom^.vr;
    pom^.vr := pom^.sl^.vr;
    pom^.sl^.vr := pomVrednost;
end;
  • Ako je trenutni indeks neparan (index mod 2 = 1) i trenutna vrednost (pom^.vr) manja od sledeće vrednosti (pom^.sl^.vr), vrednosti se zamene.

5. Vraćanje rezultata

napraviTesterasto := p;
  • Na kraju funkcija vraća pokazivač na početak liste, koja je sada preuređena u “testerasti” niz.

image

Sortiranje dvostruko povezane liste

program SortirajListu;
type pokelement =^element;
    element = record
            podatak :integer;
            sledeci, pr :pokelement;
            end;

function dodaj(p :pokelement; n :integer) :pokelement;
var pom1, pom2 :pokelement;
begin
if p = nil then
    begin
    new(p);
    p^.podatak := n;
    p^.sledeci := nil;
    p^.pr := nil;
    end
else
    begin
    pom1 := p;
    while pom1^.sledeci <> nil do
        begin
        pom2 := pom1;
        pom1 := pom1^.sledeci;
        end;
    new(pom1^.sledeci);
    pom1 := pom1^.sledeci;
    pom1^.podatak := n;
    pom1^.sledeci := nil;
    pom1^.pr := pom2;
    end;
dodaj := p;
end;

procedure stampaj_listu( p:pokelement );
var pom:pokelement;
begin
pom := p;
if p <> NIL then
	begin
	repeat
		write(pom^.podatak,' ');
	    pom:=pom^.sledeci;
	until pom = NIL;
	writeln;
	end
else
	writeln('Lista je prazna.');
writeln;
end;

function sortirajListu(p: pokelement): pokelement;
var sortirano, trenutni, novi: pokelement;
begin
sortirano := NIL;
while p <> NIL do
    begin
    novi := p;
    p := p^.sledeci;
    if (sortirano = NIL) or (novi^.podatak <= sortirano^.podatak) then
        begin
        novi^.sledeci := sortirano;
        novi^.pr := nil;
        sortirano := novi;
        end
    else
        begin
        trenutni := sortirano;
        while (trenutni^.sledeci <> NIL) and (trenutni^.sledeci^.podatak < novi^.podatak) do
            trenutni := trenutni^.sledeci;
        novi^.sledeci := trenutni^.sledeci;
        novi^.pr := trenutni;
        trenutni^.sledeci := novi;
        end;
    end;
sortirajListu := sortirano;
end;

var x, i, n :integer;
    glava :pokelement;
    
begin
glava := nil;
writeln('Unesi broj elemenata u listi:');
readln(n);
for i:=1 to n do
		begin
		writeln('Unesi ',i,'. element:');
    readln(x);
		glava := dodaj(glava, x);
		end;
writeln('Kreirana lista pre sortiranja je:');
stampaj_listu( glava );
writeln;
glava := sortirajListu(glava);
writeln('Kreirana lista posle sortiranja je:');
stampaj_listu(glava);
end.
Kako funkcioniše

1. Inicijalizacija nove sortirane liste

sortirano := NIL;
  • Kreira se prazna lista sortirano u koju će se dodavati elementi ulazne liste p, sortirani po veličini.

2. Prolazak kroz ulaznu listu

while p <> NIL do
  • Petlja prolazi kroz sve elemente ulazne liste p.
  • Svaki element se uklanja iz ulazne liste i premešta u odgovarajuću poziciju u sortiranoj listi.

3. Premeštanje trenutnog elementa

novi := p;
p := p^.sledeci;
  • novi je trenutni element liste koji se trenutno obrađuje.
  • Uklanja se iz ulazne liste tako što se pokazivač p preusmeri na sledeći element.

4. Dodavanje elementa u sortiranu listu

Postoje dva slučaja za dodavanje elementa:

a) Dodavanje elementa na početak sortirane liste

if (sortirano = NIL) or (novi^.podatak <= sortirano^.podatak) then
begin
    novi^.sledeci := sortirano;
    novi^.pr := nil;
    sortirano := novi;
end;
  • Ako je lista sortirano prazna (sortirano = NIL) ili je vrednost trenutnog elementa novi^.podatak manja ili jednaka vrednosti prvog elementa sortirane liste (sortirano^.podatak), element se dodaje na početak.
  • Podešavanja:
    • novi^.sledeci pokazuje na trenutni prvi element liste sortirano.
    • novi^.pr se postavlja na nil, jer je element na početku.
    • sortirano sada pokazuje na novi, jer je on postao prvi element.

b) Dodavanje elementa na odgovarajuću poziciju u sredini ili na kraju

trenutni := sortirano;
while (trenutni^.sledeci <> NIL) and (trenutni^.sledeci^.podatak < novi^.podatak) do
    trenutni := trenutni^.sledeci;
novi^.sledeci := trenutni^.sledeci;
novi^.pr := trenutni;
trenutni^.sledeci := novi;
  • Ako novi ne ide na početak, traži se odgovarajuća pozicija u sortiranoj listi:
    1. Pokazivač trenutni započinje od početka liste sortirano.
    2. Petlja traži mesto gde vrednost trenutnog sledećeg elementa (trenutni^.sledeci^.podatak) postaje veća ili jednaka vrednosti novi^.podatak.
  • Kada se pronađe odgovarajuće mesto:
    • novi^.sledeci pokazuje na trenutnog sledećeg elementa (trenutni^.sledeci).
    • novi^.pr pokazuje na trenutni element (trenutni).
    • trenutni^.sledeci pokazuje na novi, umetnuvši ga na odgovarajuće mesto.

5. Vraćanje sortirane liste

sortirajListu := sortirano;
  • Nakon obrade svih elemenata, funkcija vraća pokazivač na početak sortirane liste.
0 komentara

Komentariši