ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ

Ξεκίνησε από kinik, 02 Δεκ 2005, 08:28:34 ΠΜ

« προηγούμενο - επόμενο »

kinik

Γεια σε όλους. Θα ήθελα να αναφερθώ σε ένα θέμα που διάβασα σε κάποιο βοήθημα σχετικό με το μάθημα. Συγκεκριμένα το βοήθημα αναφέρεται σε δυνάμικές δομές δεδομένων και αναφέρει σε αυτές τη στοίβα και την ουρά.
Προσωπικά πιστεύω ότι είναι λάθος για δύο λόγους:
1. Η υλοποίηση και των δύο δομών γίνεται με πίνακα και συνεπώς το μέγεθος της δομής περιορίζεται.
2. Τα στοιχεία αποθηκευόνται σε συνεχομένες θέσεις μνήμης.
Ποια είναι η γνώμη σας πάνω σε αυτό το θέμα?

chaos

Καλημέρα Kinik,

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

Ευχαριστώ,
Σωτήρης

kinik

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

EleniK

Θα συμφωνήσω με το συνάδελφο chaos σχετικά με το ότι η στοίβα και η ουρά είναι δυναμικές δομές δεδομένων. Εκτός του ότι δεν αναφέρει ότι τα δεδομένα αποθηκεύονται σε συνεχόμενες θέσεις μνήμης έχουν και μη σταθερό μέγεθος. Μέσα στο βιβλίο στις δυναμικές δομές, αναφέρει οτι εκτός της δυναμικής παραχώρησης μνήμης χαρακτηριστικό τους είναι ότι δεν έχουν σταθερό μέγεθος.
΄
Ελένη
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

P.Tsiotakis

Συνάδελφοι, στο βιβλίο μαθητή (σελίδα 59) αναφέρει οτι οι στοίβα και η ουρά υλοποιούνται με πίνακες (που είναι στατικές δομές). Επομένως οι δομές δεδομένων στοίβα και ουρά είναι στατικές

Άλλωστε, οι δομές αυτές:
1. Αποθηκεύουν τα στοιχεία τους σε συνεχόμενες θέσεις μνήμης, κάτι που δηλώνουν οι δείκτες top και rear
2. Έχουν σταθερό μέγεθος, αλλιώς τι νόημα θα είχε η υπερχείλιση;

3. Στην παράγραφο 3.9 (εκτός ύλης) ξεκινάει τις ΑΛΛΕΣ δομές δεδομένων που είναι οι δυναμικές.

Κάθε βοήθημα, μπορεί να λέει ο,τι θέλει κατά τα άλλα  :juggle: . Ας προσέχουμε λίγο παραπάνω

kinik

Θα συμφωνήσω και εγώ με τον συνάδελφο ptsiotaki. Εγώ σε αυτό που διαφωνώ με το βοήθημα είναι ότι παρουσιάζει τη συγκεκριμένη υλοποίηση στοίβας και ουράς ως δυναμική δομή. Αν όντως πρόκειται για δυναμικές δομές τι νόημα έχει η υπερχείλιση όπως είπε ο ptsiotakis. Επίσης η λειτουργία της ώθησης και της απώθησης όπως περιγράφονται στο σχολικό βιβλίο (δείκτης top - push top+1 και pop top-1) δε δηλώνουν ότι τα στοιχεία αποθηκεύονται σε συνεχομένες θέσεις μνήμης?
Η ερώτηση αφορούσε τα γραφόμενα στο βιβλίο και όχι τη γενική περίπτωση στοίβας.
Εγώ πιστεύω ότι στο βιβλίο οι συγγραφείς θέλησαν να παρουσιάσουν τη στοίβα και την ουρά ως στατικές δομές δεδομένων που παρέχουν ένα συγκεκριμένο τρόπο επεξεργασίας.

kinik

Η φράση οι  δυναμικές δομές δεν έχουν σταθερό μέγεθος αναφέρεται στο αν γνωρίζουμε κατά τον προγραμματισμό το ακριβές μέγεθος μνήμης που θα καταλάβει η δομή ή όχι. Ένα πίνακας Ν θέσεων μπορεί να έχει τιμές στις πρώτες 50 θέσεις. Αυτό δεν σημαίνει ότι είναι και δυναμική δομή. Το ίδιο και στη συγκεκριμένη υλοποίηση στοίβας όπου χρησιμοποιείται πίνακας. Το μέγιστο πληθος στοιχείων πρέπει να είναι γνωστό.
Ευχαριστώ.

