Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-02 [2017/02/18 12:58]
mihai.iacov [1.1 Poveste]
+++ laboratoare:laborator-02 [2017/03/05 13:30]
florina_elena.barbu
@@ Linia 1: / Linia 1: @@
-====== Laborator 02: Liste & Hashtable ======
+====== Laborator 02: Liste ======
 \\
 =====1 Obiectivele laboratorului=====
@@ Linia 12: / Linia 12: @@
 micșora după nevoie, din orice punct al mulțimii sale de elemente.
-#POZA 1#
+{{ :laboratoare:array_vs_list.png?400 |}}
 Avantaje ale utilizării listelor:
@@ Linia 20: / Linia 20: @@
 Definirea nodului unei liste:
 <file cpp>
-typedef struct node{
+typedef struct {
      int val;
-     struct node * next;
+     node *next;
-}node t;
+} node_t;
 </file>
@@ Linia 30: / Linia 30: @@
 element pointează către NULL.
-#Poza liste simplu inlantuite#
+{{ :laboratoare:simplelist.png?500 | Liste simplu înlănțuite}}
 * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, capul listei pointând
 spre NULL și ultimul element de asemenea
-#Poza lista dublu inlantuite#
+{{ :laboratoare:doublelist.jpg?500 |}}
 * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul.
-#Poza lista circulare#
+{{ :laboratoare:circularlist.png?500 |#Poza lista circulare#}}
 ====2.3 Operații cu liste:====
@@ Linia 47: / Linia 48: @@
 *Ștergerea capului de listă
 *Ștergerea unui element oarecare din listă
 =====3.Exerciții propuse pentru laborator=====
-.//[0.5p]//Creați o listă circulară,dublu inlănțuită cu 6 angajați ai unei companii, care să conțină următoarele referințe: nume, nr de telefon, post.
+. Creați o listă circulară,dublu inlănțuită cu 6 angajați ai unei companii, care să conțină următoarele referințe: nume, nr de telefon, post.
+  * 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 "mecanic".\\
+  * Să steargă angajatul cu un anumit număr de telefon introdus.\\
-Scrieți funcțiile care să scrie urmatoarele:\\
+. 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 "mecanic".\\
+Fișierul se va da ca parametru în linia de comandă.
-//[0.75p]//Să steargă angajatul cu un anumit număr de telefon introdus.\\
+.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.
+. 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 ''%%list.c%%''.
+Descarcati arhiva de {{ :laboratoare:lab1-skel.zip |aici}} si dezarhivati-o. Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+<code bash>
+student@sda-ab-vm:~/Documents$ wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip
+--2017-03-02 20:45:55--  http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip
+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|:80... connected.
+HTTP request sent, awaiting response... 200 OK
+Length: 2368 (2,3K) [application/zip]
+Saving to: ‘lab1-skel.zip’
+lab1-skel.zip       100%[===================>]   2,31K  --.-KB/s    in 0s
+-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368]
+student@sda-ab-vm:~/Documents$ ls
+lab1-skel.zip
+student@sda-ab-vm:~/Documents$ unzip lab1-skel.zip
+Archive:  lab1-skel.zip
+  inflating: list.c
+  inflating: list.h
+  inflating: Makefile
+student@sda-ab-vm:~/Documents$ make
+gcc list.c -o list -std=gnu99
+student@sda-ab-vm:~/Documents$ make run
+</code>
+Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi fie **''%%./list%%''** fie comanda ''%%make run%%''.
+====Probleme opţionale - de interviu====
+. 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)
+. Se dau două liste(pentru fiecare listă - pointer către primul element) în formă de Y(listele se intersectează, ultimele k elemente sunt comune). Aflaţi valoarea lui k.
+. 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 de dispersie)======
@@ Linia 95: / Linia 136: @@
  **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,1,2,…}** pentru titluri care încep cu literele **{‘A’,’B’,’C’,…}**. Această funcţie se foloseşte de codul ASCII, deci ne limităm la alfabetul limbii engleze.
+   * Functia index dă valorile **{0,1,2,…}** pentru titluri care încep cu literele **{‘A’,’B’,’C’,…}**. Această funcţie se foloseşte de codul ASCII, deci ne limităm la alfabetul limbii engleze.
-	unsigned int index(char[] titlu) { return (titlu[0] - ‘A’); }
+ <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:
+  </file>
+  *  Ignorând problema spaţiului, definim secvenţa pentru distribuirea intrărilor pe sectoare:
 (presupunem structura **Carte** definită)
-	Carte sector[26][n]; //26 de vectori(unul pentru fiecare literă), n = suficient de mare
+<file cpp>
-	int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial
+Carte sector[26][n]; //26 de vectori(unul pentru fiecare literă), n = suficient de mare
-	for(int i = 0; i < nrCarti;i++) {
+int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial
-		int indexCurent = index(intrare[i].titlu); //în ce sector punem cartea?
+for(int i = 0; i < nrCarti;i++) {
-		sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i];
+	int indexCurent = index(intrare[i].titlu); //în ce sector punem cartea?
-		elemInSectorul[indexCurent]++; //am adăugat încă o carte
+	sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i];
-	} //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori
+	elemInSectorul[indexCurent]++; //am adăugat încă o carte
+} //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori
+</file>
 **Rezultatele**:
@@ Linia 138: / Linia 182: @@
 În general, putem scrie
-	index(cheie, nrSectoare) == hash(cheie) % nrSectoare
+<file cpp>
+index(cheie, nrSectoare) == hash(cheie) % nrSectoare
+</file>
 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).
  *Coincid dacă:
-	hash(cheie) == hash(cheie) % nrSectoare
+<file cpp>
+hash(cheie) == hash(cheie) % nrSectoare
+</file>
 adică atunci când valorile luate de **hash(cheie)** pot fi folosite ca **indici**(0,1,2,3,…,nrSectoare – 1). De obicei, această egalitate are loc dacă numărul de sectoare este **fixat** şi **cunoscut** de la început.
@@ Linia 148: / Linia 196: @@
  *Î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
+<file cpp>
+hash(cheie) == cheie % nrSectoare, unde cheia = întreg
+</file>
@@ Linia 162: / Linia 212: @@
 ====5.3 Observaţii====
+ *în general, un ansamblu de tipul (**structură de sectoare/buckets**) + (**funcţie de dispersie/hash**) este numit tabelă de dispersie(**Hashtable**)
  *exemplul prezentat este demonstrativ(pentru sortare eficientă care extinde ideea, vedeţi **Radix Sort**)
  *funcţiile hash au aplicaţii mai importante în protecţia(criptarea) datelor(vedeţi **Caesar-Cipher**, **ROT13**, **SHA-256**)

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină