Skip to the content.

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

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


Δ ->

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Εικόνα 3.1.1 Οι βασικές διεπαφές συλλογών της Java

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

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

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


Δ ->