Segmentation fault – C / C++ – Fórum – Programujte.com

Zdravim, nevite prosim, co v tomto kodu by mohlo zpusobovat segmantation fault? Jedna se o hledani Eulerovske cesty v grafu. S jednoduchymi daty to funguje, ale kdyz se nad tim pusti obrovska testovaci data (mne neznama), tak to vyhodi segfault. Nevim jak mam odhalit zdroj, kdyz nevim cim presne to otestovat, zkousel jsem vsechny "specialni" varianty zadani, ktere me napadly... Diky moc. 

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

class Node {
  int id;
  int in;
  int out;
  vector<int> succ;
  public:
    Node();
    Node(int i);
    int getId();
    vector<int> getSuccs();
    void addSucc(int successor);
    void updateSucc(int successor, int index);
    void delSucc(int i);
    void increaseIn();
    void decreaseIn();
    void increaseOut();
    void decreaseOut();
    int getIn();
    int getOut();
};

Node::Node(void){
  id=-1;
  in=0;
  out=0;
}

Node::Node(int i){
  id=i;  
  in=0;
  out=0;             
}

int Node::getId(){
  return id;
}

vector<int> Node::getSuccs(){
  return succ;
}

void Node::addSucc(int successor){
  succ.push_back(successor);     
}

void Node::updateSucc(int successor, int index){
  succ[index]=successor;     
}

void Node::delSucc(int i){
  succ.erase(succ.begin()+i);     
}

void Node::increaseIn(){
  in++;     
}

void Node::increaseOut(){
  out++;     
}

void Node::decreaseIn(){
  in--;     
}

void Node::decreaseOut(){
  out--;     
}

int Node::getIn(){
  return in;
}

int Node::getOut(){
  return out;
}

vector< pair<int,int> > rout;
int M;
int N;

int endNode=-1;
int endOut=0;
int nextNode=-1;

void alg(Node nodes[],int start){
  if(nodes[start].getSuccs().size() > 0 && M>0 && start>=0 && start<N){
	  int lastIndex=nodes[start].getSuccs().size()-1;
	  int successor=nodes[start].getSuccs()[0];
	  if(successor==endNode && endOut==0 && M!=1){
		int temp=successor;
		nodes[start].updateSucc(nodes[start].getSuccs()[lastIndex],0);
		nodes[start].updateSucc(temp,(lastIndex));
	    successor=nodes[start].getSuccs()[0];                                         
	  }
	  if(successor==endNode) endOut--;
	  rout.push_back(make_pair(start,successor));
	  M--;
	  nextNode=successor;
	  if(M>0 && nextNode<N && nextNode>=0){
		  nodes[start].delSucc(0);
		  alg(nodes,nextNode);
	  }
  }
}

int main(int argc, char *argv[])
{    
    cin >> N;
    Node *nodes=new Node[N];
    for(int i=0;i<N;i++) nodes[i]=Node(i);


    int first=0;
    int second=0;
    for(;;){
      cin >> first;
      cin >> second;
      if(first==0 && second==0) break;
      nodes[first].addSucc(second);
      nodes[first].increaseOut();
      nodes[second].increaseIn();
      M++;        
    }
    int tempM=M;
    int start=-1;
    
    bool eulerCheck=true;
    for(int i=0;i<N;i++){
      if(nodes[i].getIn()>nodes[i].getOut() && endNode!=-1){
        eulerCheck=false; 
        break;
      }
      if(nodes[i].getIn()<nodes[i].getOut() && start!=-1){
        eulerCheck=false; 
        break;
      }
      if(nodes[i].getIn()>nodes[i].getOut()) { endNode=i; endOut=nodes[i].getOut(); }
      else if(nodes[i].getIn()<nodes[i].getOut()) start=i;      
    }
    if(start==-1 || endNode==-1) { start=0; endNode=1; endOut=nodes[1].getOut(); }    
    
    if(eulerCheck==true){
       alg(nodes,start);                  
    }
    
    if(eulerCheck==false) cout << "-1";
    else {
      cout << N << endl;   
      for(unsigned int i=0;i<rout.size();i++) cout << rout[i].first << " " << rout[i].second << endl; 
      cout << "0 0";
    }
}

#1 Gadael
Skús použiť valgrind.

#2 vitamin
Programuju to na Windows bohužel, pokud vím, tak valgrind je pouze pro linux.

#3 Gadael
tak skus: http://www.drmemory.org/ alebo si sprav virtualku s linuxom :)

#4 vitamin
A ukaze mi cokoliv z toho (valgrind, mr.memory,...) pouze segfault hrozby? Protoze ja nemam k dispozici vstupni data, ktera tu segfault zpusobi, mam pouze takova, u kterych program probehne v poradku.

urcite neuvolnujes pamet po tech nodech, nekontrolujes vubec rozsah pri vkladan do nodu a tak

#6 KIIV
"Neuvolnuju pamet po nodech" - tzn. ze po skonceni algoritmu mam smazat to pole? Nebo nejak prubezne?

"Nekontroluju rozsah pri vkladani do nodu" - tomu nerozumim, muzes prosim upresnit?

Diky moc

kdyz udelas   pole = new Node[4]; a  pak udelas  pole[4].add(...) tak uz zapisujes mimo svoji pamet 

#8 KIIV
opravil jsem to ("if(first>=N || first<0 || second>=N || second<0) => invalid input")

bohužel segfault to stále vyhazuje, nic jiného tam nevidíš? Díky

#9 Gadael
 

