[C++] Wskaźniki a obiekty w rekurencji


(Marcin Obala) #1

Witam

Mam problem w C++. Wywołuje dosyć głęboką rekurencję i w środku tej rekurencji tworzę tablice. Następnie chciałbym w obiekcie zapamiętać jego poprzednika jednak ten poprzednik może być zmienną wygenerowaną w rekurencji. O ile dostaję jego adres w pamięci o tyle po wyjściu z rekurencji we wszystkich zmiennych tego obiektu są śmieci bo po wyjściu z rekurencji wszystko zostało usunięte. Jest to algorytm DFS do gry piętnastka. Algorytm jest głupi a co za tym idzie muszę na czuja przegrzebać wszystkie możliwe stany aż nie trafię na stan który jest końcem a następnie od końca chciałbym odtworzyć układ ruchów jaki trzeba wykonać. Jednak jak mówiłem, mimo że zapamiętuje wskaźnik na poprzednika to niestety ten poprzednik może być zmienną lokalną więc jest w ostateczności usuwany.


(etam) #2

Nie wiem czy dobrze rozumiem, ale z tego co zrozumiałem, to problem jest taki (w uproszczeniu):

class Obiekt {

public:

    Obiekt* poprzednik;

};


void rekurencja(Obiekt& ob) {

    Obiekt poprzednik;

    ob.poprzednik = &poprzednik;

}


int main() {

    Obiekt ob;

    rekurencja(ob);

    ob.poprzednik // <- wskaźnik do nieistniejącego obiektu

    return 0;

}

W tej sytuacji rozwiązaniem jest

class Obiekt {

public:

    Obiekt* poprzednik;

};


void rekurencja(Obiekt& ob) {

    Obiekt *poprzednik = new Obiekt();

    ob.poprzednik = poprzednik;

}


int main() {

    Obiekt ob;

    rekurencja(ob);

    ob.poprzednik // <- wskaźnik do istniejącego obiektu

    delete ob.poprzednik;

    return 0;

}

Czy o to chodziło? Jeżeli nie to pisz. Jeżeli tak to też :slight_smile:


(Enterbios) #3

Radze unikać rekurencji, no ale skoro już masz to tak napisane to...

Przekazuj do funkcji w rekurencji jako parametr stos przez referencje (http://www.cplusplus.com/reference/stl/stack/).

Na stos pakujesz obiekty które potem chcesz sobie od końca odtworzyć. Jeżeli się cofasz w rekurencji to ściągasz ze stosu to co nie potrzebne. Gdy znajdziesz rozwiązanie wyjdź wyjątkiem i złap go przy starcie rekurencji.

Teraz nie jestem pewien czy dobrze zrozumiałem o co Ci chodzi, bo z opisu też mogę wywnioskować że tworzysz sobie tablice wskaźników i dodajesz do niej adresy zmiennych lokalnych albo nie wiesz jeszcze co to konstruktor kopiujący i dlatego pojawiają Ci się śmieci. Jeśli twoim problemem jest druga sytuacja to napisz konstruktor kopiujący i zamiast tablicy wskaźników trzymaj tablice obiektów. Albo jeszcze lepiej niż tablice jakiś obiekt z stl.


(Marcin Obala) #4

Problem rozwiązałem chyba w ten sam dzień w który napisałem temat. Dodatkowo mam drugą wersję algorytmu tym razem iteracyjną w której mam własny stos. A co do tego co robiłem w kodzie to to pierwsze. Dawno nie pisałem w C++ i miałem lekkie zamotanie ze wskaźnikami, zazwyczaj pracuję w C#.