5.1 Δομές Δεδομένων

© Γιάννης Κωστάρας

---

Δ

>

---

Δεδομένα (data) είναι η αφαιρετική αναπαράσταση της πραγματικότητας και συνεπώς μια απλοποιημένη όψη της. Πληροφορία (information) είναι η συλλογή δεδομένων και ο συσχετισμός τους. Πληροφορική είναι η επιστήμη που μελετά τα δεδομένα κάτω απ’ τις ακόλουθες σκοπιές:

• Υλικού
• Γλωσσών προγραμματισμού
• Δομών Δεδομένων
• Ανάλυσης Δεδομένων

Με τον όρο Δομή Δεδομένων (data structure) εννοούμε ένα σύνολο δεδομένων μαζί μ’ ένα σύνολο επιτρεπτών λειτουργιών στα δεδομένα αυτά. Υπάρχουν τριών ειδών τύποι δεδομένων:

• υλικού, π.χ. προσημασμένος ακέραιος σταθερής υποδιαστολής
• ιδεατοί, δηλ. τύποι δεδομένων που προσφέρει η γλώσσα προγραμματισμού όπως int, boolean κλπ.
• αφηρημένοι, δηλ. τύποι δεδομένων που δημιουργεί ο προγραμματιστής για ν’ απεικονίσει καλύτερα τα δεδομένα του προβλήματός του.

Μια δομή δεδομένων αποτελείται από τα εξής τρία στοιχεία:

• μια δομή αποθήκευσης
• ένα σύνολο συναρτήσεων που εκτελούν μια λειτουργία στο περιεχόμενο της δομής
• ένα σύνολο από αλγορίθμους, έναν αλγόριθμο ανά συνάρτηση, που περιγράφουν τις λειτουργίες στο περιεχόμενο της δομής.

Αλγόριθμος είναι ένα πεπερασμένο σύνολο εντολών αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο για να επιτευχθεί ένα επιθυμητό αποτέλεσμα.

Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα

Οι βασικές λειτουργίες (ή πράξεις) επί των δομών είναι οι ακόλουθες:

• Προσπέλαση
• Εισαγωγή
• Διαγραφή
• Αναζήτηση
• Ταξινόμηση
• Αντιγραφή
• Συγχώνευση
• Διαχωρισμός

Δεν χρησιμοποιούνται πάντα όλες οι παραπάνω πράξεις σε όλες τις δομές. Στη συνέχεια αυτής της εβδομάδας θα μελετήσουμε τις διάφορες δομές δεδομένων της γλώσσας προγραμματισμού Java με βάση τις παραπάνω πράξεις. Έχουμε ήδη δει τη δομή δεδομένων πίνακας (array).

Μια δομή δεδομένων αποτελείται από κόμβους (nodes). Ένας κόμβος με τη σειρά του αποτελείται από πεδία (fields) τα οποία διακρίνονται σε δεδομένα (data) και δείκτες (links). Ένας δείκτης δείχνει στη διεύθυνση ενός κόμβου και η διεύθυνση αυτή μπορεί να είναι είτε απόλυτη, είτε σχετική, είτε μια διεύθυνση βάσης.

Ανάλογα, επομένως, με το πόσους δείκτες διαθέτει μια δομή δεδομένων, μπορούμε να τις ταξινομήσουμε στις ακόλουθες κατηγορίες:

• κανένας δείκτης, δηλ. μόνο δεδομένα ίδιου τύπου (πίνακες)
• ένας δείκτης (γραμμικές λίστες)
• δύο δείκτες (δυαδικά δέντρα)
• περισσότεροι από δύο δείκτες (δέντρα, γράφοι)

Επίσης, θα μιλήσουμε και για τις δυνατότητες αναζήτησης και ταξινόμησης που προσφέρει η γλώσσα.

Η δομή δεδομένων Πίνακας (array) έχει τους εξής περιορισμούς:

• έχει προκαθορισμένο μέγεθος που δεν μπορεί ν’ αλλάξει αργότερα και άρα δεν συνίσταται αν δεν γνωρίζουμε εκ των προτέρων τον αριθμό των στοιχείων που θέλουμε ν’ αποθηκεύσουμε σ’ αυτόν
• μπορεί ν’ αποθηκεύσει μόνο στοιχεία ίδιου τύπου

Για να ξεπεραστούν οι ανωτέρω περιορισμοί, η Java δημιούργησε νέες δομές δεδομένων όπως θα δούμε στη συνέχεια. Οι δομές αυτές έχουν τα εξής χαρακτηριστικά:

• Το μέγεθός τους μεταβάλλεται δυναμικά
• Μπορούμε να εισάγουμε οποιοδήποτε τύπο αντικειμένου σε μία τέτοια δομή
• ΔΕΝ υποστηρίζουν εισαγωγή αρχέγονων τύπων (π.χ. int), τα στοιχεία τους μπορούν να είναι μόνο δείκτες σε αντικείμενα. Στην περίπτωση που θέλουμε ν’ αποθηκεύσουμε αρχέγονους τύπους σε μια συλλογή χρησιμοποιούμε τους επικαλυπτόμενους τύπους (wrapper types), π.χ. Integer.

Δομές Δεδομένων στη Java

Προτού προχωρήσουμε, θα δώσουμε μια σύντομη περιγραφή των δομών δεδομένων που προσφέρει η γλώσσα Java.

Εικόνα 5.1.1 Οι βασικές διεπαφές δομών δεδομένων της Java

Όπως βλέπετε στην παραπάνω εικόνα, αυτές χωρίζονται σε δυο μεγάλες κατηγορίες:

• Συλλογές (Collections) ή Ακολουθίες (Sequences)
• Πίνακες κατακερματισμού (Maps) ή Συσχετιζόμενοι πίνακες (associative maps)

Οι συλλογές αποθηκεύουν τα δεδομένα με ακολουθιακό τρόπο και κατηγοριοποιούνται σε:

• Σύνολα (Sets) που δεν περιέχουν διπλότυπα, δηλ. την ίδια τιμή πάνω από μια φορά, ενώ δεν έχει σημασία η σειρά των δεδομένων. Η υποδιεπαφή SortedSet ταξινομεί τα δεδομένα της. Η NavigableSet διαθέτει μεθόδους που επιτρέπουν να βρείτε το στοιχείο που είναι πιο κοντά σ’ ένα στοιχείο που αναζητάτε σ’ αυτήν.
• Λίστες (Lists) όπου η σειρά των δεδομένων έχει σημασία και μπορούν να περιέχουν διπλότυπα
• Ουρές (Queues) που δέχονται δεδομένα από την ουρά τους (tail) και εξάγουν δεδομένα προς επεξεργασία από την κεφαλή τους (head). Η υποδιεπαφή Deque είναι μια διπλή ουρά, δηλ. επιτρέπει την εισαγωγή/εξαγωγή δεδομένων κι από τα δυο άκρα της.

Οι πίνακες κατακερματισμού αποτελούν συσχετίσεις κλειδιού-τιμής (key-value), δηλ. μπορείτε να ανακτάτε την τιμή αν γνωρίζετε το κλειδί. Η υποδιεπαφή SortedMap εγγυάται ότι θα επιστρέψει τις τιμές με αύξουσα τιμή του κλειδιού, ενώ η NavigableMap (όπως και η NavigableSet) βρίσκει το κλειδί που είναι πιο κοντά σ’ ένα στοιχείο που αναζητάτε σ’ αυτήν.

---

Δ

>

---