Αποστολέας Θέμα: Απορία στην Στοιβα  (Αναγνώστηκε 2499 φορές)

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5870
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Απορία στην Στοιβα
« Απάντηση #30 στις: 21 Απρ 2021, 05:18:55 μμ »
> Πρόσφατα κάπου διάβασα ότι στοίβα και σωρός άρχισαν να τα διαφοροποιούν.

Είναι εντελώς διαφορετικές δομές stack και heap, αν κάπου/κάποτε διδάχτηκαν ως ίδια, έγινε σοβαρό λάθος...

Στοίβα χρησιμοποιούμε όταν δηλώνουμε τοπικές μεταβλητές, π.χ.: char c = 'a';
Σωρό χρησιμοποιούμε όταν κάνουμε malloc (pointers), π.χ.: char *s = (char *) malloc(100);

ΔΗΜΗΤΡΗΣ Χ

  • Βετεράνος
  • ****
  • Μηνύματα: 87
Απ: Απορία στην Στοιβα
« Απάντηση #31 στις: 21 Απρ 2021, 05:41:45 μμ »
ΕΓΩ ΘΑ ΗΘΕΛΑ ΝΑ ΘΕΣΩ ΜΙΑ ΕΡΩΤΗΣΗ:
ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ, ΕΝΑ ΘΕΜΑ ΣΑΝ ΤΑ ΠΑΡΑΚΑΤΩ ΕΥΣΤΑΘΕΙ?

