2

Tenho um código (final da pergunta) que permite a manipulação de uma fila em ANSI C, minha questão é a seguinte: O código declara um tipo de dado próprio para armazenar os dados da fila e possui uma função para criar uma fila, porém ele usa no exemplo inteiros, mas eu queria usar uma struct personalizada. Como poderia alterar o código para permitir o uso de uma struct personalizada?

Lembrando que a struct e desconhecida pelo código, não gostaria de ter que acoplar essa struct no exemplo, pois desta forma sempre que fosse criar uma fila para uma determinada struct eu teria que alterar o código de manipulação de fila.

Acredito que para resolver isso preciso mexer na struct Queue e alterar o int *elements; para algum tipo de dados (talves void*) em seguida permitir que na função Queue * createQueue(int maxElements) permita a passagem da minha struct personalizada para que o código possa calcular seu sizeof para o malloc, mas não faço ideia de como fazer isso... alguma luz?

#include<stdio.h>
#include<stdlib.h>
/*Queue has five properties. capacity stands for the maximum number of elements Queue can hold.
  Size stands for the current size of the Queue and elements is the array of elements. front is the
 index of first element (the index at which we remove the element) and rear is the index of last element
 (the index at which we insert the element) */
typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;
/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the Queue. */
Queue * createQueue(int maxElements)
{
        /* Create a Queue */
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        /* Initialise its properties */
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}
void Dequeue(Queue *Q)
{
        /* If Queue size is zero then it is empty. So we cannot pop */
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                return;
        }
        /* Removing an element is equivalent to incrementing index of front by one */
        else
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                exit(0);
        }
        /* Return the element which is at the front*/
        return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                /* As we fill the queue in circular fashion */
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                /* Insert the element in its rear side */ 
                Q->elements[Q->rear] = element;
        }
        return;
}
int main()
{
        Queue *Q = createQueue(5);
        Enqueue(Q,1);
        Enqueue(Q,2);
        Enqueue(Q,3);
        Enqueue(Q,4);
        printf("Front element is %d\n",front(Q));
        Enqueue(Q,5);
        Dequeue(Q);
        Enqueue(Q,6);
        printf("Front element is %d\n",front(Q));
}

1 Resposta 1

2

Para que a fila armazene estruturas genéricas, uma possibilidade é fazer o vetor de elementos apontar para um array de ponteiros tipo void ** (para permitir a deferência).

A struct fica da seguinte forma:

typedef struct Queue
{
  int capacity;
  int size;
  int front;
  int rear;
  void **elements; // trocado para void **
} Queue;

Como a fila irá armazenar apenas um conjunto de referências (ponteiros) para os dados, o tamanho do ponteiro (sizeof(void *)) é constante (ex: 4 bytes para para um ponteiro 32bits), portanto a função createQueue não necessita saber o tamanho total do dado que será armazenado.

Para armazenar e recuperar os elementos, é necessário efetuar um cast para o tipo de dado correspondente (void para Elemento e vice-versa).


Estrutura genérica de exemplo

  typedef struct {
    int elemento1,
    float elemento2,
    double elemento3
  } Elemento;

Função para alocar uma estrutura

  Elemento *alocaElemento(int p1, float p2, double p3)
  {
    Elemento *ret = (Elemento *) malloc(sizeof(Elemento));
    ret->elemento1 = p1;
    ret->elemento2 = p2;
    ret->elemento3 = p3;
    return ret;
  }

Implementação completa com exemplos de uso:

#include<stdio.h>
#include<stdlib.h>

/*Queue has five properties. capacity stands for the maximum number of elements Queue can hold.
  Size stands for the current size of the Queue and elements is the array of elements. front is the
 index of first element (the index at which we remove the element) and rear is the index of last element
 (the index at which we insert the element) */

typedef struct Queue
{
    int capacity;
    int size;
    int front;
    int rear;
    void **elements; // trocado para (void **)
} Queue;

