Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Listas en C (página 2)




Enviado por n n



Partes: 1, 2

  • el puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento

  • el puntero anterior del elemento actual apunta hacia el nuevo elemento

  • el puntero fin no cambia

  • el puntero inicio cambia si la posición elegida es la posición 1

  • el tamaño se incrementa en una unidad

  • Monografias.com

    La función

    int ins_antes (dl_Lista * lista, char *dato, int pos){

    int i;

    dl_Elemento *nuevo_elemento, *actual;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    actual = lista->inicio;

    for (i = 1; i < pos; ++i)

    actual = actual->siguiente;

    nuevo_elemento->siguiente = actual;

    nuevo_elemento-> anterior = actual->anterior;

    if(actual->anterior == NULL)

    lista->inicio = nuevo_elemento;

    else

    actual->anterior->siguiente = nuevo_elemento;

    actual->anterior = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    5. Inserción después de un elemento de la lista

    Modelo de la función:

    int ins_después (dl_Lista * lista, char *dato, int pos);

    La función devuelve -1 en caso de error, si no devuelve 0. La inserción se efectuará después de cierta posición pasado como argumento a la función. La posición indicada no debe ser el último elemento. En ese caso hay que utilizar la función de inserción al final de la lista. Etapas:

    • asignación de memoria al nuevo elemento

    • rellenar el campo de datos del nuevo elemento

    • Elegir una posición en la lista (la inserción se hará después de la posición elegida)

    • el puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero siguiente del elemento actual (ver la imagen).

    • el puntero anterior del nuevo elemento apunta hacia el elemento actual.

    • el puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo elemento.

    • el puntero siguiente del elemento actual apunta hacia el nuevo elemento

    • el puntero inicio no cambia

    • el puntero fin cambia si la posición elegida es la posición del ultimo elemento (el tamaño de la lista)

    • el tamaño se incrementa en una unidad

    Monografias.com

    La función

    int ins_después (dl_Lista * lista, char *dato, int pos){

    int i;

    dl_Elemento *nuevo_elemento, *actual;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    actual = lista->inicio;

    for (i = 1; i < pos; ++i)

    actual = actual->siguiente;

    nuevo_elemento->siguiente = actual->siguiente;

    nuevo_elemento->anterior = actual;

    if(actual->siguiente == NULL)

    lista->fin = nuevo_elemento;

    else

    actual->siguiente->anterior = nuevo_elemento;

    actual->siguiente = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    Eliminación de un elemento de la lista

    A continuación el algoritmo para eliminar un elemento de la lista:

    • uso de un puntero temporal para guardar la dirección de los elementos a eliminar

    • el elemento a eliminar puede encontrase en cualquier posición en la lista.

    En relación a la lista enlazada simple en el que la eliminación solo puede ser hecha después que un elemento ha sido designado, las listas doblemente enlazadas son más flexibles gracias a los 2 punteros que permiten guardar el rastro tanto hacia atrás como hacia delante.

    • liberar la memoria ocupada por el elemento eliminado

    • actualizar el tamaño de la lista

    Para eliminar un elemento de la lista hay varias situaciones:

    • Eliminación al inicio de la lista

    • Eliminación al final de la lista

    • Eliminación antes de un elemento

    • Eliminación después de un elemento

    • 5 Eliminación de un elemento

    Sin embargo, la eliminación al inicio y al final de la lista doblemente enlazada así como antes o después de un elemento equivale a la eliminación en la posición 0 (cero) o en la posición N (N= numero de elementos de la lista) o en otra parte de la lista. En el caso de listas doblemente enlazadas la eliminación en cualquier posición no presenta ningún problema gracias a los punteros anterior y siguiente, que permiten conservar el enlace entre los elementos de la lista. Razón por la cual solo vamos a crear una función.

    • si deseamos eliminar el elemento al inicio de la lista elegiremos la posición cero

    • si deseamos eliminar el elemento al final de la lista elegiremos la posición N (el numero de elementos)

    • si deseamos eliminar cualquier elemento entonces elegimos su posición en la lista.

    Eliminación en la lista

    Modelo de la función:

    int supp(dl_Lista *lista, int pos);

    La función devuelve -1 en caso de error, si no devuelve 0. Podemos distinguir varias situaciones:

    • eliminación en la posición 1 en una lista con un solo elemento

    • eliminación en la posición 1 en una lista con varios elementos

    • eliminación en la ultima posición (el ultimo elemento)

    • eliminación en otra parte de la lista en cierta posición

    La eliminación en una lista vacía no tiene sentido Etapas:

    • La posición elegida es 1 (el caso de eliminación del 1er elemento de la lista)

    • el puntero sup_elemento contendrá la dirección del 1er elemento

    • el puntero inicio contendrá la dirección contenida por el puntero siguiente del 1er elemento que deseamos eliminar (si este puntero vale NULL entonces actualizamos el puntero fin ya que estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior del 2do elemento hacia NULL)

    Monografias.com

    • la posición elegida es igual al numero de elementos de la lista

    • el puntero sup_elemento contendrá la dirección del ultimo elemento

    • hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que apunta el puntero del ultimo elemento), hacia NULL

    • actualizamos el puntero fin

    Monografias.com

    • la posición elegida es aleatoria en la lista

    • el puntero sup_elemento contendrá la dirección del elemento a eliminar

    • el puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección contenida en el puntero siguiente del elemento a eliminar

    • el puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección contenida en el puntero anterior del elemento a eliminar.

    • el tamaño de la lista será disminuida en 1 elemento

    Monografias.com

    La función

    int supp(dl_Lista *lista, int pos){

    int i;

    dl_Elemento *sup_elemento,*actual;

    if(lista->tamaño == 0)

    return -1;

    if(pos == 1){ /* eliminación del 1er elemento */

    sup_elemento = lista->inicio;

    lista->inicio = lista->inicio->siguiente;

    if(lista->inicio == NULL)

    lista->fin = NULL;

    else

    lista->inicio->anterior == NULL;

    }else if(pos == lista->tamaño){ /* eliminación del último elemento */

    sup_elemento = lista->fin;

    lista->fin->anterior->siguiente = NULL;

    lista->fin = lista->fin->anterior;

    }else { /* eliminación en otra parte */

    actual = lista->inicio;

    for(i=1;i/font>

    actual = actual->siguiente;

    sup_elemento = actual;

    actual->anterior->siguiente = actual->siguiente;

    actual->siguiente->anterior = actual->anterior;

    }

    free(sup_elemento->dato);

    free(sup_elemento);

    lista->tamaño–;

    return 0;

    }

    Visualización de la lista

    Para mostrar la lista entera podemos posicionarnos al inicio
    o al final de la lista (el puntero inicio o fin lo permitirá).
    Luego utilizando el puntero siguiente o anterior de cada elemento,
    la lista es recorrida del 1er al ultimo elemento o del ultimo al 1er elemento.
    La condición para detener es dada por el puntero siguiente del
    ultimo elemento que vale NULL en el caso de la lectura del inicio hacia el fin
    de la lista, o por el puntero anterior del 1er elemento que vale NULL,
    en el caso de una lectura del final hacia el inicio de la lista. Las funciones

    void affiche(dl_Lista *lista){ /* visualización hacia
    adelante */

    dl_Elemento *actual;

    actual = lista->inicio; /* punto de inicio el 1er elemento
    */

    printf("[ ");

    while(actual != NULL){

    printf("%s ",actual->dato);

    actual = actual->siguiente;

    }

    printf("]n");

    }

    void mustra_inv(dl_Lista *lista){ /* visualización
    hacia atrás */

    dl_Elemento *actual;

    actual = lista->fin; /* punto de inicio el ultimo elemento
    */

    printf("[ ");

    while(actual != NULL){

    printf("%s : ",actual->dato);

    actual = actual->anterior;

    }

    printf("]n");

    }

    Destrucción de la lista

    Para destruir la lista entera, he utilizado la eliminación
    en la posición 1 ya que el tamaño es mayor a cero. La función

    void destruir(dl_Lista *lista){

    while(lista->tamaño > 0)

    sup(lista,1);

    }

    V. Ejemplo completo

    dlista.h

    /* ———- dlista.h ———– */

    typedef struct dl_ElementooLista{

    char *dato;

    struct dl_ElementoLista *anterior;

    struct dl_ElementoLista *siguiente;

    } dl_Elemento;

    typedef struct dl_ListaIdentificar{

    dl_Elemento *inicio;

    dl_Elemento *fin;

    int tamaño;

    } dl_Lista;

    /* inicialización de la liste */

    void inicialización (dl_Lista * lista);

    dl_Elemento *alloc (dl_Elemento * nuevo_elemento);

    /* INSERCION */

    int ins_en_lista_vacia (dl_Lista * lista, char *dato);

    int ins_inicio_lista(dl_Lista * lista, char *dato);

    int ins_fin_lista(dl_Lista * lista, char *dato);

    int ins_después (dl_Lista * lista, char *dato, int
    pos);

    int ins_antes (dl_Lista * lista, char *dato, int pos);

    /*ELIMINACION*/

    int sup(dl_Lista *liste, int pos);

    void muestra (dl_Lista * lista);

    /**************************/

    void muestra_inv (dl_Lista * lista);

    void destruir (dl_Lista * lista);

    /* ——– FIN lista.h ——— */

    dlista_function.h

    /***************************

    * dlista_function.h *

    ***************************/

    void inicialización (dl_Lista * lista){

    lista->inicio = NULL;

    lista->fin = NULL;

    lista->tamaño = 0;

    }

    int inserción_en_lista_vacia (dl_Lista * lista, char
    *dato){

    dl_Elemento *nuevo_elemento;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->anterior = NULL;

    nuevo_elemento->siguiente = NULL;

    lista->inicio = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    int ins_inicio_lista(dl_Lista * lista, char *dato){

    dl_Elemento *nuevo_elemento;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->anterior = NULL;

    nuevo_elemento->siguiente = lista->inicio;

    lista->inicio->anterior = nuevo_elemento;

    lista->inicio = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    int ins_fin_lista(dl_Lista * lista, char *dato){

    dl_Elemento *nuevo_elemento;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->siguiente = NULL;

    nuevo_elemento->anterior = lista->fin;

    lista->fin->siguiente = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    int ins_después (dl_Lista * lista, char *dato, int
    pos){

    int i;

    dl_Elemento *nuevo_elemento, *actual;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    actual = lista->inicio;

    for (i = 1; i < pos; i)

    actual = actual->siguiente;

    nuevo_elemento->siguiente = actual->siguiente;

    nuevo_elemento->anterior = actual;

    if(actual->siguiente == NULL)

    lista->fin = nuevo_elemento;

    else

    actual->siguiente->anterior = nuevo_elemento;

    actual->siguiente = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    int ins_antes (dl_Lista * lista, char *dato, int pos){

    int i;

    dl_Elemento *nuevo_elemento, *actual;

    if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    actual = lista->inicio;

    for (i = 1; i < pos; i)

    actual = actual->siguiente;

    nuevo_elemento->siguiente = actual;

    nuevo_elemento-> anterior = actual->anterior;

    if(actual->anterior == NULL)

    lista->inicio = nuevo_elemento;

    else

    actual->anterior->siguiente = nuevo_elemento;

    actual->anterior = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    int sup(dl_Lista *lista, int pos){

    int i;

    dl_Elemento *sup_elemento,*actual;

    if(lista->tamaño == 0)

    return -1;

    if(pos == 1){ /* eliminación de 1er elemento */

    sup_elemento = lista->inicio;

    lista->inicio = lista->inicio->siguiente;

    if(lista->inicio == NULL)

    lista->fin = NULL;

    else

    lista->inicio->anterior == NULL;

    }else if(pos == lista->tamaño){ /* eliminacion del
    ultimo elemento */

    sup_elemento = lista->fin;

    lista->fin->anterior->siguiente = NULL;

    lista->fin = lista->fin->anterior;

    }else { /* eliminacion en otra parte */

    actual = lista->inicio;

    for(i=1;igras>i)

    actual = actual->siguiente;

    sup_elemento = actual;

    actual->anterior->siguiente = actual->siguiente;

    actual->siguiente->anterior = actual->anterior;

    }

    free(sup_elemento->dato);

    free(sup_elemento);

    lista->tamaño–;

    return 0;

    }

    void destruir(dl_Lista *lista){

    while(lista->tamaño > 0)

    supp(lista,1);

    }

    dl_Elemento *alloc (dl_Elemento * nuevo_elemento){

    if ((nuevo_elemento = (dl_Elemento *) malloc (sizeof (dl_Elemento)))
    == NULL)

    return NULL;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return NULL;

    return nuevo_elemento;

    }

    int menu (dl_Lista *lista){

    int choix;

    if (lista->tamaño == 0){

    printf ("1. Adición del 1er elementon");

    printf ("2. Eliminarn");

    } else{

    printf ("1. Añadir al inicio de la listan");

    printf ("2. Añadir al final de la listan");

    printf ("3. Añadir antes de la posición
    especificadan");

    printf ("4. Añadir después de la posición
    especificadan");

    printf ("5. Eliminacion en la posicion especificadan");

    printf ("6. Destruir la listan");

    printf ("7. Eliminarn");

    }

    printf ("nnElija: ");

    scanf ("%d", &elección);

    getchar();

    if(lista->tamaño == 0 && elección == 2)

    elección = 7;

    return elección;

    }

    int supp(dl_Lista *lista, int pos);

    void muestra(dl_Lista *lista){

    dl_Elemento *actual;

    actual = lista->inicio;

    printf("[ ");

    while(actual != NULL){

    printf("%s ",actual->dato);

    actual = actual->siguiente;

    }

    printf("]n");

    }

    void muestra_inv(dl_Lista *lista){

    dl_Elemento *actual;

    actual = lista->fin;

    while(actual != NULL){

    printf("%s : ",actual->dato);

    actual = actual->anterior;

    }

    printf("n");

    }

    /* ——– FIN dlista_function.h ——— */

    dlista.c

    /**********************

    * dlista.c *

    **********************/

    #include

    #include

    #include

    #include "dlista.h"

    #include "dlista_function.h"

    int main (void)

    {

    int elección = 0,pos;

    char *dato;

    dato = malloc(50);

    dl_Lista *lista;

    dl_Elemento *piloto = NULL;

    lista = (dl_Lista *) malloc (sizeof(dl_Lista));

    inicialización(lista);

    while(elección != 7){

    elección = menu(lista);

    switch(elección){

    case 1:

    printf("Ingrese un elemento: ");

    scanf("%s",dato);

    getchar();

    if(lista->tamaño == 0)

    inserción_en_lista_vacia(lista,dato);

    else

    ins_inicio_lista(lista, dato);

    printf("%d elementos: deb=%s,fin=%s ",

    lista->tamaño,lista->inicio->dato,lista->fin->dato);

    muestra(lista);

    break;

    case 2:

    printf("Ingrese un elemento: ");

    scanf("%s",dato);

    getchar();

    ins_fin_lista(lista, dato);

    printf("%d elementos: deb=%s,fin=%s ",

    lista->tamaño,lista->inicio->dato,lista->fin->dato);

    muestra(lista);

    break;

    case 3:

    if(lista->tamaño == 1){

    printf("Utilizar la inserción al inicio o al
    final (Ingrese Menu: 1 ó 2)n");

    break;

    }

    printf("Ingrese un elemento: ");

    scanf("%s",dato);

    getchar();

    do{

    printf("Ingrese la posición: ");

    scanf("%d",&pos);

    }while (pos < 1 || pos > lista->tamaño);

    getchar();

    ins_antes(liste,dato,pos);

    printf("%d elementos: deb=%s fin=%s ",

    lista->tamaño,lista->inicio->dato,lista->fin->dato);

    muestra(lista);

    break;

    case 4:

    if(lista->tamaño == 1){

    Printf("Utilizar la inserción al inicio o al
    final (Ingrese Menu: 1 ó 2)n");

    break;

    }

    printf("Ingrese un elemento: ");

    scanf("%s",dato);

    getchar();

    do{

    printf("Ingrese la posicion: ");

    scanf("%d",&pos);

    }while (pos < 1 || pos > lista->tamaño);

    getchar();

    ins_después(lista,dato,pos);

    printf("%d elementos: deb=%s,fin=%s ",

    lista->tamaño,lista->inicio->dato,lista->fin->dato);

    muestra(lista);

    break;

    case 5:

    do{

    printf("Ingrese la posición : ");

    scanf("%d",&pos);

    }while (pos < 1 || pos > lista->tamaño);

    getchar();

    supp(lista,pos);

    if(lista->tamaño != 0)

    printf("%d elementos: deb=%s,fin=%s ",

    lista->tamaño,lista->inicio->dato,lista->fin->dato);

    else

    printf("liste vide : %d elementos",lista->tamaño);

    muestra(lista);

    break;

    case 6:

    destruir(lista);

    printf("la lista ha sido destruida: %d elementosn",lista->tamaño);

    break;

    }

    }

    return 0;

    }

    /* ——– FIN dlista.c ——— */


    Las pilas – Último en entrar, primero en salir (LIFO)

    • Requisitos

    • INTRUDUCCION

    • Definición

    • La construcción del modelo de un elemento de la
      pila

    • Operaciones sobre las pilas

    • Inicialización

    • Inserción de un elemento en la pila

    • Eliminar un elemento de la pila

    • Visualización de la pila

    • Recuperación del dato en la cabeza de la pila

    • V. Ejemplo completo

    • pila.h

    • pila_function.h

    • pila.c

    Requisitos

    Los tipos de datos Las estructuras El uso de typedef Los punteros
    Las funciones de usuario Las listas simplemente enlazadas Las listas doblemente
    enlazadas

    I. INTRUDUCCION

    El objetivo de este articulo es que el lector comprenda el
    empleo de las pilas. Para explicar el algoritmo he elegido utilizar una
    lista enlazada simple. Por lo tanto la comprensión de las listas enlazadas
    es necesaria.

    II. Definición

    La pila es una estructura de datos que permite almacenar
    datos en el orden LIFO (Last In First Out) en español, último
    en entrar, primero en salir). La recuperación de los datos es hecha en
    el orden inverso de su inserción. Para la implementación he elegido
    una lista enlazada simple, presentada sobre la vertical. Ya que la inserción
    es siempre hecha al inicio de la lista, el 1er elemento de la lista será
    el ultimo elemento ingresado, por lo tanto estará en la cabeza de la
    pila. No he utilizado un puntero fin, como lo hice en el caso de la lista
    enlazada simple, ya que el objetivo no es el de tratar una lista enlazada, sino
    una pila. Lo interesante es que el ultimo elemento ingresado, será
    el 1er elemento recuperado.

    Monografias.com

    III. La construcción del modelo de un elemento de
    la pila

    Para definir un elemento de la pila será utilizado
    el tipo struct. El elemento de la pila contendrá un campo dato
    y un puntero siguiente. El puntero siguiente debe ser del
    mismo tipo que el elemento, de lo contrario no podrá apuntar hacia el
    elemento. El puntero siguiente permitirá el acceso al próximo
    elemento.

    typedef struct ElementoLista {

    char *dato;

    struct ElementoLista *siguiente;

    }Elemento;

    Para permitir las operaciones sobre la pila, vamos a guardar
    ciertos elementos:

    • el primer elemento

    • el numero de elementos

    El 1er elemento, que se encuentra en la cabeza de la pila,
    nos permitirá realizar la operación de recuperación de
    los datos situados en la parte superior de la pila. Para ello, será utilizada
    otra estructura (no es obligatorio, pueden ser utilizadas variables).

    typedef struct ListaUbicación{

    Elemento *inicio;

    int tamaño;

    } Pila;

    El puntero inicio contendrá la dirección
    del 1er elemento de la lista. La variable tamaño contiene el numero
    de elementos. Nota: Esta vez no utilizamos un puntero fin (ver la lista
    enlazada simple), no lo necesitamos puesto que únicamente trabajamos
    al inicio de la lista. Cualquiera que sea la posición en la lista, el
    puntero inicio apunta siempre hacia el 1er elemento, que estará
    en la cabeza de la pila. El campo tamaño contendrá el numero
    de elementos de la pila, cualquiera que sea la operación efectuada sobre
    la pila.

    IV. Operaciones sobre las pilas

    A. Inicialización

    Modelo de la función:

    void inicialización (Pila *tas);

    Esta operación debe ser hecha antes de cualquier otra
    operación sobre la pila. Esta inicializa el puntero inicio con
    el puntero NULL, y el tamaño con el valor 0. La función

    void inicialización (Pila * tas){

    tas->inicio = NULL;

    tas->tamaño = 0;

    }

    B. Inserción de un elemento en la pila

    A continuación el algoritmo de inserción y registro
    de los elementos:

    • declaración del elemento a insertar

    • asignación de la memoria para el nuevo elemento

    • rellenar el contenido del campo de datos

    • actualizar el puntero inicio hacia el 1er elemento
      (la cabeza de la pila)

    • Actualizar el tamaño de la pila.

    Modelo de la función:

    int apilar (Pila *tas, char *dato);

    La primera imagen muestra el inicio de la inserción,
    por lo tanto la lista de tamaño 1 después de la inserción.
    La característica de la pila no es muy apreciada con un solo elemento,
    ya que es el único a recuperar.

    Monografias.com

    En cambio la 2da imagen nos permite observar el comportamiento
    de la pila. Lo que debemos retener es que la inserción siempre se hace
    en la parte superior de la pila (al inicio de la lista).

    Monografias.com

    La función

    /* apilar (añadir) un elemento en la pila */

    int apilar (Pila * tas, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->siguiente = tas->inicio;

    tas->inicio = nuevo_elemento;

    tas->tamaño++;

    }

    C. Eliminar un elemento de la pila

    Para eliminar un elemento de la pila, simplemente hay que
    eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación
    no permite recuperar el dato en la cabeza de la pila, solo eliminarlo. Modelo
    de la función:

    int desapilar (Pila *tas);

    La función devuelve -1 en caso de error, si no devuelve
    0. Las etapas:

    • el puntero sup_elemento contendrá la dirección
      del 1er elemento

    • el puntero inicio apuntará hacia el 2do
      elemento (después de la eliminación del 1er elemento, el 2do
      elemento estará en la cabeza de la pila)

    • el tamaño de la pila disminuirá un
      elemento.

    Monografias.com

    La función

    int desapilar (Pila * tas){

    Elemento *sup_elemento;

    if (tas->tamaño == 0)

    return -1;

    sup_elemento = tas->inicio;

    tas->inicio = tas->inicio->siguiente;

    free (sup_elemento->dato);

    free (sup_elemento);

    tas->tamaño–;

    return 0;

    }

    D. Visualización de la pila

    Para mostrar la pila entera, es necesario posicionarse al
    inicio de la pila (el puntero inicio lo permitirá). Luego, utilizando
    el puntero siguiente de cada elemento, la pila es recorrida del 1er hacia
    el ultimo elemento. La condición para detenerse es dada por el tamaño
    de la pila. La función

    /* visualización de la pila */

    void muestra (Pila * tas){

    Elemento *actual;

    int i;

    actual = tas->inicio;

    for(i=0;itamaño;++i){

    printf("tt%sn", actual->dato);

    actual = actual->siguiente;

    }

    }

    E. Recuperación del dato en la cabeza de la pila

    Para recuperar el dato en la cabeza de la pila sin eliminarlo,
    he utilizado una macro. La macro lee los datos en la parte superior de la pila
    utilizando el puntero inicio.

    #define pila_dato(tas) tas->inicio->dato

    V. Ejemplo completo

    pila.h

    /*********************

    * pila.h *

    *********************/

    typedef struct ElementoLista{

    char *dato;

    struct ElementoLista *siguiente;

    } Elemento;

    typedef struct ListaUbicación{

    Elemento *inicio;

    int tamaño;

    } Pila;

    /* inicialización */

    void inicialización (Pila *tas);

    /* APILAR*/

    int apilar (Pile *tas, char *dato);

    /* DESAPILAR*/

    int desapilar (Pila *tas);

    /* Visualización del elemento en la cabeza de la pila
    (LastInFirstOut) */

    #define pila_dato(tas) tas->inicio->dato

    /* muestra la pila */

    void muestra (Pila *tas);

    pila_function.h

    /***********************

    * pila_function.h *

    ***********************/

    void inicialización (Pila * tas){

    tas->inicio = NULL;

    tas->tamaño = 0;

    }

    /* apilar (añadir) un elemento en la pila */

    int apilar (Pila * tas, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->siguiente = tas->inicio;

    tas->inicio = nuevo_elemento;

    tas->tamaño++;

    }

    /* desapilar (eliminar un elemento de la pila */

    int desapilar (Pila * tas){

    Elemento *sup_elemento;

    if (tas->tamaño == 0)

    return -1;

    sup_elemento = tas->inicio;

    tas->inicio = tas->inicio->siguiente;

    free (sup_elemento->dato);

    free (sup_elemento);

    tas->tamaño–;

    return 0;

    }

    /* visualización de la pila */

    void muestra (Pila * tas){

    Elemento *actual;

    int i;

    actual = tas->inicio;

    for(i=0;itamaño;++i){

    printf("tt%sn", actual->dato);

    actual = actual->siguiente;

    }

    }

    pila.c

    /*********************

    * pila.c *

    *********************/

    #include

    #include

    #include

    #include "pila.h"

    #include "pila_function.h"

    int main ()

    {

    Pila *tas;

    char *nom;

    if ((tas = (Pila *) malloc (sizeof (Pila))) == NULL)

    return -1;

    if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)

    return -1;

    inicialización (tas);

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    apilar (tas, nom);

    printf ("La pila (%de elementos): n",tas->tamaño);

    printf("n********** Cabeza de la PILA **********n");

    muestra(tas);

    printf("__________ Bajo de la PILA __________nn");

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    apilar (tas, nom);

    printf ("La pila (%de elementos): n",tas->tamaño);

    printf("n********** Cabeza de la PILA **********n");

    muestra(tas);

    printf("__________ Bajo de la PILA __________nn");

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    apilar (tas, nom);

    printf ("La pila (%de elementos): n",tas->tamaño);

    printf("n********** Cabeza de la PILA **********n");

    muestra(tas);

    printf("__________ Bajo de la PILA __________nn");

    printf ("nLa ultima entrada (LastInFirstOut) [ %s ]
    sera eliminada",

    pile_dato(tas));

    printf ("nLa ultima entrada es eliminadan");

    desapilar (tas); /* eliminación del ultimo elemento
    ingresado */

    printf ("La pila (%de elementos): n",tas->tamaño);

    printf("n********** Cabeza de la PILA **********n");

    muestra(tas);

    printf("__________ Bajo de la PILA __________nn");

    return 0;

    }

    Las filas – Primero en Entrar, Primero en salir (FIFO)

    • Requisitos

    • Introducción

    • Definición

    • La construcción del modelo de un elemento de la
      fila

    • Operaciones sobre las filas

    • A. Inicialización

    • B. Inserción

    • C. Eliminar un elemento de la fila

    • D. Visualización de la fila

    • E. Recuperación del dato al inicio de la fila

    • V. Ejemplo completo

    • fila.h

    • fila_function.h

    • fila.c

    Requisitos

    Los tipos de datos Las estructuras El uso de typedef Los punteros
    Las funciones de usuario Las listas simplemente enlazadas Las listas doblemente
    enlazadas

    I. Introducción

    El objetivo de este articulo es que el lector comprenda el
    empleo de las filas. Para explicar el algoritmo he elegido utilizar una
    lista enlazada simple. Por lo que la comprensión de las listas enlazadas
    es necesaria.

    II. Definición

    La fila es una estructura de datos que permite almacenar
    datos en el orden FIFO (First In First Out) en español, Primero
    en Entrar, Primero en Salir). La recuperación de los datos es hecha en
    el orden en que son insertados. Para la implementación he elegido una
    lista enlazada simple. La inserción en la fila se hará en el orden
    normal, el 1er elemento de la fila será el primer elemento ingresado,
    por lo tanto su posición es al inicio de la fila.

    Monografias.com

    III. La construcción del modelo de un elemento de
    la fila

    Para definir un elemento de la fila será utilizado
    el tipo struct. El elemento de la fila contendrá un campo dato
    y un puntero siguiente. El puntero siguiente debe ser del
    mismo tipo que el elemento, de lo contrario no podrá apuntar hacia el
    elemento. El puntero siguiente permitirá el acceso al próximo
    elemento.

    typedef struct ElementoLista {

    char *dato;

    struct ElementoLista *siguiente;

    }Elemento;

    Para tener el control de la fila, es preferible guardar
    ciertos elementos: el primer elemento, el último elemento, el número
    de elementos. Para ello, será utilizada otra estructura (no es obligatorio,
    pueden ser utilizadas variables).

    typedef struct ListaUbicación{

    Elemento *inicio;

    Elemento *fin;

    int tamaño;

    } Fila;

    IV. Operaciones sobre las filas

    A. Inicialización

    Modelo de la función:

    void initialisation (Fila * serie);

    Esta operación debe ser hecha antes de cualquier otra
    operación sobre la fila. Esta inicializa el puntero inicio y el
    puntero fin con el puntero NULL, y el tamaño con el valor
    0. La función

    void inicialización (Fila * serie){

    serie->inicio = NULL;

    serie->fin = NULL;

    serie->tamaño = 0;

    }

    B. Inserción

    A continuación el algoritmo de inserción y registro
    de los elementos:

    • declaración del elemento a insertar

    • asignación de la memoria para el nuevo elemento

    • rellenar el contenido del campo de datos

    • actualizar el puntero inicio hacia el 1er elemento
      (el inicio de la fila)

    • actualizar el puntero fin (esto nos servirá para
      la inserción hacia el final de la fila)

    • actualizar el tamaño de la pila.

    Modelo de la función:

    int insertar (Fila * serie, Elemento * actual, char *dato);

    La primera imagen muestra el inicio de la inserción,
    por lo que el tamaño de la lista es 1 después de la inserción.

    Monografias.com

    En la fila, el elemento a recuperar es el primero en entrar.
    Por ello, la inserción se hará siempre al final de la fila. Es
    el orden normal de la inserción (1ro, 2do, 3ro, etc.)

    Monografias.com

    La función

    int insertar (Fila * serie, Elemento * actual, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    if(actual == NULL){

    if(serie->tamaño == 0)

    serie->fin = nuevo_elemento;

    nuevo_elemento->siguiente = serie->inicio;

    serie->inicio = nuevo_elemento;

    }else {

    if(actual->siguiente == NULL)

    serie->fin = nuevo_elemento;

    nuevo_elemento->siguiente = actual->siguiente;

    actual->siguiente = nuevo_elemento;

    }

    serie->tamaño++;

    return 0;

    }

    C. Eliminar un elemento de la fila

    Para eliminar un elemento de la fila, simplemente hay que
    eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación
    no permite recuperar el dato al inicio de la fila (el primer dato), solo
    eliminarlo. Modelo de la función:

    int eliminar (Fila * serie);

    La función devuelve -1 en caso de error, si no devuelve
    0. Las etapas:

    • el puntero sup_elemento contendrá la dirección
      del 1er elemento

    • el puntero inicio apuntará hacia el 2do
      elemento (después de la eliminación del 1er elemento, el 2do
      elemento estará al inicio de la fila)

    • el tamaño de la fila disminuirá un
      elemento.

    Monografias.com

    La función

    int eliminar (Fila * serie){

    Elemento *sup_elemento;

    if (serie->tamaño == 0)

    return -1;

    sup_elemento = serie->inicio;

    serie->inicio = serie->inicio->siguiente;

    free (sup_elemento->dato);

    free (sup_elemento);

    serie->tamaño–;

    return 0;

    }

    D. Visualización de la fila

    Para mostrar la fila entera, es necesario posicionarse
    al inicio de la fila (el puntero inicio lo permitirá). Luego,
    utilizando el puntero siguiente de cada elemento, la fila es recorrida
    del 1er hacia el ultimo elemento. La condición para detenerse es dada
    por el tamaño de la fila. La función

    void muestra(Fila *serie){

    Elemento *actual;

    int i;

    actual = serie->inicio;

    for(i=0;itamaño;++i){

    printf(" %s ", actual->dato);

    actual = actual->siguiente;

    }

    }

    E. Recuperación del dato al inicio de la fila

    Para recuperar el dato al inicio de la fila sin eliminarlo,
    he utilizado una macro. La macro lee los datos al inicio de la fila utilizando
    el puntero inicio.

    #define fila_dato(serie) serie->inicio->dato

    V. Ejemplo completo

    fila.h

    /*********************

    * fila.h *

    *********************/

    typedef struct ElementoLista{

    char *dato;

    struct ElementoLista *siguiente;

    } Elemento;

    typedef struct ListaUbicación{

    Elemento *inicio;

    Elemento *fin;

    int tamaño;

    } Fila;

    /* inicialización */

    void inicialización (Fila * serie);

    /* Insertar*/

    int insertar (Fila * serie, Elemento * actual, char *dato);

    /* Eliminar*/

    int eliminar (Fila * serie);

    /* FirstInFirstOut */

    #define fila_dato(serie) serie->inicio->dato

    /* Muestra la Fila */

    void muestra(Fila *serie);

    fila_function.h

    /***********************

    * fila_function.h *

    ***********************/

    void inicialización (Fila * serie){

    serie->inicio = NULL;

    serie->fin = NULL;

    serie->tamaño = 0;

    }

    /* insertar (añadir) un elemento en la Fila */

    int insertar (Fila * serie, Elemento * actual, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    if(actual == NULL){

    if(serie->tamaño == 0)

    serie->fin = nuevo_elemento;

    nuevo_elemento->siguiente = serie->inicio;

    serie->inicio = nuevo_elemento;

    }else {

    if(actual->siguiente == NULL)

    serie->fin = nuevo_elemento;

    nuevo_elemento->siguiente = actual->siguiente;

    actual->siguiente = nuevo_elemento;

    }

    serie->tamaño;

    return 0;

    }

    /* eliminar (quitar) un elemento de la Fila */

    int eliminar (Fila * serie){

    Elemento *sup_elemento;

    if (serie->tamaño == 0)

    return -1;

    sup_elemento = serie->inicio;

    serie->inicio = serie->inicio->siguiente;

    free (sup_elemento->dato);

    free (sup_elementoo);

    serie->tamaño–;

    return 0;

    }

    /* visualización de la Fila */

    void muestra(Fila *serie){

    Elemento *actual;

    int i;

    actual = serie->inicio;

    for(i=0;itamaño;++i){

    printf(" %s ", actual->dato);

    actual = actual->siguiente;

    }

    }

    fila.c

    /*********************

    * fila.c *

    *********************/

    #include

    #include

    #include

    #include "fila.h"

    #include "fila_function.h"

    int main ()

    {

    Fila *serie;

    char *nom;

    if ((serie = (Fila *) malloc (sizeof (Fila))) == NULL)

    return -1;

    if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)

    return -1;

    inicialización (serie);

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    insertar (serie, serie->fin, nom);

    printf ("La fila (%de elementos)n",serie->tamaño);

    printf("nInicio de la FILA [ ");

    muestra (serie); /*el primero en entrar será mostrado
    */

    printf(" ] Fin de la FILAnn");

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    insertar (serie, serie->fin, nom);

    printf ("La fila (%de elementos)n",serie->tamaño);

    printf("nInicio de la FILA [ ");

    muestra (serie); /*el primer elemento será mostrado
    */

    printf(" ] Fin de la FILAnn");

    printf ("Ingrese una palabra: ");

    scanf ("%s", nom);

    insertar (serie, serie->fin, nom);

    printf ("La fila (%de elementos)n",serie->tamaño);

    printf("nInicio de la FILA [ ");

    muestra (serie); /*el primero en entrar será mostrado
    */

    printf(" ] Fin de la FILAnn");

    printf ("nEl primero en entrar (FirstInFirstOut) [
    %s ] será eliminado",

    fila_dato(serie));

    printf ("nEl primer en entrar es eliminadon");

    eliminar (serie); /* eliminación del primer elemento
    ingresado */

    printf ("La fila (%de elementos): n",serie->tamaño);

    printf("nInicio de la FILA [ ");

    muestra (serie);

    printf(" ] Fin de la FILAnn");

    return 0;

    }

    Listas circulares

    • Requisitos

    • Introducción

    • II Definición

    • La construcción del modelo de un elemento de la
      lista

    • Operaciones sobre las listas circulares

    • A. Inicialización

    • B. Inserción de un elemento en la lista

    • Inserción en una lista vacía

    • Inserción en una lista no vacía

    • C. Eliminación de un elemento en la lista

    • 1. Eliminación al inicio de la lista

    • 2. Eliminación en una lista con un solo elemento

    • D. Mostrar la lista

    • 1. Mostrar la lista (del 1er al último elemento)

    • 2. Mostrar la lista sin una condición para detenerse
      (indefinidamente )

    • E. Destrucción de la lista

    • V. Ejemplo completo

    • lista_circ.h

    • lista_circ_function.h

    • lista_circ.c

    Requisitos

    Los tipos de datos Las estructuras El uso de typedef Los punteros
    La función usuario Las listas enlazadas simples Las listas doblemente
    enlazadas

    I. Introducción

    El objetivo de este artículo es que el lector comprenda
    lo que son las listas circulares

    II Definición

    La lista circular es una especie de lista enlazada simple
    o doblemente enlazada, pero que posee una característica adicional para
    el desplazamiento dentro de la lista, "ésta no tiene fin"
    Para que la lista sea sin fin, el puntero siguiente del último
    elemento apuntará hacia el 1er elemento de la lista en lugar de
    apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples
    o doblemente enlazadas En las listas circulares, nunca se llega a una posición
    en la que ya no sea posible desplazarse. Cuando se llegue al último elemento,
    el desplazamiento volverá a comenzar desde el primer elemento.

    Monografias.com

    III. La construcción del modelo de un elemento de
    la lista

    Para definir un elemento de la lista, el tipo struct será
    utilizado. El elemento de la lista contendrá un campo dato y un
    puntero siguiente. El puntero siguiente debe ser del mismo tipo
    que el elemento, en caso contrario no podrá apuntar hacia el elemento.
    El puntero siguiente permitirá el acceso hacia el próximo
    elemento.

    typedef struct ElementoLista {

    char *dato;

    struct ElementoLista *siguiente;

    }Elemento;

    Para tener el control de l alista es preferible guardar ciertos
    elementos: el primer elemento, el último elemento, el número de
    elementos. Para ello, otra estructura será utilizada (no es obligatorio,
    pueden ser utilizadas variables)

    typedef struct ListaIdentificar {

    Elemento *inicio;

    Elemento *fin;

    int tamaño;

    }Lista;

    El punter inicio contendrá la dirección
    del primer elemento de la lista. El puntero fin contendrá la dirección
    del ultimo elemento de la lista. La variable tamaño contiene
    el número de elementos. Cualquiera que sea la posición en la lista,
    los punteros inicio y fin siempre apuntaran hacia el 1er y el
    último elemento respectivamente. El campo tamaño contendrá
    el número de elementos de la lista cualquiera sea la operación
    efectuada sobre la lista.

    IV. Operaciones sobre las listas circulares

    A. Inicialización

    Modelo de la función

    void inicialización (Lista *lista);

    Esta operación debe ser hecha antes de cualquier otra
    operación sobre la lista. Inicializa el puntero inicio y el puntero
    fin con el puntero NULL, y el tamaño con el valor 0. La función:

    void inicialización (Lista *lista){

    lista->inicio = NULL;

    lista->fin = NULL;

    tamaño = 0;

    }

    B. Inserción de un elemento en la lista

    A continuación el algoritmo de inserción y registro
    de los elementos:

    • declaración del elemento a insertar

    • asignación de la memoria para el nuevo elemento

    • rellenar el contenido del campo de datos

    • actualizar los punteros hacia el 1er y ultimo elemento
      si es necesario.

    • Caso particular: en una lista con un solo elemento, el
      1er elemento es al mismo tiempo el ultimo.

    • Actualizar el tamaño de la lista.

    1. Inserción en una lista vacía

    Modelo de la función:

    int ins_lista_circ_vacia(Lista * lista, char *dato);

    La función devuelve -1 en caso de error, si no devuelve
    0. Etapas:

    • asignación de memoria para el nuevo elemento

    • rellenar el campo de datos del nuevo elemento

    • el puntero siguiente del nuevo elemento apuntará
      hacia si mismo (es la etapa que vuelve a la lista circular)

    • los punteros inicio y fin apuntaran hacia
      el nuevo elemento

    • el tamaño es actualizado

    Monografias.com

    La función:

    /* inserción en una lista vacía */

    int ins_lista_circ_vacia(Lista * lista, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))

    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->siguiente = nuevo_elemento;

    lista->inicio = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    2. Inserción en una lista no vacía

    Modelo de la función:

    int ins_lista_circ(Lista * lista, Elemento *actual, char *dato);

    La función devuelve -1 en caso de error, si no devuelve
    0. La inserción se efectuara al final de la lista. Etapas:

    • asignación de memoria para el nuevo elemento

    • rellenar el campo de datos del nuevo elemento

    • el puntero siguiente del nuevo elemento apunta
      hacia la dirección del primer elemento (conservar la lista circular)

    • el puntero inicio no cambia

    • el puntero fin apunta hacia el nuevo elemento

    • el tamaño se incrementa en una unidad

    Monografias.com

    La función:

    /* inserción en una lista no vacía */

    int ins_lista_circ(Lista * lista, Elemento *actual, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))

    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    if(actual != lista->fin)

    return -1;

    nuevo_elemento->siguiente = actual->siguiente;

    actual->siguiente = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño++;

    return 0;

    }

    C. Eliminación de un elemento en la lista

    A continuación el algoritmo de eliminación de
    un elemento de la lista:

    • uso de un puntero temporal para guardar la dirección
      de los elementos a eliminar

    • el elemento a eliminar se encuentra después del
      elemento actual

    Hacer apuntar el puntero siguiente del elemento actual
    hacia la dirección del puntero siguiente del elemento a eliminar

    • liberar la memoria ocupada por el elemento eliminado

    • actualizar el tamaño de la lista

    Para eliminar un elemento de la lista hay varias situaciones:

    • Eliminación dentro de la lista

    • Eliminación del último elemento de la lista

    1. Eliminación al inicio de la lista

    Modelo de la función:

    int sup_list_circ(Lista *lista);

    La función devuelve -1 en caso de error, si no devuelve
    0. Etapas:

    • el puntero sup_elemento contendrá la dirección
      del 1er elemento

    • el puntero inicio apuntara hacia el 2do elemento

    • el puntero siguiente del ultimo elemento apuntara
      hacia el 1er elemento (que era el 2do antes de la eliminación)

    • el tamaño de la lista disminuirá 1 elemento.

    Monografias.com

    La función:

    /* eliminación al inicio de la lista */

    int sup_lista_circ(Lista * lista){

    if (lista->tamaño < 2)

    return -1;

    Elemento *sup_element;

    sup_elemento = lista->inicio;

    lista->inicio = lista->inicio->siguiente;

    lista->fin->siguiente = lista->inicio;

    free (sup_elemento->dato);

    free (sup_elemento);

    lista->tamaño–;

    return 0;

    }

    2. Eliminación en una lista con un solo elemento

    Modelo de la función:

    int sup_list_circ_unica(Lista *lista);

    La función devuelve -1 en caso de error, si no devuelve
    0. Etapas:

    • el puntero sup_elemento contendrá la dirección
      del elemento (la lista contiene un solo elemento)

    • el puntero inicio apuntara hacia NULL

    • el puntero fin apuntara hacia NULL

    • el tamaño de la lista disminuirá un elemento.

    Monografias.com

    La función:

    /* eliminación en una lista con un solo elemento*/

    int sup_lista_circ_unica(Lista *lista){

    if (lista->tamaño != 1)

    return -1;

    Elemento *sup_elemento;

    sup_elemento = lista->inicio;

    lista->inicio = NULL;

    lista->fin = NULL;

    free (sup_elemento->dato);

    free (sup_elemento);

    lista->tamaño–;

    return 0;

    }

    D. Mostrar la lista

    Para mostrar la lista completa, es necesario posicionarse
    al inicio de la lista (el puntero inicio lo permitirá). Luego,
    utilizando el puntero siguiente de cada elemento, la lista es recorrida
    del 1er al ultimo elemento. En comparación con las listas simples y doblemente
    enlazadas, en el que la condición para detenerse esta dada por el puntero
    siguiente del ultimo elemento, que vale NULL, para la lista circular,
    no hay punto de detención, a menos que elijamos uno. A continuación
    dos variantes de visualización:

    • Mostrar la lista (del 1er al último elemento)

    • Mostrar la lista sin una condición para detenerse.

    1. Mostrar la lista (del 1er al último elemento)

    Utilizaremos el tamaño de la lista como la condición
    para detenerse. La función:

    /* mostrar la lista */

    void mostrar (Lista * lista){

    Elemento *actual;

    actual = lista->inicio;

    int i;

    for(i=0;itamaño;++i){

    printf ("%p – %sn", actual, actual->dato);

    actual = actual->siguiente;

    }

    }

    2. Mostrar la lista sin una condición para detenerse
    (indefinidamente )

    La función:

    /* recorrer la lista indefinidamente*/

    void mostrar_indefinidamente (Lista * lista){

    Elemento *actual;

    actual = lista->inicio;

    while (1){

    printf ("%p – %sn", actual, actual->dato);

    actual = actual->siguiente;

    }

    }

    E. Destrucción de la lista

    Para destruir la lista completa, he utilizado al eliminación
    al inicio de la lista ya que el tamaño es mayor a 1, luego la eliminación
    en una lista con un solo elemento. La función:

    /* destruir la lista */

    void destruir (Lista * lista){

    while (lista->tamaño > 0){

    if(lista->tamaño > 1)

    sup_lista_circ (lista);

    else

    sup_lista_circ_unica(lista);

    }

    }

    V. Ejemplo completo

    lista_circ.h

    /* ———- lista_circ.h ———– */

    typedef struct ElementoListaCirc {

    char *dato;

    struct ElementoListaCirc *siguiente;

    } Element;

    typedef struct ListaIdentificarCirc {

    Elemento *inicio;

    Elemento *fin;

    int tamaño;

    } Lista;

    /* inicialización de la lista */

    void inicialización (Lista * lista);

    /* INSERCION */

    /* inserción en una lista vacia */

    int ins_lista_circ_vacia(Lista * lista, char *dato);

    int ins_lista_circ(Lista * lista, Elemento *actual, char *dato);

    /* ELIMINACION */

    int sup_lista_circ (Lista * lista);

    int sup_lista_circ_unica (Lista * lista);

    int menu (Lista *lista);

    void mostrar (Lista * lista);

    void mostrar_infinito (Lista * lista);

    void destruir (Lista * lista);

    /* ——– FIN lista_circ.h ——— */

    lista_circ_function.h

    /******************************

    * lista_circ_function.h *

    ******************************/

    void inicialización (Lista * lista){

    lista->inicio = NULL;

    lista->fin = NULL;

    lista->tamaño = 0;

    }

    /* inserción en una lista vacia */

    int ins_lista_circ_vacia(Lista * lista, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))

    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    nuevo_elemento->siguiente = nuevo_elemento;

    lista->inicio = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño;

    return 0;

    }

    /* inserción en una lista no vacia */

    int ins_lista_circ(Lista * lista, Elemento *actual, char *dato){

    Elemento *nuevo_elemento;

    if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))

    == NULL)

    return -1;

    if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
    (char)))

    == NULL)

    return -1;

    strcpy (nuevo_elemento->dato, dato);

    if(actual != lista->fin)

    return -1;

    nuevo_elemento->siguiente = actual->siguiente;

    actual->siguiente = nuevo_elemento;

    lista->fin = nuevo_elemento;

    lista->tamaño;

    return 0;

    }

    /* eliminación al inicio de la lista */

    int sup_lista_circ(Lista * lista){

    if (lista->tamaño < 2)

    return -1;

    Elemento *sup_elemento;

    sup_elemento = lista->inicio;

    lista->inicio = lista->inicio->siguiente;

    lista->fin->siguiente = lista->inicio;

    free (sup_elemento->dato);

    free (sup_elemento);

    lista->tamaño–;

    return 0;

    }

    /* eliminación en una lista con un solo elemento*/

    int sup_lista_circ_unica(Lista *lista){

    if (lista->tamaño != 1)

    return -1;

    Elemento *sup_elemento;

    sup_elemento = lista->inicio;

    lista->inicio = NULL;

    lista->fin = NULL;

    free (sup_elemento->dato);

    free (sup_elemento);

    lista->tamaño–;

    return 0;

    }

    /* mostrar la lista */

    void mostrar (Lista * lista){

    Elemento *actual;

    actual = lista->inicio;

    int i;

    for(i=0;itamaño;++i){

    printf ("%p – %sn", actual, actual->dato);

    actual = actual->siguiente;

    }

    }

    /* recorrer la lista indefinidamente*/

    void mostrar_infinito (Lista * lista){

    Elemento *actual;

    actual = lista->inicio;

    while (1){

    printf ("%p – %sn", actual, actual->dato);

    actual = actual->siguiente;

    }

    }

    /* destruir la liste */

    void destruir (Lista * lista){

    while (lista->tamaño > 0){

    if(lista->tamaño > 1)

    sup_lista_circ (lista);

    else

    sup_lista_circ_unica(lista);

    }

    }

    int menu (Lista *lista){

    int elección; printf("********** MENU **********n");

    if (lista->tamaño == 0){

    printf ("1. Adicion del 1er elementon");

    printf ("2. Quitarn");

    }else {

    printf ("1. Adición de un elementon");

    printf ("2. Eliminación al inicio (la lista debe
    tener al menos 2 elementos)n");

    printf ("3. Eliminación en una lista con un solo
    elementon");

    printf ("4. Mostrar lista circularn");

    printf ("5. Mostrar lista circular [Ctrl-C] para quitar
    el programan");

    printf ("6. Destruir la listan");

    printf ("7. Quitarn");

    }

    printf ("nnElegir: ");

    scanf ("%d", &elección);

    getchar();

    if(lista->tamaño == 0 && elección == 2)

    elección = 7;

    return elección;

    }

    /* ——– FIN lista_circ_function ——— */

    lista_circ.c

    /**********************

    * lista_circ.c *

    **********************/

    #include

    #include

    #include

    #include "lista_circ.h"

    #include "lista_circ_function.h"

    int main (void)

    {

    char elección;

    char *nom;

    Lista *lista;

    Elemento *actual;

    if ((lista = (Lista *) malloc (sizeof (lista))) == NULL)

    return -1;

    if ((nombre = (char *) malloc (50)) == NULL)

    return -1;

    actual = NULL;

    elección = 'o';

    inicialización (lista);

    while (elección != 7){

    elección = menu (lista);

    switch (elección){

    case 1:

    printf ("Ingrese un elemento: ");

    scanf ("%s", nombre);

    getchar ();

    if(lista->tamaño == 0)

    ins_lista_circ_vacia (lista,nombre);

    else

    ins_lista_circ (lista,lista->fin,nombre);

    printf ("%d elements:deb=%s, fin=%sn",

    lista->tamaño,

    lista->inicio->dato,

    lista->fin->dato);

    mostrar (lista);

    break;

    case 2:

    if(lista->tamaño < 2)

    break;

    sup_lista_circ (lista);

    if (lista->tamaño != 0)

    printf ("%d elements:deb=%s, fin=%sn",

    lista->tamaño,

    lista->inicio->dato,

    lista->fin->dato);

    mostrar(lista);

    break;

    case 3:

    if(lista->tamaño != 1)

    break;

    sup_lista_circ_unica(lista);

    printf("La lista está vacian");

    break;

    case 4:

    mostrar(lista);

    break;

    case 5:

    mostrar_infinito(lista);

    break;

    case 6:

    destruir (lista);

    printf ("la lista ha sido destruida: %de elementosn",
    lista->tamaño);

    break;

    }

    }

    return 0;

    }

    Licencia

    Este documento es una compilación de varios artículos.

    Los artículos originales fueron escritos por lami20j,
    contribuidor de CommentCaMarche:

    http://www.commentcamarche.net/faq/7444-liste-simplement-chainee

    http://www.commentcamarche.net/faq/7636-liste-doublement-chainee#2-insertion-au-inicio-de-la-liste

    http://www.commentcamarche.net/faq/8283-les-piles-en-langage-c#iii-la-construction-du-prototype-d-un-element-de-la-pile

    http://www.commentcamarche.net/faq/8282-les-filas-en-langage-c

    http://www.commentcamarche.net/faq/8225-listes-circulaires-ring-buffer

    Los artículos revisados y traducidos en los cuales
    está basado este documento fueron escritos por Carlos-vialfa, contribuidor
    de Kioskea.net:

    http://es.kioskea.net/faq/2842-la-lista-enlazada-simple

    http://es.kioskea.net/faq/2872-listas-doblemente-enlazadas

    http://es.kioskea.net/faq/2885-las-pilas-en-lenguaje-c

    http://es.kioskea.net/faq/2902-las-filas-en-lenguaje-c

    http://es.kioskea.net/faq/2972-las-listas-circulares-ring-buffer

    Todos los artículos originales y el presente documento
    están puestos a diposición bajo la licencia Creative Commons.
    Puede copiar, modificar bajo las condiciones puestas por la licencia, siempre
    que esta nota sea visible.

     

     

     

    Autor:

    Nn

     

    Partes: 1, 2
     Página anterior Volver al principio del trabajoPágina siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter