Liste. Stive. Cozi

SD 2019/2020

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 2 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 3 / 58

Liste liniare – exemple

I Student, iI (Adriana, George, Luiza, Maria, Daniel)

I ExameneI (Mate, Logica, SD, ACSO, IP, ENG)

I Zilele saptamaniiI (L, M, Mi, J, V, S, D)

I Lunile anuluiI (Ian, Feb, Mar, Apr, Mai, Iun, Iul, Aug, Sep, Oct, Nov, Dec)

FII, UAIC Curs 4 SD 2019/2020 4 / 58

Tipul abstract LLin

I Obiecte: L = (e0, · · · , en−1), n ≥ 0

I ei ∈ Elt (tipul abstract al elementelor)

I Relat, ii:– e0 primul element al listei;– en−1 ultimul element al listei;– ei elementul predecesor lui ei+1.

FII, UAIC Curs 4 SD 2019/2020 5 / 58

LLin – operat, ii

I listaVida()I intrare: nimic

I ies, ire: L = () (lista cu zero elemente)

I insereaza()I intrare:

I L = (e0, · · · , en−1), k ∈ Nat, e ∈ Elt

I ies, ire:I L = (· · · , ek−1, e, ek , · · · ), daca 0 ≤ k ≤ nI eroare ın caz contrar

FII, UAIC Curs 4 SD 2019/2020 6 / 58

insereaza() – exemple

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

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

Obs. indexul elementelor a, · · · , g cres, te cu 1.

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

I insereaza(L, 7, x) ⇒ L = (a, b, c , d , e, f , g , x)

I insereaza(L, 10, x) ⇒ eroare

I insereaza(L,−7, x) ⇒ eroare

FII, UAIC Curs 4 SD 2019/2020 7 / 58

LLin – operat, ii

I elimina()I intrare:

I L = (e0, · · · , en−1), k ∈ Nat

I ies, ire:I L = (· · · , ek−1, ek+1, · · · ), daca 0 ≤ k ≤ n − 1I eroare ın caz contrar

Exemple:

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

I elimina(L, 2) ⇒ L = (a, b, d , e, f , g)Obs. indexul elementelor d , · · · , g descres, te cu 1.

I elimina(L, 10) ⇒ eroare

I elimina(L,−7) ⇒ eroare

FII, UAIC Curs 4 SD 2019/2020 8 / 58

LLin – operat, ii

I elimina()I intrare:

I L = (e0, · · · , en−1), k ∈ Nat

I ies, ire:I L = (· · · , ek−1, ek+1, · · · ), daca 0 ≤ k ≤ n − 1I eroare ın caz contrar

Exemple:

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

I elimina(L, 2) ⇒ L = (a, b, d , e, f , g)Obs. indexul elementelor d , · · · , g descres, te cu 1.

I elimina(L, 10) ⇒ eroare

I elimina(L,−7) ⇒ eroare

FII, UAIC Curs 4 SD 2019/2020 8 / 58

LLin – operat, ii

I alKlea()I intrare:

I L = (e0, · · · , en−1), k ∈ Nat

I ies, ire:I ek , daca 0 ≤ k ≤ n − 1I eroare ın caz contrar

Exemple:

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

I alKlea(L, 0) ⇒ a

I alKlea(L, 2) ⇒ c

I alKlea(L, 6) ⇒ g

I alKlea(L, 20) ⇒ eroare

I alKlea(L,−2) ⇒ eroare

FII, UAIC Curs 4 SD 2019/2020 9 / 58

LLin – operat, ii

I alKlea()I intrare:

I L = (e0, · · · , en−1), k ∈ Nat

I ies, ire:I ek , daca 0 ≤ k ≤ n − 1I eroare ın caz contrar

Exemple:

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

I alKlea(L, 0) ⇒ a

I alKlea(L, 2) ⇒ c

I alKlea(L, 6) ⇒ g

I alKlea(L, 20) ⇒ eroare

I alKlea(L,−2) ⇒ eroare

FII, UAIC Curs 4 SD 2019/2020 9 / 58

LLin – operat, ii

I elimTotE()I intrare:

I L = (e0, · · · , en−1), e ∈ Elt

I ies, ire:I lista L din care s-au eliminat toate elementele egale cu e

Exemple:

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

