Εργαστήριο 5 - Δέντρα
Προθεσμία τελικής παράδοσης: Κυριακή 9/6, 23:59.
Καλώς ήρθατε στο πέμπτο εργαστήριο του μαθήματος Δομές Δεδομένων και Τεχνικές Προγραμματισμού. Για οποιαδήποτε απορία προκύψει κατά την διάρκεια του εργαστηρίου ρωτήστε τους βοηθούς, τον υπεύθυνο εργαστηρίου ή/και στείλτε στο piazza. Καλή αρχή!
Όπως και στο εργαστήριο 4, όλες οι συναρτήσεις υλοποιούνται με 5-10 γραμμές κώδικα, δε χρειάζονται κατεβατά.
1. Κατεβάστε τον κώδικα του εργαστηρίου
Όπως σε όλα τα εργαστήρια, ο κώδικας δίνεται μέσω Git. Για να τον κατεβάσετε:
- Επισκεφτείτε τον παρακάτω σύνδεσμο: https://classroom.github.com/a/8mzmhDlW
- Δεν θα σας ζητηθεί ξανά αντιστοίχιση account (εφόσον το έχετε ήδη κάνει)
- Αναλυτικές οδηγίες, αν χρειάζεστε, υπάρχουν στο Εισαγωγικό Εργαστήριο.
- Αφού ολοκληρώσετε το προηγούμενο βήμα, κατεβάστε με
git clone
το προσωπικό σας repository (όπου<username>
το username σας στο github):git clone https://github.com/chatziko-k08/2024-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.