# Esercitazione 12: Liste 2

# Correzione Midterm (TDE 13.11.2024)

Scrivere un programma per analizzare i voti conseguiti dagli studenti di una classe del liceo durante tutte le verifiche dell'anno. Le informazioni sono registrate in un vettore di un tipo strutturato, dove ciascun elemento rappresenta uno studente e contiene:

- Un campo "cognome" di tipo stringa con il cognome dello studente.
- Un intero "n" per indicare il numero di verifiche sostenute dallo studente.
- Un array di interi "voti" che contiene i voti dello studente nelle verifiche (le caselle del vettore sono riempite dalla zero e se uno studente ha svolto meno verifiche degli altri le caselle dopo le prime n non hanno contenuto significativo)

1) Scrivere una funzione analizzaStudenti che prende in ingresso un array definito come sopra (ed eventuali variabili aggiuntive) e restituisce sia:

- media_massima: il valore della media per lo studente con la media più alta nel vettore,
- media_totale: la media delle medie di tutti gli studenti nel vettore.

2) Scrivere una funzione studentiBravi che prende in ingresso un array di studenti (ed eventuali variabili aggiuntive) e riporta al chiamante una stringa contenente i cognomi (separati da spazi) di tutti gli studenti con media superiore a media_totale.

Si invochino entrambe le funzioni nel main e si esegua la stampa dei valori calcolati dalle funzioni nel main, non nelle funzioni.

Si parta dal file: https://www.dropbox.com/scl/fi/zzhg7muve4659k13d4sh8/testo.c?rlkey=4kprwk1es8wqs2gmj96z0cswi&dl=0

Col file fornito il programma dovrà stampare

- Media massima di uno studente: 8.33
- Media totale dei voti: 6.87
- Studenti con media superiore alla media totale: Boracchi Campi Conti

#include <stdio.h>
#include <string.h>

#define NUM_STUDENTI 5
#define NUM_VERIFICHE 5

typedef struct {
    char cognome[50];
    int voti[NUM_VERIFICHE];
    int n; // numero di verifiche effettivo
} Studente;

void analizzaStudenti(Studente[], int, float*, float*);
void studentiBravi(Studente[], int, float, char[]);

int main() {
    // dichiarazione ed inizializzazione classe
    Studente classe[NUM_STUDENTI] = {
        {"Boracchi", {7, 8, 9, 6}, 4},
        {"Campi", {8, 8, 8, 8, 8}, 5},
        {"Peretti", {4, 6, 7, 5}, 4},
        {"Conti", {9, 8, 8}, 3},
        {"Valoriani", {4, 6, 7, 3}, 4}
    };
    
    // Calcolo medie
    float media_totale, media_massima;
    analizzaStudenti(classe, NUM_STUDENTI, &media_totale, &media_massima);
    
    // Stampa delle medie
    printf("Media massima di uno studente: %.2f\n", media_massima);
    printf("Media totale dei voti: %.2f\n", media_totale);
    
    // Studenti con media superiore
    char res[5 * 50] = ""; // Inizializzo a stringa vuota
    studentiBravi(classe, NUM_STUDENTI, media_totale, res);

    // Stampa degli studenti bravi
    printf("Studenti con media superiore alla media totale: %s\n", res);

    return 0;
}

void analizzaStudenti(Studente classe[], int dim_classe, float* media_totale, float* media_massima) {
    *media_totale = 0;
    *media_massima = 0;
    float tmp_media;

    // Ciclo sulla classe
    for (int i = 0; i < dim_classe; i++) {
        // Calcolo la media dello studente in questione
        tmp_media = 0;
        for (int j = 0; j < classe[i].n; j++) {
            tmp_media += classe[i].voti[j];
        }
        tmp_media /= classe[i].n;

        // Controllo se è la media massima
        if (*media_massima < tmp_media) {
            *media_massima = tmp_media;
        }

        // Aggiorno la media totale
        *media_totale += tmp_media;
    }

    // Calcolo la media totale
    *media_totale /= dim_classe;
}

void studentiBravi(Studente classe[], int dim_classe, float media_totale, char res[]) {
    // Inizializzo la stringa per il risultato
    strcpy(res, "");

    float tmp_media;

    // Ciclo sulla classe per calcolare le medie
    for (int i = 0; i < dim_classe; i++) {
        tmp_media = 0;
        for (int j = 0; j < classe[i].n; j++) {
            tmp_media += classe[i].voti[j];
        }
        tmp_media /= classe[i].n;

        // Se la media dello studente è > media_totale, aggiorno la stringa
        if (tmp_media > media_totale) {
            strcat(res, classe[i].cognome);
            strcat(res, " ");
        }
    }

    // Tolgo l'ultimo spazio, se necessario
    if (strlen(res) > 0) {
        res[strlen(res) - 1] = '\0';
    }
}

---