I elimTotE(L, a) ⇒ (b, c , b, c)

I elimTotE(L, c) ⇒ (a, b, a, b, a)

I elimTotE(L, d) ⇒ (a, b, c , a, b, c , a)

FII, UAIC Curs 4 SD 2019/2020 10 / 58

LLin – operat, ii

I elimTotE()I intrare:

I L = (e0, · · · , en−1), e ∈ Elt

I ies, ire:I lista L din care s-au eliminat toate elementele egale cu e

Exemple:

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

I elimTotE(L, a) ⇒ (b, c , b, c)

I elimTotE(L, c) ⇒ (a, b, a, b, a)

I elimTotE(L, d) ⇒ (a, b, c , a, b, c , a)

FII, UAIC Curs 4 SD 2019/2020 10 / 58

LLin – operat, ii

I parcurge()I intrare:

I L = (e0, · · · , en−1), o procedura / funct, ie viziteaza()

I ies, ire:I lista L ın care toate elementele au fost procesate aplicand viziteaza()

Exemple:

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

I parcurge(L, oriDoi()) ⇒ (2, 4, 6, 2, 4, 6)

I parcurge(L, incrementeaza()) ⇒ (2, 3, 4, 2, 3, 4)

FII, UAIC Curs 4 SD 2019/2020 11 / 58

LLin – operat, ii

I parcurge()I intrare:

I L = (e0, · · · , en−1), o procedura / funct, ie viziteaza()

I ies, ire:I lista L ın care toate elementele au fost procesate aplicand viziteaza()

Exemple:

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

I parcurge(L, oriDoi()) ⇒ (2, 4, 6, 2, 4, 6)

I parcurge(L, incrementeaza()) ⇒ (2, 3, 4, 2, 3, 4)

FII, UAIC Curs 4 SD 2019/2020 11 / 58

LLin – operat, ii

I poz()I intrare:

I L = (e0, · · · , en−1), e ∈ Elt,

I ies, ire:I prima pozit, ie pe care apare e ın L sauI −1 daca e nu apare ın L.

Exemple:

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

I poz(L, a) ⇒ 0

I poz(L, c) ⇒ 2

I poz(L, d) ⇒ 6

I poz(L, x) ⇒ −1

FII, UAIC Curs 4 SD 2019/2020 12 / 58

LLin – operat, ii

I poz()I intrare:

I L = (e0, · · · , en−1), e ∈ Elt,

I ies, ire:I prima pozit, ie pe care apare e ın L sauI −1 daca e nu apare ın L.

Exemple:

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

I poz(L, a) ⇒ 0

I poz(L, c) ⇒ 2

I poz(L, d) ⇒ 6

I poz(L, x) ⇒ −1

FII, UAIC Curs 4 SD 2019/2020 12 / 58

LLin – operat, ii

I lung()I intrare:

I L = (e0, · · · , en−1),

I ies, ire:I n – lungimea listei L.

Exemple:

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

I lung(L) ⇒ 7

FII, UAIC Curs 4 SD 2019/2020 13 / 58

LLin – operat, ii

I lung()I intrare:

I L = (e0, · · · , en−1),

I ies, ire:I n – lungimea listei L.

Exemple:

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

I lung(L) ⇒ 7

FII, UAIC Curs 4 SD 2019/2020 13 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 14 / 58

LLin – implementarea cu tablouri

I Reprezentarea obiectelor L = (e0, · · · , en−1)

L.tab Elt[Max] e0 . . . en−1

Max-1

L.ultim int

I L este o structuraI L.tab – un camp de tip tablou pentru memorarea elementelor;

I L.ultim – un camp pentru memorarea pozit, iei ultimului element.

FII, UAIC Curs 4 SD 2019/2020 15 / 58

LLin – implementarea cu tablouri

I insereaza()

I deplaseaza elementele de pe pozitiile k , k + 1, . . . la dreapta cu opozitie;

I insereaza e pe pozitia k ;

I exceptii:I k < 0, k > L.ultim + 1 (n)

I L.ultim = Max − 1.

FII, UAIC Curs 4 SD 2019/2020 16 / 58

LLin – implementarea cu tablouri

procedure insereaza(L, k , e)begin

if (k < 0 or k > L.ultim + 1) thenthrow “eroare-pozitie incorecta”

