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 Urmatoarea versiune Ambele părți următoarea reviziune | ||
|
laboratoare:laborator-03 [2017/02/14 18:15] sebastian.cancel |
laboratoare:laborator-03 [2017/02/20 00:45] florina_elena.barbu [3.3 Clasificare] |
||
|---|---|---|---|
| Linia 13: | Linia 13: | ||
| începem cu ultima, pusă deasupra teancului. | începem cu ultima, pusă deasupra teancului. | ||
| - | #poza stiva# | + | {{ : |
| ====2.2 Operații cu stive==== | ====2.2 Operații cu stive==== | ||
| Definim structura astfel: | Definim structura astfel: | ||
| - | <code> | + | <file cpp> |
| struct stack{ | struct stack{ | ||
| int s[size]; | int s[size]; | ||
| int top; | int top; | ||
| } st; | } st; | ||
| - | </code> | + | </file> |
| * **Verificăm dacă stiva e plină sau goală** | * **Verificăm dacă stiva e plină sau goală** | ||
| - | <code> | + | <file cpp> |
| int st_full(){ //int st_empty{ | int st_full(){ //int st_empty{ | ||
| | | ||
| Linia 33: | Linia 33: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </file> |
| * **Adăugarea** | * **Adăugarea** | ||
| - | <code> | + | <file cpp> |
| void push(int item){ | void push(int item){ | ||
| | | ||
| | | ||
| } | } | ||
| - | </code> | + | </file> |
| * **Ștergerea** | * **Ștergerea** | ||
| - | <code> | + | <file cpp> |
| int pop(){ | int pop(){ | ||
| int item; | int item; | ||
| Linia 49: | Linia 49: | ||
| | | ||
| } | } | ||
| - | </code> | + | </file> |
| **// | **// | ||
| Linia 55: | Linia 55: | ||
| 2.Când ștergem un element, | 2.Când ștergem un element, | ||
| 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste înlănțuite**.\\ | 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste înlănțuite**.\\ | ||
| + | |||
| + | =====3 Ce este o coadă? | ||
| + | |||
| + | ====3.1 Definiție ==== | ||
| + | O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, | ||
| + | |||
| + | {{ : | ||
| + | |||
| + | ====3.2 Operații cu cozi==== | ||
| + | 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(){ | ||
| + | | ||
| + | return 1; | ||
| + | | ||
| + | } | ||
| + | </ | ||
| + | * **Enqueue / Adăugarea** - adaugă un element (entitate) în coadă.Adăugarea se poate face doar la sfârșitul cozii. | ||
| + | <file cpp> | ||
| + | void Qinsert(int item){ | ||
| + | | ||
| + | | ||
| + | } | ||
| + | </ | ||
| + | * **Dequeue/ | ||
| + | <file cpp> | ||
| + | void Qdelete(){ | ||
| + | int item; | ||
| + | if( Qempty() ) | ||
| + | return -1; | ||
| + | else { | ||
| + | elem = Q.queue[Q.front]; | ||
| + | front ++; | ||
| + | return item; | ||
| + | } | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | ====3.3 Clasificare==== | ||
| + | |||
| + | * **Dequeue** - (sau coadă cu dublu acces) este o structură de tip coadă în care însă accesul (introducere/ | ||
| + | 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 se pot implementa folosind dequeue (și restrângând operațiile ce se realizează asupra sa).\\ | ||
| + | {{ : | ||
| + | }}* **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 din coadă.\\ | ||
| + | |||
| + | =====4 Exerciții===== | ||
| + | * **FIFO buffer** | ||
| + | O coadă este o modalitate folositoare de a stoca date care provin in mod asincronic de la un microcontroler periferic, dar care nu pot fi citite imediat. Un bun exemplu ar fi stocarea de biți proveniți de la un UART (Universal asynchronous receiver/ | ||
| + | Un buffer FIFO stochează date pe principiul " | ||
| + | Datele sunt scrise in capul cozii și citite de la coadă.Dacă parcurgerea are loc de la coadă spre cap, | ||
| + | |||
| + | **Implementare generală**\\ | ||
| + | //[0.25p]// 1) Definite structură: | ||
| + | //[0.25p]// 2) Se realizează funcția de inițializare a cozii cu bufferul dat și marimea.\\ | ||
| + | //[0.75p]// 3) Se realizează funcția de citire a celor nbytes din coadă;nr. citit de biți se returnează\\ | ||
| + | 3.1 Pentru nbytes:se verifică dacă sunt date valabile (dacă coada e diferită de cap)\\ | ||
| + | 3.2 Daca da, se ia un byte din buffer și se incrementează coada.\\ | ||
| + | 3.3 Se verifica apoi dacă s-a terminat parcurgerea pentru a se reinițializa coada cu 0.\\ | ||
| + | 3.4 În cazul în care nu sunt date valabile se returnează nr. de bytes.\\ | ||
| + | //[0.75p]// 4) Se realizează funcția de scriere a celor nbytes din coadă.\\ | ||
| + | 4.1 Pentru nbytes: | ||
| + | //[Bonus 1p]// 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ă | ||
| + | |||
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
