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:28] florina_elena.barbu [2.2 Clasificare] |
laboratoare:laborator-02 [2017/03/04 09:28] 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 {{ : | ||
+ | <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 | ||
+ | |||
+ | 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368] | ||
+ | |||
+ | 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: | ||
+ | </ | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | |||
+ | |||
+ | =====4.Exerciții propuse pentru laborator===== | ||
+ | 1. Creați o listă circulară, | ||
+ | * Scrieți funcțiile care să scrie urmatoarele: | ||
+ | * Să introducă un nou angajat după al treilea.\\ | ||
+ | * 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 în linia de comandă. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | |||
+ | ====Probleme opţionale - de interviu==== | ||
+ | |||
+ | 1. Se dă o listă simplu înlănţuită(primiţi doar un pointer către primul element). Verificaţi dacă lista conţine o buclă. (o listă simplu înlănţuită conţine o buclă => niciun element nu are legătura NULL) | ||
+ | |||
+ | 2. Se dau două liste(pentru fiecare listă - pointer către primul element) în formă de Y(listele se intersectează, | ||
+ | |||
+ | 3. Se dă o listă | ||
====== Extra: Hashtable(tabela de dispersie)====== | ====== Extra: Hashtable(tabela de dispersie)====== | ||
Linia 96: | Linia 142: | ||
**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. | **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. | ||
- | *Functia index dă valorile **{0, | + | * Functia index dă valorile **{0, |
- | unsigned int index(char[] titlu) { return (titlu[0] - ‘A’); } | + | <file cpp> |
- | + | unsigned int index(char[] titlu) { return (titlu[0] - ‘A’); } | |
- | | + | </ |
+ | |||
+ | | ||
(presupunem structura **Carte** definită) | (presupunem structura **Carte** definită) | ||
- | Carte sector[26][n]; | + | <file cpp> |
- | int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial | + | Carte sector[26][n]; |
- | for(int i = 0; i < nrCarti; | + | int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial |
- | int indexCurent = index(intrare[i].titlu); | + | for(int i = 0; i < nrCarti; |
- | sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i]; | + | int indexCurent = index(intrare[i].titlu); |
- | elemInSectorul[indexCurent]++; | + | sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i]; |
- | } //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori | + | elemInSectorul[indexCurent]++; |
+ | } //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori | ||
+ | </ | ||
**Rezultatele**: | **Rezultatele**: | ||
Linia 139: | Linia 188: | ||
În general, putem scrie | În general, putem scrie | ||
- | index(cheie, | + | <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 în care vom reţine cheia respectivă şi valoarea ei). | 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 în care vom reţine cheia respectivă şi valoarea ei). | ||
| | ||
- | hash(cheie) == hash(cheie) % nrSectoare | + | <file cpp> |
+ | hash(cheie) == hash(cheie) % nrSectoare | ||
+ | </ | ||
adică atunci când valorile luate de **hash(cheie)** pot fi folosite ca **indici**(0, | adică atunci când valorile luate de **hash(cheie)** pot fi folosite ca **indici**(0, | ||
Linia 149: | Linia 202: | ||
*Î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**. | *Î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: | *Cele mai simple funcţii hash: | ||
- | hash(cheie) == cheie % nrSectoare, unde cheia = întreg | + | <file cpp> |
+ | hash(cheie) == cheie % nrSectoare, unde cheia = întreg | ||
+ | </ | ||
Linia 166: | Linia 221: | ||
| | ||
| | ||
- |