[c++] wlasna klasa i brak możliwości jej inicjalizacji - DFS

braciszek · 18 Kwiecień 2012 08:51

Witam wszystkich ponownie,

mam 2 problemy z ktorymi pierwszy raz sie spotykam. Stworzylem klase. W niej 2 konstruktory, destruktor i 2 metody. Chec utworzenia nowego obiektu niestety konczy sie porazka - DFS dfs = new DFS(param1, param2). Ową klasę jestem w stanie wywolac tylko i wylacznie z pominieciem slowa new - czyli DFS dfs = DFS(param1, param2). TO jeden problem. Drugi problem jest tej natury ze dane czesciowo sa przekazywane przez wskazni, a mimo to tablica na ktorej pracuje zwraca smieci - liczbe zedu -891754 i tak dla n. Moglbym prosic o pomoc w zlokalizowaniu bledu.

Pnizej kod klasy

#ifndef DFS_H

#define	DFS_H


class DFS{

	private:

		std::stack > stos;	//stos do przechowywania wezlow w dfs'ie

		int *odwiedzony;

		int liczbaWezlow;

		int **mapaBinarnaPrzyleglosci;

		int C;


	public:

		DFS();

		DFS(int iloscWierzholkow, int **mapaBinarna);

		~DFS();

		int nextNod(int v);

		void runDFS(int v);

		int getC();

		void showStatus();

};


#endif	/* DFS_H */

DFS::DFS(){


}


DFS::DFS(int iloscWierzholkow, int **mapaBinarna){

	liczbaWezlow = iloscWierzholkow;

	mapaBinarnaPrzyleglosci = mapaBinarna;

	odwiedzony = new int[liczbaWezlow];

	C = 0;

}


DFS::~DFS(){


}

A na koniec error przy dolaczonym slowie new

nr47 · 18 Kwiecień 2012 08:57

new zwraca wskaźnik na pamięć, a w podanym kodzie próbujesz przypisać wskaźnik na DFS do zmiennej typu DFS.

Co do drugiego problemu, nie widzę kodu go dotyczącego. Tzn. alokujesz pamięć i w ‘odwiedzony’ będą śmieci początkowo, ale nie wiem czy to o tą tablicę ci chodzi.

braciszek · 18 Kwiecień 2012 09:04

Kolego nr47 - odpowiedz jeszcze raz jeśli mogę Ciebie prosić dlaczego nie moge tego kodu uruchomic za pomoca new - sory, ale jeszcze spie…

Ponizej caly kod. W celu sprawdzenia spojnosci grafu uzywam zmiennej C - jesli odwiedzony wszedzie ma 1 to graf spojny, w przeciwnym wypadku nie spojny. POnizej cala klasa

#ifndef DFS_H

#define	DFS_H


class DFS{

	private:

		std::stack > stos;	//stos do przechowywania wezlow w dfs'ie

		int *odwiedzony;

		int liczbaWezlow;

		int **mapaBinarnaPrzyleglosci;

		int C;


	public:

		DFS();

		DFS(int iloscWierzholkow, int **mapaBinarna);

		~DFS();

		int nextNod(int v);

		void runDFS(int v);

		int getC();

		void showStatus();

};


#endif	/* DFS_H */

#include 

#include 

#include 

#include 

#include "dfs.h"


DFS::DFS(){


}


