# Liste 4

# Liste di Prefissi (TDE 25.02.2008)

Definiamo prefisso di lunghezza p di una lista la lista ottenuta prendendo i primi p elementi della lista nello stesso ordine della lista originaria.
Ad esempio data la lista -> 5 -> 6 -> 9 -> 2 -> 4 -> 1 il prefisso di lunghezza 3 è -> 5 -> 6 -> 9
Avendo a disposizione il tipo:

// Definizione dei tipi
typedef struct Node {
    int numero;
    struct Node *next;
} Nodo;
typedef Nodo *Lista;

typedef struct NodeList {
    Lista lis;
    struct NodeList *next;
} NodoLista;
typedef NodoLista *ListaDiListe;

Definire una funzione ListaDiListe generaListaPrefissi(Lista lis, int k); che ricevuta in input una lista e un intero k restituisce la lista delle k liste costruite prendendo i k prefissi di lunghezza compresa tra 1 e k.

// Funzione per creare una copia del prefisso di lunghezza specificata
Lista copiaPrefisso(Lista lis, int lunghezza) {
    Lista prefisso = NULL;
    Nodo *curr = lis;

    for (int i = 0; i < lunghezza && curr != NULL; i++) {
        prefisso = aggiungiInCoda(prefisso, curr->numero);
        curr = curr->next;
    }

    return prefisso;
}

// Funzione per generare la lista di prefissi
ListaDiListe generaListaPrefissi(Lista lis, int k) {
    ListaDiListe listaDiListe = NULL;
    NodoLista *ultimo = NULL;

    for (int i = 1; i <= k; i++) {
        Lista prefisso = copiaPrefisso(lis, i);

        NodoLista *nuovoNodo = (NodoLista *)malloc(sizeof(NodoLista));
        if (nuovoNodo == NULL) {
            printf("Errore di allocazione\n");
            liberaListaDiListe(listaDiListe);
            return NULL;
        }

        nuovoNodo->lis = prefisso;
        nuovoNodo->next = NULL;

        if (listaDiListe == NULL) {
            listaDiListe = nuovoNodo;
            ultimo = nuovoNodo;
        } else {
            ultimo->next = nuovoNodo;
            ultimo = nuovoNodo;
        }
    }

    return listaDiListe;
}

// Funzione per aggiungere un elemento in coda a una lista
Lista aggiungiInCoda(Lista lis, int numero) {
    Nodo *nuovoNodo = (Nodo *)malloc(sizeof(Nodo));
    if (nuovoNodo == NULL) {
        printf("Errore di allocazione\n");
        return lis;
    }

    nuovoNodo->numero = numero;
    nuovoNodo->next = NULL;

    if (lis == NULL) {
        return nuovoNodo;
    }

    Nodo *curr = lis;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    curr->next = nuovoNodo;
    return lis;
}

// Funzione per stampare una lista
void stampaLista(Lista lis) {
    Nodo *curr = lis;
    while (curr != NULL) {
        printf("%d -> ", curr->numero);
        curr = curr->next;
    }
    printf("NULL\n");
}

// Funzione per stampare una lista di liste
void stampaListaDiListe(ListaDiListe listaDiListe) {
    NodoLista *curr = listaDiListe;
    int i = 1;
    while (curr != NULL) {
        printf("Prefisso %d: ", i++);
        stampaLista(curr->lis);
        curr = curr->next;
    }
}

// Funzione per liberare la memoria di una lista
void liberaLista(Lista lis) {
    Nodo *curr;
    while (lis != NULL) {
        curr = lis;
        lis = lis->next;
        free(curr);
    }
}

// Funzione per liberare la memoria di una lista di liste
void liberaListaDiListe(ListaDiListe listaDiListe) {
    NodoLista *curr;
    while (listaDiListe != NULL) {
        curr = listaDiListe;
        listaDiListe = listaDiListe->next;
        liberaLista(curr->lis);
        free(curr);
    }
}

---

# Catena di Stringhe CCTSF (Liste di Stringhe) (TDE 19.02.2007)

**Richiesta 1.** Data una lista di stringhe, scrivere una funzione che restituisce 1 se la lista rappresenta una catena di parole CCTSF (i.e., compatibile col telefono senza fili).

Una catena di parole si dice CCTSF se è composta da parole adiacenti simili (ovvero con al più due caratteri diversi).

Si supponga di poter utilizzare una funzione con prototipo **int simili(char * s1, char * s2);** che restituisce 1 se le stringhe s1 e s2 sono simili, zero altrimenti.

typedef struct Elem { 
    char * data;
    struct Elem * next; 
} Nodo;
typedef Nodo * pNode;

**Richiesta 2.** Si consideri poi la definizione di una lista di catene di parole (da ogni NodoTesta inizia una Lista).

