Εργαστήριο 5 - Δέντρα

Προθεσμία τελικής παράδοσης: Τετάρτη 20/5, 23:59.

Καλώς ήρθατε, έστω και virtually, στο πέμπτο εργαστήριο του μαθήματος Δομές Δεδομένων και Τεχνικές Προγραμματισμού. Για οποιαδήποτε απορία προκύψει κατά την διάρκεια του εργαστηρίου στείλτε στο piazza ή/και κανονίστε προσωπικό skype call. Καλή αρχή!

Όπως και στο εργαστήριο 4, όλες οι συναρτήσεις υλοποιούνται με 5-10 γραμμές κώδικα, δε χρειάζονται κατεβατά.

1. Κατεβάστε τον κώδικα του εργαστηρίου

Όπως σε όλα τα εργαστήρια, ο κώδικας δίνεται μέσω Git. Για να τον κατεβάσετε:

  1. Επισκεφτείτε τον παρακάτω σύνδεσμο: https://classroom.github.com/a/7iz2QR6f
    • Δεν θα σας ζητηθεί ξανά αντιστοίχηση account (εφόσον το έχετε ήδη κάνει)
    • Αναλυτικές οδηγίες, αν χρειάζεστε, υπάρχουν στο Εργαστήριο 1.
  2. Αφού ολοκληρώσετε το προηγούμενο βήμα, κατεβάστε με git clone το προσωπικό σας repository (όπου <username> το username σας στο github):
    git clone https://github.com/chatziko-k08/2020-lab-5-<username> 
    

2. Γενική συνάρτηση set_visit

Ο ADT Set που είδαμε στο μάθημα επιτρέπει τη διατεταγμένη διάσχιση του Set μέσω των set_first/set_next. Ένας εναλλακτικός τρόπος είναι να παρέχουμε μια συνάρτηση set_visit η οποία να παίρνει ως όρισμα ένα δείκτη σε συνάρτηση visit και την καλεί για κάθε στοιχείο σε διατεταγμένη σειρά.

// Καλεί τη visit(value) για κάθε στοιχείο του set σε διατεταγμένη σειρά
void set_visit(Set set, VisitFunc visit);

Ο ορισμός της συνάρτησης υπάρχει στο include/ADTSet.h στον κώδικα του εργαστηρίου. Επίσης, ο κώδικας του εργαστηρίου περιέχει 3 υλοποιήσεις του ADT Set, μέσω BST, AVL και BTree αντίστοιχα, στο modules/UsingXXXX/ADTSet.c (ο κώδικας είναι ακριβώς ο ίδιος με εκείνον του lecture-code). Οι 3 υλοποιήσεις περιέχουν μια κενή συνάρτηση set_visit στο τέλος του αρχείου.

Αρχικά υλοποιήστε τη συνάρτηση set_visit, χρησιμοποιώντας τις ήδη υπάρχουσες set_first/set_next. Εφόσον η υλοποίηση χρησιμοποιεί μόνο το interface του module, η ίδια συνάρτηση θα πρέπει να δουλεύει και για τις 3 υλοποιήσεις.

Δοκιμάστε τη συνάρτησή σας και στις 3 υλοποιήσεις χρησιμοποιώντας το υπάρχον tests/ADTSet_test.c, το οποίο περιέχει test και για τη set_visit. Υπάρχει επίσης Makefile που κάνει compile το test για όλες τις υλοποιήσεις, πχ make UsingBinarySearchTree_ADTSet_test.

Στο README.md εξηγήστε συνοπτικά την πολυπλοκότητα της συνάρτησής σας για κάθε μία από τις 3 υλοποιήσεις (η πολυπλοκότητα εξαρτάται από αυτή των set_first,set_next).

3. Αποδοτική υλοποίηση της set_visit

Για κάθε μία από τις 3 υλοποιήσεις του ADT Set (BST, AVL, BTree), τροποποιήστε τη set_visit ώστε να είναι πιο αποδοτική, χρησιμοποιώντας απ’ ευθείας την αντίστοιχη δομή (σκεφτείτε τους αντίστοιχους αναδρομικούς αλγορίθμους, είναι απλοί).

Στο README.md, εξηγήστε συνοπτικά την πολυπλοκότητα της κάθε υλοποίησης.

Προαιρετικά: μετρήστε το χρόνο που κάνει να εκτελεστεί η set_visit μετά από εισαγωγή 50.000 ακεραίων σε διατεταγμένη σειρά, για κάθε υλοποίηση. Μετρήστε μόνο το χρόνο της set_visit, όχι το χρόνο της εισαγωγής. Μπορείτε να χρησιμοποιήσετε τη συνάρτηση clock για το σκοπό αυτό. Περιγράψτε συνοπτικά τα αποτελέσματά σας στο README.md.

Παράδοση

Όλα τα αρχεία που φτιάξατε πρέπει να τα κάνετε commit και push στο github.