liste. stive. cozisd/curs/curs-04.pdf · ie la conversie de expresii aritmetice fii, uaic curs 4 sd...
TRANSCRIPT
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