Κεφάλαιο 6

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


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

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


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


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


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


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

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


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


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


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


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


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


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


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

  2. Παράδειγμα
• Δομές δεδομένων σε δευτερεύουσα μνήμη


  • Τα στοιχεία ενός αρχείου ονομάζονται εγγραφές (records), όπου κάθε εγγραφή αποτελείται από ένα ή περισσότερα πεδία (fields)
  • Ένα σύνολο από αρχεία αποτελούν μια βάση δεδομένων
• Πρωτεύον κλειδί (primary key)

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

  Άλλο πεδίο που ταυτοποιεί την εγγραφή, εκτός από το πρωτεύον κλειδί
• Δευτερεύουσα μνήμη (δίσκους κλπ)

  • Αποθηκεύονται μεγάλοι όγκοι δεδομένων που δεν χωρούν στην κύρια μνήμη
  • Τα δεδομένα δεν χάνονται αν διακοπεί η ηλεκτρική παροχή και διατηρούνται ακόμη και μετά τον τερματισμό ενός προγράμματος
• Κύρια μνήμη (πίνακες)


  Τα δεδομένα χάνονται όταν τελειώσει το πρόγραμμα
• Μειονεκτήματα πινάκων


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

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

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