Απορια για τις λιστες

Ξεκίνησε από chzisi, 19 Ιουλ 2015, 10:56:33 ΠΜ

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

chzisi

Καλημερα, αναφερεται στη σελ. 71 του νεου σχολικου βιβλιου για τις λιστες :"Το πεδιο Δεδομενα μπορει να περιεχει μια η περισσοτερες αλφαριθμητικες η αριθμητικες πληροφοριες. "
Υπαρχει καποιος λογος που δεν αναφερονται οι λογικες?

chzisi

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

itt

Παράθεση από: chzisi στις 19 Ιουλ 2015, 10:56:33 ΠΜ
Καλημερα, αναφερεται στη σελ. 71 του νεου σχολικου βιβλιου για τις λιστες :"Το πεδιο Δεδομενα μπορει να περιεχει μια η περισσοτερες αλφαριθμητικες η αριθμητικες πληροφοριες. "
Υπαρχει καποιος λογος που δεν αναφερονται οι λογικες?

Προφανώς και θα τους διέφυγε κατα τη συγγραφή.

Παράθεση από: chzisi στις 19 Ιουλ 2015, 10:18:11 ΜΜ
και κάτι ακόμη,
πάλι στο σημείο που παρουσιάζονται οι λίστες έχουμε έναν ορισμό για τους δείκτες, που όμως διαφέρει από τους δείκτες που έχουμε αναφέρει στους πίνακες. Συγκεκριμένα λέει "... χρησιμοποιείται ακριβώς για τη συνδεση των διαφόρων στοιχείων μιας δομής, που είναι αποθηκευμένα σε μη συνεχόμενες θέσεις μνήμης"
εδώ τώρα πως τα εξηγούμε αυτά τα πράγματα?

Στην έκδοση του βιβλίου που έχω είχε μια σημείωση που ανέφερε ότι το pointer και το index το αποδίδουμε με την ίδια λέξη αν και αναφέρεται σε διαφορετικό πράγμα. Τώρα για την όλη βλακωδία με την μνήμη, καλά κρασιά.

chzisi

πραγματι, διαφορετική αγγλική ορολογία. αλλά αυτη δεν τη διδάσκουμε. Αποφάσισα να διδάξω άλλον ορισμό για τους "δείκτες στους πινακες"  και άλλον για τους "δείκτες στις δυναμικές δομές δεδομένων".  ???



gthal

Σε Σ-Λ που υπάρχει στο διδακτικό πακέτο λέει
"Βασική λειτουργία σε μία λίστα είναι η προσπέλαση σε τυχαίο κόμβο της"
Δεν θυμάμαι αν η απάντηση αναφέρεται στο βιβλίο, θεωρώ πάντως πως απαντάμε "Λάθος", με την έννοια ότι για να πάω σε τυχαίο κόμβο της λίστας πρέπει πρώτα να προσπελάσω σειριακά όλους τους προηγούμενους. Αυτό είναι εξάλλου και ένα μειονέκτημα των λιστών σε σχέση με τους στατικούς πίνακες, έτσι?
Φιλικά,
Γιώργος Θαλασσινός

itt

Παράθεση από: gthal στις 20 Ιαν 2016, 01:14:42 ΜΜ
Σε Σ-Λ που υπάρχει στο διδακτικό πακέτο λέει
"Βασική λειτουργία σε μία λίστα είναι η προσπέλαση σε τυχαίο κόμβο της"
Δεν θυμάμαι αν η απάντηση αναφέρεται στο βιβλίο, θεωρώ πάντως πως απαντάμε "Λάθος", με την έννοια ότι για να πάω σε τυχαίο κόμβο της λίστας πρέπει πρώτα να προσπελάσω σειριακά όλους τους προηγούμενους. Αυτό είναι εξάλλου και ένα μειονέκτημα των λιστών σε σχέση με τους στατικούς πίνακες, έτσι?

Ναι, η απάντηση είναι "Λάθος".

evry

Κατά τη γνώμη μου η σωστή διατύπωση θα έπρεπε να είναι :
Βασική λειτουργία σε μία λίστα είναι η άμεση προσπέλαση σε οποιοδήποτε κόμβο της