chaos

Γεια σας και πάλι,

Νομίζω ότι συμφωνούμε όλοι ότι το σχολικό βιβλίο παρουσιάζει την υλοποίηση της στοίβας και της ουράς με τη χρήση μόνο στατικών δομών. Γι' αυτό και η ώθηση και η απώθηση αφορούν συνεχόμενες θέσεις μνήμης. Ελπίζω επίσης ότι όλοι συμφωνούμε ότι η στοίβα και η ουρά δεν είναι απαραίτητο να υλοποιηθούν με τη χρήση μόνο στατικών δομών. Αυτό που νομίζω ότι είναι απαραίτητο να διευκρινιστεί στους μαθητές μας (ειδικά αν κάνουν χρήση του συγκεκριμένου βοηθήματος) είναι ότι στο συγκεκριμένο μάθημα βλέπουν ΜΟΝΟ στατικές δομές και το παράδειγμα δημιουργίας στοίβας και ουράς ως στατικές δομές περιγράφεται στο βιβλίο τους.
Αν βέβαια κάποιος επιθυμεί να δώσει και παραδείγματα δημιουργίας δυναμικής στοίβας ή ουράς ως επιπλέον πληροφορία στο μάθημα ή στο βιβλίο που γράφει ας το κάνει στο μέτρο που δεν αφήνει σκοτεινά σημεία. Κάτι που νομίζω ότι γίνεται στο συγκεκριμένο παράδειγμα κρίνοντας από την επισήμανση του kinik.

kinik

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

Ευχαριστώ και πάλι.

BlackPainter

Το αν μία δομή είναι στατική ή δυναμική έχει να κάνει με την υλοποίησή της?(για όνομα του θεού) δηλαδή αν εγώ έκανα υλοποίηση γράφου ή δέντρου με πίνακα θα λέγαμε ότι είναι στατική δομή?Anyway νομίζω ότι είναι ακόμα ένα σκοτεινό σημείο του βιβλίου. Εγώ νομίζω ότι πουθενά δεν αναφέρεται ότι οι θέσεις είναι συνεχόμενες και οι τρεις τελείες του βιβλίου στα σχηματάκια δείχνουν ότι δεν ξέρουμε το μέγεθος άρα.....

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

Μήπως να αναρωτηθούμε για το τι καταλαβαίνουν και αυτοί οι κακόμοιροι διαβάζοντας?(Αυτό θα μπορούσε να αποτελεί και ξεχωριστό topic i guess)

Χρόνια πολλά και ελπίζω να μας μπει σε όλους καλά

sgsfak

ΠαράθεσηΤο αν μία δομή είναι στατική ή δυναμική έχει να κάνει με την υλοποίησή της?(για όνομα του θεού) δηλαδή αν εγώ έκανα υλοποίηση γράφου ή δέντρου με πίνακα θα λέγαμε ότι είναι στατική δομή?
Θα είχες μια στατική δομή δεδομένων που υλοποιεί τη λειτουργικότητα και έχει τα χαρακτηριστικά του γράφου ή του δέντρου.  :D

Νομίζω ότι θα πρέπει  να ξεχωρίσουμε τις Αφηρημένες Δομές Δεδομένων (Abstract Data Structures) από τις "συγκεκριμένες" δομές δεδομένων που υλοποιούν ή εξειδικεύουν τις ΑΔΔ θέτοντας παραπάνω περιορισμούς στη χρήση ή τη λειτουργικότητα τους. Η στοίβα και η ουρά είναι παραδείγματα ΑΔΔ και ο ορισμός τους γίνεται με βάσει τη λειτουργικότητα που παρέχουν, π.χ. σε μια στοίβα (S) μπορείς σε γενικές γραμμές να κάνεις τα εξής: να εισάγεις ένα νέο στοιχείο (push) και να εξάγεις ένα παλιό (pop) και ισχύει πάντα η συνθήκη ότι pop(push(S,e)) = e δηλ. εξάγεται το στοιχείο που εισήχθη τελευταίο. Με βάσει αυτά δεν γίνεται πουθενά αναφορά το αν είναι στατική ή δυναμική δομή δεδομένων και επομένως αυτό έχει να κάνει με την υλοποίηση της.

