Dorel Lucanu Algoritmica si programare

Curs 2- Agenda

Tipuri de date de nivel inaltListe liniareListe liniare ordonateStivaCoada

tipul abstract (LLin, LLinOrd, Stiva, Coada)implementare cu tablouriimplementare cu liste simplu inlantuite

Aplicatie la conversii de expresii

Dorel Lucanu Algoritmica si programare

Liste liniare: tipul abstract LLinobiecte

L = (e0,…, en-1), n ≥ 0, ei ∈ Elt (tipul abstract al elementelor)

operatiilistaVida()

intrare: nimiciesire

() (lista cu zero elemente)insereaza()

intrare:L = (e0,…, en-1), k ∈ Nat, e ∈ Elt

iesireL = (…ek-1, e, ek,…) daca 0 ≤ k ≤ neroare in caz contrar

Dorel Lucanu Algoritmica si programare

LLin (continuare 1)elimina()

intrare:L = (e0,…, en-1), k ∈ Nat

IesireL = (…ek-1, ek+1…) daca 0 ≤ k ≤ n-1eroare in caz contrar

alKlea()intrare:

L = (e0,…, en-1), k ∈ NatIesire

ek daca 0 ≤ k ≤ n-1eroare in caz contrar

Dorel Lucanu Algoritmica si programare

LLin (continuare 2)poz()

intrare:L = (e0,…, en-1), e ∈ Elt

iesire:prima pozitie pe care apare e in L sau -1 daca e nu apare in L

parcurge()intrare:

L = (e0,…, en-1), o procedura (functie) viziteaza()iesire:

lista L in care toate elementele au fostprocesate aplicand viziteaza()

Dorel Lucanu Algoritmica si programare

LLin: implementare cu tablouri

reprezentarea obiectelor L = (e0,…, en-1)

L este o structuraun camp de tip tablou L.tab pentrumemorarea elementelorun camp L.ultim pentru memorarea pozitieiultimului element

MAX-1en-1L.tab Elt[MAX] e0 …

0

L.ultim Nat

Dorel Lucanu Algoritmica si programare

LLin: implementare cu tablouri: operatii

insereaza()deplaseaza elementele de pe pozitiile k, k+1, … la dreapta cu o pozitieinsereaza e pe pozitia kexceptii:

k L.ultim+1 (k > n)L.ultim = MAX

Dorel Lucanu Algoritmica si programare

LLin: implementare cu tablouri: operatii

procedure insereaza(L, k, e)if (k < 0 or k > L.ultim +1)

then throw “eroare”if (L.ultim >= MAX)

then throw “eroare”for j ← L.ultim downto k do

L.tab[j+1] ← L.tab[j]L.tab[k] ← eL.ultim ← L.ultim + 1

endtimpul de executie: O(n)

Dorel Lucanu Algoritmica si programare

LLin: implementare cu tablouri: operatii

parcurgeprocedure parcurge(L, viziteaza())

for i ←0 to L.ultim doviziteaza(L.tab[i])

enddaca viziteaza() proceseaza un element in O(1), atunci parcurge proceseaza lista in O(n)

Dorel Lucanu Algoritmica si programare

LLin: implementarea cu liste inlantuite

reprezentarea obiectelor L = (e0,…, en-1)

L.prim

e0 e1 en-1…

L.ultim

L structura cu doua campuripointer la primul elementpointer la ultimul element

un nod p are doua campuri: unul pentru memorarea informatiei: p->elt = eisi unul pentru nodul succesor: p->succ

Dorel Lucanu Algoritmica si programare

LLin: implementarea cu liste inlantuite

insereaza()parcurge elementele 0, 1,…, k-1insereaza un nou dupa k-1

creeaza nodulmemoreaza informatiireface legaturi

exceptiilista vidak=0k=nk n

Dorel Lucanu Algoritmica si programare

LLin: implementarea cu liste inlantuite

ek-1

e

L.prim L.ultim

e

e e0

L.prim

Dorel Lucanu Algoritmica si programare

LLin : implementarea cu liste inlantuite

