Stive si cozi

11.2. Stive si cozi

2020/03/01 in Programare in C

In exercitiul 7.1. s-a implementat o stiva cu ajutorul unui tablou. In general, o stiva se implementeaza printr-o lista simplu inlantuita.

O stiva este o lista simplu inlantuita gestionata conform principiului LIFO (Last In First Out) - ultimul pus in stiva este primul care este scos.

Ca si lista stiva are doua capete, baza si varful stivei.

Asupra unei stive se definesc cateva operatii, dintre care cele mai importante sunt:

push - pune un element pe stiva;
pop - scoate un element din stiva;
clear - sterge (videaza) stiva.

Primele doua operatii se realizeaza in varful stivei. Astfel, daca se scoate un element din stiva, atunci acesta este cel din varful stivei si, in continuare, cel pus anterior lui pe stiva ajunge in varful stivei.

Daca un element se pune pe stiva, atunci acesta se pune pe varful stivei si in continuare el ajunge in varful stivei.

Pentru a implementa o stiva printr-o lista simplu inlantuita va trebui sa identificam baza si varful stivei cu capetele LSI. Exista doua posibilitati:

nodul spre care pointeaza variabila prim este baza stivei, iar nodul spre care pointeaza variabila ultim este varful stivei;
nodul spre care pointeaza variabila prim este varful stivei, iar nodul spre care pointeaza variabila ultim este baza stivei.

In cazul 1, functiile push si pop se identifica prin functiile adauga si respectiv sun, definite in paragrafele 11.1.3.4 si respectiv 11.1.4.3.

Daca functia adauga este eficienta, in schimb functia sun nu este eficienta.

In cazul 2, functiile push si pop se identifica prin functiile iniprim si respectiv spn, definite in paragrafele 11.1.3.1 si respectiv 11.1.4.1.

In acest caz, ambele functii sunt eficiente si de aceea sunt recomandate pentru implementarea unei stive printr-o LSI.

Operatiile push si pop pot fi schematizate ca in figura de mai jos.

In sfarsit, sa adaugam ca vidarea stivei se realizeaza cu ajutorul functiei sterglist definita in paragraful 11.1.5.

In concluzie, o stiva se poate implementa printr-o lista simplu inlantuita, pentru care se pot utiliza functiile:

iniprim - realizeaza operatia push;
spn - realizeaza operatia pop;
sterglist - realizeaza operatia clear.

Stivele pot fi implementate ca in exercitiul 7.1, folosind liste care la randul lor se implementeaza cu ajutorul tabloului de pointeri tpnod (vezi paragraful 11.1).

In acest caz, la baza stivei se afla nodul spre care pointeaza elementul tpnod[0], iar in varful stivei se afla nodul spre care pointeaza elementul tpnod[itpnod-1].

In acest caz se vor utiliza functiile definite in paragraful 11.1, astfel:

tpadauga - realizeaza operatia push;
tpspn - realizeaza operatia pop;
tpsterglist - realizeaza operatia clear.

De obicei se mai definesc doua operatii asupra stivei, isempty si isfull.

Prima se defineste printr-o functie care returneaza valoarea 1 daca stiva este vida si 0 in caz contrar. Cea de-a doua returneaza valoarea 1 daca stiva este plina si 0 in caz contrar. Aceste functii se definesc simplu astfel:

typedef enum {false, true} Boolean;
Boolean isempty() {
   extern int itpnod;
   return itpnod == 0;
}

Boolean isfull() {
   extern int itpnod;
   return itpnod >= MAX;
}

Un alt principiu de gestiune a LSI este principiul FIFO (First In First Out), cand primul element introdus in lista este si primul care este scos din lista.

Despre o lista care este gestionata in acest fel se spune ca este o coada.

Cele doua capete ale listei simplu inlantuite care implementeaza o coada sunt si capetele cozii. Asupra cozilor se definesc trei operatii, ca si asupra stivelor, folosind urmatoarele functii:

adauga - realizeaza operatia push ce pune un element in coada;
spn - realizeaza operatia pop ce scoate un element in coada;
sterglist - realizeaza operatia clear de vidare a unei cozi.

Pentru a respecta principiul FIFO, vom pune un element in coada folosind functia adauga si vom scoate un element din coada folosind functia spn. Deci, la un capat al cozii se pun elemente in coada, iar la celalalt capat se scot elementele din coada.

