Segmentation fault – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Gadael0
Návštěvník
17. 10. 2013   #1
-
0
-

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";
    }
}
Nahlásit jako SPAM
IP: 193.86.229.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
Reklama
Reklama
vitamin+8
Grafoman
17. 10. 2013   #2
-
0
-

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

Nahlásit jako SPAM
IP: 195.28.77.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Gadael0
Návštěvník
17. 10. 2013   #3
-
0
-

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

Nahlásit jako SPAM
IP: 193.86.229.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
vitamin+8
Grafoman
17. 10. 2013   #4
-
0
-

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

Nahlásit jako SPAM
IP: 195.28.77.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Gadael0
Návštěvník
17. 10. 2013   #5
-
0
-

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

Nahlásit jako SPAM
IP: 193.86.229.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
KIIV+42
God of flame
17. 10. 2013   #6
-
0
-

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Gadael0
Návštěvník
17. 10. 2013   #7
-
0
-

#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

Nahlásit jako SPAM
IP: 193.86.229.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
KIIV+42
God of flame
17. 10. 2013   #8
-
0
-

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Gadael0
Návštěvník
17. 10. 2013   #9
-
0
-

#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

Nahlásit jako SPAM
IP: 193.86.229.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
voty+1
Návštěvník
17. 10. 2013   #10
-
0
-

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

Nahlásit jako SPAM
IP: 109.239.71.–
Jednu rozbil a tu druhou ztratil.
voty+1
Návštěvník
17. 10. 2013   #11
-
0
-

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

Nahlásit jako SPAM
IP: 109.239.71.–
Jednu rozbil a tu druhou ztratil.
KIIV+42
God of flame
17. 10. 2013   #12
-
0
-

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Gadael0
Návštěvník
17. 10. 2013   #13
-
0
-

#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";
    }
}
Nahlásit jako SPAM
IP: 89.176.80.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
KIIV+42
God of flame
18. 10. 2013   #14
-
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)

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 72 hostů

Podobná vlákna

Ld - segmentation fault — založil Zelenáč

Segmentation fault 11 — založil Tomas678

Qt setlayout segmentation fault — založil rodinne.baleni.ryze

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý