Como declarar un tipo

[dehm]

Grafo.h (continuación):

Código C++:

//********************//
//destructor del grafo//
//********************//
template <typename datonodo_t, typename datoarista_t>
Grafo<datonodo_t,datoarista_t>::~Grafo()
{
    std::cout<<"Iniciamos el destructor"<<std::endl;
    pArista A;
    //meto todas las arista del nodo Raiz en la pila
    guardaAristas(Raiz);
 
    //empiezo a borrar todas las ramas que hay en la pila
    while (!pila.empty())
        {
            A=pila.top();
            pila.pop();
            borrarNodos(A);
        }
    delete Raiz;
    //~listaHojas();
    std::cout<<"Borrada la raiz"<<std::endl;
}
 
//*****************//
//constructor copia//
//*****************//
template <typename datonodo_t, typename datoarista_t>
Grafo<datonodo_t, datoarista_t>::Grafo (const Grafo<datonodo_t, datoarista_t>& G)
{
    std::cout<<"CONSTRUCTOR COPIA"<<std::endl;
    //Raiz
    pNodo indice1=G.Raiz;
    Raiz=new t_nodo (*indice1);
    pNodo indice=Raiz;
    pArista indiceA=indice1->adyacente;
    int i=0;
    while (indice1->siguiente)
        {
            indiceA=indice1->adyacente;
            //std::cout<<"Hasta aqui "<<i+1<<std::endl;
 
            while (indiceA)
                {
                    pNodo hijo=posicionarseEnNodo(indiceA->destino->datonodo);//creo un nodo con el contenido del nodo origen hijo
                    if (hijo==0)
                        {
                            hijo=new t_nodo(*indiceA->destino);
                        }
                    pArista A= new t_arista(*indiceA);
                    InsertarHijo(indice,hijo,A->anterior,A);
                    indiceA=indiceA->siguiente;
                }
 
            indice1=indice1->siguiente;
            indice=indice->siguiente;
            i++;
        }
    listaHojas(G.listaHojas);//así o listaHojas=G.listaHojas?
    std::cout<<"Copia terminada"<<std::endl;
}
 
//*************************//
//sobrecarga del operador =//
//*************************//
 
template <typename datonodo_t, typename datoarista_t>
Grafo<datonodo_t, datoarista_t>& Grafo<datonodo_t, datoarista_t>::operator=(const Grafo<datonodo_t, datoarista_t>& G)
{
    if (this!=&G)
        {
            delete Raiz;
            //vacio la pila
            while (!pila.empty())
                {
                    pila.pop();
                }
            pNodo indice1=G.Raiz;
            Raiz=new t_nodo (*indice1);
            pNodo indice=Raiz;
            pArista indiceA=indice1->adyacente;
            while (indice1->siguiente)
                {
                    indiceA=indice1->adyacente;
 
                    while (indiceA)
                        {
                            pNodo hijo=posicionarseEnNodo(indiceA->destino->datonodo);//creo un nodo con el contenido del nodo origen hijo
                            if (hijo==0)
                                {
                                    hijo=new t_nodo(*indiceA->destino);
                                }
                            pArista A= new t_arista(*indiceA);
                            InsertarHijo(indice,hijo,A->anterior,A);
                            indiceA=indiceA->siguiente;
                        }
 
                    indice1=indice1->siguiente;
                    indice=indice->siguiente;
                }
            listaHojas=G.listaHojas;
        }
    return *this;
}
 
//**************//
//añadir un nodo//
//**************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::anadirNodo(pNodo& n)
{
    pNodo indice=Raiz;
    //me posiciono al final de la lista
    while (indice && indice->siguiente!=0)
        {
            indice=indice->siguiente;
        }
    indice->siguiente=n;
    nNodos++;
}
 
//****************//
//eliminar un nodo//
//****************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::eliminarNodo(pNodo& n)
{
    pNodo anterior=Raiz;
    //avanzo anterior hasta el nodo anterior al que quiero borrar
    while (anterior->siguiente!=n)
        {
            anterior=anterior->siguiente;
        }
    if (anterior==Raiz)//primer elemento
        {
            Raiz->siguiente=n->siguiente;
        }
    else
        {
            anterior->siguiente=n->siguiente;
        }
    delete n;
    nNodos--;
}
 
