es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Una lista de colas

02 Aug, 2023 Programación

Considere un sistema de reservas de boletos. Una reserva se caracteriza por la categoría (char), ID (int), nombre (máximo 35 caracteres). Implemente una estructura de datos basada en listas enlazadas que sea eficiente desde el punto de vista del tiempo de ejecución, con los siguientes componentes: cada categoría será un nodo en la lista, y cada categoría contendrá una cola (FIFO) implementada estáticamente que contendrá la solicitud de reserva para esa categoría. Implemente las siguientes funciones:

  1. Agregar categoría
  2. Agregar solicitud de boleto – (enque)
  3. Servir solicitud de boleto – (deque)
  4. Mostrar el contenido de la lista

Aquí está mi código hasta ahora:

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

struct rev
{
    char category[100], name[35];
    int ID;
    struct rev* next;
};

struct rev* newNode(int ID, const char *category, const char *name)
{
    struct rev* new_node = (struct rev*)malloc(sizeof(struct rev));

    strcpy(new_node->category, category);
    strcpy(new_node->name, name);
    new_node->ID = ID;

    new_node->next = NULL;

    return new_node;
}

No entiendo exactamente lo que se supone que debo hacer. He intentado implementar una lista, pero no sé si solo debe tener la categoría.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para implementar el sistema de reserva de entradas descrito, es necesario crear una estructura de datos compuesta por listas enlazadas y colas. Cada categoría será un nodo en la lista enlazada, y cada nodo tendrá una cola (FIFO) que contiene las solicitudes de reserva para esa categoría.

    Aquí tienes un poco de código para comenzar:

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

#define MAX_CATEGORY_LENGTH 100
#define MAX_NAME_LENGTH 35

typedef struct reservation
{
    char category[MAX_CATEGORY_LENGTH];
    char name[MAX_NAME_LENGTH];
    int ID;
    struct reservation* next;
} reservation_t;

typedef struct queue_node
{
    reservation_t* reservation;
    struct queue_node* next;
} queue_node_t;

typedef struct queue
{
    queue_node_t* front;
    queue_node_t* rear;
    int size; // opcional
} queue_t;

typedef struct category_node
{
    char category[MAX_CATEGORY_LENGTH];
    queue_t* queue;
    struct category_node* next;
} category_node_t;

category_node_t* head = NULL;

// Función auxiliar para crear un nuevo nodo de reserva
reservation_t* new_reservation(int ID, const char* category, const char* name)
{
    reservation_t* new_node = (reservation_t*)malloc(sizeof(reservation_t));
    if (new_node == NULL)
    {
        fprintf(stderr, "Error: malloc no pudo asignar memoria para la reserva.\n");
        exit(EXIT_FAILURE);
    }

    strncpy(new_node->category, category, MAX_CATEGORY_LENGTH);
    strncpy(new_node->name, name, MAX_NAME_LENGTH);
    new_node->ID = ID;
    new_node->next = NULL;

    return new_node;
}

// Función auxiliar para crear un nuevo nodo de cola
queue_node_t* new_queue_node(reservation_t* reservation)
{
    queue_node_t* new_node = (queue_node_t*)malloc(sizeof(queue_node_t));
    if (new_node == NULL)
    {
        fprintf(stderr, "Error: malloc no pudo asignar memoria para el nodo de la cola.\n");
        exit(EXIT_FAILURE);
    }

    new_node->reservation = reservation;
    new_node->next = NULL;

    return new_node;
}

// Función auxiliar para crear una nueva cola vacía
queue_t* new_queue()
{
    queue_t* new_queue = (queue_t*)malloc(sizeof(queue_t));
    if (new_queue == NULL)
    {
        fprintf(stderr, "Error: malloc no pudo asignar memoria para la cola.\n");
        exit(EXIT_FAILURE);
    }

    new_queue->front = NULL;
    new_queue->rear = NULL;
    new_queue->size = 0;

    return new_queue;
}

// Función auxiliar para crear un nuevo nodo de categoría
category_node_t* new_category_node(const char* category)
{
    category_node_t* new_node = (category_node_t*)malloc(sizeof(category_node_t));
    if (new_node == NULL)
    {
        fprintf(stderr, "Error: malloc no pudo asignar memoria para el nodo de la categoría.\n");
        exit(EXIT_FAILURE);
    }

    strncpy(new_node->category, category, MAX_CATEGORY_LENGTH);
    new_node->queue = new_queue();
    new_node->next = NULL;

    return new_node;
}