if (L.ultim >= Max − 1) thenthrow “eroare-spatiu insuficient”

for j ← L.ultim downto k doL.tab[j + 1]← L.tab[j ]

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

end

I Timpul de execut, ie: O(n).

FII, UAIC Curs 4 SD 2019/2020 17 / 58

LLin – implementarea cu tablouri

I parcurge()

procedure parcurge(L, viziteaza())begin

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

end

I Daca viziteaza() proceseaza un element ın O(1), atunci parcurge()proceseaza lista ın O(n) (n este numarul elementelor listei).

FII, UAIC Curs 4 SD 2019/2020 18 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 19 / 58

LLin – implementarea cu structuri ınlant,uite

I Reprezentarea obiectelor L = (e0, · · · , en−1)

L.prim • L.ultim •

e0 • e1 • . . . en−1 •

I L este o structura cu doua campuriI L.prim – pointer la primul element al listei;

I L.ultim – pointer la ultimul element al listei.

I un nod * p (aflat la adresa din p) are doua campuri:I p− > elt(= ei ) – memoreaza informat, ia utila din nod;

I p− > succ – memoreaza adresa nodului succesor.

FII, UAIC Curs 4 SD 2019/2020 20 / 58

LLin – implementarea cu structuri ınlant,uite

I insereaza()

I parcurge elementele de pe pozit, iile 0, 1, . . . , k − 1;

I insereaza un nou element dupa pozitia k − 1;I creeaza noul nod;

I memoreaza informat, ii;

I reface legaturi.

I exceptii:I lista vida;

I k = 0;

I k = n;

I k < 0, k > n.

FII, UAIC Curs 4 SD 2019/2020 21 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul general

ek−1 • ek •

e •

FII, UAIC Curs 4 SD 2019/2020 22 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul general

ek−1 • ek •

e •

FII, UAIC Curs 4 SD 2019/2020 22 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul general

ek−1 • ek •

e

•

FII, UAIC Curs 4 SD 2019/2020 22 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul general

ek−1 • ek •

e •

FII, UAIC Curs 4 SD 2019/2020 22 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul general

ek−1 • ek •

e •

FII, UAIC Curs 4 SD 2019/2020 22 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: lista vida

L.prim • L.ultim •

e •

FII, UAIC Curs 4 SD 2019/2020 23 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: lista vida

L.prim • L.ultim •

e •

FII, UAIC Curs 4 SD 2019/2020 23 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: lista vida

L.prim • L.ultim •

e

•

FII, UAIC Curs 4 SD 2019/2020 23 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: lista vida

L.prim • L.ultim •

e •

FII, UAIC Curs 4 SD 2019/2020 23 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: lista vida

L.prim • L.ultim •

e •

FII, UAIC Curs 4 SD 2019/2020 23 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: inserarea la ınceputul listei

L.prim •

e0 •

e •

FII, UAIC Curs 4 SD 2019/2020 24 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: inserarea la ınceputul listei

L.prim •

e0 •

e •

FII, UAIC Curs 4 SD 2019/2020 24 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: inserarea la ınceputul listei

L.prim •

e0 •e

•

FII, UAIC Curs 4 SD 2019/2020 24 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: inserarea la ınceputul listei

L.prim •

e0 •e •

FII, UAIC Curs 4 SD 2019/2020 24 / 58

LLin – implementarea cu structuri ınlant,uite

I Cazul particular: inserarea la ınceputul listei

L.prim •

e0 •e •

FII, UAIC Curs 4 SD 2019/2020 24 / 58

LLin – implementarea cu structuri ınlant,uite

procedure insereaza(L, k, e)begin

if (k < 0) thenthrow “eroare-pozitie incorecta”

new(q); q− > elt ← eif (k == 0 or L.prim == NULL) then

q− > succ ← L.prim; L.prim← qif (L.ultim == NULL) then

L.ultim← qelse

p ← L.prim; j ← 0while (j < k − 1 and p! = L.ultim) do

p ← p− > succ ; j ← j + 1if (j < k − 1) then

throw “eroare-pozitie incorecta”q− > succ ← p− > succ ; p− > succ ← qif (p == L.ultim) then

L.ultim← qend

FII, UAIC Curs 4 SD 2019/2020 25 / 58

LLin – aplicat, ie

