Αποστολέας Θέμα: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ  (Αναγνώστηκε 14324 φορές)

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2450
  • I 'm not young enough to know everything
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #30 στις: 05 Ιαν 2006, 11:42:16 πμ »
Βαγγέλη δεν έχω καταλάβει τι ακριβώς προσπαθείς να στηρίξεις. Κάπου σε χάνω.

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

Η ώθηση και η απώθηση έχουν να κάνουν με την αφηρημένη δομή δεδομένων. Είναι οι επιτρεπόμενες πράξεις της δομής. Είτε τις υλοποιήσεις στατικά είτε δυναμικά μπορείς να κάνεις ώθηση και απώθηση.

Αν υλοποιήσεις μια ουρά στατικά (έστω με πίνακα 100 θέσεων) τότε η ουρά σου μπορεί να έχει μέσα μέχρι 100 στοιχεία. Δε σημαίνει ότι πάντα έχε 100 στοιχεία μέσα της. Σημαίνει ότι το μέγιστο μήκος της είναι τα 100 στοιχεία. Επειδή στους πίνακες ο χώρος στη μνήμη δεσμεύεται εξαρχής, είτε έχεις μέσα 50 είτε 100 στοιχεία ο χώρος που έχει δεσμευτεί  στη μνήμη είναι 100. Είναι δηλαδή σταθερός (στατικός). Για αυτό η υλοποίηση με πίνακα λέγεται στατική.

Αν την κάνεις με δείκτη τότε δεν έχεις ορίσει εξαρχής κάποιο μέγεθος. Κάθε φορά που θέλεις να βάλεις ένα καινούργιο στοιχείο δεσμεύεις εκείνη τη στιγμή χώρο μόνο για ένα στοιχείο (dynamic memory allocation),βάζεις μέσα το στοιχείο και το κολλάς στην ουρά. Σε αυτή την περίπτωση ο χώρος που είναι κάθε στιγμή δεσμευμένος στη μνήμη είναι ανάλογος των στοιχείων που έχεις μέσα. Δεν είναι λοιπόν σταθερός αλλά μεταβάλλεται δυναμικά. Γι αυτό η υλοποίηση με δείκτες λέγεται δυναμική.

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

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3190
  • I love you 3000
    • Panagiotis Tsiotakis
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #31 στις: 10 Ιαν 2006, 10:12:48 πμ »
Στο διδακτικό πακέτο της ΑΕΠΠ η υλοποίηση της στοίβας και της ουράς (ακόμη και η θέση των παραγράφων 3.4 και 3.5 στο κεφάλαιο 3) μας οδηγούν στο συμπέρασμα οτι είναι στατικές δομές δεδομένων. Στην ύλη μας ΔΕΝ ΥΠΑΡΧΟΥΝ δυναμικές δομές δεδομένων
Και αυτή δεν είναι η επικρατούσα άποψη, αλλά η δική μου άποψη

Όταν πρωτοπαρουσιάζουμε την έννοια του πίνακα στους μαθητές και σχεδιάζουμε στο χαρτί έναν μονοδιάστατο πίνακα ΣΥΝΕΧΟΜΕΝΕΣ δεν είναι οι θέσεις του (κελιά); Δεν μπορώ να καταλάβω πως θα υπάρχει παρανόηση από τους μαθητές σε ένα απλό θέμα που στο κάτω κάτω είναι και θέμα ορισμού

Ούτε στο σταθερό μέγεθος του πίνακα μπορεί να υπάρξει παρανόηση, δεν μπορεί να υπάρχει στοιχείο Ν+1 σε έναν πίνακα Α[Ν], ούτε και σε μια στοίβα Ν θέσεων απο τη στιγμή που υλοποιείται με μονοδιάστατο πίνακα. Όμοια δεν μπορεί να υπάρξει μηδέν στον παρονομαστή ενός κλάσματος

Αυτά οι μαθητές πρέπει και να τα μάθουν και να τα ξέρουν

Η ομάδα συζήτησης δεν υπάρχει (νομίζω) για να εγκαλεί κανέναν στην επικρατούσα άποψη. Και να το ήθελε, αυτό δεν είναι εφικτό καθώς συμμετέχουν και αναγνώσκουν 300 και υπάρχουν άλλοι 4.300 καθηγητές

