Listas Circulares

LISTAS CIRCULARES

DEFINICIÓN:

Recorrido simplemente despliega los datos almacenados en el arreglo Info, con ayuda de un segundo arreglo llamado Indice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

DETALLE:

Apuntador toma el valor de Indice[Inicio], después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de Inicio, si cumple lo que hace es que despliega la Info[Apuntador], después Apuntador toma el valor de Indice[Apuntador] (El cual nos indica el siguiente nodo que sigue en la lista) y hace esto hasta que Apuntador sea igual a Inicio (Cuando llega a este punto a llegado al fin de la Lista).

Algoritmo:

Recorrido(Inicio, Info, Indice)

Apuntador → Indice[Inicio]

Repetir mientras Apuntador ≠ Inicio

Imprimir Info[Apuntador]

Apuntador → Indice[Apuntador]

Fin del ciclo

Salir

Diagrama:

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.

El nodo típico es el mismo que para construir listas abiertas:

struct nodo {

int dato;

struct nodo *siguiente;

};

DECLARACIONES DE TIPOS PARA MANEJAR LISTAS CIRCULARES EN C:

Los tipos que definiremos normalmente para manejar listas cerradas son los mismos que para para manejar listas abiertas:

typedef struct _nodo {

int dato;

struct _nodo *siguiente;

} tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Lista es el tipo para declarar listas, tanto abiertas como circulares. En el caso de las circulares, apuntará a un nodo cualquiera de la lista.

A pesar de que las listas circulares simplifiquen las operaciones sobre ellas, también introducen algunas complicaciones. Por ejemplo, en un proceso de búsqueda, no es tan sencillo dar por terminada la búsqueda cuando el elemento buscado no existe.

Por ese motivo se suele resaltar un nodo en particular, que no tiene por qué ser siempre el mismo. Cualquier nodo puede cumplir ese propósito, y puede variar durante la ejecución del programa.

Otra alternativa que se usa a menudo, y que simplifica en cierto modo el uso de listas circulares es crear un nodo especial de hará la función de nodo cabecera. De este modo, la lista nunca estará vacía, y se eliminan casi todos los casos especiales.

OPERACIONES BÁSICAS CON LISTAS CIRCULARES:

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

• Añadir o insertar elementos.

• Buscar o localizar elementos.

• Borrar elementos.

• Moverse a través de la lista, siguiente.

Cada una de éstas operaciones podrá tener varios casos especiales, por ejemplo, tendremos que tener en cuenta cuando se inserte un nodo en una lista vacía, o cuando se elimina el único nodo de una lista.

AÑADIR ELEMENTO EN UNA LISTA CIRCULAR VACÍA:

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL:

El proceso es muy simple, bastará con que:

1. lista apunta a nodo.

2. lista->siguiente apunte a nodo.

AÑADIR ELEMENTO EN UNA LISTA CIRCULAR NO VACÍA:

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso, el puntero no será nulo:

El proceso sigue siendo muy sencillo:

1. Hacemos que nodo->siguiente apunte a lista->siguiente.

2. Después que lista->siguiente apunte a nodo.

AÑADIR ELEMENTO EN UNA LISTA CIRCULAR, CASO GENERAL:

Para generalizar los dos casos anteriores, sólo necesitamos añadir una

...