Εργαστήριο 3 - Εισαγωγή στην υλοποίηση ΑΤΔ

Last updated on Apr 16, 2024

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

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

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

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

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

Ο κώδικας του εργαστηρίου, περιέχει (μεταξύ άλλων):

  • modules/UsingLinkedList/ADTList.c Υλοποίηση του ADT List μέσω συνδεδεμένης λίστας.
  • tests/ADTList_test.c Unit test για τον ADT List. Τρέχοντας make στο tests directory παράγεται το εκτελέσιμο UsingLinkedList_ADTList_test το οποίο εκτελεί τα unit tests χρησιμοποιώντας την παραπάνω υλοποίηση. Τα make run και make valgrind δουλεύουν ως συνήθως.

Αρχικά εξοικειωθείτε με τα παραπάνω αρχεία, και εκτελέστε το test. Διαβάστε και κατανοήστε τη λειτουργία του κώδικα. (Ο κώδικας είναι ακριβώς ο ίδιος με εκείνον του lecture-code).

Dummy κόμβος: παρατηρήστε ότι η υλοποίηση χρησιμοποιεί dummy κόμβο, όπως αναφέρθηκε στη διάλεξη. Η κενή λίστα δηλαδή αναπαριστάται από μια συδεδεμένη λίστα με έναν βοηθητικό (dummy) κόμβο.

Όλες οι παρακάτω ασκήσεις: σας ζητάνε να προσθέσετε επιπλέον λειτουργίες στον ADT List. Για όλες τις λειτουργίες που σας ζητούνται:

  • η δήλωση της αντίστοιχης συνάρτησης υπάρχει έτοιμη στο ADTList.h
  • ένας κενός ορισμός της συνάρτησης υπάρχει στο ADTList.c
  • test της λειτουργίας υπάρχει έτοιμο στο ADTList_test.c. Τα tests αυτά προφανώς θα αποτυγχάνουν μέχρι να υλοποιήσετε τις συναρτήσεις αυτές. Η υλοποίησή σας θα πρέπει να τα περνάει (και χωρίς leaks).
  • Στο README.md θα πρέπει σε 2-3 γραμμές θα εξηγήσετε τι πολυπλοκότητα έχει η υλοποίησή σας.

Καθεμία από τις 3 ασκήσεις λύνεται με max 7 γραμμές κώδικα. Κατανόηση χρειάζεται κυρίως, όχι κατεβατά.

2. list_get_at

Υλοποιήστε μια συνάρτηση list_get_at, παρόμοια με αυτή του ADT Vector. Περιγραφή υπάρχει στο ADTList.h (δείτε και τις παραπάνω οδηγίες!). Η υλοποίηση δε χρειάζεται να είναι αποδοτική.

3. list_remove

Υλοποιήστε μια συνάρτηση list_remove(list, node) που διαγράφει τον κόμβο που δίνεται (και όχι τον επόμενό του). Περιγραφή υπάρχει στο ADTList.h (δείτε και τις παραπάνω οδηγίες!). Η υλοποίηση δε χρειάζεται να είναι αποδοτική.

4. list_append

Υλοποιήστε μια συνάρτηση list_append(list, to_append) η οποία προσθέτει όλα τα στοιχεία της λίστας to_append στο τέλος της λίστας list. Η λίστα to_append καταστρέφεται και δεν μπορεί πλέον να χρησιμοποιηθεί (αλλά τα στοιχεία της δεν καταστρέφονται αφού ανήκουν πλέον στη list). Η υλοποίηση πρέπει να είναι αποδοτική. Προσοχή στην περίπτωση που η to_append είναι κενή!

Παράδοση

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