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

Εισαγωγή

Ένας άλλος ορισμός της Επιστήμης των Υπολογιστών είναι αυτός που τη θεωρεί σαν τη μελέτη των δεδομένων από τις σκοπιές : του υλικού, των γλωσσών προγραμματισμού, της Δομής Δεδομένων και της ανάλυσης των δεδομένων.

Με τον όρο δομή δεδομένων (data structure) εννοούμε ένα σύνολο δεδομένων μαζί με ένα σύνολο επιτρεπτών λειτουργειών στα δεδομένα αυτά. Μια μορφή δομής δεδομένων είναι η εγγραφή(record), που μπορεί οι μεταβλητές της να χαρακτηρίζουν ένα πρόσωπο, ένα είδος κλπ. Οι μεταβλητές της αυτές ονομάζονται πεδία (fields). Άλλη μορφή δομής δεδομένων είναι το αρχείο (file) που αποτελείται από ένα σύνολο εγγραφών. Μια επιτρεπτή λειτουργία σε ένα αρχείο είναι η σειριακή προσπέλαση όλων των εγγραφών του.

Υπάρχει μεγάλη εξάρτηση μεταξύ του τρόπου δομής δεδομένων και του αλγόριθμου που επεξεργάζεται τα δεδομένα. Μάλιστα δε κάθε πρόγραμμα πρέπει να βλέπει τη δομή δεδομένων και τον αλγόριθμο σαν μια ενότητα. Η παρατήρηση αυτή δικαιολογεί την εξίσωση του Wirth :

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

Βασικές λειτουργίες

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

1. Προσπέλαση(Accessing). Συνήθως αναζητάμε έναν κόμβο είτε για να εξετάσουμε

το περιεχόμενό του ή να το τροποποιήσουμε(update).

1. Εισαγωγή(Insertion). Πολλές φορές επιθυμούμε να προσθέσουμε ένα νέο κόμβο

σε μια υπάρχουσα δομή.

1. Διαγραφή(deletion). Το αντίστροφο της εισαγωγής.
2. Αναζήτηση(searching). Το ρπόβλημα εδώ είναι η προσπέλαση ενός ή περισσότερων

κόμβων που έχουν σαν χαρακτηριστικό την ύπαρξη της ίδιας τιμής σε κάποιο ή κάποια πεδία του κόμβου. Το πεδίο του κόμβου που ανιχνεύεται λέγεται κλειδί(key).

1. Ταξινόμηση(sorting). Σε πολλές εφαρμογές οι κόμβοι πρέπει να ταξινομηθούν

σύμφωνα με την αύξουσα ή τη φθίνουσα σειρά ενός ή περισσότερων πεδίων του κόμβου.

1. Αντιγραφή(copying)
2. Συνένωση(combining)
3. Διαχωρισμός(separating)

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

Πίνακες

Η πιο απλή μορφή δομής δεδομένων είναι ο πίνακας(array) που αναφέρεται σε ένα σύνολο στοιχείων του ίδιου τύπου(π.χ. real, integer, boolean κτλ.). Η δήλωση των στοιχείων ενός πίνακα και η μέθοδος αναφοράς της εξαρτάται από τη συγκεκριμένη γλώσσα, υψηλού επιπέδου, που χρησιμοποιείται.

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

Για παράδειγμα στην PASCAL έχουμε τον ορισμό : bathmologia : array[1..10] of integer; Η έννοια του μονοδιάστατου πίνακα μπορεί να επεκταθεί και σε πίνακες μέχρι ν-διαστάσεις. Στις περισσότερες γλώσσες προγραμματισμού ο απαραίτητος χώρος μνήμης για τη φύλαξη ενός πίνακα καθορίζεται κατά τη μετάφραση(compilation) του προγράμματος.

Υπάρχουν επίσης 3 ειδικές μορφές πινάκων : οι συμμετρικοί κα τριγωνικοί, οι τριδιαγώνιοι και οι αραιοί.

Ένας τριδιαγώνιος πίνακας Α μεγέθους nxn είναι ένας πίνακας του οποίου όλα τα στοιχεία είναι 0 εκτός από τα στοιχεία της κύριας διαγωνίου και των δύο άλλων (παράλληλων) διαγωνίων που είναι διπλανές στην κύρια διαγώνιο. Ένας πίνακας λέγεται αραιός (sparse) όταν ένα μεγάλο ποσοστό των στοιχείων του είναι 0.

