[Consulta] C++

[Z_z]

pasame por pm tu mail y te mando las cosas.

lista.h

#ifndef AED2_LISTA_H_INCLUDED
#define AED2_LISTA_H_INCLUDED

#include <iostream>
#include "TiposBasicos.h"

namespace aed2{
/**
* Implementación del módulo Lista Enlazada(alpha) con su const_Iterador correspondiente.
* Como estamos en C++, en lugar de alpha vamos a usar T.
* Del parámetro formal T, sólo se supone la existencia de su constructor por copia.
*/
template <typename T>
class Lista
{
public:
//forward declarations
class Iterador;
class const_Iterador;

/// Crea una lista enlazada vacía. (Operación Vacia())
Lista();
/// Crea por copia una lista enlazada (operación Copiar())
Lista(const Lista& otra);
/// Destruye la lista, incluyendo los T alojados
~Lista();
/// Operacion de asignacion
Lista<T>& operator=(const Lista<T>& otra);

/// Opreaciones básicas
bool EsVacia() const;
Nat Longitud() const;


/// Acceso al primero y último elemento (en O(1) )
/// Versiones modificables y no modificables
T& Primero();
const T& Primero() const;
T& Ultimo();
const T& Ultimo() const;
/// Operador "iésimo"
T& operator[](Nat i);
const T& operator[](Nat i) const;

/// Elimina el primer elemento
void Fin();
/// Elimina el último elemento
void Comienzo();

/// Inserción de elementos
Iterador AgregarAdelante(const T& elem);
Iterador AgregarAtras(const T& elem);

/*************************************
* const_Iterador de Lista, no modificable *
*************************************/
class const_Iterador
{
public:
/// Funcion de copia
const_Iterador(const Lista<T>::const_Iterador& otro) :
lista(otro.lista), nodo_siguiente(otro.nodo_siguiente) {}

const_Iterador(const Lista<T>::Iterador& otro) :
lista(otro.lista), nodo_siguiente(otro.nodo_siguiente) {}

bool HayAnterior() const;
bool HaySiguiente() const;

const T& Anterior() const;
const T& Siguiente() const;

void Avanzar();
void Retroceder();

private:
/// El constructor es privado, necesitamos el friend.
const_Iterador(const Lista<T>* _lista, const typename Lista<T>::Nodo* _proximo)
: lista(_lista), nodo_siguiente(_proximo) {};
friend typename Lista<T>::const_Iterador Lista<T>::CrearIt() const;
friend typename Lista<T>::const_Iterador Lista<T>::CrearItUlt() const;

const Lista<T>* lista;
const typename Lista<T>::Nodo* nodo_siguiente;

//devuelve el nodo siguiente en la lista circular
const typename Lista<T>::Nodo* SiguienteReal() const;
};
/// Creación del const_Iterador
const_Iterador CrearIt() const;
const_Iterador CrearItUlt() const;


/**********************************
* const_Iterador de Lista, modificable *
**********************************/
class Iterador
{
public:
///Funcion copiar
Iterador(const Iterador& otro) :
lista(otro.lista), nodo_siguiente(otro.nodo_siguiente) {}

bool HayAnterior() const;
bool HaySiguiente() const;

T& Anterior() const;
T& Siguiente() const;

void Avanzar();
void Retroceder();

void EliminarAnterior();
void EliminarSiguiente();

void AgregarComoAnterior(const T& elem);
void AgregarComoSiguiente(const T& elem);

private:
/// El constructor es privado, necesitamos el friend.
Iterador(Lista<T>* _lista, typename Lista<T>::Nodo* _proximo)
: lista(_lista), nodo_siguiente(_proximo) {};
friend typename Lista<T>::Iterador Lista<T>::CrearIt();
friend typename Lista<T>::Iterador Lista<T>::CrearItUlt();
friend class Lista<T>::const_Iterador;

Lista<T>* lista;
typename Lista<T>::Nodo* nodo_siguiente;

//devuelve el nodo siguiente en la lista circular
typename Lista<T>::Nodo* SiguienteReal() const;

};
/// Creación del const_Iterador
Iterador CrearIt();
Iterador CrearItUlt();

private:
struct Nodo
{
Nodo(const T& d) : dato(d), anterior(NULL), siguiente(NULL) {};

T dato;
Nodo* anterior;
Nodo* siguiente;
};

Nodo* primero;
Nat longitud;
};

template<class T>
std::ostream& operator<<(std::ostream& os, const Lista<T>& l);
template<class T>
bool operator==(const Lista<T>&, const Lista<T>&);
#include "Lista.cpp"

}

#endif // AED2_LISTA_H_INCLUDED

lista.cpp

/// Implementación

