# Liste 3

# Eliminazione di Tutta la Lista
Scrivere una funzione che elimina tutta la lista (sia in modo iterativo che ricorsivo).

==:warning: fare attenzione al valore che assume il puntatore `head` nel main! Come si può fare per farlo modificare in automatico nelle funzioni sottostanti?==

## Iterativo

void eliminaListaIterativa(pNode head) {
    pNode curr;

    while (head != NULL) {
        curr = head;        // Salva il nodo corrente
        head = head->next;  // Passa al nodo successivo
        free(curr);         // Libera la memoria del nodo corrente
    }

    printf("Lista eliminata (iterativa).\n");
}

## Ricorsivo

void eliminaListaRicorsiva(pNode head) {
    // Caso base: lista vuota
    if (head == NULL) {
        printf("Lista eliminata (ricorsiva).\n");
        return;
    }

    // Passo ricorsivo: libera il resto della lista
    eliminaListaRicorsiva(head->next);

    // Libera il nodo corrente
    free(head);
}

---

# Eliminazione di un Elemento in Posizione $i$
Scrivere una funzione che elimina un singolo elemento nella lista in poisizione $i$ (sia in modo iterativo che ricorsivo).

## Iterativo

pNode eliminaPosIterativo(pNode head, int pos) {
    // Caso base: posizione non valida
    if (pos < 0) {
        printf("Posizione non valida\n");
        return head;
    }

    // Caso: lista vuota
    if (head == NULL) {
        printf("Lista vuota\n");
        return head;
    }

    // Caso: eliminazione del primo nodo
    if (pos == 0) {
        pNode tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }

    // Altri casi: scorro la lista per trovare il nodo precedente a quello da eliminare
    pNode curr = head, prev = NULL;
    int index = 0;

    while (curr != NULL && index < pos) {
        prev = curr;
        curr = curr->next;
        index++;
    }

    // Se la posizione è fuori dai limiti
    if (curr == NULL) {
        printf("Posizione %d fuori dai limiti\n", pos);
        return head;
    }

    // Elimino il nodo
    prev->next = curr->next;
    free(curr);

    return head;
}

## Ricorsivo

pNode eliminaPosRicorsivo(pNode head, int pos) {
    // Caso base: posizione non valida o lista vuota
    if (pos < 0) {
        printf("Posizione non valida\n");
        return head;
    }
    if (head == NULL) {
        printf("Lista vuota\n");
        return head;
    }

    // Caso: eliminazione del primo nodo
    if (pos == 0) {
        pNode tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }

    // Passo ricorsivo: procedo alla posizione successiva
    head->next = eliminaPosRicorsivo(head->next, pos - 1);
    return head;
}

---

# Eliminazione di Tutti gli Elementi Minori di un Valore Dato
Scrivere una funzione che elimina tutti gli elementi nella lista che sono minori di un certo valore dato (sia in modo iterativo che ricorsivo).

## Iterativo

pNode eliminaMinoriIterativo(pNode head, int val) {
    // Elimino tutti i nodi in testa che soddisfano la condizione
    while (head != NULL && head->data < val) {
        pNode tmp = head;
        head = head->next;
        free(tmp);
    }

    // Se la lista è vuota dopo aver eliminato i nodi in testa
    if (head == NULL) return NULL;

    // Scorro il resto della lista
    pNode curr = head, prec = NULL;

    while (curr != NULL) {
        if (curr->data < val) {
            // Elimina il nodo corrente
            pNode tmp = curr;
            prec->next = curr->next;
            curr = curr->next;
            free(tmp);
        } else {
            // Avanza
            prec = curr;
            curr = curr->next;
        }
    }

    return head;
}

## Ricorsivo

pNode eliminaMinoriRicorsivo(pNode head, int val) {
    // Caso base: lista vuota
    if (head == NULL) return NULL;

    // Se il nodo corrente deve essere eliminato
    if (head->data < val) {
        pNode tmp = head;
        head = eliminaMinoriRicorsivo(head->next, val); // Passo ricorsivo
        free(tmp);
        return head;
    }

    // Nodo corrente non soddisfa la condizione, passo al prossimo
    head->next = eliminaMinoriRicorsivo(head->next, val);
    return head;
}

---

# Inserimento Ordinato con Ricorsione
Scrivere una funzione ricorsiva che inserisce un nodo in modo ordinato (anche con ripetizioni).

## Iterativo

