Appunti di informatica sulle code

CODE

• Una coda è una sequenza di elementi (tutti dello stesso tipo) in cui l’inserimento e l’eliminazione di elementi avvengono secondo la regola seguente:
  • L’elemento che viene eliminato tra quelli presenti nella coda deve essere quello che è stato inserito per primo.

• Si parla di gestione FIFO (per "First In, First Out").

• InCoda 2
• InCoda 7
• OutCoda 2
• InCoda 5
• InCoda 9
• OutCoda 7

Il tipo CODA è un ADT <S,F,C> dove

• S = {coda, atomo, boolean}
  • coda è il dominio di interesse, atomo è il dominio degli elementi che formano le liste

FUNZIONI

• F = {incoda, front, null, outcoda}
  • incoda : atomo x coda -> coda
    • inserisce un elemento alla fine della coda
  • front : coda -> atomo
    • ritorna l’elemento in cima alla lista
  • null : coda -> boolean
    • ritorna il valore vero se la coda è vuota
  • outcoda : coda -> coda
    • ritorna la coda privata dell'elemento in cima

• C = coda vuota,
  • è la costante che denota la coda priva di elementi

CODE

• Una coda è una sequenza di elementi (tutti dello stesso tipo) in cui l'inserimento e l'eliminazione di elementi avvengono secondo la regola seguente:
  • L'elemento che viene eliminato tra quelli presenti nella coda deve essere quello che è stato inserito per primo.
• Si parla di gestione FIFO (per "First In, First Out").

FUNZIONI

Il tipo CODA è un ADT <S,F,C> dove

• S = {coda, atomo, boolean}
  • coda è il dominio di interesse, atomo è il dominio degli elementi che formano le liste

F = {incoda, front, null, outcoda}

• incoda : atomo x coda -> coda
  • inserisce un elemento alla fine della coda
• front : coda -> atomo
  • ritorna l'elemento in cima alla lista
• null : coda -> boolean
  • ritorna il valore vero se la coda è vuota
• outcoda : coda -> coda
  • ritorna la coda privata dell'elemento in cima

C = coda vuota,

• è la costante che denota la coda priva di elementi

CODE MEDIANTE ARRAY

DEFINIZIONE

typedef int TAtomo;

typedef struct StCoda {

int primo, ultimo, NMax;

TAtomo * e;

} Coda;

FUNZIONI

int InizializzaCoda( Coda *PC, int NElemMax )

{

PC->e=(TAtomo*)malloc(sizeof(TAtomo)*NElemMax);

if( PC->e == NULL ) return 0;;

PC->ultimo = 0;

PC->primo = -1;

return PC->NMax = NElemMax;

}

int null( Coda C ) {

return (C.primo == -1);

}

int full( Coda C ) {

return (C.primo == C.ultimo);

}

int outcoda ( Coda *PC ) {

if( null(*PC) ) return 0;

if( PC->primo == PC ->NElemMax) PC->primo = 0

else (PC->primo)++;

if( PC->ultimo == PC->primo ) PC ->primo =-1

return 0;

}

TAtomo front( Coda C ) {

if( null(C) ) return 0;

return C.e[C.primo];

}

int incoda (Coda *PC, TAtomo A ) {

if( full(*PC)) return 0;

if( null(*PC)

{ PC -> ultimo =1;

PC -> primo = 0;

PC->e[PC->primo] = A

}

else {

PC->e[PC->ultimo] = A

if (PC->ultimo == PC -> NelemMax - 1) PC->ultimo = 0;

else PC->ultimo ++;

}

return 1;

IMPLEMENTAZIONI CONCATENATE (PUNTATORI)

DEFIN IZIONE

typedef int TAtomo;

typedef struct Stelem {

struct Stelem *next;

TAtomo info;

} elem;

typedef struct StCoda {

elem *primo, *ultimo;

} TCoda, *PTCoda;