typedef struct Elem2 { 
    pNode catena;
    struct Elem2 * next; 
} NodoTesta;
typedef NodoTesta * ListaDiListe;

Si codifichi (preferibilmente in modo ricorsivo: bonus +1) una funzione che riceve una lista di liste così definita e dealloca interamente dalla lista di liste le sequenze di parole che non sono cctsf.
Attenzione: si ipotizzi che nelle catene non ci siano parole allocate staticamente, e si badi a deallocare tutta la memoria dinamica. [3 punti, +1 se in versione ricorsiva]

## Versione Iterativa (1)

// Prototipo
int stringheCCTSF(pNode head);
int simili(char * s1, char * s2);

// Funzione
int stringheCCTSF(pNode head){
	if(head == NULL || head->next == NULL) return 1;
	
	pNode curr = head;
	
	while(curr->next != NULL){
		if(!simili(curr->data, curr->next->data)) return 0;
		curr = curr->next;
	}
	
	return 1;
}

## Versione Ricorsiva (1)

// Prototipo
int stringheCCTSF(pNode head);
int simili(char * s1, char * s2);

// Funzione
int stringheCCTSF(pNode head){
	if(head == NULL || head->next == NULL) return 1;
	
	if(!simili(curr->data, curr->next->data)) return 0;
	
	return stringheCCTSF(head->next);
}

## Versione Ricorsiva (2)

void deallocaCatena(Lista a) {
	if ( a != NULL ) {
		deallocaCatena( a->next );
		free(a->parola); /* Bisogna deallocare anche il vettore dinamico */
		free( a );
	}
}

ListaDiListe sfrondaListaDiListe( ListaDiListe b ) {
	if ( b != NULL ) {
		ListaDiListe tmp = sfrondaListaDiListe( b->next );
		if ( !stringheCCTSF( b->catena ) ) {
			deallocaCatena( b->catena ); 
			free( b ); 
			return tmp;
		}
		else b->next = tmp;
	}
	return b;
}

---

