Εισαγωγή
Δουλεύεις σε ένα έργο για την ανάπτυξη ενός συστήματος προγραμματισμού δρομολογίων για ένα πολυσύχναστο σιδηροδρομικό δίκτυο.
Σου ζητήθηκε να αναπτύξεις ένα πρωτότυπο για τα δρομολόγια των τρένων στο σύστημα προγραμματισμού. Κάθε δρομολόγιο αποτελείται από μια ακολουθία σιδηροδρομικών σταθμών στους οποίους σταματάει ένα δεδομένο τρένο.
Οδηγίες
Η ομάδα σου έχει αποφασίσει να χρησιμοποιήσει μια διπλά συνδεδεμένη λίστα για να αναπαραστήσει κάθε διαδρομή τρένου στο πρόγραμμα δρομολογίων.
Κάθε σταθμός κατά μήκος της διαδρομής του τρένου θα αναπαρίσταται από έναν κόμβο στη συνδεδεμένη λίστα.
Δεν χρειάζεται να ανησυχείς για τις ώρες άφιξης και αναχώρησης στους σταθμούς.
Κάθε σταθμός θα αναπαρίσταται απλώς από έναν αριθμό.
Οι διαδρομές μπορούν να επεκταθούν, προσθέτοντας σταθμούς στην αρχή ή στο τέλος μιας διαδρομής.
Μπορούν επίσης να συντομευτούν, αφαιρώντας σταθμούς από την αρχή ή το τέλος μιας διαδρομής.
Μερικές φορές ένας σταθμός κλείνει, και σε αυτή την περίπτωση ο σταθμός πρέπει να αφαιρεθεί από τη διαδρομή, ακόμα κι αν δεν βρίσκεται στην αρχή ή στο τέλος της διαδρομής.
Το μέγεθος μιας διαδρομής δεν μετριέται από το πόσο μακριά ταξιδεύει το τρένο, αλλά από το σε πόσους σταθμούς σταματάει.
Η συνδεδεμένη λίστα είναι μια θεμελιώδης δομή δεδομένων στην επιστήμη των υπολογιστών, που χρησιμοποιείται συχνά στην υλοποίηση άλλων δομών δεδομένων.
Όπως υποδηλώνει το όνομά της, είναι μια λίστα με κόμβους που συνδέονται μεταξύ τους.
Είναι μια λίστα με "κόμβους", όπου κάθε κόμβος συνδέεται με τον γείτονά του ή τους γείτονές του.
Σε μια απλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται μόνο με τον κόμβο που τον ακολουθεί.
Σε μια διπλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται τόσο με τον κόμβο που προηγείται όσο και με τον κόμβο που ακολουθεί.
Αν θέλεις να εμβαθύνεις στις συνδεδεμένες λίστες, ρίξε μια ματιά σε αυτό το άρθρο που τις εξηγεί με ωραία σχέδια.
Πώς είναι δομημένη αυτή η άσκηση στην Python
Αν και οι συνδεδεμένες λίστες μπορούν να υλοποιηθούν με πολλούς τρόπους και με ποικίλες υποκείμενες δομές δεδομένων, εδώ σου ζητάμε να υλοποιήσεις τη συνδεδεμένη λίστα σου με αντικειμενοστρεφή τρόπο.
Στο αρχείο stub θα δεις την αρχή μιας κλάσης Node, καθώς και μιας κλάσης LinkedList.
Η κλάση Node σου θα πρέπει να παρακολουθεί την τιμή της, καθώς και ποιοι κόμβοι προηγούνται ή έπονται.
Οι push, pop, shift, unshift, καθώς και η ειδική μέθοδος για το len, θα πρέπει να υλοποιηθούν στην κλάση LinkedList.
Μπορεί επίσης να σου φανεί χρήσιμο να υλοποιήσεις μια ειδική μέθοδο iter για την επανάληψη.
Σε αντίθεση με τη βασική άσκηση, εδώ θα ελέγχουμε συνθήκες σφάλματος καλώντας τις pop και shift σε κενές LinkedLists, οπότε θα χρειαστεί να κάνεις raise στα σφάλματα με τον κατάλληλο τρόπο.
Τέλος, θα θέλαμε να υλοποιήσεις και τη delete, επιπλέον των μεθόδων που περιγράφηκαν παραπάνω.
Η delete θα δέχεται ένα όρισμα, που είναι η τιμή που θα αφαιρεθεί από τη συνδεδεμένη λίστα.
Αν η τιμή εμφανίζεται περισσότερες από μία φορές, θα πρέπει να αφαιρείται μόνο η πρώτη εμφάνισή της.
Μηνύματα εξαίρεσης
Μερικές φορές είναι απαραίτητο να πετάξεις μια εξαίρεση. Όταν το κάνεις αυτό, θα πρέπει πάντα να περιλαμβάνεις ένα κατατοπιστικό μήνυμα σφάλματος που να δείχνει ποια είναι η πηγή του σφάλματος.
Αυτό κάνει τον κώδικά σου πιο ευανάγνωστο και βοηθά σημαντικά στο debugging.
Σε περιπτώσεις όπου ξέρεις ότι η πηγή του σφάλματος θα είναι συγκεκριμένου τύπου, μπορείς να επιλέξεις να πετάξεις έναν από τους ενσωματωμένους τύπους σφαλμάτων, αλλά θα πρέπει και πάλι να περιλαμβάνεις ένα κατατοπιστικό μήνυμα.
Αυτή η συγκεκριμένη άσκηση απαιτεί να χρησιμοποιήσεις την εντολή raise για να "πετάξεις" ένα ValueError όταν μια τιμή κόμβου που διαγράφεται με delete() δεν βρίσκεται στη συνδεδεμένη λίστα.
Επιπλέον, θα πρέπει να πεταχτεί ένα IndexError αν δεν έχουν μείνει κόμβοι για pop().
Τα tests θα περάσουν μόνο αν και κάνεις raise αυτές τις exceptions και συμπεριλάβεις μηνύματα μαζί τους.
Για να πετάξεις ένα ValueError με μήνυμα, γράψε το μήνυμα ως όρισμα στον τύπο της exception:
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Για να πετάξεις ένα IndexError με μήνυμα, γράψε το μήνυμα ως όρισμα στον τύπο της exception:
# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
raise IndexError("List is empty")
Ειδικές μέθοδοι στην Python
Τα tests αυτής της άσκησης θα καλούν επίσης τη len() στη LinkedList σου.
Για να δουλέψει η len(), θα χρειαστεί να δημιουργήσεις μια ειδική μέθοδο __len__.
Για λεπτομέρειες σχετικά με την υλοποίηση ειδικών μεθόδων, ή μεθόδων "dunder", στην Python, δες Python Docs: Basic Object Customization και Python Docs: object.len(self).
Σου προτείνουμε επίσης να δημιουργήσεις μια ειδική μέθοδο __iter__ που θα σε βοηθήσει να επαναλαμβάνεις πάνω στη συνδεδεμένη λίστα σου.
Πηγή
Κλασικό θέμα επιστήμης υπολογιστών
