C++ grafo con matrice di adiacenza (diverso da quello esistente)

[pietrol83]

ciao a tutti, considerati gli inspiegabili problemi che ho avuto con l'implementazione del grafo nel forum precedente, ho deciso di fare una nuova realizzazione, solo che testando il metodo insnodo va in crash all'instruzione inslista(...).

posto i codici:

nodop.h

#ifndef nodop_h
#define nodop_h

#include<iostream>
#include<stdlib.h>

using namespace std;

template<class tipoelem>
class nodop
{
   public:
      nodop();
      
      void setprec(nodop *);
      void setelem(tipoelem);
      void setsuc(nodop *);
      
      nodop *getprec();
      tipoelem getelem();
      nodop *getsuc();
   private:
      nodop *precedente;
      tipoelem elemento;
      nodop *successivo;
};
#endif

template<class tipoelem>
nodop<tipoelem>::nodop()
{
   precedente = NULL;
   successivo = NULL;
}

template<class tipoelem>
void nodop<tipoelem>::setprec(nodop *prec)
{
   precedente = prec;
}

template<class tipoelem>
void nodop<tipoelem>::setelem(tipoelem elem)
{
   elemento = elem;
}

template<class tipoelem>
void nodop<tipoelem>::setsuc(nodop *suc)
{
    successivo = suc;
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getprec()
{
   return(precedente);
}

template<class tipoelem>
tipoelem nodop<tipoelem>::getelem()
{
   return(elemento);
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getsuc()
{
   return(successivo);
}

listap.h

#ifndef listap_h
#define listap_h

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

using namespace std;

template<class tipoelem>
class listap
{
   public:
      typedef nodop<tipoelem> *posizione;

      listap();
      void crealista();
      bool listavuota();
      posizione primolista();
      bool finelista(posizione);
      posizione predlista(posizione);
      posizione suclista(posizione);
      tipoelem leggilista(posizione);
      void scrivilista(posizione, tipoelem);
      void inslista(posizione, tipoelem);
      void canclista(posizione);
      
   private:
      nodop<tipoelem> *sentinella;
};

#endif

template<class tipoelem>
listap<tipoelem>::listap()
{
   this->crealista();
}

template<class tipoelem>
void listap<tipoelem>::crealista()
{
   sentinella = new nodop<tipoelem>;
   sentinella->setprec(sentinella);
   sentinella->setsuc(sentinella);
}

template<class tipoelem>
bool listap<tipoelem>::listavuota()
{
   return((sentinella->getprec() == sentinella) && (sentinella->getsuc() == sentinella));
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::primolista()
{
   return(sentinella->getsuc());
}

template<class tipoelem>
bool listap<tipoelem>::finelista(typename listap<tipoelem>::posizione pos)
{
   return(pos == sentinella);
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::predlista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getprec());
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::suclista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getsuc());
}

template<class tipoelem>
tipoelem listap<tipoelem>::leggilista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getelem());
}

template<class tipoelem>
void listap<tipoelem>::scrivilista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
   pos->setelem(elem);
}

template<class tipoelem>
void listap<tipoelem>::inslista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
   posizione temp = new(nodop<tipoelem>);
   
   temp->setprec(pos->getprec());
   temp->setsuc(pos);
   (pos->getprec())->setsuc(temp);
   pos->setprec(temp);
   temp->setelem(elem);
   pos = temp;
}

template<class tipoelem>
void listap<tipoelem>::canclista(typename listap<tipoelem>::posizione pos)
{
   posizione temp = new(nodop<tipoelem>);
   
   temp = pos;
   (pos->getprec())->setsuc(pos->getsuc());
   (pos->getsuc())->setprec(pos->getprec());
   pos = pos->getsuc();
   delete(temp);
}

nodog.h

#ifndef nodog_h
#define nodog_h

#include<iostream>
#include<stdlib.h>

using namespace std;

template<class tipoelem>
class nodog
{
   public:
      nodog();
      
      void setetichetta(char *);
      void setvalore(tipoelem);
      void setposizione(int);
      
      char *getetichetta();
      tipoelem getvalore();
      int getposizione();
      
      nodog<tipoelem> operator=(nodog<tipoelem>);
      bool operator==(nodog<tipoelem>); 
   private:
      char *etichetta;
      tipoelem valore;
      int posizione;
};

#endif

template<class tipoelem>
nodog<tipoelem>::nodog()
{
   etichetta = NULL;
   posizione = -1;
}

template<class tipoelem>
void nodog<tipoelem>::setetichetta(char *et)
{
   etichetta = et;
}

template<class tipoelem>
void nodog<tipoelem>::setvalore(tipoelem val)
{
   valore = val;
}

template<class tipoelem>
void nodog<tipoelem>::setposizione(int pos)
{
   posizione = pos;
}

template<class tipoelem>
char *nodog<tipoelem>::getetichetta()
{
   return(etichetta);
}

template<class tipoelem>
tipoelem nodog<tipoelem>::getvalore()
{
   return(valore);
}

template<class tipoelem>
int nodog<tipoelem>::getposizione()
{
   return(posizione);
}

template<class tipoelem>
nodog<tipoelem> nodog<tipoelem>::operator=(nodog<tipoelem> nodo)
{
   this->setetichetta(nodo.getetichetta());
   this->setvalore(nodo.getvalore());
   this->setposizione(nodo.getposizione());
}