Ambele functii, adauga si spn sunt eficiente. Ele sunt schematizate in figura de mai jos.

Stergerea unei liste se realizeaza cu ajutorul functiei sterglist.

Cozile definite ca mai sus corespund celor din viata de zi cu zi si din aceasta cauza ele se folosesc frecvent la simularea fenomenelor reale.

Stivele se utilizeaza la descrierea proceselor recursive, inversarea ordinii elementelor unei multimi ordonate, etc.

Exercitii:

11.8. Intr-o gara se considera un tren de marfaale carui vagoane sunt inventariate intr-o lista, in ordinea vagoanelor. Lista contine, pentru fiecare vagon, urmatoarele date:

codul vagonului (9 cifre);
codul continutului vagonului (9 cifre);
adresa expeditorului (4 cifre);
adresa destinatarului (4 cifre).

Deoarece in gara se inverseaza pozitia vagoanelor, se cere listarea datelor despre vagoane in noua lor ordine.

In acest scop, se creeaza o stiva in care se pastreaza datele fiecarui vagon. Datele corespunzatoare unui vagon constituie un element al stivei, adica un nod al unei LSI. Dupa ce datele au fost introduse pe stiva, ele se scot de acolo si se listeaza. In acest mod se obtine lista vagoanelor in ordine inversa celei initiale.

Stiva este o LSI pe care o gestionam folosind functiile iniprim si spn.

Aceste functii sunt generale si sunt definite in paragrafele 11.1.3.1 si respectiv 11.1.4.1.

Functia iniprim apeleaza functia incnod si elibnod, iar functia spn numai functia elibnod. Aceste doua funtii (incnod si elibnod) sunt specifice aplicatiei.

Functia principala apeleaza repetat functia iniprim pentru a pune datele pe stiva, apoi le scoate de pe stiva si le listeaza, pana cand aceasta devine vida.

Functia pcit_int a fost definita in paragraful 8.2.
Functia pcit_int_lim a fost definita in paragraful 8.3.

Programul 121 - Listare noduri LSI in ordine inversa

// needs debugging
#include <stdio.h>
#include <stdlib.h>

typedef struct tnod {
   long cvag;
   long cmarfa;
   int exp;
   int dest;
   struct tnod *urm;
} TNOD;

#include "FUNCTIA094B.C" /* pcit_int  */
#include "FUNCTIA094C.C" /* pcit_int_lim  */

int incnod(TNOD *p) {
/* incarca un nod cu datele despre vagoane */

   char t[255];
   char er[] = "s-a tastat EOF in pozitie rea\n";
   long cod;
   long icod;
   
/* citeste cod vagon */
   for ( ; ; ) {
      printf("cod vagon: ");
      if (gets(t) == 0)
         return -1; /* nu mai sunt date */
      if(sscanf(t, "%ld", &cod) == 1 && cod >= 0 && cod <= 999999999)
         break;
      printf("cod vagon eronat\n");
   }
   p -> cmarfa = cod;   
   
/* citeste cod marfa */
   for ( ; ; ) {
      printf("cod marfa: ");
      if (gets(t) == 0)
         printf(er);
         return 0;
      if(sscanf(t, "%ld", &cod) == 1 && cod >= 0 && cod <= 999999999)
         break;
      printf("cod marfa eronat\n");
   }
   p -> cmarfa = cod;
   
/* citeste cod expeditor */
   if (pcit_int_lim("cod expeditor: ", 0, 9999, &icod) == 0) {
      printf(er);
      return 0;
   }
   p -> exp = icod;
   
/* citeste cod destinatar */
   if (pcit_int_lim("cod destinatar: ", 0, 9999, &icod) == 0) {
      printf(er);
      return 0;
   }
   p -> dest = icod;
   return 1;
}

void elibnod(TNOD *p) {
   free(p);
}

