Μέρος 1ο (επόμενο)
Τα προγράμματα σε αυτή τη σελίδα αναφέρονται σε δημοσιεύσεις που έχουν γίνει στο http://alkisg.mysch.gr/steki/index.php αλλά η διαχειριστική ομάδα του συγκεκριμένου τόπου θέλει να τα αφαιρέσει, με τη δικαιολογία ότι "αποσπούν" την προσοχή των μαθητών και των καθηγητών από τα προβλεπόμενα. Σέβομαι την άποψη του διαχειριστή που επικοινώνησε μαζί μου, και για "ιστορικούς λόγους" θα μπουν τα προγράμματα εδώ:
τα προγράμματα βρίσκονται εδώ σε αρχείο zip.
Το πρόγραμμα που παρουσιάζω δείχνει πως μπορούμε με τη ΓΛΩΣΣΑ να φτιάξουμε πραγματικούς κόμβους για Ουρές και Στοίβες. Για το σκοπό αυτό έχουμε διαδικασίες που βοηθούν όπως:
Διαδικασία ΝΕΟ για να μας δώσει το νούμερο (δείκτη) ενός νέου κόμβου. Οι νέοι κόμβοι δίνονται από μια στοίβα με δείκτη το ελεύθερο. Αν αυτός ο δείκτης έχει τιμή μηδέν τότε δεν υπάρχει ελεύθερος κόμβος και δεν καλούμε τη διαδικασία (το ελέγχουμε πριν καλέσουμε τη ΝΕΟ).
Διαδικασία Ελεύθερη_Μνήμη. Μας επιστρέφει τον αριθμό των ελεύθερων κόμβων διατρέχοντας και μετρώντας ταυτόχρονα τους ελεύθερους κόμβους από το κόμβο που δείχνει η μεταβλητή Ελεύθερο.
Διαδικασία Δείξε. Ξεκινάει από ένα κόμβο, βάζοντας την τιμή του δείκτη σε μια βοηθητική μεταβλητή (για να μην πειράξουμε το δείκτη), και διατρέχουμε όλους τους κόμβους όσο η βοηθητική δεν είναι μηδέν.
Διαδικασία Χρήση. Εδώ διαβάζουμε ένα κόμβο και τον ελευθερώνουμε, δηλαδή τον επιστρέφουμε στην ελεύθερη μνήμη.
Με αυτές τις τέσσερις διαδικασίες εκτελούμε το πρόγραμμα που δίνει την παρακάτω εξαγωγή:
Μπορούν να φτιαχτούν και άλλες διαδικασίες σχετικές με λίστες, και όχι ειδικά για ουρά και στοίβα, όπως η αναζήτηση (μια παραλλαγή της Δείξε), η αναζήτηση και διαγραφή αυτό που βρίσκουμε, η αναζήτηση και η εισαγωγή σε περίπτωση μη εύρεσης, η μετακίνηση του πρώτου στοιχείου στο ν στοιχείο λίστας, η μετακίνηση του ν στοιχείου στο πρώτο της λίστας.
Είχα δώσει τον αλγόριθμο Dijkstra με χρήση πίνακα, ΚορυφέςΧΑκμές. Έτσι κάθε κορυφή είχε το μέγιστο των ακμών που θα βάζαμε στο γράφο.
Τώρα με τη χρήση της παραπάνω δομής μπορούμε να αλλάξουμε το πρόγραμμα και να έχουμε δυναμική χρήση κόμβων. Για κάθε ακμή θέλουμε δυο κόμβους, ο ένας έχει το νούμερο της κορυφής ως προορισμός και ο άλλος έχει το κόστος. Για κάθε κορυφή χρησιμοποιούμε μια στοίβα και βάζουμε ανάποδα τα στοιχεία, για να τα διαβάζουμε με την ορθή φορά! Δεν μας ενδιαφέρει το pop (απώθηση) της στοίβας. Μας ενδιαφέρει να διατρέχουμε τη στοίβα, και να διαβάζουμε δυο κόμβους κάθε φορά.
Έχω αφήσει με λατινικούς χαρακτήρες τις μεταβλητές που χρησιμοποιούνταν στο αρχικό πρόγραμμα. Ο πίνακας Edges[] δεν υπάρχει πια, και αντί αυτού χρησιμοποιούμε το cost το οποίο το τροφοδοτούμε από τη δυναμική δομή.
Αυτό το πρόγραμμα αποδεικνύει ότι με τη ΓΛΩΣΣΑ μπορούμε να φτιάξουμε δυναμικές δομές, όπως γράφους.
Ελεύθερη Μνήμη 82 κόμβων
a->b 7
a->c 9
a->f 14
b->c 10
b->d 15
c->d 11
c->f 2
d->e 6
e->f 9
Υπολογισμός βαρών
a 0
b 7
c 9
d 20
e 26
f 11
Διαδρομή από a μέχρι e:acde
Ελεύθερη Μνήμη 100 κόμβων
Παραλλαγή του κώδικα με τους κόμβους. Τώρα ο πίνακας κομ[] είναι δυο διαστάσεων για να γράφουμε δυο δείκτες, τον αριστερό και το δεξιό ως τιμές δεύτερης διάστασης 1 και 2. Έτσι τώρα κάθε κόμβος έχει δυο δείκτες. Ο πίνακας τιμ[] έγινε πίνακας χαρακτήρων.
Για τη κατασκευή του δένδρου, υπάρχουν πολλοί τρόποι. Εδώ ξεκίνησα από το 7, πήγα στο 4 και έβαλα το 7 σαν αριστερό παιδί, και μετά πήγα στο 2 όπου πέρασα το δένδρο σαν αριστερό παιδί και έβαλα το 3 ως δεξιό παιδί. μετά έβαλα ότι είχα σαν παιδί στο κόμβο με το 1 το οποίο και "σημάδεψα" στη μεταβλητή ρίζα. Κατόπιν γέμισα και ότι χρειάζονταν από την δεξιά πλευρά κάτω από το 1.
Οι τρεις τρόποι preorder, inorder, και postorder, έχουν γίνει με διαδικασία που καλεί τον εαυτό της όποτε το χρειάζεται, δηλαδή χρησιμοποιεί αναδρομή.
Ο τέταρτος τρόπος είναι πιο δύσκολος γιατί η ΓΛΩΣΣΑ δεν έχει κάποια δομή έτοιμη για ουρά, οπότε χρησιμοποίησα την δομή που είχα για ουρά, χωρίς να χρησιμοποιήσω για κάθε κόμβο τον πίνακα τιμ[]. Έτσι ο αριστερός δείκτης δείχνει τον επόμενο κόμβο, και ο δεξιός απλά κρατάει τον αριθμό του κόμβου που θέλουμε να βάλουμε στην ουρά. Υπάρχουν δυο διαδικασίες, η ΕισαγωγήΚόμβου και η ΕξαγωγήΚόμβου, και δεν χρησιμοποιούμε αναδρομή, απλά μια επανάληψη μέχρι η ουρά να αδειάσει. Τη πρώτη φορά βάζουμε στην ουρά την ρίζα.
Κάθε φορά που αδειάζει η ουρά διαγράφεται και το στοιχείο, δηλαδή πηγαίνει στην στοίβα ελεύθερων. Υπάρχει τέλος μια διαδικασία που μοιάζει με την postorder αλλά διαγράφει τα στοιχεία του δένδρου από τη ρίζα, και τα στέλνει στη στοίβα των ελεύθερων.
Στο τέλος μας δίνει το νούμερο των ελεύθερων κόμβων, το 100.
Το δένδρο είναι αυτό:
! 1
! / \
! / \
! / \
! 2 3
! / \ /
! 4 5 6
! / / \
! 7 8 9
Δηλαδή έχουμε 9 κόμβους.
Το αποτέλεσμα είναι αυτό:
Εδώ αντί για αναδρομή χρησιμοποιούμε μια ουρά. Θέλουμε στην ουρά να μπαίνει ο αριθμός κόμβου με αρνητικό πρόσημο όταν απλά θέλουμε να τυπωθεί. Όταν στην ουρά μπαίνει με θετικό πρόσημο τότε η ουρά ανατροφοδοτείται με ένα έως τρια στοιχεία ανάλογα αν υπάρχουν παιδιά στον κόμβο.
Προστέθηκαν δυο διαδικασίες για ώθηση και απώθηση σε σωρό.
Η διαγραφή κόμβων έγινε και αυτή μη αναδρομική (παραλλαγή της postorder)
Τώρα το πρόγραμμα δεν έχει αναδρομή δηλαδή είναι εντός της ύλης!
Η εξαγωγή είναι η ίδια
Παράδειγμα κωδικοποίησης RLE
Το αλφαριθμητικό εισαγωγής και το αποτέλεσμα το έχω πάρει από το παράδειγμα εδώ: Wiki
Μας ενδιαφέρει το πρόγραμμα να εμφανίσει τα αλφαριθμητικά input και output. Tο output θα προκύπτει από την επεξεργασία του input. Για κάθε χαρακτήρα θα υπολογίζεται ο αριθμός εμφάνισης και θα πηγαίνει στην εξαγωγή αμέσως μετά την μετατροπή του αριθμού σε χαρακτήρες.
Χρειαζόμαστε ένα τρόπο να προσθέτουμε χαρακτήρες και αυτό γίνεται μόνο με χρήση πίνακα στη ΓΛΩΣΣΑ.
Για να κάνουμε μετατροπή ακέραιου αριθμού σε χαρακτήρες μας ενδιαφέρει να ξέρουμε προκαταβολικά το μέγεθος σε χαρακτήρες. Αυτό βγαίνει με τη χρήση του δεκαδικού λογαρίθμου του αριθμού. Επειδή η συνάρτηση ΛΟΓ() είναι ο φυσικός λογάριθμος πρέπει να διαιρέσουμε δια του ΛΟΓ(10). Έχουμε μια συνάρτηση που γυρίζει τον αριθμό χαρακτήρων.
Σαν άσκηση για το σπίτι, φτιάχτε μια διαδικασία που θα παίρνει τους πίνακες ΕΞ και ΑΡ καθώς και το ΤΕΛ και θα παράγει από το Output το Input.
Για να εμφανίζονται οι χαρακτήρες μαζί πρέπει σε διαδοχικές ΓΡΑΨΕ να έχουμε τελευταία τιμή ένα χαρακτήρα διαστήματος.
Παράθεση
Πρόγραμμα ΤαξινόμησηΜεΟυρές.glo
Χρήση τριών ουρών για ταξινόμηση. Τις ουρές τις ονομάζω ταινίες, σαν τις μαγνητικές ταινίες παλιών υπολογιστών. Αρχικά βάζουμε στην ταινία Α τη σειρά αλφαριθμητικών που θέλουμε να ταξινομήσουμε. Μετά:
1. Σπάμε την ταινία σε δυο ταινίες. Για να το κάνουμε αυτό συγκρίνουμε το τελευταίο εισαγόμενο με το πρώτο της ταινίας Α, διαλέγουμε μια ταινία που θα αλλάζουμε το συγκρινόμενο.
2.Στη δεύτερη φάση κοιτάμε αν έχουμε όλα τα στοιχεία στην ίδια ταινία (κοιτάμε αν και οι δυο ταινίες έχουν κάτι, δηλαδή οι δείκτες τους δεν είναι μηδέν).
- Αν ναι τότε φτιάχνουμε μια νέα ταινία Α από τα στοιχεία της Β ταινίας και της Γ (συγχώνευση των Β και Γ στο Α). Το τελευταίο στοιχείο της Β το κρατάμε για την πρώτη σύγκριση. Πάμε στο βήμα 1
- Αν όχι τότε έχουμε την απάντηση στη ταινία Γ.
Έξοδος
ΑΘΗΝΑ
ΒΟΛΟΣ
ΘΕΣΣΑΛΟΝΙΚΗ
ΙΩΑΝΝΙΝΑ
ΚΑΛΛΙΘΕΑ
ΜΕΣΟΛΟΓΓΙ
ΝΑΥΠΛΙΟ
ΠΑΤΡΑ
ΠΡΕΒΕΖΑ
ΧΑΝΙΑ
ΧΑΝΙΑ
ΠΡΕΒΕΖΑ
ΠΑΤΡΑ
ΝΑΥΠΛΙΟ
ΜΕΣΟΛΟΓΓΙ
ΚΑΛΛΙΘΕΑ
ΙΩΑΝΝΙΝΑ
ΘΕΣΣΑΛΟΝΙΚΗ
ΒΟΛΟΣ
ΑΘΗΝΑ
Ελεύθερη Μνήμη 80 κόμβων
ΑΘΗΝΑ
ΑΘΗΝΑ
ΒΟΛΟΣ
ΒΟΛΟΣ
ΘΕΣΣΑΛΟΝΙΚΗ
ΘΕΣΣΑΛΟΝΙΚΗ
ΙΩΑΝΝΙΝΑ
ΙΩΑΝΝΙΝΑ
ΚΑΛΛΙΘΕΑ
ΚΑΛΛΙΘΕΑ
ΜΕΣΟΛΟΓΓΙ
ΜΕΣΟΛΟΓΓΙ
ΝΑΥΠΛΙΟ
ΝΑΥΠΛΙΟ
ΠΑΤΡΑ
ΠΑΤΡΑ
ΠΡΕΒΕΖΑ
ΠΡΕΒΕΖΑ
ΧΑΝΙΑ
ΧΑΝΙΑ
Ελεύθερη Μνήμη 100 κόμβων
(επόμενο)
Τα προγράμματα σε αυτή τη σελίδα αναφέρονται σε δημοσιεύσεις που έχουν γίνει στο http://alkisg.mysch.gr/steki/index.php αλλά η διαχειριστική ομάδα του συγκεκριμένου τόπου θέλει να τα αφαιρέσει, με τη δικαιολογία ότι "αποσπούν" την προσοχή των μαθητών και των καθηγητών από τα προβλεπόμενα. Σέβομαι την άποψη του διαχειριστή που επικοινώνησε μαζί μου, και για "ιστορικούς λόγους" θα μπουν τα προγράμματα εδώ:
τα προγράμματα βρίσκονται εδώ σε αρχείο zip.
Αλγόριθμος Dijkstra με πίνακα
Πρόγραμμα Dijkstra_algorithm.glo
Φτιάχνοντας την άσκηση στο rosettacode.org σκέφτηκα ότι μπορεί να γίνει και στη ΓΛΩΣΣΑ.
Η άσκηση έχει ως εξής:
Υπάρχουν 6 κορυφές, a b c d e f και ορίζονται ακμές μιας κατεύθυνσης και για κάθε μια από αυτές ορίζεται και ένα κόστος (ή βάρος).
Το ζητούμενο είναι να βρούμε την διαδρομή από a στο e με το μικρότερο συνολικό κόστος (ή βάρος),
Επιμέρους ζητούμενα είναι:
1. Να δείξουμε το παρακάτω πίνακα από μια δομή που θα φτιάξουμε
2. Να δείξουμε όλα τα βάρη για κάθε κορυφή σε σχέση με το a
3. Να δείξουμε τη διαδρομή.
a->b 7
a->c 9
a->f 14
b->c 10
b->d 15
c->d 11
c->f 2
d->e 6
e->f 9
Συμπληρωματικά:
α) Για την λύση του προβλήματος θα χρειαστούμε ένα πίνακα ακεραίων δυο διαστάσεων. Ο Edges[i,k] αν έχει τιμή>0 τότε σημαίνει ότι η ακμή από τη κορυφή i στη k υπάρχει και η τιμή που δίνει είναι το βάρος.
β) Ο αλγόριθμος του Dijkstra δουλεύει ως εξής:
Υπάρχουν τρεις πίνακες, ο s[], o d[] και o p[].
Τον πίνακα s[] τον χρησιμοποιούμε για να αφαιρούμε τη κορυφή που έχει το μικρότερο βάρος, βάζοντας στη θέση της το 0. Επίσης τον χρησιμοποιούμε για να αντιστρέψουμε το μονοπάτι και να το εμφανίσουμε από το a στο e.
Τον πίνακα d[] τον χρησιμοποιούμε για να βάλουμε ένα μεγάλο αρχικό βάρος (το ίδιο σε όλα), εκτός από τη κορυφή που είναι η αφετηρία, όπου βάζουμε το 0. Τον πίνακα p[] τον θέλουμε για να βάζουμε την προηγούμενη κορυφή, ώστε να μπορούμε να βρούμε το μονοπάτι.
Ο αλγόριθμος είναι μια επανάληψη για όσο υπάρχουν στο s[] μη μηδενικοί αριθμοί (δηλαδή όσο υπάρχουν κορυφές). Εντός της επανάληψης έχουμε δυο φάσεις. Η πρώτη βρίσκει τη κορυφή με το μικρότερο βάρος βάσει αυτών των κορυφών που υπάρχουν στο s[] και τοποθετεί τον αριθμό της στο u. Αμέσως μετά την αφαιρεί από το s[] (βάζουμε ένα μηδέν). Μετά ακολουθεί η δεύτερη φάση. Σε αυτήν πρέπει να εξετάσουμε όλες τις ακμές για την κορυφή u. Αν το k είναι η εξεταζόμενη κορυφή, και το Edges[u,k] δηλώνει ότι υπάρχει ακμή τότε, αν ισχύει αυτό:
Μόλις τελειώσει ο αλγόριθμος o d[] περιέχει τα βάρη που σχετίζονται με την αφετηρία. Αν το βάρος μιας κορυφής είναι ίσο με το μέγιστο αριθμό σημαίνει ότι δεν υπάρχει διαδρομή από την αφετηρία σε αυτή τη κορυφή.
Εδώ να προσέξει ο αναγνώστης ότι έχουμε δυο είδη βαρών. Το βάρος που καταγράφεται στη δομή (στο Edges[]) και το οποίο δεν αλλάζει, και το βάρος που καταγράφεται στο d[], το υπολογιζόμενο βάρος για δοσμένη αφετηρία.
Η άσκηση έχει ως εξής:
Υπάρχουν 6 κορυφές, a b c d e f και ορίζονται ακμές μιας κατεύθυνσης και για κάθε μια από αυτές ορίζεται και ένα κόστος (ή βάρος).
Το ζητούμενο είναι να βρούμε την διαδρομή από a στο e με το μικρότερο συνολικό κόστος (ή βάρος),
Επιμέρους ζητούμενα είναι:
1. Να δείξουμε το παρακάτω πίνακα από μια δομή που θα φτιάξουμε
2. Να δείξουμε όλα τα βάρη για κάθε κορυφή σε σχέση με το a
3. Να δείξουμε τη διαδρομή.
a->b 7
a->c 9
a->f 14
b->c 10
b->d 15
c->d 11
c->f 2
d->e 6
e->f 9
Συμπληρωματικά:
α) Για την λύση του προβλήματος θα χρειαστούμε ένα πίνακα ακεραίων δυο διαστάσεων. Ο Edges[i,k] αν έχει τιμή>0 τότε σημαίνει ότι η ακμή από τη κορυφή i στη k υπάρχει και η τιμή που δίνει είναι το βάρος.
β) Ο αλγόριθμος του Dijkstra δουλεύει ως εξής:
Υπάρχουν τρεις πίνακες, ο s[], o d[] και o p[].
Τον πίνακα s[] τον χρησιμοποιούμε για να αφαιρούμε τη κορυφή που έχει το μικρότερο βάρος, βάζοντας στη θέση της το 0. Επίσης τον χρησιμοποιούμε για να αντιστρέψουμε το μονοπάτι και να το εμφανίσουμε από το a στο e.
Τον πίνακα d[] τον χρησιμοποιούμε για να βάλουμε ένα μεγάλο αρχικό βάρος (το ίδιο σε όλα), εκτός από τη κορυφή που είναι η αφετηρία, όπου βάζουμε το 0. Τον πίνακα p[] τον θέλουμε για να βάζουμε την προηγούμενη κορυφή, ώστε να μπορούμε να βρούμε το μονοπάτι.
Ο αλγόριθμος είναι μια επανάληψη για όσο υπάρχουν στο s[] μη μηδενικοί αριθμοί (δηλαδή όσο υπάρχουν κορυφές). Εντός της επανάληψης έχουμε δυο φάσεις. Η πρώτη βρίσκει τη κορυφή με το μικρότερο βάρος βάσει αυτών των κορυφών που υπάρχουν στο s[] και τοποθετεί τον αριθμό της στο u. Αμέσως μετά την αφαιρεί από το s[] (βάζουμε ένα μηδέν). Μετά ακολουθεί η δεύτερη φάση. Σε αυτήν πρέπει να εξετάσουμε όλες τις ακμές για την κορυφή u. Αν το k είναι η εξεταζόμενη κορυφή, και το Edges[u,k] δηλώνει ότι υπάρχει ακμή τότε, αν ισχύει αυτό:
d[k] > Edges[u, k] + d[u]αλλάζουμε το d[k] με την τιμή Edges[u, k] + d[u]και καταχωρούμε στο p[k] το u (δηλώνει ότι από το u πήγαμε στο k, και αυτό είναι το πιο σύντομο)Μόλις τελειώσει ο αλγόριθμος o d[] περιέχει τα βάρη που σχετίζονται με την αφετηρία. Αν το βάρος μιας κορυφής είναι ίσο με το μέγιστο αριθμό σημαίνει ότι δεν υπάρχει διαδρομή από την αφετηρία σε αυτή τη κορυφή.
Εδώ να προσέξει ο αναγνώστης ότι έχουμε δυο είδη βαρών. Το βάρος που καταγράφεται στη δομή (στο Edges[]) και το οποίο δεν αλλάζει, και το βάρος που καταγράφεται στο d[], το υπολογιζόμενο βάρος για δοσμένη αφετηρία.
ΣΤΟΙΒΑ και ΟΥΡΑ με πραγματικούς ΚΟΜΒΟΥΣ
Πρόγραμμα κομβοι.gloΤο πρόγραμμα που παρουσιάζω δείχνει πως μπορούμε με τη ΓΛΩΣΣΑ να φτιάξουμε πραγματικούς κόμβους για Ουρές και Στοίβες. Για το σκοπό αυτό έχουμε διαδικασίες που βοηθούν όπως:
Διαδικασία ΝΕΟ για να μας δώσει το νούμερο (δείκτη) ενός νέου κόμβου. Οι νέοι κόμβοι δίνονται από μια στοίβα με δείκτη το ελεύθερο. Αν αυτός ο δείκτης έχει τιμή μηδέν τότε δεν υπάρχει ελεύθερος κόμβος και δεν καλούμε τη διαδικασία (το ελέγχουμε πριν καλέσουμε τη ΝΕΟ).
Διαδικασία Ελεύθερη_Μνήμη. Μας επιστρέφει τον αριθμό των ελεύθερων κόμβων διατρέχοντας και μετρώντας ταυτόχρονα τους ελεύθερους κόμβους από το κόμβο που δείχνει η μεταβλητή Ελεύθερο.
Διαδικασία Δείξε. Ξεκινάει από ένα κόμβο, βάζοντας την τιμή του δείκτη σε μια βοηθητική μεταβλητή (για να μην πειράξουμε το δείκτη), και διατρέχουμε όλους τους κόμβους όσο η βοηθητική δεν είναι μηδέν.
Διαδικασία Χρήση. Εδώ διαβάζουμε ένα κόμβο και τον ελευθερώνουμε, δηλαδή τον επιστρέφουμε στην ελεύθερη μνήμη.
Με αυτές τις τέσσερις διαδικασίες εκτελούμε το πρόγραμμα που δίνει την παρακάτω εξαγωγή:
Οι τελευταίες ενέργειες, είναι να αδειάσουμε την Στοίβα και να δείξουμε την ελεύθερη μνήμη, να αδειάσουμε την Ουρά και να δείξουμε την ελεύθερη μνήμη. Στο τέλος η ελεύθερη μνήμη είναι αυτή των 100 κόμβων, όπως ξεκινήσαμε.Δημιουργία στοίβας 20 στοιχείωνΏθηση 100Ώθηση 119Ελεύθερη Μνήμη 80 κόμβωνΔημιουργία ουράς 20 στοιχείωνΕισαγωγή 120.................Εισαγωγή 139Ελεύθερη Μνήμη 60 κόμβωνΔιάβασμα Στοιβας χωρίς να πετάξουμε τα στοιχεία119.............100Διαβασμα Ουράς χωρίς να πετάξουμε τα στοιχεία120...............139Απώθηση 5 πρώτων από την στοίβα119.............115Εξαγωγή 5 πρώτων από την Ουρά120...............124Ελεύθερη Μνήμη 70 κόμβωνΕλεύθερη Μνήμη 85 κόμβωνΕλεύθερη Μνήμη 100 κόμβων
Μπορούν να φτιαχτούν και άλλες διαδικασίες σχετικές με λίστες, και όχι ειδικά για ουρά και στοίβα, όπως η αναζήτηση (μια παραλλαγή της Δείξε), η αναζήτηση και διαγραφή αυτό που βρίσκουμε, η αναζήτηση και η εισαγωγή σε περίπτωση μη εύρεσης, η μετακίνηση του πρώτου στοιχείου στο ν στοιχείο λίστας, η μετακίνηση του ν στοιχείου στο πρώτο της λίστας.
Αλγόριθμος Dijkstra με κόμβους στη Γλώσσα
Πρόγραμμα Dijkstra_algorithm_2.gloΕίχα δώσει τον αλγόριθμο Dijkstra με χρήση πίνακα, ΚορυφέςΧΑκμές. Έτσι κάθε κορυφή είχε το μέγιστο των ακμών που θα βάζαμε στο γράφο.
Τώρα με τη χρήση της παραπάνω δομής μπορούμε να αλλάξουμε το πρόγραμμα και να έχουμε δυναμική χρήση κόμβων. Για κάθε ακμή θέλουμε δυο κόμβους, ο ένας έχει το νούμερο της κορυφής ως προορισμός και ο άλλος έχει το κόστος. Για κάθε κορυφή χρησιμοποιούμε μια στοίβα και βάζουμε ανάποδα τα στοιχεία, για να τα διαβάζουμε με την ορθή φορά! Δεν μας ενδιαφέρει το pop (απώθηση) της στοίβας. Μας ενδιαφέρει να διατρέχουμε τη στοίβα, και να διαβάζουμε δυο κόμβους κάθε φορά.
Έχω αφήσει με λατινικούς χαρακτήρες τις μεταβλητές που χρησιμοποιούνταν στο αρχικό πρόγραμμα. Ο πίνακας Edges[] δεν υπάρχει πια, και αντί αυτού χρησιμοποιούμε το cost το οποίο το τροφοδοτούμε από τη δυναμική δομή.
Αυτό το πρόγραμμα αποδεικνύει ότι με τη ΓΛΩΣΣΑ μπορούμε να φτιάξουμε δυναμικές δομές, όπως γράφους.
Ελεύθερη Μνήμη 82 κόμβων
a->b 7
a->c 9
a->f 14
b->c 10
b->d 15
c->d 11
c->f 2
d->e 6
e->f 9
Υπολογισμός βαρών
a 0
b 7
c 9
d 20
e 26
f 11
Διαδρομή από a μέχρι e:acde
Ελεύθερη Μνήμη 100 κόμβων
Ανάγνωση δυαδικού δένδρου με τέσσερις τρόπους
Πρόγραμμα Δένδρο1.gloΠαραλλαγή του κώδικα με τους κόμβους. Τώρα ο πίνακας κομ[] είναι δυο διαστάσεων για να γράφουμε δυο δείκτες, τον αριστερό και το δεξιό ως τιμές δεύτερης διάστασης 1 και 2. Έτσι τώρα κάθε κόμβος έχει δυο δείκτες. Ο πίνακας τιμ[] έγινε πίνακας χαρακτήρων.
Για τη κατασκευή του δένδρου, υπάρχουν πολλοί τρόποι. Εδώ ξεκίνησα από το 7, πήγα στο 4 και έβαλα το 7 σαν αριστερό παιδί, και μετά πήγα στο 2 όπου πέρασα το δένδρο σαν αριστερό παιδί και έβαλα το 3 ως δεξιό παιδί. μετά έβαλα ότι είχα σαν παιδί στο κόμβο με το 1 το οποίο και "σημάδεψα" στη μεταβλητή ρίζα. Κατόπιν γέμισα και ότι χρειάζονταν από την δεξιά πλευρά κάτω από το 1.
Οι τρεις τρόποι preorder, inorder, και postorder, έχουν γίνει με διαδικασία που καλεί τον εαυτό της όποτε το χρειάζεται, δηλαδή χρησιμοποιεί αναδρομή.
Ο τέταρτος τρόπος είναι πιο δύσκολος γιατί η ΓΛΩΣΣΑ δεν έχει κάποια δομή έτοιμη για ουρά, οπότε χρησιμοποίησα την δομή που είχα για ουρά, χωρίς να χρησιμοποιήσω για κάθε κόμβο τον πίνακα τιμ[]. Έτσι ο αριστερός δείκτης δείχνει τον επόμενο κόμβο, και ο δεξιός απλά κρατάει τον αριθμό του κόμβου που θέλουμε να βάλουμε στην ουρά. Υπάρχουν δυο διαδικασίες, η ΕισαγωγήΚόμβου και η ΕξαγωγήΚόμβου, και δεν χρησιμοποιούμε αναδρομή, απλά μια επανάληψη μέχρι η ουρά να αδειάσει. Τη πρώτη φορά βάζουμε στην ουρά την ρίζα.
Κάθε φορά που αδειάζει η ουρά διαγράφεται και το στοιχείο, δηλαδή πηγαίνει στην στοίβα ελεύθερων. Υπάρχει τέλος μια διαδικασία που μοιάζει με την postorder αλλά διαγράφει τα στοιχεία του δένδρου από τη ρίζα, και τα στέλνει στη στοίβα των ελεύθερων.
Στο τέλος μας δίνει το νούμερο των ελεύθερων κόμβων, το 100.
Το δένδρο είναι αυτό:
! 1
! / \
! / \
! / \
! 2 3
! / \ /
! 4 5 6
! / / \
! 7 8 9
Δηλαδή έχουμε 9 κόμβους.
Το αποτέλεσμα είναι αυτό:
Ελεύθερη Μνήμη 91 κόμβων
preorder: 124753689
inorder: 742518693
postorder: 745289631
level-order: 123456789
Ελεύθερη Μνήμη 100 κόμβων
Ανάγνωση δυαδικού δένδρου με τέσσερις τρόπους (2)
Πρόγραμμα ΔένδροΑναζήτησης2.glo
Το ίδιο πρόγραμμα χωρίς αναδρομή στα τρία πρώτα (preorder, inorder, postorder).Εδώ αντί για αναδρομή χρησιμοποιούμε μια ουρά. Θέλουμε στην ουρά να μπαίνει ο αριθμός κόμβου με αρνητικό πρόσημο όταν απλά θέλουμε να τυπωθεί. Όταν στην ουρά μπαίνει με θετικό πρόσημο τότε η ουρά ανατροφοδοτείται με ένα έως τρια στοιχεία ανάλογα αν υπάρχουν παιδιά στον κόμβο.
Προστέθηκαν δυο διαδικασίες για ώθηση και απώθηση σε σωρό.
Η διαγραφή κόμβων έγινε και αυτή μη αναδρομική (παραλλαγή της postorder)
Τώρα το πρόγραμμα δεν έχει αναδρομή δηλαδή είναι εντός της ύλης!
Η εξαγωγή είναι η ίδια
Ελεύθερη Μνήμη 91 κόμβων
preorder: 124753689
inorder: 742518693
postorder: 745289631
level-order: 123456789
Ελεύθερη Μνήμη 100 κόμβων
Πρόγραμμα Run-length encoding
Πρόγραμμα RLE.gloΠαράδειγμα κωδικοποίησης RLE
Το αλφαριθμητικό εισαγωγής και το αποτέλεσμα το έχω πάρει από το παράδειγμα εδώ: Wiki
Μας ενδιαφέρει το πρόγραμμα να εμφανίσει τα αλφαριθμητικά input και output. Tο output θα προκύπτει από την επεξεργασία του input. Για κάθε χαρακτήρα θα υπολογίζεται ο αριθμός εμφάνισης και θα πηγαίνει στην εξαγωγή αμέσως μετά την μετατροπή του αριθμού σε χαρακτήρες.
Χρειαζόμαστε ένα τρόπο να προσθέτουμε χαρακτήρες και αυτό γίνεται μόνο με χρήση πίνακα στη ΓΛΩΣΣΑ.
Για να κάνουμε μετατροπή ακέραιου αριθμού σε χαρακτήρες μας ενδιαφέρει να ξέρουμε προκαταβολικά το μέγεθος σε χαρακτήρες. Αυτό βγαίνει με τη χρήση του δεκαδικού λογαρίθμου του αριθμού. Επειδή η συνάρτηση ΛΟΓ() είναι ο φυσικός λογάριθμος πρέπει να διαιρέσουμε δια του ΛΟΓ(10). Έχουμε μια συνάρτηση που γυρίζει τον αριθμό χαρακτήρων.
Σαν άσκηση για το σπίτι, φτιάχτε μια διαδικασία που θα παίρνει τους πίνακες ΕΞ και ΑΡ καθώς και το ΤΕΛ και θα παράγει από το Output το Input.
Για να εμφανίζονται οι χαρακτήρες μαζί πρέπει σε διαδοχικές ΓΡΑΨΕ να έχουμε τελευταία τιμή ένα χαρακτήρα διαστήματος.
Παράθεση
Input: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Output: 12W1B12W3B24W1B14W
Ταξινόμηση με τρεις ουρές
Πρόγραμμα ΤαξινόμησηΜεΟυρές.glo
Χρήση τριών ουρών για ταξινόμηση. Τις ουρές τις ονομάζω ταινίες, σαν τις μαγνητικές ταινίες παλιών υπολογιστών. Αρχικά βάζουμε στην ταινία Α τη σειρά αλφαριθμητικών που θέλουμε να ταξινομήσουμε. Μετά:
1. Σπάμε την ταινία σε δυο ταινίες. Για να το κάνουμε αυτό συγκρίνουμε το τελευταίο εισαγόμενο με το πρώτο της ταινίας Α, διαλέγουμε μια ταινία που θα αλλάζουμε το συγκρινόμενο.
2.Στη δεύτερη φάση κοιτάμε αν έχουμε όλα τα στοιχεία στην ίδια ταινία (κοιτάμε αν και οι δυο ταινίες έχουν κάτι, δηλαδή οι δείκτες τους δεν είναι μηδέν).
- Αν ναι τότε φτιάχνουμε μια νέα ταινία Α από τα στοιχεία της Β ταινίας και της Γ (συγχώνευση των Β και Γ στο Α). Το τελευταίο στοιχείο της Β το κρατάμε για την πρώτη σύγκριση. Πάμε στο βήμα 1
- Αν όχι τότε έχουμε την απάντηση στη ταινία Γ.
Έξοδος
ΑΘΗΝΑ
ΒΟΛΟΣ
ΘΕΣΣΑΛΟΝΙΚΗ
ΙΩΑΝΝΙΝΑ
ΚΑΛΛΙΘΕΑ
ΜΕΣΟΛΟΓΓΙ
ΝΑΥΠΛΙΟ
ΠΑΤΡΑ
ΠΡΕΒΕΖΑ
ΧΑΝΙΑ
ΧΑΝΙΑ
ΠΡΕΒΕΖΑ
ΠΑΤΡΑ
ΝΑΥΠΛΙΟ
ΜΕΣΟΛΟΓΓΙ
ΚΑΛΛΙΘΕΑ
ΙΩΑΝΝΙΝΑ
ΘΕΣΣΑΛΟΝΙΚΗ
ΒΟΛΟΣ
ΑΘΗΝΑ
Ελεύθερη Μνήμη 80 κόμβων
ΑΘΗΝΑ
ΑΘΗΝΑ
ΒΟΛΟΣ
ΒΟΛΟΣ
ΘΕΣΣΑΛΟΝΙΚΗ
ΘΕΣΣΑΛΟΝΙΚΗ
ΙΩΑΝΝΙΝΑ
ΙΩΑΝΝΙΝΑ
ΚΑΛΛΙΘΕΑ
ΚΑΛΛΙΘΕΑ
ΜΕΣΟΛΟΓΓΙ
ΜΕΣΟΛΟΓΓΙ
ΝΑΥΠΛΙΟ
ΝΑΥΠΛΙΟ
ΠΑΤΡΑ
ΠΑΤΡΑ
ΠΡΕΒΕΖΑ
ΠΡΕΒΕΖΑ
ΧΑΝΙΑ
ΧΑΝΙΑ
Ελεύθερη Μνήμη 100 κόμβων
Ταξινόμηση με τρεις ουρές 2
Πρόγραμμα ΤαξινόμησηΜεΟυρές2.glo
Αντί να συγχωνεύσουμε τις δυο ουρές σε μια, διαβάζοντας και γράφοντας, απλά τις συνδέουμε, και φτιάχνουμε νέους δείκτες για την Α. Αυτό γίνεται γιατί όλοι οι κόμβοι είναι στο ίδιο μέρος. Αν είχαμε ταινίες δεν θα γίνονταν.Ταξινόμηση με τρεις ουρές 3
Πρόγραμμα ΤαξινόμησηΜεΟυρές3.glo
Το τελικό.
Τώρα δεν φτιάχνουμε τις Β και Γ ουρές με χρήση των ελεύθερων κόμβων. Βγάζουμε το κόμβο από την Α και τον βάζουμε στην Β ή στην Γ.
(επόμενο)
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου
You can feel free to write any suggestion, or idea on the subject.