Εργαστήριο 2 - Χρήση ADTs

Last updated on Apr 2, 2024

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

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

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

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

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

Ο κώδικας του εργαστηρίου, περιέχει τη βιβλιοθήκη lib/k08.a που υλοποιεί όλους τους ADTs που έχουμε δει στο μάθημα. Μια βιβλιοθήκη απλά περιέχει precompiled .o αρχεία και χρησιμοποιείται στον gcc ακριβώς όπως ένα .ο αρχείο. Παράδειγμα χρήσης υπάρχει στο programs/list_example/Makefile.

Documentation για κάθε ADT υπάρχει στο αντίστοιχο .h αρχείο, πχ στο include/ADTList.h.

2. Λίστες και δέσμευση μνήμης

Στο directory programs/list_example υπάρχει ένα πρόγραμμα που προσθέτει τους αριθμούς 0-9 σε μια λίστα.

  1. Εξετάστε τον κώδικά του. Τι αποτέλεσμα θα έχει η προσθήκη του &i στη λίστα; Λειτουργεί σωστά;
  2. Τροποποιήστε το πρόγραμμα ώστε να τυπώνει όλα τα στοιχεία της λίστας, ώστε να βεβαιωθείτε ότι οι αριθμοί δεν είναι οι αναμενόμενοι.
  3. Τροποποιήστε τον κώδικα ώστε να προσθέτει σωστά τους αριθμούς 0-9, χρησιμοποιώντας δυναμική δέσμευση μνήμης (malloc), μέσω της συνάρτησης create_int που υπάρχει στο ίδιο αρχείο.
    int* create_int(int value) {
    int* pointer = malloc(sizeof(int)); // δέσμευση μνήμης
    *pointer = value;                   // αντιγραφή του value στον νέο ακέραιο
    return pointer;
}
  4. Τρέξτε το πρόγραμμα μέσω valgrind, και ελέγξτε αν περιέχει memory leaks. Αν ναι διορθώστε τα (περνώντας μια κατάλληλη συνάρτηση destroy_value στη list_create).

3. Ουρές προτεραιότητας και σύνολα

Δημιουργήστε ένα πρόγραμμα pqueue_set_example το οποίο:

  1. Να προσθέτει 20 τυχαίους ακεραίους (χρησιμοποιώντας τη rand) σε μια ουρά προτεραιότητας (ADTPriorityQueue).
  2. Να τυπώνει τον αριθμό στην κορυφή της ουράς, και στη συνέχεια να τον αφαιρεί, μέχρι να αδειάσει.
    • Οι αριθμοί θα πρέπει να εμφανίζονται σε φθίνουσα σειρά.
  3. Να προσθέτει 20 τυχαίους αριθμούς σε ένα σύνολο (ADTSet).
  4. Να διασχίζει τα στοιχεία του συνόλου και να τα τυπώνει.
    • Οι αριθμοί θα πρέπει να εμφανίζονται σε αύξουσα σειρά.

4. Pair Sum

Στο directory programs/pair_sum υπάρχει ένα module pair_sum.h που περιέχει μία συνάρτηση pair_sum. Η συνάρτηση αυτή παίρνει ένα Vector ακεραίων και έναν ακέραιο target και ελέγχει αν υπάρχουν 2 στοιχεία a,b στο Vector τέτοια ώστε a + b == target.

Στο ίδιο directory, υπάρχει ένα test pair_sum_test.c που ελέγχει τη λειτουργία της συνάρτησης αυτής.

  1. Διαβάστε τον κώδικα στα 2 αυτά αρχεία και κατανοήστε τη λειτουργία του.
  2. Υλοποιήστε τη συνάρτηση αυτή στο αρχείο pair_sum.c με τον “προφανή” τρόπο: ελέγχοντας όλα τα ζευγάρια στοιχείων του Vector, ψάχνοντας ένα ζευγάρι που ικανοποιεί τη σχέση a + b == target.
  3. Μεταγλωτίστε και εκτελέστε το test ώστε να βεβαιωθείτε ότι η υλοποίηση λειτουργεί σωστά.
  4. Στο pair_sum_test.c υπάρχει μια παράμετρος N που καθορίζει το μέγεθος του Vector που χρησιμοποιείται στο test. Αυξήστε σταδιακά στο μέγεθος αυτό (πολλαπλασιάζοντας πχ κάθε φορά επί 10) και εξετάστε πώς μεταβάλλεται ο χρόνος εκτέλεσης (μπορείτε να διακόπτετε ένα test που αργεί με Ctrl-C).
  5. (Προαιρετικά) Προσθέστε επιπλέον ελέγχους στο test ώστε να γίνει πιο περιεκτικό.

5. Pair Sum μέσω Map (bonus)

Δημιουργήστε μια νέα υλοποίηση pair_sum_using_map.c του module pair_sum.h της προηγούμενης άσκησης, η οποία να είναι πιο αποδοτική χρησιμοποιώντας ένα Map. Αυτό μπορεί να γίνει ως εξής:

  1. Δημιουργήστε ένα Map και προσθέστε σε αυτό όλα τα στοιχεία του Vector.
    • Τόσο για key όσο και για value βάζετε το ίδιο το στοιχείο. (Η επιλογή του value είναι ουσιαστικά αυθαίρετη, το σημαντικό είναι το key.)
  2. Διατρέχετε κάθε στοιχείο a του Vector, και ελέγχετε αν το στοιχείο b = target - a υπάρχει στο Map (η αναζήτηση αυτή είναι γρήγορη).
    • Αν ναι βρήκατε το ζευγάρι που ψάχνετε, αφού a + b == target.
    • Αν ο έλεγχος αποτύχει για όλα τα στοιχεία τότε δεν υπάρχει τέτοιο ζευγάρι.
  3. Ελέγξτε μέσω του test ότι η νέα υλοποίηση είναι σωστή.
  4. Όπως και στην προηγούμενη άσκηση, αυξήστε το N στο test και ελέγξτε πώς μεταβάλλεται ο χρόνος εκτέλεσης.

Παράδοση

Ολα τα αρχεία που φτιάξατε πρέπει να τα κάνετε commit και push στο github. Αν επιθυμείτε, μπορείτε να συνεχίσετε να τα δουλεύετε και μετά τη λήξη του εργαστηρίου, μέχρι την τελική ημερομηνία παράδοσης.