Unelte utilizator
laboratoare:laborator-03
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 | ||
|
laboratoare:laborator-03 [2017/02/14 18:15] sebastian.cancel |
laboratoare:laborator-03 [2018/02/25 22:13] mihai.iacov |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== Laborator 03: Stive & Cozi ====== | + | ====== Laborator 03: Liste ====== |
| \\ | \\ | ||
| =====1 Obiectivele laboratorului===== | =====1 Obiectivele laboratorului===== | ||
| - | *Înțelegerea conceptului de funcționare | + | *Înțelegerea conceptului de funcționare |
| - | *Implementarea unor funcții individuale de lucru cu acestea. | + | *Implementarea unor funcții individuale de lucru cu aceste structuri de date. |
| \\ | \\ | ||
| - | =====2 Ce este o stivă?===== | + | =====2 Ce este o listă?===== |
| ====2.1 Definiție==== | ====2.1 Definiție==== | ||
| - | O stivă reprezintă o listă cu structuri de date de tipul: Last-In-First-Out (LIFO).\\ | + | Listele sunt cele mai bune și cele mai simple exemple a unei structuri de date dinamice care folosește pointeri |
| - | Un exemplu comun ar fi un teanc de cărți: tot punem cărți pe o masă, dar în momentul când vrem să le ridicăm | + | la implementarea sa.în mod esențial, trebuie înțeles |
| - | începem cu ultima, pusă deasupra teancului. | + | micșora după nevoie, din orice punct al mulțimii sale de elemente. |
| - | #poza stiva# | + | {{ : |
| - | ====2.2 Operații cu stive==== | + | 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ă | ||
| - | Definim structura astfel: | + | Definirea nodului unei liste: |
| - | <code> | + | <file cpp> |
| - | struct | + | typedef |
| - | | + | |
| - | int top; | + | node *next; |
| - | } st; | + | } node_t; |
| - | </code> | + | </file> |
| - | * **Verificăm dacă stiva e plină sau goală** | + | ====2.2 Clasificare==== |
| - | < | + | * **Liste simplu înlănțuite** - Elementele au o singură legătură către următorul element introdus, iar ultimul |
| - | int st_full(){ //int st_empty{ | + | element pointează către NULL. |
| - | if(st.top>=size - 1) //if(st.top==-1) | + | |
| - | | + | {{ : |
| - | else | + | |
| - | | + | |
| - | } | + | * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, |
| - | </ | + | spre NULL și ultimul element de asemenea |
| - | * **Adăugarea** | + | |
| - | < | + | {{ : |
| - | void push(int item){ | + | |
| - | st.top++; | + | * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul. |
| - | st.s[st.top]=item; | + | |
| - | } | + | {{ : |
| - | </code> | + | |
| - | * **Ștergerea** | + | ====2.3 Operații cu liste:==== |
| - | < | + | *Adăugare la începutul listei |
| - | int pop(){ | + | *Adăugare la sfârsitul listei |
| - | int item; | + | *Adăugarea înainte sau după un element dat |
| - | item = st.s[st.top]; | + | *Ștergerea capului de listă |
| - | st.top--; | + | *Ștergerea unui element oarecare din listă |
| - | return | + | |
| - | } | + | =====3.Exerciții propuse pentru laborator===== |
| + | 1. Creați o listă circulară, | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | |||
| + | 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 {{ : | ||
| + | < | ||
| + | student@sda-ab-vm: | ||
| + | --2017-03-02 20: | ||
| + | Resolving elf.cs.pub.ro | ||
| + | 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: | ||
| + | |||
| + | 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 '' |
| - | 1.Când introducem elemente într-o stivă,trebuie să incrementăm top-ul și apoi să adăugam elementul.\\ | + | |
| - | 2.Când ștergem un element, | + | ====Probleme opţionale - de interviu==== |
| - | 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste înlănțuite**.\\ | + | |
| + | 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ă 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. | ||
laboratoare/laborator-03.txt · Ultima modificare: 2018/02/25 22:13 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