Γραμμικές λίστες

Με τον όρο γραμμική λίστα (linear list) εννοούμε ένα σύνολο από κόμβους x[1], x[2],...,x[n] με την ιδιότητα ότι το στοιχείο x[1] είναι ο πρώτος κόμβος και ο κόμβος x[k] προηγείται του κόμβου x[k+1] και έπεται του κόμβου x[k-1], 1<k<n.

Οι πίνακες που εξετάσαμε είναι μια μορφή γραμμικής λίστας. Η πιο συνηθισμένη μορφή γραμμικής λίστας είναι η διατεταγμένη γραμμική λίστα(ordered list). Ενδιαφέρον παρουσιάζουν οι λίστες όπου οι εισαγωγές, οι διαγραφές και οι προσπελάσεις στους κόμβους γίνονται πάντοτε είτε στον πρώτο, είτε στον τελευταίο κόμβο. Σ' αυτές τις κατηγορίες συμπεριλαμβάνονται οι στοίβες (stacks), ουρές(queues) και οι ουρές με δύο άκρα(dequeues).

Οι γραμμικές λίστες κατατάσσονται συνήθως σε δύο κατηγορίες: Τις σειριακές γραμμικές λίστες (sequential linear lists) και τις συνδεδεμένες γραμμικές λίστες (linked linear lists). Η κύρια διαφορά αυτών των δύο κατηγοριών είναι ότι στην πρώτη χρησιμοποιούνται συνεχόμενες θέσεις μνήμης στην αποθήκευση των κόμβων, ενώ στη δεύτερη οι κόμβοι των λιστών βρίσκονται σε απομακρυσμένες θέσεις στη μνήμη που όμως είναι μεταξύ τους συνδεδεμένες.

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

Στοίβα

Στη στίβα τα δεδομένα που βρίσκονται στην κορυφή τα επεξεργαζόμαστε πρώτα και τα δεδομένα που βρίσκονται στο βάθος τα επεξεργαζόμαστε τελευταία. Η μέθοδος αυτή ονομάζεται LIFO(Last-In-First-Out). Υπάρχει ένας δείκτης δείκτης top που δείχνει πάντοτε το στοιχείο που τοποθετήθηκε τελευταίο στη στίβα.

Δύο είναι οι κύριες λειτουργίες που μπορούν να γίνουν σε μια στίβα. (1) η ώθηση(push) ενός στοιχείου στην κορυφή της στίβας και (2) η εξαγωγή(pop) ενός στοιχείου από τη στίβα.

Η διαδικασία της ώθησης πρέπει ωποσδήποτε να ελέγχει αν η στίβα είναι ήδη γεμάτη, οπότε λέμε ότι έχουμε υπερχείλιση(overflow) της στίβας. Αντίστοιχα η διαδικασία της εξαγωγής ελέγχει αν υπάρχει ένα τουλάχιτον στοιχείο για εξαγωγή, δηλαδή αν γίνεται υποεκχείλιση(underflow) της στίβας.

Ουρά

Σε μια ουρά αναμονής εξυπηρετείται εκείνος που στάθηκε στην ουρά πρώτος από όλους τους άλλους. Η μέθοδος αυτή ονομάζεται FIFO(First-In-First-Out). Στη δομή δεδομένων με ουρά επιτρέπεται όλες οι εισαγωγές στοιχείων να γίνονται από το ένα άκρο, και όλες οι διαγραφές, από το άλλο. Κατά συνέπεια χρειαζόμαστε δύο δείκτες τον μπρος(front) και τον πίσω(rear).

Συνδεδεμένες γραμμικές λίστες

Κάποια χαρακτηριστικά των συνδεδεμένων λιστών είναι ότι οι κόμβοι βρίσκονται σε απομακρυσμένες θέσεις μνήμης και η σύνδεση μεταξύ τους γίνεται με δείκτες(pointers ή links). Αυτό διευκολύνει την εισαγωγή(διαγραφή) νέων(παλιών) κόμβων.

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

Άλλες λειτουργίες στις συνδεδεμένες λίστες είναι η συνένωση(concatenation) δύο λιστών σε μία και η αντιστροφή(inversion) μιας λίστας.

Δέντρα

