NOTA: SI DESEAS DESCARGAR EL DIAGRAMA DE FLUJO DE LISTAS ENLAZADAS SIMPLES DESPLAZATE AL FINAL DE LA PÁGINA Y TIENES QUE PINCHAR EN "DESCARGAR DIAGRAMA DE LISTAS Y LUEGO SALTAR PUBLICIDAD"
Què es una lista?Una lista enlazada es un conjunto de elementosllamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo,donde el orden de los mismos seestablece mediante punteros.
La idea básica es que cada componente de la listaincluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.
El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
Listas Enlazadas frente a Arrays
Las listas enlazadas tienen las siguiente ventajas sobre los arrays:
No requieren memoria extra para soportar la expansión. Por el contrario, los arrays requieren memoria extra si se necesita expandirlo (una vez que todos los elementos tienen datos no se pueden añadir datos nuevos a un array).
Ofrecen una inserción/borrado de elementos más rápida que sus operaciones equivalentes en los arrays. Sólo se tienen que actualizar los enlaces después de identificar la posición de inserción/borrado. Desde la perspectiva de los arrays, la inserción de datos requiere el movimiento de todos los otros datos del array para crear un elemento vacío. De forma similar, el borrado de un dato existente requiere el movimiento de todos los otros datos para eliminar el elementovacío.
En contraste, los arrays ofrecen las siguiente ventajas sobre las listas enlazadas:
Los elementos de los arrays ocupan menos memoria que los nodos porque no requieren campos de enlace.
Los arrays ofrecen un aceso más rápido a los datos, medante índices basados en enteros.
Las listas enlazadas son más apropiadas cuando se trabaja con datos dinámicos. En otras palabras, inserciones y borrados con frecuencia. Por el contrario, los arrays son más apropiados cuando los datos son estáticos (las inserciones y borrados son raras). De todas formas, no olvide que si se queda sin espacio cuando añade ítems a un array, debe crear un array más grande, copiar los datos del array original el nuevo array mayor y elimiar el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace repetidamente.
Mezclando una lista de enlace simple con un array uni-dimensional para acceder a los nodos mediante los índices del array no se consigue nada. Gastará más memoria, porque necesitará los elementos del array más los nodos, y tiempo, porque necesitará mover los ítems del array siempre que inserte o borre un nodo. Sin embargo, si es posible integrar el array con una lista enlazada para crear una estructura de datos úti.
Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas y Listas Enlazadas Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C, C++ o Java disponen de referencias para crear listas enlazadas.
Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:
Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
Insertar un nodo al inicio.
Insertar un nodo antes o después de cierto nodo.
Insertar un nodo al final.
Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
Eliminar el primer nodo.
Eliminar el último nodo.
Eliminar un nodo con cierta información.
Eliminar el nodo anterior o posterior al nodo cierta con información.
Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.
Figura 1. Esquema de un nodo y una lista enlazada.
Lista.png
LISTA ENLAZADA SIMPLE
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.Singly-linked-list.svg
He aquì tenemos un ejemplo de una lista enlazada simple
//DECLARACIÒN DE PROTOTIPOS
#include<alloc.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream.h>
//Declaramosla estructura
typedef struct nodo
{
int dato;
struct nodo * siguiente;
}tipoNodo;
//reservamos el espacio de memoria
tipoNodo *nuevo_elemento();
//Operaciones que vamos a arealizar
void crear();
void insertar();
void insertar_inicio();
void insertar_ordenado();
void insertar_final();
void presentar();
void modificar();
void buscar();
void ordenar();
void ordenar_ascendente();
void ordenar_descendente();
void eliminar();
void eliminar_cabeza();
//FUNCION PARA EL CUADRO
void cuadro(int x1,int y1, int x2, int y2, char simb);
//NUESTRA CABEZA
tipoNodo *cab;
tipoNodo *nuevo_elemento()
{
tipoNodo *nodo1;
nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));
if(!nodo1)
cout<<”No se ha reservado memoria para el nuevo “;
return nodo1;
}
void main()
{
clrscr();
crear();
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,35,56,’²’);
gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: INSERTAR\n”;
gotoxy(12,12);cout<<” [2]: MODIFICAR\n”;
gotoxy(12,15);cout<<” [3]: BUSCAR\n”;
gotoxy(12,17);cout<<” [4]: ORDENAR\n”;
gotoxy(12,19);cout<<” [5]: ELIMINAR\n”;
gotoxy(12,21);cout<<” [6]: PRESENTAR\n”;
gotoxy(12,24);cout<<” [7]: SALIR DEL MENU\n”;
gotoxy(12,27);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,27);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertar();getch();break;
case’2′:
clrscr();
modificar();getch();break;
case’3′:
clrscr();
buscar();getch();break;
case’4′:
clrscr();
ordenar();getch();break;
case’5′:
clrscr();
eliminar();getch();break;
case’6′:
clrscr();
presentar();getch();break;
}
}while(opc!=’7′);
getch();
}
//CREANDO LA CABEZA
void crear()
{
clrscr();
cab=nuevo_elemento();
gotoxy(20,20);
cout<<”Ingrese valor de cabeza :\t”;
cin>>cab->dato;
cab->siguiente=NULL;
getch();
}
//MENU DE INSERTAR
void insertar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,35,56,’²’);
gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: INSERTAR AL INICIO\n”;
gotoxy(12,12);cout<<” [2]: insertar AL FINAL\n”;
gotoxy(12,15);cout<<” [3]: INSERTAR ORDENADO\n”;
gotoxy(12,18);cout<<” [4]: REGRESAR\n”;
gotoxy(12,21);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,21);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertar_inicio();getch();break;
case’2′:
clrscr();
insertar_final();getch();break;
case’3′:
clrscr();
insertar_ordenado();getch();break;
}
}while(opc!=’4′);
getch();
}
//INSERATAR AL INICIO
void insertar_inicio()
{
clrscr();
nodo *pAuxElem;
nodo *recorre;
pAuxElem=(tipoNodo*) malloc(sizeof(tipoNodo));
while(recorre->siguiente!=NULL)
{
recorre=recorre->siguiente;
}
int n;
gotoxy(20,20);
cout<<”INGRESE VALOR :\t”;
cin>>n;
pAuxElem->dato=n;
pAuxElem->siguiente=cab;
cab=pAuxElem;
}
//INSERTAR AL FINAL
void insertar_final()
{
clrscr();
nodo *elem;
elem=nuevo_elemento();
clrscr();
gotoxy(20,20);
cout<<”INGRESE VALOR :\t”;
cin>>elem->dato;
nodo *recorrer;
recorrer=cab;
while(recorrer->siguiente!=NULL)
recorrer=recorrer->siguiente;
recorrer->siguiente=elem;
elem->siguiente=NULL;
getch();
}
//INSERATAR ORDENADO
void insertar_ordenado()
{
clrscr();
nodo *pAuxElem;
nodo *post;
nodo *recorre;
pAuxElem=(tipoNodo*) malloc(sizeof(tipoNodo));
post=(tipoNodo*) malloc(sizeof(tipoNodo));
int n;
gotoxy(20,20);
cout<<”INGRESE VALOR :\t”;
cin>>n;
if(n<cab->dato)
{
post=cab->siguiente;
while((pAuxElem->dato>post->dato)&&(post->siguiente!=NULL))
{
post=post->siguiente;
}
if(post->siguiente!=NULL)
{
pAuxElem->siguiente=cab;
cab=pAuxElem;
}
else
{
pAuxElem->siguiente=NULL;
post->siguiente=pAuxElem;
}
}
else
{
while(recorre->siguiente!=NULL)
{
recorre=recorre->siguiente;
}
pAuxElem->dato=n;
pAuxElem->siguiente=cab;
cab=pAuxElem;
}
/*cout<<”Ingrese un numero”;
cin>>n;
if(n>cab->dato)
{
insertar_inicio(n);
}
else
{
nodo *aux;
nodo *ant;
aux=cab->siguiente;
while((aux!=NULL)(n>aux->dato))
{
ant=aux;
aux=aux->siguiente
}
nodo *nuevo;
nuevo=crear_nuevo();
nuevo->dato=n;
ant->siguiente=nuevo;
nuevo->siguiente=aux;
}*/
}
//PARA MODIFICAR
void modificar()
{
clrscr();
nodo *elem;
nodo *ele;
gotoxy(10,25);cout<<”ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;
gotoxy(10,26);cout<<”º º\n”;
gotoxy(10,27);cout<<”ºMODIFICAR NUMERO DE LISTA º\n”;
gotoxy(10,28);cout<<”º º\n”;
gotoxy(10,29);cout<<”ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;
gotoxy(20,20);
cout<<”INGRESE EL VALOR A MODIFICAR :\t”;
cin>>elem->dato;
nodo *recorrer;
recorrer=cab;
while(recorrer!=NULL)
{
if(recorrer->dato==elem->dato)
{
clrscr();
gotoxy(20,20);
cout<<”INGRESE VALOR :\t”;
cin>>ele->dato;
recorrer->dato=ele->dato;
}
recorrer=recorrer->siguiente;
}
getch();
}
//PARA BUSCAR
void buscar()
{
clrscr();
nodo *elem;
gotoxy(10,25);cout<<”ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;
gotoxy(10,26);cout<<”º º\n”;
gotoxy(10,27);cout<<”ºBUSCADOR DE NUMERO DE LISTAº\n”;
gotoxy(10,28);cout<<”º º\n”;
gotoxy(10,29);cout<<”ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;
gotoxy(20,20);
cout<<”INGRESE EL VALOR A BUSCAR :\t”;
cin>>elem->dato;
nodo *recorrer;
recorrer=cab;
while(recorrer!=NULL)
{
if(recorrer->dato==elem->dato)
{
clrscr();
gotoxy(20,20);
cout<<elem->dato<<”:\t”;
cout<<”ESTE ELEMENTO SI EXISTE”;
recorrer->dato=elem->dato;
}
recorrer=recorrer->siguiente;
}
getch();
}
//ORDENAR
void ordenar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,25,56,’²’);
gotoxy(13,3);cout<<”->[ ORDENAR LAS LISTAS ENLAZADAS ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: ORDENAR ASCENDENTE\n”;
gotoxy(12,12);cout<<” [2]: ORDENAR DESCENDENTE\n”;
gotoxy(12,15);cout<<” [3]: REGRESAR\n”;
gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,17);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
ordenar_ascendente();getch();break;
case’2′:
clrscr();
ordenar_descendente();getch();break;
}
}
while(opc!=’3′);
getch();
}
void ordenar_ascendente()
{
nodo* aux;
nodo* temp;
int vaux;
aux=(tipoNodo *)malloc(sizeof(tipoNodo));
temp=(tipoNodo *)malloc(sizeof(tipoNodo));
aux=cab;
while (aux!=NULL)
{
temp=aux;
while(temp->siguiente!=NULL)
{
temp=temp->siguiente;
if(aux->dato>temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->siguiente;
}
}
void ordenar_descendente()
{
nodo* aux;
nodo* temp;
int vaux;
aux=(tipoNodo *)malloc(sizeof(tipoNodo));
temp=(tipoNodo *)malloc(sizeof(tipoNodo));
aux=cab;
while (aux!=NULL)
{
temp=aux;
while(temp->siguiente!=NULL)
{
temp=temp->siguiente;
if(aux->dato<temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->siguiente;
}
}
//ELIMINAR
void eliminar()
{
presentar();
nodo *eliminar;
// nodo *recorrer;
nodo *asigna;
gotoxy(10,25);cout<<”ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;
gotoxy(10,26);cout<<”º º\n”;
gotoxy(10,27);cout<<”ºINSERTAR NUMERO A ELIMINARº\n”;
gotoxy(10,28);cout<<”º º\n”;
gotoxy(10,29);cout<<”ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;
gotoxy(10,31);cout<<”Ingrese el n—mero a eliminar\t”;
cin>>eliminar->dato;
// recorrer=cab;
if (eliminar->dato==cab->dato)
{
eliminar_cabeza();
}
else
{
nodo *anterior=cab;
nodo * aux=cab->siguiente;
while((aux!=NULL)&&(aux->dato!=eliminar->dato))
{
anterior=aux;
aux=aux->siguiente;
}
if(aux!=NULL)
{
anterior->siguiente=aux->siguiente;
aux->siguiente=NULL;
free(aux);
}
else
{
gotoxy(10,33);
cout<<”NO SE ENCUENTRA”;
}
}
}
//ELIMINAR CABEZA
void eliminar_cabeza()
{
nodo *aux;
aux=cab;
cab=cab->siguiente;
aux->siguiente=NULL;
free(aux);
}
//PRESENTAR LA LISTA
void presentar()
{
clrscr();
int f=10;
nodo *recorrer;
recorrer=cab;
gotoxy(20,f);
while(recorrer!=NULL)
{
gotoxy(20,f);
cout<<recorrer->dato;
cout<<”\n\n”;
recorrer=recorrer->siguiente;
f=f+2;
}
getch();
}
//ESTA FUNCION PERMITE PRESENTAR LOS BORDES DE UN CUADRO
void cuadro(int x1,int y1, int x2, int y2, char simb)
{
for (int i1=y1;i1<=y2;i1++)
{
gotoxy(i1,x1);cout<<simb;
gotoxy(i1,x2);cout<<simb;
}
for (int i2=x1;i2<=x2;i2++)
{
gotoxy(y1,i2);cout<<simb;
gotoxy(y2,i2);cout<<simb;
}
}
LISTAS ENLAZADAS DOBLES
Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL o a la lista vacía si es el primer nodo; y otro que apunta al siguiente nodo siguiente, o apunta al valor NULL o a la lista vacía si es el último nodo.Doubly-linked-list.svg
He aquì tenemos un ejemplo de una lista enlazada simple
//LISTA DOBLE ENLAZADA
//DECLARACIÒN DE PROTOTIPOS
#include<alloc.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream.h>
//Estructuras Doblemente enlazadas
typedef struct nododoble
{
int dato;
struct nododoble *sig;
struct nododoble *ant;
}tipoNodo;
//PROTOTIPOS
tipoNodo *nuevo_elemento();
void creardoble();
void presentar();
void insertar();
void insertarfinaldoble();
void insertarordenadodoble();
void insertariniciodoble();
void modificar();
void buscar();
void ordenar();
void ordenardoblesasc();
void ordenardoblesdesc();
void eliminar();
void eliminar_cabeza();
void cuadro(int x1,int y1,int x2,int y2,char c);
tipoNodo *cab;
tipoNodo *cola;
tipoNodo *nuevo_elemento()
{
tipoNodo *nodo1;
nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));
if(!nodo1)
cout<<”No se ha reservado memoria para el nuevo “;
return nodo1;
}
//MENU PRINCIPAL
void main()
{
clrscr();
creardoble();
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,35,56,’ ’);
gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS DOBLES ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: INSERTAR \n”;
gotoxy(12,12);cout<<” [2]: MODIFICAR\n”;
gotoxy(12,15);cout<<” [3]: BUSCAR\n”;
gotoxy(12,17);cout<<” [4]: ORDENAR\n”;
gotoxy(12,19);cout<<” [5]: ELIMINAR\n”;
gotoxy(12,21);cout<<” [6]: PRESENTAR\n”;
gotoxy(12,24);cout<<” [7]: SALIR DEL MENU\n”;
gotoxy(12,27);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,27);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertar();;getch();break;
case’2′:
clrscr();
modificar();getch();break;
case’3′:
clrscr();
buscar();getch();break;
case’4′:
clrscr();
ordenar();getch();break;
case’5′:
clrscr();
eliminar();getch();break;
case’6′:
clrscr();
presentar();getch();break;
}
}while(opc!=’7′);
getch();
}
//CREAR LA CABEZA
void creardoble()
{
clrscr();
int dat;
gotoxy(20,20);
cout<<”Ingrese Elemento: “;
cin>>dat;
cab=nuevo_elemento();
cola=nuevo_elemento();
cab->dato=dat;
cab->sig=NULL;
cab->ant=NULL;
cola=cab;
getch();
}
void insertar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,25,56,’ ’);
gotoxy(13,3);cout<<”->[ INSERTAR ELEMENMTOS A LA LISTA ENLAZADA ]<-\n”;
gotoxy(12,6); cout<<” [1]: INSERTAR ORDENADO\n”;
gotoxy(12,9);cout<<” [2]: INSERTAR CABEZA\n”;
gotoxy(12,12);cout<<” [3]: INSERTAR AL FINAL\n”;
gotoxy(12,15);cout<<” [4]: REGRESAR\n”;
gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,17);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertarordenadodoble();getch();break;
case’2′:
clrscr();
insertariniciodoble();getch();break;
case’3′:
clrscr();
insertarfinaldoble();getch();break;
}
}
while(opc!=’4′);
getch();
}
void insertarfinaldoble()
{
clrscr();
nododoble *elem;
elem=nuevo_elemento();
clrscr();
gotoxy(20,20);
cout<<”\t\t”<<”INGRESE VALOR :\t”;
cin>>elem->dato;
cola->sig=elem;
elem->sig=NULL;
elem->ant=cola;
cola=elem;
getch();
}
void insertarordenadodoble()
{
int dat;
nododoble *aux;
nododoble *ant;
nododoble *post;
aux=nuevo_elemento();
ant=nuevo_elemento();
post=nuevo_elemento();
gotoxy(18,22);
cout<<”Ingrese un elemento: “;
cin>>dat;
aux->dato=dat;
if(aux->dato>cab->dato)
{
ant=cab;
post=cab->sig;
while((aux->dato>post->dato) && (post->sig!=NULL))
{
ant=post;
post=post->sig;
}
if (post->sig==NULL)
{
if (aux->dato<post->dato){
aux->sig=post;
post->ant=aux;
ant->sig=aux;
aux->ant=ant;
}else{
aux->sig=NULL;
post->sig=aux;
aux->ant=post;
}
}
else
{
aux->sig=post;
post->ant=aux;
ant->sig=aux;
aux->ant=ant;
}
}
else{
aux->dato=dat;
aux->sig=cab;
cab->ant=aux;
aux->ant=NULL;
cab=aux;
}
}
void insertariniciodoble()
{
nododoble *Aux;
int dat;
Aux=nuevo_elemento();
gotoxy(18,22);
cout<<”Ingrese un numero:”;
cin>>dat;
Aux->dato=dat;
Aux->ant=NULL;
Aux->sig=cab;
cab->ant=Aux;
cab=Aux;
}
void modificar()
{
clrscr();
nododoble *modificar;
nododoble *ele;
modificar=nuevo_elemento();
int db,encontrado=0;
modificar=cab;
gotoxy(10,20);
cout<<”\t”<<”INGRESE EL VALOR A MODIFICAR :\t”;
cin>> db;
while(modificar!=NULL)
{
if(db==modificar->dato)
{
gotoxy(10,22);cout<<”Elemento existente en la lista”;
encontrado=1;
gotoxy(10,25);
cout<<”\t\t”<<”INGRESE VALOR :\t”;
cin>>ele->dato;
modificar->dato=ele->dato;
}
modificar=modificar->sig;
}
if(encontrado==0)
{
gotoxy(10,22);cout<<”Elemento no existente en la lista”;
}
getch();
}
void buscar()
{
clrscr();
nododoble *buscar;
buscar=nuevo_elemento();
int db,encontrado=0;
buscar=cab;
gotoxy(18,15);
cout<<”Ingrese el numero a buscar: “;
cin>> db;
while(buscar!=NULL)
{
if(db==buscar->dato)
{
gotoxy(18,18);cout<<”Elemento existente en la lista”;
encontrado=1;
}
buscar=buscar->sig;
}
if(encontrado==0)
{
gotoxy(18,18);cout<<”Elemento no existente en la lista”;
}
getch();
}
void ordenar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,25,56,’ ’);
gotoxy(13,3);cout<<”->[ ORDENAR LAS LISTAS ENLAZADAS ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: ORDENAR ASCENDENTE\n”;
gotoxy(12,12);cout<<” [2]: ORDENAR DESCENDENTE\n”;
gotoxy(12,15);cout<<” [3]: REGRESAR\n”;
gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,17);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
ordenardoblesasc();break;
case’2′:
clrscr();
ordenardoblesdesc();break;
}
}
while(opc!=’3′);
getch();
}
void ordenardoblesasc()
{
nododoble *aux;
nododoble *temp;
int vaux;
aux=nuevo_elemento();
temp=nuevo_elemento();
aux=cab;
while (aux!=NULL)
{
temp=aux;
while(temp->sig!=NULL)
{
temp=temp->sig;
if(aux->dato>temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->sig;
}
}
void ordenardoblesdesc()
{
nododoble *aux;
nododoble *temp;
int vaux;
aux=nuevo_elemento();
temp=nuevo_elemento();
aux=cab;
while (aux!=NULL)
{
temp=aux;
while(temp->sig!=NULL)
{
temp=temp->sig;
if(aux->dato<temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->sig;
}
}
void presentar()
{
clrscr();
int c=8;
nododoble *recorre;
recorre=nuevo_elemento();
recorre=cab;
gotoxy(18,7);
cout<<” ELEMENTOS INSERTADOS: \n”;
while(recorre!=NULL)
{
c=c+1;
gotoxy(30,c);cout<<recorre->dato<<”\n”;
recorre=recorre->sig;
}
getch();
}
void eliminar()
{
presentar();
nododoble *eliminar;
nododoble *asigna;
gotoxy(10,25);cout<<”ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;
gotoxy(10,26);cout<<”º º\n”;
gotoxy(10,27);cout<<”ºINSERTAR NUMERO A ELIMINARº\n”;
gotoxy(10,28);cout<<”º º\n”;
gotoxy(10,29);cout<<”ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;
gotoxy(10,31);cout<<”Ingrese el n—mero a eliminar\t”;
cin>>eliminar->dato;
if (eliminar->dato==cab->dato)
{
eliminar_cabeza();
}
else
{
nododoble *anterior=cab;
nododoble * aux=cab->sig;
while((aux!=NULL)&&(aux->dato!=eliminar->dato))
{
anterior=aux;
aux=aux->sig;
}
if(aux!=NULL)
{
asigna=aux->sig;
anterior->sig=asigna;
aux->ant=anterior;
aux->ant=NULL;
aux->sig=NULL;
free(aux);
}
else
{
gotoxy(10,33);
cout<<”NO SE ENCUENTRA”;
}
}
}
void eliminar_cabeza()
{
nododoble *aux;
aux=cab;
cab=cab->sig;
aux->sig=NULL;
aux->ant=NULL;
free(aux);
}
void cuadro(int x1,int y1, int x2, int y2, char simb)
{
for (int i1=y1;i1<=y2;i1++)
{
gotoxy(i1,x1);cout<<simb;
gotoxy(i1,x2);cout<<simb;
}
for (int i2=x1;i2<=x2;i2++)
{
gotoxy(y1,i2);cout<<simb;
gotoxy(y2,i2);cout<<simb;
}
}
Listas enlazadas circulares
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer un lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.
Circularly-linked-list.svg
Listas enlazadas circulares simples
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.
Lista Enlazada Doblemente Circular
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como una lista doblemente enlazada con falsos nodos.
Aquì un ejemplo de lista circular doblemente enlazadas en C++
//LISTA DOBLE CIRCULARES
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
//Estructuras Doblemente enlazadas
typedef struct nododoble
{
int dato;
struct nodoc *sig;
struct nodoc *ant;
}tipoNodo;
//PROTOTIPOS
tipoNodo *nuevo_elemento();
void crearc();
void presentar();
void presentar_recorrido();
void insertar();
void insertarfinalc();
void insertarordenadoc();
void insertarinicioc();
void modificar();
void buscar();
void ordenar();
void ordenarc();
void ordenarcdesc();
void eliminar();
void eliminar_cabeza();
void cuadro(int x1,int y1,int x2,int y2,char c);
tipoNodo *cab;
tipoNodo *cola;
tipoNodo *nuevo_elemento()
{
tipoNodo *nodo1;
nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));
if(!nodo1)
cout<<”No se ha reservado memoria para el nuevo “;
return nodo1;
}
//MENU PRINCIPAL
void main()
{
clrscr();
creardoble();
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,35,56,’ ’);
gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS CIRCULARES ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: INSERTAR \n”;
gotoxy(12,12);cout<<” [2]: MODIFICAR\n”;
gotoxy(12,15);cout<<” [3]: BUSCAR\n”;
gotoxy(12,18);cout<<” [4]: ORDENAR\n”;
gotoxy(12,21);cout<<” [5]: ELIMINAR\n”;
gotoxy(12,24);cout<<” [6]: PRESENTAR\n”;
gotoxy(12,27);cout<<” [7]: PRESENTAR RECORRIDO\n”;
gotoxy(12,30);cout<<” [8]: SALIR DEL MENU\n”;
gotoxy(12,33);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,33);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertar();;getch();break;
case’2′:
clrscr();
modificar();getch();break;
case’3′:
clrscr();
buscar();getch();break;
case’4′:
clrscr();
ordenar();getch();break;
case’5′:
clrscr();
eliminar();getch();break;
case’6′:
clrscr();
presentar();getch();break;
case’7′:
clrscr();
presentar_recorrido();getch();break;
}
}while(opc!=’8′);
getch();
}
//CREAR LA CABEZA
void crearc()
{
clrscr();
int dat;
gotoxy(20,20);
cout<<”Ingrese Elemento: “;
cin>>dat;
cab=nuevo_elemento();
cab->dato=dat;
cola=cab;
cola->sig=cab;
cab->ant=cola;
getch();
}
void insertar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,25,56,’ ’);
gotoxy(13,3);cout<<”->[ INSERTAR ELEMENMTOS A LA LISTA ENLAZADA ]<-\n”;
gotoxy(12,6); cout<<” [1]: INSERTAR ORDENADO\n”;
gotoxy(12,9);cout<<” [2]: INSERTAR CABEZA\n”;
gotoxy(12,12);cout<<” [3]: INSERTAR AL FINAL\n”;
gotoxy(12,15);cout<<” [4]: REGRESAR\n”;
gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,17);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
insertarordenadoc();getch();break;
case’2′:
clrscr();
insertarinicioc();getch();break;
case’3′:
clrscr();
insertarfinalc();getch();break;
}
}
while(opc!=’4′);
getch();
}
void insertarfinalc()
{
clrscr();
nodoc *elem;
elem=nuevo_elemento();
clrscr();
gotoxy(20,20);
cout<<”\t\t”<<”INGRESE VALOR :\t”;
cin>>elem->dato;
cola->sig=elem;
elem->ant=cola;
elem->sig=cab;
cab->ant=elem;
cola=elem;
getch();
}
void insertarordenadoc()
{
nodoc *ant;
nodoc *Aux;
nodoc *post;
int dat;
Aux=nuevo_elemento();
ant=nuevo_elemento();
post=nuevo_elemento();
gotoxy(18,22);
cout<<”Ingrese un elemento: “;
cin>>dat;
Aux->dato=dat;
if(Aux->dato>cab->dato)
{
ant=cab;
post=cab->sig;
while((Aux->dato>post->dato)&&(post->sig!=cab))
{
ant=post;
post=post->sig;
}
if(post->sig==cab)
{
if (Aux->dato<post->dato)
{
Aux->sig=post;
post->ant=Aux;
ant->sig=Aux;
Aux->ant=ant;
}
else
{
Aux->sig=cab;
post->sig=Aux;
Aux->ant=post;
cab->ant=Aux;
cola=Aux;
}
}
else
{
Aux->sig=post;
post->ant=Aux;
ant->sig=Aux;
Aux->ant=ant;
}
}
else
{
Aux->dato=dat;
Aux->sig=cab;
cab->ant=Aux;
Aux->ant=cola;
cab=Aux;
cola->sig=cab;
}
}
void insertarinicioc()
{
nodoc *Aux;
int dat;
Aux=nuevo_elemento();
gotoxy(18,22);
cout<<”Ingrese un numero:”;
cin>>dat;
Aux->dato=dat;
Aux->sig=cab;
cab->ant=Aux;
cola->sig=Aux;
Aux->ant=cola;
cab=Aux;
getch();
}
void modificar()
{
clrscr();
nodoc *modificar;
nodoc *ele;
modificar=nuevo_elemento();
int db,encontrado=0;
modificar=cab;
gotoxy(10,20);
cout<<”\t”<<”INGRESE EL VALOR A MODIFICAR :\t”;
cin>> db;
for(int c=0;c<=1;c++)
{
while(db!=modificar->dato)
{
modificar=modificar->sig;
}
gotoxy(10,22);
cout<<”Elemento existente en la lista”;
encontrado=1;
gotoxy(10,25);
cout<<”\t\t”<<”INGRESE VALOR :\t”;
cin>>ele->dato;
modificar->dato=ele->dato;
c++;
}
if(encontrado==0)
{
gotoxy(10,22);
cout<<”Elemento no existente en la lista”;
}
getch();
}
void buscar()
{
clrscr();
cuadro(15,5,50,25,’ ’);
nodoc *buscar;
buscar=nuevo_elemento();
int db,encontrado=0;
buscar=cab;
gotoxy(18,15);
cout<<”Ingrese el numero a buscar: “;
cin>> db;
for(int c=0;c<=1;c++)
{
while(buscar->dato!=db)
{
buscar=buscar->sig;
}
gotoxy(18,18);
cout<<”Elemento existente en la lista”;
encontrado=1;
c++;
}
if(encontrado==0)
{
gotoxy(18,18);cout<<”Elemento no existente en la lista”;
}
getch();
}
void ordenar()
{
clrscr();
char opc=’ ‘;
do
{
clrscr();
cuadro(1,10,25,56,’ ’);
gotoxy(13,3);cout<<”->[ ORDENAR LAS LISTAS ENLAZADAS ]<-\n”;
gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]: ORDENAR ASCENDENTE\n”;
gotoxy(12,12);cout<<” [2]: ORDENAR DESCENDENTE\n”;
gotoxy(12,15);cout<<” [3]: REGRESAR\n”;
gotoxy(12,17);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,17);cin>>opc;
switch(opc)
{
case’1′:
clrscr();
ordenarc();break;
case’2′:
clrscr();
ordenarcdesc();break;
}
}
while(opc!=’3′);
getch();
}
void ordenarc()
{
nodoc *aux;
nodoc *temp;
int vaux;
aux=nuevo_elemento();
temp=nuevo_elemento();
aux=cab;
while (aux->sig!=cab)
{
temp=aux;
while(temp->sig!=cab)
{
temp=temp->sig;
if(aux->dato>temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->sig;
}
}
void ordenarcdesc()
{
nodoc *aux;
nodoc *temp;
int vaux;
aux=nuevo_elemento();
temp=nuevo_elemento();
aux=cab;
while (aux->sig!=cab)
{
temp=aux;
while(temp->sig!=cab)
{
temp=temp->sig;
if(aux->dato<temp->dato)
{
vaux=aux->dato;
aux->dato=temp->dato;
temp->dato=vaux;
}
}
aux=aux->sig;
}
}
void presentar()
{
clrscr();
nodoc * recorre;
recorre=nuevo_elemento();
recorre=cab;
cout<<”Elementos insertados:\n\n”;
for(int c=0;c<=1;c++)
{
cout<<recorre->dato<<”\t”;
recorre=recorre->sig;
while(recorre!=cab)
{
cout<<recorre->dato<<”\t”;
recorre=recorre->sig;
}
c++;
}
getch();
}
void presentar_recorrido()
{
clrscr();
nodoc * recorre;
recorre=nuevo_elemento();
recorre=cab;
cout<<”Elementos insertados:\n\n”;
for(int c=0;c<=1;c++)
{
cout<<recorre->dato<<”\t”;
recorre=recorre->sig;
while(recorre!=cab)
{
cout<<recorre->dato<<”\t”;
recorre=recorre->sig;
}
cout<<”\n”;
}
getch();
}
void eliminar()
{
presentar();
nodoc *eliminar;
nodoc *asigna;
gotoxy(10,25);cout<<”ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n”;
gotoxy(10,26);cout<<”º º\n”;
gotoxy(10,27);cout<<”ºINSERTAR NUMERO A ELIMINARº\n”;
gotoxy(10,28);cout<<”º º\n”;
gotoxy(10,29);cout<<”ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n”;
gotoxy(10,31);cout<<”Ingrese el n—mero a eliminar\t”;
cin>>eliminar->dato;
if (eliminar->dato==cab->dato)
{
eliminar_cabeza();
}
else
{
nodoc *anterior=cab;
nodoc * aux=cab->sig;
while((aux!=NULL)&&(aux->dato!=eliminar->dato))
{
anterior=aux;
aux=aux->sig;
}
if(aux!=NULL)
{
asigna=aux->sig;
anterior->sig=asigna;
aux->ant=anterior;
aux->ant=NULL;
aux->sig=NULL;
free(aux);
}
else
{
gotoxy(10,33);
cout<<”NO SE ENCUENTRA”;
}
}
}
void eliminar_cabeza()
{
/* nododoble *aux;
aux=cab;
cab=cab->sig;
// cab->ant=cola;
aux->sig=NULL;
cab->ant=cola;
aux->ant=NULL;
free(aux); */
nodoc *aux;
aux=cab;
cab=cab->sig;
// aux->sig=NULL;
aux->ant=NULL;
free(aux);
}
void cuadro(int x1,int y1, int x2, int y2, char simb)
{
for (int i1=y1;i1<=y2;i1++)
{
gotoxy(i1,x1);cout<<simb;
gotoxy(i1,x2);cout<<simb;
}
for (int i2=x1;i2<=x2;i2++)
{
gotoxy(y1,i2);cout<<simb;
gotoxy(y2,i2);cout<<simb;
}
}
0 comentarios:
Publicar un comentario