Δομές Δεδομένων και Τεχνικές Προγραμματισμού

Κώστας Χατζηκοκολάκης

Εισαγωγή

Ιστοσελίδα του μαθήματος: https://k08.chatzi.org/

Ολες οι πληροφορίες για βαθμολόγηση, εργαστήρια, εξετάσεις, βιβλιογραφία, συζητήσεις κλπ βρίσκονται εκεί.

Γιατί είμαστε εδώ;

  1. Για να μάθουμε να προγραμματίζουμε. Αλλά γιατί;
  • Γιατί είναι χρήσιμο
  • Γιατί μαθαίνουμε να σκεφτόμαστε αλγοριθμικά
  • Γιατί είναι δημιουργικό!

Programming can be like composing poetry or music; […] it can give us both intellectual and emotional satisfaction, because it is a real achievement to master complexity and to establish a system of consistent rules.

Computer programming is an art, […] especially because it produces objects of beauty. […] A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.

Donald Knuth, CACM, 1974

The three virtues of a great programmer:

  • Laziness: The quality that makes you go to great effort to reduce overall energy expenditure.
  • Impatience: The anger you feel when the computer is being lazy.
  • Hubris: Excessive pride; makes you write programs that other people won't want to say bad things about.

Larry Wall, Programming Perl

Γιατί σε C;

« Κανείς δε γράφει C πλέον, σε όλες τις δουλειές ζητάνε Javascript / Ruby / Python / R / Java / PHP / … »

« Η C είναι δύσκολη στην εκμάθηση »

Γιατί είμαστε εδώ;

  1. Για να μάθουμε οργανώνουμε τα δεδομένα μας, χρησιμοποιώντας:
    • Αφηρημένους Τύπους Δεδομένων
    • Δομές Δεδομένων

Ας δούμε ένα παράδειγμα…

Πώς θα αποθηκεύσουμε τα βιβλία μας…

Πρόβλημα:

Ποιος είναι ο καλύτερος τρόπος να οργανώσουμε τα βιβλία μας;

Πώς θα αποθηκεύσουμε τα βιβλία μας…

Λύση 1 : Χάος

Απλή και εύκολη! (αρκεί να μην μας ενδιαφέρει το διάβασμα)

Πώς θα αποθηκεύσουμε τα βιβλία μας…

Λύση 2 : Array

Πλεονεκτήματα; Προβλήματα;

Πώς θα αποθηκεύσουμε τα βιβλία μας…

Λύση 3 : Sorted array

Πολύ καλύτερα! Τέλεια λύση; Προβλήματα;

Πώς θα αποθηκεύσουμε τα βιβλία μας…

Λύση 4 : B-tree

Πλεονεκτήματα;

Αφηρημένοι Τύποι Δεδομένων

ADTBookStore

  • insert(title)
    Πρόσθεσε το βιβλίο με τίτλο title
  • remove(title)
    Αφαίρεσε το βιβλίο με τίτλο title
  • find(title)
    Ψάξε το βιβλίο με τίτλο title

Ως χρήστες, δανειζόμαστε βιβλία χρησιμοποιώντας αυτή τη διεπαφή.
Δε μας απασχολεί πώς είναι αποθηκευμένα.

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

4 Δομές Δεδομένων υλοποιούν τον ίδιο ADTBookStore

  • Chaos
  • Array
  • SortedArray
  • BTree

Κάθε δομή έχει διαφορετικά πλεονεκτήματα & μειονεκτήματα.

Μπορούμε να αλλάξουμε υλοποίηση χωρίς να επηρρεαστούν οι χρήστες.

Περιεχόμενο του Μαθήματος

  • Εισαγωγή & τεχνικές αποδοτικού προγραμματισμού
    • Modules, Makefiles, Editors, Git
    • Recap: memory allocation, pointers, structs, typedefs, void pointers
    • Code style, Naming convensions, Tests
  • Αφηρημένοι Τύποι Δεδομένων και εφαρμογές
    • Vectors, λίστες, στοίβες, ουρές
    • Ουρές προτεραιότητας, Δέντρα (trees), Maps, Σύνολα
  • Δομές δεδομένων
    • Δυναμικοί Πίνακες, Συνδεδεμένες Λίστες, Δένδρα, Σωροί
    • Δυαδικά δένδρα αναζήτησης, AVL δένδρα, B-δένδρα
    • Κατακερματισμός, Γράφοι