Δομή δεδομένων

Βασικές δομές δεδομένων

Συστοιχία

Ο απλούστερος τύπος δομής δεδομένων είναι ένας γραμμικός πίνακας. Γνωστός και ως μονοδιάστατος πίνακας. Ένας πίνακας περιέχει πολλές τιμές του ίδιου τύπου (ακέραιος αριθμός, κινητές μονάδες, συμβολοσειρά κ.λπ.). Η προσπέλαση των στοιχείων εντός του πίνακα είναι πολύ γρήγορη. Ένας πίνακας έχει συνήθως σταθερό μέγεθος. Αφού καθοριστεί το μέγεθος του πίνακα στην αρχή, μπορεί να μην είναι δυνατή η αύξηση του μεγέθους του πίνακα χωρίς τη δημιουργία ενός νέου μεγαλύτερου πίνακα και την αντιγραφή όλων των τιμών στο νέο πίνακα. Στην επιστήμη των υπολογιστών, μια δομή δεδομένων συστοιχίας ή απλά ένας πίνακας είναι μια δομή δεδομένων που αποτελείται από μια συλλογή στοιχείων (τιμών ή μεταβλητών), καθένα από τα οποία προσδιορίζεται από τουλάχιστον έναν δείκτη ή κλειδί συστοιχίας. Ένας πίνακας αποθηκεύεται έτσι ώστε η θέση κάθε στοιχείου να μπορεί να υπολογιστεί από την πλειάδα του δείκτη του μέσω ενός μαθηματικού τύπου.

Για παράδειγμα, ένας πίνακας 10 ακέραιων μεταβλητών, με δείκτες 0 έως 9, μπορεί να αποθηκευτεί ως 10 λέξεις στις διευθύνσεις μνήμης 2000, 2004, 2008, 2036, έτσι ώστε το στοιχείο με δείκτη i να έχει τη διεύθυνση 2000 + 4 × i.

Καθώς η μαθηματική έννοια του πίνακα μπορεί να αναπαρασταθεί ως δισδιάστατο πλέγμα, οι δισδιάστατοι πίνακες ονομάζονται επίσης μερικές φορές πίνακες. Σε ορισμένες περιπτώσεις ο όρος "διάνυσμα" χρησιμοποιείται στην πληροφορική για να αναφερθεί σε έναν πίνακα, αν και οι πλειάδες αντί για διανύσματα είναι το πιο σωστό μαθηματικό ισοδύναμο. Οι πίνακες χρησιμοποιούνται συχνά για την υλοποίηση πινάκων, ιδίως πινάκων αναζήτησης- η λέξη πίνακας χρησιμοποιείται μερικές φορές ως συνώνυμο του πίνακα.

Οι συστοιχίες είναι από τις παλαιότερες και σημαντικότερες δομές δεδομένων και χρησιμοποιούνται σχεδόν από κάθε πρόγραμμα. Μπορούν επίσης να χρησιμοποιηθούν για την υλοποίηση πολλών άλλων δομών δεδομένων, όπως λίστες και συμβολοσειρές. Εκμεταλλεύονται αποτελεσματικά τη λογική διευθυνσιοδότησης των υπολογιστών. Στους περισσότερους σύγχρονους υπολογιστές και σε πολλές εξωτερικές συσκευές αποθήκευσης, η μνήμη είναι ένας μονοδιάστατος πίνακας λέξεων, των οποίων οι δείκτες είναι οι διευθύνσεις τους. Οι επεξεργαστές, ιδίως οι διανυσματικοί επεξεργαστές, είναι συχνά βελτιστοποιημένοι για λειτουργίες σε πίνακες.

