Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Urmatoarea versiune | Versiuni anterioare | ||
laboratoare:laborator-03 [2017/01/29 01:10] florina_elena.barbu creat |
laboratoare:laborator-03 [2018/02/25 22:13] mihai.iacov |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 03: TODO ====== | + | ====== Laborator 03: Liste ====== |
+ | \\ | ||
+ | =====1 Obiectivele laboratorului===== | ||
+ | *Înțelegerea conceptului de funcționare și implementarea unor liste dublu înlănțuite și circulare | ||
+ | *Implementarea unor funcții individuale de lucru cu aceste structuri de date. | ||
+ | \\ | ||
- | TODOD | + | =====2 Ce este o listă? |
+ | ====2.1 Definiție==== | ||
+ | Listele sunt cele mai bune și cele mai simple exemple a unei structuri de date dinamice care folosește pointeri | ||
+ | la implementarea sa.în mod esențial, trebuie înțeles că listele funcționează ca un vector care se poate mări sau | ||
+ | micșora după nevoie, din orice punct al mulțimii sale de elemente. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Avantaje ale utilizării listelor: | ||
+ | *Elementele pot fi adăugate sau șterse din mijlocul listei | ||
+ | *Nu trebuie definită o mărime inițială, iar memoria se alocă pe rând, odată cu fiecare element adăugat | ||
+ | |||
+ | Definirea nodului unei liste: | ||
+ | <file cpp> | ||
+ | typedef struct { | ||
+ | int val; | ||
+ | node *next; | ||
+ | } node_t; | ||
+ | </ | ||
+ | |||
+ | ====2.2 Clasificare==== | ||
+ | * **Liste simplu înlănțuite** - Elementele au o singură legătură către următorul element introdus, iar ultimul | ||
+ | element pointează către NULL. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | |||
+ | * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, | ||
+ | spre NULL și ultimul element de asemenea | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ====2.3 Operații cu liste: | ||
+ | *Adăugare la începutul listei | ||
+ | *Adăugare la sfârsitul listei | ||
+ | *Adăugarea înainte sau după un element dat | ||
+ | *Ștergerea capului de listă | ||
+ | *Ștergerea unui element oarecare din listă | ||
+ | |||
+ | =====3.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. Să 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. Adunaţi 2 polinoame rare, reprezentând fiecare polinom printr-o listă înlănţuită, | ||
+ | |||
+ | 5. 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 '' | ||
+ | |||
+ | 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/ | ||
+ | |||
+ | 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 '' | ||
+ | |||
+ | ====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ă | ||