Και υπάρχουν αρκετές υλοποιήσεις/εξειδικεύσεις για στοίβες και ουρές με διαφορετικά χαρακτηριστικά κάθε μία. Π.χ. για την υλοποίηση ενός buffer χρησιμοποιείται συνήθως στατική υλοποίηση της ουράς (δηλ. έχει στατικά καθορισμένο μέγιστο μέγεθος) ενώ για ένα σύστημα παραγωγού καταναλωτή χρησιμοποιείται συνήθως στατική ουρά αλλά με επιπλέον blocking χαρακτηριστικά έτσι ώστε ο καταναλωτής να "περιμένει" όταν πάει να βγάλει ένα στοιχείο από άδεια ουρά και ομοίως να "περιμένει" ο παραγωγός όταν πάει να  εισάγει ένα στοιχείο σε γεμάτη ουρά.

Όσον αφορά το γράφο και το δέντρο πρόκειται και εδώ για ΑΔΔ των οποίων ο ορισμός δεν ασχολείται με το αν έχουν μέγιστο μέγεθος ή όχι, αλλά αναφέρει τα συγκεκριμένα χαρακτηριστικά που έχουν (π.χ. ο γράφος αποτελείται από ένα σύνολο κορυφών και ένα σύνολο ακμών που τις συνδέουν). Το στατικό ή δυναμικό των δομών δεδομένων συνήθως παρουσιάζεται κατά την υλοποίηση εκτός από τις περιπτώσεις όπου η εφαρμογή έχει συγκεκριμένες απαιτήσεις, όπως είναι το παράδειγμα παραγωγού καταναλωτή που έδωσα παραπάνω, όπου μια τέτοια απόφαση πρέπει να ληφθεί κατά τη σχεδίαση της εφαρμογής. Και φυσικά υπάρχουν διαφορετικές υλοποιήσεις για γράφους (π.χ. με δείκτες και δυναμική εκχώρηση μνήμης, με δισδιάστατους πίνακες κλπ) και για δέντρα
Ακόμα δύο παρατηρήσεις:
  • Το να είναι κάτι στατικό δεν είναι πάντα κακό. Η δυναμική εκχώρηση μνήμης και η χρήση των δεικτών που απαιτούνται σε δυναμικές (όχι abstract) δομές δεδομένων έχει συνήθως επιβάρυνση στο run time, έχει μη predictable συμπεριφορά (απαραίτητη για real time συστήματα), και κάνει πιο δύσκολο των προγραμματισμό (εκτός αν χρησιμοποιείς έτοιμες βιβλιοθήκες όπως είναι τα Collections της Java ή η STL της C++)
  • Ο πίνακας όπως παρουσιάζεται στο βιβλίο είναι μια στατική δομή δεδομένων, προερχόμενη από το array της Pascal, που είναι υλοποίηση της ΑΔΔ sequence (ακολουθία). Γενικά όμως υπάρχουν και δυναμικά arrays όπως είναι τα vector των Java και C++ ή τα arrays διαφόρων scripting γλωσσών (π.χ. Perl). Σε αυτές τις περιπτώσεις ο πίνακας "μεγαλώνει" (συνήθως διπλασιάζεται το μέγεθος του) όταν γεμίσει για να δημιουργήσεις θέσεις για νέα στοιχεία ενώ θέσεις μνήμης που καταλαμβάνει συνεχίζουν να είναι συνεχόμενες. Με έναν τέτοιο πίνακα η υλοποίηση ενός δέντρου είναι στατική ή δυναμική; ;)
Χρόνια Πολλά!
Στέλιος

BlackPainter

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

Παρόλα αυτά ακόμα και αυτή η αναφορά στο ΜΕΓΙΣΤΟ μέγεθος της στοίβας ή της ουράς με κάνει να αναρωτιέμαι αν αναφέρεται στο μέγεθος της στοίβας που είναι πεπερασμένο ή στην "περατότητα" του φυσικού κόσμου. Γιατί αν είναι έτσι, εφόσον οποιοσδήποτε ΑΤΔ ΠΡΕΠΕΙ να υλοποιηθεί σε ένα "φυσικό" άρα πεπερασμένο μέσο, ,ακόμα και αν δεν είναι κομμάτι του ορισμού του, μοιραία έχει πεπερασμένο μέγιστο μέγεθος άρα ,ίσως θα έπρεπε να χαρακτηρίζεται στατικός. Συνεπώς το κριτήριο οφείλει να είναι η λειτουργία και επειδή δεν μπορούμε να κάνουμε αναφορά σε δυναμική παραχώρηση μνήμης στους μαθητές μας καλούμαστε να αποφασίσουμε αν τα δύο πολύ συγκεκριμένα κριτήρια (διαδοχικές θέσεις και σταθερό μέγεθος) μας οδηγούν (και δεν οδηγούμαστε μόνοι μας) σύμφωνα με τα γραφόμενα στις παραγράφους 3.4 και 3.5 σε ασφαλές συμπέρασμα. Έτσι καταλίγω στα συμπεράσματα του παραπάνω μηνύματός μου.

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

