Check the new version here

Popular channels

Programita en C para implementar listas doblemente enlazadas



Dejo esta excelente implementación que encontré, la traduje casi completamente, corregí algunos errores, fue compilado con éxito en gcc con los comandos -ansi -Wall -Werror -pedantic, el programa funcionó a la perfección en las pruebas que le hice.


/* Programa en C para implementar listas doblemente enlazadas: provee inserción, eliminación y búsqueda y actualización de nodos*/

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

struct node
{
    struct node *prev;
    int n;
    struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;

void insert1();
void insert2();
void insert3();
void traversebeg();
void traverseend(int);
void sort();
void search();
void update();
void delete();

int count = 0;

int main(void)
{
    int ch;

    h = NULL;
    temp = temp1 = NULL;

    printf("n 1 - Insertar al comienzo");
    printf("n 2 - Insertar al final");
    printf("n 3 - Insertar en la posición i");
    printf("n 4 - Eliminar en la posición i");
    printf("n 5 - Mostrar desde el principio");
    printf("n 6 -  Mostrar desde el final");
    printf("n 7 - Buscar un elemento");
    printf("n 8 -  Ordenar la lista");
    printf("n 9 - Actualizar un elemento");
    printf("n 10 - Salir");

    while (1)
    {
        printf("n Ingrese opción : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            insert1();
            break;
        case 2:
            insert2();
            break;
        case 3:
            insert3();
            break;
        case 4:
            delete();
            break;
        case 5:
            traversebeg();
            break;
        case 6:
            temp2 = h;
            if (temp2 == NULL)
                printf("n Error : Lista a mostrar vacia ");
            else
            {
                printf("n El orden invertido de la lista enlazada es : ");
                traverseend(temp2->n);
            }
            break;
        case 7:
            search();
            break;
        case 8:
            sort();
            break;
        case 9:
            update();
            break;
        case 10:
            exit(0);
        default:
            printf("n Elección errónea");
            break;
        }
    }


    return 0;
}

/* Para crear un nodo vacio*/
void create()
{
    int data;

    temp =(struct node *)malloc(1*sizeof(struct node));
    temp->prev = NULL;
    temp->next = NULL;
    printf("n Ingrese el valor al nodo: ");
    scanf("%d", &data);
    temp->n = data;
    count++;
}

/*  Para insertar al comienzo*/
void insert1()
{
    if (h == NULL)
    {
        create();
        h = temp;
        temp1 = h;
    }
    else
    {
        create();
        temp->next = h;
        h->prev = temp;
        h = temp;
    }
}

/*  Para insertar al final*/
void insert2()
{
    if (h == NULL)
    {
        create();
        h = temp;
        temp1 = h;
    }
    else
    {
        create();
        temp1->next = temp;
        temp->prev = temp1;
        temp1 = temp;
    }
}

/* Para insertar en cualquier posición*/
void insert3()
{
    int pos, i = 2;

    printf("n Ingrese la posición donde será insertado el nodo : ");
    scanf("%d", &pos);
    temp2 = h;

    if ((pos < 1) || (pos >= count + 1))
    {
        printf("n Posición para insertar fuera de rango");
        return;
    }
    if ((h == NULL) && (pos != 1))
    {
        printf("n En la lista vacia no se puede insertar más que en la primera posición");
        return;
    }
    if ((h == NULL) && (pos == 1))
    {
        create();
        h = temp;
        temp1 = h;
        return;
    }
    else
    {
        while (i < pos)
        {
            temp2 = temp2->next;
            i++;
        }
        create();
        temp->prev = temp2;
        temp->next = temp2->next;
        temp2->next->prev = temp;
        temp2->next = temp;
    }
}

/* Para eliminar un elemento */
void delete()
{
    int i = 1, pos;

    printf("n Ingrese la posición del nodo a ser eliminado: ");
    scanf("%d", &pos);
    temp2 = h;

    if ((pos < 1) || (pos >= count + 1))
    {
        printf("n Error : Posición a eliminar fuera de rango");
        return;
    }
    if (h == NULL)
    {
        printf("n Error : Lista vacia, no hay elementos que eliminar");
        return;
    }
    else
    {
        while (i < pos)
        {
            temp2 = temp2->next;
            i++;
        }
        if (i == 1)
        {
            if (temp2->next == NULL)
            {
                printf("Nodo eliminado de la lista");
                free(temp2);
                temp2 = h = NULL;
                return;
            }
        }
        if (temp2->next == NULL)
        {
            temp2->prev->next = NULL;
            free(temp2);
            printf("Nodo eliminado de la lista");
            return;
        }
        temp2->next->prev = temp2->prev;
        if (i != 1)
            temp2->prev->next = temp2->next;    /* Esto no será necesario si vale i == 1  */
        if (i == 1)
            h = temp2->next;
        printf("n Nodo eliminado");
        free(temp2);
    }
    count--;
}

/* Traverse desde el comienzo*/
void traversebeg()
{
    temp2 = h;

    if (temp2 == NULL)
    {
        printf("n La lista a mostrar esta vacia ");
        return;
    }
    printf("n Elementos de la lista enlazada desde el comienzo : ");

    while (temp2->next != NULL)
    {
        printf(" %d ", temp2->n);
        temp2 = temp2->next;
    }
    printf(" %d ", temp2->n);
}

/* To traverse from end recursively */
void traverseend(int i)
{
    if (temp2 != NULL)
    {
        i = temp2->n;
        temp2 = temp2->next;
        traverseend(i);
        printf(" %d ", i);
    }
}

/* Para buscar un elemento de la lista */
void search()
{
    int data, count = 0;
    temp2 = h;

    if (temp2 == NULL)
    {
        printf("n Error : La lista esta vacía para buscar datos");
        return;
    }
    printf("n Ingrese el valor a buscar : ");
    scanf("%d", &data);
    while (temp2 != NULL)
    {
        if (temp2->n == data)
        {
            printf("n Dato encontrado en la posición %d ",count + 1);
            return;
        }
        else
             temp2 = temp2->next;
            count++;
    }
    printf("n Error : %d no fue encontrado en la lista", data);
}

/* Para actualizar el valor de un nodo en la lista*/
void update()
{
    int data, data1;

    printf("n Ingrese el nodo a ser actualizado: ");
    scanf("%d", &data);
    printf("n Ingrese el nuevo dato : ");
    scanf("%d", &data1);
    temp2 = h;
    if (temp2 == NULL)
    {
        printf("n Error : Lista vacia, no hay nodo que actualizar");
        return;
    }
    while (temp2 != NULL)
    {
        if (temp2->n == data)
        {

            temp2->n = data1;
            traversebeg();
            return;
        }
        else
            temp2 = temp2->next;
    }

    printf("n Error : %d no fue encontado en la lista para actualizarlo", data);
}

/* Para ordenar la lista enlazada */
void sort()
{
    int x;

    temp2 = h;
    temp4 = h;

    if (temp2 == NULL)
    {
        printf("n La lista esta vacia para ordenar");
        return;
    }

    for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
    {
        for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
        {
            if (temp2->n > temp4->n)
            {
                x = temp2->n;
                temp2->n = temp4->n;
                temp4->n = x;
            }
        }
    }
    traversebeg();

}



DUDAS: http://en.wikipedia.org/wiki/Linked_data_structure

http://www.sanfoundry.com/c-program-doubly-linked-list/
0
0
0
5
0No comments yet