# Liste 1

## Nota sulle soluzioni
Alcune sono da completare con le funzioni elencate nei due "Esercizio 00". Al termine della consegna, è indicata una nota che riporta se l'esercizio è completo o meno. N.B.: Nella prossima esercitazione ci saranno altre operazioni base sulle liste di interi, e di stringhe.

## Esercizio 00: Operazioni Base su Liste di Interi
==Qui trovate l'implementazione delle funzioni base su liste di interi. Le soluzioni agli esercizi seguenti fanno riferimento a questo codice. Sarà da completare con l'esercizio 00 della prossima esercitazione.==

// Librerie 
#include <stdio.h>
#include <stdlib.h> // !!!

// Dati
typedef struct NodeStruct {
    int data;
    struct NodeStruct * next;
} Node;
typedef Node * pNode;

// Prototipi
void stampaLista(pNode);
pNode inserisciCoda(pNode, int);
pNode inserisciTesta(pNode, int);
pNode inserisciPos(pNode, int, int);
int listaLen(pNode);
float listaMedia(pNode, int*);
int cercaElemento(pNode, int);
void eliminaLista(pNode);

// Main
int main() {
    pNode head = NULL; // Inizializzazione della lista
    int err;

    printf("Creazione lista con inserimento in testa:\n");
    head = inserisciTesta(head, 10);
    head = inserisciTesta(head, 20);
    head = inserisciTesta(head, 30);
    stampaLista(head);

    printf("\nInserimento in coda:\n");
    head = inserisciCoda(head, 40);
    head = inserisciCoda(head, 50);
    stampaLista(head);

    printf("\nInserimento in posizione:\n");
    head = inserisciPos(head, 25, 2); // Inserisce 25 alla posizione 2
    stampaLista(head);

    printf("\nInserimento ordinato senza duplicati:\n");
    head = inserisciOrdinatoNoRip(head, 35); // Inserisce ordinato
    head = inserisciOrdinatoNoRip(head, 10); // Tentativo duplicato
    stampaLista(head);

    printf("\nCalcolo della lunghezza e media della lista:\n");
    int len = listaLen(head);
    float media = listaMedia(head, &err);
    if (!err) {
        printf("Lunghezza: %d, Media: %.2f\n", len, media);
    } else {
        printf("Errore nel calcolo della media (lista vuota).\n");
    }

    printf("\nRicerca di un elemento nella lista:\n");
    int val = 25;
    if (cercaElemento(head, val)) {
        printf("Elemento %d trovato nella lista.\n", val);
    } else {
        printf("Elemento %d non trovato.\n", val);
    }

    printf("\nEliminazione del nodo in posizione 3:\n");
    head = eliminaPos(head, 3); // Elimina il nodo alla posizione 3
    stampaLista(head);

    printf("\nEliminazione di tutti i nodi con valore 40:\n");
    head = eliminaElementiValore(head, 40); // Elimina tutti i nodi con valore 40
    stampaLista(head);

    printf("\nLiberazione della lista:\n");
    eliminaLista(head);
    head = NULL;
    stampaLista(head); // Verifica che la lista sia vuota

    return 0;
}

// Funzioni
void stampaLista(pNode head){
    if(head == NULL){
        printf("Lista vuota!\n");
    }
    else{
        pNode curr = head;
        // Stampo fino al penultimo
        while(curr->next != NULL){
            printf("%d ->", curr->data);
            curr = curr->next;
        }
        // stampo l'ultimo
        printf("%d\n", curr->data);
    }
}

pNode inserisciCoda(pNode head, int new_data){
    // Alloco il nuovo nodo
    pNode new = (pNode)malloc(sizeof(Node));
    if(new == NULL){
        printf("Errore di allocazione\n");
        return head;
    }
    new->data = new_data;
    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
    pNode curr = head;
    while(curr->next != NULL) curr = curr->next;
    
    // curr è l'ultimo elemento, quindi attacco new
    curr->next = new;

    return head;
}

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

    // Bisogna che il nuovo nodo sia la testa e bisogna restituire la testa
    new->next = head;

    return new;
}