Παράθεση από: gthal στις 20 Ιαν 2016, 01:14:42 ΜΜ
Σε Σ-Λ που υπάρχει στο διδακτικό πακέτο λέει
"Βασική λειτουργία σε μία λίστα είναι η προσπέλαση σε τυχαίο κόμβο της"
Δεν θυμάμαι αν η απάντηση αναφέρεται στο βιβλίο, θεωρώ πάντως πως απαντάμε "Λάθος", με την έννοια ότι για να πάω σε τυχαίο κόμβο της λίστας πρέπει πρώτα να προσπελάσω σειριακά όλους τους προηγούμενους. Αυτό είναι εξάλλου και ένα μειονέκτημα των λιστών σε σχέση με τους στατικούς πίνακες, έτσι?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

dski

Κατά την άποψή μου η απάντηση στην ερώτηση είναι "Σωστό" και όχι "Λάθος". Φυσικά σε μια λίστα είναι βασική λειτουργία να μπορεί κανείς να προσπελάσει οποιοδήποτε στοιχείο της (αυτό αντιλαμβάνομαι εγώ με τη διατύπωση τυχαίο κόμβο). Η υλοποίηση της λίστας δε νομίζω πως παίζει ρόλο. Αν είναι με συνδεδεμένη λίστα τότε ναι θα μπορούσε να απαιτείται σειριακή προσπέλαση όλων των προηγούμενων στοιχείων της αλλά πάλι η λειτουργία είναι η ίδια: η προσπέλαση ενός τυχαίου στοιχείου (του 1ου, του 6ου, του 100ου, του τελευταίου) ενώ αν η λίστα είναι υλοποιημένη με πίνακα ή αν υλοποιήσουμε και κάποιο μηχανισμό indexing θα μπορούσαμε να έχουμε ακόμη και άμεση προσπέλαση σε κάποιο στοιχείο της.

Παράθεση από: gthal στις 20 Ιαν 2016, 01:14:42 ΜΜ
Σε Σ-Λ που υπάρχει στο διδακτικό πακέτο λέει
"Βασική λειτουργία σε μία λίστα είναι η προσπέλαση σε τυχαίο κόμβο της"
Δεν θυμάμαι αν η απάντηση αναφέρεται στο βιβλίο, θεωρώ πάντως πως απαντάμε "Λάθος", με την έννοια ότι για να πάω σε τυχαίο κόμβο της λίστας πρέπει πρώτα να προσπελάσω σειριακά όλους τους προηγούμενους. Αυτό είναι εξάλλου και ένα μειονέκτημα των λιστών σε σχέση με τους στατικούς πίνακες, έτσι?

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

Παράθεση από: dski στις 21 Ιαν 2016, 01:08:50 ΜΜ
...να μπορεί κανείς να προσπελάσει οποιοδήποτε στοιχείο της (αυτό αντιλαμβάνομαι εγώ με τη διατύπωση τυχαίο κόμβο).

Μα πάντα θα μπορεί κανείς να προσπελάσει με τον ένα ή τον άλλο τρόπο οποιοδήποτε στοιχείο...

Δεν είχαμε μάθει για μνήμη τυχαίας προσπέλασης (βλ. RAM) και μνήμη σειριακής προσπέλασης (βλ. Tape); Η λίστα δεν είναι κάτι σαν tape;

https://el.wikipedia.org/wiki/%CE%9C%CE%BD%CE%AE%CE%BC%CE%B7_%CF%84%CF%85%CF%87%CE%B1%CE%AF%CE%B1%CF%82_%CF%80%CF%81%CE%BF%CF%83%CF%80%CE%AD%CE%BB%CE%B1%CF%83%CE%B7%CF%82

Θα πρέπει να "...επιτρέπει πρόσβαση στα αποθηκευμένα δεδομένα στον ίδιο χρόνο οπουδήποτε και αν βρίσκονται αυτά, δηλαδή με «τυχαία πρόσβαση». "

dski

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

Παράθεση από: Νίκος Αδαμόπουλος στις 21 Ιαν 2016, 01:45:57 ΜΜ
Μα πάντα θα μπορεί κανείς να προσπελάσει με τον ένα ή τον άλλο τρόπο οποιοδήποτε στοιχείο...

