PDA

Visualizza la versione completa : [C++] Grafo con lista di adiacenze


pietrol83
22-05-2012, 16:58
ciao a tutti, ho implementato la struttura dati grafo con la lista delle adiacenze. nel metodo insarco c' un'istruzione che d errore. posto il codice del metodo:

grafola.h


#ifndef grafolla_h
#define grafolla_h

#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include"listap.h"

using namespace std;

template<class tipoelem>
class grafolla
{
public:
typedef struct nodoad
{
char etichetta[15];
int cursore;
int peso;
} adiacente;

typedef struct Nodo
{
char etichetta[15];
int posizione;
tipoelem valore;
listap<struct nodoad> *adiacent;
} nodo;

grafolla();

void creagrafo();
bool grafovuoto();
void insnodo(nodo);
void insarco(nodo, nodo);
void cancnodo(nodo);
void cancarco(nodo, nodo);
listap<struct Nodo> 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:
nodo *nodi;
int numnodi;
};

#endif

template<class tipoelem>
grafolla<tipoelem>::grafolla()
{
this->creagrafo();
}

template<class tipoelem>
void grafolla<tipoelem>::creagrafo()
{
nodi = NULL;
numnodi = 0;
}

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++;
nodo *noditmp = new struct Nodo[numnodi];
if(numnodi > 1)
{
for(int i = 0; i < numnodi - 1; i++)
noditmp[i] = nodi[i];
delete[] nodi;
}
cout << "inserire l'etichetta del nodo: ";
cin >> node.etichetta;
cout << "inserire il valore del nodo: ";

cin >> node.valore;
node.adiacent = NULL;
node.posizione = numnodi - 1;
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 = n2.etichetta;
a.cursore = n2.posizione;
listap<struct nodoad> *l = nodi[n1.posizione].adiacent;
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<typename grafolla<tipoelem>::nodo> 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.posizione].valore);
}

template<class tipoelem>
void grafolla<tipoelem>::scrivinodo(typename grafolla<tipoelem>::nodo node, tipoelem elem)
{
assert(this->esistenodo(node));

nodi[node.posizione].valore = 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);
}
}


l'errore che mi viene visualizzato il seguente:

101 C:\Dev-Cpp\Strutture\Grafi\grafolla.h ISO C++ forbids assignment of arrays

perch??? da quando in qua proibito fare un assegnamento in un campo di un record??

oregon
22-05-2012, 17:05
Abbi pazienza ... qual la linea a cui ti riferisci ? Indicala sempre quando c' un errore ...

pietrol83
22-05-2012, 17:10
certo che l'ho indicata!! quella in rosso. :-)

oregon
22-05-2012, 17:15
Ah ... non si vedeva facilmente ... (se solo l'avessi detto ... )

In ogni caso, mi sembra ovvio ... da quando in C (neanche in C++) un array lo assegni in quel modo ad un altro?

Se parliamo di una stringa di 15 char, come saprai, devi usare la funzione

strcpy

pietrol83
24-05-2012, 14:55
ho cambiato la realizzazione implementando per i nodi un'apposita classe. ecco i codici:
nodogl.h

#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

#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

#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.

oregon
24-05-2012, 14:56
Ma scusa, questo un altro quesito ... che fine ha fatto quello precedente?

Hai usato la strcpy o no?

Cos si fa confusione ...

pietrol83
24-05-2012, 15:12
ho scritto sempre qui per non creare un alro questio sempre sul grafo con lista di adiacenza.
in pratice chome se stessi facendo tutto d'accapo, quindi non sono ancora arrivato alla strcpy perch sono fermo su quell'errore di compilazione che non mi fa andare avanti e non riesco a spiegarmi perch dato che il metoto e il prototipo corrispondono.

pietrol83
24-05-2012, 15:30
vi prego aiutatemi!!!

LeleFT
24-05-2012, 15:57
Se l'argomento principale della discussione cambiato, si apre una nuova discussione; a maggior ragione se il codice sul quale si sta lavorando non pi quello preso in esame finora.

Il fatto di aver dato alla discussione un titolo "pi generico" del contenuto stesso della discussione, non esime da quanto detto sopra, anzi, un motivo in pi per rendersi conto che il titolo usato non era adeguato.

Tutto questo nello spirito di voler mantenere un ordine logico delle discussioni all'interno del forum, in modo da agevolare anche gli altri utenti, non solo nel seguire una discussione, ma anche nella ricerca della stessa per eventuali soluzioni o spunti.

Detto questo, visto che il codice sul quale stai lavorando completamente diverso, apri una nuova discussione (con un titolo pi preciso).

Ciao. :ciauz:

Loading