Algoritmi e strutture dati - Specifiche: Code

Torna alla pagina di Algoritmi e strutture dati

---

 :: Algoritmi e strutture dati - Specifiche ::

Code

---

Sintassi

• creacoda: () -> coda
  Crea ed inizializza una coda alla sequenza vuota.
• codavuota: (coda) -> booleano
  Restituisce vero o falso a seconda che la coda sia vuota o no.
• leggicoda: (coda) -> tipoelem
  Legge il valore dell'elemento in testa alla coda.
• fuoricoda: (coda) -> coda
  Elimina l'elemento che si trova in testa alla coda.
• incoda: (tipoelem, coda) -> coda
  Aggiunge un elemento in fondo alla coda.

Semantica

• creacoda() = Q'
  Post: Q' = Λ
• codavuota(Q) = b
  Post: b = vero, se Q = Λ; b = falso altrimenti
• leggicoda(Q) = a
  Pre: Q = a₁, a₂, ... , a_n con n≥1
  Post: a = a₁
• fuoricoda(Q) = Q'
  Pre: Q = a₁, a₂, ... , a_n con n≥1
  Post: Q' = a₂, a₃, ... , a_n se n>1, Q' = Λ se n=1
• incoda(a, Q) = Q'
  Pre: Q = a₁, a₂, ... , a_n con n≥0
  Post: Q' = a₁, a₂, ... , a_n, a

Implementazione in C++

Realizzazione con vettore circolare

#define MAXL 100

typedef struct _coda {
   int testa, lung;
   tipoelem elementi[MAXL];
} coda;

coda Q;

• creacoda:
  

  
  void creacoda (coda *Q) {
     Q->testa = Q->lung = 0;
  }
  
• codavuota:
  

  
  boolean codavuota (coda *Q) {
     return (Q->lung == 0;
  }
  
• leggicoda:
  

  
  tipoelem codavuota (coda *Q) {
     if( !codavuota(Q))
        return (Q->elementi[Q->testa]);
  }
  
• fuoricoda:
  

  
  void fuoricoda (coda *Q) {
     if( !codavuota(Q)) {
        Q->testa = (Q->testa+1) % MAXL;
        Q->lung = Q->lung -1;
     }
  }
  
• incoda:
  

  
  tipoelem incoda (tipoelem a, coda *Q) {
     if( Q->lung == MAXL)
        printf("Coda satura\n");
     else {
        Q->elementi[(Q->testa + Q.lung) % MAXL] = a;
        Q->lung++;
     }
  }
  

---

Torna alla pagina di Algoritmi e strutture dati