Las listas circulares
Haz una pregunta
- Requisitos
- Introducción
- Definición
- Cómo construir el modelo de un elemento de la lista
- Operaciones sobre las listas circulares
- Ejemplo completo
Requisitos
Los requisitos son los siguientes: los tipos de datos, las estructuras, el uso de typedef, los punteros, la función usuario, las listas enlazadas simples y las listas doblemente enlazadas.Introducción
El objetivo de este artículo es que el lector pueda entender lo que son las listas circulares.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: esta no tiene fin.Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el primer 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.
Cómo construir el modelo de un elemento de la lista
Para definir un elemento de la lista, el tipo struct será utilizado. El elemento de la lista va a tener un campo dato y un puntero siguiente. Este debe ser del mismo tipo que el elemento, en caso 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 lista es mejor guardar ciertos elementos: el primer elemento, el último elemento y 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 puntero inicio albergará la dirección del primer elemento de la lista.
El puntero fin contendrá la dirección del último 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 apuntarán hacia el primer 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.
Operaciones sobre las listas circulares
Inicialización
Modelo de la función:void inicialización (Lista *lista);
Esta operación debe ser realizada primero antes de cualquier otra operación sobre la lista. Comienza colocando el puntero inicio y 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;
}
Inserción de un elemento en la lista
Enseguida, el algoritmo de inserción y el registro de los elementos: afirmación del elemento que se insertará, asignación de la memoria destinada al nuevo elemento, llenar el contenido del campo de los datos, actualizar los punteros hacia el primer y último elemento si es necesario.Caso particular: en una lista con un solo elemento, el primer elemento es al mismo tiempo el último. Luego, se tiene que actualizar el tamaño de la lista.
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 falla, si no devuelve 0.
Etapas: asignación de memoria para el nuevo elemento, rellenar el campo de datos del elemento nuevo, el puntero siguiente del nuevo elemento apuntará hacia si mismo (es la etapa que vuelve a la lista circular), los punteros inicio y fin apuntarán hacia el nuevo elemento, el tamaño es actualizado.
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;
}
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 equivocación, si no devuelve 0.
La inserción se efectuará al final de la lista.
Etapas: asignación de memoria para el nuevo elemento, rellenar el campo de datos del reciente 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.
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;
}
Eliminación de un elemento en la lista
En seguida, el algoritmo de eliminación de un elemento de la lista: uso de un puntero temporal para guardar la dirección de los elementos que se van a eliminar, el elemento a eliminar se encontrará después del elemento actual.Apunta el puntero siguiente del elemento actual hacia la dirección del puntero siguiente del elemento que se eliminará, libera la memoria ocupada por el elemento eliminado yactualiza el tamaño de la lista.
Para eliminar un elemento de la lista hay varias situaciones: eliminación dentro de la lista y eliminación del último elemento de la lista.
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 un error, si no devuelve 0.
Etapas: el puntero sup_elemento contendrá la dirección del elemento 1, el puntero inicio apuntará hacia el segundo elemento, el puntero siguiente del último elemento apuntará hacia el primer elemento (que era el segundo antes de la eliminación), el tamaño de la lista disminuirá 1 elemento.
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;
}
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 algún 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 apuntará hacia NULL, el puntero fin apuntará hacia NULL y el tamaño de la lista disminuirá un elemento.
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;
}
Mostrar la lista
Para mostrar la lista completa, es necesario posicionarse al inicio de la lista (el puntero inicio lo permitirá). Después, utilizando el puntero siguiente de cada elemento, la lista es recorrida del primer al último 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 último 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 primer al último elemento) y mostrar la lista sin una condición para detenerse.
Mostrar la lista (del primer 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;i<lista->tamaño;++i){
printf ("%p - %s\n", actual, actual->dato);
actual = actual->siguiente;
}
}
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 - %s\n", actual, actual->dato);
actual = actual->siguiente;
}
}
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 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);
}
}
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<gras>; 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<gras>; 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;i<lista->tamaño;++i){ printf ("%p - %s\n", actual, actual->dato); actual = actual->siguiente; }}/* recorrer la lista indefinidamente*/void mostrar_infinito (Lista * lista){ Elemento *actual; actual = lista->inicio; while (1){ printf ("%p - %s\n", actual, actual->dato); actual = actual->siguiente; }}/* destruir esta 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); }}int menu (Lista *lista){ int elección; printf("********** MENU **********\n"); if (lista->tamaño == 0){ printf ("1. Adicion del 1er elemento\n"); printf ("2. Quitar\n"); }else { printf ("1. Adición de un elemento\n"); 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 elemento\n"); printf ("4. Mostrar lista circular\n"); printf ("5. Mostrar lista circular [Ctrl-C] para quitar el programa\n"); printf ("6. Destruir la lista\n"); printf ("7. Quitar\n"); } printf ("\n\nElegir: "); 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 <stdio.h>#include <stdlib.h>#include <string.h>#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=%s\n", 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=%s\n", 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á vacia\n"); break; case 4: mostrar(lista); break; case 5: mostrar_infinito(lista); break; case 6: destruir (lista); printf ("la lista ha sido destruida: %de elementos\n", lista->tamaño); break; } } return 0;}
Jean-François Pillou - Fundador de CCM
Mejor conocido como Jeff, Jean-François Pillou es el fundador de CommentCaMarche.net. También es CEO de CCM Benchmark y director digital en el Grupo Figaro.
Consulta también
- Listas enlazadas circulares
- Listas circulares
- Lista circular simple
- Listas enlazadas simples » Fichas prácticas - Lenguaje C
- Listas doblemente enlazadas » Fichas prácticas - Lenguaje C
- Informconf lista de morosos paraguay » Foros - Internet
- Listas en html » Artìculos
- Lista de comandos ms dos » Fichas prácticas - Windows