Buongiorno a tutti:
Sto provando a svolgere questo esercizio
Progettare una realizzazione del tipo di dato Coda che utilizza un array circolare dinamico. Sia n il numero di elementi nella coda e h la dimensione dell'array dinamico. Ogni qualvolta n è uguale a h, l'array viene riallocato raddoppiandone la dimensione mentre, quando n scende sotto h/4, l'array viene riallocato dimezzandone la dimensione.
La coda ha la seguente struttura:
struct queue{ /* tipo della queue realizzato con array circolare */
Item * contents;
int head;
int tail;
int dim; /* dimensione dell'array */
};
typedef struct queue *Queue;
Item ha la struttura
typedef struct node{
int key;
} * Node;
typedef Node Item;
Il file con le funzioni da svolgere è il seguente (le ho già scritte praticamente tutte)
/* post: costruisce una coda vuota */
Queue initqueue(){
Queue coda = (Queue)malloc(sizeof(struct queue));
if(coda){
(coda->contents) = (Item*)malloc(sizeof(Item));
coda->head = 0;
coda->tail = 0;
coda->dim = 1;
return coda;
}
else
return NULL;
}
/*post: ritorna 1 se la coda e' vuota, 0 altrimenti */
int queueEmpty(Queue q){
return (q->head == q->tail);
}
/*post: inserisce elem come ultimo elemento di q */
void enqueue(Queue q, Item elem){
// inserisco l'elemento nella coda e incremento subito tail di 1
(q->contents)[(q->tail)++] = elem;
// se la coda è arrivata a fine array allora dovrò inserire partendo dall'inizio
if( (q->tail == q->dim) && (q->head != 0) ) {
q->tail = 0;
}
/* ho riempito l'array quindi raddoppio la dimensione (non modifico tail
perchè è gia stato incrementato) */
else if( (q->tail == q->dim) && (q->head == 0) ){
q->contents = realloc(q->contents, ((q->dim)*2)*sizeof(int));
(q->dim)*=2;
}
/* la testa e la coda sono uguali, raddoppio l'array e i valori che precedono la testa vengono
shiftati verso destra di dim posizioni */
else if(q->tail == q->head){
int i;
q->contents = realloc(q->contents, (q->dim)*2*sizeof(int));
for(i=0;i<q->head;i++){
(q->contents)[i + (q->dim)] = (q->contents)[i];
}
(q->tail)+=(q->dim);
(q->dim)*=2;
}
}
/*pre: coda non vuota */
/*post: ritorna e rimuove il primo elemento in coda */
Item dequeue(Queue q){
return NULL;
}
/*pre: coda non vuota */
/*post: restituisce il primo elemento in q */
Item first(Queue q){
return NULL;
}
/*post: ritorna il numero di elementi nella coda */
int size(Queue q){
int i = q->head;
int nElem = 0;
while(i != q->tail){
nElem++;
i=(i+1)%(q->dim);
}
return nElem;
}
Lo so che manca ancora l'implementazione di dequeue, ma il problema è che ho creato un main di prova su cui eseguo per 6 volte la enqueue e sempre alla quarta iterazione mi da errore (realloc(): invalid next size) vi prego aiutatemi a capire .