Αναδρομική κλήση σε C++

[Nexus]

Στο παράδειγμα που ακολουθεί έχω ορίσει μία κλάση που περιέχει τις συντεταγμένες του κόμβου και ένα δείκτη προς τον προηγούμενο κόμβο. Όλοι οι προηγούμενοι κόμβοι βρίσκονται σε ένα vector, με όνομα evaluated. Αυτό που θέλω να κάνω είναι: στο πρώτο if ελέγχω μία συνθήκη και εάν ισχύει θέτω στον κόμβο αυτό τις συντεταγμένες και βάζω το δείκτη να δείχνει στο στοιχείο κ του vector που είναι ο προηγούμενος κόμβος του κόμβου nb που εξετάζω αυτή τη στιγμή. Έπειτα ελέγχω με το 2ο if εάν είναι ο τελικός κόμβος που ψάχνω και εάν είναι καλώ την αναδρομική συνάρτηση για να μου εκτυπώσει όλη τη διαδρομή. Το πρόβλημα είναι ότι ενώ ξεκινά η εκτέλεση το πρόγραμμα κρεμάει. Άλλαξα τη σειρά των 2 υπογραμμισμένων εντολών έτσι ώστε πρώτα να εκτυπώνει τον τρέχοντα κόμβο και μετά να εκτελείται η αναδρομή και είδα ότι εκτυπώνει του τελευταίους 2-3 κόμβους και μετά άσχετους αριθμούς... Κάποια βοήθεια ??

 

Ευχαριστώ !

 

>class node {
       public:

       int x;                    
       int y;                    
       node *came_from;      

       void reconstruct_path() {
           if (came_from) {
               [u]came_from->reconstruct_path();[/u]
               [u]cout << " -> (" << x <<"," << y << ")";[/u]
           }
           else {							//O deikths tou arxikou komboy einai null
               cout <<"The path is: ";
               cout << "(" << x <<"," << y << ")";
           }
       }
};


int main () {

       
   vector<node> evaluated;     //Telikoi Komboi

	........
     
       if (nb_pos == -1) {
           nb.x = new_x;
           nb.y = new_y;
           nb.came_from = &evaluated[k];            
           }
    
	.....
while(...){

if (nb==goal) {   

       nb.reconstruct_path();     //Print the path

       return 0;       
   }    
}
}

[MitsakosGR]

...

Άλλαξα τη σειρά των 2 υπογραμμισμένων εντολών έτσι ώστε πρώτα να εκτυπώνει τον τρέχοντα κόμβο και μετά να εκτελείται η αναδρομή και είδα ότι εκτυπώνει του τελευταίους 2-3 κόμβους και μετά άσχετους αριθμούς... Κάποια βοήθεια ??

 

Ευχαριστώ !

 

Το ότι σου βγάζει άσχετους αριθμούς σημαίνει ότι πάει να διαβάσει περιοχές της μνήμης που δεν είναι ορισμένες μέσα στο πρόγραμμά σου.

Για να λειτουργήσει σωστά η if (came_from){ } πρέπει πρώτα να έχεις κάνει null τους Pointers έτσι ώστε να ξέρεις αν έχουν πάρει πραγματική τιμή ή απλά έχουν τυχαία data από την μνήμη. Στον Constructor της class node βάλε να γίνεται null.

>class node {
       public:

       int x;                    
       int y;                    
       node *came_from;
     
       [b]node(){
           came_from = null;
       }[/b]

       void reconstruct_path() {
           if (came_from) {
               [u]came_from->reconstruct_path();[/u]
               [u]cout << " -> (" << x <<"," << y << ")";[/u]
           }
           else {							//O deikths tou arxikou komboy einai null
               cout <<"The path is: ";
               cout << "(" << x <<"," << y << ")";
           }
       }
};

[Nexus]

Το ότι σου βγάζει άσχετους αριθμούς σημαίνει ότι πάει να διαβάσει περιοχές της μνήμης που δεν είναι ορισμένες μέσα στο πρόγραμμά σου.

Για να λειτουργήσει σωστά η if (came_from){ } πρέπει πρώτα να έχεις κάνει null τους Pointers έτσι ώστε να ξέρεις αν έχουν πάρει πραγματική τιμή ή απλά έχουν τυχαία data από την μνήμη. Στον Constructor της class node βάλε να γίνεται null.

>class node {
       public:

       int x;                    
       int y;                    
       node *came_from;
     
       [b]node(){
           came_from = null;
       }[/b]

       void reconstruct_path() {
           if (came_from) {
               [u]came_from->reconstruct_path();[/u]
               [u]cout << " -> (" << x <<"," << y << ")";[/u]
           }
           else {							//O deikths tou arxikou komboy einai null
               cout <<"The path is: ";
               cout << "(" << x <<"," << y << ")";
           }
       }
};

 

Το έχω κάνει αυτό στον constructor αλλά δεν λειτουργεί. Η εντολή "nb.came_from = &evaluated[k];" όπου περνάω τη διεύθυνση του στοιχείου κ στον δείκτη σωστή δεν είναι ? Παίζει κάποιο ρόλο που δείχνει σε στοιχείο του vector ?

[parsifal]

Η εντολή "nb.came_from = &evaluated[k];" όπου περνάω τη διεύθυνση του στοιχείου κ στον δείκτη σωστή δεν είναι ? Παίζει κάποιο ρόλο που δείχνει σε στοιχείο του vector ?

 

Αν ρωτάς για το αν είναι συντακτικά σωστή και περνάει το type checking, φαίνεται να είναι. Σε κάθε περίπτωση, θα σε ενημερώσει ο compiler σου αν δεν είναι.

 

Αλλά μπορεί να υπάρχει λογικό λάθος στον κώδικα, σε σημείο του που δεν παραθέτεις εδώ.

Π.χ.1: Η τιμή του k, εκεί που την αλλάζεις στον κώδικα (γιατί στο απόσπασμα που παραθέτεις δεν φαίνεται να γίνεται κάτι τέτοιο) είναι συνεπής; Αντί του τελεστή vector::operator[] μπορείς να χρησιμοποιήσεις τη μέθοδο vector::at, η οποία πετάει out_of_range exception αν το k έχει τιμή που σηματοδοτεί πρόσβαση σε περιοχή μνήμης εκτός της τρέχουσας έκτασης του vector container σου.

Π.χ.2: Έχεις σίγουρα δώσει τιμές στα x, y members όλων των node objects που βρίσκονται μέσα στο vector; Δεν τα αρχικοποιείς κι αυτά καλού κακού στον constructor της κλάσης node σε μία τιμή όπως π.χ. INT_MIN (climits.h) ;

Π.χ.3.: Κλπ κλπ...

[MitsakosGR]

Αφού χρησιμοποιείς vector, δεν είναι ανάγκη να έχεις pointer σε αντικείμενο τύπου node, στην συγκεκριμένη εφαρμογή τουλάχιστον (αν κατάλαβα καλά φτιάχνεις κάτι σαν συνδεδεμένη λίστα).

Στην συνδεδεμένη λίστα με πίνακα κρατάς την θέση του πίνακα που έχεις το προηγούμενο/επόμενο στοιχείο, όχι την διεύθυνση μνήμης του στοιχείου. Έτσι μπορείς να έχεις ένα int came_fromκαι να κρατάς της θέση του vector που έχεις το προηγούμενο node. Ίσως αυτό σε διευκολύνει λίγο και στο να βρεις που έχεις το πρόβλημα.

[Nexus]

Ευχαριστώ πολύ για τις απαντήσεις, τα κοιτάζω και θα επανέλθω !

[Nexus]

Τελικά δούλεψε, αντικατέστησα τον pointer με έναν ακέραιο που έδειχνε τη θέση του προηγούμενου στοιχείου στο vector και δούλεψε.

 

Ευχαριστώ πολύ ! ;-)