Diferență între revizuiri ale paginii „SDA Lucrarea 4”
Linia 257: | Linia 257: | ||
Implementați funcțiile definite în header într-un fișier <code>linkedQueue.c</code>. | Implementați funcțiile definite în header într-un fișier <code>linkedQueue.c</code>. | ||
</li> | </li> | ||
− | <li></li> | + | <li>Scrieți o altă sursă, <code>main.c</code> în care să creați trei cozi: <code>inQueue</code>, <code>shortStringsQueue</code> și <code>longStringsQueue</code>. Citiți conținutul fișierului de mai jos linie cu linie și inserați-le în <code>inQueue</code>. Apoi extrageti elementele din <code>inQueue</code> și dacă ele sunt mai lungi de 10 caractere, inserați-le în <code>longStringQueue</code> iar dacă nu, inserați-le în <code>shortStringsQueue</code>. Apoi extrageți elementele din <code>shortStringsQueue</code> și afișați-le pe ecran, urmate de elementele din <code>longStringsQueue</code>. |
+ | |||
+ | Observație: În contextul curent, utilizarea cozilor în programul de mai sus nu este necesar. Cozile se utilizează în practică în două situații: | ||
+ | # Când există două procese sau fire de execuție care funcționează în paralel, și din care unul adaugă elemente în coadă iar celălalt consumă. | ||
+ | # Când același proces extrage elemente din coadă dar în același timp generează alte elemente în coadă pentru procesare ulterioră (vom vedea acest lucru la capitolul parcurgeri de arbori). | ||
+ | </li> | ||
</ol> | </ol> |
Versiunea de la data 5 aprilie 2016 12:05
În acest laborator se vor implementa stive și cozi cu vectori și liste înlănțuite.
Coada
Coada este o structură de date de tip FIFO (First In First Out), care stochează o colecție de elemente în ordinea în care au fost adăugate.
Coada are următoarele proprietăți:
- Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
- Numărul de elemente ce poate fi stocat de structură este nelimitat sau limitat, în funcție de implementare.
- Elementele stocate în coadă sunt de același fel.
- Elementele pot fi adăugate doar la unul din capete și extrase doar de la celălalt - primul element inserat este primul care este extras.
Secvența suportă următoarele operații de bază:
- Interogarea numărului de elemente din coadă.
- Verificarea dacă coada este goală.
- Verificarea dacă coada este plină (pentru cozi limitate).
- Adăugarea unui element în coadă (push).
- Extragerea unui element din coadă (pop).
- Vizualizarea unui element din coadă fără extragerea acestuia (peek).
Implementarea cozii cu liste
Pentru aplicațiile care folosesc doar funcționalitatea de bază a cozii (operațiile descrise mai sus), nu va necesară utilizarea unei liste dublu înlănțuite. Prin urmare, având o structură în care memorăm ultimul și primul nod dintr-o listă, adăugarea se va face întotdeauna după ultimul nod, iar extragerea va fi întotdeauna din primul nod. Definim în continuare structura de tip nod și structura ce va memora o coadă de șiruri de caractere:
struct SimplyLinkedNode {
char * string; // pointer la primul caracter din șir, aceasta este valoarea stocată în nod
struct SimplyLinkedNode * next; // pointer la nodul următor.
};
#define UNLIMITED_SIZE (unsigned)-1
struct LinkedQueue {
struct SimplyLinkedNode * firstNode;
struct SimplyLinkedNode * lastNode;
unsigned size;
unsigned maxSize;
};
Se observă că cele două structuri sunt foarte similare cu definițiile pentru secvențele implementate cu liste simplu înlănțuite, diferențele constau în operațiile ce vor fi definite și modul lor de implementare. Ce a apărut în plus este câmpul maxSize
care va fi inițializat cu valoarea numărului maxim de elemente din coadă, sau UNLIMITED_SIZE
dacă coada este nelimitată. -1 este convertit la valoare fără semn în macro-ul UNLIMITED_SIZE
pentru a obține cea mai mare valoare de tip unsigned int
. Ne amintim că -1 în complement față de 2 se calculează plecând de la valoarea pozitivă (1) pe care o negăm pe biți și la care adunăm 1, obținând 0xFFFFFFFF, sau 4294967295.
Crearea unui LinkedQueue
Pentru crearea unei cozi noi, se definește următoarea funcție:
/**
* Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată.
* @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE dacă aceasta
* este nelimitată.
* @return pointer la o structura de tip LinkedQueue.
*/
struct LinkedQueue * createLinkedQueue(unsigned maxSize);
Implementarea acestei funcții se face folosind următorul algoritm:
- Se alocă memorie pentru o variabilă de tip
struct LinkedQueue
. - Se inițializează câmpul
maxSize
din strutură cu valoarea argumentuluimaxSize
. - Se inițializează
size
cu 0. - Se inițializează
firstNode
șilastNode
cuNULL
. - Se întoarce adresa variabilei de tip
struct LinkedQueue
.
Interogarea dimensiunii
Pentru interogarea dimensiunii, se definește următoarea funcție:
/**
* Functia intoarce numarul de elemente valide din coada specificata.
* @param queue coada pentru care se cere dimensinea.
* @return numarul de elemente valide din coada queue.
*/
unsigned linkedQueueSize(struct LinkedQueue * queue);
Implementarea acestei funcții se face întorcând direct valoarea câmpului size
din structură.
Pentru a verifica dacă structura este goală se definește următoarea funcție:
/**
* Functia intoarce 1 dacă coada specificată este goală.
* @param queue coada pentru care se cere dimensiunea.
* @return 1 dacă coada este goală, 0 dacă nu
*/
int linkedQueueIsEmpty(struct LinkedQueue * queue);
Implementarea acestei funcții se face întorcând 1 dacă size
este egal cu 0.
Pentru a verifica dacă structura este plină se definește următoarea funcție:
/**
* Functia intoarce 1 dacă coada specificată este plină.
* @param queue coada pentru care se cere dimensiunea.
* @return 1 dacă coada este plină, 0 dacă nu
*/
int linkedQueueIsFull(struct LinkedQueue * queue);
Implementarea acestei funcții se face întorcând 1 dacă size
este egal cu maxSize
.
Adăugarea unui element - push
Pentru adăugarea unui element newString în coadă, se definește următoarea funcție:
/**
* Functia inserează elementul newString în coadă.
* @param queue coada la care se adaugă elementul.
* @param newString elementul ce trebuie adăugat.
*/
void linkedQueuePush(struct LinkedQueue * queue, char * newString);
Adăugarea unui element în coadă se face urmând pașii de mai jos.
- Dacă coada este plină, se afișează un mesaj de eroare și funcția se încheie.
- Se alocă memorie pentru un nou nod
tmpNode
în caretmpNode->next
este inițializat cuNULL
șitmpNode->string
cunewString
. - Dacă
size
este 0,firstNode
devinetmpNode
, altfellastNode->next
devinetmpNode
. lastNode
devinetmpNode
.size
se incrementează cu 1.
Extragerea unui element - pop
Pentru extragerea unui element din coadă, se definește următoarea funcție:
/**
* Functia extrage următorul element din coadă.
* @return următorul element din coadă sau NULL dacă coada este goală.
*/
char * linkedQueuePop(struct LinkedQueue * queue);
Extragerea unui element din coadă se face urmând pașii de mai jos.
- Dacă coada este goală, se afișează un mesaj de eroare și se întoarce
NULL
. - Se definește un pointer la nod numit
tmpNode
care ia valoarea luifirstNode
. firstNode
ia valoarea luifirstNode->next
.- Dacă
size
este 1,lastNode
devineNULL
. size
se decrementează cu 1.- Se definește o variabilă
returnString
care ia valoareatmpNode->string
. - Se dezalocă memoria pentru
tmpNode
. - Se întoarce valoarea
returnString
.
Vizualizarea primului element din coadă - peek
Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea funcție:
/**
* Functia întoarce următorul element din coadă, fără a-l extrage.
* @return următorul element din coadă sau NULL dacă coada este goală.
*/
char * linkedQueuePeek(struct LinkedQueue * queue);
Extragerea unui element din coadă se face urmând pașii de mai jos.
- Dacă coada este goală, se afișează un mesaj de eroare și se întoarce
NULL
. - Se întoarce valoarea
firstNode->string
.
Ștergerea unui LinkedQueue
Pentru ștergerea unui LinkedQueue
se definește următoarea funcție.
/**
* Functia dezalocă memoria folosită de coada specificată.
* @param queue coada care trebuie ștearsă.
*/
void deleteLinkedQueue(struct LinkedQueue * queue);
Ștergerea unui LinkedQueue
se realizează felul următor:
- Se utilizează un pointer temporar
tmpNode
pentru a itera peste toate nodurile din listă. - Pentru fiecare nod, se șterge memoria alocată pentru
tmpNode->string
și pentru nod în sine (cu grijă să nu se piardă legătura la nodul următor). - Se dezalocă memoria alocată pentru structura de tip
struct LinkedQueue
.
Exerciții
Săptămâna 1
- Se dă fișierul header
linkedQueue.h
de mai jos:struct SimplyLinkedNode { char * string; // pointer la primul caracter din șir, aceasta este valoarea stocată în nod struct SimplyLinkedNode * next; // pointer la nodul următor. }; #define UNLIMITED_SIZE (unsigned)-1 struct LinkedQueue { struct SimplyLinkedNode * firstNode; struct SimplyLinkedNode * lastNode; unsigned size; unsigned maxSize; }; /** * Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată. * @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE dacă aceasta * este nelimitată. * @return pointer la o structura de tip LinkedQueue. */ struct LinkedQueue * createLinkedQueue(unsigned maxSize); /** * Functia intoarce numarul de elemente valide din coada specificata. * @param queue coada pentru care se cere dimensinea. * @return numarul de elemente valide din coada queue. */ unsigned linkedQueueSize(struct LinkedQueue * queue); /** * Functia intoarce 1 dacă coada specificată este goală. * @param queue coada pentru care se cere dimensiunea. * @return 1 dacă coada este goală, 0 dacă nu */ int linkedQueueIsEmpty(struct LinkedQueue * queue); /** * Functia intoarce 1 dacă coada specificată este plină. * @param queue coada pentru care se cere dimensiunea. * @return 1 dacă coada este plină, 0 dacă nu */ int linkedQueueIsFull(struct LinkedQueue * queue); /** * Functia inserează elementul newString în coadă. * @param queue coada la care se adaugă elementul. * @param newString elementul ce trebuie adăugat. */ void linkedQueuePush(struct LinkedQueue * queue, char * newString); /** * Functia extrage următorul element din coadă. * @return următorul element din coadă sau NULL dacă coada este goală. */ char * linkedQueuePop(struct LinkedQueue * queue); /** * Functia întoarce următorul element din coadă, fără a-l extrage. * @return următorul element din coadă sau NULL dacă coada este goală. */ char * linkedQueuePeek(struct LinkedQueue * queue); /** * Functia dezalocă memoria folosită de coada specificată. * @param queue coada care trebuie ștearsă. */ void deleteLinkedQueue(struct LinkedQueue * queue);
Implementați funcțiile definite în header într-un fișier
linkedQueue.c
. - Scrieți o altă sursă,
main.c
în care să creați trei cozi:inQueue
,shortStringsQueue
șilongStringsQueue
. Citiți conținutul fișierului de mai jos linie cu linie și inserați-le îninQueue
. Apoi extrageti elementele dininQueue
și dacă ele sunt mai lungi de 10 caractere, inserați-le înlongStringQueue
iar dacă nu, inserați-le înshortStringsQueue
. Apoi extrageți elementele dinshortStringsQueue
și afișați-le pe ecran, urmate de elementele dinlongStringsQueue
. Observație: În contextul curent, utilizarea cozilor în programul de mai sus nu este necesar. Cozile se utilizează în practică în două situații:- Când există două procese sau fire de execuție care funcționează în paralel, și din care unul adaugă elemente în coadă iar celălalt consumă.
- Când același proces extrage elemente din coadă dar în același timp generează alte elemente în coadă pentru procesare ulterioră (vom vedea acest lucru la capitolul parcurgeri de arbori).