TNOD *iniprim() {
/* insereaza nodul curent inaintea primului nod al listei */
/* push */

   extern TNOD *prim, *ultim;
   TNOD *p;
   int n;

   n = sizeof(TNOD);
   if ((p = (TNOD *)malloc(n)) != 0 && (incnod(p) == 1)) {
      if (prim == 0) {
         prim = ultim = 0;
         p -> urm = 0;
      }
      else {
         p -> urm = prim;
         prim = p;
      }
      return p;
   }
   if (p == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
   elibnod(p);
   return 0;
}

void spn() {
/* sterge primul nod din lista */
/* pop */

   extern TNOD *prim, *ultim;
   TNOD *p;

   if (prim == 0) /* lista vida */
      return;
   p = prim;
   prim = prim -> urm;
   elibnod(p);
   if (prim == 0) /* lista a devenit vida */
      ultim = 0;
}

TNOD *prim, *ultim;

int main () {
/* listeaza inventarul vagoanelor in ordinea inversa citirii lor */

   prim = ultim = 0; /* la inceput lista este vida */
/* se creeaza lista apeland iniprim pana cand aceasta returneaza valoarea 0 */
   while (iniprim() != 0);
/* - se listeaza elementul din varful stivei si apoi se sterge din stiva;
   - se repeta pana cand stiva devine vida.*/
   while (prim != 0) {
      printf("cod vagon: %d\tcontinut: %d\n", prim -> cvag, prim -> cmarfa);
      printf("expeditor: %d\tdestinatar: %d\n", prim -> exp, prim -> dest);
      spn();
   }
}

11.9. Cozile se folosesc adesea la simularea fenomenelor reale pe calculator.

Un exemplu simplu de simulare cu ajutorul cozilor este descris mai jos.

Presupunem o agentie CEC mica, cu un singur ghiseu, care se deschide la ora 8. Agentia se inchide la ora 14, dar publicul aflat la coada este deservit in continuare. Cu alte cuvinte, dupa ora 16 publicul nu mai are voie sa intre in agentie ca sa se aseze la coada la ghiseu. Intrucat s-a constatat ca de obicei coada este destul de mare la ora inchiderii, se ridica problema oportunitatii deschiderii a inca unui ghiseu la agentia respectiva. In acest scop, se realizeaza o simulare pe calculator a situatiei existente, care sa stabileasca o medie a orelor suplimentare efectuate zilnic pe o perioada de un an.

Pentru a simula acest fenomen se au in vedere operatiile efectuate la ghiseu, dupa cum urmeaza:

Operatie	Timp de executie
Operatia 1	7
Operatia 2	7
Operatia 3	3
Operatia 4	3
Operatia 5	1
Total	21

Se vor genera numere pseudoaleatoare situate in intervalul [1, 21], iar operatia se defineste astfel:

Fie r un numar pseudoaleator din intervalul [1, 21]:

daca 1 <= r <= 7, atunci se realizeaza Operatia 1;
daca 8 <= r <= 14, atunci se realizeaza Operatia 2;
daca 15 <= r <= 17, atunci se realizeaza Operatia 3;
daca 18 <= r <= 20, atunci se realizeaza Operatia 4;
daca r = 21, atunci se realizeaza Operatia 5.

Numerele pseudoaleatoare pot fi generate folosind functiile random si srand din biblioteca limbajelor C si C++.

Functia random are prototipul:

int random(int n);

Ea returneaza un numar pseudoaleatoraflat in intervalul [0, n] (numar natural mai mic decat n).

Numerele pseudoaleatoare se genereaza printr-un proces de calcul iterativ. Acest proces porneste cu o valoare initiala care poate fi definita de programator apeland functia srand. Aceasta valoare initiala se numeste samanta sirului de numere pseudoaleatoare.

Functia random are prototipul:

void srand(unsigned n);

unde:

n	este valoarea la care se seteaza samanta dupa apelul functiei srand.

Ambele functii au prototipul in fisierul stdlib.h.

Programul de simulare a problemei indicate mai sus construieste o coada de asteptare cu persoanele care sosesc la agentie in intervalul de timp indicat mai sus.

Apeland functia random se determina operatia solicitata de fiecare persoana aflata la coada. Se scot elementele din coada respectand principiul FIFO si procesul continua pana la ora 16, cand se sisteaza operatia de adaugare. Se determina timpul necesar pentru realizarea operatiilor solicitate de persoanele aflate la coada.

Ramane de precizat modul in care vin persoanele la agentie. Vom presupune ca intervalul de timp intre doua persoane care vin la agentie este aleator si ca acesta este de maximum 15 minute. In acest caz, se poate apela functia random cu parametrul 15 si valoarea: random(15) + 1 va reprezenta intervalul in care soseste persoana urmatoare in agentie.

Avem 8 ore de lucru la ghiseu, deci timpcrt <= 8*60 = 480 minute.

O alta variabila care numara minutele rezultate din deservirea persoanelor care s-au aflat la coada la ghiseu este timpghiseu.

Valorile acestor variabile satisfac relatia: timpghiseu <= timpcrt.

Cand o persoana se asaza la coada, atunci timpcrt se mareste cu timpul dat de expresia: random(15) + 1.

Cand o persoana se scoate din coada (a fost deservita), timpghiseu se mareste cu timpul necesar pentru operatia solicitata de persoana respectiva, operatie care se defineste cu ajutorul expresiei: random(21) + 1.

Deoarece timpcrt defineste timpul curent (numarul de minute care s-au socotit incepand cu ora 8 si pana in momentul in care ultima persoana s-a asezat la coada), rezulta ca persoana din fata este deservita (scoasa din coada) numai daca:

timpghiseu + timp operatie persoana <= timpcrt
Astfel se adauga o noua persoana la coada daca timpcrt <= 480
Deasemenea, persoana din fata este deservita daca timpcrt > 480

Programul 122 - Simulare coada agentie CEC

// needs debugging, may work in Turbo C
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct tnod {
   int timpoperatie;
   struct tnod *urm;
} TNOD;

#define MAXTIMP 480
#define INTERVAL 15

int incnod(TNOD *p) {
/* - incarca nodul curent daca timpul curent nu depaseste cel admis si returneaza 1;
   -  altfel returneaza -1.*/

   extern int timpcrt;
   int r;
   
/* determina timpul, in minute, la care soseste persoana la agentie */
   timpcrt += random(INTERVAL) + 1;
   if (timpcrt > MAXTIMP)
      return -1; /* agentie inchisa */   
   
/* determina operatia si pastreaza in nod timpul necesar operatiei respective */
   r = random(21) + 1;
   if (r <= 7)
      r = 5;
   else
      if (r <= 14)
         r = 7;
      else
         if (r <= 17)
            r = 10;
         else
            if (r <= 20)
               r = 20;
            else
               r = 25;
   p -> timpoperatie = r;
   return 1;
}  

void elibnod(TNOD *p) {
/* elibereaza zona de memorie ocupata de nodul listei spre care pointeaza p */
   free(p);
}

#include "FUNCTIA119C.C" /* adauga */

void spn() {
/* sterge primul nod al listei (cozii) */

   extern TNOD *prim, *ultim;
   TNOD *p;

   if (prim == 0) /* lista vida */
      return;
   p = prim;
   prim = prim -> urm;
   elibnod(p);
   if (prim == 0) /* lista a devenit vida */
      ultim = 0;
}

TNOD *prim, *ultim;
int timpcrt;

int main () {
/* simuleaza cozile de la o agentie CEC pe o perioada de 1 an */

   int timpghiseu;
   int i;

   for (i = 1; i <= 360; i++) {
      srand(i*10); /* seteaza samanta sirului pseudoaleator */
/* initializari la deschiderea agentiei */
      timpcrt = timpghiseu = 0;
      prim = ultim = 0; /* coada este vida */
      while (adauga())
/* ultima persoana sosita la agentie se pune la coada */
/* - se deservesc persoanele aflate la coada;
   - trebuie ca:
     1) prim != 0 (altfel nu exista coada);
     2) timpghiseu <= timpcrt. */
         while (prim != 0 && (timpghiseu <= timpcrt)) {
/* se deserveste prima persoana din coada */
            timpghiseu += prim -> timpoperatie;
/* se elimina din coada persoana deservita */
            spn();
         }
/* - se inchide agentia;
   - se deservesc in continuare persoanele aflate la coada la ghiseu */
      while(prim != 0) {
         timpghiseu += prim -> timpoperatie;
         spn();
      }
/* se afiseaza timpul suplimentar in minute */
      if (timpghiseu - 480 > 0) {
         printf("timp peste ora 16: %d minute\n", timpghiseu - 480);
         if (i%22 == 0) {
            printf("Actionati o tasta pentru a continua\n");
            getch();
         }
      }
   }
}

11.3. Lista circulara simplu inlantuita (LCSI)