template <typename T>
Lista<T>::Lista() : primero(NULL), longitud(0) {}

template <typename T>
Lista<T>::Lista(const Lista<T>& otra) : primero(NULL), longitud(0)
{
*this = otra;
}

template <typename T>
Lista<T>& Lista<T>::operator=(const Lista<T>& otra) {
if(this != &otra) {
while(!EsVacia()) Fin();
for(const_Iterador it = otra.CrearIt(); it.HaySiguiente(); it.Avanzar())
this->AgregarAtras(it.Siguiente());
}
return *this;
}

template <typename T>
Lista<T>::~Lista()
{
while(!EsVacia()) Fin();
}

template <typename T>
bool Lista<T>::EsVacia() const
{
return primero == NULL;
}

template <typename T>
Nat Lista<T>::Longitud() const
{
return longitud;
}

template <typename T>
T& Lista<T>:rimero()
{
assert(not EsVacia());
return CrearIt().Siguiente();
}

template <typename T>
const T& Lista<T>:rimero() const
{
assert(not EsVacia());
return CrearIt().Siguiente();
}

template <typename T>
T& Lista<T>::Ultimo()
{
assert(not EsVacia());
return CrearItUlt().Anterior();
}

template <typename T>
const T& Lista<T>::Ultimo() const
{
assert(not EsVacia());
return CrearItUlt().Anterior();
}

template <typename T>
const T& Lista<T>::operator[](Nat i) const
{
assert(i < longitud);
const_Iterador it = CrearIt();
while(i > 0) {
it.Avanzar();
--i;
}

return it.Siguiente();
}

template <typename T>
T& Lista<T>::operator[](Nat i)
{
assert(i < longitud);
Iterador it = CrearIt();
while(i > 0)
{
it.Avanzar();
--i;
}

return it.Siguiente();
}

template <typename T>
void Lista<T>::Fin()
{
assert(not EsVacia());
CrearIt().EliminarSiguiente();
}

template <typename T>
void Lista<T>::Comienzo()
{
assert(not EsVacia());
CrearItUlt().EliminarAnterior();
}

template <typename T>
typename Lista<T>::Iterador Lista<T>::AgregarAdelante(const T& dato)
{
typename Lista<T>::Iterador res = CrearIt();
res.AgregarComoSiguiente(dato);
return res;
}

template <typename T>
typename Lista<T>::Iterador Lista<T>::AgregarAtras(const T& dato)
{
typename Lista<T>::Iterador res = CrearItUlt();
res.AgregarComoSiguiente(dato);
return res;
}

/*
template <typename T>
std::ostream& Lista<T>::Mostrar(std::ostream& os) const
{
os << "| ";
const_Iterador it = CrearIt();

while(it.HaySiguiente())
{
os << it.Siguiente() << " ";
it.Avanzar();
}
return os << "|";
}
*/


template <typename T>
typename Lista<T>::const_Iterador Lista<T>::CrearIt() const
{
return const_Iterador(this, primero);
}

template <typename T>
typename Lista<T>::const_Iterador Lista<T>::CrearItUlt() const
{
return const_Iterador(this, NULL);
}

template <typename T>
bool Lista<T>::const_Iterador::HaySiguiente() const
{
return nodo_siguiente != NULL;
}

template <typename T>
bool Lista<T>::const_Iterador::HayAnterior() const
{
return nodo_siguiente != lista->primero;
}

template <typename T>
const T& Lista<T>::const_Iterador::Siguiente() const
{
assert(HaySiguiente());
return nodo_siguiente->dato;
}

template <typename T>
const T& Lista<T>::const_Iterador::Anterior() const
{
assert(HayAnterior());
return SiguienteReal()->anterior->dato;
}

template <typename T>
void Lista<T>::const_Iterador::Avanzar()
{
assert(HaySiguiente());
nodo_siguiente = nodo_siguiente->siguiente;
if(nodo_siguiente == lista->primero) nodo_siguiente = NULL;
}

template <typename T>
void Lista<T>::const_Iterador::Retroceder()
{
assert(HayAnterior());
nodo_siguiente = SiguienteReal()->anterior;
}

template <typename T>
const typename Lista<T>::Nodo* Lista<T>::const_Iterador::SiguienteReal() const {
return nodo_siguiente == NULL ? lista->primero : nodo_siguiente;
}

template <typename T>
typename Lista<T>::Iterador Lista<T>::CrearIt()
{
return Iterador(this, primero);
}

template <typename T>
typename Lista<T>::Iterador Lista<T>::CrearItUlt()
{
return Iterador(this, NULL);
}

template <typename T>
bool Lista<T>::Iterador::HaySiguiente() const
{
return nodo_siguiente != NULL;
}