//*****************//
//añadir una arista//
//*****************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::anadirArista (pNodo& NodoOrigen, pNodo& NodoDestino, pArista& precedente, pArista& NuevaArista)
{
    if (!NodoOrigen->adyacente)//primera arista
        {
            NodoOrigen->adyacente=NuevaArista;
            NuevaArista->destino=NodoDestino;
            //std::cout<<"Primera arista"<<std::endl;
        }
    else
        {
            pArista Aux=NodoOrigen->adyacente;
            while (Aux!=precedente && Aux->siguiente)
                {
                    Aux=Aux->siguiente;
                }
            NuevaArista->siguiente=Aux->siguiente;
            Aux->siguiente=NuevaArista;
            NuevaArista->destino=NodoDestino;
            NuevaArista->anterior=Aux;
        }
}
 
//*******************//
//eliminar una arista//
//*******************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::eliminarArista(pArista& A)
{
    pNodo indice=Raiz;
    //veo si la arista a borrar es la adyacente de algún nodo (primera arista)
    while (indice && indice->adyacente!=A)
        {
            indice=indice->siguiente;
        }
    if (indice)//si finalmente la arista a borrar es adyacente de indice
        {
            //si es arista única
            if (!A->anterior && !A->siguiente)
                {
                    indice->adyacente=0;
                    listaHojas.remove(indice);
                }
            else
                {
                    indice->adyacente=A->siguiente;
                }
        }
 
    //inicio el borrado propiamente dicho
    if (A->anterior)
        {
            A->anterior->siguiente=A->siguiente;
        }
    if (A->siguiente)
        {
            A->siguiente->anterior=A->anterior;
        }
    delete A;
}
 
//***********************************************//
//borrar todos los nodos que penden de una arista//
//***********************************************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::borrarNodos(pArista& A)
{
    pNodo hijo=A->destino;
    //quitar un padre al nodo hijo
    if (hijo->nPadres>0) hijo->nPadres--;
    //si todavía es hijo de algún padre....
    if (hijo->nPadres)
        {
            //...me limito a borrar la arista que une al padre con el hijo
            eliminarArista(A);
        }
    else //si se queda huerfanito
        {
            //si el hijo es hoja no tiene aristas que salgan de él, luego adyacente apunta a 0
            if (!hijo->adyacente)
                {
                    //me posiciono en la arista a borrar
                    eliminarArista(A);
                    listaHojas.remove(hijo);
                    eliminarNodo(hijo);//lo saco de la lista general de nodos
                }
            else
                {
                    guardaAristas(hijo);
                    eliminarArista(A);
                    eliminarNodo(hijo);
                    while (!pila.empty())
                        {
                            A=pila.top();
                            pila.pop();
                            borrarNodos(A);
                        }
                }
        }
}
//**************************//
//insertar un hijo a un nodo//
//**************************//
 
template <typename datonodo_t, typename datoarista_t>
void Grafo<datonodo_t,datoarista_t>::InsertarHijo(pNodo& padre, pNodo& hijo, pArista& precedente, pArista& NuevaArista)
{
    //primer elemento
    if (Raiz==0)
        {
            Raiz=hijo;
            listaHojas.push_back(Raiz);
            nNodos++;
        }
    else
        {
            if (!existeHermano(padre,hijo))
                {
                    listaHojas.remove(padre);//el padre deja de ser hijo...para convertirse en padre :-)
                    hijo->nPadres++;//añado un padre
                    //solo añado el nodo si es nuevo
                    if (!existeNodo(hijo))
                        {
                            anadirNodo(hijo);
                            listaHojas.push_back(hijo);
                        }
                    anadirArista(padre, hijo, precedente, NuevaArista);
                }
            else std::cout<<"2 nodos iguales no pueden tener el mismo padre"<<std::endl;
        }
    /*std::cout<<"Lista de hojas: "<<std::endl;
    for (auto it=listaHojas.begin();it!=listaHojas.end();it++)
    {
        std::cout<<((*it)->datonodo.LeeCodigo())<<" - ";
    }
    std::cout<<std::endl;*/
}