Εισαγωγή κλειδιών σε άδειο σωρό.

[gpapava]

Καλησπέρα παιδιά.

Έχω να κάνω την εξής ερώτηση. Πως ξεκινάμε να εισάγουμε αριθμούς σε άδειους σωρούς;

 

Παράδειγμα αν έχουμε τα κλειδιά 3, 1, 4, 1, 5, 9, 2, 6, 5, 4 πως ξεκινάμε;

Με αυτήν την σειρά. Αν μπορεί ας με βοηθήσει κάποιος.

[V.I.Smirnov]

Για σωρό (stack) που αφορά αριθμούς και υλοποιείται με συνδεσμική λίστα (linked list)

είχα δώσει ένα παράδειγμα εδώ :

 

http://www.insomnia.gr/topic/396401-%cf%85%ce%bb%ce%bf%cf%80%ce%bf%ce%b9%ce%b7%cf%83%ce%b7-%cf%83%cf%89%cf%81%ce%bf%cf%85-%cf%83%ce%b5-c/

 

-

[gpapava]

Δεν θέλω τον κώδικα. Θα ήθελα να κατανοήσω πως γίνεται. Για παράδειγμα το 3 μπαινει πρώτο, έπειτα το1 μπάινει από κάτω αφού είναι μικρότερο. Μπαίνει από αριστερά ή απο δεξια όμως; Το 4 μετά πως εισάγεται; Δεν υπάρχει μια τεχνική όπως υπάρχει αντίστοιχα στα δυαδικα δενδρα avl κτλ; Ευχαριστώ για την απάντηση φίλε

[V.I.Smirnov]

Από αυτά που ρωτάς φαίνεται ότι δεν έχεις καταλάβει τι είναι ο σωρός (stack).

 

Το stack είναι μια απλή λίστα στην οποία προστίθενται και αφαιρούνται στοιχεία με καθορισμένη σειρά.

Η σειρά αυτή είναι η λεγόμενη LIFO (last in/first out) και αποτελεί το μοναδικό κριτήριο τοποθέτησης

και ανάκτησης των δεδομένων.

Έτσι, τα δεδομένα αποθηκεύονται διαδοχικά με την σειρά που δίνονται.

Πέραν του LIFO, κανένα άλλο κριτήριο δεν παίζει ρόλο στην αποθήκευση (ούτε και το μέγεθος).

 

Στα δυαδικά δέντρα αναζήτησης, κάποιο μέγεθος που ορίζει διάταξη χρησιμοποιείται ως

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

και για την αναζήτησή τους.

 

Τα AVL δέντρα είναι ειδική περίπτωση δυαδικών δέντρων αναζήτησης όπου χρησιμοποιείται ειδική

τεχνική κατά την εισαγωγή ώστε τα παραμένουν "ισορροπημένα" και να μην εκφυλλίζονται σε λίστες.

Το ίδιο και τα splay trees καθώς και τα Red-Black trees (αυτά είναι τα καλύτερα όλων).

Ο εκφυλλισμός ενός δέντρου σε λίστα μετατρέπει την χρονική τάξη της αναζήτησης από λογαριθμική σε

γραμμική αναιρώντας το πλεονέκτημα της ταχύτητάς τους.

Το stack δεν έχει τίποτε απ' όλα αυτά.

 

-

[gpapava]

Σου διαβάζω ακριβώς το θέμα από παλαιότερες εξετάσεις:

 

Υπολογίστε τους σωρούς, που σχηματίζονται, αν σε έναν αρχικά άδειο σωρό διαδοχικά εισάγουμε δέκα

κλειδιά, με τη σειρά: 3, 1, 4, 1, 5, 9, 2, 6, 5, 4.

 

Εννοεί κάτι άλλο; Εννοεί heap; Και αν εννοεί heap πως γίνεται η εισαγωγή;

[V.I.Smirnov]

Όταν μιλάμε για σωρούς, είναι αυτό που σου είπα πριν.

 

Υπάρχουν δομές τύπου heap που είναι οι διάφοροι τύποι δέντρων και η ουρά προτεραιότητας (priority queue).

Ειδικότερα,

ένα δέντρο είναι "heap-ordered" αν σε κάθε κόμβο,

το κλειδί είναι μεγαλύτερο ή ίσο από τα κλειδιά των όλων των κόμβων που είναι θυγατρικοί του.

 

Οι δομές heap, αν θυμάμαι καλά, είναι ένα σύνολο κόμβων με κλειδιά,

τοποθετημένοι σε ένα πλήρες, heap-ordered δυαδικό δέντρο.

Μάλιστα θυμάμαι ότι οι ορισμοί επισημαίνουν ότι η υλοποίηση του δέντρου πρέπει να είναι με πίνακα

κι' όχι με λίστα (δείκτες) όπως συνήθως γίνεται.

 

Σε αυτό το πλαίσιο η εκφώνηση εννοεί δυαδικό δέντρο και η τοποθέτηση γίνεται με τον ανάλογο τρόπο.

 

 

Τέλος, επειδή εγώ δεν έχω σπουδές πληροφορικής και εφόσον πρόκειται για εξετάσεις,

οι απαντήσεις μου να ληφθούν με επιφύλαξη...

 

-

[gpapava]

Την ψιλοβρήκα την άκρη. Ευχαριστώ για την βοήθεια πάντως.

[V.I.Smirnov]

Όταν βρεις χρόνο πες μου σε παρακαλώ σε τι αναφέρεται η εκφώνηση (δηλ. σε ποιά δομή).

Έτσι, απο περιέργεια...

 

-

[parsifal]

Όταν βρεις χρόνο πες μου σε παρακαλώ σε τι αναφέρεται η εκφώνηση (δηλ. σε ποιά δομή).

Έτσι, απο περιέργεια...

Stack = η δομή δεδομένων «στοίβα»

Heap = η δομή δεδομένων «σωρός»

Εντελώς διαφορετικές μεταξύ τους.

 

Άρα, εδώ:

Από αυτά που ρωτάς φαίνεται ότι δεν έχεις καταλάβει τι είναι ο σωρός (stack).

υπάρχει το λάθος, που σου δημιούργησε την απορία.

[V.I.Smirnov]

@parsifal

 

Έχεις δίκιο, δική μου παρανόηση.

Mετέφρασα λανθασμένα ότι "σωρός" και "στοίβα" είναι συνώνυμα του "stack".

Στα αγγλικά βέβαια ήξερα την διαφορά heap vs stack, γι' αυτό γράφω και τον αγγλικό όρο δίπλα.

Άρα πρόκειται για heap ordered δομή όπως γράφω στο post #6.

 

Σε ευχαριστώ για την υπόδειξη.

 

-