Με εκτίμηση,

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2450
  • I 'm not young enough to know everything
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #32 στις: 12 Ιαν 2006, 11:43:22 πμ »
Υπάρχει ένα λεπτό ζήτημα. Οι στοίβα και η ουρά  μπορούν να είνα είτε στατικές είτε δυναμικές ανάλογα με την υλοποίηση.  

Στις παραγράφους 3.4 και 3.5 αφού παρουσιαστούν οι πράξεις, λέει και 2 λόγια για την υλοποίηση.

Στην 3.4 λέει "Μια στοίβα μπορεί να υλοποιηθεί πολύ εύκολα με τη βοήθεια ενός μονοδιάστατου πίνακα"

Στην 3.5 λέει "Μια ουρά μπορεί να υλοποιηθεί με τη βοήθεια ενός μονοδιάστατους πίνακα . . . "

Σε αυτά τα σημεία το βιβλίο αναφέρει μια πιθανή υλοποίηση, την πιο απλή. Δε σημαίνει ότι οι στοίβα και οι ουρά είναι στατικές σώνει και καλά. Άπλά λέει 2 λόγια για τη στατική υλοποίηση. Σα να λέει δηλαδή "μπορεί να υλοποιηθεί στατικά". Δε σημαίνει ότι είναι πάντα στατική.


Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3190
  • I love you 3000
    • Panagiotis Tsiotakis
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #33 στις: 13 Ιαν 2006, 09:28:18 πμ »

Υπάρχει η έννοια της υπερχείλισης σε μια δυναμική δομή δεδομένων;;

(στατική = σταθερό πλήθος θέσεων)

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2450
  • I 'm not young enough to know everything
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #34 στις: 13 Ιαν 2006, 11:13:33 πμ »
Ναι. Μπορεί να πρέπει να προσομοιωθεί στοίβα/ουρά μέχρι πχ 1000 θέσεις και να γίνει δυναμική υλοποίηση. Θα υπάρχει μετρητής που θα κρατάει το πλήθος. Έλεγχος για υπερχείλιση θα γίνεται. Αλλά κάθε στιγμή ο χώρος που θα δεσμεύεται θα είναι ανάλογος με το πλήθος των μελών της δομής και όχι σταθερός. Έτσι η υλοποίηση θα είναι δυναμική (με δείκτες και όχι με πίνακα).

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

Όπως και να έχει το πράγμα η στοίβα και η ουρά μπορούν να είναι στατικές ή δυναμικές ανάλογα με την υλοποίηση, ανεξάρτητα από το τι λέει το βιβλίο. Νομίζω πως το βιβλίο τα αναφέρει κάπως περιληπτικά χωρίς να σκοτιστεί με τις λεπτομέρειες. Για παράδειγμα αν διαβάσεις την παράγραφο για την ουρά και δεις το σχήμα θα παρατηρήσεις ότι όσο πάει τα στοιχεία της ουράς προχωράνε προς τα δεξιά. Κάποια στιγμή θα φτάσουν στο τέρμα. Και μετά; Προφανώς θα αρχίζουν να γεμίζουν από τις πρώτες θέσεις, αλλά αυτό δεν το λέει το βιβλίο. Λέει μόνο ότι οι δείκτες αυξάνουν κατά ένα. Θέλω να πω ότι δε συμφωνώ με το να στεκόμαστε κατά λέξη στο τι λέει το βιβλίο. Εγώ βλέπω ποιες έννοιες αναφέρει και εξηγώ πως έχουν τα πράγματα. Είμαι βέβαιος ότι και οι συγγραφείς αυτό θέλουν από μένα. Μπορεί να τους ξέφυγε κάτι ή να μην το διατύπωσαν όσο σωστά θα ήθελαν. Δεν έρχομαι σε αντίθεση με το βιβλίο κάνοντας κάτι τέτοιο. Το κάνω σε περιοχές που υπάρχει ασάφεια και δεν είναι κατανοητό αυτό που θα ήθελε να πει ο συγγαφέας. Δεν το κάνω στο κριτήριο της περατότητας που είναι σαφές τι θέλει να πει το βιβλίο αλλά εγώ διαφωνώ.

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


