Εργασία 3

Last updated on May 29, 2026

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Μην ξεχάσετε να συμπληρώσετε το αρχείο AUTHORS. Αν δεν το συμπληρώσετε, ή αν η εργασία σας δεν κάνει compile στοv αυτόματο έλεγχο που γίνεται σε κάθε push, θα πάρετε email λάθους και θα εμφανιστεί ένα ❌ στο GitHub. Μπορείτε να δείτε ακριβώς τι λάθος συνέβη στην καρτέλα “Actions” στο GitHub.

Γενικά

Στην εργασία αυτή καλείστε να δημιουργήσετε διαφορετικές υλοποιήσεις του ADT OrderedMap. Ο αφηρημένος αυτός τύπος δεδομένων παρέχει όλες τις λειτουργίες του κλασικού Map, με τη διαφορά ότι η διάσχιση σέβεται τη διάταξη των κλειδιών:

// Επιστρέφει τον πρώτο/τελευταίο κόμβο του map (ελάχιστο/μέγιστο κλειδί)
OMapNode omap_first(OMap omap);
OMapNode omap_last(OMap omap);

// Επιστρέφει τον επόμενο/προηγούμενο κόμβο (με μεγαλύτερο/μικρότερο κλειδί)
OMapNode omap_next    (OMap omap, OMapNode node);
OMapNode omap_previous(OMap omap, OMapNode node);

Το interface του ADT OrderedMap βρίσκεται στο include/ADTOrderedMap.h και το test στο tests/ADTOrderedMap_test.c. Το tests/Makefile είναι ήδη φτιαγμένο ώστε να κάνει compile όλες τις υλοποιήσεις με όλα τα dependencies.

Σημειώσεις:

  • Κάθε άσκηση μπορεί να υλοποιηθεί ανεξάρτητα.
  • Για όλες τις ασκήσεις, συμπληρώστε στο README.md την πολυπλοκότητα κάθε λειτουργίας.

Άσκηση 1 - Υλοποίηση μέσω ADT Set (20%)

Δημιουργήστε μια απλή υλοποίηση του ADT OrderedMap χρησιμοποιώντας ένα ADT Set για να αποθηκεύετε τα ζεύγη (key, value). Στο lecture-code υπάρχει ήδη μια υλοποίηση του ADT Map χρησιμοποιώντας Set. Η υλοποίηση αυτή, παρόλο που ο ADT Map δεν το απαιτεί, στην πραγματικότητα τηρεί τη διάταξη των στοιχείων, αφού αυτό γίνεται αυτόματα από το Set, δηλαδεί στην πραγματικότητα παρέχει ένα OrderedMap.

Στο αρχείο modules/UsingADTSet/ADTOrderedMap.c υπάρχει η δομή της υλοποίησης. Το μόνο που έχετε να κάνετε είναι τα αντιγράψετε την υλοποίηση του Map μέσω Set από το lecture-code, και να τροποποιήσετε ελάχιστα τον κώδικα ώστε να ακολουθεί το interface του OrderedMap.

Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 2 - Υλοποίηση μέσω ADT Map (20%)

Δημιουργήστε μια υλοποίηση του ADT OrderedMap χρησιμοποιώντας ένα απλό ADT Map για την αποθήκευση. Οι βασικές λειτουργίες (find, insert, remove) γίνονται απλά καλώντας τις αντίστοιχες λειτουργίες του Map.

Η διατεταγμένη διάσχιση, από την άλλη, θέλει διαφορετική αντιμετώπιση: για να υλοποιήσετε την omap_first δεν μπορείτε απλά να καλέσετε την map_first, διότι το πρώτο στοιχείο του Map δεν υπάρχει καμία εγγύηση ότι θα είναι και το ελάχιστο στη διάταξη. Η μόνη γενική λύση (αν θεν θέλουμε να προσθέσουμε κάποια επιπλέον δομή) είναι να διασχίσουμε ολόκληρο το Map, για να βρούμε το ελάχιστο, και το ίδιο για τα next, previous και last.

Για την υλοποίηση αυτή δεν χρειάζεστε ξεχωριστό struct omap_node, είναι πολύ πιο απλό να κάνετε cast το MapNode σε OMapNode.

Στο αρχείο modules/UsingADTMap/ADTOrderedMap.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 3 - Υλοποίηση μέσω sorted ADT List (20%)

Δημιουργήστε μια υλοποίηση του ADT OrderedMap χρησιμοποιώντας ένα ADT List με τα στοιχεία διατηρημένα πάντα ταξινομημένα κατά κλειδί. Στην υλοποίηση αυτή η διατεταγμένη διάσχιση είναι εύκολη, αλλά οι υπόλοιπες λειτουργίες προβληματικές.

