Technology fan Δημοσ. 7 Οκτωβρίου 2009 Δημοσ. 7 Οκτωβρίου 2009 Μπορεί να μου πει κάποιος πως έχω πρόσβαση στο τελευταίο κόμβο του σωρού αν είναι υλοποιημένο δεσμεύοντας δυναμικά μνήμη? θέλω να πω οτι αν κάνω εισαγωγή πως ξέρω που είναι ο τελευταίος κόμβος? εφόσον το μόνο το οποίο κρατάω είναι η κορυφή του σωρού... Τη λογική θέλω οχι την υλοποίηση...
pbr_80 Δημοσ. 7 Οκτωβρίου 2009 Δημοσ. 7 Οκτωβρίου 2009 Μπορεί να μου πει κάποιος πως έχω πρόσβαση στο τελευταίο κόμβο του σωρού αν είναι υλοποιημένο δεσμεύοντας δυναμικά μνήμη? θέλω να πω οτι αν κάνω εισαγωγή πως ξέρω που είναι ο τελευταίος κόμβος? εφόσον το μόνο το οποίο κρατάω είναι η κορυφή του σωρού... Τη λογική θέλω οχι την υλοποίηση... μια φιλική συμβουλή να σου δώσω, επειδή δουλεύω σε εταιρεία πληροφορικής ως προγραμματιστής και είναι η δουλειά μου, καλό είναι στον προγραμματισμό να αναφέρεις τα πράγματα με την αγγλικη ορολογία και όχι με ελληνικές ορολογίες γιατί 2 απλούς λόγους 1. ο προγραμματισμός υπάρχει μόνο σε μια γλώσσα την αγγλική και 2. για να μπορείς να είσαι σε κοινή βάση με όλους τους προγραμματιστές. πχ θες να ψάξεις σε ένα φορουμ που ασχολούνται προγραμματιστές σε όλο τον κόσμο, δεν νομίζω να καταφέρεις να αναζητήσεις αυτό που θες εύκολα. το αναφέρω φιλικά ως καλοπροαίρετη συμβουλή
Technology fan Δημοσ. 7 Οκτωβρίου 2009 Μέλος Δημοσ. 7 Οκτωβρίου 2009 Φυσικά το δέχομαι... σωρός=heap ε όλα τα άλλα είναι κατανοητά πιστεύω
C6WGMN Δημοσ. 7 Οκτωβρίου 2009 Δημοσ. 7 Οκτωβρίου 2009 Θα συμφωνήσω και εγώ στο ότι η αγγλική ορολογία βοηθάει στην περιγραφή ενός προβλήματος για ποικίλους λόγους. Η απάντηση είναι πως πρέπει από την αρχή να καταλήξεις στο σωστό leaf node ψάχνοντας το δέντρο (tree) σαν να ήτανε binary tree. Σε binary trees με πραγματικούς αριθμούς χρησιμοποιείτε κανονική σύγκριση, αν αυτό που ψάχνω είναι μεγαλύτερο παο αριστερά αλλιώς δεξιά. Μπορείς να δώσεις μια αφηρημένη εννιά στο τι είναι μεγαλότητα και τι μικρότητα μετατρέποντας την μέθοδο σύγκρισης σε συνάρτηση. Ο κόμβος στον οποιο θα καταλήξεις με αυτή την μέθοδο είναι ο κόμβος στον οποιο πρέπει να εισχωρήσεις την νέα τιμή. Η θέση της τιμής (αριστερά η δεξιά του κόμβου) καθορίζεται από την συνάρτηση σύγκρισης.
Technology fan Δημοσ. 7 Οκτωβρίου 2009 Μέλος Δημοσ. 7 Οκτωβρίου 2009 Μόνο που στη συγκεκριμένη περίπτωση η εισαγωγή δεν γίνεται όπως λες, το οποίο σημαίνει οτι δε μου απαντάς. Η εισαγωγή στη heap προυποθέτει την εισαγωγή του στοιχείου στη τελευταία θέση και ύστερα επαναδιατάσεις τους δείκτες των κόμβων ανάλογα με το αν θα είναι max heap ή min heap! Επίσης θα εκτιμούσα αν ο pbr_80 ώντας όπως είπε προγραμματιστής (και μελλοντικά ελπίζω συνάδελφος) σε εταιρεία να με βοηθούσε να καταλάβω τη λογική της εύρεσης του τελευταίου κόμβου.
bxenos Δημοσ. 8 Οκτωβρίου 2009 Δημοσ. 8 Οκτωβρίου 2009 stfw1 stfw2 γιατι να μπεί στην τελευταία θέση; Δεν θα είναι sorted με κάποιο κλειδί; Για να βρίσκεις το βάθος (σε πόσα επίπεδα απλώνετε ένα δένδρο): > unsigned depth(node *root){ if(root != NULL) return 1 + max(depth(root->left),depth(root->right)); //επέστρεψε το μέγιστο βάθος αναμεσα στο αριστερο και στο δεξί υποδένδρο return 0; } Με ελάχιστες αλλαγές μπορείς να βρείς το αριστερότερο παιδί ή το δεξιότερο παιδί.
Technology fan Δημοσ. 8 Οκτωβρίου 2009 Μέλος Δημοσ. 8 Οκτωβρίου 2009 Δε ψάχνω ούτε το αριστερότερο παιδί ούτε το δεξιότερο ψάχνω το τελευταίο... η μόνη ταξινόμηση είναι οτι κάθε κόμβος είναι μεγαλύτερος απο τα παιδιά του. Η εισαγωγή όμως βάζει κάθε στοιχείο στο τέλος και ύστερα γίνεται κάποιο update και διορθώνεται το sorting... Επίσης ωραίες οι σημειώσεις θα τις κοιτάξω...
bxenos Δημοσ. 9 Οκτωβρίου 2009 Δημοσ. 9 Οκτωβρίου 2009 ψάχνω το τελευταίο ποιό είναι το τελευταίο; το μικρότερο; το μεγαλύτερο; αυτο που εισήχθηκε τελευταιο χρονικά; Σε ένα πίκακα ή σε μια συνδεδεμένη λίστα υπάρχουν και πρωτοι και τελευταίοι κόμβοι, Στη λογική δομή ενός δένδρου δεν γνωρίζω όρο τελευταίο. Διευκρίνησε το.
Technology fan Δημοσ. 9 Οκτωβρίου 2009 Μέλος Δημοσ. 9 Οκτωβρίου 2009 πιθανό να το σκέφτομαι λανθασμένα και να είναι όντως μία δυναμική ουρά και απλά να έχω δέικτες απο κάθε κόμβο της ουράς σε άλλους δύο... Όσον αφορά το τελυταίο κόμβο σε ένα δέντρο σημαίνει αυτό εκεί που λέει, Add the element on the bottom level of the heap. ουσιαστικά είναι στο χαμηλότερο height που μπορει να εισαχθεί κόμβος ο αριστερότερος κόμβος..
bxenos Δημοσ. 9 Οκτωβρίου 2009 Δημοσ. 9 Οκτωβρίου 2009 το enqueue είναι αυτό που θέλεις. count είναι ο αριθμός των δεσμευμένων θέσεων (count < array.length) array είναι ο πίνακας με τα δεδομένα (array.length είναι το μέγεθος του) object αυτό που προσθέτεις.
Technology fan Δημοσ. 10 Οκτωβρίου 2009 Μέλος Δημοσ. 10 Οκτωβρίου 2009 Δε με βοηθάει αυτό κάπως, ουσιαστικά μου εξηγείς το πως γίνεται εισαγωγή σε στατικό πίνακα... Τέλοςπάντων ευχαριστώ που ασχολείσαι αλλα πρέπει να είναι με συνδεδεμένη λίστα όπως είπα πριν..
bxenos Δημοσ. 11 Οκτωβρίου 2009 Δημοσ. 11 Οκτωβρίου 2009 Δεν έχεις δώσει τη δομή της λίστας που χρησιμοποίησες, οπότε υποθέτω είναι κάτι σαν > typedef ... datum; struct node { datum data; struct node *left,*right; }; Αν έχεις έναν μετρητή count για το πόσα δεδομένα έχει το δένδρο και θεωρώντας ότι πρώτα γεμίζουν τα αριστερα φύλλα, μετα τα δεξια και το δένδρο είναι balanced (heap), τότε: για να γίνει μια εισαγωγή δεδομένου στην "τελευταία" θέση, η μεταβλητή count είναι υπεύθυνη να σου δείξει τη θέση αυτή. περιορισμός κώδικα: χωρίς να πιάσω μολυβι και χαρτί, βλέπω ότι οι παρακάτω συναρτησεις που έγραψα, αξιοποιούν depth εώς τον αριθμό bit του unsigned-1. Δηλαδή για 16bit ακεραίους, εχουμε έως depth εως 15. Για μεγαλύτερα depth, πρέπει να χρησιμοποιηθεί μεγαλύτερος τύπος ακεραίου ή άλλου είδους λύση. > [color="DarkGreen"]η παρακάτω συνάρτηση πέρνει σαν παράμετρο τον αριθμό των δεδομένων που έχει ένα δένδρο και επιστρέφει: α) το βάθος (επίπεδο) που βρίσκεται ο πρώτος αχρησιμοποίητος κόμβος (π.χ. 0=root,1=επίπεδο κάτω απο το root,... β) τη θέση απο αριστερά που βρίσκεται ο πρώτος αχρησιμοποίητος κόμβος (0 = 1η θέση, 1 = δευτερη, ... 2^depth-1 = τελευταια) [/color] void where_is_the_first_free_pos(unsigned count,unsigned *pdepth,unsigned *ppos_from_left){ unsigned depth = 0; while(1){ //πόσα leaf χωράνε στο επίπεδο depth; unsigned this_depth_leafs = 1 << depth; if(count < this_depth_leafs){ //είμαστε στο τελευταίο επίπεδο και υπάρχει χώρος για ένα leaf *ppos_from_left = count; *pdepth = depth; break; } count -= this_depth_leafs; depth++; } } αποτελέσματα συνάρτησης: > count=0 depth=0 pos=0 count=1 depth=1 pos=0 count=2 depth=1 pos=1 count=3 depth=2 pos=0 count=4 depth=2 pos=1 count=5 depth=2 pos=2 count=6 depth=2 pos=3 count=7 depth=3 pos=0 count=8 depth=3 pos=1 count=9 depth=3 pos=2 count=10 depth=3 pos=3 count=11 depth=3 pos=4 count=12 depth=3 pos=5 count=13 depth=3 pos=6 count=14 depth=3 pos=7 count=15 depth=4 pos=0 ---------- Το μήνυμα προστέθηκε στις 00:08 ---------- και άλλος ένας τρόπος προγραμματισμού για την ίδια λύση (ίσως πιο δυσνόητος): > #include <limits.h> void where_is_the_first_free_pos2(unsigned count,unsigned *pdepth,unsigned *ppos_from_left){ unsigned depth; count++;//εδω θα μπεί ο νεος κόμβος for(depth=CHAR_BIT*sizeof(unsigned);depth;){ unsigned depth_mask = 1 << --depth; if(count & depth_mask){//we found the node's level. count &= depth_mask - 1;//strip previous levels nodes, keep only the last level ones break; } //else: this level is empty yet! } *ppos_from_left = count; *pdepth = depth; } Η λύση με log2(count) δεν είναι βολική λόγω χρόνου εκτέλεσης... ---------- Το μήνυμα προστέθηκε στις 00:24 ---------- Δηλαδή ο κόμβος της θέσης 68 (στο δυαδικό=001000100) αναλύετε ως εξής: MSBIT-> 001000100 <- LSBIT το πρώτο 1 απο τα αριστερα, δηλώνει το επίπεδο. ολα τα επόμενα bit (στο παράδειγμα είναι 000100) δηλώνουν τη θέση του κόμβου μέσα στο επίπεδο απο τα αριστερά. (ο κώδικας αναζήτησης συγκεκριμένου κόμβου στο heap βασιζόμενος στο παραπάνω, θα ανέβει εδώ αν χρειαστεί) ενδεικτικά αναφέρω ότι για τη διαδρομή στο να βρεθεί ένας κόμβος, απαιτείται recusrive μετακίνηση στο heap, π.χ. με > //κάθε κόμβος με αριθμό α, έχει για παιδια του τα 2*α και 2*α+1 static node *_find(node *root,hindex depth,hindex offset){ βρές τον "μπαμπά" αναδρομικά επέστρεψε το παιδί (offset) } node *find(node *root,hindex aa,hindex count){ //root is the head top node //aa is the number of the node, 0 = root,1-2 are root children,3-4-5-6 are those children children //count is the number of nodes (that means node numbers are from 0 to count-1 inclusive) καλεσε τη _find... }
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.