Γενικό Λύκειο > Δομές δεδομένων

Καλύτερη υλοποίηση ουράς

<< < (2/9) > >>

epsilonXi:
Αλκη, χωρίς να το τσεκάρω προσεκτικά, η υλοποίησή σου καλύπτει και τις περιπτώσεις όπου η εισαγωγή γίνεται σε κενή ουρά, και η εξαγωγή γίνεται σε ουρά που έχει ένα στοιχείο; Το λέω επειδή περίμενα να αλλάζουν front και rear μαζί... το καλύπτεις με το πλήθος;

alkisg:
Ναι, π.χ. από το αρχικό παράδειγμα:

Έναρξη: Ουρά = [ε, , , , ]
Εισαγωγή: 1, Ουρά = [επ1, , , , ]

Αυτό ήταν εισαγωγή σε κενή ουρά. Το "πίσω" έδειχνε στη θέση 0 και έγινε 1. Το "εμπρός" έδειχνε στη θέση 1 και παρέμεινε 1. Στην εισαγωγή, μπαίνει ένα στοιχείο (εδώ το "1") στο τέλος της ουράς, οπότε αλλάζει μόνο το πίσω, όχι το εμπρός.

Εξαγωγή:  7, Ουρά = [, , επ10, , ]
Εξαγωγή:  10, Ουρά = [, , π, ε, ]

Αυτό ήταν εξαγωγή σε ουρά με ένα στοιχείο. Και το εμπρός και το πίσω έδειχναν στη θέση 3. Το εμπρός μας δείχνει το πρώτο στοιχείο της ουράς και το πίσω το τελευταίο, οπότε όταν υπάρχει ένα μόνο στοιχείο (εδώ το "10"), δείχνουν και τα δύο σε αυτό. Κατά την εξαγωγή αλλάζει μόνο το εμπρός και αυξάνεται κυκλικά κατά ένα.

epsilonXi:
βιβλίο σελ.61
«ο εμπρός (front) και ο πίσω (rear) δείκτης, που μας δίνουν τη θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί και τη θέση του στοιχείου που μόλις εισήλθε»

συμπληρωματικό υλικό σελ. 24
«Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου. Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν»

Προφανώς και μπορούν αυτές οι περιγραφές να αλλάξουν αν προταθεί ένας άλλος αλγόριθμος υλοποίησης της ουράς, αλλά προσωπικά δεν θα ήθελα να αλλάξουν γιατί μου φαίνεται ότι είναι ορθές:
- ο front δείχνει τη θέση του στοιχείου που είναι έτοιμο να φύγει
- ο rear δείχνει τη θέση του στοιχείου που που μπήκε πιο πρόσφατα στην ουρά

θέλοντας να είμαι πιο πιστός σε αυτούς τους «ορισμούς» θα προτείνω τα ακόλουθα:

όπου χ = ο ελεύθερος χώρος της ουράς (αρχικά ίσο με το μέγεθός της)
όπου μ = ο δείκτης front (αρχικά μηδέν)
όπου π = ο δείκτης rear (αρχικά μηδέν)

για την εισαγωγή της τιμής Τ στην ουρά A με μέγεθος Ν:


--- Κώδικας: Bash ---αν χ = 0 τότε  γράψε 'περάστε από Δευτέρα'αλλιώς  π <-- (π+Ν) mod Ν + 1 ! π <-- κυκλική_θέση(π)  Α[π] <-- Τ  χ <-- χ - 1  αν μ = 0 τότε    μ <-- 1  τέλος_αντέλος_αν
για την εξαγωγή στην μεταβλητή Τ από την ουρά Α με μέγεθος Ν:


--- Κώδικας: Bash ---αν χ = Ν τότε  γράψε 'ουκ αν λάβοις παρά του μη έχοντος'αλλιώς  Τ <-- Α[μ]  μ <-- (μ + Ν) mod N + 1 ! μ <-- κυκλική_θέση(μ)  χ <-- χ + 1  αν χ = Ν τότε    π <-- 0    μ <-- 0  τέλος_αντέλος_αν


επίσης, αν είναι τις στοίβες και τις ουρές να τις υλοποιούμε με υποπρογράμματα, προσωπικά θα ήθελα και κάτι του στυλ:
διαδικασία αρχικοποίηση(ουρά, εμπρός, πίσω, ελεύθερος_χώρος)
μόνο και μόνο για να μην υπάρχει στον κώδικα του προγράμματος καμμία εντολή εκχώρησης τιμής στις 3 μεταβλητές που θέλω, κι έτσι να έχω την ψευδαίσθηση κάποιας «αυτονομίας» αν το δω ως υποπρόγραμμα, ή κάποιας «ενθυλάκωσης» αν το δω σαν μέθοδο αντικειμένου



alkisg:

--- Παράθεση από: epsilonXi στις 16 Φεβ 2020, 05:00:42 μμ ---Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου.

--- Τέλος παράθεσης ---

Σε αυτό νομίζω συμφωνούμε όλοι.


--- Παράθεση από: epsilonXi στις 16 Φεβ 2020, 05:00:42 μμ ---Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν

--- Τέλος παράθεσης ---

Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:

* Μετά την πρώτη εισαγωγή, θέλουμε να δείχνουν και οι δύο δείκτες το πρώτο στοιχείο, rear=1 και front=1.
* Στις εισαγωγές, θέλουμε να μεταβάλλουμε μόνο τον δείκτη rear. Δεν έχει νόημα να μεταβάλλουμε και τον front. Έτσι και γλυτώνουμε μια ΑΝ και κάνουμε τον κώδικα απλούστατο, μόνο 3 γραμμές.
* Από τα δύο προηγούμενα bullets συνεπάγεται ότι οι καλύτερες αρχικές τιμές και από πλευράς υλοποίησης και από πλευράς διδασκαλίας είναι rear=0 και front=1.Αντίστοιχα στις εξαγωγές εννοείται ότι θέλουμε να μεταβάλλουμε μόνο τον δείκτη front.

akalest0s:

--- Παράθεση από: alkisg στις 17 Φεβ 2020, 08:41:02 πμ ---Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:

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

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

[*] Προηγούμενη σελίδα

Μετάβαση στην πλήρη έκδοση