gkark

  • Θαμώνας
  • ***
  • Μηνύματα: 20
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #35 στις: 13 Ιαν 2006, 12:35:09 μμ »
Εστω ότι στις πανελλήνιες υπάρχουν σε ερώτησεις σωστου λαθους οι εξής προτάσεις:
Η στοιβα είναι στατικη δομη.
Η ουρά ειναι δυναμική δομη.
Τι απαντάνε οι μαθητές;
Αν  οι προτάσεις είναι πιο καθορισμένες και αναφέρουν οτι η υλοποίησης της δομής γίνεται με πίνακα τότε η απάντηση είναι ευκολή.
Αν όμως δεν το αναφέρουν τότε τι πρέπει να απαντήσουν οι μαθητές;

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2450
  • I 'm not young enough to know everything
Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #36 στις: 13 Ιαν 2006, 01:14:52 μμ »
Η θέση μου είναι ότι θα είναι λάθος τους αν βάλουν τέτοιο θέμα. Η σωστή απάντηση είναι ότι οι 2 δομές μπορούν να είναι στατικές ή δυναμικές ανάλογα με την υλοποίηση αλλά ο μαθητής δεν έχει επίσημα γραπτά στοιχεία για να ξέρει και να απαντήσει κάτι τέτοιο.


daidalos69

  • Νέος
  • *
  • Μηνύματα: 4
  • Arimba-arimbaaaaa!!!
Απ: Re: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #37 στις: 05 Απρ 2008, 06:08:39 μμ »
 :o 8) ??? ::) :P :-[ :angel: :'( ;) :)
Κυριε μου,θαρρω πως ειστε πολυ σωστος θετοντας τετοιες αποριες.........
Γεια χαρα........

_sleeper

  • Οπαδός
  • **
  • Μηνύματα: 16
Απ: ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ
« Απάντηση #38 στις: 06 Αύγ 2008, 06:25:42 μμ »
αν κ πέρα για πέρα ετεροχρονισμένα θα καταθέσω κ εγώ την άποψή μου για το θέμα. όλοι γνωρίζουμε οτι οποιαδήποτε δομή μπορεί να υλοποιηθεί με οποιοδήποτε τρόπο. μπορώ να σου κάνω ουρά με διπλά συνδεδεμένη λίστα, στοίβα, που θα υλοποιείται με απλή λίστα ή διάνυσμα ή ουρά ή οτιδήποτε, κοκ. αυτά όλα είναι γνωστά σε εμάς. το θέμα, όμως, είναι οτι για εκπαιδευτικούς σκοπούς (κ όχι μόνο) η στοίβα κ η ουρά ΠΡΕΠΕΙ να θεωρούνται στατικές δομές, έτσι ώστε να υπάρχει η σύγκριση με τις λίστες, τους γράφους, τα δέντρα, κτλ. καλώς ή κακώς η στοίβα/ουρά υλοποιείται κατά κύριο λόγο με τη χρήση πίνακα, οπότε αυτό αυτομάτως την κάνει στατική δομή. ένας μαθητής της τεχνολογικής πιστεύω πως μπορεί να αρκεστεί σ'αυτή την "ψευδή" γνώση. η απάντηση που εγώ δίνω είναι η εξής: η ουρά κ η στοίβα για εσάς είναι στατική δομή δεδομένων.

άλλωστε δεν υπάρχει εκπαιδευτικό ενδιαφέρον να διδάσκεται η στοίβα/ουρά (και) ως δυναμική δομή. η χρήση της ουράς κ της στοίβας γίνεται για την εξοικίωση με την έννοια των πινάκων κ τις έννοιες FIFO, LIFO κ όχι για αυτές καθεαυτές τις δομές. δεν πρόκειται να γίνουν προγραμματιστές τα περισσότερα από αυτά τα παιδιά, οπότε το να γνωρίζουν οτι η ουρά μπορεί να υλοποιηθεί κ με στατικό κ δυναμικό τρόπο, ξεφεύγει από τα όρια του μαθήματος πιστεύω.
what better place than here, what better time than now!