procedure insereaza(L, k, e)if (kelt ← eif (k = 0 or L.prim = NULL)then q->succ ← L.prim

L.prim ← qif (L.ultim = NULL) then L.ultim ← q

else p ← L.prim; j ← 0while (jsucc; j ← j+1if (j < k-1) then throw “error”q->succ ← p->succ; p->succ ← q if (p = L.ultim) then L.ultim ← q

end

Dorel Lucanu Algoritmica si programare

LLin: aplicatie

linie poligonala de punctePunct structura cu doua campuri x si ycrearea unei liste

procedure creeazaLista(L)L ← listaVida();//citeste nfor i ← 0 to n-1 do//citeste p.x, p.yinsereaza(L, i, p)

endatentie: timpul de executie depinde de implementare

Dorel Lucanu Algoritmica si programare

LLin: aplicatie

multiplica cu 2 coordonatele unui punctprocedure ori2Punct(p)

p.x ← p.x * 2p.y ← p.y * 2

endmultiplica cu 2 coordonatele unei liniipoligonala

procedure ori2Linie(L)parcurge(L, ori2Punct())

end

Dorel Lucanu Algoritmica si programare

LLin: aplicatie

translateaza punctprocedure trPunct(p, dx, dy)

p.x ← p.x + dxp.y ← p.y + dy

endtranslateaza linie poligonala

procedure trLinie(L, dx, dy)parcurge(L, trPunct(), dx, dy)

end… totusi presupune modificarea proceduriiparcurge

Dorel Lucanu Algoritmica si programare

Liste liniare ordonate: LLinOrd

obiecteL = (e0,…, en-1), n ≥ 0, ei ∈ Elt, e0

Dorel Lucanu Algoritmica si programare

LLinOrd

elimina()intrare:

L = (e0,…, en-1), e ∈ EltIesire

L = (…ek-1, ek+1…) daca e = ekeroare in caz contrar

alKlea()parcurge()

Dorel Lucanu Algoritmica si programare

LLinOrd

poz() intrare:

L = (e0,…, en-1), e ∈ Eltiesire:

pozitia pe care apare e in L sau -1 daca e nu apare in L

…

Dorel Lucanu Algoritmica si programare

LLinOrd: implementarea cu tablouri

cautare binarafunction Poz(L, e)begin

p ← 0; q ← L.ultimm ← [(p+q)/2]while (L.tab[m] != e && p < q) do

if (e < L.tab[m])then q ← m-1else p ← m+1m ← [(p+q)/2]

if (L.tab[m] = e)then return melse return -1;

end

Dorel Lucanu Algoritmica si programare

LLinOrd: implementarea cu tablouri

cautare binaratimpul de executie O(log n)demonstratie:

Dorel Lucanu Algoritmica si programare

LLinOrd: implementarea cu liste inlantuite

cautare binara => cautare liniaratimpul de executie O(n) dar mai mic decatin cazul neordonat

Dorel Lucanu Algoritmica si programare

Tipul abstract Stivaobiecte

liste in care se cunoaste vechimeaelementelor introduse (liste LIFO)

operatiistivaVida()

intrare: nimiciesire

lista vidapush()

intrareS ∈ Stiva, e ∈ Elt

iesireS la care s-a adaugat e ca ultimulelement introdus (cel cu vechimeacea mai mica)

Dorel Lucanu Algoritmica si programare

Tipul abstract Stiva (continuare 1)pop()

intrareS ∈ Stiva

iesireS din care s-a eliminat ultimul element introdus (cel cu vechimea cea maimica)eroare daca S este vida

esteVida()intrare

S ∈ Stivaisesire

true daca S este vidafalse daca S nu este vida

Dorel Lucanu Algoritmica si programare

Tipul abstract Stiva (continuare 2)top()

intrareS ∈ Stiva

iesireultimul element introdus (cel cu vechimea cea mai mica)eroare daca S este vida

Dorel Lucanu Algoritmica si programare

Stiva: implementarea cu liste liniare

push(S, e) = insereaza(S, 0, e)pop(S) = elimina(S, 0)top(S) = alKlea(S, 0)

sau

push(S, e) = insereaza(S, lung(S), e)pop(S) = elimina(S, lung(S)-1)top(S) = alKlea(S, lung(S)-1)

Dorel Lucanu Algoritmica si programare

Stiva: implementarea cu tablouri

reprezentarea obiectelor

MAX-1

en-1S.tab Elt[MAX] e0…

0

S.virf n-1

implementarea operatiilorpush()procedure push(S, e)

if (S.virf = MAX-1)then throw “eroare”S.virf ← S.virf+1S.tab[virf] ← e

end

Dorel Lucanu Algoritmica si programare

Stiva: implementarea cu liste inlantuite

reprezentarea obiectelor

e0

en-1

en-2

...

S

Dorel Lucanu Algoritmica si programare

Stiva: implementarea cu liste inlantuite

implementarea operatiilorpush()procedure push(S, e)

new(q)q->elt ← eq->succ ← SS ← q

endpop()procedure pop(S)

if (S = NULL) then throw “eroare”q ← SS ← S->succdelete(q)

end

Dorel Lucanu Algoritmica si programare

Tipul abstract Coadaobiecte

liste in care se cunoaste vechimeaelementelor introduse (liste FIFO)

operatiicoadaVida()

intrare: nimiciesire

lista vidainsereaza()

intrareC ∈ Coada, e ∈ Elt

iesireC la care s-a adaugat e ca ultimulelement introdus (cel cu vechimeacea mai mica)

Dorel Lucanu Algoritmica si programare

Tipul abstract Coada (continuare 1)elimina()

intrareC ∈ Coada

iesireC din care s-a eliminat primul element introdus (cel cu vechimea cea maimare) eroare daca C este vida

esteVida()intrare

C ∈ Coadaisesire

true daca C este vidafalse daca C nu este vida

Dorel Lucanu Algoritmica si programare

Tipul abstract Coada (continuare 2)citeste()

intrareC ∈ Coada

iesireprimul element introdus (cel cu vechimea cea mai mare)eroare daca C este vida

Dorel Lucanu Algoritmica si programare

Coada: implementarea cu liste liniare

insereaza(C, e) = LLin.insereaza(C, lung(C), e)elimina(C) = LLin.elimina(C, 0)citeste(C) = LLin.alKlea(C, 0)

Dorel Lucanu Algoritmica si programare

Coada: implementarea cu tablouri

reprezentarea obiectelor

C.tab Elt[nMax] …MAX-1

C.prim p

… …

C.ultimq

e0 en-1

C.tab Elt[nMax] …MAX-1

C.ultim q

… …

C.primp

en-1 e0 ei

C are patru campuri: C.tab, C.prim, C.ultim, C.nrElem

Dorel Lucanu Algoritmica si programare

Coada: implementarea cu tablouri

implementarea operatiilorinsereaza()procedure insereaza(C, e)

if (C.nrElem = MAX-1) then throw “error”C.ultim ← (C.ultim + 1) % MAXC.tab[C.ultim] ← eC.nrElem ← C.nrElem + 1

end

Dorel Lucanu Algoritmica si programare

Coada: implementarea cu liste inlantuite

reprezentarea obiectelor

C.prim

e0 e1 en-1…

C.ultim

Dorel Lucanu Algoritmica si programare

Coada: implementarea cu liste inlantuite

implementarea operatiilorinsereaza()procedure insereaza(C, e)

new(q)q->elt ← eq->succ ← NULL if (C.ultim = NULL)then C.prim ← q

C.ultim ← qelse C.ultim->succ ← q

C.ultim ← qend

Dorel Lucanu Algoritmica si programare

Aplicatie: notatia postfixata a expresiilor

notatia infixataa + ba + (b * 2)notatia postfixataa b +b 2 * a +reguli de precedentaa + b * 2reguli de asociere7 / 3 * 2

la stanga (7 / 3) * 2la dreapta 7 / (3 * 2)

Dorel Lucanu Algoritmica si programare

Translatarea infix -> postfix

procedure convInfix2Postfix(infix, postfix)/* infix si postfix sunt cozi */begin

S ← stivaVida()while (!esteVida(infix)) do

citeste(infix, x); elimina(infix);if (x este operand) then insereaza(postfix,x)else if (x = ‘)’)then

while (top(s) ≠ ‘(‘) doinsereaza(postfix, top(S)); pop(S)

pop(S)else

while (priorit(top(S)) >= priorit(x)) doinsereaza(postfix, top(S)); pop(S)

push(S,x)while (!estevida(S)) do

insereaza(postfix, top(S)); pop(S)end

Dorel Lucanu Algoritmica si programare

Evaluare a expresiilor postfixate

function valPostfix(postfix)begin

S ← stivaVida()while (!esteVida(postfix)) do

citeste(postfix, x); elimina(postfix)if (x este operand)then push(S, x)else drp ← top(S); pop(S)

stg ← top(S); pop(S)val ← stg op(x) drppush(S, val)

val = top(S); pop(S)return val

end