Node *nodes=new Node[N];

Zde bych ještě kontroloval, zda alokace neselže, víc než KIIV tam toho na první pohled nevidím.

#10 voty
Jo a taky by se hodila kontrola vstupu, zda N není rovno 0, na to by asi taky padlo.

pak uz jen dodej ty parametry co tomu hazes a pada ti to.. neni problem to projet valgrindem

#12 KIIV 

Tady je posledni verze, opravdu nevim v cem je problem.. Pokud bys to mohl prohnat valgrindem, tak super. Nevim jak presne to funguje - umi to odhalit segfaulty i s datama, pri kterych nevzniknou? Umi to proste nejak identifikovat misto "kde by se to mohlo pokazit kdyby xyz bylo tato hodnota"?

Vstupní data mohou byt ruzna a ruzne slozita. Prvni cislo je vzdy pocet uzlu grafu. Kazda dalsi dvojice cisel oznacuje hrany mezi uzly (0 az N). Cele je to zakoncene dvema nulama. Nejjdenodussi je treba toto (3-uzly orientovana kruznice: 2-1,1-0,0-2):

3

2

1

1

0

0

2

0

0

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

class Node {
  int id;
  int in;
  int out;
  vector<int> succ;
  public:
    Node();
    Node(int i);
    int getId();
    vector<int> getSuccs();
    void addSucc(int successor);
    void updateSucc(int successor, int index);
    void delSucc(int i);
    void increaseIn();
    void decreaseIn();
    void increaseOut();
    void decreaseOut();
    int getIn();
    int getOut();
};

Node::Node(void){
  id=-1;
  in=0;
  out=0;
}

Node::Node(int i){
  id=i;  
  in=0;
  out=0;             
}

int Node::getId(){
  return id;
}

vector<int> Node::getSuccs(){
  return succ;
}

void Node::addSucc(int successor){
  succ.push_back(successor);     
}

void Node::updateSucc(int successor, int index){
  succ[index]=successor;     
}

void Node::delSucc(int i){
  succ.erase(succ.begin()+i);     
}

void Node::increaseIn(){
  in++;     
}

void Node::increaseOut(){
  out++;     
}

void Node::decreaseIn(){
  in--;     
}

void Node::decreaseOut(){
  out--;     
}

int Node::getIn(){
  return in;
}

int Node::getOut(){
  return out;
}

vector< pair<int,int> > rout;
int M;
int N;

int endNode=-1;
int endOut=0;
int nextNode=-1;

void alg(Node nodes[],int start){
  if(nodes[start].getSuccs().size() > 0 && M>0 && start>=0 && start<N){
	  int lastIndex=nodes[start].getSuccs().size()-1;
	  int successor=nodes[start].getSuccs()[0];
	  if(successor==endNode && endOut==0 && M!=1){
		int temp=successor;
		nodes[start].updateSucc(nodes[start].getSuccs()[lastIndex],0);
		nodes[start].updateSucc(temp,(lastIndex));
	    successor=nodes[start].getSuccs()[0];                                         
	  }
	  if(successor==endNode) endOut--;
	  rout.push_back(make_pair(start,successor));
	  M--;
	  nextNode=successor;
	  if(M>0 && nextNode<N && nextNode>=0){
		  if(nodes[start].getSuccs().size()>0) nodes[start].delSucc(0);
		  alg(nodes,nextNode);
	  }
  }
}

int main(int argc, char *argv[])
{    
    cin >> N;
    Node *nodes=new Node[N];
    for(int i=0;i<N;i++) nodes[i]=Node(i);

	bool invalidInput=false;
    int first=0;
    int second=0;
    for(;;){
      cin >> first;
      cin >> second;
	  if(first>=N || first<0 || second>=N || second<0) { invalidInput=true; break; }
      if(first==0 && second==0) break;
      nodes[first].addSucc(second);
      nodes[first].increaseOut();
      nodes[second].increaseIn();
      M++;        
    }
    int tempM=M;
    int start=-1;
    
    bool eulerCheck=true;
    for(int i=0;i<N;i++){
	  if(nodes[i].getIn()==0 && nodes[i].getOut()==0 && N!=1){
		eulerCheck=false;
		break;
 	  }
      if(nodes[i].getIn()>nodes[i].getOut() && endNode!=-1){
        eulerCheck=false; 
        break;
      }
      if(nodes[i].getIn()<nodes[i].getOut() && start!=-1){
        eulerCheck=false; 
        break;
      }
      if(nodes[i].getIn()>nodes[i].getOut()) { endNode=i; endOut=nodes[i].getOut(); }
      else if(nodes[i].getIn()<nodes[i].getOut()) start=i;      
    }
    if(start==-1 || endNode==-1) { start=0; endNode=0; endOut=nodes[0].getOut(); }    
    
    if(eulerCheck==true && invalidInput==false){
       alg(nodes,start);                  
    }

	delete [] nodes;
    
    if(eulerCheck==false || invalidInput==true) cout << "-1";
    else {
      cout << N << endl;   
      for(unsigned int i=0;i<rout.size();i++) cout << rout[i].first << " " << rout[i].second << endl; 
      cout << "0 0";
    }
}

s tim cos poslal a posledni verzi to vcelku i funguje... pokud se ceka jen vypsat zadani...

valgrind hlida veskere cteni/zapisy do pameti - pozna kdyz se zapisuje mimo alokovanou pamet (ale samozrejme nepozna kdyz zapisujes do alokovany pameti tim ze ti pretece pole a tak)