ciao a tutti ho implementato la seguente struttura dati:
nodogl.h
codice:
#ifndef nodogl_h
#define nodogl_h
#include<iostream>
#include<stdlib.h>
#include "listap.h"
using namespace std;
template<class tipoelem>
class nodogl
{
public:
typedef struct nodoad
{
char *etichetta;
int cursore;
int peso;
} adiacente;
nodogl();
void setetichetta(char *);
void setvalore(tipoelem);
void setposizione(int);
void setadiacent(listap<struct nodoad> *);
char *getetichetta();
tipoelem getvalore();
int getposizione();
listap<struct nodoad> *getadiacent();
nodogl<tipoelem> operator=(nodogl<tipoelem> );
bool operator==(nodogl<tipoelem> );
private:
char *etichetta;
tipoelem valore;
int posizione;
listap<struct nodoad> *adiacent;
};
#endif
template<class tipoelem>
nodogl<tipoelem>::nodogl()
{
etichetta = NULL;
posizione = -1;
adiacent = new listap<tipoelem>;
}
template<class tipoelem>
void nodogl<tipoelem>::setetichetta(char *et)
{
etichetta = et;
}
template<class tipoelem>
void nodogl<tipoelem>::setvalore(tipoelem val)
{
valore = val;
}
template<class tipoelem>
void nodogl<tipoelem>::setposizione(int pos)
{
posizione = pos;
}
template<class tipoelem>
void nodogl<tipoelem>::setadiacent(listap<struct nodoad> *ad)
{
adiacent = ad;
}
template<class tipoelem>
char *nodogl<tipoelem>::getetichetta()
{
return(etichetta);
}
template<class tipoelem>
tipoelem nodogl<tipoelem>::getvalore()
{
return(valore);
}
template<class tipoelem>
int nodogl<tipoelem>::getposizione()
{
return(posizione);
}
template<class tipoelem>
listap<struct nodoad> *nodogl<tipoelem>::getadiacent()
{
return(adiacent);
}
template<class tipoelem>
nodogl<tipoelem> nodogl<tipoelem>::operator=(nodogl<tipoelem> nodo)
{
this->setetichetta(nodo.getetichetta());
this->setvalore(nodo.getvalore());
this->setposizione(nodo.getposizione());
this->setadiacent(nodo.getadiacent());
}
template<class tipoelem>
bool nodogl<tipoelem>::operator==(nodogl<tipoelem> nodo)
{
bool etic = (this->getetichetta() == nodo.getetichetta());
bool val = (this->getvalore() == nodo.getvalore());
return(etic && val);
}
grafola.h
codice:
#ifndef grafolla_h
#define grafolla_h
#include<iostream>
#include<stdlib.h>
#include<assert.h>
//#include "listap.h"
#include "nodogl.h"
using namespace std;
template<class tipoelem>
class grafolla
{
public:
typedef nodogl<tipoelem> *nodo;
grafolla();
void creagrafo();
bool grafovuoto();
void insnodo(nodo);
void insarco(nodo, nodo);
void cancnodo(nodo);
void cancarco(nodo, nodo);
listap<nodog<tipoelem> > adiacenti(nodo);
bool esistenodo(nodo);
bool esistearco(nodo, nodo);
tipoelem legginodo(nodo);
void scrivinodo(nodo, tipoelem);
int leggiarco(nodo, nodo);
void scriviarco(nodo, nodo, int);
private:
nodogl<tipoelem> *nodi;
int numnodi;
};
#endif
template<class tipoelem>
grafolla<tipoelem>::grafolla()
{
this->creagrafo();
}
template<class tipoelem>
void grafolla<tipoelem>::creagrafo()
{
numnodi = 0;
nodi = new nodogl<tipoelem>[numnodi + 1];
}
template<class tipoelem>
bool grafolla<tipoelem>::grafovuoto()
{
return(numnodi == 0);
}
template<class tipoelem>
void grafolla<tipoelem>::insnodo(typename grafolla<tipoelem>::nodo node)
{
assert(!this->esistenodo(node));
++numnodi;
cout << "inserire l'etichetta del nodo: ";
char *c = new char[15];
cin >> c;
node->setetichetta(c);
cout << "inserire il valore del nodo: ";
tipoelem val;
cin >> val;
node->setvalore(val);
node->setadiacent(NULL);
node->setposizione(numnodi - 1);
nodogl<tipoelem> *noditmp = new nodogl<tipoelem>[numnodi];
if(numnodi > 1)
{
for(int i = 0; i < numnodi - 1; i++)
noditmp[i] = nodi[i];
}
noditmp[numnodi - 1] = *node;
nodi = noditmp;
}
template<class tipoelem>
void grafolla<tipoelem>::insarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
assert(this->esistenodo(n1) && this->esistenodo(n2) && !this->esistearco(n1, n2));
adiacente a;
a.etichetta = strcpy(a.etichetta, n2->getetichetta());
a.cursore = n2->getposizione();
listap<struct nodoad> *l = nodi[n1->getposizione()].getadiacent();
l->inslista(l->predlista(l->primolista()), a);
}
template<class tipoelem>
void grafolla<tipoelem>::cancnodo(typename grafolla<tipoelem>::nodo node)
{
assert(this->esistenodo(node));
//eliminazione degli archi (adiacenze) uscenti
bool trovato = false;
int i = 0;
while(!trovato)
{
if(nodi[i].etichetta == node.etichetta)
{
listap<struct nodoad> *l = nodi[i].adiacent;
while(!l->listavuota())
l->canclista(l->primolista());
trovato = true;
}
else
i++;
}
//eliminazione degli archi (adiacenze) entranti
for(int k = 0; k < numnodi; k++)
{
if(this->esistearco(nodi[k], node))
this->cancarco(nodi[k], node);
else
k++;
}
//modifica del vettore dei nodi
nodo *noditmp = new struct Nodo[numnodi - 1];
int j;
for(j = 0; j < i; j++)
noditmp[j] = nodi[j];
j = i + 1;
for(j = i + 1; j < (numnodi - 1); j++)
{
noditmp[j - 1] = nodi[j];
noditmp[j - 1].posizione -= 1;
}
nodi = noditmp;
numnodi -= 1;
}
template<class tipoelem>
void grafolla<tipoelem>::cancarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
assert(this->esistenodo(n1) && this->esistenodo(n2) && this->esistearco(n1, n2));
listap<struct nodoad> *l = nodi[n1.posizione].adiacent;
typename listap<struct nodoad>::posizione p = l->primolista();
bool trovato = false;
while(!trovato && (p != l->predlista(l->primolista())))
{
if(l->leggilista(p).etichetta == n2.etichetta)
{
l->canclista(p);
trovato = true;
}
else
p = l->suclista(p);
}
}
template<class tipoelem>
listap<nodog<tipoelem> > grafolla<tipoelem>::adiacenti(typename grafolla<tipoelem>::nodo node)
{
assert(this->esistenodo(node));
listap<struct Nodo> lis;
if(nodi[node.posizione].adiacent != NULL)
{
listap<nodoad> l = *nodi[node.posizione].adiacent;
typename listap<nodoad>::posizione p = l.primolista();
while(p != l.predlista(l.primolista()))
{
lis.inslista(lis.predlista(lis.primolista()), nodi[l.leggilista(p).cursore]);
p = l.suclista(p);
}
}
return lis;
}
template<class tipoelem>
bool grafolla<tipoelem>::esistenodo(typename grafolla<tipoelem>::nodo node)
{
bool esito = false;
int i = 0;
while(!esito && (i < numnodi))
{
if((nodi[i].etichetta == node.etichetta))
esito = true;
else
i++;
}
return esito;
}
template<class tipoelem>
bool grafolla<tipoelem>::esistearco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
assert(this->esistenodo(n1) && this->esistenodo(n2));
listap<nodoad> *l = nodi[n1.posizione].adiacent;
typename listap<nodoad>::posizione p = l->primolista();
bool trovato = true;
while(!trovato && (p != l->predlista(l->primolista())))
{
if(l->leggilista(p).etichetta == nodi[n2.posizione].etichetta)
trovato = true;
else
p = l->suclista(p);
}
return trovato;
}
template<class tipoelem>
tipoelem grafolla<tipoelem>::legginodo(typename grafolla<tipoelem>::nodo node)
{
assert(this->esistenodo(node));
return(nodi[node->getposizione()].getvalore());
}
template<class tipoelem>
void grafolla<tipoelem>::scrivinodo(typename grafolla<tipoelem>::nodo node, tipoelem elem)
{
cout << "node.posizione = " << node->getposizione() << "\n\n";
cout << "node.etichetta = " << node->getetichetta() << "\n\n";
cout << "nodi[node.posizione].etichetta = " << nodi[node->getposizione()].getetichetta() << "\n\n";
assert(this->esistenodo(node));
nodi[node->getposizione()].setvalore(elem);
}
template<class tipoelem>
int grafolla<tipoelem>::leggiarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2)
{
assert(this->esistearco(n1, n2));
listap<nodoad> *l = nodi[n1.posizione].adiacent;
typename listap<nodoad>::posizione p = l->primolista();
bool trovato = false;
while(!trovato && (p != l->predlista(l->primolista())))
{
if(l->leggilista(p).etichetta == n2.etichetta)
trovato = true;
else
p = l->suclista(p);
}
return(l->leggilista(p).peso);
}
template<class tipoelem>
void grafolla<tipoelem>::scriviarco(typename grafolla<tipoelem>::nodo n1, typename grafolla<tipoelem>::nodo n2, int pes)
{
assert(!this->esistearco(n1, n2));
listap<nodoad> *l = nodi[n1.posizione].adiacent;
typename listap<nodoad>::posizione p = l->primolista();
bool trovato = false;
while(!trovato && (p != l->predlista(l->primolista())))
{
if(l->leggilista(p).etichetta == n2.etichetta)
{
nodoad n = l->leggilista(p);
n.peso = pes;
l->scrivilista(p, n);
trovato = true;
}
else
p = l->suclista(p);
}
}
testgrafo.cpp
codice:
#include<iostream>
#include<stdlib.h>
//#include"grafoma.h"
#include"grafolla.h"
using namespace std;
int main()
{
grafolla<int> G;
cout << "grafovuoto() = " << G.grafovuoto() << "\n\n";
grafolla<int>::nodo n;
G.insnodo(n);
grafolla<int>::nodo n2;
G.insnodo(n2);
G.scrivinodo(n, 10);
cout << "legginodo(n) = " << G.legginodo(n) << "\n\n";
G.insarco(n, n2);
system("pause");
G.scriviarco(n, n2, 20);
cout << "leggiarco(n, n2) = " << G.leggiarco(n, n2) << "\n\n";
listap<nodog<int> > L;
L = G.adiacenti(n);
G.cancnodo(n);
system("pause");
cout << "esistearco(n, n2) = " << G.esistearco(n, n2) << "\n\n";
L = G.adiacenti(n);
listap<nodog<int> >::posizione p = L.primolista();
cout << "esistenodo(n2) = " << G.esistenodo(n2) << "\n\n";
cout << "esistenodo(n) = " << G.esistenodo(n) << "\n\n";
system("pause");
return 0;
}
quando compilo il tutto questa mi dà errore nella classe nodogl, dicendo che il prototipo del metodo getadiacent() non corrisponde a nessun metodo nella classe. ecco l'errore:
96 C:\Dev-Cpp\Strutture\Grafi\nodogl.h prototype for `listap<nodoad<tipoelem> >* nodogl<tipoelem>::getadiacent()' does not match any in class `nodogl<tipoelem>'
perchè? ho controllato varie volte e la segnatura del metodo corrisponde al prototipo.