I Linie poligonala de puncte.I Punct: structura cu doua campuri x s, i y ;

I crearea unei liste

procedure creeazaLista(L)begin

L← listaVida()/* citeste n */

for i ← 0 to n − 1 do/* citeste p.x, p.y */

insereaza(L, 0, p)end

I Obs. Timpul de execut, ie depinde de implementare.

FII, UAIC Curs 4 SD 2019/2020 26 / 58

LLin – aplicat, ie

I Multiplica cu 2 coordonatele unui punct:

procedure ori2Punct(p)begin

p.x ← p.x ∗ 2p.y ← p.y ∗ 2

end

I Multiplica cu 2 coordonatele unei linii poligonale:

procedure ori2Linie(p)begin

parcurge(L, ori2Punct())end

FII, UAIC Curs 4 SD 2019/2020 27 / 58

LLin – aplicat, ie

I translateaza punct:

procedure trPunct(p, dx , dy)begin

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

end

I translateaza linie poligonala:

procedure trLinie(L, dx , dy)begin

parcurge(L, trPunct())end

FII, UAIC Curs 4 SD 2019/2020 28 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 29 / 58

Liste liniare ordonate: LLinOrd

I Obiecte:L = (e0, · · · , en−1), n ≥ 0, ei ∈ Elt, e0 ≤ e1 ≤ · · · ≤ en−1

I Operat, ii:I listaVida()

I intrare: nimic

I ies, ire: L = () (lista cu zero elemente)

I insereaza()I intrare: L = (e0, . . . , en−1), e ∈ Elt

I ies, ire: L = (· · · , ek−1, e, ek , · · · ), daca ek−1 ≤ e ≤ ek(e−1 = −∞, en = +∞)

FII, UAIC Curs 4 SD 2019/2020 30 / 58

Liste liniare ordonate: LLinOrd

I elimina()I intrare: L = (e0, . . . , en−1), e ∈ Elt

I ies, ire: L = (· · · , ek−1, ek+1, · · · ), daca e = ekeroare ın caz contrar

I alKlea()

I parcurge()

I poz()

FII, UAIC Curs 4 SD 2019/2020 31 / 58

LLinOrd – implementarea cu tablouri

function poz(L, e)begin

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

if (e < L.tab[m]) thenq ← m–1

elsep ← m + 1

m← (p + q)/2if (L.tab[m] == e) then

return melse

return −1end

FII, UAIC Curs 4 SD 2019/2020 32 / 58

LLinOrd – complexitatea cautarii

I Implementarea cu tablouri: O(log2 n);

I Implementarea cu liste ınlant,uite: O(n);

FII, UAIC Curs 4 SD 2019/2020 33 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 34 / 58

Stiva

FII, UAIC Curs 4 SD 2019/2020 35 / 58

Stiva – aplicat, ii

I Aplicat, ii directeI Istoricul paginilor web vizitate ıntr-un browser;

I Sevent,a “undo” ıntr-un editor de text;

I S, iruri de apeluri recursive ale unui subprogram.

I Aplicat, ii indirecteI Structura de date auxiliara ın anumit, i algoritmi;

I Componenta a altor structuri de date.

FII, UAIC Curs 4 SD 2019/2020 36 / 58

Tipul abstract Stiva

I Obiecte:Liste ın care se cunoas, te vechimea elementelor introduse:liste LIFO (Last-In-First-Out).

I Operat, ii:I stivaVida()

I intrare: nimic

I ies, ire: S = () (lista vida)

I esteVida()I intrare: S ∈ Stiva

I ies, ire:– true daca S este vida;– false daca S nu este vida.

FII, UAIC Curs 4 SD 2019/2020 37 / 58

Tipul abstract Stiva

I Operat, ii:I push()

I intrare: S ∈ Stiva, e ∈ Elt

I ies, ire: S la care s-a adaugat e ca ultim element introdus(cel cu vechimea cea mai mica).

I pop()I intrare: S ∈ Stiva

I ies, ire:– S din care s-a eliminat ultimul element introdus(cel cu vechimea cea mai mica);– eroare daca S este vida.

I top()I intrare: S ∈ Stiva

I ies, ire:– ultimul element introdus ın S (cel cu vechimea cea mai mica);– eroare daca S este vida.

FII, UAIC Curs 4 SD 2019/2020 38 / 58