pNode inserisciPos(pNode head, int new_data, int index) {
    // Controllo se l'indice è valido
    if (index < 0) {
        printf("Indice %d non valido\n", index);
        return head;
    }

    // Caso speciale: lista vuota
    if (head == NULL) {
        if (index == 0) {
            return inserisciTesta(head, new_data);
        } else {
            printf("Lista vuota, impossibile inserire in posizione %d.\n", index);
            return head;
        }
    }

    // Caso speciale: inserimento in testa
    if (index == 0) {
        return inserisciTesta(head, new_data);
    }

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

    // Altri casi: Scorro la lista per trovare la posizione
    int pos = 0;
    pNode curr = head, prec = NULL;

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

    // Verifica se l'indice è fuori dai limiti
    if (pos != index) {
        printf("Indice %d fuori dai limiti.\n", index);
        free(new);
        return head;
    }

    // Inserimento del nodo
    prec->next = new;
    new->next = curr;

    return head;
}

int listaLen(pNode head){
    int len = 0;
    pNode curr = head;

    while(curr != NULL){
        curr = curr->next;
        len ++;
    }

    return len;
}

int listaMax(pNode head, int* err){
    // lista vuota
    if(head == NULL){
        printf("Lista vuota\n");
        *err = 1;
        return 0;
    }

    // altrimenti
    *err = 0;
    int max = head->data;
    pNode curr = head;

    while(curr != NULL){
        if(max < curr->data) max = curr->data;
        curr = curr->next;
    }

    return max;
}

float listaMedia(pNode head, int* err){
    // lista vuota
    if(head == NULL){
        printf("Lista vuota\n");
        *err = 1;
        return 0;
    }

    // altrimenti
    *err = 0;
    float media = 0;
    int len = 0;
    pNode curr = head;

    while(curr != NULL){
        media += curr->data;
        curr = curr->next;
        len++;
    }

    return media/len;
}

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

    return 0;
}

void eliminaLista(pNode head){
    pNode curr = head;

    while(head != NULL){
        curr = head;
        head = head->next;

        free(curr);
    }
}

---

## Esercizio 01 Trova Elemento Massimo (Lista di Interi)

Data una lista di interi, scrivere una funzione che trova e restituisce il massimo.

**Nota**: Questa soluzione è completa

// include
#include <stdio.h>
#include <stdlib.h>

// Dati
typedef struct NodeStruct {
    int data;
    struct NodeStruct *next;
} Node;
typedef Node *pNode;

// Prototipo
void stampaLista(pNode);
int trovaMax(pNode, int*);
pNode inserisciTesta(pNode, int);

int main() {
    // errore
    int err = 0;

    // inizializzo la lista
    pNode head = NULL;
    head = inserisciTesta(head, 10);
    head = inserisciTesta(head, 5);
    head = inserisciTesta(head, 20);
    head = inserisciTesta(head, 15);
    // lista: 15 -> 20 -> 5 -> 10

    printf("Lista creata:\n");
    stampaLista(head);
    printf("\n");

    // trovo il massimo
    int max = trovaMax(head, &err);
    if (!err) {
        printf("Il valore massimo nella lista è: %d\n", max);
    } else {
        printf("La lista è vuota.\n");
    }
    return 0;
}

// Funzione
int trovaMax(pNode head, int *err) {
    // Inizializzo l'errore a 0
    *err = 0;

    // Gestione della lista vuota
    if (head == NULL) {
        printf("Errore: Lista vuota.\n");
        *err = 1;
        return 0; // Valore predefinito in caso di errore
    }

    // Inizializzo il massimo con il primo elemento
    int max = head->data;
    pNode curr = head->next;

    // Scorro la lista per trovare il massimo
    while (curr != NULL) {
        if (curr->data > max) {
            max = curr->data;
        }
        curr = curr->next;
    }

    return max;
}

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

    // Bisogna che il nuovo nodo sia la testa e bisogna restituire la testa
    new->next = head;

    return new;
}

