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

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

Στόχοι Μαθήματος

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

Προαπαιτούμενες Γνώσεις

Διαδικαστικός Προγραμματισμός, γλώσσα C

Περιεχόμενα

-- Εισαγωγή στις δομές δεδομένων, Αφηρημένος Τύπος Δεδομένων (ΑΤΔ). -- Βασικοί τύποι δεδομένων (ΑΤΔ ακέραιος, πραγματικός, χαρακτήρας, λογικός). -- ΑΤΔ πίνακας, εγγραφή, σύνολο. -- Στοίβα (stack), βασικές πράξεις, υλοποίηση στοίβας με πίνακα, εφαρμογές με τη χρήση στοίβας (μετατροπή ακέραιου από το δεκαδικό στο δυαδικό σύστημα, υπολογισμός αριθμητικών παραστάσεων). -- Ουρά (queue), βασικές πράξεις, υλοποίηση ουράς με πίνακα, εφαρμογές με τη χρήση ουράς. -- Λίστα (list), βασικές πράξεις, υλοποίηση λίστας με σειριακή αποθήκευση. -- Συνδεδεμένη λίστα (linked list), υλοποίηση με χρήση δεικτών, υλοποίηση στοίβας, ουράς ως ΣΛ, εφαρμογές ΣΛ. -- Δένδρα, Δυαδικά δένδρα (binary trees)(ΔΔ), βασικές πράξεις, υλοποίηση ΔΔ με πίνακα, με δείκτες και με αναδρομή, εφαρμογές ΔΔ: κώδικες Huffman. Β-ΔΔ, βασικές πράξεις. -- Κατακερματισμός (hashing), τεχνικές κατακερματισμού: ανοιχτής διεύθυνσης (open probing) και αλυσίδες συνωνύμων (chaining), υλοποίηση της τεχνικής αλυσίδες συνωνύμων με πίνακα. -- B Δέντρα, AVL Δέντρα