pNode inserisciOrdinatoIterativo(pNode head, int new_data) {
    // Alloco il nuovo nodo
    pNode new_node = (pNode)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Errore di allocazione\n");
        return head;
    }
    new_node->data = new_data;
    new_node->next = NULL;

    // Caso: lista vuota o nuovo nodo da inserire in testa
    if (head == NULL || new_data < head->data) {
        new_node->next = head;
        return new_node;
    }

    // Trovo la posizione in cui inserire il nuovo nodo
    pNode curr = head;
    while (curr->next != NULL && curr->next->data < new_data) {
        curr = curr->next;
    }

    // Inserisco il nodo tra curr e curr->next
    new_node->next = curr->next;
    curr->next = new_node;

    return head;
}

## Ricorsivo

pNode inserisciOrdinatoRicorsivo(pNode head, int new_data) {
    // Caso base: lista vuota o inserimento in testa
    if (head == NULL || new_data < head->data) {
        pNode new_node = (pNode)malloc(sizeof(Node));
        if (new_node == NULL) {
            printf("Errore di allocazione\n");
            return head;
        }
        new_node->data = new_data;
        new_node->next = head;
        return new_node;
    }

    // Passo ricorsivo: scorro la lista
    head->next = inserisciOrdinatoRicorsivo(head->next, new_data);
    return head;
}

---

# Eliminazione dei Primi $N$ Elementi
Scrivere una funzione che elimini i primi $N$ elementi di una lista (in modo iterativo e ricorsivo).

## Iterativo

pNode eliminaPrimiElementiIterativo(pNode head, int n) {
    // Lista vuota o n non valido
    if (head == NULL || n <= 0) return head;

    // Scorro ed elimino i primi `n` elementi
    pNode curr;
    while (head != NULL && n > 0) {
        // Salvo il nodo corrente (head)
        curr = head;

        // Avanzo nella lista
        head = head->next;

        // Libero il nodo corrente
        free(curr);

        // Decremento il contatore
        n--;
    }

    // Restituisco la nuova testa della lista
    return head;
}

## Ricorsivo

pNode eliminaPrimiElementiRicorsivo(pNode head, int n) {
    // Lista vuota o n non valido
    if (head == NULL || n <= 0) return head;

    // Passo ricorsivo: elimino il primo nodo
    pNode new_head = eliminaPrimiElementiRicorsivo(head->next, n - 1);

    // Libero il nodo corrente
    free(head);

    // Restituisco la nuova testa
    return new_head;
}

---

# Eliminazione degli Elementi Duplicati
Scrivere una funzione che elimina gli elementi duplicati da una lista (in modo iterativo e ricorsivo).

## Iterativo

pNode eliminaDuplicatiIterativo(pNode head) {
    // Lista vuota o con un solo elemento
    if (head == NULL || head->next == NULL) return head;

    pNode curr = head;

    // Scorro la lista esterna
    while (curr != NULL) {
        pNode runner = curr; // Runner per scorrere il resto della lista
        while (runner->next != NULL) {
            if (runner->next->data == curr->data) {
                // Nodo duplicato trovato
                pNode tmp = runner->next;
                runner->next = runner->next->next; // Salta il duplicato
                free(tmp); // Libera il nodo duplicato
            } else {
                runner = runner->next; // Avanza
            }
        }
        curr = curr->next; // Avanza nella lista esterna
    }

    return head;
}

## Ricorsivo

pNode eliminaElementiUguali(pNode head, int value) {
    // Caso base: lista vuota
    if (head == NULL) return NULL;

    // Caso: il nodo corrente contiene `value`
    if (head->data == value) {
        pNode tmp = head;          // Salvo il nodo corrente
        head = eliminaElementiUguali(head->next, value); // Elimino il resto dei nodi con `value`
        free(tmp);                 // Libero il nodo corrente
        return head;
    }

    // Caso: il nodo corrente non contiene `value`
    head->next = eliminaElementiUguali(head->next, value);
    return head;
}

pNode eliminaDuplicatiRicorsivo(pNode head) {
    // Caso base: lista vuota o con un solo elemento
    if (head == NULL || head->next == NULL) return head;

    // Elimino ricorsivamente i duplicati del resto della lista
    head->next = eliminaDuplicatiRicorsivo(head->next);

    // Elimino ricorsivamente tutti i nodi uguali al dato di head
    head->next = eliminaElementiUguali(head->next, head->data);

    return head;
}

---

# Costruzione Liste Compresse
Si considerino le seguenti definizioni:

