Στο παράδειγμα παρακάτω θέλουμε να δούμε πώς θα βάλουμε μια λίστα τιμών συνδεδεμένες μεταξύ τους με δυο δείκτες, τον δεξιό και τον αριστερό.
Την λίστα την κόβουμε σε δυο λίστες και ζητάμε από μια θέση του κάτω μισού, από 0 έως 4 να πάρουμε το στοιχείο, να το βγάλουμε εκτός λίστας και να το βάλουμε σε μια θέση στην πάνω λίστα. Στην κάτω λίστα η θέση είναι αυτό που δείχνει ο δείκτης, δηλαδή είναι απόλυτη θέση. Στη πάνω λίστα η θέση είναι η νιοστή θέση. Επειδή η πάνω μισή έχει πέντε στοιχεία, οι θέσεις που μια από αυτές δύναται να καταλάβει το στοιχείο από την κάτω λίστα είναι έξι, μια θέση πριν το πρώτο στοιχείο της λίστας και πέντε θέσεις, μια μετά από κάθε στοιχείο της λίστας.
Αρχικά γνωρίζουμε τις θέσεις και μάλιστα γεμίζουμε τους δείκτες με απλό τρόπο, ώστε ο δείκτης -1 να δηλώνει "μη έγκυρο" ή "δεν υπάρχει συνέχεια", ενώ κάθε άλλο νούμερο να δηλώνει θέση στην "μνήμη" εδώ είναι ο πίνακας για μνήμη και σε κάθε στοιχείο βάζουμε μια ομάδα (οι πίνακες στη Μ2000 μπορούν να μεγαλώνουν χωρίς να αντιγράφονται οι ομάδες αλλά οι εσωτερικοί δείκτες στις ομάδες - οι ομάδες σε πίνακες είναι αντικείμενα, αλλά οι εσωτερικοί δείκτες δεν είναι διαχειρίσιμοι από τον χρήστη της Μ2000, αλλά από τον διερμηνευτή)
Η κλάση κόμβος δίνει απλά μια ομάδα με τρεις τιμές, δυο αριθμούς και ένα αλφαριθμητικό για την πληροφορία που φέρει.
Οι πίνακες στη Μ2000 ξεκινούν από 0 και για το λόγο αυτό βάλαμε το -1 να είναι η "μη έγκυρη τιμή δείκτη", ή νούλα, που σημαίνει αποτυχία (και πράγματι στην αγγλική ορολογία λέγεται Null Pointer αυτός ο δείκτης που δείχνει σε μη έγκυρο αντικείμενο).
Nil & Null
Στην ορολογία των προγραμματιστών υπάρχει το Nil από την λατινική Nil που σημαίνει τίποτα ή μηδέν, αλλά όχι μη έγκυρο. Θα μπορούσαμε να πούμε ότι δείκτης 0 είναι μη έγκυρος (δεν θα χρησιμοποιούμε το στοιχείο 0 της μνήμης μας). Τότε αυτός που φέρει το 0 είναι δείκτης NULL ενώ αυτό που περιέχει έχει υπόσταση και είναι το NIL, αυτό που δηλώνει το τίποτα. Άρα όταν μιλάμε για δείκτες ή θα δείχνουν κάτι ή θα είναι NULL, άρα το NULL δηλώνει κατάσταση. Το Nil λοιπόν είναι αναγνωριστικό ποσότητας και δύναται να περιέχεται κάπου. Αν τώρα η κατάσταση δηλώνεται με αριθμό που ποσοτικά είναι το μηδέν ή τίποτα..τότε λέγοντας πως ο δείκτης είναι ο Nil (που συμφωνήσαμε να δηλώνει ότι έχουμε μη έγκυρο δείκτη) τότε ο δείκτης δεν είναι έγκυρος παρόλο που έχει κάποια τιμή. Πράγματι οι θέσεις μνήμης δεν μπορούν να μην έχουν τίποτα, γιατί είναι θέσεις μνήμης άρα θέσεις από κάτι! Ένας δείκτης είναι μια θέση που δείχνει σε μια άλλη θέση. Άρα ένας δείκτης ως θέση οφείλει να έχει κάτι. Αν λοιπόν συμφωνήσουμε στο νούμερο Nil το μηδέν δηλαδή να το λέμε μη έγκυρο δείκτη, τότε έτσι αναγνωρίζουμε το NULL. Εδώ πάμε κόντρα στο ρεύμα (τα Windows δεν χρησιμοποιούν την θέση 0 της μνήμης γιατί έχουν το 0 ως NULL στους δείκτες που χρησιμοποιούν), και έτσι θα βάλουμε το -1 για ένδειξη NULL.
Αλφαριθμητικό κενό!
Αν προσέξουμε λίγο θα δούμε ότι η κλάση κόμβος που γνωρίζουμε ότι δημιουργεί μια συνάρτηση που όταν την καλέσουμε επιστρέφει ένα αντικείμενο "ομάδα", περιέχει τρεις μεταβλητές χωρίς τιμές. Όπως όμως είδαμε παραπάνω δεν υπάρχει κάτι χωρίς τιμή. Εδώ οι τιμές είναι οι μηδενικές. Καλά για τα νούμερα οι μηδενικές τιμές είναι σωστές. Αν και εδώ τα νούμερα θα είναι δείκτες, θα μπορούσαν να είχαν αρχικές τιμές -1 (δηλαδή NULL). Όμως στο παράδειγμά μας δεν μας στεναχωρεί αυτό. Η μεταβλητή όμως που λέγεται πληροφορία$ τι στο καλό έχει μέσα για αρχή; Εδώ λοιπόν είναι καιρός να μάθουμε ότι τα αλφαριθμητικά είναι λίστες καθορισμένου μήκους, και βρίσκονται σε δυο θέσεις. Στη πρώτη θέση υπάρχει ο δείκτης που δείχνει την άλλη θέση, και ένας αριθμός που λέει πόσα γράμματα θα βρούμε εκεί. Η άλλη θέση έχει τουλάχιστον τα γράμματα (ίσως και μερικά βοηθητικά στοιχεία, αλλά εδώ δεν μας ενδιαφέρουν αυτά). Έτσι η μηδενική τιμή για το αλφαριθμητικό είναι ένας NULL δείκτης, που σημαίνει ότι δεν υπάρχει θέση με γράμματα και μπορούμε να έχουμε και τον αριθμό γραμμάτων στο μηδέν (NIL). Ένα NULL (κατάσταση δείκτη) και ένα Nil (ποσότητα γραμμάτων) αρκούν για το κενό αλφαριθμητικό που το συμβολίζουμε έτσι "" με τα αυτάκια ή εισαγωγικά το ένα δίπλα στο άλλο, χωρίς διάστημα μεταξύ τους. Έτσι ακόμα και το κενό αλφαριθμητικό είναι μια πληροφορία, είναι κάτι, και τρώει μνήμη!
Τι συμβαίνει όταν προσθέτουμε ένα χαρακτήρα σε ένα μεγάλο αλφαριθμητικό
Δείτε τώρα τι συμβαίνει όταν πάμε να προσθέσουμε ένα χαρακτήρα. Το σύστημα ψάχνει να βρει χώρο και αντιγράφει ότι έχει το αλφαριθμητικό και στη συνέχεια αυτό που βάζουμε. Πάει μετά στο δείκτη και τον ενημερώνει και βάζει και το σωστό αριθμό στοιχείων. Αυτό που μένει, το προηγούμενο που έδειχνε ο δείκτης το επιστρέφει στο σύστημα. Υπάρχουν αλφαριθμητικά πολλών τύπων, ανάλογα τη περίπτωση, όταν όμως χρησιμοποιούμε γλώσσες όπως η C++. Εδώ λοιπόν στην Μ2000 η μεταφορά ενός αλφαριθμητικού σε ένα άλλο γίνεται με αντιγραφή, ή ακόμα και αν προσθέσουμε ένα μόνο χαρακτήρα, θα πρέπει να γίνει αντιγραφή και του ενός και όλων των άλλων που ήδη υπάρχουν.
Γιατί μας βολεύουν οι δείκτες
Όπου τώρα μιλάγαμε για αλφαριθμητικά ας σκεφτούμε ότι μπορεί να είναι ό,τι άλλο, στοιχεία δηλαδή, με την ιδιότητα ότι "απλώνουν" το ένα μετά το άλλο (αυτό είναι το θέμα με τα αλφαριθμητικά), χωρίς να ξεκινούν με όλο το χώρο, αλλά να παίρνουν χώρο όπως λέμε δυναμικά. Οι πίνακες της Μ2000 πράγματι μεγαλώνουν και αυτό γίνεται με αντιγραφή. Όμως δείτε τι κερδίζουμε με τους δείκτες. Αν ο πίνακας έχει αντικείμενο ή αλφαριθμητικό τότε έχουμε δυο θέσεις, για κάθε στοιχείο, η θέση στον πίνακα που δείχνει τη θέση του αντικειμένου ή αλφαριθμητική. Αυτό λοιπόν που αντιγράφουμε όταν αυξάνουμε τα στοιχεία του πίνακα είναι μόνο έναν δείκτη σε θέση αντικειμένου ή αλφαριθμητικού, όχι τα αντικείμενα ή τα αλφαριθμητικά! Άρα η επέκταση γίνεται γρήγορα επειδή τα πολύ μεγαλύτερα σε μνήμη αντικείμενα ή και αλφαριθμητικά θα μείνουν στην θέση τους.
Τα βασικά για το παράδειγμα
Στο παράδειγμά μας θέλουμε να έχουμε την πληροφορία δεμένη με δείκτες δεξί και αριστερό για να μπορούμε τη λίστα να τη διαβάζουμε από την αρχή ή από το τέλος (τη καλή και την ανάποδη που αναφέρω στο πρόγραμμα). Ενώ αρχικά βγάζουμε ένα στοιχείο από την σύνδεση με απευθείας γνώση της θέσης (αυτό δεν γίνεται σε μια λίστα λειτουργική αλλά εδώ κάνουμε ότι μας αρέσει, γιατί ξέρουμε ακριβώς τις θέσεις των στοιχείων). Μετά το προσθέτουμε στη "λειτουργική" λίστα όπου δεν ασχολούμαστε με τους πραγματικούς δείκτες, αλλά με μεταβλητές που περιέχουν πραγματικούς δείκτες. Στο παράδειγμα δεν κάνουμε ειδικό έλεγχο περί κενής λίστας. Κενή λίστα θα σήμαινε πως αρκεί και ένας από τους δυο δείκτες να είναι Null (-1 εδώ). Αυτό θα το δούμε στο δεύτερο μέρος που θα προχωρήσω το θέμα.
Στόχος του παραδείγματος
Εδώ μας αρκεί να δούμε ότι ένα στοιχείο με δείκτη από 0 έως 4 θα γίνει μέρος της λίστας που ξεκίνησε από το 5 έως το 9, χωρίς να μετακινηθεί πραγματικά καμία πληροφορία$ (μόνο για να εμφανιστεί αντιγράφεται στην Τύπωσε). Το που θα μπει το καθορίζουμε με το ν-οστό στοιχείο, όπου για ν=0 θα μπει στην αρχή της δεύτερης λίστας, για ν=1 μετά το 1ο, ώσπου για ν>=5 μετά το 5ο στοιχείο
Αφού λοιπόν ετοιμάσουμε την Μ2000 (τρέξουμε το m2000.exe και βάλουμε το πρόγραμμα στο Α) δίνουμε εντολή:
Α 3, 4
Που σημαίνει πάρε από την απόλυτη θέση 3 και μετέφερε τη πληροφορία μετά το τέταρτο στοιχείο.
Σαν άσκηση θα μπορούσε κανείς το πρώτο νούμερο να το δει σαν το ν-οστό στοιχείο της πρώτης λίστας (Αλλά αφού εδώ σηκώνουμε στοιχεία θα πρέπει να ξεκινάει από 1, αφού 0 στοιχείο δεν υπάρχει).
Γράφουμε το παρακάτω σε ένα τμήμα έστω Α (Σ Α enter)
Αν όχι Ταύτιση("ΑΑ") τότε Λάθος "Δεν βρήκα δυο αριθμούς"
\\ ζητάμε μια θέση από 0 έως 4 - δείκτης
\\ και μια σχετική θέση από 0 έως 5 - θέση στη λίστα
κλάση κόμβος {
δεξιά, αριστερά
πληροφορία$
}
Πίνακας Κόμβοι(10)=κόμβος()
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
\\ έχω βάλει ν και μ στο σωρό από την κλήση του τμήματος
Φέρεπίσω 12 ' πάω πίσω το ν δώδεκα θέσεις
Φέρεπίσω 12 ' πάω πίσω το μ δώδεκα θέσεις
\\ άρα διαβάζω από το "Α"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9 {
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
}
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=-1
' ι=9
Επανέλαβε {
Κόμβοι(ι).δεξιά=ι-1
ι--
} μέχρι ι=0
\\ Τώρα έχουμε μια συνδεδεμένη λίστα μέσα σε ένα πίνακα.
\\ για να δουλεύει σωστά η λίστα χρειάζονται μερικές ευκολίες
Τμήμα Δείξε.Λίστα.Αρ {
Διαβασε &κ(), π
Ενώ π>=0 {
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Αριστερά
}
Τύπωσε
}
Τμήμα Δείξε.Λίστα.Δε {
Διαβασε &κ(), π
Ενώ π>=0 {
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Δεξιά
}
Τύπωσε
}
\\ από 0 έως 9
Αναφορά "Η λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
\\ από 9 έως 0
Αναφορά "Η λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
\\ θα κόψουμε τη λίστα σε δυο λίστες!
\\ 0 έως 4 ή πρώτη και 5 έως 9 η δεύτερη
Κόμβοι(4).Αριστερά=-1
Κόμβοι(5).Δεξιά=-1
Αναφορά "Η κάτω μισή λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
Αναφορά "Η κάτω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 4
Αναφορά "Η πάνω μισή λίστα από την καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 5
Αναφορά "Η πάνω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
Αναφορά "θέλω να αφαιρέσω ένα στοιχείο από την πρώτη λίστα"
Δα=0 ' Δείκτης αρχής
Δτ=4 'Δείκτης τέλους
\\ δοκιμάστε για οποιοδήποτε μ από 0 έως 4
\\ προσοχή εδώ ζητάμε το μ πραγματικό στοιχείο
\\ όχι το μ-οστό
\\μ=4
Διάβασε μ
Αναφορά Μορφή$("Θα αφαιρέσω το στοιχείο με δείκτη {0} της λίστας - από 0 έως 4", μ)
αν Κόμβοι(μ).Δεξιά>=0 τότε {
Κόμβοι(Κόμβοι(μ).Δεξιά).Αριστερά=Κόμβοι(μ).Αριστερά
} αλλιώς Δα=Κόμβοι(μ).Αριστερά
\\ υπάρχει μια ωραία συμμετρία στο κώδικα!
αν Κόμβοι(μ).Αριστερά>=0 τότε {
Κόμβοι(Κόμβοι(μ).Αριστερά).Δεξιά=Κόμβοι(μ).Δεξιά
} αλλιώς Δτ=Κόμβοι(μ).Δεξιά
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ
\\τώρα έχουμε το μ έξω από την πρώτη λίστα
\\ υπάρχουν 6 θέσεις για να μπει το μ στοιχείο στην λίστα
\\ με τα πέντε στοιχεία. Ή στην αρχή ή μετά από ένα στοιχείο της λίστας
Δα2=5 ' δείκτης αρχής
Δτ2=9 ' δείκτης τέλους
\\ Οπότε ζητάμε ένα ν όπου αν ν=0 τότε βάζουμε στην αρχή
\\ προσοχή εδώ δεν ζητάμε το ν στοιχείο αλλά το ν-οστό στοιχείο
\\ν=1
Διάβασε ν
Αναφορά Μορφή$("Θα προσθέσω το στοιχείο με δείκτη {0} της λίστας στη πάνω λίστα στη σχετική θέση {1}", μ,ν)
Αν ν=0 τότε {
Κόμβοι(μ).δεξιά=-1
Κόμβοι(μ).αριστερά=Δα2
Κόμβοι(Δα2).δεξιά=μ ' εδώ συνδέθηκε το πρώην πρώτο με το νυν πρώτο
Δα2=μ
} αλλιώς {
\\ τώρα πρέπει να μετράμε
π=Δα2
Ενώ π>=0 και ν>0 {
π=Κόμβοι(π).Αριστερά
ν--
}
Αν π<0 τότε {
\\ είμαστε στο άκρο, θα βάλουμε εδώ το στοιχείο
Κόμβοι(μ).αριστερά=-1 \\ δεν έχει άλλο
Κόμβοι(Δτ2).αριστερά=μ
Κόμβοι(μ).δεξιά=Δτ2
Δτ2=μ
} Αλλιώς {
Κόμβοι(κόμβοι(π).δεξιά).αριστερά=μ ' ΄ενώ έδειχνε το π
Κόμβοι(μ).αριστερά=π '' τώρα ο μ θα δείχνει στο π
Κόμβοι(μ).δεξιά=Κόμβοι(π).δεξιά ' και ο μ θα δείχνει δεξιά ότι έδειχνε ο π
Κόμβοι(π).δεξιά=μ '' και ο π θα δείχνει δεξιά το μ
}
}
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα2
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ2
Πιο πάνω έχω βάλει δυο ΦΕΡΕΠΙΣΩ εντολές για το σωρό (ειδική στοίβα της Μ2000) το οποίο αν θέλουμε βάζουμε το Σωρός Νέος { } και μέσα σε αυτό την εντολή Σειρά. Έτσι δεν πειράζουμε το σωρό όπου είναι τα ν και μ και ακόμα δεν τα έχουμε σηκώσει:
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σωρός Νέος {
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9 {
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
}
Διάβασε Κόμβοι(ι).πληροφορία$
}
Την λίστα την κόβουμε σε δυο λίστες και ζητάμε από μια θέση του κάτω μισού, από 0 έως 4 να πάρουμε το στοιχείο, να το βγάλουμε εκτός λίστας και να το βάλουμε σε μια θέση στην πάνω λίστα. Στην κάτω λίστα η θέση είναι αυτό που δείχνει ο δείκτης, δηλαδή είναι απόλυτη θέση. Στη πάνω λίστα η θέση είναι η νιοστή θέση. Επειδή η πάνω μισή έχει πέντε στοιχεία, οι θέσεις που μια από αυτές δύναται να καταλάβει το στοιχείο από την κάτω λίστα είναι έξι, μια θέση πριν το πρώτο στοιχείο της λίστας και πέντε θέσεις, μια μετά από κάθε στοιχείο της λίστας.
Αρχικά γνωρίζουμε τις θέσεις και μάλιστα γεμίζουμε τους δείκτες με απλό τρόπο, ώστε ο δείκτης -1 να δηλώνει "μη έγκυρο" ή "δεν υπάρχει συνέχεια", ενώ κάθε άλλο νούμερο να δηλώνει θέση στην "μνήμη" εδώ είναι ο πίνακας για μνήμη και σε κάθε στοιχείο βάζουμε μια ομάδα (οι πίνακες στη Μ2000 μπορούν να μεγαλώνουν χωρίς να αντιγράφονται οι ομάδες αλλά οι εσωτερικοί δείκτες στις ομάδες - οι ομάδες σε πίνακες είναι αντικείμενα, αλλά οι εσωτερικοί δείκτες δεν είναι διαχειρίσιμοι από τον χρήστη της Μ2000, αλλά από τον διερμηνευτή)
Η κλάση κόμβος δίνει απλά μια ομάδα με τρεις τιμές, δυο αριθμούς και ένα αλφαριθμητικό για την πληροφορία που φέρει.
Οι πίνακες στη Μ2000 ξεκινούν από 0 και για το λόγο αυτό βάλαμε το -1 να είναι η "μη έγκυρη τιμή δείκτη", ή νούλα, που σημαίνει αποτυχία (και πράγματι στην αγγλική ορολογία λέγεται Null Pointer αυτός ο δείκτης που δείχνει σε μη έγκυρο αντικείμενο).
Nil & Null
Στην ορολογία των προγραμματιστών υπάρχει το Nil από την λατινική Nil που σημαίνει τίποτα ή μηδέν, αλλά όχι μη έγκυρο. Θα μπορούσαμε να πούμε ότι δείκτης 0 είναι μη έγκυρος (δεν θα χρησιμοποιούμε το στοιχείο 0 της μνήμης μας). Τότε αυτός που φέρει το 0 είναι δείκτης NULL ενώ αυτό που περιέχει έχει υπόσταση και είναι το NIL, αυτό που δηλώνει το τίποτα. Άρα όταν μιλάμε για δείκτες ή θα δείχνουν κάτι ή θα είναι NULL, άρα το NULL δηλώνει κατάσταση. Το Nil λοιπόν είναι αναγνωριστικό ποσότητας και δύναται να περιέχεται κάπου. Αν τώρα η κατάσταση δηλώνεται με αριθμό που ποσοτικά είναι το μηδέν ή τίποτα..τότε λέγοντας πως ο δείκτης είναι ο Nil (που συμφωνήσαμε να δηλώνει ότι έχουμε μη έγκυρο δείκτη) τότε ο δείκτης δεν είναι έγκυρος παρόλο που έχει κάποια τιμή. Πράγματι οι θέσεις μνήμης δεν μπορούν να μην έχουν τίποτα, γιατί είναι θέσεις μνήμης άρα θέσεις από κάτι! Ένας δείκτης είναι μια θέση που δείχνει σε μια άλλη θέση. Άρα ένας δείκτης ως θέση οφείλει να έχει κάτι. Αν λοιπόν συμφωνήσουμε στο νούμερο Nil το μηδέν δηλαδή να το λέμε μη έγκυρο δείκτη, τότε έτσι αναγνωρίζουμε το NULL. Εδώ πάμε κόντρα στο ρεύμα (τα Windows δεν χρησιμοποιούν την θέση 0 της μνήμης γιατί έχουν το 0 ως NULL στους δείκτες που χρησιμοποιούν), και έτσι θα βάλουμε το -1 για ένδειξη NULL.
Αλφαριθμητικό κενό!
Αν προσέξουμε λίγο θα δούμε ότι η κλάση κόμβος που γνωρίζουμε ότι δημιουργεί μια συνάρτηση που όταν την καλέσουμε επιστρέφει ένα αντικείμενο "ομάδα", περιέχει τρεις μεταβλητές χωρίς τιμές. Όπως όμως είδαμε παραπάνω δεν υπάρχει κάτι χωρίς τιμή. Εδώ οι τιμές είναι οι μηδενικές. Καλά για τα νούμερα οι μηδενικές τιμές είναι σωστές. Αν και εδώ τα νούμερα θα είναι δείκτες, θα μπορούσαν να είχαν αρχικές τιμές -1 (δηλαδή NULL). Όμως στο παράδειγμά μας δεν μας στεναχωρεί αυτό. Η μεταβλητή όμως που λέγεται πληροφορία$ τι στο καλό έχει μέσα για αρχή; Εδώ λοιπόν είναι καιρός να μάθουμε ότι τα αλφαριθμητικά είναι λίστες καθορισμένου μήκους, και βρίσκονται σε δυο θέσεις. Στη πρώτη θέση υπάρχει ο δείκτης που δείχνει την άλλη θέση, και ένας αριθμός που λέει πόσα γράμματα θα βρούμε εκεί. Η άλλη θέση έχει τουλάχιστον τα γράμματα (ίσως και μερικά βοηθητικά στοιχεία, αλλά εδώ δεν μας ενδιαφέρουν αυτά). Έτσι η μηδενική τιμή για το αλφαριθμητικό είναι ένας NULL δείκτης, που σημαίνει ότι δεν υπάρχει θέση με γράμματα και μπορούμε να έχουμε και τον αριθμό γραμμάτων στο μηδέν (NIL). Ένα NULL (κατάσταση δείκτη) και ένα Nil (ποσότητα γραμμάτων) αρκούν για το κενό αλφαριθμητικό που το συμβολίζουμε έτσι "" με τα αυτάκια ή εισαγωγικά το ένα δίπλα στο άλλο, χωρίς διάστημα μεταξύ τους. Έτσι ακόμα και το κενό αλφαριθμητικό είναι μια πληροφορία, είναι κάτι, και τρώει μνήμη!
Τι συμβαίνει όταν προσθέτουμε ένα χαρακτήρα σε ένα μεγάλο αλφαριθμητικό
Δείτε τώρα τι συμβαίνει όταν πάμε να προσθέσουμε ένα χαρακτήρα. Το σύστημα ψάχνει να βρει χώρο και αντιγράφει ότι έχει το αλφαριθμητικό και στη συνέχεια αυτό που βάζουμε. Πάει μετά στο δείκτη και τον ενημερώνει και βάζει και το σωστό αριθμό στοιχείων. Αυτό που μένει, το προηγούμενο που έδειχνε ο δείκτης το επιστρέφει στο σύστημα. Υπάρχουν αλφαριθμητικά πολλών τύπων, ανάλογα τη περίπτωση, όταν όμως χρησιμοποιούμε γλώσσες όπως η C++. Εδώ λοιπόν στην Μ2000 η μεταφορά ενός αλφαριθμητικού σε ένα άλλο γίνεται με αντιγραφή, ή ακόμα και αν προσθέσουμε ένα μόνο χαρακτήρα, θα πρέπει να γίνει αντιγραφή και του ενός και όλων των άλλων που ήδη υπάρχουν.
Γιατί μας βολεύουν οι δείκτες
Όπου τώρα μιλάγαμε για αλφαριθμητικά ας σκεφτούμε ότι μπορεί να είναι ό,τι άλλο, στοιχεία δηλαδή, με την ιδιότητα ότι "απλώνουν" το ένα μετά το άλλο (αυτό είναι το θέμα με τα αλφαριθμητικά), χωρίς να ξεκινούν με όλο το χώρο, αλλά να παίρνουν χώρο όπως λέμε δυναμικά. Οι πίνακες της Μ2000 πράγματι μεγαλώνουν και αυτό γίνεται με αντιγραφή. Όμως δείτε τι κερδίζουμε με τους δείκτες. Αν ο πίνακας έχει αντικείμενο ή αλφαριθμητικό τότε έχουμε δυο θέσεις, για κάθε στοιχείο, η θέση στον πίνακα που δείχνει τη θέση του αντικειμένου ή αλφαριθμητική. Αυτό λοιπόν που αντιγράφουμε όταν αυξάνουμε τα στοιχεία του πίνακα είναι μόνο έναν δείκτη σε θέση αντικειμένου ή αλφαριθμητικού, όχι τα αντικείμενα ή τα αλφαριθμητικά! Άρα η επέκταση γίνεται γρήγορα επειδή τα πολύ μεγαλύτερα σε μνήμη αντικείμενα ή και αλφαριθμητικά θα μείνουν στην θέση τους.
Τα βασικά για το παράδειγμα
Στο παράδειγμά μας θέλουμε να έχουμε την πληροφορία δεμένη με δείκτες δεξί και αριστερό για να μπορούμε τη λίστα να τη διαβάζουμε από την αρχή ή από το τέλος (τη καλή και την ανάποδη που αναφέρω στο πρόγραμμα). Ενώ αρχικά βγάζουμε ένα στοιχείο από την σύνδεση με απευθείας γνώση της θέσης (αυτό δεν γίνεται σε μια λίστα λειτουργική αλλά εδώ κάνουμε ότι μας αρέσει, γιατί ξέρουμε ακριβώς τις θέσεις των στοιχείων). Μετά το προσθέτουμε στη "λειτουργική" λίστα όπου δεν ασχολούμαστε με τους πραγματικούς δείκτες, αλλά με μεταβλητές που περιέχουν πραγματικούς δείκτες. Στο παράδειγμα δεν κάνουμε ειδικό έλεγχο περί κενής λίστας. Κενή λίστα θα σήμαινε πως αρκεί και ένας από τους δυο δείκτες να είναι Null (-1 εδώ). Αυτό θα το δούμε στο δεύτερο μέρος που θα προχωρήσω το θέμα.
Στόχος του παραδείγματος
Εδώ μας αρκεί να δούμε ότι ένα στοιχείο με δείκτη από 0 έως 4 θα γίνει μέρος της λίστας που ξεκίνησε από το 5 έως το 9, χωρίς να μετακινηθεί πραγματικά καμία πληροφορία$ (μόνο για να εμφανιστεί αντιγράφεται στην Τύπωσε). Το που θα μπει το καθορίζουμε με το ν-οστό στοιχείο, όπου για ν=0 θα μπει στην αρχή της δεύτερης λίστας, για ν=1 μετά το 1ο, ώσπου για ν>=5 μετά το 5ο στοιχείο
Αφού λοιπόν ετοιμάσουμε την Μ2000 (τρέξουμε το m2000.exe και βάλουμε το πρόγραμμα στο Α) δίνουμε εντολή:
Α 3, 4
Που σημαίνει πάρε από την απόλυτη θέση 3 και μετέφερε τη πληροφορία μετά το τέταρτο στοιχείο.
Σαν άσκηση θα μπορούσε κανείς το πρώτο νούμερο να το δει σαν το ν-οστό στοιχείο της πρώτης λίστας (Αλλά αφού εδώ σηκώνουμε στοιχεία θα πρέπει να ξεκινάει από 1, αφού 0 στοιχείο δεν υπάρχει).
Γράφουμε το παρακάτω σε ένα τμήμα έστω Α (Σ Α enter)
Αν όχι Ταύτιση("ΑΑ") τότε Λάθος "Δεν βρήκα δυο αριθμούς"
\\ ζητάμε μια θέση από 0 έως 4 - δείκτης
\\ και μια σχετική θέση από 0 έως 5 - θέση στη λίστα
κλάση κόμβος {
δεξιά, αριστερά
πληροφορία$
}
Πίνακας Κόμβοι(10)=κόμβος()
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
\\ έχω βάλει ν και μ στο σωρό από την κλήση του τμήματος
Φέρεπίσω 12 ' πάω πίσω το ν δώδεκα θέσεις
Φέρεπίσω 12 ' πάω πίσω το μ δώδεκα θέσεις
\\ άρα διαβάζω από το "Α"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9 {
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
}
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=-1
' ι=9
Επανέλαβε {
Κόμβοι(ι).δεξιά=ι-1
ι--
} μέχρι ι=0
\\ Τώρα έχουμε μια συνδεδεμένη λίστα μέσα σε ένα πίνακα.
\\ για να δουλεύει σωστά η λίστα χρειάζονται μερικές ευκολίες
Τμήμα Δείξε.Λίστα.Αρ {
Διαβασε &κ(), π
Ενώ π>=0 {
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Αριστερά
}
Τύπωσε
}
Τμήμα Δείξε.Λίστα.Δε {
Διαβασε &κ(), π
Ενώ π>=0 {
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Δεξιά
}
Τύπωσε
}
\\ από 0 έως 9
Αναφορά "Η λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
\\ από 9 έως 0
Αναφορά "Η λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
\\ θα κόψουμε τη λίστα σε δυο λίστες!
\\ 0 έως 4 ή πρώτη και 5 έως 9 η δεύτερη
Κόμβοι(4).Αριστερά=-1
Κόμβοι(5).Δεξιά=-1
Αναφορά "Η κάτω μισή λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
Αναφορά "Η κάτω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 4
Αναφορά "Η πάνω μισή λίστα από την καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 5
Αναφορά "Η πάνω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
Αναφορά "θέλω να αφαιρέσω ένα στοιχείο από την πρώτη λίστα"
Δα=0 ' Δείκτης αρχής
Δτ=4 'Δείκτης τέλους
\\ δοκιμάστε για οποιοδήποτε μ από 0 έως 4
\\ προσοχή εδώ ζητάμε το μ πραγματικό στοιχείο
\\ όχι το μ-οστό
\\μ=4
Διάβασε μ
Αναφορά Μορφή$("Θα αφαιρέσω το στοιχείο με δείκτη {0} της λίστας - από 0 έως 4", μ)
αν Κόμβοι(μ).Δεξιά>=0 τότε {
Κόμβοι(Κόμβοι(μ).Δεξιά).Αριστερά=Κόμβοι(μ).Αριστερά
} αλλιώς Δα=Κόμβοι(μ).Αριστερά
\\ υπάρχει μια ωραία συμμετρία στο κώδικα!
αν Κόμβοι(μ).Αριστερά>=0 τότε {
Κόμβοι(Κόμβοι(μ).Αριστερά).Δεξιά=Κόμβοι(μ).Δεξιά
} αλλιώς Δτ=Κόμβοι(μ).Δεξιά
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ
\\τώρα έχουμε το μ έξω από την πρώτη λίστα
\\ υπάρχουν 6 θέσεις για να μπει το μ στοιχείο στην λίστα
\\ με τα πέντε στοιχεία. Ή στην αρχή ή μετά από ένα στοιχείο της λίστας
Δα2=5 ' δείκτης αρχής
Δτ2=9 ' δείκτης τέλους
\\ Οπότε ζητάμε ένα ν όπου αν ν=0 τότε βάζουμε στην αρχή
\\ προσοχή εδώ δεν ζητάμε το ν στοιχείο αλλά το ν-οστό στοιχείο
\\ν=1
Διάβασε ν
Αναφορά Μορφή$("Θα προσθέσω το στοιχείο με δείκτη {0} της λίστας στη πάνω λίστα στη σχετική θέση {1}", μ,ν)
Αν ν=0 τότε {
Κόμβοι(μ).δεξιά=-1
Κόμβοι(μ).αριστερά=Δα2
Κόμβοι(Δα2).δεξιά=μ ' εδώ συνδέθηκε το πρώην πρώτο με το νυν πρώτο
Δα2=μ
} αλλιώς {
\\ τώρα πρέπει να μετράμε
π=Δα2
Ενώ π>=0 και ν>0 {
π=Κόμβοι(π).Αριστερά
ν--
}
Αν π<0 τότε {
\\ είμαστε στο άκρο, θα βάλουμε εδώ το στοιχείο
Κόμβοι(μ).αριστερά=-1 \\ δεν έχει άλλο
Κόμβοι(Δτ2).αριστερά=μ
Κόμβοι(μ).δεξιά=Δτ2
Δτ2=μ
} Αλλιώς {
Κόμβοι(κόμβοι(π).δεξιά).αριστερά=μ ' ΄ενώ έδειχνε το π
Κόμβοι(μ).αριστερά=π '' τώρα ο μ θα δείχνει στο π
Κόμβοι(μ).δεξιά=Κόμβοι(π).δεξιά ' και ο μ θα δείχνει δεξιά ότι έδειχνε ο π
Κόμβοι(π).δεξιά=μ '' και ο π θα δείχνει δεξιά το μ
}
}
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα2
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ2
Πιο πάνω έχω βάλει δυο ΦΕΡΕΠΙΣΩ εντολές για το σωρό (ειδική στοίβα της Μ2000) το οποίο αν θέλουμε βάζουμε το Σωρός Νέος { } και μέσα σε αυτό την εντολή Σειρά. Έτσι δεν πειράζουμε το σωρό όπου είναι τα ν και μ και ακόμα δεν τα έχουμε σηκώσει:
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σωρός Νέος {
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9 {
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
}
Διάβασε Κόμβοι(ι).πληροφορία$
}
Προσθήκη 2020
Ο κώδικας μπορεί να εκτελεστεί και με αλλαγές στις δομές επανάληψης και επιλογής όπως φαίνονται παρακάτω. Επίσης τα εσωτερικά τμήματα χρησιμοποιούν την λίσα παραμέτρων σε παρενθέσεις η οποία θα γίνει μια Διάβασε όπως στο πάνω πρόβλημα.
Στη δομή επιλογής Αν όταν βγάζουμε τα μπλοκ και χρησιμοποιούμε το Τέλος Αν τότε ο διερμηνευτής χρησιμοποιεί μια διαφορετική εσωτερική δομή, χωρίς μπλοκ. Οπότε αποφεύγουμε τα άλματα με την Προς, διότι αυτά σχετίζονται με το μπλοκ που ανήκει η δομή, και επειδή υπάρχει μέτρημα των Τέλος Αν κατά την εκτέλεση μπορεί να βγει λάθος αν πχ η Προς (Goto) χρησιμοποιηθεί έτσι ώστε να κάνει αλλαγές ροής που δεν περιλάμβάνουν το σωστό αριθμό Τέλος Αν. Στις Επανάλαβε και Ενώ αν και δεν βλέπουμε μπλοκ όταν χρησιμοποιούμε την έκδοση χωρίς αγκύλες ο διερμηνευτής αποδίδει αυτόματα μπλοκ, οπότε τυχόν εντολές για μπλοκ όπως και η ΠΡΟΣ (Goto) λειτουργούν πάντα σωστά.
Αν όχι Ταύτιση("ΑΑ") Τότε Λάθος "Δεν βρήκα δυο αριθμούς"
\\ ζητάμε μια θέση από 0 έως 4 - δείκτης
\\ και μια σχετική θέση από 0 έως 5 - θέση στη λίστα
κλάση κόμβος {
δεξιά, αριστερά
πληροφορία$
}
Πίνακας Κόμβοι(10)=κόμβος()
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
\\ έχω βάλει ν και μ στο σωρό από την κλήση του τμήματος
Φέρεπίσω 12 ' πάω πίσω το ν δώδεκα θέσεις
Φέρεπίσω 12 ' πάω πίσω το μ δώδεκα θέσεις
\\ άρα διαβάζω από το "Α"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
Τέλος Ενώ
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=-1
' ι=9
Επανέλαβε
Κόμβοι(ι).δεξιά=ι-1
ι--
Μέχρι ι=0
\\ Τώρα έχουμε μια συνδεδεμένη λίστα μέσα σε ένα πίνακα.
\\ ζητάμε μια θέση από 0 έως 4 - δείκτης
\\ και μια σχετική θέση από 0 έως 5 - θέση στη λίστα
κλάση κόμβος {
δεξιά, αριστερά
πληροφορία$
}
Πίνακας Κόμβοι(10)=κόμβος()
' Συνδέουμε σε μια λίστα απλή όλους τους άδειους κόμβους, και τους γεμίζουμε!
Σειρά "Α","Β","Γ","1","3","9","Κ","Λ","Ω","%"
\\ έχω βάλει ν και μ στο σωρό από την κλήση του τμήματος
Φέρεπίσω 12 ' πάω πίσω το ν δώδεκα θέσεις
Φέρεπίσω 12 ' πάω πίσω το μ δώδεκα θέσεις
\\ άρα διαβάζω από το "Α"
ι=0
Κόμβοι(0).δεξιά=-1
Ενώ ι<9
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=ι+1
ι++
Τέλος Ενώ
Διάβασε Κόμβοι(ι).πληροφορία$
Κόμβοι(ι).Αριστερά=-1
' ι=9
Επανέλαβε
Κόμβοι(ι).δεξιά=ι-1
ι--
Μέχρι ι=0
\\ Τώρα έχουμε μια συνδεδεμένη λίστα μέσα σε ένα πίνακα.
\\ για να δουλεύει σωστά η λίστα χρειάζονται μερικές ευκολίες
Τμήμα Δείξε.Λίστα.Αρ (&κ(), π){
Ενώ π>=0
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Αριστερά
Τέλος Ενώ
Τύπωσε
}
Τμήμα Δείξε.Λίστα.Δε (&κ(), π) {
Ενώ π>=0
Τύπωσε κ(π).πληροφορία$;
π=κ(π).Δεξιά
Τέλος Ενώ
Τύπωσε
}
\\ από 0 έως 9
Αναφορά "Η λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
\\ από 9 έως 0
Αναφορά "Η λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
\\ θα κόψουμε τη λίστα σε δυο λίστες!
\\ 0 έως 4 ή πρώτη και 5 έως 9 η δεύτερη
Κόμβοι(4).Αριστερά=-1
Κόμβοι(5).Δεξιά=-1
Αναφορά "Η κάτω μισή λίστα από τη καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 0
Αναφορά "Η κάτω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 4
Αναφορά "Η πάνω μισή λίστα από την καλή"
Δείξε.Λίστα.Αρ &Κόμβοι(), 5
Αναφορά "Η πάνω μισή λίστα από την ανάποδη"
Δείξε.Λίστα.Δε &Κόμβοι(), 9
Αναφορά "θέλω να αφαιρέσω ένα στοιχείο από την πρώτη λίστα"
Δα=0 ' Δείκτης αρχής
Δτ=4 'Δείκτης τέλους
\\ δοκιμάστε για οποιοδήποτε μ από 0 έως 4
\\ προσοχή εδώ ζητάμε το μ πραγματικό στοιχείο
\\ όχι το μ-οστό
\\μ=4
Διάβασε μ
Αναφορά Μορφή$("Θα αφαιρέσω το στοιχείο με δείκτη {0} της λίστας - από 0 έως 4", μ)
Αν Κόμβοι(μ).Δεξιά>=0 Τότε
Κόμβοι(Κόμβοι(μ).Δεξιά).Αριστερά=Κόμβοι(μ).Αριστερά
Αλλιώς
Δα=Κόμβοι(μ).Αριστερά
Τέλος Αν
\\ υπάρχει μια ωραία συμμετρία στο κώδικα!
Αν Κόμβοι(μ).Αριστερά>=0 Τότε
Κόμβοι(Κόμβοι(μ).Αριστερά).Δεξιά=Κόμβοι(μ).Δεξιά
Αλλιώς
Δτ=Κόμβοι(μ).Δεξιά
Τέλος Αν
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ
\\τώρα έχουμε το μ έξω από την πρώτη λίστα
\\ υπάρχουν 6 θέσεις για να μπει το μ στοιχείο στην λίστα
\\ με τα πέντε στοιχεία. Ή στην αρχή ή μετά από ένα στοιχείο της λίστας
Δα2=5 ' δείκτης αρχής
Δτ2=9 ' δείκτης τέλους
\\ Οπότε ζητάμε ένα ν όπου Αν ν=0 Τότε βάζουμε στην αρχή
\\ προσοχή εδώ δεν ζητάμε το ν στοιχείο αλλά το ν-οστό στοιχείο
\\ν=1
Διάβασε ν
Αναφορά Μορφή$("Θα προσθέσω το στοιχείο με δείκτη {0} της λίστας στη πάνω λίστα στη σχετική θέση {1}", μ,ν)
Αν ν=0 Τότε
Κόμβοι(μ).δεξιά=-1
Κόμβοι(μ).αριστερά=Δα2
Κόμβοι(Δα2).δεξιά=μ ' εδώ συνδέθηκε το πρώην πρώτο με το νυν πρώτο
Δα2=μ
Αλλιώς
\\ τώρα πρέπει να μετράμε
π=Δα2
Ενώ π>=0 και ν>0
π=Κόμβοι(π).Αριστερά
ν--
Τέλος Ενώ
Αν π<0 Τότε
\\ είμαστε στο άκρο, θα βάλουμε εδώ το στοιχείο
Κόμβοι(μ).αριστερά=-1 \\ δεν έχει άλλο
Κόμβοι(Δτ2).αριστερά=μ
Κόμβοι(μ).δεξιά=Δτ2
Δτ2=μ
Αλλιώς
Κόμβοι(κόμβοι(π).δεξιά).αριστερά=μ ' ΄ενώ έδειχνε το π
Κόμβοι(μ).αριστερά=π '' τώρα ο μ θα δείχνει στο π
Κόμβοι(μ).δεξιά=Κόμβοι(π).δεξιά ' και ο μ θα δείχνει δεξιά ότι έδειχνε ο π
Κόμβοι(π).δεξιά=μ '' και ο π θα δείχνει δεξιά το μ
Τέλος Αν
Τέλος Αν
Δείξε.Λίστα.Αρ &Κόμβοι(), Δα2
Δείξε.Λίστα.Δε &Κόμβοι(), Δτ2
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου
You can feel free to write any suggestion, or idea on the subject.