listas circulares en C++

Listas lineales (circulares ,doblemente enlazadas recopilación Raúl H Ruiz C)

Listas circulares:
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en las 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ñadeun nodo especial de cabecera, de ese modo se evita la
única excepción posible, la de que la lista esté vacía.
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 declararnodos, 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 tansencillo 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) Añadir o insertar elementos.
b) Buscar o localizar elementos.
c) Borrar elementos.
d)Moverse a través de la lista, siguiente.
Cada una de estas 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) Añadir un elemento
El único caso especial a la hora de insertar nodos en listas circulares es cuando la lista esté
vacía.
a1) Añadir elemento en unalista circular vacía:
[Escribir texto]

Página 1

Listas lineales (circulares ,doblemente enlazadas recopilación Raúl H Ruiz C)

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:

[Escribir texto]

Página 2

Listas lineales (circulares ,doblemente enlazadas recopilación Raúl H Ruiz C)El proceso es muy simple, bastará con que:
lista apunta a nodo.
lista->siguiente apunte a nodo.
a2) 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:
Hacemos que nodo->siguiente apunte a lista->siguiente.
Después quelista->siguiente apunte a nodo.
a3) Añadir elemento en una lista circular, caso general:
Para generalizar los dos casos anteriores, sólo necesitamos añadir una operación:
Si lista está vacía hacemos que lista apunte a nodo.
Si lista no está vacía, hacemos que nodo->siguiente apunte a lista->siguiente.
Después que lista->siguiente apunte a nodo.
b) Buscar un elemento en una lista circular:
A lahora de buscar elementos en una lista circular sólo hay que tener una precaución, es necesario
almacenar el puntero del nodo en que se empezó la búsqueda, para poder detectar el caso en que
no exista el valor que se busca. Por lo demás, la búsqueda es igual que en el caso de las listas
abiertas, salvo que podemos empezar en cualquier punto de la lista.
c) Borrar un elemento de una lista...