Χρόνια Πολλά !!!
Γιώργος

P.Tsiotakis


Στο βιβλίο καθηγητή στις σελίδες 86-88 (κεφάλαιο 3) υλοποιούνται οι δομές δεδομένων στοίβα (με ώθηση και απώθηση) και ουρά (με εισαγωγή και εξαγωγή), αντίστοιχα έχω κάνει μια τέτοια προσπάθεια και στο Β τεύχος (10 Ιανουαρίου)

Δεν είναι ξεκάθαρο οτι οι δομές αυτές είναι στατικές;
1. Αποθηκεύουν τα στοιχεία τους σε συνεχόμενες θέσεις μνήμης, κάτι που δηλώνουν οι δείκτες top και rear
2. Έχουν σταθερό μέγεθος, αφού κάθε πίνακας έχει σταθερό μέγεθος (αλλιώς τι νόημα θα είχε η υπερχείλιση; )

Χρόνια πολλά σε όλους και καλή πρωτοχρονιά,

bagelis1

Το ίδιο το βιβλίο δεν αναφέρει ότι η στοίβα και η ουρά είναι στατικές δομές δεδομένων. Το βιβλίο λέει ότι υλοποιούνται με πίνακες. Αυτό ούτως ή άλλως είναι ευρέως γνωστό. Επίσης είναι ευρέως γνωστό ότι η στοίβα και η ουρά υλοποιούνται και με δείκτες, πράγμα που τις κάνει δυναμικές δομές δεδομένων.
Επίσης πάντα μία δομή δεδομένων είναι πεπερασμένη (ακόμα και με δείκτες έχει όριο τη μνήμη του Η/Υ στον οποίο εκτελείται), αυτό δεν σημαίνει ότι όλες οι δομές δεδομένων είναι στατικές. Ακόμη, υπερχείλιση δεν είναι μία έννοια που χρησιμοποιείται σε πίνακα. Υπερχείλιση είναι έννοια των δυναμικών δομών δεδομένων και σημαίνει "δεν χωράει άλλο δεδομένο η μνήμη".
Τέλος μην ξεχνάμε το προφανές: Κάθε λύση επιστημονικά αποδεκτή θεωρείται σωστή Δεν μπορώ να διανοηθώ ότι θα διδάξω λάθος τους μαθητές μου, μόνο και μόνο επειδή το βιβλίο δεν αναφέρει ρητά ότι είναι δυναμικές δομές δεδομένων. Στο κάτω κάτω ούτε το αντίθετο αναφέρει. Αν τώρα κάποιοι συνάδελφοι πιάνονται από την υλοποίηση σε πίνακα και βγάζουν γενικότερα συμπεράσματα, δεν νομίζω ότι αυτός είναι ορθός τρόπος απόδειξης.
Ένα γενικότερο σχόλιο: Το βιβλίο είναι οδηγός μας, αναμφισβήτητα, δεν είναι όμως η χρυσή βίβλος του προγραμματισμού, ούτε το έγραψε ο Knuth! Τα πάντα είναι θέμα ερμηνείας, και η ερμηνεία γίνεται με γενικότερα επιστημονικά κριτήρια. Ας μην είμαστε τόσο αγκυλωμένοι πια! Όύτε η Ιερά Εξέταση θα μας διορθώσει (και αν σε αυτό διαψευστώ, πάλι εμείς είμαστε υπεύθυνοι, εμείς διορθώνουμε) ούτε γέροι και κουρασμένοι είμαστε για να βάζουμε τόσες πολλές παρωπίδες και να λέμε "ότι λέει το βιβλίο". Δεν είναι αυτό σύγχρονη εκπαίδευση και αλλοίμονο αν ούτε εμείς δεν μπορούμε να υπηρετήσουμε κάτι τέτοιο!
Με εκτίμηση...
Βαγγέλης Μπέκος

BlackPainter

Εγκρίνω και επαυξάνω Βαγγέλη!