Κεφάλαιο 5

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


  Ένα σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών
• Βασικές λειτουργίες επί των δομών δεδομένων

  • Προσπέλαση
  • Εισαγωγή
  • Διαγραφή
  • Αναζήτηση
  • Ταξινόμηση
  • Αντιγραφή
  • Συγχώνευση
  • Διαχωρισμός
• Υπάρχει μεγάλη εξάρτηση μεταξύ της δομής δεδομένων και του αλγόριθμου που επεξεργάζεται τη δομή
• Κατηγορίες δομών δεδομένων


  • Στατικές
  • Δυναμικές
• Στατικές δομές δεδομένων


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


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


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

  Ο πρώτος δείκτης (i) δείχνει τη γραμμή και ο δεύτερος (j) τη στήλη
• Αναζήτηση


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


  • Παράδειγμα σειριακής αναζήτησης σε πίνακα
• Σειριακή αναζήτηση


  Η πιο απλή, αλλά και η λιγότερο αποτελεσματική μέθοδος αναζήτησης, χρησιμοποιείται μόνο σε περιπτώσεις όπου ο πίνακας είναι μη ταξινομημένος, μικρού μεγέθους, και η αναζήτηση γίνεται σπάνια
• Ταξινόμηση


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


  • Παράδειγμα ταξινόμησης ευθείας ανταλλαγής
• Δομές δεδομένων σε δευτερεύουσα μνήμη


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


  • Ο πίνακας είναι μη ταξινομημένος
  • Ο πίνακας είναι μικρού μεγέθους (για παράδειγμα, n ≤ 20)
  • Η αναζήτηση σε ένα συγκεκριμένο πίνακα γίνεται σπάνια
• Ταξινόμηση


  Η μετάθεση (permutation) της θέσης των στοιχείων a1,a2,...,an, ώστε να τοποθετηθούν σε μία σειρά ak1,ak2,...,akn έτσι ώστε, δοθείσης μίας συνάρτησης διάταξης (ordering function), f, να ισχύει: f(ak1) ≤ f(ak2) ≤ ... ≤ f(akn)
• Ταξινόμηση ευθείας ανταλλαγής


  1. Περιγραφή της διαδικασίας

  2. Παράδειγμα
• Εγγραφή


  Τα στοιχεία ενός αρχείου
• Πεδίο


  Τα μέρη από τα οποία αποτελείται μια εγγραφή
• Βάση δεδομένων


  Ένα σύνολο από αρχεία
• Πρωτεύον κλειδί


  Το πεδίο που ταυτοποιεί την εγγραφή
• Δευτερεύον κλειδί


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


  • Απαιτούν μνήμη
  • Περιορίζουν τις δυνατότητες του προγράμματος
• Τυπικές επεξεργασίες σε πίνακες:

  • Υπολογισμός αθροισμάτων στοιχείων
  • Εύρεση του μέγιστου ή του ελάχιστου στοιχείου
  • Ταξινόμηση των στοιχείων
  • Αναζήτηση ενός στοιχείου
  • Συγχώνευση δύο πινάκων
• Μέθοδος «Διαίρει και Βασίλευε»

  Μέθοδος σχεδίασης αλγορίθμων που υποδιαιρεί ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά είναι μικρότερα σε μέγεθος
• Ο μέγιστος αριθμός των συγκρίσεων (επαναλήψεων) που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο «n» ταξινομημένων στοιχείων, συμπεριλαμβανομένης και της περίπτωσης μη ύπαρξης του στοιχείου, δίνεται από το ακέραιο μέρος του [log2(n)+1] (με στρογγυλοποίηση προς τα κάτω)