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 19:28] 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 61: | Linia 61: | ||
O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, | O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, | ||
- | #poza coada# | + | {{ : |
====3.2 Operații cu cozi==== | ====3.2 Operații cu cozi==== | ||
Definim structura astfel: | Definim structura astfel: | ||
- | <code> | + | <file cpp> |
struct queue{ | struct queue{ | ||
int queue[size]; | int queue[size]; | ||
Linia 71: | Linia 71: | ||
}Q | }Q | ||
int front = 0; | int front = 0; | ||
- | </code> | + | </file> |
* **IsEmpty** - întoarce 0 dacă coada este goală;1 dacă are cel puțin un element. | * **IsEmpty** - întoarce 0 dacă coada este goală;1 dacă are cel puțin un element. | ||
- | <code> | + | <file cpp> |
int Qempty(){ | int Qempty(){ | ||
| | ||
Linia 80: | Linia 80: | ||
| | ||
} | } | ||
- | </code> | + | </file> |
* **Enqueue / Adăugarea** - adaugă un element (entitate) în coadă.Adăugarea se poate face doar la sfârșitul cozii. | * **Enqueue / Adăugarea** - adaugă un element (entitate) în coadă.Adăugarea se poate face doar la sfârșitul cozii. | ||
- | <code> | + | <file cpp> |
void Qinsert(int item){ | void Qinsert(int item){ | ||
| | ||
| | ||
} | } | ||
- | </code> | + | </file> |
* **Dequeue/ | * **Dequeue/ | ||
- | <code> | + | <file cpp> |
void Qdelete(){ | void Qdelete(){ | ||
int item; | int item; | ||
Linia 100: | Linia 100: | ||
} | } | ||
} | } | ||
- | </code> | + | </file> |
====3.3 Clasificare==== | ====3.3 Clasificare==== | ||
Linia 107: | Linia 107: | ||
De cele mai multe ori sunt implementate folosind liste dublu înlănțuite.\\ \\ | 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).\\ | 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).\\ | ||
- | # poza # | + | {{ : |
- | * **Priority queue** - Coada prioritară reprezintă un tip de coadă în care fiecare element are asociată o anume prioritate.\\ | + | }}* **Priority queue** - Coada prioritară reprezintă un tip de coadă în care fiecare element are asociată o anume prioritate.\\ |
În aceste condiții, | În aceste condiții, | ||
* **Enqueue** - adaugă la coadă un element cu prioritatea specificată\\ | * **Enqueue** - adaugă la coadă un element cu prioritatea specificată\\ | ||
Linia 121: | Linia 121: | ||
**Implementare generală**\\ | **Implementare generală**\\ | ||
- | //[0.25p]// 1)Definite structură: | + | //[0.25p]// 1) Definite structură: |
- | //[0.25p]// 2)Se realizează funcția de inițializare a cozii cu bufferul dat și marimea.\\ | + | //[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ă\\ | + | //[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.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.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.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.\\ | 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ă\\ | + | //[0.75p]// 4) Se realizează funcția de scriere a celor nbytes din coadă.\\ |
- | 4.1 Pentru nbytes: | + | 4.1 Pentru nbytes: |
- | //[Bonus 1p]// | + | //[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ă |