template <typename T>
bool Lista<T>::Iterador::HayAnterior() const
{
return nodo_siguiente != lista->primero;
}

template <typename T>
T& Lista<T>::Iterador::Siguiente() const
{
assert(HaySiguiente());
return nodo_siguiente->dato;
}

template <typename T>
T& Lista<T>::Iterador::Anterior() const
{
assert(HayAnterior());
return SiguienteReal()->anterior->dato;
}

template <typename T>
void Lista<T>::Iterador::Avanzar()
{
assert(HaySiguiente());
nodo_siguiente = nodo_siguiente->siguiente;
if(nodo_siguiente == lista->primero) nodo_siguiente = NULL;
}

template <typename T>
void Lista<T>::Iterador::Retroceder()
{
assert(HayAnterior());
nodo_siguiente = SiguienteReal()->anterior;
}

template <typename T>
void Lista<T>::Iterador::AgregarComoAnterior(const T& dato)
{
Nodo* sig = SiguienteReal();
Nodo* nuevo = new Nodo(dato);

//asignamos anterior y siguiente de acuerdo a si el nodo es el primero
//o no de la lista circular
nuevo->anterior = sig == NULL ? nuevo : sig->anterior;
nuevo->siguiente = sig == NULL ? nuevo : sig;

//reencadenamos los otros nodos (notar que no hay problema cuando nuevo
//es el primer nodo creado de la lista)
nuevo->anterior->siguiente = nuevo;
nuevo->siguiente->anterior = nuevo;

//cambiamos el primero en el caso que nodo_siguiente == primero
if(nodo_siguiente == lista->primero)
lista->primero = nuevo;

lista->longitud++;
}

template <typename T>
void Lista<T>::Iterador::AgregarComoSiguiente(const T& dato)
{
AgregarComoAnterior(dato);
Retroceder();
}

template <typename T>
void Lista<T>::Iterador::EliminarAnterior()
{
assert(HayAnterior());
Retroceder();
EliminarSiguiente();
}

template <typename T>
void Lista<T>::Iterador::EliminarSiguiente()
{
assert(HaySiguiente());

Nodo* tmp = nodo_siguiente;

//reencadenamos los nodos
tmp->siguiente->anterior = tmp->anterior;
tmp->anterior->siguiente = tmp->siguiente;

//borramos el unico nodo que habia?
nodo_siguiente = tmp->siguiente == tmp ? NULL : tmp->siguiente;
//borramos el último?
nodo_siguiente = tmp->siguiente == lista->primero ? NULL : tmp->siguiente;

if(tmp == lista->primero) //borramos el primero?
lista->primero = nodo_siguiente;

delete tmp;
lista->longitud--;
}

template <typename T>
typename Lista<T>::Nodo* Lista<T>::Iterador::SiguienteReal() const {
return nodo_siguiente == NULL ? lista->primero : nodo_siguiente;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const Lista<T>& lista)
{
return Mostrar(os, lista, '<', '>');
}

template <typename T>
bool operator==(const Lista<T>& l1, const Lista<T>& l2)
{
typename Lista<T>::const_Iterador it1 = l1.CrearIt();
typename Lista<T>::const_Iterador it2 = l2.CrearIt();
while(it1.HaySiguiente() and it2.HaySiguiente() and it1.Siguiente() == it2.Siguiente()) {
it1.Avanzar(); it2.Avanzar();
}
return not it1.HaySiguiente() and not it2.haySiguiente();
}

tiposbasico.h

#ifndef AED2_TIPOSBASICOS_H_INCLUDED
#define AED2_TIPOSBASICOS_H_INCLUDED

#include<iostream>
#include<string>
#include<cassert>

#ifndef NULL
#define NULL 0
#endif

namespace aed2{
typedef unsigned int Nat;
typedef std::string String;

template<class T>
std::ostream& Mostrar(std::ostream& os, const T& t, char izq, char der, char sep = ',') {
typename T::const_Iterador it = t.CrearIt();
os << izq;
while(it.HaySiguiente()) {
os << it.Siguiente();
it.Avanzar();
if(it.HaySiguiente()) os << sep;
}
return os << der;
}
}

#endif //AED2_TIPOSBASICOS_H_INCLUDED

fijate, es un asquerosidad pegarlo asi, tiene iteradores si no me equivoco, a lo mejor falta algun include, sino, como y dije, pasame el mail y te paso las cosas como dios manda (no hay para mandar attachments por pm y me da paja subir)

---------- Post added at 00:30 ---------- Previous post was at 00:09 ----------

edit: Bueno...

list - C++ Reference

estan por default entre las librerias de c++, , y bastante completa..