sd_curs-04

Curs 4 coninut

Tipuri de date de nivel naltListe liniareListe liniare ordonateStivaCoada

Algoritmi i programare 1

Coada

Tipul abstract (LLin, LLinOrd, Stiva, Coada) Implementarea cu tablouri Implementarea cu liste simplu nlnuite

Aplicaie la conversii de expresii

Liste liniare - exemple

Studeni

(Adriana, George, Luiza, Maria, Daniel)

Examene

(Mate, Logica, SD, ACSO, ENG) (Mate, Logica, SD, ACSO, ENG)

Zile sptmnii

(L, M, Mi, J, V, S, D)

Lunile anului

(Ian, Feb, Mar, Apr, ..., Dec)

Algoritmi i programare 2

Tipul de date abstract LLin

Obiecte: L = (e0,, en-1), n 0

ei Elt (tipul abstract al elementelor)

Relaii:

Algoritmi si programare 3

Relaii: e0 primul element al listei

en-1 ultimul element al listei

ei elementul predecesor lui ei+1

LLin operaii

listaVida() intrare: nimic

iesire: L = () (lista cu zero elemente)

insereaza()


insereaza()intrare:

L = (e0,, en-1), k Nat, e Elt

iesire

L = (ek-1, e, ek,) daca 0 k n

eroare in caz contrar

LLin insereaza()- exemple

L = (a, b, c, d, e, f, g)

insereaza(L, 0, x) =>

L = (x, a, b, c, d, e, f, g)

(Obs.: Indexul elementelor a,...,g crete cu 1.)


insereaza(L, 2, x) => L = (a, b, x, c, d, e, f, g)

insereaza(L, 0, x) => L = (x, a, b, c, d, e, f, g)

insereaza(L, 10, x) => eroare

insereaza(L, -7, x) => eroare

LLin - operaii

elimina()

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

iesire


iesire L = (ek-1, ek+1) daca 0 k n-1


LLin elimina()- exemple

L = (a, b, c, d, e, f, g)

elimina(L, 2) =>

L = (a, b, d, e, f, g)

(Obs.: Indexul elementelor d,...,g descrete cu 1.)


elimina(L, 10) => eroare

elimina(L, -7) => eroare

LLin - operaii

alKlea()

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


L = (e0,, en-1), k Nat

iesire ek daca 0 k n-1


LLin alKlea()- exemple

L = (a, b, c, d, e, f, g)

alKlea(L, 0) => a

alKlea(L, 2) => c


alKlea(L, 6) => g

alKlea(L, 20) => eroare

alKlea(L, -2) => eroare

LLin - operaii

elimTotE()

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


iesire: lista L din care s-au eliminat toate

elementele egale cu e

LLin elimTotE()- exemple

L = (a, b, c, a, b, c, a)

elimTotE(L, a) => (b, c, b, c)


elimTotE(L, c) => (a, b, a, b, a)

elimTotE(L, d) => (a, b, c, a, b, c, a)

LLin - operaii

parcurge()

intrare: L = (e0,, en-1), o procedur (funcie) viziteaza()


0 n-1

viziteaza()

ieire: lista L n care toate elementele au fost

procesate aplicnd viziteaza()

LLin parcurge()- exemple

L = (1, 2, 3, 1, 2, 3)

parcurge(L, oriDoi() ) => (2, 4, 6, 2, 4, 6)


parcurge(L, incrementeaza()) => (2, 3, 4, 2, 3, 4)

LLin - operaii

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

LLin poz()- exemple

L = (a, b, c, a, b, c, d)

poz(L, a) => 0


poz(L, c) => 2

poz(L, d) => 6

poz(L, e) => -1

LLin - operaii

lung()

intrare: L = (e0,, en-1)

iesire: n lungimea listei L


n lungimea listei L

Exemplu:

L = (a, b, c, a, b, c, d)

lung(L) => 7

LLin: implementare cu tablouri

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

MAX-1

en-1L.tab Elt[MAX] e0

0

L.ultim Nat


L este o structur

un cmp de tip tablou L.tab pentru memorarea elementelor

un cmp L.ultim pentru memorarea poziiei ultimului element

Llin (implementare cu tablouri): operaii

insereaza()

deplaseaz elementele de pe poziiile k, k+1, la dreapta cu o poziie


