PROGRAMAS PARA MANEJO DE LISTAS
LISTAS SIMPLES ENLAZADAS:
El siguiente programa define la clase e implementa los
métodos definidos. Debe guardarse en un
archivo con el mismo nombre de la clase y extensión .h (ListaSimple.h), tenga
en cuenta mayúsculas y minúsculas.
//Definicion de clase
#ifndef LISTASIMPLE_H
#define LISTASIMPLE_H
class ListaSimple
{
/* Se define la estructura del nodo de la lista,
en este caso se guardaran datos de tipo entero.
*/
struct nodo{
int dato;
nodo *siguiente;
};
nodo *Lista, *Aux, *Aux1; //Lista el la variable para manejar la lista de datos
//Aux es una variable auxiliar para recorrer la lista
public:
ListaSimple(); // Constructor
void InsertarAlInicio();
void InsertarAlFinal();
void InsertarAntesDeNodo();
void MostrarDatos();
~ListaSimple(); // Destructor
}; //Finaliza la definicion de metodos...
#endif
// Se implementan los metodos
// Constructor
ListaSimple::ListaSimple()
{
Lista = NULL;
}
//Metodo para insertar un nodo al inicio
void ListaSimple::InsertarAlInicio()
{
int Valor;
//Leer el dato a insertar
cout<<"Digite el valor a insertar: "; cin>>Valor;
//Se crea un nuevo nodo usando la variable auxiliar
Aux = new nodo;
// Se guarda la informacion leida en el campo de datos
Aux->dato = Valor;
// se actualiza el enlace del apuntador el nodo siguiente.
Aux->siguiente = Lista;
// Se actualiza el puntero de lista para indicar el nuevo nodo
Lista = Aux;
cout<<"El nodo se inserto al inicio de la lista..."<<endl;
} // Fin del metodo InertarAlInicio
//Metodo para insertar un nodo antes de un nodo dado.
void ListaSimple::InsertarAntesDeNodo()
{
int Nodo, Con=0, valor;
bool seguir=false;
bool Hallado = false;
cout<<"Digite el numero del nodo antes del cual incluir: ";
cin>>Nodo;
Aux = Lista;
if (Lista != NULL) seguir = true;
//Se recorre toda la lista buscando el nodo correcto
while(seguir)
{
Con++;
if (Con==Nodo-1 || Nodo==1) //Se hallo el nodo buscado
{
Hallado = true;
seguir = false;
Aux1 = Aux;
}
Aux=Aux->siguiente;
if(Aux==NULL) seguir = false;
} // Termina el recorrido por la lista
if(!Hallado) // No se hallo el nodo buscado
{
cout<<"No hay suficientes nodos en la lista...Revise sus datos..."<<endl;
system("PAUSE");
}
else
{
cout<<"Digite el dato a guardar: ";
cin>>valor;
Aux = new nodo;
Aux->dato = valor;
if(Nodo==1)
{
Lista = Aux;
Aux->siguiente = Aux1;
}
else
{
Aux->siguiente = Aux1->siguiente;
Aux1->siguiente = Aux;
}
cout<<"Se inserto el nodo nuevo antes del nodo: "<<Nodo<<endl;
system("PAUSE");
}
}//Termina el metodo InsertarAntesDeNodo
//Metodo para insertar al final de la lista
void ListaSimple::InsertarAlFinal()
{
int Valor;
//Leer el dato a insertar
cout<<"Digite el valor a insertar: "; cin>>Valor;
//Se crea un nuevo nodo usando la variable auxiliar
Aux = new nodo;
// Se guarda la informacion leida en el campo de datos
(*Aux).dato = Valor;
if (Lista==NULL)
Lista = Aux;
else
{
Aux1 = Lista;
while(Aux1->siguiente!=NULL)
{
Aux1 = Aux1->siguiente;
}
//Enlazo el ultimo nodo de la lista con el nuevo
Aux1->siguiente = Aux;
}
// se pone NULL el enlace siguiente del nodo creado por ser ahora el ultimo.
Aux->siguiente = NULL;
} // Fin del metodo IncluirAlFinal
void
ListaSimple::MostrarDatos()
{
Aux = Lista;
cout<<"INFORMACION DE
while(Aux!=NULL)
{
cout<<Aux->dato<<",
";
Aux = Aux->siguiente;
}
cout<<"\nFinal de la
lista...\n"<<endl;
} // Final del metodo mostrar la lista
//Destructor
ListaSimple::~ListaSimple()
{
delete Lista; Aux;
} //Fin de la implementacio de los metodos de la clas
El siguiente es el programa principal, puede llamarse de cualquier manera, y con la extensión .cpp, por ejemplo (Listas.cpp)
#include
<cstdlib>
#include
<iostream>
#include
<iomanip>
using
namespace std;
#include
"ListaSimple.h"
int main(int
argc, char *argv[])
{
int opc;
ListaSimple MiLista;
do
{
// Menu de opciones disponibles
cout<<"*** OPCIONES
DISPONIBLES ***\n"<<endl;
cout<<"1. Incluir nodo al inicio"<<endl;
cout<<"2. Incluir nodo en medio"<<endl;
cout<<"3. Incluir nodo al final"<<endl;
cout<<"4. Borrar un nodo"<<endl;
cout<<"5. Mostrar la lista"<<endl;
cout<<"6. Buscar datos"<<endl;
cout<<"7. Terminar"<<endl;
cout<<"digite su opcion: ";
//Lectura de la opcion elegida por el usuario
do {
cin>>opc;
} while (opc<1 ||opc>7);
switch(opc)
{
case 1:
{
MiLista.InsertarAlInicio();
break;
}
case 2:
{
MiLista.InsertarAntesDeNodo();
break;
}
case 3:
{
MiLista.InsertarAlFinal();
break;
}
case 5:
{
MiLista.MostrarDatos();
break;
}
} // Fin
} while (opc <=6);
cout<<"Programa terminado
"<<endl;
system("PAUSE");
return EXIT_SUCCESS;
} // Fin del programa principal
LISTAS DOBE ENLACE
Este es el programa principal:
#include
<cstdlib>
#include
<iostream>
#include
<iomanip>
using
namespace std;
#include
"listasDE.h"
int main(int
argc, char *argv[])
{
int opc;
listasDE MiListaDE ;
do
{
// Menu de opciones disponibles
cout<<"*** OPCIONES
DISPONIBLES ***\n"<<endl;
cout<<"1. Insertar al inicio"<<endl;
cout<<"2. Insertar al final"<<endl;
cout<<"3. Consultar contenido"<<endl;
cout<<"4. Mostrar la lista"<<endl;
cout<<"5. Eliminar un nodo"<<endl;
cout<<"6. Terminar"<<endl;
cout<<"Digite su opcion: ";
//Lectura de la opcion elegida por el usuario
do {
cin>>opc;
} while (opc<1 ||opc>6);
switch(opc)
{
case 1:
{
int valor;
MiListaDE.InsAlInicio(MiListaDE.leerValor());
break;
}// Fin del caso 1
case 4:
{
MiListaDE.MostrarLista();
break;
} // Fin del caso 4
case 5:
{
int vr;
MiListaDE.EliminarNodo(MiListaDE.leerValor());
break;
} // Fin del caso 5
} // Fin
} while (opc <=5);
cout<<"\nPrograma terminado...
"<<endl;
system("PAUSE");
return EXIT_SUCCESS;
} // Fin del programa principal
Y esta es la clase. Guardar en un archivo con extensión .h, en con el nombre “listasDE.h”
class listasDE
{
struct nodo
{
int datos;
nodo *siguiente, *anterior;
};
nodo *listaDE, *Aux, *Aux1;
public:
listasDE();
int leerValor();
int InsAlInicio(int valor);
int EliminarNodo(int valor);
void MostrarLista();
};
// Metodo constructor
listasDE::listasDE()
{
listaDE = NULL;
} // Fin del metodo constructor
// Metodo que permite leer el valor a incluir en cda nodo
int
listasDE::leerValor()
{
int vr;
cout<<"Digite un valor: ";
cin>>vr;
return vr;
} // Fin del metodo leerValor
// Metodo para insertar un nodo al final de la lista
int listasDE::InsAlInicio(int
valor)
{
Aux = new nodo;
if(Aux==NULL)
{
cout<<"NO hay memoria disponible para crear mas nodos.."<<endl;
system("PAUSE");
return -1;
}
Aux->datos = valor;
Aux->anterior = NULL;
if(listaDE==NULL) // Lista vacia
Aux->siguiente = NULL;
else
{
Aux->siguiente = listaDE;
listaDE->anterior = Aux;
}
listaDE = Aux;
} // Fin del metodo insertar nodo al final
// Metodo para eliminar un nodo de la lista
int
listasDE::EliminarNodo(int valor)
{
Aux = listaDE;
int i = 0;
bool parar = false;
if (listaDE==NULL)
{
cout<<"La lista esta vacia..."<<endl;
parar = true;
} // Fin de validacion si la lista esta vacia
// recorremos la lista buscando el nodo a eliminar
while(!parar)
{
i++;
if(Aux->datos==valor)
{
cout<<"Nodo: "<<Aux->datos<<endl;
cout<<"Siguiente: "<<Aux->siguiente->datos;
cout<<"Anterior :
"<<Aux->anterior->datos;
system("PAUSE");
Aux1=Aux->anterior;
Aux1->siguiente = Aux->siguiente;
Aux1=Aux->siguiente;
Aux1->anterior = Aux->anterior;
delete Aux;
parar = true;
}
else
Aux = Aux->siguiente;
if(Aux==NULL)
{
cout<<"EL dato buscado no se encontro en la lista..."<<endl;
parar = true;
}
}
} // Fin del metodo EliminarNodo
// Metodo que permite mostrar el contenido de la lista
void listasDE::MostrarLista()
{
int i=0; // Variable usada para contar los nodos de la lista
Aux = listaDE;
cout<<"\n\nCONTENIDO DE
cout<<"---------------------"<<endl;
while(Aux!=NULL)
{
i++;
cout<<"Nodo
"<<i<<"= "<<Aux->datos<<endl;
Aux = Aux->siguiente;
}
cout<<"---------------------"<<endl;
cout<<"Final de la lista..."<<endl;
system("PAUSE");
delete Aux;
} // Fin del metodo MostrarLista
EJEMPLO
2. LISTAD DE DOBLE ENLACE
/* Este programa crea una lista de doble enlace,
guardando en cada
nodo valores enteros positivos,
de manera que la
lista permanece ordenada
Elaborado por:
Edgar Romero Rodríguez, Ing. de Sistemas, UIS
*/
#include <cstdlib>
#include <iostream>
#include
<iomanip>
using
namespace std;
class
listasDE
{
struct nodo
{
int datos;
nodo *siguiente, *anterior;
};
nodo *listaDE, *aux, *aux1;
public:
listasDE(); //Constructor
int leerValor();
int InsertarNodo(int valor);
int EliminarNodo(int valor);
void MostrarLista();
};
// Metodo constructor
listasDE::listasDE()
{
listaDE = NULL;
} // Fin del metodo constructor
// Metodo que permite leer el valor a incluir en cda nodo
int
listasDE::leerValor()
{
int vr;
cout<<"Digite un valor:
";
cin>>vr;
return vr;
} // Fin del metodo leerValor
// Metodo para insertar un nodo al final de la lista
int listasDE::InsertarNodo(int valor)
{
aux = new nodo; //
Se crea el nuevo nodo
if(aux==NULL) // Se verifica si se pudo crear en nuevo nodo
{
cout<<"NO hay memoria disponible para crear mas
nodos.."<<endl;
system("PAUSE");
return -1;
}
aux->datos =
valor; // Se guarda el valor en el nuevo nodo
aux->anterior =
NULL;
if(listaDE==NULL) //
Averiguamos si la lista esta vacia
{
cout<<"Lista vacia..."<<endl;
aux->siguiente
= NULL;
listaDE = aux;
}
else
{
// Si la lista no
está vacía se busca donde insertarlo
// Verificamos si
el nodo se inserta al inicio
if(listaDE->datos > valor) // El nodo se insertara al inicio
{
aux->siguiente = listaDE;
listaDE->anterior = aux;
listaDE =
aux; //Muevo el incio de la lista al
nuevo nodo
}
else // El nodo se nsertara en medio de otros
nodos...
{
aux1 =
listaDE;
bool hallado =
false; // Usamos esta variable para parar el ciclo una ves hallado el punto de
insercion
//Se recorre la
lista buscando el punto donde se insertara el nodo
while(not
hallado)
{
if
(aux1->datos > valor) // El nodo se inserta en medio de otros
{
// Antes de
este nodo se inserta el nuevo.
Establezco enlaces
cout<<"El nodo se insertara antes del nodo:
"<<aux1->datos<<endl;
aux1->anterior->siguiente = aux; // Enlazo en anterior con el
nuevo, hacia adelante
aux->anterior = aux1->anterior; //Enlazo el nuevo con el anterior,
hacia atraz
aux->siguiente = aux1; //Enlazo el nuevo con el siguiente, hacia
adelante
aux1->anterior = aux; //Enlazo el siguiente con el nuevo, hacia atras
hallado =
true; //no se continua el ciclo
} else
{
if(aux1->siguiente!=NULL) aux1=aux1->siguiente; // Paso al
siguiente nodo
else //este es el nodo final, agrego el nuevo
nodo.
{
cout<<"El nodo se insertara al final de la lista..."<<endl;
aux1->siguiente=aux; //Enlazo el ultimo con el nuevo nodo
aux->anterior=aux1; //Enlazo el nuevo nodo con el anterior, hacia
atras
aux->siguiente=NULL; // Muevo el final de la lista al nuevo nodo.
hallado =
true;
}//Fin del
else
}//Fin del
else
}//Fin del
while
} //Fin del
else
}//Fin del else
lista vacia.
return 0;
} // Fin del metodo insertar nodo al final
// Metodo para eliminar un nodo de la lista
int listasDE::EliminarNodo(int valor)
{
aux = listaDE;
int i = 0;
bool parar = false;
if (listaDE==NULL)
{
cout<<"La lista esta vacia..."<<endl;
bool hallado =
true;
} // Fin de
validacion si la lista esta vacia
// recorremos la
lista buscando el nodo a eliminar
while(!parar)
{
i++;
if(aux->datos==valor)
{
cout<<"Nodo: "<<aux->datos<<endl;
cout<<"Siguiente:
"<<aux->siguiente->datos<<endl;
cout<<"Anterior :
"<<aux->anterior->datos<<endl;
system("PAUSE");
aux1=aux->anterior;
aux1->siguiente = aux->siguiente;
aux1=aux->siguiente;
aux1->anterior = aux->anterior;
delete aux;
parar = true;
}
else
aux = aux->siguiente;
if(aux==NULL)
{
cout<<"EL dato buscado no se encontro en la
lista..."<<endl;
parar = true;
}
}
} // Fin del metodo EliminarNodo
// Metodo que permite mostrar el contenido de la lista
void listasDE::MostrarLista()
{
int i=0; // Variable
usada para contar los nodos de la lista
aux = listaDE;
cout<<"\n\nCONTENIDO DE
cout<<"---------------------"<<endl;
while(aux!=NULL)
{
i++;
cout<<"Nodo
"<<i<<"= "<<aux->datos<<endl;
aux = aux->siguiente;
}
cout<<"---------------------"<<endl;
cout<<"Final de la
lista..."<<endl;
system("PAUSE");
delete aux;
} // Fin del metodo MostrarLista
//Este es el progrma principal
int main(int argc, char *argv[])
{
int opc;
listasDE MiListaDE;
do
{
// Menu de
opciones disponibles
cout<<"*** OPCIONES
DISPONIBLES ***\n"<<endl;
cout<<"1. Insertar un nodo"<<endl;
cout<<"2. Mostrar la lista"<<endl;
cout<<"3. Eliminar un
nodo"<<endl;
cout<<"4.
Terminar"<<endl;
cout<<"Digite su opcion: ";
//Lectura de
la opcion elegida por el usuario
do {
cin>>opc;
} while (opc<1 ||opc>4);
switch(opc)
{
case 1:
{
int valor;
MiListaDE.InsertarNodo(MiListaDE.leerValor());
break;
}// Fin del
caso 1
case 2:
{
MiListaDE.MostrarLista();
break;
} // Fin del caso 4
case 3:
{
int vr;
MiListaDE.EliminarNodo(MiListaDE.leerValor());
break;
} // Fin del
caso 5
} // Fin del
switch
} while (opc
<=3);
cout<<"\nPrograma
terminado... "<<endl;
system("PAUSE");
return
EXIT_SUCCESS;
} // Fin del programa principal