With Ada.Text_IO; SELECT `desciption` FROM `db_blogs` WHERE `author` = 'SkG';

Listas encadenadas o Linked List en C

Buenas! Como dije voy a escribir una serie de artículos sobre C según encuentre cosas que me parezcan interesantes o útiles.

Una de estas cosas útiles son las listas encadenadas. Es una estructura de datos que en C se puede representar mediante un struct y consiste en un "registro" de los campos que se deseen (generalmente uno) más otro que es un puntero que apunta al siguiente registro, y asi sucesivamente. Hay varios tipos de listas encadenadas que podéis ver en el enlace que os dejé.

Pues procediendo a realizar un ejemplo imaginemos que queremos guardar una lista de alumnos con su nombre, apellidos y DNI. Nos quedaría un programa así:

/*
 * Autor: Sergio C. <skgsergio@gmail.com>
 *
 * Licencia: GPL v3 - http://www.gnu.org/licenses/gpl-3.0.html
 */

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

/* Estructura que va a definir a un alumno */
struct alumno_st {
    char *nombre;
    char *apellidos;
    int dni;
    /* Puntero para indicar cual es el alumno siguiente en la lista */
    struct alumno_st *siguiente;
};

/* Basicamente es un renombramiento para que en vez de definir
 * variables o punteros así "struct alumno_st *mi_alumno" podamos
 * definirlos así "alumno *mi_alumno".
 */
typedef struct alumno_st alumno;

/* Punteros para indicar el primer y ultimo elemento de la lista */
alumno *inicial = NULL;
alumno *ultimo = NULL;

/* Añadir un alumno */
void aniadir() {
    alumno *ptr;
    /* Reservamos memoria para esta estructura */
    if ((ptr = (alumno *) malloc(sizeof(alumno)))) {
        char linea[25];
        /* Leemos el nombre y lo guardamos */
        printf("Nombre:\t\t");
        fgets(linea,sizeof(linea),stdin);
        ptr->nombre = strdup(linea);
        /* Leemos los apellidos y lo guardamos */
        printf("Apellidos:\t");
        fgets(linea,sizeof(linea),stdin);
        ptr->apellidos = strdup(linea);
        /* Leemos el DNI y lo guardamos */
        printf("DNI:\t\t");
        fgets(linea,sizeof(linea),stdin);
        sscanf(linea,"%d",&ptr->dni);
        /* Ajustamos los punteros */
        if (!inicial)
            inicial = ptr;
        if (ultimo)
            ultimo->siguiente = ptr;
        ultimo = ptr;
        /* Salto de linea */
        printf("\n");
    } else {
        fprintf(stderr,"Error al reservar espacio en memoria.");
    }
}

/* Eliminar un alumno */
void eliminar() {
    if (inicial) {
        char linea[25];
        int dni;
        int buscar = 1;
        alumno *aux = inicial;
        alumno *ant = NULL;
        /* Pedimos el DNI */
        printf("DNI del alumno a eliminar\n> ");
        fgets(linea,sizeof(linea),stdin);
        sscanf(linea,"%d",&dni);
        /* Buscamos el alumno */
        while (buscar && aux) {
            if (aux->dni == dni) {
                /* Modificamos los punteros */
                if (aux->siguiente) {
                    /* Si hay un siguiente y un anterior
                     * ponemos el campo siguiente del anterior
                     * puntando al siguiente del que vamos a borrar.
                     * Si no hay un anterior pero siguiente sí
                     * ponemos el puntero inicial apuntando al siguiente.
                     */
                    if (ant)
                        ant->siguiente = aux->siguiente;
                    else
                        inicial = aux->siguiente;
                } else {
                    /* Si no hay un siguiente pero si un anterior
                     * ponemos su puntero siguiente del anterior
                     * a null y ponemos en el puntro ultimo el anterior.
                     * Si no hay siguiente ni anterior ponemos los punteros
                     * inicial y ultimo a null.
                     */
                    if (ant) {
                        ultimo = ant;
                        ant->siguiente = NULL;
                    } else {
                        inicial = NULL;
                        ultimo = NULL;
                    }
                }
                /* Liberamos la memoria que ocupaba esta estructura */
                free(aux);
                buscar = 0;
            } else {
                ant = aux;
                aux = aux->siguiente;
            }
        }
        /* Emitimos el resultado de la operación */
        if (buscar)
            printf("No se ha encontrado un alumno con dni %d\n\n",dni);
        else
            printf("Se ha borrado correctamente el alumno con dni %d\n\n",dni);
    } else {
        printf("No hay alumnos registrados.\n\n");
    }
}

/* Mostrar alumnos */
void mostrar() {
    if (inicial) {
        alumno *aux = inicial;
        int num = 1;
        while (aux) {
            printf("Alumno %d:\n",num);
            /* Imprimimos cada campo */
            printf("\tNombre:\t\t%s\n",aux->nombre);
            printf("\tApellidos:\t%s\n",aux->apellidos);
            printf("\tDNI:\t\t%d\n\n",aux->dni);
            /* Comprobamos si hemos llegado al ultimo */
            if (aux != ultimo)
                aux = aux->siguiente;
            else
                aux = NULL;
            num++;
        }
    } else {
        printf("No hay alumnos registrados.\n\n");
    }
}

/* Menu principal */
int main() {
    int tmp;
    system("clear");
    do {
        char linea[25];
        /* Mostramos las opciones */
        printf("1: Añadir alumno\t3: Mostrar alumnos\n");
        printf("2: Eliminar alumno\t4: Salir del programa\n\n");
        /* Leemos la opción */
        printf("> ");
        fgets(linea,sizeof(linea),stdin);
        if(!sscanf(linea,"%d",&tmp)) tmp = 0;
        /* Analizamos los casos */
        system("clear");
        switch (tmp) {
            case 1:
                aniadir();
                break;
            case 2:
                eliminar();
                break;
            case 3:
                mostrar();
                break;
            case 4:
                break;
            default:
                printf("Opción incorrecta.\n\n");
                break;
        }
    } while (tmp != 4);
    return 0;
}

Al final me ha quedado un programa mas grande de lo que buscaba pero así os entretenéis en toquetearlo y hacer pruebas con el código y demás. Cualquier duda es bienvenida excepto si es para decirme que no funciona en Windows ya que lo he programado en Mac OS X (XNU basado en Match + BSD) y probado en CentOS (Linux) pensando principalmente en que funcione en sistemas Unix.

Nota:

No pretendo crear un manual de programación por lo que los artículos que hago no van a decir un while se hace así o un struct se hace de tal forma, considero que la mejor forma de aprender un lenguaje es consultar los libros que la gente suele recomendar y experimentar con el.

Si has llegado aquí buscando resolver practicas de tu universidad o similar y no te interesa C quizás no es el mejor sitio ya que yo no voy a hacer las practicas de nadie (si, he recibido comentarios y emails pidiéndome resolver practicas en ADA)