Εισαγωγή
Σκοπιές που μελετά η πληροφορική τα δεδομένα:
Δομή Δεδομένων: Σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών:
Κάθε δομή δεδομένων αποτελείται από ένα σύνολο κόμβων. Οι βασικές λειτουργίες επί των δομών δεδομένων είναι οι εξής :
Προσπέλαση : Πρόσβαση σε ένα κόμβο με σκοπό να εξεταστεί ή να τροποποιηθεί το περιεχόμενό του
Εισαγωγή : Προσθήκη νέων κόμβων σε μια υπάρχουσα δομή
Διαγραφή : Το αντίστροφο της εισαγωγής, αφαίρεση ενός κόμβου από τη δομή
Αναζήτηση : Προσπέλαση των κόμβων μιας δομής, προκειμένου να εντοπιστούν ένας ή περισσότεροι που έχουν μια συγκεκριμένη ιδιότητα
Ταξινόμηση : Οι κόμβοι μιας δομής διατάσσονται κατ' αύξουσα ή φθίνουσα σειρά
Αντιγραφή : Όλοι ή κάποιοι κόμβοι μιας δομής αντιγράφονται σε μια άλλη δομή
Συγχώνευση : Δύο ή περισσότερες δομές συνενώνονται σε μια ενιαία δομή
Διαχωρισμός : Αντίστροφη πράξη της συγχώνευσης
Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
Δυναμικές: τα περιεχόμενα δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης αλλά στηρίζονται στην τεχνική της δυναμικής παραχώρησης μνήμης. Δεν έχουν σταθερό μέγεθος αλλά αυτό αυξομειώνεται με την εισαγωγή/διαγραφή στοιχείων
Στατικές: Το ακριβές μέγεθος της απαιτούμενης κύριας μνήμης καθορίζεται κατά τη στιγμή του προγραμματισμού. Τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης. Οι στατικές δομές υλοποιούνται με πίνακες. Οι πίνακες περιέχουν στοιχεία ιδίου τύπου (δηλαδή ακεραίους, πραγματικούς κ.λ.π.). Η αναφορά στους πίνακες πραγματοποιείται με τη χρήση συμβολικού ονόματος (με κανόνες ονοματολογίας όπως αυτές που αναφέρθηκαν για τις μεταβλητές) ακολουθούμενου από την τιμή των θέσεων μνήμης που δεσμεύονται σε αγκύλη. Ένας πίνακας μπορεί να έχει μία, δυο ή περισσότερες διαστάσεις
Αναγκαιότητα χρήσης πινάκων. Γιατί χρησιμοποιούμε πίνακες; Με τις δομές που έχουν εισαχθεί μέχρι τώρα δεν λύνονται όλα τα προβλήματα;
Η απάντηση είναι πως δεν αρκούν. Υπάρχουν περιπτώσεις που απαιτείται η πολλαπλή επεξεργασία των εισαχθέντων δεδομένων. Δεν είναι αποδεκτό όμως να ζητιέται από το χρήστη να εισάγει εκ νέου δεδομένα που έχει ήδη εισάγει. Παράδειγμα: Να διαβαστούν 20 αριθμοί και να εκτυπωθεί το ποσοστό των στοιχείων που είναι μεγαλύτερα του μέσου όρου. Πρέπει να διαβαστούν όλα τα στοιχεία και να υπολογιστεί ο μέσος όρος και στη συνέχεια να προσπελαστούν ξανά ώστε να μετρηθεί το πλήθος των μεγαλύτερων του μέσου όρου και να εκτιμηθεί το ζητούμενο ποσοστό
Μονοδιάστατοι πίνακες
Για την προσπέλαση ενός μονοδιάστατου πίνακα Ν θέσεων απαιτείται η χρήση μιας δομής επανάληψης
Παράδειγμα 1: Να βρείτε το άθροισμα και το μέσο όρο των στοιχείων ενός μονοδιάστατου πίνακα με αριθμό θέσεων Ν
Αλγόριθμος Παράδειγμα_1 |
Σχολιασμός : Μπορούμε να φανταστούμε τον μετρητήI ως έναν συνδετήρα που σε κάθε επανάληψη υποδεικνύει μια θέση από τον πίνακα Α ως την τρέχουσα θέση Δεν θα συναντήσουμε ποτέ στον αλγόριθμο το όνομα του πίνακα Α χωρίς την χρήση αγκύλων [], εκτός από τις εντολές Δεδομένα ή Αποτελέσματα |
Παράδειγμα 2: Να βρεθεί το μέγιστο μεταξύ των στοιχείων μονοδιάστατου πίνακα
Αλγόριθμος Παράδειγμα_2 |
Σχολιασμός: Η μεθοδολογία επίλυσης είναι η εξής: Έστω ότι το πρώτο στοιχείο του πίνακα είναι το μέγιστο Θα σαρώσουμε τον πίνακα ελέγχοντας αν υπάρχει μεγαλύτερο στοιχείο από το υποτιθέμενο μέγιστο. Αν υπάρχει θεωρούμε αυτό ως μέγιστο Αντίστοιχος είναι και ο αλγόριθμος εύρεσης ελαχίστου |
Αν επιθυμούμε εκτός από την εύρεση του μεγίστου να εντοπίσουμε και την θέση του στον πίνακα τότε ο παραπάνω αλγόριθμος δεν μας καλύπτει, θα τροποποιηθεί ως εξής:
Αλγόριθμος Παράδειγμα_2α |
Σχολιασμός: Προστίθεται η μεταβλητή που περιέχει τη θέση του μεγίστου Αρχικά και αφού θεωρούμε ότι το μέγιστο βρίσκεται στην πρώτη θέση, τότε και η ομώνυμη μεταβλητή λαμβάνει την τιμή 1 Στη συνέχεια, αν εντοπιστεί κάποιο στοιχείο μεγαλύτερο από το υποτιθέμενο μέγιστο, κρατείται στη μεταβλητή μέγιστος αλλά ταυτόχρονα και η θέση του Τελικά, η μεταβλητή θέση θα περιέχει τη θέση του μεγίστου στοιχείου στο πίνακα |
Δισδιάστατοι πίνακες
Μπορούμε να ορίσουμε πίνακες δύο ή περισσοτέρων διαστάσεων. Είναι προφανές ότι για την προσπέλαση δισδιάστατων χρειάζονται δυο μετρητές π.χ.i, j που θα χρησιμοποιηθούν σε δυο δομές επανάληψης Για…από…μέχρι. Για το κάθε στοιχείο του πίνακα αναφέρουμε πρώτα τη γραμμή και ύστερα τη στήλη. Ένας δισδιάστατος ΝxΝ πίνακας ονομάζεται τετραγωνικός
Παράδειγμα 3: Να βρεθεί ο μέσος όρος των στοιχείων ενός δισδιάστατου πίνακα 5x5
Αλγόριθμος Παράδειγμα_3 |
Παράδειγμα 4: Να βρεθεί ο μέσος όρος των στοιχείων κάθε γραμμής σε έναν δισδιάστατο πίνακα ΝxΜ, και να τοποθετηθεί σε έναν μονοδιάστατο πίνακα
Αλγόριθμος Παράδειγμα_4 |
Σχολιασμός: Η μεταβλητή άθροισμα πρέπει να μηδενίζεται στην αρχή κάθε κύκλου επανάληψης του εξωτερικού βρόχου ώστε να υπολογίζει το άθροισμα των στοιχείων για κάθε γραμμή. Αν η αρχικοποίηση γίνει εξωτερικά από τους βρόχους θα υπολογίζει το άθροισμα των γραμμών από την πρώτη μέχρι την τρέχουσα τιμή
Στοίβα & Ουρά
Η στοίβα αποτελεί δυναμική δομή δεδομένων και θα μπορούσαμε να την προσομοιώσουμε με μια στοίβα πιάτων: τα εισερχόμενα στοιχεία μπαίνουν από την κορυφή (top) και εξέρχονται επίσης από την κορυφή. Η λειτουργία αυτή ονομάζεται και LIFO (Last In First Out) ή τελευταίο μέσα, πρώτο έξω
Οι δυο κύριες λειτουργίες μιας στοίβας είναι: - ώθηση (push) στην κορυφή της στοίβας - απώθηση (pop) από την στοίβα Πρέπει να λαμβάνεται ειδική μέριμνα κατά τις παραπάνω λειτουργίες: - Κατά την ώθηση δεν πρέπει η στοίβα να είναι γεμάτη. Το φαινόμενο ονομάζεται υπερχείλιση (overflow) - Κατά την απώθηση προσοχή χρειάζεται όταν διαγράφεται το τελευταίο στοιχείο της στοίβας. Η στοίβα υλοποιείται με τη βοήθεια ενός πίνακα και μιας μεταβλητής με το όνομα top |
Ουρά
Η ουρά αποτελεί επίσης δυναμική δομή δεδομένων και θα μπορούσαμε να την προσομοιώσουμε με μια ουρά αναμονής π.χ. στο ταμείο μιας τράπεζας: τα νέα μέλη της ουράς μπαίνουν στο τέλος της ουράς (rear) και εξέρχονται από την κορυφή (top). Η λειτουργία αυτή ονομάζεται και FIFO (First In First Out) ή πρώτο μέσα, πρώτο έξω
Οι δυο κύριες λειτουργίες μιας στοίβας είναι:
- εισαγωγή (enqueue) στο πίσω άκρο της ουράς
- εξαγωγή (dequeue) από το εμπρός άκρο της ουράς
Πρέπει να ελέγχονται κατά την εισαγωγή/εξαγωγή στοιχείων περιπτώσεις υπερχείλισης/υποχείλισης
Η στοίβα υλοποιείται με τη βοήθεια ενός πίνακα και δυο μεταβλητών δεικτών rear και front