// Lista di interi
typedef struct el {
    int data;
    struct el * next;
} Node;
typedef Node * pNode;

// Lista compressa di interi
typedef struct c_el{
    int data, count;
    struct c_el * next;
} CNode;
typedef CNode * pCNode;

Le liste compresse rappresentano le classiche liste con nodi in cui appare il valore e il numero di volte che appare nella lista originale.
Ad esempio:
2->1->3->2->1->3->3->4 = (2,2)->(1,2)->(3,3)->(4,1)

Scrivere una funzione che prende una lista e costruisce la sua rappresentazione compressa.

==**Bonus:** fare in modo che la lista compressa risultante sia ordinata (per `->data`) senza modificare la lista originale.==

## Soluzione 1

pCNode inserisciCodaCompresso(pCNode head, int new_data, int new_count){
    // Alloco il nuovo nodo
    pCNode new = (pCNode)malloc(sizeof(CNode));
    if(new == NULL){
        printf("Errore di allocazione\n");
        return head;
    }
    new->data = new_data;
    new->count = new_count;
    new->next = NULL;

    // Verifico che la lista sia allcocata, altrimenti il nuovo nodo è il primo
    if(head == NULL) return new;

    // Scorro la lista fino alla fine
    pCNode curr = head;
    while(curr->next != NULL) curr = curr->next;
    
    // curr è l'ultimo elemento, quindi attacco new
    curr->next = new;

    return head;
}

int contaOccorrenze(pNode head, int value){
    int count = 0;
    pNode curr = head;
    while(curr != NULL){
        if(curr->data == value) count++;
        curr = curr->next;
    }
    return count;
}

int cercaElemento(pCNode head, int value){
    int found = 0;
    pCNode curr = head;
    while(curr != NULL && !found){
        if(curr->data == value) found = 1;
        curr = curr->next;
    }
    return found;
}

pCNode comprimiLista(pNode head, pCNode c_head){
    if(head == NULL) return c_head;

    pNode curr = head;
    int tmp_count;

    while(curr != NULL){
        if(!cercaElemento(c_head, curr->data)){
            tmp_count = contaOccorrenze(curr, curr->data);
            c_head = inserisciCodaCompresso(c_head, curr->data, tmp_count);
        }
        curr = curr->next;
    }

    return c_head;
}

## Soluzione 2

pCNode inserisciCodaCompresso(pCNode head, int new_data, int new_count){
    // Alloco il nuovo nodo
    pCNode new = (pCNode)malloc(sizeof(CNode));
    if(new == NULL){
        printf("Errore di allocazione\n");
        return head;
    }
    new->data = new_data;
    new->count = new_count;
    new->next = NULL;

    // Verifico che la lista sia allcocata, altrimenti il nuovo nodo è il primo
    if(head == NULL) return new;

    // Scorro la lista fino alla fine
    pCNode curr = head;
    while(curr->next != NULL) curr = curr->next;
    
    // curr è l'ultimo elemento, quindi attacco new
    curr->next = new;

    return head;
}

pCNode aggiornaListaCompressa(pCNode head, int value){
    // Se la lista compressa è vuota, aggiungo l'elemento
    if(head == NULL) return inserisciCodaCompresso(head, value, 1);

    // Scorro la lista compressa, se trovo l'elemento aggiorno il counter
    pCNode curr = head;
    while(curr != NULL){
        if(curr->data == value){
            curr->count += 1;
            return head;
        }
        curr = curr->next;
    }

    // Se siamo qui, l'elelemento non è presente
    return inserisciCodaCompresso(head, value, 1);
}

pCNode comprimiListaBase(pNode head, pCNode c_head){
    if(head == NULL) return c_head;

    pNode curr = head;

    while(curr != NULL){
        c_head = aggiornaListaCompressa(c_head, curr->data);
        curr = curr->next;
    }

    return c_head;
}

---

# Rete di Ricercatori
Si definisca una struttura dati Ricercatore con i seguenti campi: nome, citazioni, h index, numero di articoli pubblicati e vettore di articoli.
Si definisca una struttura articolo con i campi: titolo, numero di autori e vettore di nome degli autori.
Si usi una lista di tutti i ricercatori.
Si definisca una lista contenente le liste di tutti i coatuori per ogni autore.
Si definisca una funzione per incrementare il numero di citazioni di un articolo dato solo il titolo, la funzione deve incrementare il numero di citazioni di ogni autore dell'articolo e, nel caso, si aggiorni anche l'h index.

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

// TODO