Δεδομένα και δομές δεδομένων
Κεφ. 3 §3.1–3.3 · Δεδομένα, λειτουργίες, στατικές και δυναμικές δομές, πίνακες
Ο τηλεφωνικός κατάλογος του κινητού σου έχει εκατοντάδες επαφές, κι όμως βρίσκεις την «Κατερίνα» σε κλάσματα του δευτερολέπτου. Το μυστικό δεν είναι μόνο ο αλγόριθμος, αλλά και πώς είναι οργανωμένα τα δεδομένα.
Αυτή η οργάνωση λέγεται δομή δεδομένων — και η σωστή επιλογή της κάνει ένα πρόγραμμα γρήγορο ή απελπιστικά αργό.
Δεδομένα
Δεδομένα είναι τα ακατέργαστα γεγονότα — οι «πρώτες ύλες» της επεξεργασίας (π.χ. ο αριθμός 17 ή το όνομα «Νίκος»). Όταν τα δεδομένα επεξεργαστούν και αποκτήσουν νόημα, προκύπτει πληροφορία.
Η Επιστήμη των Υπολογιστών μελετά τα δεδομένα από διάφορες οπτικές γωνίες:
- Υλικού: πώς αποθηκεύονται στη μνήμη και στις περιφερειακές συσκευές.
- Γλωσσών προγραμματισμού: ποιοι τύποι δεδομένων υπάρχουν σε κάθε γλώσσα.
- Δομών δεδομένων: πώς οργανώνονται ώστε να επεξεργάζονται αποδοτικά.
- Ανάλυσης δεδομένων: πώς καταγράφονται και συσχετίζονται για να δώσουν πληροφορία.
Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
Δομή δεδομένων είναι ένα σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών. Αλγόριθμος και δομή δεδομένων είναι αλληλένδετα: η επιλογή της δομής επηρεάζει τον αλγόριθμο, και το αντίστροφο.
Οι βασικές λειτουργίες (πράξεις) επί των δομών δεδομένων είναι:
- Προσπέλαση: πρόσβαση σε έναν κόμβο για εξέταση ή αλλαγή του.
- Εισαγωγή: προσθήκη νέου κόμβου.
- Διαγραφή: αφαίρεση κόμβου.
- Αναζήτηση: εύρεση κόμβων με συγκεκριμένα χαρακτηριστικά.
- Ταξινόμηση: διάταξη των κόμβων σε αύξουσα ή φθίνουσα σειρά.
- Αντιγραφή: αντιγραφή κόμβων σε άλλη δομή.
- Συγχώνευση: δύο ή περισσότερες δομές ενώνονται σε μία.
- Διαχωρισμός: μια δομή χωρίζεται σε δύο ή περισσότερες.
Η ένωση δύο ταξινομημένων πινάκων σε έναν νέο ταξινομημένο πίνακα είναι η λειτουργία:
Στατικές και δυναμικές δομές
- Στατικές δομές: το ακριβές μέγεθός τους καθορίζεται πριν από την εκτέλεση του προγράμματος και δεν αλλάζει. Τα στοιχεία τους αποθηκεύονται σε συνεχόμενες θέσεις μνήμης. Χαρακτηριστικό παράδειγμα: ο πίνακας.
- Δυναμικές δομές: δεν έχουν σταθερό μέγεθος — μεγαλώνουν και μικραίνουν κατά την εκτέλεση. Τα στοιχεία τους δεν βρίσκονται απαραίτητα σε συνεχόμενες θέσεις· συνδέονται με δείκτες. Παραδείγματα: λίστες, δένδρα, γράφοι.
Στατικές ή δυναμικές μπορούν να υλοποιηθούν και η στοίβα και η ουρά — στο βιβλίο τις υλοποιούμε με πίνακα, δηλαδή στατικά.
Πίνακες
Πίνακας είναι μια δομή που περιέχει στοιχεία του ίδιου τύπου (ακέραια, πραγματικά κ.λπ.), με σταθερό πλήθος. Είναι στατική δομή και κάθε στοιχείο του προσπελάζεται άμεσα μέσω του δείκτη του (της θέσης του).
- Μονοδιάστατος πίνακας (διάνυσμα): μία σειρά στοιχείων, π.χ. οι βαθμοί 25 μαθητών — Β[1], Β[2], …, Β[25].
- Δισδιάστατος πίνακας: γραμμές και στήλες, π.χ. οι βαθμοί 25 μαθητών σε 6 μαθήματα — Β[i, j] είναι ο βαθμός του μαθητή i στο μάθημα j.
- Τετραγωνικός: δισδιάστατος με ίσο αριθμό γραμμών και στηλών.
Οι πίνακες έχουν και περισσότερες διαστάσεις, αλλά συνήθως αρκούν μία ή δύο.
Ποιο είναι βασικό χαρακτηριστικό μιας στατικής δομής δεδομένων;
Μέθοδος: επιλογή δομής δεδομένων
- Ξέρω από πριν πόσα στοιχεία θα αποθηκεύσω; Ναι → πίνακας (στατική). Όχι, αλλάζουν συνεχώς → δυναμική δομή.
- Χρειάζομαι άμεση πρόσβαση σε οποιοδήποτε στοιχείο με τη θέση του; → πίνακας.
- Έχω δεδομένα με δύο διαστάσεις (π.χ. μαθητής × μάθημα); → δισδιάστατος πίνακας.
- Η πρόσβαση γίνεται μόνο από το ένα άκρο (τελευταίο μέσα, πρώτο έξω); → στοίβα. Πρώτο μέσα, πρώτο έξω; → ουρά.
- Γίνονται πολλές εισαγωγές/διαγραφές στη μέση; → λίστα.
Παράδειγμα 1: Ένα σχολείο θέλει να αποθηκεύσει τις απουσίες 120 μαθητών για καθεμία από τις 5 ημέρες της εβδομάδας. Ποια δομή είναι κατάλληλη και πόσα στοιχεία έχει;
Λύση: Τα δεδομένα έχουν δύο διαστάσεις (μαθητής, ημέρα), ίδιο τύπο (ακέραιοι) και γνωστό πλήθος, άρα ένας δισδιάστατος πίνακας ΑΠ[120, 5]. Πλήθος στοιχείων: . Αν ορίσεις ότι η στήλη 1 είναι η Δευτέρα, τότε το ΑΠ[37, 2] είναι οι απουσίες του 37ου μαθητή την Τρίτη.
Παράδειγμα 2: Ποια λειτουργία επί δομής δεδομένων περιγράφει καθεμία ενέργεια;
- (α) Ο καθηγητής βρίσκει τον μαθητή με αριθμό μητρώου 1024.
- (β) Χωρίζεις τους μαθητές σε δύο πίνακες: άρρενες και θήλεις.
- (γ) Αλλάζεις τον βαθμό του 5ου μαθητή.
- (δ) Βάζεις τους μαθητές σε αλφαβητική σειρά.
Λύση: (α) Αναζήτηση · (β) Διαχωρισμός · (γ) Προσπέλαση (πρόσβαση για αλλαγή) · (δ) Ταξινόμηση.
Θέμα τύπου Πανελλαδικών: Να εξηγήσετε τη σχέση «Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα» και να αναφέρετε δύο διαφορές στατικών και δυναμικών δομών.
Λύση: Ένα πρόγραμμα αποτελείται από τον αλγόριθμο (τις ενέργειες) και τις δομές δεδομένων στις οποίες αυτός εφαρμόζεται. Τα δύο είναι αλληλένδετα: η επιλογή μιας δομής καθορίζει ποιοι αλγόριθμοι μπορούν να εφαρμοστούν αποδοτικά (π.χ. η δυαδική αναζήτηση απαιτεί ταξινομημένο πίνακα).
Διαφορές: (1) Στις στατικές το μέγεθος καθορίζεται πριν από την εκτέλεση, στις δυναμικές μεταβάλλεται κατά την εκτέλεση. (2) Οι στατικές αποθηκεύονται σε συνεχόμενες θέσεις μνήμης, ενώ οι δυναμικές όχι απαραίτητα — τα στοιχεία τους συνδέονται με δείκτες.
Η φράση «Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα» είναι ο τίτλος βιβλίου του Ελβετού επιστήμονα Niklaus Wirth (1976), δημιουργού της γλώσσας Pascal. Η ΓΛΩΣΣΑ του σχολικού βιβλίου μοιάζει αρκετά με την Pascal.
Ένας πίνακας Β[8, 8] που αναπαριστά σκακιέρα είναι:
Η θέση κάθε στοιχείου ενός δισδιάστατου πίνακα Α[4, 5] μπορεί να αντιστοιχιστεί σε θέση μονοδιάστατου πίνακα Β[20], γραμμή προς γραμμή (πρώτα όλη η 1η γραμμή, μετά η 2η κ.ο.κ.). Σε ποια θέση του Β θα βρίσκεται το Α[3, 2]; Γράψε τον γενικό τύπο για το Α[i, j].
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Πριν από τη 3η γραμμή υπάρχουν 2 πλήρεις γραμμές των 5 στοιχείων, δηλαδή 10 στοιχεία. Το Α[3, 2] είναι το 2ο της 3ης γραμμής, άρα θέση . Γενικά: . Έλεγχος: Α[1, 1] → 1, Α[4, 5] → ✓. Έτσι ακριβώς αποθηκεύει ένας υπολογιστής τους πίνακες στη μνήμη, που είναι «μονοδιάστατη».
- «Ο πίνακας μπορεί να έχει στοιχεία διαφορετικού τύπου.» Λάθος: όλα του ίδιου τύπου.
- Σύγχυση προσπέλασης (πρόσβαση σε γνωστή θέση) με αναζήτηση (εύρεση με βάση την τιμή).
- «Η στοίβα είναι πάντα στατική δομή.» Υλοποιείται στατικά (με πίνακα) ή δυναμικά.
- Δεδομένα = ακατέργαστα γεγονότα· πληροφορία = αποτέλεσμα της επεξεργασίας τους.
- Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα.
- 8 λειτουργίες: προσπέλαση, εισαγωγή, διαγραφή, αναζήτηση, ταξινόμηση, αντιγραφή, συγχώνευση, διαχωρισμός.
- Στατικές: σταθερό μέγεθος, συνεχόμενες θέσεις (πίνακας). Δυναμικές: μεταβλητό μέγεθος, δείκτες.
- Πίνακας: στοιχεία ίδιου τύπου, άμεση πρόσβαση με δείκτη, μονο- ή δισδιάστατος.