Θέμα: Απορια για τις λιστες

[chzisi]

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

[chzisi]

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

[itt]

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

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

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

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

[chzisi]

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

[gthal]

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

[itt]

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

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

[evry]

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

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

[dski]

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

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

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

...να μπορεί κανείς να προσπελάσει οποιοδήποτε στοιχείο της (αυτό αντιλαμβάνομαι εγώ με τη διατύπωση τυχαίο κόμβο).

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

Δεν είχαμε μάθει για μνήμη τυχαίας προσπέλασης (βλ. 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ου και του τελευταίου).

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

Δεν είχαμε μάθει για μνήμη τυχαίας προσπέλασης (βλ. 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]

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

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

[itt]

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

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

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

[evry]

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

Άρα είναι Λάθος όχι επειδή δεν μπορείς να προσπελάσεις ένα "τυχαίο" κόμβο αλλά επειδή η άμεση προσπέλαση δεν είναι βασική πράξη της λίστας.