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

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

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

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

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

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

Περιεχόμενα

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