Unelte utilizator
laboratoare:laborator-02
Diferențe
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:30] florina_elena.barbu [1.1 Poveste] |
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 51: | Linia 51: | ||
| =====3.Exerciții propuse pentru laborator===== | =====3.Exerciții propuse pentru laborator===== | ||
| - | 1.//[0.5p]//Creați o listă circulară, | + | 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.\\ | ||
| - | Scrieți funcțiile care să scrie urmatoarele: | + | 2. Să se creeze o listă liniara simplu inlantuita care contine elemente intregi citite dintr-ul fisier text. |
| - | //[0.5p]//Să introducă un nou angajat după al treilea.\\ | + | Se citeste apoi o valoare intreaga x. Sa se stearga primul nod care contine valoarea x. |
| - | //[0.75p]//Să introducă un nou angajat inainte de cel care e " | + | 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 107: | ||
| **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, |
| - | <file cpp> | + | < |
| - | unsigned int index(char[] titlu) { return (titlu[0] - ‘A’); } | + | |
| - | </ | + | </ |
| - | + | ||
| - | | + | * Ignorând problema spaţiului, definim secvenţa pentru distribuirea intrărilor pe sectoare: |
| (presupunem structura **Carte** definită) | (presupunem structura **Carte** definită) | ||
| <file cpp> | <file cpp> | ||
| Linia 142: | 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 152: | 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 | ||
| + | </ | ||
laboratoare/laborator-02.txt · Ultima modificare: 2018/02/25 22:02 de către mihai.iacov
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