Οι πίνακες είναι χρήσιμοι επειδή οι δείκτες των στοιχείων μπορούν να υπολογιστούν κατά την εκτέλεση. Μεταξύ άλλων, αυτό το χαρακτηριστικό επιτρέπει σε μία μόνο επαναληπτική εντολή να επεξεργάζεται αυθαίρετα πολλά στοιχεία ενός πίνακα. Για το λόγο αυτό, τα στοιχεία μιας δομής δεδομένων πίνακα απαιτείται να έχουν το ίδιο μέγεθος και θα πρέπει να χρησιμοποιούν την ίδια αναπαράσταση δεδομένων. Το σύνολο των έγκυρων πλειάδων δεικτών και οι διευθύνσεις των στοιχείων (και συνεπώς ο τύπος διευθυνσιοδότησης των στοιχείων) είναι συνήθως, αλλά όχι πάντα, σταθερές όσο ο πίνακας είναι σε χρήση.

Ο όρος array χρησιμοποιείται συχνά για να δηλώσει τον τύπο δεδομένων array, ένα είδος τύπου δεδομένων που παρέχεται από τις περισσότερες γλώσσες προγραμματισμού υψηλού επιπέδου και αποτελείται από μια συλλογή τιμών ή μεταβλητών που μπορούν να επιλεγούν από έναν ή περισσότερους δείκτες που υπολογίζονται κατά την εκτέλεση. Οι τύποι συστοιχιών συχνά υλοποιούνται με δομές συστοιχιών- ωστόσο, σε ορισμένες γλώσσες μπορεί να υλοποιούνται με πίνακες κατακερματισμού, συνδεδεμένες λίστες, δέντρα αναζήτησης ή άλλες δομές δεδομένων.

Συνδεδεμένη λίστα

Μια συνδεδεμένη δομή δεδομένων είναι ένα σύνολο πληροφοριών/δεδομένων που συνδέονται μεταξύ τους με αναφορές. Τα δεδομένα συχνά ονομάζονται κόμβοι. Οι αναφορές ονομάζονται συχνά σύνδεσμοι ή δείκτες. Από εδώ και στο εξής, οι λέξεις κόμβος και δείκτης θα χρησιμοποιούνται για αυτές τις έννοιες.

Στις συνδεδεμένες δομές δεδομένων, οι δείκτες αποαναφέρονται ή συγκρίνονται μόνο για ισότητα. Έτσι, οι συνδεδεμένες δομές δεδομένων διαφέρουν από τους πίνακες, οι οποίοι απαιτούν την πρόσθεση και αφαίρεση δεικτών.

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

Στοίβα

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

Η βασική υλοποίηση μιας στοίβας ονομάζεται επίσης δομή "Last In First Out"- ωστόσο υπάρχουν διαφορετικές παραλλαγές υλοποιήσεων στοίβας.

Υπάρχουν βασικά τρεις λειτουργίες που μπορούν να εκτελεστούν σε στοίβες. Αυτές είναι:

• εισαγωγή ("ώθηση") ενός στοιχείου σε μια στοίβα
• διαγραφή ("popping") ενός στοιχείου από τη στοίβα
• εμφάνιση του περιεχομένου του κορυφαίου στοιχείου της στοίβας ("κρυφοκοίταγμα")

Ουρά

Η ουρά είναι ένας αφηρημένος τύπος δεδομένων ή μια γραμμική δομή δεδομένων, στην οποία το πρώτο στοιχείο εισάγεται από το ένα άκρο (την "ουρά") και η διαγραφή υπάρχοντος στοιχείου πραγματοποιείται από το άλλο άκρο (την "κεφαλή"). Η ουρά είναι μια δομή "First In First Out". "First In First Out" σημαίνει ότι τα στοιχεία που εισάγονται πρώτα στην ουρά θα βγουν πρώτα, και τα στοιχεία που εισάγονται τελευταία στην ουρά θα βγουν τελευταία. Ένα παράδειγμα ουράς είναι οι ουρές αναμονής. Το πρώτο άτομο στην ουρά βγαίνει πρώτο, και το τελευταίο άτομο στην ουρά βγαίνει τελευταίο.