insereaz e pe poziia k

excepii: k L.ultim+1 (n)

L.ultim = MAX-1

LLin (implementare cu tablouri): operaii

procedure insereaza(L, k, e)

begin

if (k < 0 or k > L.ultim+1)

then throw eroare-pozitie incorecta

if (L.ultim >= MAX-1)

then throw eroare-spatiu insuficient


then throw eroare-spatiu insuficient

for j L.ultim downto k do

L.tab[j+1] L.tab[j]

L.tab[k] e

L.ultim L.ultim + 1

end

timpul de executie: O(n)

LLin: implementare cu tablouri: operaii

parcurge()procedure parcurge(L, viziteaza())

begin

for i 0 to L.ultim do

viziteaza(L.tab[i])


viziteaza(L.tab[i])

end

dac viziteaza() proceseaz un element n O(1), atunci parcurge() proceseaz lista n O(n) (n este numrul elementelor listei)

L structur cu dou cmpuri

LLin: implementarea cu liste nlnuite

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

L.prim

e0 e1 en-1

L.ultim


L structur cu dou cmpuri

pointer la primul element

pointer la ultimul element

un nod *p (aflat la adresa din p) are dou cmpuri:

unul pentru memorarea informaiei: p->elt = ei unul pentru nodul succesor: p->succ


insereaza()parcurge elementele 0, 1,, k-1 insereaz un nou element dup k-1

creeaz nodul memoreaz informaii reface legturi


reface legturi

excepii lista vida k=0 k=n k n


ek-1

e

L.prim L.ultim

ek


e

e e0

L.prim

LLin : implementarea cu listenlnuite

procedure insereaza(L, k, e)begin

