Estructuras con Punteros

7. Listas Circulares.

Las listas circulares nos son otra cosa que un caso particular de una  la lista doble enlazada o doblemente enlazada.

En este tipo de lista los punteros en los extremos que antes ( Lista enlazada doble) que antes se inicializaban en NULL ahora se inicializan a las instancias de manera de logra que NO tenga fin.

• el puntero que apuntan a la siguiente instancia en la última instancia DEBE apuntar a la primera.
• el puntero que apunta a la instancia anterior en la primer instancia DEBE apuntar a la última instancia.

Veamos un ejemplo gŕaficamente.

Observación:

• La lista NO tiene FIN.
• Si perdemos el inicio no podemos Recorrerla.
• Se puede recorrer en AMBOS sentidos.

Consigna: Crear una lista Circular doblemente enlazada a partir de una Lista Enlazada Simple.

Código:

#include <iostream>
using namespace std;

struct datos{     //Estructura global
   int Tel;
   int legajo;
   struct datos *p_siguiente;   //puntero a la proxima instancia
   struct datos *p_anterior;   // puntero a la instancia anterior.
};

void cargar (datos *);
void agregar (datos *);

int main (){
   datos *puntero_inicio = new datos;   //creo un puntero y solicito la 1er instancia (en main())
   puntero_inicio->p_anterior=puntero_inicio;
   puntero_inicio->p_siguiente=puntero_inicio;
cargar (puntero_inicio); //cargo la 1er instancia
//Cargo segunda instancia
agregar (puntero_inicio); //siempre paso el puntero a la 1er instancia
//Cargo tercer instancia
agregar (puntero_inicio); //siempre paso el puntero a la 1er instancia
//Muestro la lista enlazada doble de tres instancias
datos *p = puntero_inicio;
bool primera = true;
do {
if (primera) {
primera = false;
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "siguiente: " << p->p_siguiente << "-" << "anterior: " << p->p_anterior << endl;
}
else {
p = p->p_siguiente;
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "siguiente: " << p->p_siguiente << "-" << "anterior: " << p->p_anterior << endl;
}
} while (p->p_siguiente != 0);
//Ahora hago la lista Circular.
p = puntero_inicio;
//Busco la última instancia donde el puntero era NULL
while (p->p_siguiente != 0) { //me posiciono en la última instancia utilizando los enlaces
p = p->p_siguiente;
}
// Cambio el puntero a anterior de la primer instancia para que apunte a la ultima instancia
puntero_inicio->p_anterior = p;
// Cambio el puntero a proximo de la ultima instancia a puntero_inicio
p->p_siguiente = puntero_inicio;
// para demostrar que es cirular uso un for, por que como es circular no terminaría..
cout << "Muestar de Lista Circular: " << endl;
p = puntero_inicio;
for (int i = 0; i < 10; i++) {
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "p_siguiente: " << p->p_siguiente<< "-" << "p_anterior: " << p->p_anterior << endl;
p = p->p_siguiente;
}
delete[]puntero_inicio;
return 0;
}

void cargar (datos * puntero){ //ver que puntero es una COPIA de punterodato
cout << "ingrese telefono" << endl;
cin >> puntero->Tel; //cargo los datos
cout << "ingrese legajo" << endl;
cin >> puntero->legajo;
puntero->p_siguiente = NULL;
}

void agregar (datos * puntero){ //ver que puntero es una COPIA de punterodato
//al pasar por valor la función crea una copia del puntero. No modifico el de main
while (puntero->p_siguiente != 0) { //me posiciono en la última instancia utilizando los enlaces
puntero = puntero->p_siguiente;
}
puntero->p_siguiente = new datos; //solicito una nueva instancia y asigno la dirección
//en el puntero al prox de la última
puntero->p_siguiente->p_anterior = puntero;
cargar (puntero->p_siguiente);
}

Observación : 

El código mostrado es el mismo que para Lista Doble Enlazada, solo se agregaron las líneas 26 a 35 que reemplan los punteros a NULL de la primer y utlima instancia para hacer una lista circular.

La salida del código anterior es: