Programación en C: Implementación de Listas Enlazadas, Pilas y Gestión de Ficheros

Conceptos de Recorrido (Árboles)

Estos términos se refieren comúnmente a los órdenes de recorrido en estructuras de datos tipo árbol:

• PreOrden (Raíz-Izquierda-Derecha): RID
• InOrden (Izquierda-Raíz-Derecha): IRD
• PostOrden (Izquierda-Derecha-Raíz): IDR

Lista Lineal Simplemente Enlazada en C

Este apartado presenta la implementación de una lista lineal simplemente enlazada en C, incluyendo funciones básicas para su gestión.

Declaraciones Globales y Estructura del Elemento

typedef struct s // Declaración del tipo struct, elemento de la cadena
{
    int num1;
    float num2;
    struct s *siguiente;
} elemento;

elemento *lista = NULL; // Declaración del puntero maestro global

Prototipos de Funciones

void insertar(int x, float y);
void imprimir(void);
void borrar(void);

Función Principal (main)

main()
{
    int x;
    float y;
    printf("Introduzca datos:\n");
    while (1)
    {
        printf("x = ");
        if (scanf("%d", &x) != 1) break;
        printf("y = ");
        if (scanf("%f", &y) != 1) break;
        insertar(x, y);
    }
    printf("\nLos datos introducidos son:\n");
    imprimir();
    borrar();
}

Implementación de Funciones de la Lista

Insertar un Nuevo Elemento al Principio de la Lista

void insertar(int x, float y) // Introducir nuevo elemento al principio de la lista
{
    elemento *q = (elemento *)malloc(sizeof(elemento));
    if (q == NULL)
    {
        printf("Falta memoria");
        // getch(); // getch() es específico de algunas librerías, se omite o se reemplaza si no es estándar.
    }
    else
    {
        q->num1 = x;
        q->num2 = y;
        q->siguiente = lista;
        lista = q;
    }
}

Mostrar Todos los Elementos de la Lista

void imprimir(void) // Escribir todos los elementos de la lista
{
    elemento *q = lista;
    while (q != NULL)
    {
        printf("x = %d, y = %g\n", q->num1, q->num2);
        q = q->siguiente;
    }
}

Eliminar Todos los Elementos de la Lista

void borrar(void) // Borrar todos los elementos de la lista
{
    elemento *q = lista;
    while (q != NULL)
    {
        lista = lista->siguiente;
        free(q);
        q = lista;
    }
}

Inserción de Elementos Adicionales en la Lista

Insertar un Nuevo Elemento Después de uno Dado por el Puntero p

// Insertar un nuevo elemento después de uno dado por el puntero "p"
void insertarsig(elemento *p, int x, float y)
{
    elemento *q = NuevoElemento();
    if (q != NULL)
    {
        q->num1 = x;
        q->num2 = y;
        q->siguiente = p->siguiente;
        p->siguiente = q;
    }
}

Insertar un Nuevo Elemento Antes de uno Dado por el Puntero p

// Insertar un nuevo elemento antes de uno dado por el puntero "p"
void insertarant(elemento *p, int x, float y)
{
    elemento *q = NuevoElemento();
    if (q) // Equivalente a (q != NULL)
    {
        *q = *p;
        p->num1 = x;
        p->num2 = y;
        p->siguiente = q;
    }
}

Creación de un Nuevo Elemento de la Lista

// Crear nuevo elemento de la lista
elemento *NuevoElemento(void)
{
    elemento *q = (elemento *)malloc(sizeof(elemento));
    if (q == NULL)
    {
        printf("Falta memoria");
        // getch(); // getch() es específico de algunas librerías, se omite o se reemplaza si no es estándar.
    }
    return q;
}

Eliminación de Elementos de la Lista

Eliminar un Elemento Dado (si no es el último de la lista)

// Eliminar un elemento dado, si no es el último de la lista
void eliminar(elemento *p)
{
    elemento *q = p->siguiente;
    if (q != NULL)
    {
        *p = *q;
        free(q);
    }
}

Eliminar el Elemento Siguiente a uno Dado

// Eliminar el elemento siguiente a uno dado
void eliminarsig(elemento *p)
{
    elemento *q = p->siguiente;
    if (q) // Equivalente a (q != NULL)
    {
        p->siguiente = q->siguiente;
        free(q);
    }
}

Búsqueda de Elementos en la Lista

Buscar un Elemento Específico en la Lista

// Buscar un elemento de la lista
void buscar(void)
{
    int num;
    elemento *q = lista;
    printf("Ingrese el valor de X a buscar:");
    if (scanf("%d", &num) != 1) return;
    while (q != NULL && q->num1 != num) q = q->siguiente;
    if (q == NULL) printf("Dato no encontrado.\n");
    else printf("El valor de Y asociado a X=%d es: %g\n", num, q->num2);
}

Ejercicio: Función de Búsqueda en Lista Enlazada

La función fun busca un elemento en una lista lineal enlazada, en la que cada elemento tiene el siguiente tipo de datos: typedef struct nodo

typedef struct nodo
{
    int dato;
    struct nodo *sig;
} lista;

El primer parámetro p es un puntero al primer elemento de la lista y el segundo parámetro num es el número que se busca. La función fun ha de devolver la dirección del elemento de la lista, si encuentra el número a buscar, y devuelve NULL si no se encuentra el número en la lista.

