Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-02 [2017/02/20 00:42] florina_elena.barbu [4. Funcţia de dispersie(hash function)] |
laboratoare:laborator-02 [2017/03/02 20:51] iulian.matesica [4. Exercitii Liste] |
||
---|---|---|---|
Linia 20: | Linia 20: | ||
Definirea nodului unei liste: | Definirea nodului unei liste: | ||
<file cpp> | <file cpp> | ||
- | typedef struct | + | typedef struct { |
int val; | int val; | ||
- | struct | + | node *next; |
- | }node t; | + | } node_t; |
</ | </ | ||
Linia 63: | Linia 63: | ||
3.Sa se construiasca o lista liniara simplu inlantuita cu elemente numere intregi. Să se afișeze și apoi să se stearga din lista elementele pare. | 3.Sa se construiasca o lista liniara simplu inlantuita cu elemente numere intregi. Să se afișeze și apoi să se stearga din lista elementele pare. | ||
+ | =====4. Exercitii Liste ===== | ||
+ | Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet de laborator. Nu veti scrie codul de la zero ci veti implementa cateva functii in fisierul '' | ||
+ | Descarcati arhiva de aici si dezarhivati-o. Puteti folosi utilitarul '' | ||
+ | <code bash> | ||
+ | student@sda-ab-vm: | ||
+ | --2017-03-02 20: | ||
+ | Resolving elf.cs.pub.ro (elf.cs.pub.ro)... 141.85.227.116 | ||
+ | Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|: | ||
+ | HTTP request sent, awaiting response... 200 OK | ||
+ | Length: 2368 (2,3K) [application/ | ||
+ | Saving to: ‘lab1-skel.zip’ | ||
- | ====== | + | lab1-skel.zip |
- | =====1 Introducere===== | + | 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368] |
- | (De urmărit ideea din introducere şi funcţia de indexare) | + | student@sda-ab-vm: |
+ | lab1-skel.zip | ||
+ | student@sda-ab-vm: | ||
+ | Archive: | ||
+ | inflating: list.c | ||
+ | inflating: list.h | ||
+ | inflating: Makefile | ||
+ | student@sda-ab-vm: | ||
+ | gcc list.c -o list -std=gnu99 | ||
+ | student@sda-ab-vm: | ||
+ | </ | ||
- | ====1.1 Poveste==== | + | Pentru compilare folositi comanda '' |
- | ===Să presupunem urmatoarele detalii dintr-un caz real:=== | ||
- | | ||
- | | ||
- | | ||
- | **O soluţie**: -Ei consideră că două carţi “seamană” între ele dacă titlurile lor încep cu aceeaşi literă, aşa că au nevoie de câte un sector pentru fiecare literă cu care ar putea începe titlul unei cărţi. Folosind această regulă, angajaţii nu au nevoie de mai mult de 32 de sectoare(26 pentru engleză), adică | + | ====Probleme opţionale |
- | | + | 1. Se dă o listă simplu înlănţuită(primiţi doar un pointer |
- | *O carte poate fi pusă într-un raft imediat după ce identificăm ce sector are aceeaşi literă cu prima literă din titlul cărţii, putem lua această decizie fără a ţine cont de celelalte | + | |
- | *Când cineva vrea să găsească o carte din bibliotecă, este suficient să caute într-un sector, | + | |
- | | + | 2. Se dau două liste(pentru fiecare listă - pointer către primul element) în formă de Y(listele se intersectează, |
- | **Concluzie**: | + | 3. Se dă o listă |
- | ===Folosind o abordare mai tehnică, să urmărim aceleaşi detalii:=== | + | ====== Extra: Hashtable(tabela de dispersie)====== |
- | | + | =====1 Introducere===== |
- | | + | (De urmărit ideea din introducere |
- | | + | ====1.1 Poveste==== |
- | **O soluţie**: -alegem ca un sector să reprezinte o literă şi aceea să fie litera cu care încep toate titlurile intrărilor din acel sector. În realitate, sectoarele pot fi notate cu litere, dar, într-un limbaj de programare, le notăm cu numere pentru a lucra mai uşor. | + | ===Să presupunem urmatoarele detalii dintr-un caz real:=== |
- | * Functia index dă valorile **{0, | + | **Situaţia**: -Într-o bibliotecă sunt foarte multe cărţi şi, deşi spaţiul nu reprezintă o problemă, angajaţii nu dispun |
- | < | + | |
- | | + | |
- | </ | + | |
- | + | ||
- | | + | |
- | (presupunem structura | + | |
- | <file cpp> | + | |
- | Carte sector[26][n]; | + | |
- | int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial | + | |
- | for(int i = 0; i < nrCarti; | + | |
- | int indexCurent = index(intrare[i].titlu); | + | |
- | sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i]; | + | |
- | elemInSectorul[indexCurent]++; | + | |
- | } //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori | + | |
- | </ | + | |
- | + | ||
- | **Rezultatele**: | + | |
- | + | ||
- | | + | |
- | | + | |
- | + | ||
- | | + | |
- | + | ||
- | + | ||
- | ====1.2 Simplificare==== | + | |
- | + | ||
- | Cum ar fi dacă, în loc de foarte multe cărţi, am avea 26 de cărţi şi, în plus, nu ar exista nicio pereche | + | |
- | + | ||
- | *În acest caz, indexarea este perfectă: fiecare sector conţine o carte. | + | |
- | | + | |
- | + | ||
- | =====2. Conceptele Cheie-Valoare(Key-Value)===== | + | |
- | Atunci când reorganizăm o structură de date, aşezăm într-o ordine diferită **valorile** din structura de date, folosind o regulă bazată pe **cheile** acestora. | + | |
- | + | ||
- | *În exemplul nostru, structura de date este biblioteca. Aceasta conţine mai multe **cărţi**(valori), | + | |
- | + | ||
- | =====3. Funcţia de indexare şi sectoarele(buckets)===== | + | |
- | Sectoarele sunt stocate sub formă de elemente ale unui vector. Avem nevoie de o funcţie care să facă legătura dintre cheie şi indice(index) al vectorului. | + | |
- | + | ||
- | *În exemplul nostru, funcţia **index** preia prima litera din **titlu**(cheie) şi calculează “diferenţa” dintre această literă şi prima literă din alfabet. | + | |
- | + | ||
- | =====4. Funcţia de dispersie(hash function)===== | + | |
- | Când coincide cu funcţia de indexare? | + | |
- | + | ||
- | În general, putem scrie | + | |
- | <file cpp> | + | |
- | index(cheie, | + | |
- | </ | + | |
- | unde hash = funcţia de dispersie. Cu alte cuvinte, funcţia de dispersie trebuie să genereze un întreg(**oricât de mare**), folosindu-se de cheie, iar funcţia de indexare obţine un **indice**(indicele sectorului | + | |
- | + | ||
- | | + | |
- | <file cpp> | + | |
- | hash(cheie) == hash(cheie) % nrSectoare | + | |
- | </ | + | |
- | adică atunci când valorile luate de **hash(cheie)** pot fi folosite ca **indici**(0, | + | |
- | + | ||
- | + | ||
- | *În exemplul nostru, funcţia index nu are nevoie de nrSectoare(am considerat această valoare **mereu** egală cu **26**) şi nu apare “%26” în formulă, deci putem considera funcţia de dispersie şi funcţia de indexare **identice**. | + | |
- | *Cele mai simple funcţii hash: | + | |
- | <file cpp> | + | |
- | hash(cheie) == cheie % nrSectoare, unde cheia = întreg | + | |
- | </ | + | |
- | + | ||
- | + | ||
- | =====5 Avantaje/ | + | |
- | + | ||
- | ====5.1 Avantaje==== | + | |
- | *timp de acces(un **vector** cu sectoare) | + | |
- | *timp de inserare(fiecare sector = o **listă**) | + | |
- | + | ||
- | ====5.2 Dezavantaje==== | + | |
- | *nu este mereu uşor de ales o funcţie pentru dispersia(**uniformă** a) cheilor | + | |
- | | + | |
- | + | ||
- | ====5.3 Observaţii==== | + | |
- | *în general, un ansamblu de tipul (**structură de sectoare/ | + | |
- | | + | |
- | | + | |
+ | |