DFS::DFS(int iloscWierzholkow, int **mapaBinarna){

	liczbaWezlow = iloscWierzholkow;

	mapaBinarnaPrzyleglosci = mapaBinarna;

	odwiedzony = new int[liczbaWezlow];

	for(int i = 0; i
		odwiedzony[i] = 0;

	C = 0;

}


DFS::~DFS(){


}


void DFS::showStatus(){

	for(int i = 0; i
		std::cout << odwiedzony[i] << " ";

	}

}


int DFS::getC(){

	return C;

}


void DFS::runDFS(int v){

	int u;

	int next;

	odwiedzony[v] = 1;

	next = nextNod(v);

	while(next != -1){

		stos.push(next);

		next = nextNod(v);

	}

	if(!stos.empty()){

		u = stos.top();

		stos.pop();

		runDFS(u);

	}

	bool tmp = true;

	for(int i = 0; i
		if(odwiedzony[i] = 1)

			continue;

		else{

			tmp = false;

		}

	}

	if(tmp == true)

		C = 1;

	else

		C = 0;

}


int DFS::nextNod(int v){

	int i;

	for(i=liczbaWezlow-1; i>=0; i--){

		if(mapaBinarnaPrzyleglosci[i][v] == 1 && odwiedzony[i] == 0){

			odwiedzony[i] = 1;

			return i;

		}

	}

	return -1;	//zwraca gdy wierzcholek v nie ma juz nastepnikow

}

etam · 18 Kwiecień 2012 09:12

Mam wrażenie, że wcześniej pisałeś w innym języku (java?), a teraz uczysz się c++ i niedokładnie czytasz tutoriale. Kilka przykładów użycia konstruktora:

DFS dfs; - deklaracja obiektu klasy DFS; konstruktor domyślny / bezargumentowy
DFS dfs(param1, param2); - deklaracja obiektu klasy DFS; konstruktor pasujący do przekazanych argumentów
DFS dfs = DFS(param1, param2); - zapis równoważny z 2
DFS *dfs = new DFS(); - stworzenie nowego obiektu (konstruktorem domyślnym) w pamięci na stosie i zapisanie adresu do wskaźnika dfs
DFS *dfs = new DFS(param1, param2); - domyśl się podpowiedź: to jest skrzyżowanie przykładów 2 i 4
DFS dfs(); - deklaracja funkcji zwracającej obiekt klasy DFS

Ponownie odsyłam cię do tutorala o klasach: http://cplusplus.com/doc/tutorial/classes/

Przy okazji: zaprzyjaźnij się z “initializer list”: http://en.cppreference.com/w/cpp/langua … lizer_list

(ciąg dalszy nastąpi)

braciszek · 18 Kwiecień 2012 09:18

Zgadłeś etam. Ale też nie do końca, w c/c++ pisałem 5 -7 lat temu. Potem siadlem na jave i tak sie zaczelo. Teraz jest chwilowa potrzeba wykonania aplikacji ktora moge wykonac z poziomu php i usiadlem znowu do C. Moze to brzydko za brzmi. Pracuje w javie, a ta przesiadka na c/c++ na czas skonczenia tego badziewia jakos nie zacheca mnie do ponownego zaglebiania sie w c/c++. Po prostu nie mam na to czasu prawde powiedziawszy. CO prawda z tego co widze to wskazniki z C kompletnie z glowy mi wylecialy… java robi swoje…

Wracajac do tematu. Pozostaje jeszcze kwestia smieci w tablicy odwiedzone - juz zmodyfikowalem konstruktor po odpowiedzi nr47, ale nadal mam tam syf…

nr47 · 18 Kwiecień 2012 09:22

Przydzielenie pamięci poprzez new nie inicjalizuje jej żadną konkretną wartością, więc jeśli zakładasz, że tam są na początku zera - źle zakładasz. Użyj memset, żeby zainicjalizować pamięć wartością jaką chcesz: http://www.cplusplus.com/reference/clib … ng/memset/

(zakładając oczywiście, że w tym jest problem)

etam · 18 Kwiecień 2012 09:28

Ja bym zaczął od tego, że implementacja runDFS jest całkowicie źle zaprojektowana od podstaw. Przeprojektuj ją tak, żeby pozbyć się “std::stack > stos” (przy okazji: to nie jest stos wektorów, tylko stos, który używa wektora do przechowywania danych). Wejdź np. na https://duckduckgo.com/Depth-first_search, zobacz przykładowy pseudokod na wikipedii i poszukaj jak się robi porządnie rekurencję.

(na teraz: “bez odbioru”; będę wieczorem)

braciszek · 18 Kwiecień 2012 09:34

Etam, sprecyzuj ostatnią wypowiedź dot. złego zaprojektowania metody runDFS… Co w niej jest nie tak? Moż bardziej przypadnie TObie do gustu jak wywale z niej wszystko to co jest po bool tmp = true ?? A tak na serio teraz, zawsze w celu pozbycia sie tego stacka moge napisac własną klasę stos. Teoretycznie jest to rozwiązanie. Nadal jednak nie wiem czemu mi się tablica odzwiedzony nie modyfikuje…

– Dodane 18.04.2012 (Śr) 21:20 –

Dobra, pomoże mi ktoś znaleźć błąd innej kategorii? Chodzi o to że program nie wykonuje się tak jak powinien. Program ma zadeklarowana petle w ktorej ma sie wykonywac tak dlugo az znajdzie graf spojny. Problem w tym ze petla/DFS nie działa… prawidłowo

etam · 18 Kwiecień 2012 22:23

Twoja implementacja opowiedziana słowami wygląda tak:

funkcja runDFS(v):

    dla każdego sąsiada next wierzchołka v (znajdując ich przez przeglądanie tablicy za każdym razem od początku):

        jeżeli next jest nieodwiedzony:

            odwiedzony[next] = true

            wrzuć next na stos

    jeżeli stos jest niepusty:

        zdejmij jednego ze stosu jako u

        runDFS(u)

    sprawdź, czy wszyscy zostali odwiedzeni i jeżeli tak, to C=1

To nie może działać dobrze. To nie ma prawa działać dobrze. Już nie mówiąc o tym, że absolutnie nie ma prawa działać optymalnie. :evil: Pozwól, że cię oświecę jak to powinno wyglądać (uproszczona wersja https://pl.wikipedia.org/wiki/Przeszukiwanie_w_g%C5%82%C4%85b#Algorytm):

funkcja VisitNode(v):

    odwiedzony[v] = true

    dla każdego sąsiada u wierzchołka v:

        jeżeli u jest nieodwiedzony:

            VisitNode(u)


function DepthFirstSearch(Graf G):

    dla każdego wierzchołka v z grafu G:

        jeżeli v jest nieodwiedzony:

            VisitNode(v)

    // jeżeli graf jest z założenia spójny, to wystarczy samo VisitNode(0)

Wnioski i uwagi: - Implementacja przeszukiwania DFS jako obiektu jest z założenia nietrafione. Przeszukiwanie to czynność, nie obiekt. Próba implementacji tego jako obiektu jest tylko i wyłącznie kulą u nogi. - Poprawna implementacja DFS nie potrzebuje dodatkowego sprawdzania czy wszystkie wierzchołki zostały odwiedzone. Takie sprawdzanie tylko spowolni twój program. - Widzisz tu gdzieś stos? A teraz będę się czepiał szczegółów w implementacji (mimo, że ten kod i tak jest do wywalenia): Porównaj to

next = nextNod(v);

   while(next != -1){

      stos.push(next);

      next = nextNod(v);

   }

z tym

while ((next = nextNod(v)) != -1)

      stos.push(next);

Prostsze, prawda?

bool tmp = true;

   for(int i = 0; i
      if(odwiedzony[i] = 1) // !!! ERROR !!!!

         continue;

      else{

         tmp = false;

      }

   }

   if(tmp == true)

      C = 1;

   else

      C = 0;[/code]
Nie sądzisz, że usunięcie stąd zmiennej tmp jest niemal oczywiste?

[code] for(i=liczbaWezlow-1; i>=0; i–){ if(mapaBinarnaPrzyleglosci[i][v] == 1

Pytanie konkursowe: czy będzie jakaś różnica jeżeli będzie "if(mapaBinarnaPrzyleglosci[v] == 1"? Jeżeli tak, to jaka?

I jeszcze jedno: jeżeli używasz zmiennej typu int i przypisujesz jej tylko 0 lub 1, to użyj zamiast tego typu bool i wartości true i false. Główna i właściwie jedyna różnica jest taka, że int ma 4 bajty, a bool 1.

braciszek · 18 Kwiecień 2012 23:06

Dzięki etam. Na Ciebie można liczyć. Później to poprawie. Teraz pytanie konkursowe z mojej strony. Jak złączyć dane typu int w stringa?Tzn. mam coś takiego

string fileName;

fileName = “mapaSieci”+siec+“ilosc”+ilosc+".txt";

Wiem ze to co napisałem jest nie poprawne, ale chodziło o idee tego co chce uzyskać. Tym kodem odnosnie dfs’a pobawie sie jutro - tzn dzisiaj rano

Różnica będzie taka że będziesz odnosił się do innej “symetrii” macierzy.

Ten błąd z = 1 już usunąłem, zmienna tmp nie mniej jednak cały czas jest mi potrzebna. Po co? A no po to, że w przypadku nie wygenerowania grafu o spojnego program ma caly czas podejmowac proby wylosowania takich wspolrzednych aby otrzymac graf spojny.

etam · 19 Kwiecień 2012 09:02

std::ostringstream fileName;

fileName << "mapaSieci" << siec << "ilosc" << ilosc << ".txt";

wynik jest dostępny przed metodę http://en.cppreference.com/w/cpp/io/bas … stream/strEwentualnie w standardzie c++11 jest możliwość taka:

std::string fileName("mapaSieci"+std::to_string(siec)+"ilosc"+std::to_string(ilosc)+".txt"

Różnica jest taka, że iterując po pierwszej współrzędnej twój program skacze po pamięci, a iterując po drugiej jedzie po ciągłym fragmencie pamięci, co jest po prostu szybsze.

braciszek · 19 Kwiecień 2012 09:19

Dobra, ten program i tak nie dziala… Nadal nie liczy - nie sprawdza - czy graf jest spojny… Chce ktoś kod do obczajenia? Trochę się w nim zmieniło…

Problem stringa rozwiązałem za pomocą ostringstream

etam · 19 Kwiecień 2012 13:38

Wrzucaj. Sprawdzenie, czy graf jest spójny jest bardzo prostym algorytmem. Jeżeli tego nie opanujesz, to marny twój los programisty. Chociaż mógłbym ci napisać gotowe rozwiązanie (robota na jakieś 15 min.), ale było by to z mojej strony niemoralne.

braciszek · 19 Kwiecień 2012 13:50

o to kod, pominmy chwilowo jeszcze brak naniesionych poprawek, tych o których spowmniałeś ostatnio.

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

//#include "DFS.h"


using namespace std;


//zmienne globalne

int ilosc = 0; //ilosc wezlow

int zasieg = 0; //zasieg urzadzen podany w srednicy

int wysokosc = 0;	//zakres losowania na osi y -tj. od 0 do y

int szerokosc = 0;	//zakres losowania na osi x - tj. od 0 do x

int siec = 0; //okresla nr generowanej sieci, głownie do tworzenia plików potrzebna


//zmienneg globalne dla dfs'a

int directed = 0;



void dane(int argc, char *argv[]);

int toInt(char *liczba);

void losuj(int **tab);

void zapisz(int **tab);

void sasiedztwo(int **wsp, int** mapa, int **mapaBin);

void zapiszMape(int **mapa);



int main(int argc, char *argv[])

{

    dane(argc, argv);

	srand(time(NULL));	//losowanie - ustawienie roznego ziarna

    int **wspolrzedne;	//tablica 2d na wskaznikach

    wspolrzedne = new int *[ilosc];	//jak wyzej

	int **sasiedzi;	//mapa sasiadow nxn

	sasiedzi = new int *[ilosc];	//jak wyzej

	int **sasiedziBinarnie;

	sasiedziBinarnie = new int *[ilosc];

	for(int i=0; i
		wspolrzedne[i] = new int [2];

		wspolrzedne[i][0] = 0;

		wspolrzedne[i][1] = 0;

		sasiedzi[i] = new int [ilosc];

		sasiedziBinarnie[i] = new int [ilosc];

	}


	/*losuj(wspolrzedne);

	sasiedztwo(wspolrzedne, sasiedzi, sasiedziBinarnie);

	//DFS

	DFS dfs = DFS(ilosc, sasiedziBinarnie);

	dfs.runDFS(0);

	while(dfs.getC() != 1){

		losuj(wspolrzedne);

		sasiedztwo(wspolrzedne, sasiedzi, sasiedziBinarnie);

		dfs.setMapBinary(sasiedziBinarnie);

		dfs.setC();

		dfs.runDFS(0);

	}*/


	zapisz(wspolrzedne);

	zapiszMape(sasiedzi);

    return 1;

}


void zapiszMape(int **mapa){

	ofstream outFile;

	ostringstream data;

	data << "mapaKosztowSieci" << siec << "Ilosc" << ilosc << "zasieg" << zasieg << ".txt";

	string nazwaPliku = data.str();

	outFile.open(nazwaPliku, ios_base::trunc);

	for(int i = 0; i 
		for(int j = 0; j 
			if(j == ilosc-1)

				outFile << mapa[i][j] << "\n";

			else

				outFile << mapa[i][j] << ",";

	outFile.close();

}


void sasiedztwo(int **wsp, int** mapa, int **mapaBin){

	ofstream outFile2;

	ostringstream data;

	data << "mapaBinSieci" << siec << "Ilosc" << ilosc << "zasieg" << zasieg << ".txt";

	string nazwaPliku = data.str();

	outFile2.open(nazwaPliku, ios_base::trunc);

	for(int i= 0; i
		for(int j = 0; j < ilosc; j++){

			int XminusX = wsp[i][0] - wsp[j][0];

			int YminusY = wsp[i][1] - wsp[j][1];

			double tmp = sqrt(pow(XminusX, (double)2) + pow(YminusY, (double)2));

			if(i == j){

				mapa[i][j] = 0;

				mapaBin[i][j] = 0;

				outFile2 << mapaBin[i][j];

			} else if(tmp < (zasieg/2) && tmp != 0){

				mapa[i][j] = tmp;

				mapaBin[i][j] = 1;

				outFile2 << mapaBin[i][j];

			} else{

				mapa[i][j] = 999999;

				mapaBin[i][j] = 0;

				outFile2 << mapaBin[i][j];

			}

		}

		outFile2 << "\n";

	}

}


void zapisz(int **tab){

    ofstream outFile;

	ostringstream data;

	data << "wspolrzedneSieci" << siec << "Ilosc" << ilosc << "zasieg" << zasieg << ".txt";

	string nazwaPliku = data.str();

    outFile.open(nazwaPliku, ios_base::trunc);

    for(int i = 0; i
        if(i == ilosc-1)

			outFile << tab[i][0] << "," << tab[i][1];

		else

			outFile << tab[i][0] << "," << tab[i][1] << "\n";

    }

    outFile.close();

}


void losuj(int **tab){

    int a = 0;

    int b1 = szerokosc;

    int b2 = wysokosc;

    int x = 0;

    int y = 0;

    int count = 0;

    bool status = true;

    while(count < ilosc){

        x = rand()%(b1-a+1)+a;

        y = rand()%(b2-a+1)+a;

        for(int i=0; i
            if(tab[i][0] == x && tab[i][1] == y){

                status = false;

                break;

            }

        }

        if(status == true){

            tab[count][0] = x;

            tab[count][1] = y;

            count++;

        }

    }

}


void dane(int argc, char *argv[]){

    if(argc == 6){

        ilosc = toInt(argv[1]);

        zasieg = toInt(argv[2]);

        szerokosc = toInt(argv[3]);

        wysokosc = toInt(argv[4]);

		siec = toInt(argv[5]);

    }


    ofstream outFile;

    outFile.open("dane.txt", ios::app);

    outFile << ilosc << ",";

    outFile << zasieg << ",";

    outFile << wysokosc << ",";

    outFile << szerokosc << "\n";

    outFile.close();

}


int toInt (char *liczba) {

    int dlugoscLiczby = strlen(liczba);

    int liczbaINT = 0;

    int znak = 1;

    int cyfraAktualna;


    for (int i=0; i
       if ( (i==0) && (liczba[i]=='-') ) {

          znak = -1;

          continue;

       }

       if ( (liczba[i]<'0') || (liczba[i]>'9') )

          return(0);


       cyfraAktualna = liczba[i] - '0';

       liczbaINT = 10*liczbaINT + cyfraAktualna;

    }


    liczbaINT *= znak;

    return liczbaINT;

}

#ifndef DFS_H

#define	DFS_H


class DFS{

	private:

		std::stack > stos;	//stos do przechowywania wezlow w dfs'ie

		int *odwiedzony;

		int liczbaWezlow;

		int **mapaBinarnaPrzyleglosci;

		int C;


	public:

		DFS();

		DFS(int iloscWierzholkow, int **mapaBinarna);

		~DFS();

		int nextNod(int v);

		int getC();

		void setMapBinary(int **mapaBinarna);

		void setC();

		void runDFS(int v);

		void showStatus();

		void zeruj();

};


#endif	/* DFS_H */

#include 

#include 

#include 

#include 

#include "dfs.h"


DFS::DFS(){


}


DFS::DFS(int iloscWierzholkow, int **mapaBinarna){

	liczbaWezlow = iloscWierzholkow;

	mapaBinarnaPrzyleglosci = mapaBinarna;

	odwiedzony = new int[liczbaWezlow];

	for(int i = 0; i
		odwiedzony[i] = 0;

	C = 0;

}


DFS::~DFS(){

	delete[] odwiedzony;

}


void DFS::zeruj(){

	for(int i = 0; i < liczbaWezlow; i++)

		odwiedzony[i] = 0;

}


void DFS::showStatus(){

	for(int i = 0; i
		std::cout << odwiedzony[i] << " ";

	}

}


void DFS::setC(){

	C = 0;

}


int DFS::getC(){

	return C;

}


void DFS::setMapBinary(int **mapaBinarna){

	mapaBinarnaPrzyleglosci = mapaBinarna;

}


void DFS::runDFS(int v){

	int u;

	int next;

	odwiedzony[v] = 1;

	next = nextNod(v);

	while(next != -1){

		stos.push(next);

		next = nextNod(v);

	}

	if(!stos.empty()){

		u = stos.top();

		stos.pop();

		runDFS(u);

	}

	bool tmp = true;

	for(int i = 0; i
		if(odwiedzony[i] == 1)

			tmp = true;

		else

			tmp = false;

	if(tmp)

		C = 1;

	else

		C = 2;

}


int DFS::nextNod(int v){

	int i;

	for(i=liczbaWezlow-1; i>=0; i--){

		if((mapaBinarnaPrzyleglosci[i][v] == 1) && (odwiedzony[i] == 0)){

			odwiedzony[i] = 1;

			return i;

		}

	}

	return -1;	//zwraca gdy wierzcholek v nie ma juz nastepnikow

}

Program powinien wykonywać się do póki nie wygeneruje grafu spójnego. Problem w tym że teoretycznie program generuje graf spojny, teoretycznie, bo wyswietlenie grafu za pomoca php i svg z pliku daje zupelnie inne wyniki… Graf na którym pracuje jest w postaci tablicy NxN zapisanej binarnie. Funkcja powinna mi zwrocic jakas wartosc, najlepiej 1 inforumajac ze graf jest spojny - inna wartosc oznacza ponowne wykonanie petli

kostek135 · 19 Kwiecień 2012 21:12

Jeśli mogę coś zasugerować sprawdzanie spójności grafu poprzez DFS jest jak jedzenie zupy sitem. Niby coś jest, ale nie do końca. Zainteresuj się find & union z naprawianiem ścieżek, jest to bardziej wydajne. A implementacja zajmuje góra 5 minut.