Η διαδικασία προσθήκης ενός στοιχείου σε μια ουρά ονομάζεται "εγγραφή σε ουρά" και η διαδικασία αφαίρεσης ενός στοιχείου από μια ουρά ονομάζεται "απομάκρυνση από ουρά".

Γράφημα

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

Μια δομή δεδομένων γράφου αποτελείται από ένα πεπερασμένο (και ενδεχομένως μεταβλητό) σύνολο διατεταγμένων ζευγών, που ονομάζονται ακμές ή τόξα, ορισμένων οντοτήτων που ονομάζονται κόμβοι ή κορυφές. Όπως και στα μαθηματικά, μια ακμή (x,y) λέγεται ότι δείχνει ή πηγαίνει από το x στο y. Οι κόμβοι μπορεί να είναι μέρος της δομής γράφου ή μπορεί να είναι εξωτερικές οντότητες που αναπαρίστανται με ακέραιους δείκτες ή αναφορές. Μια δομή δεδομένων γράφου μπορεί επίσης να συσχετίζει σε κάθε ακμή κάποια τιμή ακμής, όπως μια συμβολική ετικέτα ή ένα αριθμητικό χαρακτηριστικό.

Δέντρο

Το δέντρο είναι μια από τις πιο ισχυρές προηγμένες δομές δεδομένων. Εμφανίζεται συχνά σε προηγμένα θέματα όπως η Τεχνητή Νοημοσύνη (ΤΝ) και ο σχεδιασμός. Παραδόξως, το δέντρο είναι σημαντικό σε μια πολύ πιο βασική εφαρμογή - την τήρηση ενός αποτελεσματικού ευρετηρίου.

Όταν χρησιμοποιείται ένα δέντρο, υπάρχει μεγάλη πιθανότητα να χρησιμοποιείται ένα ευρετήριο. Ο απλούστερος τύπος ευρετηρίου είναι ένας ταξινομημένος κατάλογος πεδίων-κλειδιών. Ένα δέντρο έχει συνήθως μια καθορισμένη δομή. Στην περίπτωση ενός δυαδικού δέντρου, μπορείτε να χρησιμοποιήσετε μια δυαδική αναζήτηση για να εντοπίσετε οποιοδήποτε στοιχείο χωρίς να χρειάζεται να εξετάσετε κάθε στοιχείο.

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

Το πρόβλημα με μια απλή διατεταγμένη λίστα εμφανίζεται όταν αρχίζετε να προσθέτετε νέα στοιχεία και πρέπει να διατηρείτε τη λίστα ταξινομημένη - μπορεί να γίνει αρκετά αποτελεσματικά, αλλά απαιτεί κάποιες τροποποιήσεις. Επιπλέον, ένα γραμμικό ευρετήριο δεν είναι εύκολο να διαμοιραστεί επειδή ολόκληρο το ευρετήριο πρέπει να "κλειδωθεί" όταν ένας χρήστης το επεξεργάζεται, ενώ ένα "κλαδί" ενός δέντρου μπορεί να κλειδωθεί, αφήνοντας τα άλλα κλαδιά επεξεργάσιμα από άλλους χρήστες (καθώς δεν μπορούν να επηρεαστούν).

Πίνακας κατακερματισμού

Ένας πίνακας κατακερματισμού είναι ένας πίνακας όπου κάθε δείκτης δείχνει σε μια συνδεδεμένη λίστα με βάση μια τιμή κατακερματισμού. Μια τιμή κατακερματισμού είναι μια τιμή που καθορίζεται από μια συνάρτηση κατακερματισμού. Μια συνάρτηση κατακερματισμού καθορίζει μια μοναδική τιμή με βάση τα δεδομένα που αποθηκεύει. Αυτό επιτρέπει την πρόσβαση σε δεδομένα σε σταθερό χρόνο, επειδή ο υπολογιστής ξέρει πάντα πού να ψάξει.

Κάθε κόμβος δείχνει έναν άλλο κόμβο.