Η έννοια του δέντρου είναι στενά συνδεδεμένη με την έννοια της ιεραρχίας. Είναι μια μη γραμμική δομή.

Ένα δέντρο Τ είναι ένα πεπερασμένο σύνολο από έναν ή περισσότερους κόμβους σε τρόπο ώστε να υπάρχει ένας ειδικός κόμβος t που ονομάζεται ρίζα(root) του δέντρου. Οι υπόλοιποι κόμβοι μπορούν να διαμεριστούν σε ξένα μεταξύ τους σύνολα Τ1,Τ2,...Τn όπου κάθε υποσύνολο είναι με τη σειρά του ένα δέντρο. Τα δέντρα αυτά ονομάζονται υποδέντρα (subtrees) του αρχικού δέντρου.

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

Οι κόμβοι ενός δέντρου από τους οποίους δεν αρχίζει κάποιο υποδέντρο ονομάζονται φύλλα (leaves). Όλοι οι άλλοι κόμβοι ονομάζονται μη-τερματικοί ή κλαδιά(branches).

Όταν αναφερόμαστε σε μια δομή δέντρου πολύ συχνά χρησιμοποιούμε τους ακόλουθους όρους: ο κόμβος a είναι ο πατέρας των κόμβων b και c, ενώ τα b και c λέγονται παιδιά του a. Ένα διατεταγμένο δέντρο είναι αυτό που έχει σημασία η διάταξη των κλαδιών του. Μια ενδιαφέρουσα μορφή ενός διατεταγμένου δυαδικού δέντρου είναι το δένδρο αναζήτησης (search tree).

Ένας κόμβος y που είναι αμέσως από κάτω από έναν κόμβο x, ονομάζεται απόγονος του x. Αν ο x βρίσκεται στο επίπεδο i, τότε ο y βρίσκεται στο επίπεδο i+1. Ο x λέγεται πρόγονος του y. Το μέγιστο επίπεδο κάθε κόμβου λέγεται βάθος(depth) του δέντρου.

Δυαδικά δένδρα

Ένα δυαδικό δέντρο αποτελείται από ένα πεπερασμένο σύνολο κόμβων. Το δέντρο είναι είτε άδειο, είτε αποτελείται από δύο άλλα δυαδικά δέντρα που ονομάζονται το αριστερό και το δεξιό υποδέντρο.

Για να ανιχνεύσουμε όλους τους κόμβους ενός δέντρου πρέπει να το διασχίσουμε(traverse). Η διάσχιση απαιτεί την επίσκεψη κάθε κόμβου αλλά μόνο μια φορά.

Υπάρχουν διάφοροι τρόποι διάσχισης: η προδιατεταγμένη(preorder), η μεταδιατεταγμένη (postorder) και η ενδοδιατεταγμένη(inorder).

Γράφοι

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

Ένας γράφος, G, χαρακτηρίζεται από δύο σύνολα V και E. Το σύνολο V είναι ένα πεπερασμένο διάφορο του κενού σύνολο και περιέχει σαν στοιχεία τις κορυφές(vertices) του γράφου. Το σύνολο E έχει σαν στοιχεία τα ζευγάρια των κορυφών του γράφου που ορίζουν τις ακμές(edges). Τα σύμβολα V(G) και G(V,E) χρησιμοποιούνται αντίστοιχα για την αναπαράσταση των συνόλων V,E και του γράφου G.

Ένας γράφος ονομάζεται μη διευθυνόμενος(undirected) αν τα ζευγάρια των κορυφών του που ορίζουν τις ακμές του στερούνται διάταξης. Για παράδειγμα, οι συμβολισμοί (v1,v2) και (v2,v1) αναφέρονται στην ίδια ακμή. Στους διευθυνόμενους γράφους (directed graphs) κάθε ακμή συμβολίζεται με το διευθυνόμενο ζευγάρι <v1,v2>, όπου v1 είναι η ουρά(tail) και v2 είναι η κεφαλή(head) της ακμής. Κατά συνέπεια οι ακμές <v1,v2> και <v2,v1> είναι δύο διαφορετικές ακμές.

ΠΡΟΤΑΣΗ: Για κάθε μη διευθυνόμενο γράφο με n κορυφές, ο μεγαλύτερος αριθμός ακμών που μπορεί να έχει είναι Emax = n(n-1). Ένας διευθυνόμενος(μη διευθυνόμενος) γράφος με n κορυφές λέγεται πλήρης(complete) αν έχει ακριβώς n(n-1) ή n(n-1)/2(για μη διυθυνόμενο) ακμές.