# Inserisci in Coda + (Liste di Interi)
Scrivere una variante della funzione inserisci in coda per liste di interi che riesca ad effettuare l’inserimento in coda in tempo costante.
Vale a dire: ogni volta che si vuole inserire un nodo in coda non si deve scorrere tutta la lista.
**Nota**: la soluzione va integrata con il codice dell’esercizio “Operazioni Base su Liste di Interi”.

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

// Funzione
pNode inserisciCodaPlus(pNode head, pNode * tail, int new_value){
	// Alloco il nuovo nodo
	pNode new = (pNode)malloc(sizeof(Node));
	if(new == NULL){
		printf("Errore di Allocazione.\n");
		return head;
	}
	
	// Assegno i campi del nuovo nodo
	new->data = new_value;
	new->next = NULL;
	
	// Controllo se la lista è vuota
	if(head == NULL){
		// Assegno il nuovo valore alla coda
		*tail = new;
		// REstituisco la testa
		return new;
	}
	
	// Modifico il puntatore a next dell'ultimo nodo
	(*tail)->next = new;
	// Modifico l'ultimo nodo
	*tail = new;
	// Restituisco la testa (quella data in input)
	return head;
}

---

# Selection Sort su Liste (Liste di Interi)
Si scriva una funzione che implementi l’algoritmo Selection Sort per ordinare liste di interi.
La funzione deve ordinare la lista direttamente, non copiarla in un’altra lista.
**Nota**: la soluzione va integrata con il codice dell’esercizio “Operazioni Base su Liste di Interi”.
==**Bonus**: e se volessi fare lo swap tra i nodi invece che scambiare i valori?==

// Prototipo
pNode selectionSortListe(pNode);

// Funzione
pNode selectionSortListe(pNode head) {
    // Controllo lista vuota o con un solo elemento
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // Variabili per il ciclo
    pNode curr_i = head, curr_j;
    int tmp;

    // Algoritmo di ordinamento
    while (curr_i->next != NULL) {
        curr_j = curr_i->next;
        while (curr_j != NULL) {
            if (curr_i->data > curr_j->data) {
                // Scambia i dati tra curr_i e curr_j
                tmp = curr_i->data;
                curr_i->data = curr_j->data;
                curr_j->data = tmp;
            }
            curr_j = curr_j->next;
        }
        curr_i = curr_i->next;
    }
    
		// Restituisco la testa della lista
    return head; 
}

---

# Bubble Sort su Liste (Liste di Interi)
Si scriva una funzione che implementi l’algoritmo Bubble Sort per ordinare liste di interi.
La funzione deve ordinare la lista direttamente, non copiarla in un’altra lista.
**Nota**: la soluzione va integrata con il codice dell’esercizio “Operazioni Base su Liste di Interi”.
==**Bonus**: e se volessi fare lo swap tra i nodi invece che scambiare i valori?==

pNode bubbleSortListe(pNode head) {
    // Controllo se la lista è vuota o ha un solo elemento
    if (head == NULL || head->next == NULL) {
        return head; // Già ordinata
    }

    pNode last_sorted = NULL;  // Nodo fino al quale la lista è già ordinata
    pNode curr;
    int tmp, n_swap;

    do {
        curr = head;
        n_swap = 0;

        // Scorro la lista fino al nodo già ordinato
        while (curr->next != last_sorted) {
            if (curr->data > curr->next->data) {
                // Scambia i dati tra curr e curr->next
                tmp = curr->data;
                curr->data = curr->next->data;
                curr->next->data = tmp;
                n_swap = 1;
            }
            curr = curr->next; // Avanza al nodo successivo
        }

        // Aggiorno il nodo fino al quale la lista è già ordinata
        last_sorted = curr;
    } while (n_swap); // Continua finché ci sono scambi

    return head;
}

---

# Inversione di Lista (Liste di Interi o Stringhe)

Si scriva una funzione che prenda in input una lista di stringhe e che inverta la lista senza usarne un’altra d’appoggio.

**Nota**: la soluzione va integrata con il codice dell’esercizio “Operazioni Base su Liste di Interi” oppure “Operazioni Base su Liste di Stringhe”.

// Prototipo
pNode invertiLista(pNode);

// Funzione
pNode invertiLista(pNode head) {
    // Controllo se la lista è vuota o ha un solo elemento
    if (head == NULL || head->next == NULL) return head;

    // Variabili per tracciare i puntatori
    pNode curr = head, prec = NULL, succ;

    // Scorro la lista e inverto i collegamenti
    while (curr != NULL) {
        succ = curr->next;   // Salvo il successore
        curr->next = prec;   // Inversione del link
        prec = curr;         // Avanzo il precedente
        curr = succ;         // Avanzo il corrente
    }

    // Restituisco la nuova testa
    return prec;
}

---

# Catena di Stringhe CCTSF (Liste di Stringhe) (TDE 19.02.2007 p.t. 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.

## Versione Iterativa

// 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

// 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);
}