Esercizio 29C, centralina meteo (lista ordinata)

Richiami

Liste concatenate e puntatore a puntatore (vedi Liste concatenate in CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C → e Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C →). Si usa il modello "puntatore al puntatore da modificare" (Node **p), che tratta uniformemente testa e nodi intermedi.

Soluzione

Node *insertSorted(Node *log, Reading reading) {
    Node *n = malloc(sizeof(Node));
    n->data = reading;
    Node **p = &log;                                  /* p: indirizzo del puntatore da modificare */
    while (*p != NULL && (*p)->data.minute <= reading.minute)
        p = &(*p)->next;                              /* si ferma al primo minuto maggiore */
    n->next = *p;
    *p = n;
    return log;
}

int removeOutOfRange(Node **log, double minTemperature, double maxTemperature) {
    int removed = 0;
    Node **p = log;
    while (*p != NULL) {
        double t = (*p)->data.temperature;
        if (t < minTemperature || t > maxTemperature) {
            Node *dead = *p;
            *p = dead->next;                          /* scollega (anche la testa) */
            free(dead);
            removed++;
        } else
            p = &(*p)->next;
    }
    return removed;
}

double averageTemperatures(Node *log) {
    double sum = 0.0;
    int n = 0;
    for (; log != NULL; log = log->next) {
        sum += log->data.temperature;
        n++;
    }
    return n == 0 ? 0.0 : sum / n;
}

int countReadingsAboveThreshold(Node *log, double threshold) {
    int c = 0;
    for (; log != NULL; log = log->next)
        if (log->data.temperature > threshold)
            c++;
    return c;
}

Idea del puntatore a puntatore. p contiene l'indirizzo del puntatore che punta al nodo corrente: all'inizio è &log (la testa), poi diventa &(*p)->next (il campo next del nodo precedente). Inserire o togliere significa scrivere in *p, e funziona allo stesso modo per la testa e per un nodo qualsiasi: non servono casi speciali (lista vuota, inserimento in testa, rimozione della testa).

Dettagli.

• insertSorted usa <= nel confronto: una misura con un minuto già presente viene messa dopo quelle con lo stesso minuto (inserimento stabile). Con < andrebbe prima: il testo non lo specifica, vanno bene entrambe purché la lista resti ordinata in modo non decrescente.
• Nella rimozione si legge dead->next prima di free(dead); dopo la free il nodo non si deve più usare. Dopo una rimozione p non avanza (il nodo successivo è ora in *p); avanza solo se il nodo resta.
• averageTemperatures divide per n solo se $n > 0$; la somma è double, quindi nessuna divisione intera.
• Complessità: insertSorted $O(n)$ (scorre fino al punto di inserimento, $O(1)$ se va in testa); removeOutOfRange, averageTemperatures, countReadingsAboveThreshold $\Theta(n)$.

Prove eseguite

• Inserimenti $(30, 22{,}0)$, $(10, 20{,}5)$, $(20, 21{,}0)$ e $(20, 25{,}0)$: lista (10, 20.5) (20, 21.0) (20, 25.0) (30, 22.0) (minuti ordinati; il secondo $20$ dopo il primo).
• Temperature $18{,}0$, $41{,}0$, $22{,}0$, $-3{,}0$ ai minuti $0, 1, 2, 3$, soglie $0{,}0$ e $35{,}0$: rimossi $2$ nodi, restano $(0, 18{,}0)$ e $(2, 22{,}0)$; media $20{,}00$; sopra $19{,}0$: $1$.
• Con soglie $19{,}0$ e $21{,}0$ su quella lista: rimossi $2$ (testa e coda), lista vuota; media $0{,}0$ e conteggio $0$ ✓.

Errori comuni

• Passare Node *log a removeOutOfRange (il prototipo ha Node **): se si rimuove la testa il chiamante non lo vede.
• In insertSorted non gestire l'inserimento in testa o in lista vuota: con il puntatore a puntatore il caso è automatico.
• Fare free(dead) e poi leggere dead->next.
• Avanzare p dopo una rimozione (si salta un nodo).
• Dividere per $0$ nella media con lista vuota (serve il controllo $n > 0$).
• Dimenticare > stretto in countReadingsAboveThreshold (la soglia stessa non conta).