# Rete di Ricercatori
Si definisca una struttura dati Ricercatore con i seguenti campi: nome, citazioni, h index, numero di articoli pubblicati e vettore (dinamico) di articoli.
Si definisca una struttura articolo con i campi: titolo e citazioni (l'appartenenza ad un autore è definita dalla sua comparsa nel vettore di articoli di un autore).
Per quanto segue, si supponga di avere accesso ad una lista di tutti i ricercatori e ad una lista completa di articoli, si supponga che ogni campo sia adeguatamente popolato (si prenda come riferimento il codice delle strutture fornito).
Richieste:
1. Si scriva una funzione che, per ogni autore nella lista di tutti gli autori vada a popolare una lista di liste in cui ogni nodo fa riferimento ad un ricercatore specifico e che contiene una sotto-lista di autori (diversi dal ricercatore stesso) che sono suoi coautori.
2. Si scriva una funzione per incrementare il numero di citazioni di un articolo dato solo il titolo nella lista di tutti gli articoli. La funzione deve incrementare anche il numero di citazioni di ogni autore dell'articolo e, nel caso, si aggiorni anche l'h-index degli autori.

Si supponga di avere accesso a tutte le funzioni per l'eliminazione e l'inserimento delle liste.

==**Nota:** un autore ha un h-index uguale a N se ha almeno N articoli con N citazioni.==

typedef struct ArtStruct{
    char * titolo;
    int citazioni;
} Articolo;

typedef struct RicStruct {
    char * nome;
    int citazioni;
    int h_index;
    int n_articoli;
    Articolo * articoli;
} Ricercatore;

typedef struct NodoArticolo {
    Articolo articolo;
    struct NodoArticolo * next;
} NodoArticolo;
typedef NodoArticolo * ListaArticoli;

typedef struct NodoRicercatore {
    Ricercatore ricercatore;
    struct NodoRicercatore * next;
} NodoRicercatore;
typedef NodoRicercatore * ListaRicercatori;

typedef struct NodoListaRicercatore {
    Ricercatore ricercatore;
    ListaRicercatori coautori;
    struct NodoListaRicercatore * next;
} NodoListaRicercatore;
typedef NodoListaRicercatore * ListaListeRicercatori;

## Popolo Lista

ListaListeRicercatori popolaListaCoautori(ListaRicercatori listaRicercatori) {
    ListaListeRicercatori listaCoautori = NULL;

    // Scorro la lista di ricercatori
    for (NodoRicercatore *currRicercatore = listaRicercatori; currRicercatore != NULL; currRicercatore = currRicercatore->next) {
        // Creo una nuova lista di coautori per il ricercatore corrente
        ListaRicercatori coautori = NULL;

        // Scorro tutti gli articoli del ricercatore
        for (int i = 0; i < currRicercatore->ricercatore.n_articoli; i++) {
            Articolo art = currRicercatore->ricercatore.articoli[i];

            // Cerco altri ricercatori che hanno questo articolo
            for (NodoRicercatore *altroRicercatore = listaRicercatori; altroRicercatore != NULL; altroRicercatore = altroRicercatore->next) {
                if (strcmp(currRicercatore->ricercatore.nome, altroRicercatore->ricercatore.nome) != 0) {
                    // Scorro gli articoli dell'altro ricercatore
                    for (int j = 0; j < altroRicercatore->ricercatore.n_articoli; j++) {
                        if (strcmp(art.titolo, altroRicercatore->ricercatore.articoli[j].titolo) == 0) {
                            // Aggiungo l'altro ricercatore come coautore
                            if (!esisteRicercatore(coautori, altroRicercatore->ricercatore.nome)) {
                                coautori = aggiungiRicercatore(coautori, altroRicercatore->ricercatore);
                            }
                        }
                    }
                }
            }
        }

        // Aggiungo il ricercatore con la sua lista di coautori alla lista di liste
        listaCoautori = aggiungiListaCoautori(listaCoautori, currRicercatore->ricercatore, coautori);
    }

    return listaCoautori;
}

## Aggiorno Citazioni

void incrementaCitazioni(ListaArticoli listaArticoli, ListaRicercatori listaRicercatori, char *titoloArticolo) {
    // Trovo l'articolo nella lista di articoli
    for (NodoArticolo *currArticolo = listaArticoli; currArticolo != NULL; currArticolo = currArticolo->next) {
        if (strcmp(currArticolo->articolo.titolo, titoloArticolo) == 0) {
            // Incremento le citazioni dell'articolo
            currArticolo->articolo.citazioni++;

            // Aggiorno i ricercatori
            for (NodoRicercatore *currRicercatore = listaRicercatori; currRicercatore != NULL; currRicercatore = currRicercatore->next) {
                for (int i = 0; i < currRicercatore->ricercatore.n_articoli; i++) {
                    if (strcmp(currRicercatore->ricercatore.articoli[i].titolo, titoloArticolo) == 0) {
                        // Incremento le citazioni totali dell'autore
                        currRicercatore->ricercatore.citazioni++;

                        // Aggiorno l'h-index
                        currRicercatore->ricercatore.h_index = calcolaHIndex(currRicercatore->ricercatore);
                    }
                }
            }

            return;
        }
    }

    printf("Articolo '%s' non trovato nella lista di articoli.\\n", titoloArticolo);
}

## Funzioni Ausiliarie

ListaRicercatori aggiungiRicercatore(ListaRicercatori lista, Ricercatore ricercatore) {
    NodoRicercatore *nuovoNodo = (NodoRicercatore *)malloc(sizeof(NodoRicercatore));
    nuovoNodo->ricercatore = ricercatore;
    nuovoNodo->next = lista;
    return nuovoNodo;
}

ListaListeRicercatori aggiungiListaCoautori(ListaListeRicercatori lista, Ricercatore ricercatore, ListaRicercatori coautori) {
    NodoListaRicercatore *nuovoNodo = (NodoListaRicercatore *)malloc(sizeof(NodoListaRicercatore));
    nuovoNodo->ricercatore = ricercatore;
    nuovoNodo->coautori = coautori;
    nuovoNodo->next = lista;
    return nuovoNodo;
}

int esisteRicercatore(ListaRicercatori lista, char *nome) {
    for (NodoRicercatore *curr = lista; curr != NULL; curr = curr->next) {
        if (strcmp(curr->ricercatore.nome, nome) == 0) return 1;
    }
    return 0;
}

int calcolaHIndex(Ricercatore ricercatore) {
    int *citazioni = (int *)malloc(ricercatore.n_articoli * sizeof(int));
    for (int i = 0; i < ricercatore.n_articoli; i++) {
        citazioni[i] = ricercatore.articoli[i].citazioni;
    }

    // Ordina l'array in ordine decrescente
    for (int i = 0; i < ricercatore.n_articoli - 1; i++) {
        for (int j = i + 1; j < ricercatore.n_articoli; j++) {
            if (citazioni[i] < citazioni[j]) {
                int temp = citazioni[i];
                citazioni[i] = citazioni[j];
                citazioni[j] = temp;
            }
        }
    }

    // Calcola l'h-index
    int h_index = 0;
    for (int i = 0; i < ricercatore.n_articoli; i++) {
        if (citazioni[i] >= i + 1) h_index = i + 1;
        else break;
    }

    free(citazioni);
    return h_index;
}