Implementate una struttura dati che manipola numeri interi con il paradigma FIFO (First in First Out), usando una lista di interi con due puntatori alla testa e alla coda della lista.
In particolare deve essere definito un nuovo tipo queue
e devono essere implementate opportunamente due funzioni enqueue
e dequeue
per l'inserimento in coda e l'estrazione dalla testa.
Potete partire dal programma riportato in fondo alla pagina, che contiene alcune funzioni per manipolare liste di interi.
Scrivete poi un programma che:
Eseguendo
./soluzione
avendo nel flusso di ingresso i numeri:
1 2 3 4 5 6 7 8 0
il programma emette sul flusso di uscita:
1 3 5 7
Eseguendo
./soluzione
avendo nel flusso di ingresso i numeri:
14 2 -7 10 4 30 0
il programma emette sul flusso di uscita:
-7
#include <stdio.h>
#include <stdlib.h>
struct element { // definizione di un elemento della lista
int info;
struct element *next; // prossimo elemento
};
typedef struct element element;
element *insert(int n, element *h);
void printList(element *h);
element *delete(int x, element *h);
typedef ....
... enqueue( ... ){
...
}
... dequeue( ... ){
...
}
int main(){
...
}
/* Inserisce un nuovo elemento contenente n in testa alla lista h
Restituisce la lista ottenuta. */
element *insert(int n, element *h){
element *new = malloc(sizeof(element));
new->info = n;
new->next = h;
return new;
}
/* Stampa gli elementi della lista h */
void printList(element *h){
/* h e' usato per attraversare la lista */
for( ; h!= NULL; h=h->next)
printf("%d ", h->info);
putchar('\n');
}
/* Cancella l'elemento x nella lista h e restituisce la lista ottenuta */
element *delete(int n, element *h){
element *tmp, *p;
if(h->info == n){ // l'elemento da cancellare e' il primo
tmp = h;
h = h->next;
free(tmp);
}
else{ // l'elemento da cancellare non e' il primo
for(p = h; p->next != NULL && p->next->info != n; p = p->next)
; /* p e' l'elemento che precede x oppure l'ultimo della lista */
if ( p->next != NULL ) {
tmp = p->next;
p->next = p->next->next;
free(tmp);
}
}
return h;
}