L5b
2
Structuri de Date (1CC) L A B O R A T O R 5(b) Dictionar ca tabel de dispersie 1. Sa se defineasca urmatoarele tipuri de date !od nod de lista inlantuita care contine o c"eie si o #aloare (intre$i) %ap tip dictionar& ca structura cu un #ector de pointeri !od' si cu dimensiunea #ectorului Sa se defineasca urmatoarele functii pentru operatii cu un dictionar reali at ca tabel de dispersie #oid init (%ap d& int n)*++ initiali are dictionar (#ector de n pointeri) #oid put (%ap d&int ,&int #)* ++ pune in dictionar c"eia , si #aloarea # int $et (%ap d&int ,)* ++ scoate din d #aloarea asociata c"eii , #oid print (%ap d)* ++ afisare dictionar -unctia put #erifica daca e/ista o perec"e cu c"eia ,* daca nu e/ista atunci se adau$a perec"ea (,&#)& iar daca e/ista c"eia , atunci se inlocuieste #aloarea asociata ei cu #aloarea # (primita ca ar$ument de put). -iecare perec"e se afisea a sub forma ,# si fiecare lista de coli iuni incepe pe o linie separata (,0c"eie�#aloare& ambele intre$i). O noua perec"e se adau$a la sfarsitul listei de coli iuni. Sa se #erifice functiile anterioare cu urmatorul pro$ram int main () int i&n023* ++ n0nr de c"ei $enerate %ap d* ++ dictionar init (d&4)* for (i01*i 0n*i66) ++ $enerea a n perec"i c"eie7#aloare put (d&i815&i)* ++ pune in d c"eie si #aloare print(d)* ++ afisare dictionar s9stem( pause )* : Sa se modifice dimensiunea #ectorului de pointeri si sa se obser#e cum se modifica listele de coli iuni si ordinea c"eilor in dictionar. (se #or folosi succesi# numerele prime 5&4 si 11). ;. Sa se modifice functiile put& $et si print pentru ca ul cand c"eile sunt siruri de caractere. Sa se #erifice cu pro$ramul urmator int main () c"ar' <=>0 alfa & beta & $ama & delta & $ama & beta & $ama :* int n0si eof(<)+si eof(c"ar')* ++ nr de cu#inte int i&nr* ++ nr de aparitii %ap d* ++ dictionar de cu#inte init (d&5)* ++ #ector de lun$ime 5
-
Upload
leslie-nelson -
Category
Documents
-
view
214 -
download
0
description
l5b
Transcript of L5b
Structuri de Date (1CC)
L A B O R A T O R 5(b)
Dictionar ca tabel de dispersie
1. Sa se defineasca urmatoarele tipuri de date :
Nod : nod de lista inlantuita care contine o cheie si o valoare (intregi) Map: tip dictionar, ca structura cu un vector de pointeri Nod* si cu dimensiunea vectorului
Sa se defineasca urmatoarele functii pentru operatii cu un dictionarrealizat ca tabel de dispersie:
void init (Map & d, int n);// initializare dictionar (vector de n pointeri) void put (Map & d,int k,int v); // pune in dictionar cheia k si valoarea v int get (Map d,int k);// scoate din d valoarea asociata cheii k void print (Map d);// afisare dictionar
Functia "put" verifica daca exista o pereche cu cheia k; daca nu exista atuncise adauga perechea (k,v), iar daca exista cheia k atunci se inlocuieste valoareaasociata ei cu valoarea v (primita ca argument de put).
Fiecare pereche se afiseaza sub forma k:v si fiecare lista de coliziuni incepe pe o linie separata (k=cheie,v=valoare, ambele intregi). O noua pereche se adauga la sfarsitul listei de coliziuni. Sa se verifice functiile anterioare cu urmatorul program:
int main () { int i,n=30; // n=nr de chei generate Map d; // dictionar init (d,7); for (i=1;i