Ο ADT List στο repository της εργασίας, σε αντίθεση με το lecture-code, παρέχει μια επιπλέον λειτουργία list_previous που θα σας χρησιμεύσει στο OrderedMap.

Στο αρχείο modules/UsingADTList/ADTOrderedMap.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 4 - Υλοποίηση μέσω sorted ADT List + ADT Map (20%)

Βελτιώστε την υλοποίηση της Άσκησης 3 προσθέτοντας ένα ADT Map που αντιστοιχίζει κάθε key στον αντίστοιχο κόμβο της λίστας. Η επιπλέον αυτή δομή θα βελτιώσει σημαντικά κάποιες από τις λειτουργίες.

Στο αρχείο modules/UsingADTListAndMap/ADTOrderedMap.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 5 - Υλοποίηση μέσω Skip List (20%)

Υλοποιήστε τον ADT OrderedMap χρησιμοποιώντας ένα Skip List, μια πιθανοτική δομή δεδομένων που επιτυγχάνει $O(\log n)$ αναμενόμενο χρόνο για find, insert και remove, ενώ διατηρεί τα στοιχεία ταξινομημένα.

Τι είναι ένα Skip List: Ένα skip list αποτελείται από πολλαπλά επίπεδα (levels) συνδεδεμένων λιστών. Το επίπεδο 0 περιέχει όλα τα στοιχεία σε ταξινομημένη σειρά. Κάθε ανώτερο επίπεδο περιέχει ένα υποσύνολο των στοιχείων, που λειτουργεί σαν «γρήγορη λωρίδα» για να παρακάμψουμε μεγάλα τμήματα της λίστας.

Κάθε κόμβος έχει ένα τυχαίο ύψος (height): αν ο κόμβος έχει ύψος $k$, συμμετέχει στα επίπεδα $0, 1, \ldots, k-1$. Το ύψος επιλέγεται τυχαία: ξεκινάμε από 1 και αυξάνουμε με πιθανότητα $\frac{1}{2}$ (coin flipping), μέχρι να “πέσει κορώνα” ή να φτάσουμε σε κάποιο μέγιστο MAX_LEVEL.

Αυτό δίνει αναμενόμενο ύψος $O(\log n)$ για κάθε κόμβο.

Δομή κόμβου: Κάθε κόμβος έχει έναν πίνακα forward pointers forward[0..height-1], όπου forward[i] δείχνει στον επόμενο κόμβο στο επίπεδο i. Η δέσμευση μνήμης είναι tight: αν ο κόμβος έχει ύψος h, δεσμεύουμε ακριβώς h θέσεις (χρήση flexible array member ή malloc με επιπλέον χώρο).

Το skip list έχει μια ειδική κεφαλή (header) με MAX_LEVEL forward pointers, που αρχικά δείχνουν όλα σε NULL.

Εισαγωγή: Η εισαγωγή ακολουθεί τον παρακάτω αλγόριθμο (δίνεται ο ψευδοκώδικας):

function insert(list, key):
    height = 1
    while flipCoin() and height < maxLevel:
        height += 1
    new_node = makeNode(key, height)
    insertRec(list.header, list.level, key, new_node, height)

function insertRec(node, level, key, new_node, height):
    while node.forward[level] != NIL and node.forward[level].key < key:
        node = node.forward[level]

    if level > 0:
        insertRec(node, level - 1, key, new_node, height)

    if level < height:
        new_node.forward[level] = node.forward[level]
        node.forward[level] = new_node

Η insertRec καλείται αρχικά με level = list.level - 1 (το τρέχον μέγιστο επίπεδο). Κατεβαίνει αναδρομικά, και μόνο στα επίπεδα $< height$ συνδέει τον νέο κόμβο. Παρατηρήστε ότι η list.level (μέγιστο επίπεδο σε χρήση) ενημερώνεται αν ο νέος κόμβος έχει μεγαλύτερο ύψος.

Αναζήτηση:

function find(list, key):
    node = list.header
    for level = list.level - 1 downto 0:
        while node.forward[level] != NIL and node.forward[level].key < key:
            node = node.forward[level]
    node = node.forward[0]
    if node != NIL and node.key == key:
        return node
    return NIL

Αφαίρεση: Η αφαίρεση μπορεί να γίνει αναδρομικά ανά επίπεδο τροποποιώντας τον αλγόριθμο της εισαγωγής.

Επιπλέον: prev pointer

Για να υποστηρίξετε γρήγορο omap_previous μπορείτε να προσθέσετε έναν prev pointer σε κάθε κόμβο που δείχνει στον προηγούμενο κόμβο στο επίπεδο 0. Ενημερώνεται κατά την εισαγωγή και αφαίρεση.

Στο αρχείο modules/UsingSkipList/ADTOrderedMap.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.