/*
* LISTAS ENLAZADAS
*
* Ejemplo un poco modificado del libro "Aprendiendo C++ para Linux"
*
* Probado con g++-4.0 sobre GNU/Debian
*/
#include <iostream>
using namespace std;
enum {kEsMasPequeno,kEsMasGrande,kEsIgual};
/*
* INICIO Clase Datos
*/
//la clase Datos, contiene los datos que se guardaran en la lista enlazada
class Datos
{ public:
//constructor
Datos(int);
//destructor
~Datos() {} //funciones de la clase
int Comparar(const Datos &);
void Mostrar();
private:
int miValor;
};
//inicializa la variable miValor
Datos::Datos(int val):miValor(val)
{}
//compara la referencia obtenida con el valor actual de miValor
int Datos::Comparar(const Datos & losOtrosDatos)
{ if(miValor<losOtrosDatos.miValor)
return kEsMasPequeno;
else if(miValor>losOtrosDatos.miValor)
return kEsMasGrande;
else
return kEsIgual;
}
void Datos::Mostrar()
{ cout << miValor << endl;
}
/*
* FIN Clase Datos
*/
/*
* INICIO Clase Nodo
*/
class Nodo
{ public:
//constructor
Nodo() {}; //destructor
virtual ~Nodo() {}; //funciones de la clase
virtual Nodo * Insertar(Datos * losDatos)=0;
virtual void Mostrar()=0;
};
/*
* FIN Clase Nodo
*/
/*
* INICIO Clase NodoInterno
*/
//esta clase hereda de la clase Nodo
class NodoInterno: public Nodo
{ public:
//constructor
NodoInterno(Datos * losDatos, Nodo * siguiente);
~NodoInterno();
virtual Nodo * Insertar(Datos * losDatos);
virtual void Mostrar();
private:
//apuntador a los datos en si
Datos * misDatos;
//apunta al siguiente apuntador de la lista
Nodo * miSiguiente;
};
NodoInterno::NodoInterno(Datos * losDatos, Nodo * siguiente): misDatos(losDatos), miSiguiente(siguiente)
{}
NodoInterno::~NodoInterno()
{ delete miSiguiente;
delete misDatos;
}
Nodo * NodoInterno::Insertar(Datos * losDatos)
{ //comprovamos si el nodo es mas grande o mas pequeño que el nuevo valor
int resultado=misDatos->Comparar(*losDatos);
switch(resultado)
{ //si es igual que yo, tiene que colocarse el primero
case kEsIgual:
//avanzar al siguiente case sin hacer nada, ya que es como si fuera mas pequeño
//si es mas pequeño que yo o igual...
case kEsMasGrande:
//los datos nuevos van antes que de mi
{ NodoInterno * nodoDatos=new NodoInterno(losDatos,this);
return nodoDatos;
}
//si es mas grande que yo...
case kEsMasPequeno:
miSiguiente=miSiguiente->Insertar(losDatos);
return this;
}
return this;
}
void NodoInterno::Mostrar()
{ //muestra el contenido de los Datos
misDatos->Mostrar();
//se va llamando a el mismo utilizando el apuntados al siguiente NodoInterno
//el ultimo NodoInterno, el apuntador apunta al NodoCola
miSiguiente->Mostrar();
}
/*
* FIN Clase NodoInterno
*/
/*
* INICIO Clase NodoCola
*/
class NodoCola: public Nodo
{ public:
//constructor
NodoCola() {} //destructor
~NodoCola() {} //funciones de la clase
virtual Nodo * Insertar(Datos * losDatos);
virtual void Mostrar() {}};
//si se llega a este punto, se debe insertar los nodos antes de la cola.
Nodo * NodoCola::Insertar(Datos * losDatos)
{ NodoInterno * nodoDatos = new NodoInterno(losDatos,this);
return nodoDatos;
}
/*
* FIN Clase NodoCola
*/
/*
* INICIO Clase NodoCabeza
*/
//el nodo cabeza, no tiene datos, solo apunta al inicio de la lista
class NodoCabeza: public Nodo
{ public:
//constructor
NodoCabeza();
//destructor
~NodoCabeza();
//funciones de la clase
virtual Nodo * Insertar(Datos * losDatos);
virtual void Mostrar();
private:
Nodo * miSiguiente;
};
//en el momento que se crea el NodoCabeza, se crea el NodoCola
NodoCabeza::NodoCabeza()
{ //como primera instancia, miSiguiente es un apuntador a un NodoCola
//porteriormente apuntara a algun NodoIntero
miSiguiente=new NodoCola;
}
NodoCabeza::~NodoCabeza()
{ delete miSiguiente;
}
Nodo * NodoCabeza::Insertar(Datos * losDatos)
{ miSiguiente=miSiguiente->Insertar(losDatos);
return this;
}
void NodoCabeza::Mostrar()
{ miSiguiente->Mostrar();
}
/*
* FIN Clase NodoCabeza
*/
/*
* INICIO Clase ListaEnlazada
*/
class ListaEnlazada
{ public:
//constructor
ListaEnlazada();
//destructor
~ListaEnlazada();
//funciones de la clase
void Insertar(Datos * losDatos);
void MostrarTodo();
private:
NodoCabeza * miCabeza;
};
//el constructor se ejecuta al declarar la variable le del tipo ListaEnlazada en el objeto main
ListaEnlazada::ListaEnlazada()
{ //se asigna un apuntador a un NodoCabeza
miCabeza=new NodoCabeza;
}
ListaEnlazada::~ListaEnlazada()
{ delete miCabeza;
}
void ListaEnlazada::Insertar(Datos * apDatos)
{ miCabeza->Insertar(apDatos);
}
void ListaEnlazada::MostrarTodo()
{ miCabeza->Mostrar();
}
/*
* FIN Clase ListaEnlazada
*/
int main()
{ Datos * apDatos;
int val;
ListaEnlazada le;
//bucle infinito
for(;;)
{ //solicitamos un valor al usuario
cout << "Indica un valor entero: (0 para terminar) ";
cin >> val;
//si introducimos un 0 (valor negativo) salimos del bucle
if(!val)
break;
apDatos=new Datos(val);
le.Insertar(apDatos);
}
//Mostramos los datos introducidos
le.MostrarTodo();
return 0;
}
/*
* En en momento que se genera la variable "le" en el main, se ejecuta el constructor de ListaEnlazada
* el cual ejecuta el constructor de NodoCabeza, el cual a su vez ejecuta el constructor del NodoCola
* quedando esta grafica
*
* ListaEnlazada NodoCabeza NodoCola
* --------------- ---> --------------- ---> ---------------
* | | | | | | | |
* | | | | | | | |
* | | | | | | | |
* | | | | | | | |
* | | | | | | | |
* --------------- | --------------- | ---------------
* | miCabeza |--- | miSiguiente |--- | |
* --------------- --------------- ---------------
*
* En este momento, se solicita un valor al usuario. Como es el primer valor, se llama a la función
* ListaEnlazada::Insertar, la cual llama a la funcion Insertar de NodoCabeza (miCabeza apunta
* al NodoCabeza), la cual llama a la funcion Insertar de NodoCola (miSiguiente apunta al NodoCola).
* Se genera un apuntar a un NodoInterno, pasandole el apuntador a Datos y el apuntador del NodoCola.
* Se devuelve su valor, que se coloca en la variable miSiguiente del NodoCabeza, y se devuelve
* a la ListaEnlazaza.
* Quedaria esta grafica
*
* ListaEnlazada NodoCabeza NodoInterno NodoCola
* --------------- ---> --------------- ---> --------------- ---> ---------------
* | | | | | | | | | | |
* | | | | | | | apuntador | | | |
* | | | | | | | a Datos | | | |
* | | | | | | | | | | |
* | | | | | | | | | | |
* --------------- | --------------- | --------------- | ---------------
* | miCabeza |--- | miSiguiente |--- | miSiguiente |--- | |
* --------------- --------------- --------------- ---------------
*
* El programa sigue pidiendo un valor al usuario. Una vez introducido un valor, se llama a la
* funcion ListaEnlazada::Insertar, la cual llama a la funcion Insertar del NodoCabeza (miSiguiente
* del NodoCabeza apunta al NodoInterno) la cual llama a la funcion Insertar de NodoInterno. En
* Insertar, se comprueba si el valor que pasamos, es igual o inferior al contenido del apuntado
* de datos del NodoIntero. Si el nuevo valor es inferior o igual, se crea un nuevo objeto NodoInterno,
* devolviendo el apuntador a miSiguiente del NodoCabeza. Si el valor es superior, se vuelve a llamar
* a la funcion insertar pasando el valor miSiguiente del NodoInterno, y asi sucesivamente...
*/
Crear cuenta
Comentarios sobre la versión: Versión 1 (0)
No hay comentarios