Multidicționar ordonat (MDO)

Multidicționar = o cheie are mai multe valori asociate (o listă de valori asociate)

Multidicționar ordonat = cheile sunt într-o anumită relație de ordine R și sunt memorate în ordine

Problemă: Să se implementeze TAD Multidicționar ordonat (MDO) – reprezentare înlănțuită cu

alocare dinamică.

Operații:

creeaza (mdo, R)

pre: R – relatie pe multimea cheilor

post: mdoMDOmdo ,

distruge(mdo)

pre: MDOmdo

post:mdo a fost “distrusa” (spatiul alocat a fost eliberat)

adauga(mdo, c, v)

pre: TValoarevTCheiecMDOmdo ,,

post: perechea <c,v> a fost adaugata in mdo

sterge(mdo, c, v)

pre: TValoarevTCheiecMDOmdo ,,

post: perechea <c,v> a fost stearsa din mdo

cauta(mdo, c, l)

pre: TCheiecMDOmdo ,

post:

altfellsifals

mdoincheieestecdaca

ccuasociatevalorilorlistaestelsitrue

Ll

,

,

,

iterator(mdo, i)

pre: MDOmdo

post: Ii , i este iterator pe mdo

Alte operatii posibile:

multimeaCheilor(mdo, m)

pre: MDOmdo

post: ,Mm m este multimea tuturor cheilor din mdo

multimeaValorilor(mdo, m)

pre: MDOmdo

post: ,Mm m este multimea tuturor valorilor din mdo

Reprezentare:

MDO:

prim: ↑NodT

R: relație

NodT:

urm: ↑NodT

e: Telement

TElement:

c: TCheie

l : TLista

Iterator MDO:

mdo: MDO

curent: ↑NodT

itL: IteratorList

Operații iterator:

Subalgoritm creeaza (it, mdo): { Θ (1) }

it.mdo ←mdo

it.curent ← [it.mdo].prim

Daca it.curent ≠ NIL atunci

iterator ([it.mdo.prim].e.l, it.itL)

SfDaca

SfSubalgoritm

Functia valid(it): { Θ (1) }

valid ← it.curent ≠ NIL

SfSubalgoritm

Subalgoritm element(it, e): {e = <c,v>} { Θ (1) }

e.c ← [it.curent].e.c

element (it.itL, e.v)

SfSubalgoritm

Subalgoritm urmator (it): { Θ (1) }

urmator(it.itL)

Daca ¬valid(it.itL) atunci

it.curent ← [it.curent].urm

Daca it.curent ≠ NIL atunci

iterator ([it.curent].e.l, it.itL)

SfDaca

SfDaca

SfSubalgoritm

Operatii multidictionar ordonat:

La complexitati:

- n – nr de chei distinct

- mdo – nr total de elemente

Subalgoritm creeaza(mdo, R): { Θ (1) }

mdo.R ← R

mdo.prim ←NIL

SfSubalgoritm

Subalgoritm distruge(mdo): {Θ (mdo)}

CatTimp mdo.prim ≠ NIL executa

p ←mdo.prim

distruge ([p].e.l)

mdo.prim ← [mdo.prim].urm

dealoca(p)

SfCatTimp

SfSubalgoritm

Subalgoritm cauta (mdo, c, l): {Θ (n)}

p ← mdo.prim

gasit ← fals

CatTimp p ≠NIL si ¬ gasit executa

Daca [p].e.c = c atunci

gasit ← adevarat

altfel

p ← [p].urm

SfDaca

SfCatTimp

Daca gasit atunci

l ← [p].e.l

altfel

creeaza (l)

SfDaca

SfSubalgoritm

Functia cautNod (mdo, c): {Θ(n)}

p ← mdo.prim

gasit ← fals

CatTimp p ≠NIL si ¬ gasit executa

Daca [p].e.c = c atunci

gasit ← adevarat

altfel

p ← [p].urm

SfDaca

SfCatTimp

Daca gasit atunci

cautNod ← p

altfel

cautNod ← NIL

SfDaca

SfFunctia

Subalgoritm adauga (mdo, c, v): {Θ(n)}

p ← cautNod (mdo, c)

Daca p = NIL atunci

adaugaCheieNoua (mdo, c, v)

altfel

adaugaSfarsit([p].e.l, v)

SfDaca

SfSubalgoritm

Subalgoritm adaugaCheieNoua(mdo, c,v): {Θ(n)}

Daca mdo.prim = NIL atunci

aloca (mdo.prim)

[mdo.prim].e.c ←c

creeaza ([mdo.prim].e.l)

adaugaSfarsit([mdo.prim].e.l, v)

altfel

aloca (q)

[q].e.c ← c

creeaza ([q].e.l)

adaugaSfarsit([q].e.l, v)

p ← mdo.prim

Daca mdo.R(c, [p].e.c) atunci {inseram inainte de primul nod}

[q].urm ← p

mdo.prim ← q

altfel

CatTimp ([p].urm ≠ NIL si ¬mdo.R(c, [[p].urm].e.c)) executa

p ← [p].urm

SfCatTimp

{am gasit pozitia (nodul p) dupa care inseram}

[q].urm ← [p].urm

[p].urm ← q

SfDaca

SfDaca

SfSubalgoritm

Subalgoritm sterge (mdo, c, v): {Θ(n)}

p ← cautNod (mdo, c)

Daca p ≠ NIL atunci

pos ← pozitie ([p].e.l, v)

Daca pos ≠ ┴ atunci

sterge ([p].e.l, pos, e)

SfDaca

Daca vida ([p].e.l) atunci

stergCheie (mdo, c)

SfDaca

SfDaca

SfSubalgoritm

Subalgoritm stergCheie (mdo, c): {Θ(n)}

Daca [mdo.prim].e.c = c atunci

p ←mdo.prim

mdo.prim ← [mdo.prim].urm

dealoca (p)

altfel

p ←mdo.prim

CatTimp [p].urm ≠NIL si [[p].urm].e.c ≠ c executa

p ←[p].urm

SfCatTimp

q← [p].urm

[p].urm ← [q].urm

dealoca (q)

SfDaca

SfSubalgoritm