Code con Lista di Puntatori
Per la maggior parte degli algoritmi su Code, Pile e Liste, utilizzeremo una struttura dati ricorrente che contiene un campo informazione e uno che punta al successivo elemento.
typedef struct nodo *pnodo;
struct nodo{
int inf;
pnodo *next;
};
La coda è una struttura dati di tipo FIFO (First In First Out) e nella sua forma dinamica ha ottime prestazioni.
L'idea base è quella di utilizzare due puntatori Q (in realtà dovrebbe essere H perchè sta per HEAD = testa) e T (TAIL = coda), in maniera da rendere O(1) le due operazioni di inserimento e di cancellazione.
Vediamo prima che dichiarazioni dobbiamo effettuare nel main e successivamente vedremo i codici delle funzioni di
ENQUEUE,
DEQUEUE e
STAMPA:
main(){
pnodo Q = NULL, /* ricordo che è sempre bene inizializzare a NULL tutti i puntatori */
T = NULL;
int queue_in, /* elemento da inserire in coda */
queue_out; /* elemento tolto dalla coda */
/* ... codice vario ... */
/* INSERIMENTO IN CODA */
enqueue(&T, queue_in);
if( Q == NULL) /* vuol dire che era il primo inserimento */
Q = T;
/* TOGLIAMO DALLA CODA */
queue_out = dequeue(&Q);
if( Q == NULL) /* vuol dire che era l'ultimo elemento della coda */
T = NULL;
/* STAMPIAMO LA CODA */
print_q(Q);
}
Ed ecco il codice delle tre funzioni (può essere tranquillamente implementato nella libreria)
/****************************************************************************/
/* ENQUEUE */
/****************************************************************************/
void enqueue(pnodo *T, int queue_in)
{
pnodo aus;
if (( aus = (pnodo) malloc (sizeof(struct nodo) ) ) == NULL )
fprintf(stderr,"ERRORE overflow %d\n");
else{
aus->inf = queue_in;
aus->next = NULL;
if(*T == NULL)
*T = aus;
else{
(*T)->next = (pnodo *) aus;
(pnodo *) *T = (*T)->next;
}
}
}
/****************************************************************************/
/* DEQUEUE */
/****************************************************************************/
int dequeue(pnodo *Q)
{
int queue_out = -1;
pnodo aus;
if( *Q == NULL)
fprintf(stderr,"ERRORE di underflow %d\n");
else{
aus = *Q;
queue_out = aus->inf;
(pnodo *) *Q = (*Q)->next;
free(aus);
}
return queue_out;
}
/****************************************************************************/
/* STAMPA CODA */
/****************************************************************************/
void print_q(pnodo Q){
while (Q != NULL){
printf("%d -> ",Q->inf);
(pnodo *) Q = Q->next;
}
printf("NULL\n");
}
Laboratorio di Algoritmi e Strutture Dati
Non ci sono commenti in questa pagina. [Scrivi commento]