Ένας λογιστής συνεργάζεται με τον βοηθό του και τοποθετεί τους φακέλους των πελατών για τους οποίους  θέλει να καταγράψουν όνομα, έσοδα, και έξοδα του καθενός σε ένα αρχείο στον υπολογιστή του. Να φτιάξετε πρόγραμμα το οποίο περιγράφει την διαδικασία ως εξης
Α. χρησιμοποιει τρεις πινακες ον[200], ες[200] και εξ[200] για να πραγματοποιηθεί σε αυτούς η λειτουργία της στοίβας
Β. πραγματοποιείται επαναληπτικά η παρακάτω διαδικασία:
Ο χρήστης επιλέγει ‘Ω’ για τοποθέτηση φακέλου στη στοίβα, ‘Α’ για να πάρει φάκελο ο βοηθός από τη στοίβα ώστε να περαστούν τα στοιχεία όνομα, έσοδα και έξοδα στον υπολογιστή, και ‘Τ’ για τερματισμό και βέβαια πραγματοποιείται κάθε φορά η αντίστοιχη λειτουργία.( Στην περίπτωση της τοποθέτησης φακέλου, θα ελέγχει αν υπάρχει χώρος στην στοίβα, θα διαβάζει το όνομα τα έσοδα και τα έξοδα του πελάτη και θα τα τοποθετεί στην αντίστοιχη στοίβα, διαφορετικά θα εμφανίζει μήνυμα «η στοίβα είναι γεμάτη». Στην περίπτωση της απώθησης, θα ελέγχει αν υπάρχει κάποιο στοιχείο στις στοίβες, θα το εμφανίζει και θα το βγάζει από τη στοίβα, διαφορετικά θα εμφανίζει μήνυμα «η στοίβα είναι Άδεια» .

Γ. για τους φακέλους που τοποθετούνται στη στοίβα μετράει το πλήθος τους και εκτυπώνει πόσοι και ποιοι πελάτες εχουν έσοδα>εξοδα κατά περισσότερο από 10.000 ευρώ
Δ. για τους φακέλους που απωθούνται από τη στοίβα για να περαστούν τα στοιχεία, υπολογίζει και εκτυπώνει μεσο όρο εσόδων και εξόδων καθώς και ποιος είχε τα περισσότερα έσοδα
Ε. . Αν στο τέλος δεν έχει απομείνει κανένας  φάκελος στη στοίβα, εκτυπώνει ‘ η στοιβα άδειασε’, διαφορετικα για τους φακέλους που μετά τον τερματισμό της διαδικασίας έχουν απομείνει στη στοίβα, υπολογίζει και εκτυπώνει πόσοι και ποιοι πελάτες έχουν εσοδα>=20.000 ευρώ, περισσότερα έξοδα και ποιος τα έχει.


Η ΓΝΩΜΗ ΜΟΥ ΕΙΝΑΙ ΟΤΙ - ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ ΜΑΣ - ΕΥΣΤΑΘΕΙ. ΜΕ ΟΤΙ ΓΝΩΣΕΙΣ ΕΧΟΥΝ ΤΑ ΠΑΙΔΙΑ ΑΠΟ ΠΙΝΑΚΕΣ + ΩΘΗΣΕΙΣ ΚΑΙ ΑΠΩΘΗΣΕΙΣ ΜΠΟΡΟΥΝΕ ΝΑ ΤΟ ΔΙΑΧΕΙΡΙΣΤΟΥΝΕ.
ΑΝΑΓΝΩΡΙΖΩ ΟΤΙ ΤΕΧΝΙΚΑ Η ΣΤΟΙΒΑ ΜΕ ΤΗ ΧΡΗΣΗ ΤΗΣ ΕΧΕΙ ΠΟΛΛΕΣ ΦΟΡΕΣ ΠΙΟ ΑΥΣΤΗΡΗ ΧΡΗΣΗ ΜΕΣΩ ΩΘΗΣΕΩΝ ΑΠΩΘΗΣΕΩΝ ΜΟΝΟ, ΑΛΛΑ ΝΟΜΙΖΩ ΟΤΙ ΕΔΩ -  ΣΤΟ ΒΙΒΛΙΟ  ΚΑΙ ΓΕΝΙΚΑ ΣΤΟ ΜΑΘΗΜΑ - ΔΕΝ ΑΝΑΦΕΡΕΤΑΙ ΚΑΠΟΙΟΣ ΤΕΤΟΙΟΣ ΠΕΡΙΟΡΙΣΜΟΣ.

ΕΓΩ ΘΑ ΗΘΕΛΑ ΜΙΑ ΥΠΕΥΘΥΝΗ ΑΠΑΝΤΗΣΗ ΓΙΑ ΤΟ ΑΝ ΤΕΛΙΚΑ ΚΑΤΙ ΤΕΤΟΙΟ ΕΙΝΑΙ ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ ΜΑΣ.
« Τελευταία τροποποίηση: 21 Απρ 2021, 06:45:31 μμ από ΔΗΜΗΤΡΗΣ Χ »

ssimaiof

  • Πληροφορικοί Δυτικής Μακεδονίας
  • *
  • Μηνύματα: 37
Απ: Απορία στην Στοιβα
« Απάντηση #32 στις: 21 Απρ 2021, 06:30:51 μμ »
> Πρόσφατα κάπου διάβασα ότι στοίβα και σωρός άρχισαν να τα διαφοροποιούν.

Είναι εντελώς διαφορετικές δομές stack και heap, αν κάπου/κάποτε διδάχτηκαν ως ίδια, έγινε σοβαρό λάθος...

Στοίβα χρησιμοποιούμε όταν δηλώνουμε τοπικές μεταβλητές, π.χ.: char c = 'a';
Σωρό χρησιμοποιούμε όταν κάνουμε malloc (pointers), π.χ.: char *s = (char *) malloc(100);

Όχι δεν διδάχτηκαν και τα δύο. Όχι το heap. Προφανώς αποτελεί θέμα ελληνικής μετάφρασης των αντίστοιχων αγγλικών όρων. Το stack μεταφράστηκε σε σωρό. Δυστυχώς δεν βρήκα το δικό μου βιβλίο, αλλά βρήκα το Επεξεργασία Δεδομένων σελ. 115 της Γ' τάξης Ενιαίου Πολυκλαδικού Λυκείου (έκδοση 1993) όπου αναφέρει όσα γνωρίζουμε για τη στοίβα χωρίς να αναφέρει πουθενά τον όρο στοίβα αλλά στη θέση της τον όρο σωρό (stack).
Προφανώς από ότι κατάλαβα, όπως τα είπες, ΤΩΡΑ με τον όρο σωρό αναφερόμαστε στο heap.
Ευχαριστώ για τη διευκρίνηση.
Σταύρος Σημαιοφορίδης

ΔΗΜΗΤΡΗΣ Χ

  • Βετεράνος
  • ****
  • Μηνύματα: 87
Απ: Απορία στην Στοιβα
« Απάντηση #33 στις: 21 Απρ 2021, 10:41:44 μμ »
Συνάδελφοι, θα ήθελα τελικα να ξερω κάποια πράγματα για τη στοίβα και την ουρα, ως προς το τι τελικά επιτρέπεται και τι όχι, και το λεω πραγματικά ως ερώτηση και όχι προσπαθώντας να περάσω κάτι.
Επειδή ναι μεν η στοίβα ως δομή και λειτουργια ειναι κάτι πιο αυστηρο ... ωστόσο το βιβλίο γράφει ότι η στοίβα υλοποιείται με μονοδιάστατους πίνακες, ότι 2 είναι οι ΚΥΡΙΕΣ λειτουργιες σε μια στοίβα και οχι οι μοναδικες... και επειδή γενικότερα στο μάθημα θέλουμε οι μαθητές να σκέφτονται ποια εργαλεια θα χρησιμοποιουν και οχι να αποτυπωνουν απλα λυσεις ρωταω τα εξης:
1. μπορουμε να αδειασουμε τη στοιβα με δομη για; πχ τι διαφορα εχουν τα παρακατω (ιδια ερωτηση και για την ουρα)

ΔΙΑΔΙΚΑΣΙΑ αδειασμα( Χ,ΤΟΠ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ι,Χ[100],ΤΟΠ
ΑΡΧΗ
ΑΝ ΤΟΠ<>0 ΤΟΤΕ
     ΓΙΑ Ι ΑΠΟ ΤΟΠ ΜΕΧΡΙ 1 ΜΕ ΒΗΜΑ -1
         ΓΡΑΨΕ 'ΑΠΩΘΕΙΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ',Χ[Ι]
     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
     TOP<-0
ΑΛΛΙΩΣ
      ΓΡΑΨΕ ' ΑΔΕΙΑ ΣΤΟΙΒΑ'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

ΔΙΑΔΙΚΑΣΙΑ αδειασμα( Χ,ΤΟΠ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ι,Χ[100],ΤΟΠ
ΑΡΧΗ
ΑΝ ΤΟΠ<>0 ΤΟΤΕ
     ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
         ΓΡΑΨΕ 'ΑΠΩΘΕΙΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ',Χ[ΤΟΠ]
         ΤΟΠ<-ΤΟΠ-1
     ΜΕΧΡΙΣ_ΟΤΟΥ ΤΟΠ=0
ΑΛΛΙΩΣ
      ΓΡΑΨΕ ' ΑΔΕΙΑ ΣΤΟΙΒΑ'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

και
2. μπορουμε μετα το πέρας μιας διαδικασιας βαλε-βγάλε, να επεξεργαστουμε τα στοιχεια της στοιβας σαν στοιχεία πίνακα, όπως στο θέμα που εχω ανεβάσει 2 απαντησεις πιο πάνω; και για να το θέσω αλλιώς,απαγορεύεται Άραγε να χρησιμοποιηθεί η δομή μιας στοίβας με τις λειτουργίες της ώστε να προσομοιώσει ένα μοντέλο σαν το παραπάνω; Αν και αυτο ειναι θεμα θεματων ... οπότε αν δεν γίνεται δεν θα ζητηθεί άρα δεν πειραζει, αλλά τουλάχιστον να μην κανουμε τετοιες ασκησεις. ενω το πρωτο ερωτημα ειναι θεμα απάντησης από τον μαθητη

Θα ήθελα μια υπευθυνη τοποθετηση απο κάποιον αν ξερει.
ευχαριστω πολυ.



« Τελευταία τροποποίηση: 21 Απρ 2021, 11:39:12 μμ από ΔΗΜΗΤΡΗΣ Χ »

thaaanos

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Απορία στην Στοιβα
« Απάντηση #34 στις: 23 Απρ 2021, 10:05:25 πμ »
Πιο σωστό είναι για εμενα το δεύτερο γιατι σε κάθε απώθηση ενημερώνεται το TOP. και όχι μια και καλη στο τέλος. Το πρόβλημα θα ήταν πιο προφανές ισως αν είχες παραλληλισμό και πολλές διεργασίες χρησιμοποιούσαν την στοιβα, δεν θες τότε μετά από κάθε απώθηση να μεινει η στοιβα σε ασυνεπή κατάσταση.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5870
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Απορία στην Στοιβα
« Απάντηση #35 στις: 23 Απρ 2021, 10:38:17 πμ »
Δηλαδή η διαδικασία "εισαγωγή" στην ουρά επιτρέπεται να κάνει ολίσθηση χρησιμοποιώντας την ουρά σαν πίνακα, με πρόσβαση στα ενδιάμεσα στοιχεία της πέρα από την αρχή και το τέλος της,
αλλά δεν επιτρέπεται να κάνουμε το ίδιο στη στοίβα;

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

Με άλλα λόγια, επιμένω ότι η απευθείας πρόσβαση σε στοιχεία των δομών θα έπρεπε να μην είναι ταμπού, χρησιμοποιείται συχνά σε αυτές τις δομές μέχρι και με υποστήριξη εντολών του hardware. Γιατί να επιτρέπονται οι παραλλαγές της ταξινόμησης φυσαλίδας, π.χ. με "σημαία" ή κάνοντας μόνο 10 επαναλήψεις για να βρούμε τους 10 μεγαλύτερους αριθμούς, και να μην επιτρέπονται οι παραλλαγές στη στοίβα π.χ. με εντολές τύπου peek(top-2);
ΟΚ, οι δομές αυτές είναι ακόμα φρέσκες στην ύλη και να μην βάλουμε ακόμα δύσκολες ασκήσεις, αλλά μην φτάνουμε στο σημείο να αναφέρουμε τις παραλλαγές τους σαν αντι-επιστημονικές...

thaaanos

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Απορία στην Στοιβα
« Απάντηση #36 στις: 23 Απρ 2021, 11:56:52 πμ »
Νομιζω οτι υπάρχει μια παρανόηση σχετικά με το Χρήστη σε σχέση με τον Προγραμματιστή της Δομής.
Ο Χρήστης δεν μπορεί να χρησιμοποιήσει την δομή παρα μόνο μέσω των λειτουργιών που προσφέρει ο Προγραμματιστής της.
Ακόμα και αν αυτός είναι το ίδιο πρόσωπο.

Η απευθείας πρόσβαση από τον χρήστη στα περιεχόμενα της δομής είναι προβληματική, γιατί δεν υπάρχει καμία εγγυηση οτι τα δεδομένα παραμένουν στην ίδια θέση. Πχ μπορεί μια λειτουργεία να προκαλέσει αναδιάταξη των δεδομένων στην δομή οπότε ότι δείκτες ή θέσεις είχαμε για κάποιο στοιχείο δεν είναι πια έγκυρο

Μπορεί μια υλοποίηση πχ της Ουράς να χρησιμοποιεί μεν πίνακα αλλα τα στοιχεία να είναι κύκλικά τοποθετημένα πχ, τοτέ το
Για Ι από Front μέχρι Rear να μήν σκαναρει τίποτα γιατί μπορέι κάλλιστα το Front > Rear

ΔΗΜΗΤΡΗΣ Χ

  • Βετεράνος
  • ****
  • Μηνύματα: 87
Απ: Απορία στην Στοιβα
« Απάντηση #37 στις: 23 Απρ 2021, 12:12:10 μμ »
Πιο σωστό είναι για εμενα το δεύτερο γιατι σε κάθε απώθηση ενημερώνεται το TOP. και όχι μια και καλη στο τέλος. Το πρόβλημα θα ήταν πιο προφανές ισως αν είχες παραλληλισμό και πολλές διεργασίες χρησιμοποιούσαν την στοιβα, δεν θες τότε μετά από κάθε απώθηση να μεινει η στοιβα σε ασυνεπή κατάσταση.

Θάνο Σε ευχαριστώ για τη τοποθέτησή σου η οποία έχει λογική και συμφωνώ εν μερει. Ωστόσο όταν πάμε για κάποιο άδειασμα όπως για παράδειγμα στην λυμένη άσκηση του βιβλίου με το πλοίο, δεν μας ενδιαφέρον οι ενδιάμεσες καταστάσεις. Αλλα Αν ακόμα γίνει και αυτό και θες να ελέγχεις ενδιάμεσα τη στοιβα, μπορείς μέσα στη για να βάλεις τις κατάλληλες εντολές. γενικά πιστεύω ότι πρέπει να μελετάται ως μία δομή πίνακα και απλά με τις λειτουργίες ώθηση και απώθηση, να προσομοιώνονται τα διάφορα προβλήματα και αυτό έχω καταλάβει από τις αναφορές των βιβλίων του μαθήματος.
Θα συμφωνήσω πλήρως με τις παρατηρήσεις του Άλκη και γενικά νομίζω ότι κακώς τίθενται αυτοί οι περιορισμοί.
Δηλαδή στοιβα - ουρα = μονοδιάστατοι πίνακες συνοδευόμενοι με τις αναφερόμενες στο βιβλίο λειτουργίες και με ασκήσεις επικεντρωμένες μεν σε αυτές τις βασικές λειτουργίες χωρίς όμως τρελούς περιορισμούς που έχουν να κάνουν με τεχνικά θέματα. Και βέβαια ως πρώτη χρονιά ουσιαστικά για αυτές τις δομές, θα συμφωνήσω με τον Άλκη πάλι ότι καλό είναι να είμαστε λίγο συγκρατημένοι.
Τελευταιο πάλι όμως θα γράψω ότι θα ήθελα να γινόταν μία υπεύθυνη τοποθέτηση, παρότι νομίζω, και το τονίζω ότι νομίζω, ότι το όλο θέμα κακώς διυλίζεται τόσο.
(Συμπεριλαμβανομένου και εμένα :D)
« Τελευταία τροποποίηση: 23 Απρ 2021, 02:31:51 μμ από ΔΗΜΗΤΡΗΣ Χ »

thaaanos

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Απορία στην Στοιβα
« Απάντηση #38 στις: 23 Απρ 2021, 12:19:37 μμ »
Να σήμειώσω εδώ οτι ο αλγόριθμος εισαγωγής/ εξαγωγής σε στοίβα και ουρά ειναι **ανεξάρτητος** από την υλοποιηση και γιαυτό επιμένω να ακολουθείτε η λογική του ακόμα και αν δεν δινεται ως υποπρόγραμμα.
και εξηγώ

υποθέστε 1 γραμμική αποθήκη Q, 2 δείκτες που δειχνουν την αρχή και το τέλος, f,r

εισαγωγή Δ:
 προχώρα το f κατα μία θέση
 τοποθέτησε το Δ στην θέση f

Εξαγωγή Δ
 Πάρε το Δ από την θέση r
 προχώρα το r κατα μια θέση

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

 

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3564
  • to Iterate is human to Recurse divine
Απ: Απορία στην Στοιβα
« Απάντηση #39 στις: 23 Απρ 2021, 11:29:51 μμ »
Δηλαδή η στοίβα που υλοποιείται με δυναμική δομή δεδομένων δεν είναι στοίβα? Είναι άλλη δομή?
Επίσης αν αυτά είναι πίνακες τι κουραζόμαστε με ορισμούς στοίβας και ουράς? Γιατί να μην μιλάμε κατευθείαν για πίνακες? Τι παραπάνω κερδίζουμε;
Για ποιον λόγο να χρησιμοποιούμε ώθηση/απώθηση αφού μπορούμε να έχουμε πρόσβαση σε οποιοδήποτε στοιχείο του πίνακα-στοίβα;

Δηλαδή στοιβα - ουρα = μονοδιάστατοι πίνακες συνοδευόμενοι με τις αναφερόμενες στο βιβλίο λειτουργίες και με ασκήσεις επικεντρωμένες μεν σε αυτές τις βασικές λειτουργίες χωρίς όμως τρελούς περιορισμούς που έχουν να κάνουν με τεχνικά θέματα.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 793
Απ: Απορία στην Στοιβα
« Απάντηση #40 στις: 24 Απρ 2021, 12:18:08 πμ »
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2349
Απ: Απορία στην Στοιβα
« Απάντηση #41 στις: 24 Απρ 2021, 01:20:37 πμ »
Δηλαδή η στοίβα που υλοποιείται με δυναμική δομή δεδομένων δεν είναι στοίβα? Είναι άλλη δομή?
Επίσης αν αυτά είναι πίνακες τι κουραζόμαστε με ορισμούς στοίβας και ουράς? Γιατί να μην μιλάμε κατευθείαν για πίνακες? Τι παραπάνω κερδίζουμε;
Για ποιον λόγο να χρησιμοποιούμε ώθηση/απώθηση αφού μπορούμε να έχουμε πρόσβαση σε οποιοδήποτε στοιχείο του πίνακα-στοίβα;

Ευρυπίδη, θα έλεγα το εξής απλό
Το ότι υλοποιείται με πίνακα δεν σημαίνει ότι μπορείς να έχεις πρόσβαση σε οποιοδήποτε στοιχείο γιατί τότε "κλέβεις" και ουσιαστικά δεν υλοποιείς στοίβα
Σίγουρα δεν υπάρχει η αναγκαστική προσπέλαση κόμβο-κόμβο όπως σε μια συνδεδεμένη λίστα, αλλά και πάλι, αν βάζεις τον μαθητή να υλοποιήσει μια στοίβα με πίνακα, τον αναγκάζεις να προσπελαύνει μόνο τον κόμβο της κορυφής, αλλιώς η λύση του είναι λανθασμένη, αφού δεν υλοποιεί στοίβα με χρήση πίνακα, αλλά απλά χρήση πίνακα

Φυσικά και θα κουραζόμαστε με τους ορισμούς της στοίβας και ουράς, γιατί αλλιώς ο μαθητής δεν μπορεί να κατανοήσει ότι μιλάμε για κάτι πολύ συγκεκριμένο και όχι απλά για μια (ακόμη) άσκηση με πίνακες
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5870
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Απορία στην Στοιβα
« Απάντηση #42 στις: 24 Απρ 2021, 10:18:57 πμ »
...τον αναγκάζεις να προσπελαύνει μόνο τον κόμβο της κορυφής, αλλιώς η λύση του είναι λανθασμένη, αφού δεν υλοποιεί στοίβα με χρήση πίνακα...

Τέλεια αφορμή για να πετάξω την απορία μου:
Γιατί στη λύση της άσκησης με το ταχυδρομείο προσπελαύνουμε άμεσα τα στοιχεία του πίνακα της ουράς, αντί να προσπελαύνουμε μόνο το Ουρά[δείκτης_αρχής] ή το Ουρά[δείκτης_τέλους];
Η λειτουργία ολίσθησης στις ουρές που "πρέπει να διδάξουμε", πώς υλοποιείται όταν εσωτερικά χρησιμοποιούμε δείκτες αντί για πίνακες;

Δεν υπάρχει αντίφαση εκεί; Η στοίβα είναι "αφηρημένη δομή" αλλά η ουρά "υλοποιείται με απευθείας πρόσβαση σε ενδιάμεσα στοιχεία ενός πίνακα";
Δεν μπορούμε να έχουμε ενιαία αντιμετώπιση και στις δύο δομές;

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2349
Απ: Απορία στην Στοιβα
« Απάντηση #43 στις: 24 Απρ 2021, 10:48:10 πμ »
Ποια άσκηση είναι αυτή Άλκη;
Αν θέλεις, δώσε λίγο το σημείο που αναφέρεσαι
Δεν έχω ασχοληθεί σοβαρά με τις ασκήσεις που έχει το νέο τεύχος
Θεωρώ ότι έχουν τρύπες ή είναι υπερβολικά πολύπλοκες οι λύσεις που παρουσιάζονται
Προτίμησα να δώσω δικές μου ασκήσεις
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5870
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Απορία στην Στοιβα
« Απάντηση #44 στις: 24 Απρ 2021, 11:19:39 πμ »
Πέτρο λέω για τις ενδεικτικές λύσεις ασκήσεων:
http://ebooks.edu.gr/ebooks/d/8547/5296/22-0263-01_Pliroforiki-G-Lykeiou-SpOikPlir_Lyseis-Askiseon.pdf

Σελίδα 19, γραμμή 40:

Κώδικας: ΓΛΩΣΣΑ
  1. ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ αθρ
  2.     πινακας_επιθετων[i] <- πινακας_επιθετων[αρχ - 1 + i]
  3. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Κάνει απευθείας πρόσβαση στα στοιχεία της ουράς, για να τα κάνει ολίσθηση προς τα αριστερά, για να χωρέσει η ουρά κι άλλα στοιχεία.
Ε δεν μπορούμε από τη μία να το διδάσκουμε αυτό και από την άλλη να λέμε για αφηρημένες δομές δεδομένων, είναι αντίφαση.

Για να μην παρεξηγηθώ, εγώ εννοώ ότι:
  • Είμαι κατά της ολίσθησης, αφού εκτός από τη λάθος πολυπλοκότητα Ο(Ν), δεν υφίσταται καν σαν έννοια αν υλοποιήσουμε ουρά με δείκτες.
  • Όπως είπε ο Θάνος παραπάνω, είμαι υπέρ του: ο "χρήστης" της "βιβλιοθήκης στοίβα/ουρά" δεν πρέπει να ξέρει την εσωτερική αναπαράσταση. Για μένα αυτό σημαίνει αφηρημένη δομή, ο ορισμός του API μιας βιβλιοθήκης.
  • Όμως θεωρώ ότι εμείς διδάσκουμε και "προγραμματιστές" της "βιβλιοθήκης στοίβα/ουρά", άρα υπό εκείνο το πρίσμα, επιτρέπεται να μιλήσουμε για εσωτερική αναπαράσταση.
  • Τέλος, το να κάνουμε μικροαλλαγές στο API της στοίβας/ουράς δεν σημαίνει ότι κάναμε ιεροσυλία, ούτε ότι ξαφνικά σταμάτησαν να είναι ουρές και στοίβες. Ακόμα και το API εξαρτάται από το δοθέν πρόβλημα. Αν το πρόβλημα που θέλω να λύσω απαιτεί συνάρτηση Peek(top - 1), και την υλοποιήσω, πάλι στοίβα είναι, ελαφρώς προσαρμοσμένη χωρίς να χάνονται οι χαρακτηριστικές της ιδιότητες.