void stampaLista(pNode head){
    if(head == NULL){
        printf("Lista vuota!\n");
    }
    else{
        pNode curr = head;
        // Stampo fino al penultimo
        while(curr->next != NULL){
            printf("%d ->", curr->data);
            curr = curr->next;
        }
        // stampo l'ultimo
        printf("%d\n", curr->data);
    }
}

---

## Esercizio 02: Somma Multipli di un Numero (Liste di Interi)

Data una lista di interi e un numero n, scrivere una funzione restituisce la somma di tutti i multipli di n nella lista.

**Nota**: la soluzione va integrata con il codice di “Operazione Base su Liste di Interi”

// Prototipo
int sommaMultipli(pNode, int, int *);

// Funzione
int sommaMultipli(pNode head, int n, int *err) {
    *err = 0;

    // Controllo lista vuota
    if (head == NULL) {
        printf("Lista vuota.\n");
        *err = 1;
        return 0;
    }

    // Controllo valore di n
    if (n == 0) {
        printf("Valore non valido.\n");
        *err = 1;
        return 0;
    }

    int somma = 0;
    pNode curr = head;

    // Scorri la lista e somma i multipli di n
    while (curr != NULL) {
        if (curr->data % n == 0) {
            somma += curr->data; 
        }
        curr = curr->next;
    }

    return somma;
}

---

## Esercizio 03: Puntatore Minimo Elemento Pari (Liste di Interi)

Data una lista di interi, scrivere una funzione che cerca il minimo elemento pari e restituisce il puntatore all’area di memoria contenente il nodo associato a quel valore.

**Nota**: la soluzione va integrata con il codice di “Operazione Base su Liste di Interi”

### Versione 1

// Prototipo
pNode minimoPari(pNode);

// Funzione
pNode minimoPari(pNode head){
    if(head == NULL){
        printf("Lista vuota.\n");
        return NULL;
    }

    pNode curr = head, pMin = NULL;
    int min = 0;

    while(curr != NULL){
        if(curr->data % 2 == 0){
            if(pMin == NULL || min > curr->data){
                pMin = curr;
                min = curr->data;
            }
        }
        curr = curr->next;
    }

    return pMin;
}

### Versione 2

// Prototipo
pNode minimoPari(pNode);

// Funzione
pNode minimoPari(pNode head) {
    if (head == NULL) {
        printf("Lista vuota.\n");
        return NULL;
    }

    pNode curr = head;
    pNode pMin = NULL;

    // Trova il primo nodo con un valore pari
    while (curr != NULL) {
        if (curr->data % 2 == 0) {
            pMin = curr;
            break;
        }
        curr = curr->next;
    }

    // Se nessun valore pari è trovato
    if (pMin == NULL) {
        printf("Nessun elemento pari trovato.\n");
        return NULL;
    }

    // Cerca il minimo valore pari
    while (curr != NULL) {
        if (curr->data % 2 == 0 && curr->data < pMin->data) {
            pMin = curr;
        }
        curr = curr->next;
    }

    return pMin;
}

---

## Esercizio 04: Cerca e Aggiungi (Lista di Interi)

Data una lista di interi e un valore intero, scrivere una funzione che cerca nella lista la PRIMA occorrenza del valore dato e, se lo trova, aggiunge un nodo adiacente a quello trovato, contenente lo stesso valore.

**Nota**: la soluzione va integrata con il codice di “Operazione Base su Liste di Interi”

==**Nota**: implementare una variante che svole la stessa operazione nella lista per TUTTE le occorrenze del numero in questione.==

// Prototipo
pNode cercaAggiungi(pNode head, int num)