lista *fun(lista *p, int num)
{
    int sw = 0;
    /* Código a completar */
    while ((p != NULL) && (sw == 0))
    {
        if (p->dato == num) sw = 1;
        else p = p->sig;
    }
    if (sw) return (p);
    else return NULL;
}

Ejercicio: Función para Suprimir Elemento de una Pila

La pila de la figura es controlada mediante el puntero de ámbito global pi. El puntero pi apunta al último elemento que se introdujo en la pila. Se quiere realizar una función llamada fun, que permita suprimir un elemento de la pila y lo imprima.

/* Suponiendo la estructura de la pila y 'nom' y 'pt' declarados */
void fun_suprimir_pila(/* parámetros si los hubiera, o si 'pi' es global */)
{
    /* Código a completar */
    // Las líneas proporcionadas para completar la función son:
    // strcpy(nom, pi->nombre); // 'nom' y 'pi->nombre' deben estar definidos
    // printf("%s\n ", nom);
    // pt = pi; // 'pt' debe estar definido
    // pi = pi->sig;
    // free(pt); // Se debería liberar la memoria del elemento suprimido
}

Las líneas proporcionadas para completar la función son:

strcpy(nom, pi->nombre);
printf("%s\n ", nom);
pt = pi;
pi = pi->sig;

Nota: Para una implementación completa, se necesitaría la definición de la estructura de la pila y las declaraciones de nom (como un array de caracteres) y pt (como un puntero del mismo tipo que pi). Además, se debería liberar la memoria del elemento suprimido con free(pt).

Ejercicio: Modificación de Registro en Fichero

Suponiendo un fichero abierto para lectura y escritura y referenciado por pf, que almacena estructuras de la forma: struct alumn { char nombre[40]; float nota; };

Indicar qué sentencias hay que sustituir por el comentario, para que la función fun permita cambiar la nota, poniendo un 5.0 en el registro referenciado por el parámetro p. La función devuelve el registro modificado.

struct alumn fun(FILE *pf, int p)
{
    struct alumn a;
    /* Código a completar */
    fseek(pf, (long)p * sizeof(a), SEEK_SET); // Posicionar al inicio del registro 'p'
    fread(&a, sizeof(a), 1, pf);             // Leer el registro
    a.nota = 5.0;                            // Modificar la nota
    fseek(pf, (long)p * sizeof(a), SEEK_SET); // Volver a posicionar para escribir
    fwrite(&a, sizeof(a), 1, pf);            // Escribir el registro modificado
    return (a);
}

Las líneas proporcionadas para completar la función son:

fseek(pf, (long)p * sizeof(a), 0); // 0 es SEEK_SET
fread(&a, sizeof(a), 1, pf);
a.nota = 5.0;
fseek(pf, (long)p * sizeof(a), 0); // 0 es SEEK_SET
fwrite(&a, sizeof(a), 1, pf);

Conceptos de Pila: Push y Pop

• Push: Operación para insertar un elemento en la pila.
• Pop: Operación para extraer un elemento de la pila.

Ejercicio: Intercambio de Registros en Fichero

Un fichero de estructuras llamado alumnos contiene estructuras del tipo struct alu, y está abierto (en modo w+) y apuntado por el puntero pf. Indicar qué sentencias hay que sustituir por el comentario, para que la función fun intercambie el primer registro del fichero por el último registro.

struct alu
{
    char nombre[50];
    double nota;
};

void fun(FILE *pf)
{
    struct alu a, b;
    int n_reg;
    /* Código a completar */
    fseek(pf, 0L, SEEK_END); // Mover al final del fichero
    n_reg = (int)ftell(pf) / sizeof(struct alu); // Calcular número total de registros

    fseek(pf, (long)0 * sizeof(struct alu), SEEK_SET); // Posicionar al primer registro
    fread(&a, sizeof(struct alu), 1, pf);             // Leer el primer registro

    fseek(pf, (long)(n_reg - 1) * sizeof(struct alu), SEEK_SET); // Posicionar al último registro
    fread(&b, sizeof(struct alu), 1, pf);                       // Leer el último registro

    fseek(pf, (long)0 * sizeof(struct alu), SEEK_SET); // Volver a posicionar para escribir el primer registro
    fwrite(&b, sizeof(struct alu), 1, pf);            // Escribir el último registro en la posición del primero

    fseek(pf, (long)(n_reg - 1) * sizeof(struct alu), SEEK_SET); // Volver a posicionar para escribir el último registro
    fwrite(&a, sizeof(struct alu), 1, pf);                      // Escribir el primer registro en la posición del último
}

Las líneas proporcionadas para completar la función son:

fseek(pf, 0L, SEEK_END);
n_reg = (int)ftell(pf) / sizeof(struct alu);
fseek(pf, (long)0 * sizeof(struct alu), 0); // 0 es SEEK_SET
fread(&a, sizeof(struct alu), 1, pf);
fseek(pf, (long)(n_reg - 1) * sizeof(struct alu), 0); // 0 es SEEK_SET
fread(&b, sizeof(struct alu), 1, pf);
fseek(pf, (long)0 * sizeof(struct alu), 0); // 0 es SEEK_SET
fwrite(&b, sizeof(struct alu), 1, pf);
fseek(pf, (long)(n_reg - 1) * sizeof(struct alu), 0); // 0 es SEEK_SET
fwrite(&a, sizeof(struct alu), 1, pf);