Δεν είχαμε μάθει για μνήμη τυχαίας προσπέλασης (βλ. RAM) και μνήμη σειριακής προσπέλασης (βλ. Tape); Η λίστα δεν είναι κάτι σαν tape;

https://el.wikipedia.org/wiki/%CE%9C%CE%BD%CE%AE%CE%BC%CE%B7_%CF%84%CF%85%CF%87%CE%B1%CE%AF%CE%B1%CF%82_%CF%80%CF%81%CE%BF%CF%83%CF%80%CE%AD%CE%BB%CE%B1%CF%83%CE%B7%CF%82

Θα πρέπει να "...επιτρέπει πρόσβαση στα αποθηκευμένα δεδομένα στον ίδιο χρόνο οπουδήποτε και αν βρίσκονται αυτά, δηλαδή με «τυχαία πρόσβαση». "

gthal

Παράθεση από: evry στις 21 Ιαν 2016, 12:15:06 ΜΜ
Κατά τη γνώμη μου η σωστή διατύπωση θα έπρεπε να είναι :
Βασική λειτουργία σε μία λίστα είναι η άμεση προσπέλαση σε οποιοδήποτε κόμβο της
Κι εγώ έτσι αντιλαμβάνομαι την ερώτηση, αλλιώς η ερώτηση δεν έχει νόημα γιατί προφανώς σε κάθε δομή μπορώ (με κάποιον τρόπο) να προσπελάσω οποιονδήποτε κόμβο της - αλίμονο αν δεν μπορούσα.
Φιλικά,
Γιώργος Θαλασσινός

itt

Παράθεση από: dski στις 21 Ιαν 2016, 02:10:33 ΜΜ
Νίκο, εδώ δε μιλάμε για τυχαία προσπέλαση της λίστας, μιλάμε για προσπέλαση τυχαίου στοιχείου της λίστας. Όπως το καταλαβαίνω εγώ θα πρέπει να μπορεί κανείς να έχει δυνατότητα προσπέλασης (δηλ. πρόσβαση) οποιουδήποτε στοιχείου της λίστας επιθυμεί (όπως το έγραψα πριν). Επίσης νομίζω θα πρέπει να διαχωρίσουμε την έννοια της λίστας ως αφηρημένη δομή δεδομένων από την όποια υλοποίησή της. Στη δομή λίστα, ναι, πρέπει να παρέχεται η δυνατότητα πρόσβασης σε τυχαίο στοιχείο της

Όχι, δεν "πρέπει" να παρέχεται η δυνατότητα προσπέλασης σε οποιοδήποτε στοιχείο της λίστας. Όταν χρησιμοποιείς λίστα, είναι επειδή θες constant time εισαγωγή και διαγραφή, δεν ξέρεις πόσα στοιχεία θα βάλεις (οκ αυτό στα πλαίσια του μαθήματος το αγνοούμε), θες να βάλεις στοιχείο στη μέση της λίστας και δεν σε απασχολεί να έχεις random access.

Κάτι που έχει random access και μοιάζει σαν λίστα, είναι τα dynamic arrays ή vectors ή όπως το λέει το implementation που χρησιμοποιείς. Αλλά άμα θες να έχεις το χαρακτηριστικό του random access με το interface της λίστας θα χάσεις το το constant insert/removal, το οποίο είναι από τα πιο κρίσιμα χαρακτηριστικά της δομής.

evry

Υποθέτω ότι το ΣΛ εμπεριέχει κάποια μετάφραση του random access  που έγινε τυχαίος κόμβος, ενώ έπρεπε να γίνει "άμεση προσπέλαση".
Στη λίστα μπορούμε να προσπελάσουμε οποιονδήποτε κόμβο αλλά η προσπέλαση δεν είναι άμεση, δεν έχουμε (random access) όπως είπε και ο Νίκος πολύ σωστά είναι η διαφορά μεταξύ CD και ταινίας. Επίσης όπως είπε και ο itt τίθεται και θέμα πολυπλοκότητας. Επιλέγουμε μια δομή με βάση τη λειτουργικότητα που ζητάμε, δηλαδή αν έχουμε συχνές διαγραφές/εισαγωγές η λίστα είναι καλή, αλλά αν θέλουμε άμεση προσπέλαση όχι.

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