// Función para agregar una categoría a la lista
void add_category(const char* category)
{
    category_node_t* new_node = new_category_node(category);

    if (head == NULL)
    {
        head = new_node;
    }
    else
    {
        category_node_t* current = head;
        while (current->next != NULL)
        {
            current = current->next;
        }
        current->next = new_node;
    }
}

// Función para agregar una nueva reserva a la cola de una categoría dada
void add_reservation(const char* category, int ID, const char* name)
{
    category_node_t* current = head;
    while (current != NULL && strcmp(current->category, category) != 0)
    {
        current = current->next;
    }

    if (current == NULL)
    {
        fprintf(stderr, "Error: la categoría '%s' no existe.\n", category);
        return;
    }

    reservation_t* new_reservation = new_reservation(ID, category, name);
    queue_node_t* new_queue_node = new_queue_node(new_reservation);

    if (current->queue->rear == NULL)
    {
        current->queue->front = new_queue_node;
        current->queue->rear = new_queue_node;
    }
    else
    {
        current->queue->rear->next = new_queue_node;
        current->queue->rear = new_queue_node;
    }

    current->queue->size++;
}

// Función para eliminar y devolver la reserva más antigua de la cola de una categoría dada
reservation_t* serve_reservation(const char* category)
{
    category_node_t* current = head;
    while (current != NULL && strcmp(current->category, category) != 0)
    {
        current = current->next;
    }

    if (current == NULL)
    {
        fprintf(stderr, "Error: la categoría '%s' no existe.\n", category);
        return NULL;
    }

    if (current->queue->front == NULL)
    {
        fprintf(stderr, "Error: la cola de la categoría '%s' está vacía.\n", category);
        return NULL;
    }

    queue_node_t* temp = current->queue->front;
    current->queue->front = current->queue->front->next;
    if (current->queue->front == NULL)
    {
        current->queue->rear = NULL;
    }

    reservation_t* reservation = temp->reservation;
    free(temp);

    current->queue->size--;

    return reservation;
}

// Función para mostrar el contenido de la lista
void display_list()
{
    if (head == NULL)
    {
        printf("La lista está vacía.\n");
        return;
    }

    category_node_t* current = head;
    while (current != NULL)
    {
        printf("Categoría: %s\n", current->category);
        printf("    Tamaño de la cola: %d\n", current->queue->size);
        printf("    Contenido de la cola: ");

        queue_node_t* queue_current = current->queue->front;
        while (queue_current != NULL)
        {
            reservation_t* reservation = queue_current->reservation;
            printf("{categoría: %s, ID: %d, nombre: '%s'} ", reservation->category, reservation->ID, reservation->name);
            queue_current = queue_current->next;
        }
        printf("\n");

        current = current->next;
    }
}

int main()
{
    add_category("primera");
    add_category("segunda");
    add_reservation("primera", 1, "Alice");
    add_reservation("primera", 2, "Bob");
    add_reservation("segunda", 3, "Charlie");
    add_reservation("segunda", 4, "David");
    display_list();
    reservation_t* reservation = serve_reservation("primera");
    printf("Reserva atendida: {categoría: %s, ID: %d, nombre: '%s'}\n", reservation->category, reservation->ID, reservation->name);
    free(reservation);
    display_list();
    return EXIT_SUCCESS;
}

    La estructura reservation_t representa una reserva, con campos para la categoría, el ID y el nombre. La estructura queue_node_t representa un nodo en la cola para una categoría determinada, con un puntero a la reserva y un puntero al siguiente nodo en la cola. La estructura queue_t representa la cola en sí, con punteros a los nodos frontal y trasero y un campo de tamaño (que es opcional).

    La estructura category_node_t representa un nodo en la lista enlazada de categorías, con una cadena que contiene el nombre de la categoría y un puntero a la cola de esa categoría.

    La función add_category agrega una nueva categoría a la lista creando una nueva estructura category_node_t y añadiéndola al final de la lista.

    La función add_reservation agrega una nueva reserva a la cola de una categoría dada creando una nueva estructura reservation_t y una nueva estructura queue_node_t, y añadiendo el queue_node_t al final de la cola de la categoría dada.

    La función serve_reservation elimina y devuelve la reserva más antigua de la cola de una categoría dada.

    La función display_list imprime el contenido de la lista iterando sobre cada nodo de la lista e imprimiendo el nombre de la categoría, el tamaño de la cola para esa categoría y el contenido de la cola en sí.

    La función main demuestra el uso de estas funciones agregando categorías y reservas, atendiendo una reserva y mostrando el contenido de la lista. Ten en cuenta que en este código de ejemplo, se asigna memoria de forma dinámica para cada nuevo nodo y se libera cuando ya no se necesita para evitar pérdidas de memoria.</string.h></stdlib.h></stdio.h>

Comments are closed.