Curs 2- Agenda - Alexandru Ioan Cuza UniversityCurs 2- Agenda Tipuri de date de nivel inalt Liste...

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


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


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


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()


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


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



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)



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)


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



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

creeaza nodulmemoreaza informatiireface legaturi

exceptiilista vidak=0k=nk n



ek-1

e

L.prim L.ultim

e

e e0

L.prim


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


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


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


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


Liste liniare ordonate: LLinOrd

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


LLinOrd

elimina()intrare:

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

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

alKlea()parcurge()


LLinOrd

poz() intrare:

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

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

…


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


LLinOrd: implementarea cu tablouri

cautare binaratimpul de executie O(log n)demonstratie:


LLinOrd: implementarea cu liste inlantuite

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


Tipul abstract Stivaobiecte

liste in care se cunoaste vechimeaelementelor introduse (liste LIFO)

operatiistivaVida()


lista vidapush()

intrareS ∈ Stiva, e ∈ Elt

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


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


Tipul abstract Stiva (continuare 2)top()

intrareS ∈ Stiva

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


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)


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


Stiva: implementarea cu liste inlantuite


e0

en-1

en-2

...

S


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


Tipul abstract Coadaobiecte

liste in care se cunoaste vechimeaelementelor introduse (liste FIFO)

operatiicoadaVida()


lista vidainsereaza()

intrareC ∈ Coada, e ∈ Elt

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


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


Tipul abstract Coada (continuare 2)citeste()

intrareC ∈ Coada

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


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)


Coada: implementarea cu tablouri


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


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


Coada: implementarea cu liste inlantuite


C.prim

e0 e1 en-1…

C.ultim


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


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)


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


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

Curs 2- Agenda - Alexandru Ioan Cuza UniversityCurs 2- Agenda Tipuri de date de nivel inalt Liste...

Documents

Transcript of Curs 2- Agenda - Alexandru Ioan Cuza UniversityCurs 2- Agenda Tipuri de date de nivel inalt Liste...