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:39] florina_elena.barbu [3.Exerciții propuse pentru laborator] |
laboratoare:laborator-02 [2017/03/02 19:26] iulian.matesica [2.1 Definiție] |
||
---|---|---|---|
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. | ||
+ | ====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 147: | Linia 153: | ||
Î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 157: | Linia 167: | ||
*Î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 | ||
+ | </ | ||