Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 02: Algoritmi de sortare 1
Traseu:
laboratoare:laborator-02

Diferențe

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

Link către această vizualizare comparativă

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/05 13:30]
florina_elena.barbu
Linia 20: Linia 20:
 Definirea nodului unei liste: Definirea nodului unei liste:
 <file cpp> <file cpp>
-typedef struct node{+typedef struct {
      int val;      int val;
-     struct node * next; +     node *next; 
-}node t;+} node_t;
 </file> </file>
  
Linia 48: Linia 48:
 *Ștergerea capului de listă *Ștergerea capului de listă
 *Ștergerea unui element oarecare din listă *Ștergerea unui element oarecare din listă
- 
  
 =====3.Exerciții propuse pentru laborator===== =====3.Exerciții propuse pentru laborator=====
Linia 63: Linia 62:
 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. 
  
 +4. 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      
 +
 +2017-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====
 +
 +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ă, ultimele k elemente sunt comune). Aflaţi valoarea lui k.
 +
 +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 de dispersie)====== ====== Extra: Hashtable(tabela de dispersie)======
Linia 147: Linia 182:
  
 În general, putem scrie Î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). 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ă:  *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. 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 157: 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**.  *Î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 
 +</file>
  
  
Linia 174: Linia 215:
  *exemplul prezentat este demonstrativ(pentru sortare eficientă care extinde ideea, vedeţi **Radix Sort**)  *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**)  *funcţiile hash au aplicaţii mai importante în protecţia(criptarea) datelor(vedeţi **Caesar-Cipher**, **ROT13**, **SHA-256**)
- 
laboratoare/laborator-02.txt · Ultima modificare: 2018/02/25 22:02 de către mihai.iacov

Unelte pagină

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
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki