3.1 Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
Τα δεδομένα ενός προβλήματος αποθηκεύονται στον υπολογιστή,
- είτε στην κύρια μνήμη του
- είτε στη δευτερεύουσα μνήμη του (σε διάφορες περιφερειακές συσκευές όπως ο σκληρός δίσκος)
Η αποθήκευση αυτή γίνεται με ένα συστηματικά τρόπο, μέσω μίας Δομής Δεδομένων.
Ορισμός Δομή Δεδομένων είναι ένα σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών. Κάθε μορφή δομής δεδομένων αποτελείται από ένα σύνολο κόμβων (nodes).
Για παράδειγμα τα δεδομένα ενός αρχείου μαθητών αποθηκεύονται στο σκληρό δίσκο με ένα συστηματικό τρόπο, οργανωμένα σε κόμβους για κάθε ξεχωριστό μαθητή που λέγονται εγγραφές και σε κάθε εγγραφή περιέχονται τα δεδομένα που περιγράφουν τον κάθε μαθητή
Οι βασικές λειτουργίες (ή αλλιώς πράξεις) επί των δομών δεδομένων είναι οι ακόλουθες:
- Προσπέλαση (access), πρόσβαση σε έναν κόμβο με σκοπό να εξετασθεί ή να τροποποιηθεί το περιεχόμενό του.
- Εισαγωγή (insertion), δηλαδή η προσθήκη νέων κόμβων σε μία υπάρχουσα δομή.
- Διαγραφή (deletion), που αποτελεί το αντίστροφο της εισαγωγής, δηλαδή ένας κόμβος αφαιρείται από μία δομή.
- Αναζήτηση (searching), κατά την οποία προσπελαύνονται οι κόμβοι μιας δομής, προκειμένου να εντοπιστούν ένας ή περισσότεροι που έχουν μια δεδομένη ιδιότητα.
- Ταξινόμηση (sorting), όπου οι κόμβοι μιας δομής διατάσσονται κατά αύξουσα ή φθίνουσα σειρά.
- Αντιγραφή (copying), κατά την οποία όλοι οι κόμβοι ή μερικοί από τους κόμβους μίας δομής αντιγράφονται σε μία άλλη δομή.
- Συγχώνευση (merging), κατά την οποία δύο ή περισσότερες δομές συνενώνονται σε μία ενιαία δομή.
- Διαχωρισμός (separation), που αποτελεί την αντίστροφη πράξη της συγχώνευσης.
Παρατηρήσεις
- σπάνια χρησιμοποιούνται και οι οκτώ λειτουργίες για κάποια δομή
- συνήθως μία δομή δεδομένων να είναι αποδοτικότερη από μία άλλη δομή με κριτήριο κάποια λειτουργία, για παράδειγμα την αναζήτηση, αλλά λιγότερο αποδοτική για κάποια άλλη λειτουργία, για παράδειγμα την εισαγωγή
- υπάρχουν πολλές διαφορετικέ δομές δεδομένων και είναι σημαντικό η επιλογή της καταλληλότερης δομής κάθε φορά
Υπάρχει μεγάλη εξάρτηση μεταξύ της δομής δεδομένων και του αλγορίθμου που επεξεργάζεται τη δομή. Το πρόγραμμα πρέπει να θεωρεί τη δομή δεδομένων και τον αλγόριθμο ως μία αδιάσπαστη ενότητα, όπως φαίνεται στην εξίσωση που διατυπώθηκε το 1976 από τον Wirth :
Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
Θα μπορούσαμε να πούμε ότι ο ίδιος αλγόριθμος με διαφορετική δομή δεδομένων, δίνει κάθε φορά ένα διαφορετικό πρόγραμμα λόγω του διαφορετικού τρόπου που πραγματοποιούνται οι λειτουργίες σε κάθε ξεχωριστή δομή.
Παράδειγμα
Έστω ότι πρέπει να γραφεί ένας αλγόριθμος που να δέχεται ως είσοδο το όνομα ενός συνδρομητή του ΟΤΕ και να δίνει ως έξοδο το τηλέφωνό του.
Πρώτη Λύση Δομή Δεδομένων:
Δημιουργείται μία ακολουθία (Ονομα 1, Τηλέφωνο 1), (Ονομα 2, Τηλέφωνο 2), ..., (Ονομα n, Τηλέφωνο n), όπου οι μεταβλητές Ονομα i και Τηλέφωνο i αναφέρονται στο όνομα και στο τηλέφωνο του i-οστού συνδρομητή, για i = 1,2,...,n.
|
Ονομα 1
|
Τηλέφωνο 1
|
|
Ονομα 2
|
Τηλέφωνο 2
|
|
Ονομα 3
|
Τηλέφωνο 3
|
|
Ονομα 4
|
Τηλέφωνο 4
|
|
….
|
….
|
|
Ονομα ν
|
Τηλέφωνο ν
|
Αλγόριθμος: Η ακολουθία ανιχνεύεται μέχρι να βρεθεί το ζητούμενο όνομα του συνδρομητή Ονομα k και εκτυπώνεται το τηλέφωνο Τηλέφωνο k.
Ο αλγόριθμος αυτός είναι αποδοτικός για συνδρομητές ενός χωριού ή μίας κωμόπολης, αλλά για συνδρομητές μίας μεγάλης πόλης είναι χρονοβόρος.
Δεύτερη Λύση Δομή Δεδομένων:
|
Χρησιμοποιείται και πάλι η ακολουθία της πρώτης λύσης, αλλά αυτή τη φορά οι συνδρομητές είναι ταξινομημένοι λεξικογραφικά.
|
|
1
|
Α-Ονομα 1
|
Α-Τηλέφωνο 1
|
|
2
|
Α-Ονομα 2
|
Α-Τηλέφωνο 2
|
|
3
|
Α-Ονομα 3
|
Α-Τηλέφωνο 3
|
|
…
|
……
|
….
|
|
10563
|
Β-Ονομα 1
|
Β-Τηλέφωνο 1
|
|
10564
|
Β-Ονομα 2
|
Β-Τηλέφωνο 2
|
|
10565
|
Β-Ονομα 3
|
Β-Τηλέφωνο 3
|
|
…
|
…..
|
….
|
|
18631
|
Γ-Ονομα 1
|
Γ-Τηλέφωνο 1
|
|
|
….
|
….
|
|
56978
|
Ω-Ονομα 1
|
Ω-Τηλέφωνο 1
|
|
…
|
….
|
…
|
|
Δημιουργείται μία δεύτερη ακολουθία με τα στοιχεία (Α,n1), (Β,n2), ..., (Ω,n24).
Κάθε στοιχείο της δεύτερης αυτής ακολουθίας δίνει για κάθε γράμμα του αλφαβήτου τη θέση ni (για i = 1, 2, ..., 24) στην πρώτη ακολουθία με το πρώτο όνομα συνδρομητή που αρχίζει από το γράμμα αυτό.
|
|
Αρχικό γράμμα
|
Θέση του πρώτου ονόματος στον ταξινομημένο κατάλογο
|
|
Α
|
1
|
|
Β
|
10563
|
|
Γ
|
18631
|
|
…
|
|
|
Ω
|
56978
|
Αλγόριθμος: Αφήνεται για άσκηση στο μαθητή.
ΚΑΤΗΓΟΡΙΕΣ ΔΟΜΩΝ ΔΕΔΟΜΕΝΩΝ
Οι δομές δεδομένων διακρίνονται σε δύο μεγάλες κατηγορίες:
|
στατικές (static)
· αποθηκεύονται σε συνεχόμενες θέσεις μνήμης
· έχουν σταθερό μέγεθος το οποίο καθορίζεται στην αρχή του προγράμματος, στο τμήμα δηλώσεων
Οι στατικές δομές υλοποιούνται με πίνακες
|
δυναμικές (dynamic)
· δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης
· στηρίζονται στην τεχνική της λεγόμενης δυναμικής παραχώρησης μνήμης (dynamic memory allocation) δηλαδή δεν έχουν σταθερό μέγεθος, αλλά ο αριθμός των κόμβων τους μεγαλώνει και μικραίνει καθώς στη δομή εισάγονται νέα ή διαγράφονται κάποια δεδομένα αντίστοιχα
· το μέγεθος της μνήμης που χρειάζονται καθορίζεται κατά την εκτέλεση του προγράμματος
Οι δυναμικές δομές υλοποιούνται με λίστες, δέντρα και γράφους
|
Παρατηρήσεις
- Μια δομή δεδομένων δεν είναι εγγενώς στατική ή δυναμική, αλλά εξαρτάται από τις δυνατότητες της γλώσσας προγραμματισμού που χρησιμοποιούμε και από τον τρόπο υλοποίησης της δομής στη γλώσσα αυτή.
- Δεν υποστηρίζουν όλες οι γλώσσες προγραμματισμού όλες τις δομές δεδομένων.
- Οι σύγχρονες γλώσσες προγραμματισμού συνήθως υποστηρίζουν και τις δυναμικές δομές δεδομένων.
- Το προγραμματιστικό περιβάλλον ΓΛΩΣΣΑ, υποστηρίζει μόνο στατικές δομές και κατά συνέπεια, η δομή του πίνακα αντιμετωπίζεται ως στατική και για να χρησιμοποιηθεί ένας πίνακας θα πρέπει να έχει πρώτα δηλωθεί, τόσο ο πίνακας, όσο και το μέγεθός του.
- Επιπλέον, οι δομές ουρά και στοίβα θεωρούνται επίσης στατικές δομές για τη ΓΛΩΣΣΑ, και στο πλαίσιο του μαθήματος υλοποιούνται με τη χρήση μονοδιάστατων πινάκων.
- Οι λειτουργίες των δομών είναι γενικές και αποκτούν συγκεκριμένη σημασία, ανάλογα με τη δομή στην οποία εφαρμόζονται. Για παράδειγμα σε μια δομή πίνακα που στη ΓΛΩΣΣΑ , διαχειρίζεται ως στατική δομή δεδομένων, κατά την πράξη της ταξινόμησης, δεν αναδιατάσσονται οι κόμβοι του πίνακα αλλά το περιεχόμενο των κόμβων.
