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:32] florina_elena.barbu [1.1 Poveste] |
laboratoare:laborator-02 [2017/03/02 20:52] iulian.matesica |
||
---|---|---|---|
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 50: | Linia 50: | ||
- | =====3.Exerciții propuse pentru laborator===== | ||
- | 1.// | ||
- | Scrieți funcțiile care să scrie urmatoarele: | + | =====3. Exercitii Liste ===== |
- | // | + | Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet |
- | // | + | |
- | //[0.75p]//Să steargă angajatul cu un anumit număr de telefon introdus.\\ | + | |
+ | Descarcati arhiva de [[laboratoare: | ||
+ | <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 | ||
- | ====== Extra: Hashtable(tabela de dispersie)====== | + | 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368] |
- | =====1 Introducere===== | + | 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: | ||
+ | </ | ||
- | (De urmărit ideea din introducere şi funcţia de indexare) | + | Pentru compilare folositi comanda '' |
- | ====1.1 Poveste==== | ||
- | ===Să presupunem urmatoarele detalii dintr-un caz real:=== | ||
- | | + | =====4.Exerciții propuse pentru laborator===== |
+ | 1. Creați | ||
+ | * Scrieți funcțiile care să scrie urmatoarele: | ||
+ | * Să introducă un nou angajat | ||
+ | * Să introducă un nou angajat inainte de cel care e " | ||
+ | * Să steargă angajatul cu un anumit număr de telefon introdus.\\ | ||
- | | + | 2. Să se creeze o listă liniara simplu inlantuita care contine elemente intregi citite dintr-ul fisier text. |
+ | Se citeste apoi o valoare intreaga x. Sa se stearga primul nod care contine valoarea x. | ||
+ | Fișierul se va da ca parametru | ||
- | | + | 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. |
- | **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ă de atâtea sectoare câte litere sunt în alfabet, deci fiecarui sector îi va corespunde o literă. | ||
- | | + | ====Probleme opţionale |
- | *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ărţi, deci vom avea nevoie de mai puţin timp. | + | |
- | *Când cineva vrea să găsească o carte din bibliotecă, | + | |
- | | + | 1. Se dă o listă simplu înlănţuită(primiţi doar un pointer |
- | | + | 2. Se dau două liste(pentru fiecare listă - pointer |
- | ===Folosind | + | 3. Se dă o listă cu 2n+1 elemente, fiecare element conţine câte un întreg. Toate valorile întregi apar de două ori în listă, excepţie facând una singură. Aflaţi acea valoare. |
- | | + | ====== Extra: Hashtable(tabela |
- | | + | =====1 Introducere===== |
- | | + | (De urmărit ideea din introducere şi funcţia de indexare) |
- | **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. | + | ====1.1 Poveste==== |
- | * Functia index dă valorile **{0, | + | ===Să presupunem urmatoarele detalii dintr-un caz real:=== |
- | < | + | |
- | | + | |
- | </ | + | |
- | + | ||
- | * Ignorând problema spaţiului, definim secvenţa pentru distribuirea intrărilor pe sectoare: | + | |
- | (presupunem structura **Carte** definită) | + | |
- | <file cpp> | + | |
- | Carte sector[26][n]; | + | |
- | int elemInSectorul[26] | + | |
- | 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**: | + | **Situaţia**: -Într-o bibliotecă sunt foarte multe cărţi şi, deşi spaţiul nu reprezintă o problemă, angajaţii nu dispun |
- | + | ||
- | | + | |
- | | + | |
- | + | ||
- | | + | |
- | + | ||
- | + | ||
- | ====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 | + | |
- | 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 | + | |
- | + | ||
- | | + | |
- | 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: | + | |
- | 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/ | + | |
- | | + | |
- | | + | |
+ | |