jueves, 11 de agosto de 2011

Listas enlazadas

Estos últimos días he estado tratando de recordar el funcionamiento de los punteros en C. Al principio me costó un poco, y cometí muchos de los errores que solía cometer cuando los descubrí hace años durante mis primeras incursiones en la programación (en C, en particular). De todos modos, creo que ya he vuelto a entender la esencia de los mismos y para comprobar mis progresos he realizado unas pruebas creando una lista enlazada y realizando ciertas operaciones básicas sobre ella (añadir elementos, eliminar, buscar y listar los elementos). El código correspondiente se puede ver a continuación.

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

//Definición de los elementos de la lista
 struct list {
    int valor;
    struct list *sig;
};
typedef struct list item;

//Prototipos de funciones
int long_lista(item *lista);
item *add_lista(item *lista, int valor);
item *del_lista(item *lista, int valor);
int search_lista(item *lista, int valor);
void print_lista(struct list *lista);

int main()
{
    item *lista, *item1, *item2, *item3;
    int tamano=0;
    int i=0;

    lista=NULL;
    for (i=0; i<10; i++) {
        //Añadimos elementos a la lista
        lista = add_lista(lista,i);
    }
    printf("La longitud de la lista es: %d\n",long_lista(lista));
    printf("Antes de borrar: \n");
    //Mostramos el contenido de la lista
    print_lista(lista);
    //Borramos un elemento de la lista
    lista = del_lista(lista,9);
    printf("Despues de borrar: \n");
    //Mostramos los elementos de la lista
    print_lista(lista);

    //Búsqueda de elementos en la lista
    if (search_lista(lista,4)) printf("La lista contiene un 4\n");
    else printf("La lista no contiene un 4\n");
    if (search_lista(lista,9)) printf("La lista contiene un 9\n");
    else printf("La lista no contiene un 9\n");
    return 0;
}

/*
    Esta función devuelve el número de elementos que contiene la lista que
    recibe como parámetro
*/
int long_lista(item *lista) {
    int lon=0;

    if (lista==NULL) return 0;
    else {
        while (lista!=NULL) {
            lista=lista->sig;
            lon++;
        }
        return lon;
    }
}

/*
    Esta función devuelve un puntero al inicio de la lista después de añadirle un
    nuevo elemento cuyo valor se le pasa como parámetro a la función.
*/
item *add_lista(item *lista, int valor) {
    item *lista_aux;

    lista_aux = (item *)malloc(sizeof(item));

    if (lista==NULL) {
        lista_aux->valor=valor;
        lista_aux->sig=NULL;
        lista=lista_aux;
    }
    else {
        lista_aux->valor=valor;
        lista_aux->sig=lista;
        lista=lista_aux;
    }

    return lista;
}

/*
    Esta función devuelve un puntero a la cabeza de la lista resultante de eliminar
    el elemento cuyo valor asociado coincide con el que se pasa por parámetro.
*/
item *del_lista(item *lista, int valor) {
    item *index;
    item *temp;

    index = lista;
    if (index != NULL) {
        if (index->valor==valor) {
            index=index->sig;
            lista=index;
            return lista;   //hemos borrado el primer elemento de la lista
        }
        else {
            temp=lista;
            index=lista->sig;
            while (index!=NULL) {
                if (index->valor==valor) {
                    temp->sig=index->sig;
                    return lista;  //eliminamos de la lista el primer elemento encontrado
                }
                else {
                    index=index->sig;
                    temp=temp->sig;
                }
            }
        }
    } else
        return lista;  //no se ha borrado nada de la lista porque estaba vacía
}

/*
    Esta función devuelve un 0 si no encuentra ningún elemento en la lista cuyo valor
    asociado coincida con el pasado por parámetro, y un 1 si encuentra al menos un
    elemento cuyo valor si coincida.
*/
int search_lista(item *lista, int valor) {
    item *index;
    int encontrado=0;

    index=lista;
    while (index!=NULL) {
        if (index->valor==valor) {
            return 1;
        }
        else {
            index=index->sig;
        }
    }
    return 0;
}

/*
    Esta función se ocupa de mostrar por pantalla el valor de todos los elementos
    pertenecientes a la lista que se pasa por parámetro.
*/
void print_lista(item *lista) {
    item *index;

    index=lista;
    while (index!=NULL) {
        printf("Valor: %d\n", index->valor);
        index=index->sig;
    }
}

No hay comentarios:

Publicar un comentario