// Funzione
pNode cercaAggiungi(pNode head, int num) {
    // Controllo se la lista è vuota
    if (head == NULL) {
        printf("Lista vuota, impossibile cercare.\n");
        return head;
    }

    // Scorro la lista per cercare il numero
    pNode curr = head;
    while (curr != NULL) {
        if (curr->n == num) {
            // Numero trovato, aggiungo una copia come nodo successivo
            pNode new = (pNode)malloc(sizeof(Node));
            if (new == NULL) {
                printf("Errore di allocazione.\n");
                return head;
            }

            new->n = num;
            new->next = curr->next;
            curr->next = new;

            printf("Elemento %d trovato e aggiunto.\n", num);
            return head; // Ritorno subito dopo aver aggiunto
        }
        curr = curr->next;
    }

    // Se non ho trovato il numero
    printf("Elemento %d non trovato.\n", num);
    return head;
}

---

## Esercizio 05: Trova Massimo Ricorsivo
Come Esercizio $01$, ma ricorsivo. Questo esempio contiene anche delle print per capire meglio cosa succede, ed è già funzionante così (se lo copiate-incollate, va già)

**Nota**: Questa soluzione è completa

// include
#include <stdio.h>
#include <stdlib.h>

// Dati
typedef struct NodeStruct {
    int data;
    struct NodeStruct *next;
} Node;
typedef Node *pNode;

// Prototipo
void stampaLista(pNode);
pNode trovaMaxRicorsivo(pNode);
pNode inserisciTesta(pNode, int);

int main() {
    // inizializzo la lista
    pNode head = NULL;
    head = inserisciTesta(head, 10);
    head = inserisciTesta(head, 5);
    head = inserisciTesta(head, 20);
    head = inserisciTesta(head, 15);
    // lista: 15 -> 20 -> 5 -> 10

    // stampo la lista
    printf("Lista creata:\n");
    stampaLista(head);
    printf("\n");

    // trovo il massimo
    pNode maxNode = trovaMaxRicorsivo(head);
    if (maxNode != NULL) {
        printf("Il valore massimo nella lista è: %d\n", maxNode->data);
    } else {
        printf("La lista è vuota.\n");
    }
    return 0;
}

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

    // Bisogna che il nuovo nodo sia la testa e bisogna restituire la testa
    new->next = head;

    return new;
}

pNode trovaMaxRicorsivo(pNode head) {
    // Caso base: lista vuota
    if (head == NULL) {
        return NULL;
    }

    printf("[LOG]: chiamata a funzione con:\n");
    printf("       head = %d\n", head->data);

    // Caso base: un solo elemento
    if (head->next == NULL) {
        printf("       next: NULL, ritorno %d\n", head->data);
        return head;
    }

    printf("       next: %d, chiamo ricorsivamente\n", head->next->data);

    // Chiamata ricorsiva sul resto della lista
    // Come fa a trovare il massimo della lista?
    // ogni volta che lo chiamo, nella chiamata più interna
    // shifto di un elemento oltre. Quando arrivo al fondo,
    // risalgo confrontando gli elementi, l'ultimo torna col caso base di
    // un solo elemento, risale alla linea dopo la chiamata, e lo confronta
    // con l'elemento appena prima, ritorna il massimo tra i due, e così via
    pNode maxRest = trovaMaxRicorsivo(head->next);

    printf("[LOG]: dopo chiamata ricorsiva, nodo = %d, next = %d\n", head->data, head->next->data);
    printf("       ricevuto maxRest = %d\n", maxRest->data);
    
    // Confronto il valore corrente con il massimo del resto della lista
    if (maxRest->data > head->data) {
        printf("       confrontato %d < %d, ritorno %d\n", head->data, maxRest->data, maxRest->data);
        return maxRest;
    } else {
        printf("       confrontato %d >= %d, ritorno %d\n", head->data, maxRest->data, head->data);
        return head;
    }
}

void stampaLista(pNode head){
    if(head == NULL){
        printf("Lista vuota!\n");
    }
    else{
        pNode curr = head;
        // Stampo fino al penultimo
        while(curr->next != NULL){
            printf("%d ->", curr->data);
            curr = curr->next;
        }
        // stampo l'ultimo
        printf("%d\n", curr->data);
    }
}