Stiva – implementare cu liste

tipul Stiva tipul LLin

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

sau

tipul Stiva tipul LLin

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

FII, UAIC Curs 4 SD 2019/2020 39 / 58

Stiva – implementarea cu tablouri

I Reprezentarea obiectelor

S.tab Elt[Max] e0 . . . en−1

Max-1

S.varf int n − 1

I implementarea operat, iilor

procedure push(S , e)begin

if S .varf == Max − 1 thenthrow “eroare”

elseS .varf ← S .varf + 1S .tab[varf ]← e

end

FII, UAIC Curs 4 SD 2019/2020 40 / 58

Stiva – implementarea cu structuri ınlant,uite

I Reprezentarea obiectelor

S • en−1 •

en−2 •

...

e0 •

FII, UAIC Curs 4 SD 2019/2020 41 / 58

Stiva – implementarea cu structuri ınlant,uite

I Implementarea operat, iilorI push()

procedure push(S , e)begin

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

end

I pop()

procedure pop(S)begin

if S == NULL thenthrow “eroare”

q ← SS ← S− > succ

delete(q) end

FII, UAIC Curs 4 SD 2019/2020 42 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 43 / 58

Coada

FII, UAIC Curs 4 SD 2019/2020 44 / 58

Coada – aplicat, ii

I Aplicat, ii directeI Liste / fire de as, teptare;

I Accesul la resurse partajate.Exemplu: imprimante.

I Aplicat, ii indirecteI Structura de date auxiliara ın anumit, i algoritmi.

FII, UAIC Curs 4 SD 2019/2020 45 / 58

Tipul abstract Coada

I Obiecte:Liste ın care se cunoas, te vechimea elementelor introduse:liste FIFO (First-In-First-Out).

I Operat, ii:I coadaVida()

I intrare: nimic

I ies, ire: C = () (lista vida)

I esteVida()I intrare: C ∈ Coada

I ies, ire:– true daca C este vida;– false daca C nu este vida.

FII, UAIC Curs 4 SD 2019/2020 46 / 58

Tipul abstract Coada

I Operat, ii:I insereaza()

I intrare: C ∈ Coada, e ∈ Elt

I ies, ire: C la care s-a adaugat e ca ultim element introdus(cel cu vechimea cea mai mica).

I elimina()I intrare: C ∈ Coada

I ies, ire:– C din care s-a eliminat primul element introdus(cel cu vechimea cea mai mare);– eroare daca C este vida.

I citeste()I intrare: C ∈ Coada

I ies, ire:– primul element introdus ın C (cel cu vechimea cea mai mare);– eroare daca C este vida.

FII, UAIC Curs 4 SD 2019/2020 47 / 58

Coada – implementare cu liste

tipul Coada tipul LLin

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

FII, UAIC Curs 4 SD 2019/2020 48 / 58

Coada – implementarea cu tablouri

I Reprezentarea obiectelor

C.tab Elt[Max] e0 . . . en−1

Max-1

C.prim p q C.ultim

C.tab Elt[Max] . . . . . . eien−1 e0

Max-1

C.ultim q p C.prim

FII, UAIC Curs 4 SD 2019/2020 49 / 58

Coada – implementarea cu tablouri

I Reprezentarea obiectelor

C.tab Elt[Max] e0 . . . en−1

Max-1

C.prim p q C.ultim

C.tab Elt[Max] . . . . . . eien−1 e0

Max-1

C.ultim q p C.prim

FII, UAIC Curs 4 SD 2019/2020 49 / 58

Coada – implementarea cu tablouri

I Implementarea operat, iilorI insereaza()

procedure insereaza(C , e)begin

if (C .ultim + 1)%Max == C .prim thenthrow “eroare”

elseC .ultim← (C .ultim + 1)%MaxC .tab[ultim]← e

end

FII, UAIC Curs 4 SD 2019/2020 50 / 58

Coada – implementarea cu structuri ınlant,uite

I Reprezentarea obiectelor

C.prim • C.ultim •

e0 • e1 • . . . en−1 •

FII, UAIC Curs 4 SD 2019/2020 51 / 58

Coada – implementarea cu structuri ınlant,uite

I Implementarea operat, iilorI insereaza()

procedure insereaza(C , e)begin

