Listas Circulares

Publicado por rogikato / en 4:29 / /

Una lista circular puede ser simple o doblemente encadenada. Lo que caracteriza a las listas circulares es el hecho que el sucesor del último elemento es el primer elemento de la lista. En el caso de una lista doblemente encadenada, el predecesor del primer elemento es el último elemento de la lista.
 
La principal ventaja de las listas circulares es que no necesitamos considerar casos especiales de inserción y eliminación de elemento (primero y último).

 Implementación (Dinámica)

Listas Circulares simplemente enlazada

Código
#include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista { int elem; NO *prox; /* guarda la posicion del proximo elemento en la lista */ }; struct lista { NO *head ; /* guarda la dirección del primer elemento de la lista */ }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A) { NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL) { aux->prox = aux; L->head = aux; } else { /* Inserta en la pos. anterior de head */ aux->prox = L->head->prox; L->head->prox = aux; } } else exit(0); return; } int Eliminar_Elemento(LE *L,int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) { if(L->head == NULL){ return -1; } else { act=L->head; ant=NULL; do {ant=act; act=act->prox; }while(act->elem!=A&&act!=L->head); if(act->elem==A) { ant->prox=act->prox; act->prox=NULL; if(act==L->head) {L->head=ant; if(act==ant) L->head=NULL; } return 1; } else return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; do { if(L->head!=NULL) {tam++; cout<<atu->elem<<" "; atu = atu->prox; } }while (atu != L->head); if(tam)cout<<" de tama\xa4o "<<tam; else cout<<"Lista vacia"; } } /* Ejercicios: Implementar las funciones que faltan */ main() { int aux_l; LE *l; int x=0; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el número entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }

Listas Circulares doblemente enlazada

Código
#include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista { int elem; NO *prox,*ante; /* guarda la posicion del proximo elemento en la lista */ }; struct lista { NO *head ; /* guarda la dirección del primer elemento de la lista */ }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A) { NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL) { aux->prox = aux; aux->ante=aux; L->head = aux; } else { /* Inserta en la pos. anterior de head */ aux->prox = L->head->prox; L->head->prox = aux; aux->ante=L->head; L->head->prox->ante = aux; } } else exit(0); return; } int Eliminar_Elemento(LE *L,int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) { if(L->head == NULL){ return -1; } else { act=L->head; ant=NULL; do {ant=act; act=act->prox; }while(act->elem!=A&&act!=L->head); if(act->elem==A) { ant->prox=act->prox; act->prox->ante=ant; act->prox=NULL; act->ante=NULL; if(act==L->head) {L->head=ant; if(ant==act) L->head=NULL; } return 1; } else return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; do { if(L->head!=NULL) {tam++; cout<<atu->elem<<" "; atu = atu->prox; } }while (atu != L->head); if(tam)cout<<" de tama\xa4o "<<tam; else cout<<"Lista vacia"; } } /* Ejercicios: Implementar las funciones que faltan */ main() { int aux_l; LE *l; int x=0; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el número entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }