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/03/05 19:07] iulian.matesica |
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. |
- | {{ : | + | {{ : |
- | ====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: |
<file cpp> | <file cpp> | ||
- | struct | + | typedef |
- | | + | |
- | int top; | + | node *next; |
- | } st; | + | } node_t; |
</ | </ | ||
- | * **Verificăm dacă stiva e plină sau goală** | + | ====2.2 Clasificare==== |
- | <file cpp> | + | * **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. |
- | | + | |
- | return 1; | + | |
- | | + | |
- | return 0; | + | |
- | } | + | |
- | </ | + | |
- | * **Adăugarea** | + | |
- | <file cpp> | + | |
- | void push(int item){ | + | |
- | st.top++; | + | |
- | | + | |
- | } | + | |
- | </ | + | |
- | * **Ștergerea** | + | |
- | <file cpp> | + | |
- | int pop(){ | + | |
- | int item; | + | |
- | item = st.s[st.top]; | + | |
- | | + | |
- | | + | |
- | } | + | |
- | </ | + | |
- | **// | + | {{ : |
- | 1.Când introducem elemente într-o stivă, | + | |
- | 2.Când ștergem un element, | + | |
- | 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste | + | |
- | =====3 Ce este o coadă? | ||
- | ====3.1 Definiție ==== | + | * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul |
- | O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, | + | spre NULL și ultimul element de asemenea |
- | {{ : | + | {{ : |
- | ====3.2 Operații cu cozi==== | + | * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul. |
- | Definim structura astfel: | + | |
- | <file cpp> | + | |
- | struct queue{ | + | |
- | int queue[size]; | + | |
- | int rear = -1; | + | |
- | }Q | + | |
- | int front = 0; | + | |
- | </ | + | |
- | * **IsEmpty** - întoarce 0 dacă coada este goală;1 dacă are cel puțin un element. | + | {{ : |
- | <file cpp> | + | |
- | int Qempty(){ | + | ====2.3 Operații cu liste:==== |
- | if(front > rear) | + | *Adăugare la începutul listei |
- | | + | *Adăugare la sfârsitul listei |
- | | + | *Adăugarea |
- | } | + | *Ștergerea capului de listă |
- | </ | + | *Ștergerea unui element oarecare din listă |
- | * **Enqueue / Adăugarea** - adaugă un element | + | |
- | <file cpp> | + | =====3.Exerciții propuse pentru laborator===== |
- | void Qinsert(int item){ | + | 1. Creați o listă circulară, |
- | Q.rear++; | + | * Scrieți funcțiile care să scrie urmatoarele: |
- | Q.queue[Q.rear]==item; | + | |
- | } | + | * Să introducă un nou angajat inainte de cel care e " |
- | </ | + | * Să steargă angajatul cu un anumit număr de telefon introdus.\\ |
- | * **Dequeue/ | + | |
- | <file cpp> | + | |
- | void Qdelete(){ | + | |
- | int item; | + | |
- | if( Qempty() ) | + | |
- | return -1; | + | |
- | else { | + | |
- | elem = Q.queue[Q.front]; | + | |
- | front ++; | + | |
- | return item; | + | |
- | } | + | |
- | } | + | |
- | </ | + | |
- | ====3.3 Clasificare==== | + | 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ă. | ||
- | * **Dequeue** - (sau coadă cu dublu acces) este o structură de tip coadă în care însă accesul (introducere/ | + | 3. Să se construiasca o lista liniara simplu inlantuita |
- | De cele mai multe ori sunt implementate folosind liste dublu înlănțuite.\\ \\ | + | |
- | Dintr-un anume punct de vedere, se poate considera că atât stiva cât si coada clasică sunt specializări ale tipului abstract dequeue întrucât ambele | + | |
- | {{ : | + | |
- | }}* **Priority queue** - Coada prioritară reprezintă un tip de coadă în care fiecare element are asociată o anume prioritate.\\ | + | |
- | În aceste condiții, | + | |
- | * **Enqueue** - adaugă la coadă un element cu prioritatea specificată\\ | + | |
- | * **Dequeue** - extrage elementul cu cea mai mare prioritate\\ | + | |
- | * **Front** - examinează elementul cu cea mai mare prioritate fără a-l extrage | + | |
- | =====4 Exerciții propuse ===== | + | 4. Adunaţi 2 polinoame rare, reprezentând fiecare polinom printr-o listă înlănţuită, |
- | ==== 4.1 Exerciții clasice ==== | + | 5. Pentru laboratorul |
- | 1. **FIFO buffer** | + | |
- | O coadă este o modalitate folositoare | + | |
- | Un buffer FIFO stochează date pe principiul " | + | |
- | Datele sunt scrise | + | |
- | **Implementare generală**\\ | + | Descarcati arhiva de {{ :laboratoare: |
- | 1) Definite structură:head, | + | <code bash> |
- | 2) Se realizează funcția de inițializare a cozii cu bufferul dat și marimea.\\ | + | student@sda-ab-vm: |
- | 3) Se realizează funcția de citire a celor nbytes din coadă;nr. citit de biți se returnează\\ | + | --2017-03-02 20: |
- | 3.1 Pentru nbytes:se verifică dacă sunt date valabile | + | Resolving elf.cs.pub.ro |
- | 3.2 Daca da, se ia un byte din buffer și se incrementează coada.\\ | + | Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|: |
- | 3.3 Se verifica apoi dacă s-a terminat parcurgerea pentru a se reinițializa coada cu 0.\\ | + | HTTP request sent, awaiting response... 200 OK |
- | 3.4 În cazul în care nu sunt date valabile se returnează nr. de bytes.\\ | + | Length: 2368 (2,3K) [application/zip] |
- | 4) Se realizează funcția de scriere a celor nbytes din coadă.\\ | + | Saving to: ‘lab1-skel.zip’ |
- | 4.1 Pentru nbytes:inițial se verifică dacă este spațiu în buffer | + | |
- | //[Bonus]// Generarea in mod random a datelor de intrare și prelucrarea lor cu ajutorul funcțiilor de mai sus;astfel valorile folosite vor fi introduse de la tastatură | + | |
- | 2.Implementați pentru o structură de tip stivă funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală au stivă plină). | + | lab1-skel.zip |
- | ====4.2 Exercitii alternative | + | 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368] |
- | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | + | |
- | Pentru acest laborator sunt două exerciții, primul cu stive și al doilea cu cozi. Fiecare are mai multe task-uri. Urmăriți cu atenție comentariile din fișierele sursă. | + | 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: | ||
+ | </ | ||
- | ====4.3 Opţional - de interviu==== | + | Pentru compilare folositi comanda '' |
- | 1. Implementaţi o stivă folosind două cozi. | + | ====Probleme opţionale - de interviu==== |
- | 2. Implementaţi o coadă folosind două stive.(utilizarea apelurilor recursive ale unor funcţii se contorizează ca folosirea unei stive) | + | 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) |
- | 3. Implementaţi o stivă cu valori întregi şi o funcţie care obţine valoarea maximă din stivă. Pentru interviu se cere ca funcţia să aibă complexitate | + | 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. |
- | 4. Se dă un vector | + | 3. Se dă o listă |