/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the Queue. */
Queue * createQueue(int maxElements)
{
    /* Create a Queue */
    Queue *Q;
    Q = (Queue *)malloc(sizeof(Queue));
    /* Initialise its properties */
    // Aqui, o tamanho de cada elemento é o tamanho de um ponteiro void
    Q->elements = (void *)malloc(sizeof(void *)*maxElements); 
    Q->size = 0;
    Q->capacity = maxElements;
    Q->front = 0;
    Q->rear = -1;
    /* Return the pointer */
    return Q;
}

void Dequeue(Queue *Q)
{
    /* If Queue size is zero then it is empty. So we cannot pop */
    if(Q->size==0)
    {
        printf("Queue is Empty\n");
        return;
    }
    else
    {
        /* Removing an element is equivalent to incrementing index of front by one */       
        Q->size--;
        Q->front++;
        /* As we fill elements in circular fashion */
        if(Q->front==Q->capacity)
        {
            Q->front=0;
        }
    }
    return;
}

void *front(Queue *Q) // trocado para retornar um elemento (void *)
{
    if(Q->size==0)
    {
        printf("Queue is Empty\n");
        exit(0);
    }
    /* Return the element which is at the front*/
    return Q->elements[Q->front];
}

void Enqueue(Queue *Q, void *element) // trocado para aceitar um ponteiro void
{
    /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
    if(Q->size == Q->capacity)
    {
        printf("Queue is Full\n");
    }
    else
    {
        Q->size++;
        Q->rear = Q->rear + 1;
        /* As we fill the queue in circular fashion */
        if(Q->rear == Q->capacity)
        {
           Q->rear = 0;
        }
        /* Insert the element in its rear side */ 
        Q->elements[Q->rear] = element;
    }
    return;
}

// Elemento "generico"
typedef struct {
    int elemento1;
    float elemento2;
    double elemento3;
} Elemento;

// funcao que aloca um elemento 
Elemento *alocaElemento(int p1, float p2, double p3)
{
    Elemento *ret = (Elemento *) malloc(sizeof(Elemento));
    ret->elemento1 = p1;
    ret->elemento2 = p2;
    ret->elemento3 = p3;
    return ret;
}

int main()
{
    Queue *Q = createQueue(5);
    Elemento *e;

    e = alocaElemento(1, 1.5, 1.5e10);
    Enqueue(Q, (void *) e); // efetua o cast de (Elemento *) para (void *)

    e = alocaElemento(2, 2.5, 2.5e20);
    Enqueue(Q, (void *) e);

    e = alocaElemento(3, 3.5, 3.55e9);
    Enqueue(Q, (void *) e);

    e = alocaElemento(4, 4.5, 4.5e12);
    Enqueue(Q, (void *) e);

    // efetua o cast "contrario" de (void *) para (Elemento *)
    printf("Front element is %f\n",((Elemento *) front(Q))->elemento2); 

    Dequeue(Q); // Retira um elemento da fila

    // efetua o cast "contrario" de (void *) para (Elemento *)
    printf("Front element is %f\n",((Elemento *) front(Q))->elemento2); 

    e = alocaElemento(5, 5.5, 3.112121);
    Enqueue(Q, (void *) e); // insere um novo elemento

    Dequeue(Q); // retira um elemento da fila

    e = alocaElemento(6, 6.0, 2.0);

    Enqueue(Q, (void *) e);

    printf("Front element is %f\n",((Elemento *) front(Q))->elemento3);

    Dequeue(Q); // retira um elemento da fila
    Dequeue(Q); // retira um elemento da fila

    printf("Front element is %f\n",((Elemento *) front(Q))->elemento3);
}

Resultado após a execução:

Front element is 1.500000
Front element is 2.500000
Front element is 3550000000.000000
Front element is 3.112121

Obs: é importante liberar toda a memória alocada durante o processo (free(...)).

Testado com gcc version 6.2.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .