Προς το περιεχόμενο
  • 0
Συνδεθείτε  
pagratios

Πως να βρω το κατάλληλο μονοπάτι για τα φύλλα σε Δέντρο C

Ερώτηση

Σε μία εργασία πρέπει να φτιάξουμε ένα hash tree στο οποίο δεσμεύουμε όλους τους κόμβους και τα φύλλα ξέροντας το height και το fanout, δηλαδή δεν το φτιάχνουμε δυναμικά σε κάθε εισαγωγή σελίδας επίσης είναι πλήρης δέντρο έχοντας σε κάθε επίπεδο όλους τους κόμβους.

 

Τώρα έχοντας το δέντρο δεσμευμένο δεν ξέρω πως θα βρω το κατάλληλο μονοπάτι για το φύλλο που θα αποθηκεύσω την σελίδα.

 

πχ. Σε ένα δέντρο ύψους 4(δλδ 0 1 2 3) με fanout 3 το οποίο έχει 3^3 φύλλα (δλδ id 0-26) πως θα βρω ότι το σωστό μονοπάτι για την σελίδα 16 είναι το 1 2 1?

 

φαντάζομαι κάποια διαίρεση με κατάλληλα νούμερα αλλά δεν μπορώ(πλην του πρώτου μονοπατιού) τα επόμενα.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

4 απαντήσεις σε αυτή την ερώτηση

Προτεινόμενες αναρτήσεις

  • 0

Για δοκίμασε αυτό:

...
	
	for ( i = 1; i <= height; i++ ){
		route = (page/(int)pow(fanout,(height-i))) ;
		page -= (route)*(int)pow(fanout, height-i);
		printf("%d ",route);
	}

...

Αν το i το ξεκινήσεις από το 0 τότε πρεπει να αλλάξει η δύναμη σε (height-i+1)

Το page είναι το id και τα height & fanout όπως τα δηλωσες παραπάνω...

 

Πιθανόν να υπάρχει και πιο σύντομος τρόπος, αλλά αυτό μου ήρθε τώρα...

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0
Δημοσ. (επεξεργασμένο)

Ευχαριστώ για την βοήθεια. Θα το δοκιμάσω στην πρώτη ευκαιρία.

Edit: αν έχουμε ύψος 4 το δέντρο έχει τα επίπεδα 0 για την ρίζα μέχρι το 3 για τα φύλλα. Μήπως πρέπει να κάνω pow(fanout, height-2-i) αν ξεκινήσω την for με i=0

Επεξ/σία από pagratios

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Ευχαριστώ για την βοήθεια. Θα το δοκιμάσω στην πρώτη ευκαιρία.

 

Edit: αν έχουμε ύψος 4 το δέντρο έχει τα επίπεδα 0 για την ρίζα μέχρι το 3 για τα φύλλα. Μήπως πρέπει να κάνω pow(fanout, height-2-i) αν ξεκινήσω την for με i=0

Παρακαλώ, δεν κάνει τίποτα :)

 

Αν δεν έχω κάνει κάποιο λάθος, δουλεύει γενικά για οποιαδήποτε τιμή του height & fanout...

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
Συνδεθείτε  
×
×
  • Δημιουργία νέου...

Χρήσιμες πληροφορίες

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.