Prova Finale di Algoritmi e Strutture Dati - a.a. 2018-2019

Scopo del progetto è quello di implementare in linguaggio C standard un sistema in grado di gestire entità e relazioni .

L'istanza da gestire è fornita in un file di testo ricevuto come standard input, nel quale vengono definite le entità da monitorare e le relazioni tra queste.

Attraverso i seguenti comandi:

• addent
• addrel
• delent
• delrel
• report
• end

vengono istanziate nuove entità o relazioni (addent e addrel) ed eliminate (delent e delrel); il comando report serve per verificare la corretta gestione del caso fornito.

La report scrive su standard output, in ordine alfabetico, tutte le relazioni che sta gestendo il sistema fornendo per ciascuna di queste, l'entità che riceve il maggior numero di quella relazione; in caso più entità ricevessero lo stesso numero di una relazione verrebbero considerate tutte in ordine alfabetico prima del numero di occorrenze.

Implementazione

Le strutture dati utilizzate per gestire il sistema sono di 3 tipi:

• Hash Table
• Lista Doppiamente Concatenata
• Albero Rosso Nero

Appena una entità inizia ad essere monitorata, viene inserito un nodo all'interno di una hash-table il cui indice è determinato con la funzione di hash djb2 che opera sul nome dell'entità stessa.

Appena una relazione inizia ad essere monitorata, attraverso una lista doppiamente concatenata, viene inserito il nodo relativo a questa in modo tale che, in seguito a nuovi inserimenti della stessa relazione, vengano aggiornati solamente i contenuti delle strutture dati presenti all'interno di ciascun nodo.

Ciascun nodo della lista di relazioni contiene:

• Nome
• Massimo occorrenze
• Albero Rosso Nero delle entità riceventi
• Albero Rosso Nero per la report

In questo modo per qualsiasi operazione che coinvolga una entità o relazione si va ad aggiungere (o eliminare) nell'albero delle entità riceventi il nodo relativo alla entità in esame e, in caso, ad aggiornare il contatore e il relativo albero per la report. I nodi dell'albero delle entità riceventi posseggono ciascuno un altro albero che tiene traccia delle entità da cui quella relazione è ricevuta.

I principali algoritmi utilizzati per la gestione delle strutture dati illustrate sono relativi principalmente all'aggiunta e alla eliminazione di nodi in un albero rosso-nero e l'esplorazione di questo attraverso tree trasversal visits.

Casi di Test

L'implementazione è stata testata e debuggata attraverso i Test Pubblici e valutata attraverso i Test Privati da una piattaforma apposita in grado di determinare la memoria occupata e il tempo di esecuzione del programma.

Compilazione ed Esecuzione

Per eseguire il programma compilare il file main.c da linea di comando con i seguenti flag:

gcc -Wmaybe-uninitialized -Wuninitialized -Wall -pedantic -Werror -g3 main.c -o main

Per eseguire il programma utilizzare uno degli input pubblici e verificare l'output ottenuto con il relativo output:

cat input.txt | ./main > output.txt
diff output.txt public_output.txt