Esercizio 25C, ordini della focacceria (coda)

Richiami

Coda FIFO realizzata con una lista a due puntatori (testa per estrarre, coda per inserire), 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 →; passaggio di strutture per puntatore (Giornata *) e operatore ->, vedi 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 →.

Soluzione

void processaOrdini(Coda *coda, Giornata *giornata, double listino_prezzi[]) {
    while (!isEmpty(coda)) {
        Ordine ordine = dequeue(coda);
        int id = ordine.tipo_focaccia;
        if (giornata->focacce_rimaste[id] > 0) {
            giornata->incasso += listino_prezzi[id];
            giornata->focacce_rimaste[id]--;
        }
    }
}

void calcolaInvenduto(Giornata *giornata, double listino_prezzi[]) {
    for (int i = 0; i < 3; i++)
        giornata->invenduto += giornata->focacce_rimaste[i] * listino_prezzi[i];
}

Scelte da notare.

• Lo pseudocodice ripeti-finché esegue dequeue almeno una volta anche con la coda vuota, e dequeue su una coda vuota è un errore. Con while (!isEmpty(coda)) il controllo precede l'estrazione e la funzione è corretta anche per la coda vuota.
• Gli ordini per un tipo esaurito vengono estratti dalla coda ma non fanno incassare né diminuire la scorta (il cliente se ne va).
• giornata è un puntatore: giornata->incasso modifica la struttura del chiamante (side effect), mentre listino_prezzi[] è un array passato come puntatore (non viene modificato).
• Il tipo tipo_focaccia è usato come indice di focacce_rimaste e di listino_prezzi: $0, 1, 2$.
• calcolaInvenduto somma nell'invenduto: se è chiamata due volte lo conta due volte (il testo parte da invenduto = 0).
• Complessità: processaOrdini $\Theta(n)$ per $n$ ordini in coda (ogni dequeue è $\Theta(1)$); calcolaInvenduto $\Theta(1)$.

Prova eseguita

Prezzi $3{,}4$, $3{,}5$, $3{,}2$; scorte $(2, 1, 3)$; ordini per tipo, in coda: $0, 1, 1, 0, 2, 0, 2$.

• Ordine $0$: venduto ($3{,}4$; scorte $1, 1, 3$). Ordine $1$: venduto ($3{,}5$; scorte $1, 0, 3$). Ordine $1$: esaurita, ignorato. Ordine $0$: venduto ($3{,}4$; scorte $0, 0, 3$). Ordine $2$: venduto ($3{,}2$; $0, 0, 2$). Ordine $0$: esaurita, ignorato. Ordine $2$: venduto ($3{,}2$; $0, 0, 1$).
• Incasso: $3{,}4 + 3{,}5 + 3{,}4 + 3{,}2 + 3{,}2 = 16{,}70$; rimaste $(0, 0, 1)$; invenduto $1 \cdot 3{,}2 = 3{,}20$. Il programma stampa incasso=16.70 invenduto=3.20 rimaste=0 0 1.
• Con la coda vuota e scorte $(1, 1, 1)$: incasso $0$, invenduto $3{,}4 + 3{,}5 + 3{,}2 = 10{,}10$ ✓.

Errori comuni

• Usare giornata.incasso con il punto invece di -> (il parametro è un puntatore).
• do { dequeue } while (...) come nello pseudocodice: errore con la coda vuota.
• Decrementare la scorta anche quando è già zero (scorta negativa) o incassare gli ordini non soddisfatti.
• Dimenticare double per i prezzi e dividere/moltiplicare con interi.
• Cercare di conservare un puntatore al nodo estratto: dequeue libera il nodo e restituisce l'Ordine per valore, quindi basta usare la copia restituita.