template<class tipoelem>
bool nodog<tipoelem>::operator==(nodog<tipoelem> nodo)
{
   bool etic = (this->getetichetta() == nodo.getetichetta());
   bool val = (this->getvalore() == nodo.getvalore());
   bool pos = (this->getposizione() == nodo.getposizione());
   
   return(etic && val && pos);
}

grafoma.h

#ifndef grafoma_h
#define grafoma_h

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

using namespace std;

template<class tipoelem>
class grafoma
{
   public:
      typedef nodog<tipoelem> nodo;
      
      grafoma();
      void creagrafo();
      bool grafovuoto();
      void insnodo(nodo);
   private:
      int **matrice;
      int numnodi;
      listap<nodo> nodi;
};

#endif

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

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

template<class tipoelem>
bool grafoma<tipoelem>::grafovuoto()
{
   return(numnodi == 0);
}

template<class tipoelem>
void grafoma<tipoelem>::insnodo(typename grafoma<tipoelem>::nodo node)
{
   //sert(!this->esistenodo(node));
   numnodi++;
   if(nodi.listavuota())
   {
      matrice = new int *[numnodi];
      for(int i = 0; i < numnodi; i++)
         matrice[i] = new int;
   }
   else
   {
      int **mattmp = new int *[numnodi];
      for(int i = 0; i < numnodi; i++)
         mattmp[i] = new int[numnodi];
      
      for(int i = 0; i < numnodi - 1; i++)
      {
         for(int j = 0; j < numnodi - 1; j++)
            mattmp[i][j] = matrice[i][j];
      }
      for(int i = 0; i < numnodi; i++)
      {
         mattmp[i][numnodi - 1] = 0;
         mattmp[numnodi - 1][i] = 0;
      }
      matrice = mattmp;
   }
   char *etichet;
   cout << "inserire l'etichetta: ";
   cin >> etichet;
   node.setetichetta(etichet);
   tipoelem val;
   cout << "inserire il valore del nodo: ";
   cin >> val;
   node.setvalore(val);
   node.setposizione(numnodi - 1);
   nodi.inslista(nodi.predlista(nodi.primolista()), node);
}

testgrafoma.cpp

#include<iostream>
#include<stdlib.h>
#include"grafoma.h"

using namespace std;

int main()
{
   grafoma<int> G;
   
   cout << "grafovuoto() = " << G.grafovuoto() << "\n\n";
   
   nodog<int> n;
   G.insnodo(n);
   
   system("pause");
   return 0;
}

la linea di codice che va in crash è quella in rosso. ho provato a fare il debug ma non parte nemmeno quello. tutte a me succedono!!!

[pietrol83]

risolto!!!! ci ritrovaimo al prossimo problema (e sono sicuro che ce ne saranno, ahime).

[pietrol83]

come scritto nella risposta precedente, ho un nuovo problema:
ho implementato il metodo cancnodo nella lclass grafoma.h ma nel test va in crash appena arriva a un'istruzione che sembra fatta bene. questo è il codice del metodo:

metodo void cancnodo(nodo node):

template<class tipoelem>
void grafoma<tipoelem>::cancnodo(typename grafoma<tipoelem>::nodo node)
{
   //assert(this->esistenodo(node));

   //aggiornamento della matrice
   int **tmp = new int *[numnodi - 1];
   for(int i = 0; i < numnodi - 1; i++)
         tmp[i] = new int[numnodi - 1];
   for(int i = 0; i < node->getposizione(); i++)
   {
      for(int j = 0; j < node->getposizione(); j++)
         tmp[i][j] = matrice[i][j];
      for(int j = node->getposizione() + 1; j < numnodi; j++)
         tmp[i][j - 1] = matrice[i][j];
   }
   for(int i = node->getposizione() + 1; i < numnodi; i++)
   {
      for(int j = 0; j < node->getposizione(); j++)
         tmp[i][j] = matrice[i][j];
      for(int j = (node->getposizione() + 1); j < numnodi; j++)
         tmp[i - 1][j - 1] = matrice[i][j];
   }
   matrice = tmp;
  
   //eliminazione del nodo dalla lista
   bool trovato = false;
   typename listap<nodog<tipoelem> >::posizione p = nodi->primolista();
   while(!trovato)
   {
      if(nodi->leggilista(p) == *node)
      {
         nodi->canclista(p);
         trovato = true;
      }
      else
         p = nodi->suclista(p);
      system("pause");
   }
   while(p != nodi->predlista(nodi->primolista()))
   {
      nodog<tipoelem> n;
      n = nodi->leggilista(p);
      n.setposizione(n.getposizione() - 1);
      nodi->scrivilista(p, n);
      
      p = nodi->suclista(p);
   }
   cout << nodi->leggilista(nodi->primolista()).getetichetta() << " " << nodi->leggilista(nodi->primolista()).getposizione() << "\n\n";
   numnodi--;
}

in pratica il metodo crea una matrice quadrate di dimensione inferiore di 1 rispetto alla matrice di adiacenza, copia il contenuto della matrice i adiacenza tranne la riga e la colonna relative al nodo da eliminare, poi viene eliminato dalla lista dei nodi il nodo in questione. il problema è che appena si arriva all'aggiornamento della matrice, l'esecuzione va in crash all'istruzione in rosso. perchè??? eppure ho allocato lo spazio necessario!!!

[Who am I]

Il problema è qua:

tmp[i - 1][j - 1]

i-1 è fuori dagli indici validi della matrice.