I have a segmentation fault problem occurring at the very end of my program. Everything works as expected except for the sole error message. And the one appears only if I choose the second option from my menu (see menu.cpp below) which calls for one graph class method (see in Graf.cpp - "odszukaj_dfs"). After completing all tasks it exits with an above mentioned error. This means my error occurs only if during my session I use this method, hoverer just after I safely exit my session through menu option #4, regardless of what has been done in between (which menu options invoked) those two calls.
I would appreciate for any hint on what is wrong. Please let me know if you need more pieces of my code to solve it, I didn't post all of it in order not to make my post too bloated. Secondly, forgive for not using English in my code - the project is for my University and I had to stick to my native tongue. Thank you in advance.
As to what the program itself is to do - it is to read a graph from a file and be able to perform a depth-first search on it. The problem occurs while doing the latter.
//main.cpp
#include <iostream>
#include "wczytywanie_grafu/wczytaj_nazwe_pliku.h"
#include "wczytywanie_grafu/wczytaj_graf.h"
#include "menu/menu.h"
#include "graf_struktura/Graf.h"
int main( int argc, char *argv[] )
{
using namespace std;
const char* npliku = wczytaj_nazwe_pliku( argc, argv );
if( npliku != 0 )
{
Graf *g = poprosze_graf(npliku);
while( menu(*g) );
delete g;
}
cout << "Do widzenia.\n";
return 0;
}
Here is where the problem occurs:
//menu.cpp
#include "menu.h"
#include <iostream>
//wyswietla menu dostepnych operacji na poprawnie wczytanym grafie.
bool menu(Graf &g)
{
using namespace std;
int i;
char *token;
cout << endl;
cout << "Jaka operacje wykonac na wczytanym grafie?\n";
cout << endl;
cout << "1) Wyswietlic schemat.\n";
cout << "2) Wyszukac wierzcholek metoda DFS.\n";
cout << "3) Wczytac inny graf.\n";
cout << "4) Opuscic program.\n";
cout << endl;
cout << "Prosze o wybor jednej z powyzszych opcji. ";
while( !(cin >> i) || i < 1 || i > 4 )
{
cin.clear();
cin.ignore(1000, '\n');
cout << "\nBlad. Prosze podac desygnujaca odpowiedz liczbe z podanego zakresu. ";
}
cout << endl;
switch( i )
{
case 1 :
g.wyswietl();
break;
case 2 :
cout << "Prosze podac nazwe szukanego wierzcholka. ";
cin >> token;
cout << "Odwiedzone wierzcholki: ";
if( g.odszukaj_dfs(token) == 0 )
cout << "\nNie odnaleziono wierzcholka " << token << ".\n";
else
cout << "\nOdnaleziono wierzcholek " << token << ".\n";
break;
// case 3 :
//
// break;
case 4 :
return false;
}
return true;
}
Here are the graph definitions ("Graf" is for graph and "Wierzcholek" for its node)
//Graf.cpp
#include "Graf.h"
#include "../lifo/TabDyn.h"
#include "../lifo/Stos.h"
#include <cstring>
/*###########################################################*/
/*####################### WIERZCHOLEK #######################*/
/*###########################################################*/
/*konstruktory*/
Wierzcholek::Wierzcholek(void)
{
sasiedztwo = -1;
nastepny = poprzedni = 0;
sasiedzi = new Wierzcholek* [1*sizeof(Wierzcholek*)];
}
Wierzcholek::Wierzcholek(char* k)
{
klucz = k;
//wierzcholek izolowany grafu.
sasiedztwo = 0;
nastepny = poprzedni = 0;
sasiedzi = new Wierzcholek* [1*sizeof(Wierzcholek*)];
}
Wierzcholek::Wierzcholek(char* k, int s)
{
klucz = k; sasiedztwo = s;
nastepny = poprzedni = 0;
//przygotowanie tablicy sasiadow o stosownym rozmiarze
sasiedzi = new Wierzcholek* [s*sizeof(Wierzcholek*)];
}
Wierzcholek::Wierzcholek(char* k, int s, Wierzcholek** &n)
{
//typowy wierzcholek grafu.
klucz = k; sasiedztwo = s; sasiedzi = n;
nastepny = poprzedni = 0;
}
Wierzcholek::Wierzcholek(char* k, int s, Wierzcholek** &n, Wierzcholek* &nast , Wierzcholek* &poprz)
{
//typowy wierzcholek grafu.
klucz = k; sasiedztwo = s; sasiedzi = n;
nastepny = nast; poprzedni = poprz;
}
/*przeciazenia i metody*/
//relacja rownowaznosci obiektow oparta na identycznosci kluczy
bool Wierzcholek::operator==(Wierzcholek const &prawy) const
{
if ( klucz == prawy.klucz )
return true;
else
return false;
}
void Wierzcholek::okresl_ilosc_sasiadow(int n)
{
delete [] sasiedzi;
sasiedzi = new Wierzcholek* [n*sizeof(Wierzcholek)];
sasiedztwo = n;
}
/*###########################################################*/
/*########################### GRAF ##########################*/
/*###########################################################*/
/*konstruktor*/
Graf::Graf(void)
{
pierwszy = ostatni = 0;
rozmiar = 0;
}
/*metody*/
void Graf::dodaj(Wierzcholek* w)
{
if ( pierwszy != 0 )
{
w->poprzedni = ostatni;
ostatni = w;
ostatni->poprzedni->nastepny = ostatni;
}
else
pierwszy = ostatni = w;
ostatni->pozycja = rozmiar++;
}
void Graf::wyswietl(void)
{
using namespace std;
Wierzcholek *n = pierwszy;
for( int j=0; j < rozmiar; n = n->nastepny)
{
cout << n->klucz << " :";
for( int i=0; i < n->sasiedztwo; i++ )
cout << " " << n->sasiedzi[i]->klucz;
cout << " ;\n";
j++;
}
return;
}
int Graf::podaj_rozmiar(void)
{
return rozmiar;
}
Wierzcholek* Graf::odszukaj_dfs(char* &klucz)
{
using namespace std;
//tablica przyporzadkowujaca kazdemu kolejnemu wierzcholkowi grafu
//binarna wartosc oznaczajaca fakt odwiedzenia wierzcholka przez algorytm.
TabDyn<bool> odwiedzony;
for(int i=0; i < rozmiar; i++)
odwiedzony.dodaj(0);
//stos wierzcholkow sasiadujacych z juz odwiedzonymi wierzcholkami.
Stos< Wierzcholek* > stos;
//wierzcholek zdjety ze stosu.
Wierzcholek* biezacy = pierwszy;
//kolejny wierzcholek ciagu wierzcholkow grafu,
//uwzgledniony, aby nie pominac wierzcholkow izolowanych.
Wierzcholek* numerowany = pierwszy;
//zmienna pomocnicza stworzona dla przejrzystosci kodu
//wierzcholek sasiadujacy z biezacym
//dokladany na stos, jezeli nie zostal jeszcze odwiedzony.
Wierzcholek* sasiad = 0;
//elementow grafu jest dokladnie "rozmiar".
for( int i=0; i < rozmiar; i++, numerowany=numerowany->nastepny )
{
cout << "plus: " << numerowany->klucz << endl;
if( odwiedzony[numerowany->pozycja] )
continue;
stos.doloz( numerowany );
while( !stos.jest_pusty() )
{
biezacy = stos.zdejmij();
if ( odwiedzony[biezacy->pozycja] )
continue;
else
odwiedzony[biezacy->pozycja] = true;
if( strcmp(biezacy->klucz, klucz) == 0 )
{
cout << endl;
return biezacy;
}
//sasiadow jest dokladnie "sasiedztwo".
for( int j=0; j < biezacy->sasiedztwo; j++)
{
sasiad = biezacy->sasiedzi[j];
if( !odwiedzony[sasiad->pozycja] )
stos.doloz(sasiad);
}
}
}
cout << endl;
return 0;
}
Here are the files for Stack (here as "Stos") and Dynamically Allocated Table (here as "TabDyn")
#ifndef STOS_H
#define STOS_H
template<typename T> class TabDyn;
template<typename T>
class Stos
{
private:
/*pola*/
TabDyn<T>* pula;
public:
/*konstruktory*/
Stos(void);
Stos(int);
~Stos(void);
/*metody*/
void wyczysc(void);
bool jest_pusty(void) const;
T& top(void);
T zdejmij(void);
void doloz(const T&);
};
#include "Stos.tcc"
#endif
//Stos.tcc
#ifndef STOS_TCC
#define STOS_TCC
#include "TabDyn.h"
template<typename T>
Stos<T>::Stos(void)
{
pula = new TabDyn<T>;
}
template<typename T>
Stos<T>::Stos(int rozmiar)
{
pula = new TabDyn<T>(rozmiar);
}
template<typename T>
Stos<T>::~Stos(void)
{
delete pula;
}
template<typename T>
void Stos<T>::wyczysc(void)
{
pula->wyczysc();
}
template<typename T>
bool Stos<T>::jest_pusty(void) const
{
return pula->jest_pusty();
}
template<typename T>
T& Stos<T>::top(void)
{
return pula->koniec();
}
template<typename T>
T Stos<T>::zdejmij(void)
{
//nalezy uprzednio sprawdzic czy stos nie jest pusty!
T el = pula->koniec();
pula->usun();
return el;
}
template<typename T>
void Stos<T>::doloz(const T& el)
{
pula->dodaj( el );
}
#endif
//TabDyn.h
#ifndef TABDYN_H
#define TABDYN_H
using namespace std;
int const STD_ROZMIAR = 50;
/*###########################################################*/
template<typename T>
class TabDyn
{
private:
/*pola*/
int max_rozmiar;
int akt_rozmiar;
T *przydzial_pamieci;
public:
/*metody*/
TabDyn(int rozmiar = STD_ROZMIAR);
T& operator[](int i);
//usuwa stary przydzial pamieci i nadaje nowy
bool zarezerwuj(int);
//chyba: wyjebac stary przydzial i przydzielic nowy
void wyczysc(void);
//sprawdzic akt_rozmiar
bool jest_pusty(void);
//wskaznik na poczatek plus akt_rozmiar
T& koniec(void);
bool usun(void); //!!! pop_back
// void doloz_nkoniec( const T& ); //!!! push_back
void dodaj( const T& ); //!!! push_back
};
#include "TabDyn.tcc"
#endif
//TabDyn.tcc
#ifndef TABDYN_TPP
#define TABDYN_TPP
#include <iostream>
/*###########################################################*/
template<typename T>
TabDyn<T>::TabDyn(int rozmiar)
{
przydzial_pamieci = new T [rozmiar*sizeof(T)];
max_rozmiar = rozmiar;
akt_rozmiar = 0;
}
template<typename T>
T& TabDyn<T>::operator[](int i)
{
if( i >= 0 && i < akt_rozmiar )
{
return *(przydzial_pamieci + i);
}
cout << "Blad: Zarzadano wartosci tablicy dynamicznej spoza zakresu. Podano wartosc ostatniego elementu.\n";
return *(przydzial_pamieci + akt_rozmiar);
}
template<typename T>
bool TabDyn<T>::zarezerwuj(int wolumen)
{
if ( max_rozmiar == wolumen )
return true;
if ( wolumen < akt_rozmiar )
{
cout << "Blad: Nowy zadany rozmiar tablicy dynamicznej nie jest w stanie pomiescic elementow, ktore juz sie w niej znajduja. Odmowa wykonania operacji. " << endl;
return false;
}
T *npamiec = new T [wolumen*sizeof(T)];
if ( ! jest_pusty() )
{
for( int i=0; i < akt_rozmiar; i++ )
{
*(npamiec + i) = *(przydzial_pamieci + i);
}
}
max_rozmiar = wolumen;
delete [] przydzial_pamieci;
przydzial_pamieci = npamiec;
return true;
}
template<typename T>
void TabDyn<T>::wyczysc(void)
{
delete [] przydzial_pamieci;
przydzial_pamieci = new T [max_rozmiar*sizeof(T)];
}
template<typename T>
bool TabDyn<T>::jest_pusty(void)
{
return !akt_rozmiar;
}
//zwraca ostatni element tablicy
template<typename T>
T& TabDyn<T>::koniec(void)
{
T& ans = *(przydzial_pamieci + akt_rozmiar - 1);
if( !akt_rozmiar )
std::cout << "Blad, stos jest pusty.\n";
return ans;
}
//usuwa ostatni element tablicy
template<typename T>
bool TabDyn<T>::usun(void)
{
if ( akt_rozmiar == 0 )
{
std::cout << "Blad: Nie mam co usunac.\n";
return false;
}
akt_rozmiar--;
return true;
}
//dodaje ostatni element tablicy
template<typename T>
void TabDyn<T>::dodaj( const T& el )
{
if ( akt_rozmiar + 1 > max_rozmiar )
{
cout << "Uwaga: przekroczono rozmiar tablicy dynamicznej. Zostanie przydzielona nowa wielkosc." << endl;
zarezerwuj(max_rozmiar+1);
}
*(przydzial_pamieci + akt_rozmiar++) = el;
}
#endif