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

Last updated on May 24, 2023

Προθεσμία τελικής παράδοσης: Κυριακή 4/6, 23:59.

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

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

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

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

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

Παράδοση

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