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

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

Εισαγωγή

Ιστοσελίδα του μαθήματος: 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 είναι δύσκολη στην εκμάθηση »

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

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

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

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

Πρόβλημα:

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

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

Λύση 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 conventions, Tests
• Αφηρημένοι Τύποι Δεδομένων και εφαρμογές
  • Vectors, λίστες, στοίβες, ουρές
  • Ουρές προτεραιότητας, Maps, Σύνολα
• Δομές δεδομένων
  • Δυναμικοί Πίνακες, Συνδεδεμένες Λίστες, Δένδρα, Σωροί
  • Δυαδικά δένδρα αναζήτησης, AVL δένδρα, B-δένδρα
  • Κατακερματισμός, Γράφοι