new(q)q− > elt ← eq− > succ ← NULLif C .ultim == NULL then

C .prim← qC .ultim← q

elseC .ultim− > succ ← qC .ultim← q

end

FII, UAIC Curs 4 SD 2019/2020 52 / 58

Continut

Tipurile abstracte LLin, LLinOrd, Stiva, CoadaListe liniareImplementarea cu tablouriImplementarea cu liste simplu ınlant,uiteListe liniare ordonateStiveCozi

Aplicat, ie la conversie de expresii aritmetice

FII, UAIC Curs 4 SD 2019/2020 53 / 58

Aplicat, ie – notat, ia postfixata a expresiilor

I notat, ia infixataI a + bI a + (b ∗ 2)

I notat, ia postfixataI a b +I a b 2 ∗+

I reguli de precedent, aI a + b ∗ 2

I reguli de asociere: 7/3 ∗ 2I la stanga: (7/3) ∗ 2I la dreapta: 7/(3 ∗ 2)

FII, UAIC Curs 4 SD 2019/2020 54 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e↓

↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max]

a b c d + ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓

↓

↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a

b c d + ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓

↓

↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a

b c d + ∗ + e +

S (stiva)

+

∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓

↓↓

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a b

c d + ∗ + e +

S (stiva)

+

∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓

↓

↓ ↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a b

c d + ∗ + e +

S (stiva)

+∗

(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓

↓

↓ ↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a b

c d + ∗ + e +

S (stiva)

+∗(

+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓

↓

↓ ↓ ↓ ↓ ↓

postf.tab Elt[Max] a b c

d + ∗ + e +

S (stiva)

+∗(

+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓

postf.tab Elt[Max] a b c

d + ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

postf.tab Elt[Max] a b c d

+ ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

postf.tab Elt[Max] a b c d +

∗ + e +

S (stiva)

+∗(

+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

postf.tab Elt[Max] a b c d +

∗ + e +

S (stiva)

+∗

(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓

postf.tab Elt[Max] a b c d +

∗ + e +

S (stiva)

+∗

(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓

postf.tab Elt[Max] a b c d + ∗

+ e +

S (stiva)

+

∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓

postf.tab Elt[Max] a b c d + ∗ +

e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓

postf.tab Elt[Max] a b c d + ∗ +

e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓

postf.tab Elt[Max] a b c d + ∗ + e

+

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

postf.tab Elt[Max] a b c d + ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postixat

Exemplu: a + b ∗ (c + d) + e

inf.tab Elt[Max] a + b ∗ ( c + d ) + e

↓ ↓ ↓ ↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

postf.tab Elt[Max] a b c d + ∗ + e +

S (stiva)

+∗(+

+

FII, UAIC Curs 4 SD 2019/2020 55 / 58

Conversia infixat → postfixat

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

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

x ← citeste(infix); elimina(infix)if (operand(x) then

insereaza(postfix , x)else

if (x ==′)′) thenwhile (top(S)! =′ (′) do

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

elsewhile (not estevida(S) and top(S)! =′ (′ and

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

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

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

FII, UAIC Curs 4 SD 2019/2020 56 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +↓

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓

↓

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

S (stiva)

a

b

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓

↓

↓ ↓ ↓ ↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓

↓

↓ ↓ ↓ ↓ ↓ ↓

S (stiva)

ab

c

dc + d

b ∗ (c + d)a + b ∗ (c + d)

ea + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓ ↓

S (stiva)

ab

c

dc + d

b ∗ (c + d)a + b ∗ (c + d)

ea + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + d

b ∗ (c + d)a + b ∗ (c + d)

ea + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓ ↓

S (stiva)

a

b

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

S (stiva)

a

b

cd

c + d

b ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

S (stiva)

a

b

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓ ↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)

ea + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)

ea + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postixate

Exemplu: a b c d + ∗+ e+

postf.tab Elt[Max] a b c d + ∗ + e +

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

↓

S (stiva)

ab

cd

c + db ∗ (c + d)

a + b ∗ (c + d)e

a + b ∗ (c + d) + e

FII, UAIC Curs 4 SD 2019/2020 57 / 58

Evaluarea expresiilor postfixate

function valPostfix(postfix)begin

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

x ← citeste(postfix); elimina(infix)if (operand(x) 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

FII, UAIC Curs 4 SD 2019/2020 58 / 58