if (kelt eif (k = 0 or L.prim = NULL)then q->succ L.prim

L.prim q


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 eroare-pozitieincorecta

q->succ p->succ; p->succ q if (p = L.ultim) then L.ultim q

end

LLin: aplicaie

linie poligonal de puncte Punct: structur cu dou cmpuri x si y

crearea unei listeprocedure creeazaLista(L)

begin

L listaVida();


L listaVida();

/* citeste n */

for i 0 to n-1 do

/* citeste p.x, p.y */

insereaza(L, 0, p)

end

atenie: timpul de execuie depinde de implementare

LLin: aplicaie

multiplic cu 2 coordonatele unui punct

procedure ori2Punct(p)

begin

p.x p.x * 2

p.y p.y * 2

end


end

multiplic cu 2 coordonatele unei linii poligonale

procedure ori2Linie(L)

begin

parcurge(L, ori2Punct())

end

LLin: aplicaie

translateaz punct

procedure trPunct(p, dx, dy)

begin

p.x p.x + dx

p.y p.y + dy

end


end

translateaz linie poligonal

procedure trLinie(L, dx, dy)

begin

parcurge(L, trPunct())

end

Liste liniare ordonate: LLinOrd

obiecte L = (e0,, en-1), n 0, ei Elt, e0

Liste liniare ordonate: LLinOrd

elimina() intrare:

L = (e0,, en-1), e Elt

Iesire L = (ek-1, ek+1) daca e = ek eroare in caz contrar



alKlea()

parcurge()

poz()

LLinOrd: Implementare cu tablouri cutare binarfunction Poz(L, e)

begin

p 0; q L.ultim

m [(p+q)/2]

while(L.tab[m] != e && p < q) do

if (e < L.tab[m])


if (e < L.tab[m])

then q m 1

else p m + 1

m [(p+q)/2]

if (L.tab[m] = e)

then return m

else return -1;

end

LLinOrd: Complexitatea cutrii

implementare cu tablouri timpul de execuie O(logn)


implementarea cu liste nlnuite timpul de execuie O(n) (cutare liniar)

Tipul abstract Stiva

obiecte liste n care se cunoate vechimea

elementelor introduse (liste LIFO) operaii

stivaVida() intrare: nimic


intrare: nimic iesire

S=(), lista vida

push() intrare

S Stiva, e Elt

iesire S la care s-a adaugat e ca ultimul element

introdus (cel cu vechimea cea mai mic)


pop() intrare

S Stiva

iesire S din care s-a eliminat ultimul element introdus

(cel cu vechimea cea mai mic)

eroare dac S este vid



esteVida() intrare

S Stiva

iesire true dac S este vid

false dac S nu este vid


top() intrare

S Stiva

iesire ultimul element introdus (cel cu vechimea cea


ultimul element introdus (cel cu vechimea cea mai mic)


Stiva: implementarea cu liste liniare

push(S, e) = insereaza(S, 0, e)

pop(S) = elimina(S, 0)

top(S) = alKlea(S, 0)

sau


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 operaiilor


implementarea operaiilor push()

procedure push(S, e)

begin

if (S.virf = MAX-1)

then throw eroare

S.virf S.virf+1

S.tab[virf] e

end

Stiva: implementarea cu liste nlnuite

reprezentarea obiectelor

en-1

e

S


e0

en-2

.

.

.

Stiva: implementarea cu liste nlnuite

implementarea operaiilor push()

procedure push(S, e)

beginnew(q)

q->elt e

q->succ S


q->succ S

S q

end

pop()procedure pop(S)

beginif (S = NULL) then throw eroare

q S

S S->succ

delete(q)

end

Tipul abstract Coada

obiecte liste n care se cunoate vechimea

elementelor introduse (liste FIFO) operaii

coadaVida() intrare: nimic iesire


intrare: nimic iesire

lista vid

insereaza() intrare

C Coada, e Elt

iesire C la care s-a adugat e ca ultimul element

introdus (cel cu vechimea cea mai mic)


elimina() intrare

C Coada

iesire C din care s-a eliminat primul element introdus

(cel cu vechimea cea mai mare)

eroare dac C este vid



esteVida() intrare

C Coada

isesire true dac C este vid

false dac C nu este vid


citeste() intrare

C Coada

iesire primul element introdus (cel cu vechimea cea mai


primul element introdus (cel cu vechimea cea mai mare)


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)


citeste(C) = LLin.alKlea(C, 0)

p

Coada: implementarea cu tablouri


C Elt[nMax]

nMax-1

prim

ultimq

e0

en-1


pprim ultimq

C Elt[nMax]

nMax-1

ultim q

primp

en-1

e0

ei

Coada: implementarea cu tablouri

implementarea operaiilor insereaza()

procedure insereaza(C, e)

beginif ((ultim + 1) % nMax = prim)


if ((ultim + 1) % nMax = prim)

then throw error

ultim (ultim + 1) % nMax

C[ultim] e

end

Coada: implementarea cu liste nlnuite


prim


e0 e1 en-1

prim ultim

Coada: implementarea cu liste nlnuite

implementarea operaiilor insereaza()

procedure insereaza(C, e)

beginnew(q)

q->elt e


q->elt e

q->succ NULL

if (ultim = NULL)

then prim q

ultim q

else ultim->succ q

ultim q

end

Aplicatie: notatia postfixata a expresiilor

notatia infixataa + b

a + (b * 2)

notatia postfixataa b +

a b 2 * +


a b 2 * +

reguli de precedentaa + b * 2

reguli de asociere7 / 3 * 2

la stanga (7 / 3) * 2

la dreapta 7 / (3 * 2)

Translatarea infix -> postfixprocedure convInfix2Postfix(infix, postfix)

/* infix si postfix sunt cozi */

begin

S stivaVida()

while (not esteVida(infix)) do

citeste(infix, x); elimina(infix);

if (x este operand) then insereaza(postfix,x)

else if (x = ))then

while (top(s) () do

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



pop(S)

else

while (not estevida(S) and top(S)( and priorit(top(S))>=priorit(x)) do


push(S,x)

while (not estevida(S)) do


end

Translatarea infix -> postfixExemplu: a+b*(c+d)+e

(inf.tab Elt[MAX] a *b+ c d+ ) + e

+postf.tab Elt[MAX] a dcb * e+ +

x x


(

S (stiva)

+

*

+

+

Evaluarea 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) drp

push(S, val)

val = top(S); pop(S)

return val

end

c d

Translatarea infix -> postfixExemplu: abcd+*+e+

+postf.tab Elt[MAX] a b * e+ +

S (stiva)

x x


a

b

c

d

c+d

b*(c+d)

a+b*(c+d)

e

a+b*(c+d)+e

sd_curs-04

Documents