Αν (v1,v2) είναι μια ακμή στο E(G) τότε οι κορυφές v1 και v2 λέγονται διπλανές(adjacent) και η ακμή (v1,v2) ονομάζεται στιγμιότυπο(incident) των κορυφών v1 και v2. Αν <v1,v2> είναι μια διευθυνόμενη ακμή, τότε η κορυφή v1 λέγεται διπλανή στη(adjacent to) v2 και η v2 διπλανή από τη (adjacent from) v1.

Ένας γράφος G' για τον οποίο ισχύει ότι V(G') υποσύνολο του V(G) ή E(G') υποσύνολο του E(G) ονομάζεται υπογράφος(subgraph) του γράφου G. Σαν ένα μονοπάτι(path) από την κορυφή vp στην κορυφή vq του γράφου G, ορίζεται η ακολουθία των κορυφών vp,vi1,...,vin,vq, που έχουν την ιδιότητα ότι τα (vp,vi1),(vi1,vi2),...,(vin,vq) είναι ακμές στο E(G). Το μήκος ενός μονοπατιού, ορίζεται σαν τον αριθμό των ακμών που υπάρχουν στο μονοπάτι. Απλό μονοπάτι(simple path) λέγεται το μονοπάτι εκείνο στο οποίο όλες οι κορυφές εκτός ενδεχόμενα από την πρώτη και την τελευταία είναι διακεκριμένες. Ένας κύκλος(cycle) είναι ένα απλό μονοπάτι, στο οποίο η πρώτη και η τελευταία κορυφή είναι ίδιες. Σε ένα μη διευθυνόμενο γράφο, G, δύο κορυφές v1 και v2 λέγονται συνδεδεμένες(connected), όταν υπάρχει ένα μονοπάτι στον G από την κορυφή v1 στην κορυφή v2. Φυσικά στην περίπτωση αυτή θα υπάρχει και μονοπάτι από την v2 στη v1.

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

Εσωτερική παράσταση γραφών

Υπάρχουν αρκετοί τρόποι απεικόνισης ενός γράφου στην κεντρική μνήμη του Η-Υ. Η αποδοτικότητα κάθε παράστασης εξαρτάται(για άλλη μια φορά) από τις συγκεκριμένες λειτουργίες που θέλουμε να κάνουμε στο γράφο. Οι συνηθισμένες μέθοδοι παράστασης είναι: τα μητρώα διπλανών κορυφών(adjecency matrices), οι λίστες διπλανών κορυφών(adjacency lists) και οι πολλαπλές λίστες διπλανών κορυφών(adjacency multilists).

Μέθοδοι διάσχισης

Δοθέντος ενός μη διευθυνόμενου γράφου G=(V,E) και μιας κορυφής v στο V(G), μας ενδιαφέρει η επίσκεψη όλων των κορυφών του G στις οποίες μπορούμε να φτάσουμε ξεκινώντας από το v. Δύο είναι οι πιο συνηθισμένες μέθοδοι: Αναζήτηση βάθους πρώτα(depth first search) και Αναζήτηση πλάτους πρώτα(breath first search).

Το μικρότερο μονοπάτι

Μια από τις εφαρμογές των γράφων είναι η παράσταση ενός οδικού δικτύου, όπου οι κορυφές αντιστοιχούν με πόλεις και οι ακμές παριστάνουν τμήματα του δικτύου. Σε κάθε ακμή αντιστοιχεί μια βαρύτητα(weight) που μπορεί να είναι είτε η χιλιομετρική απόσταση μεταξύ 2 πόλεων της ακμής, είτε ο χρόνος για να μεταβούμε από τη μια πόλη στην άλλη. Σε μια τέτοια απεικόνιση μας ενδιαφέρει η απάντηση στα ακόλουθα ερωτήματα: "Υπάρχει μονοπάτι μεταξύ των πόλεων Α και Β; Αν υπάρχουν πολλά τέτοια μονοπάτια, τότε ποιο από αυτά είναι το μικρότερο;" Με την απάντηση των ερωτημάτων αυτών ασχολούνται τα προβλήματα μονοπατιών (path problems).