Θέμα: ΟΥΡΑ-ΣΤΟΙΒΑ

[tkon]

ΖΗΤΩ ΤΗΝ ΒΟΗΘΕΙΑ ΣΤΑ ΠΑΡΑΚΑΤΩ ΕΡΩΤΗΜΑΤΑ:

1)Η ΟΥΡΑ ΚΑΙ Η ΣΤΟΙΒΑ ΤΙ ΔΟΜΗ ΔΕΔΟΜΕΝΩΝ ΕΙΝΑΙ;
2)Η ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΠΟΡΕΙ ΝΑ ΕΦΑΡΜΟΣΤΕΙ ΣΕ ΤΑΞΙΝΟΜΗΜΕΜΟ ΠΙΝΑΚΑ;
3)Η ΤΑΞΙΝΟΜΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΜΠΟΡΕΙ ΝΑ ΠΕΣΕΙ ΩΣ ΘΕΜΑ ΣΤΙΣ ΕΞΕΤΑΣΕΙΣ;(ΕΠΕΣΕ ΣΤΑ ΘΕΜΑΤΑ ΟΕΦΕ ΤΟΥ 2006)

[andreas_p]

1) Στατική (υλοποίηση με πίνακα)
2) Ναι
3) Ναι (σε επίπεδο γραμμής ή στήλης)

[P.Tsiotakis]

πολύ ωραίο θέμα θα ήταν η αναζήτηση σε δισδιάστατο

[evry]

1)Η ΟΥΡΑ ΚΑΙ Η ΣΤΟΙΒΑ ΤΙ ΔΟΜΗ ΔΕΔΟΜΕΝΩΝ ΕΙΝΑΙ;

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

Η άποψη η δική μου είναι ότι όταν μιλάμε γενικά για στοίβα και ουρά δεν μας ενδιαφέρει η υλοποίηση. Μας ενδιαφέρει μόνο το interface. Εμείς βλέπουμε μόνο τις δύο πράξεις (push/pop) και τίποτα άλλο. Αυτή δεν είναι άλλωστε και η έννοια του Αφηρημένου Τύπου Δεδομένων? Δεν μας ενδιαφέρει πως υλοποιείται εσωτερικά αλλά μόνο η διεπαφή. Με αυτό το σκεπτικό θα μπορούσαμε να πούμε ότι πρόκειται για δυναμικές δομές δεδομένων.
Αυτό όσον αφορά το επιστημονικό κομμάτι που έρχεται σε δεύτερη μοίρα γιατί υπάρχει και το διδακτικό κομμάτι. Ο μαθητής έχει στο μυαλό του ότι μια στατική δομή είναι αυτή η οποία έχει σταθερή μέγεθος ενώ μια δυναμική αλλάζει μέγεθος. Επίσης αν ρωτήσεις τον μαθητή ποιο είναι το μέγεθος της ουράς ή πόσα στοιχεία έχει, δεν θα σου απαντήσει με τον αριθμό των χρησιμοποιούμενων θέσεων και όχι με το μέγιστο δυνατό αριθμό των στοιχείων που μπορεί να δεχτεί. Πιστεύω ότι για τον μαθητή πιο εύκολο είναι να δεχτεί ότι η ουρά/στοίβα είναι δυναμικές δομές παρά στατικές

2)Η ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΠΟΡΕΙ ΝΑ ΕΦΑΡΜΟΣΤΕΙ ΣΕ ΤΑΞΙΝΟΜΗΜΕΜΟ ΠΙΝΑΚΑ;

Προφανώς και μπορεί, εφαρμόζεται σε όλους τους πίνακες, η δυαδική είναι αυτή που εφαρμόζεται μόνο σε ταξινομημένους πίνακες

3)Η ΤΑΞΙΝΟΜΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΜΠΟΡΕΙ ΝΑ ΠΕΣΕΙ ΩΣ ΘΕΜΑ ΣΤΙΣ ΕΞΕΤΑΣΕΙΣ;(ΕΠΕΣΕ ΣΤΑ ΘΕΜΑΤΑ ΟΕΦΕ ΤΟΥ 2006)

Δεν ξέρω τι έπεσε στις εξετάσεις του ΟΕΦΕ αλλά πολύ θα ήθελα να δω την εκφώνηση και πως όριζαν την ταξινόμηση στον δισδιάστατο. Δε νομίζω ότι έχει ιδιαίτερο νόημα κάτι τέτοιο γιατί μπορείς κάλλιστα να αντιγράψεις τα δεδομένα σε έναν μονοδιάστατο και να κάνεις ταξινόμηση εκεί.

edit: Τώρα είδα την ταξινόμηση, είναι στα θέματα του 2007 και δεν λέει για ταξινόμηση του πίνακα αλλά για ταξινόμηση των γραμμών του. Δηλαδή εφαρμόζεις ξεχωριστά σε κάθε γραμμή τον αλγόριθμο της ταξινόμησης

Παρεπιπτόντως εκεινή τη χρονιά ο ΟΕΦΕ έβαλε ένα ολόιδιο θέμα με αυτό που έπεσε πέρυσι με την Επίλεξε. Το έχει παρατηρήσει κανένας??

[xpanta]

Καλησπέρα.

Έχω την εντύπωση οτι η δομές της στοίβας και της ουράς είναι στην πραγματικότητα στατικές δομές. Εξού και το stack overflow μήνυμα.

[evry]

  Αυτό σηκώνει κάποια κουβέντα, έχει να κάνει με το τι ορισμό δίνουμε για το στατικός και για το δυναμικός. Τι θέλω να πω. Ας σκεφτούμε μια δυναμικά συνδεδεμένη λίστα. Αυτή θεωρείται δυναμική δομή δεδομένων. Και εδώ όμως υπάρχει αντίστοιχο μήνυμα "list overflow" ας πούμε, γιατί η μνήμη του υπολογιστή δεν είναι άπειρη. Αν δεν υπάρχει διαθέσιμη μνήμη η συνάρτηση δυναμικής εκχώρησης μνήμης θα μας επιστρέψει έναν μεγαλοπρεπή null pointer αν τα θυμάμαι καλά.
   Με το σκεπτικό αυτό, όλες οι δομές είναι στατικές.

[Νίκος Αδαμόπουλος]

Καλησπέρα.

Έχω την εντύπωση οτι η δομές της στοίβας και της ουράς είναι στην πραγματικότητα στατικές δομές. Εξού και το stack overflow μήνυμα.

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

Μάλιστα, η υλοποίηση ουράς με πίνακα έχει ενδιαφέρον γιατί πρέπει να ελέγχεις αν έχεις φτάσεις στο τέλος του πίνακα, ώστε στη συνέχεια η επόμενη "εισαγωγή" να γίνει πάλι στην αρχή του πίνακα (αν δεν έχει γεμίσει). Δηλαδή είναι σαν "κυκλικός" πίνακας: το τέλος φανταζόμαστε ότι ενώνεται με την αρχή ώστε η ουρά να "προχωρά" μέσα σε αυτόν τον "δακτύλιο". Αλήθεια, αυτό φαίνεται δεν αποσχόλησε καθόλου τους συγγραφείς του βιβλίου: Τι θα γίνει δηλαδή αν φτάσουμε στο τέλος του πίνακα ενώ υπάρχουν ελεύθερες θέσεις πλέον στην αρχή του ...