Esercizio 18rubrica ordinata in C

Esame

In questa pagina 4

Testo (prova di programmazione di "appello simulato" di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD, anno accademico non indicato nel testo; adattato da un tema d'esame in Java: il tipo di esercizio, un dizionario su array ordinato, è tipico anche di una prova in C, e qui è riscritto in C).

Si gestisce una rubrica telefonica: un dizionario di coppie nome numero in cui il nome è la chiave (nessun omonimo) e il numero è un intero grande (qui long long). Scrivere:

il tipo Rubrica con le operazioni di inserimento (se il nome c'è già si sostituisce il numero), ricerca, rimozione e stampa; la ricerca deve costare $O(\log n)$ ; la stampa scrive una coppia per riga nel formato nome : numero;
un programma di prova che riceve due nomi di file, file1 e file2, dalla riga di comando; carica una prima rubrica dal contenuto di file1 (stesso formato della stampa); poi legge dallo standard input nomi, uno per riga: se il nome è nella prima rubrica, la coppia viene spostata (rimossa dalla prima e inserita in una seconda rubrica); il ciclo termina con il carattere Q; infine scrive la seconda rubrica in file2.

Esempio di file1 (paperopoli.txt):

Pippo : 3424987574
Topolino : 3874628761
Paperino : 4866286343
Ciccio : 4992348384
Minnie : 3762476513
Gastone : 872348761
Rockerduck : 4802382434
Gambadilegno : 3759483281
Paperina : 4832340983

e dello standard input (input.txt): Pippo, Topolino, Bassotti, Gambadilegno, Minnie, Q (una riga ciascuno). Lanciato come ./rubrica paperopoli.txt topolinia.txt < input.txt, il programma scrive in topolinia.txt le quattro coppie trovate, in ordine alfabetico; Bassotti non c'è: si segnala su standard error.

Teoria: Ordinare e cercare in C - qsort, bsearch e puntatori a funzione, Strutture (struct) in C, Gestione della memoria in C, File di record e controllo degli errori riga per riga.

Progetto

Voce = struct con il nome (array di char di lunghezza fissa, così la copia è semplice) e il numero in long long: nel testo originale il numero è un long Java (64 bit); in C long ha 32 bit su Windows e 64 su Linux, e numeri come 4992348384 superano $2^{31}$ , quindi serve long long (con %lld e strtoll).
Rubrica = array dinamico di Voce ordinato per nome, con n voci e capacità cap che si raddoppia con realloc. L'ordine rende possibile bsearch ( $O(\log n)$ ) e la stampa ordinata.
Inserimento $O(n)$ : se il nome c'è già (trovato con bsearch) si sostituisce il numero; altrimenti si cerca il posto, si fa spazio con memmove (le zone si sovrappongono: memcpy sarebbe scorretto) e si copia la voce.
Rimozione $O(n)$ : bsearch, copia della voce in un parametro di uscita, memmove per chiudere il buco.
Caricamento: righe nome : numero; per ogni riga strstr(riga, " : ") trova il separatore, strtoll converte il numero controllando fine; le righe errate sono segnalate su stderr con il numero di riga e saltate.
main: due rubriche, fgets per i nomi (togliendo il '\n' con strcspn), strcmp(nome, "Q") per terminare; ogni nome trovato viene spostato con rubrica_rimuovi seguito da rubrica_inserisci nella seconda; la seconda si scrive su file2; si liberano entrambe.

Codice

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

#define LUNG_NOME 32

typedef struct {
    char nome[LUNG_NOME];
    long long num;                 /* long long: su Windows long ha solo 32 bit */
} Voce;

typedef struct {
    Voce *v;                       /* array ordinato per nome */
    size_t n, cap;
} Rubrica;

static int cmp_nome(const void *a, const void *b) {
    return strcmp(((const Voce *)a)->nome, ((const Voce *)b)->nome);
}

void rubrica_init(Rubrica *r) { r->v = NULL; r->n = r->cap = 0; }
void rubrica_libera(Rubrica *r) { free(r->v); rubrica_init(r); }

/* O(log n): puntatore alla voce o NULL */
Voce *rubrica_cerca(const Rubrica *r, const char *nome) {
    Voce chiave;
    snprintf(chiave.nome, sizeof chiave.nome, "%s", nome);
    return bsearch(&chiave, r->v, r->n, sizeof(Voce), cmp_nome);
}

/* O(n) per gli spostamenti; restituisce 0 se ok, -1 se la memoria manca */
int rubrica_inserisci(Rubrica *r, const char *nome, long long num) {
    Voce *p = rubrica_cerca(r, nome);
    if (p != NULL) { p->num = num; return 0; }               /* chiave unica: sostituisce */
    if (r->n == r->cap) {
        size_t nuova = r->cap ? 2 * r->cap : 8;
        Voce *t = realloc(r->v, nuova * sizeof(Voce));
        if (t == NULL) return -1;
        r->v = t; r->cap = nuova;
    }
    size_t i = 0;
    while (i < r->n && strcmp(r->v[i].nome, nome) < 0) i++;  /* primo elemento >= nome */
    memmove(&r->v[i + 1], &r->v[i], (r->n - i) * sizeof(Voce));
    snprintf(r->v[i].nome, sizeof r->v[i].nome, "%s", nome);
    r->v[i].num = num;
    r->n++;
    return 0;
}

/* toglie la voce e la copia in *uscita; 0 se rimossa, -1 se assente */
int rubrica_rimuovi(Rubrica *r, const char *nome, Voce *uscita) {
    Voce *p = rubrica_cerca(r, nome);
    if (p == NULL) return -1;
    *uscita = *p;
    size_t i = (size_t)(p - r->v);
    memmove(&r->v[i], &r->v[i + 1], (r->n - i - 1) * sizeof(Voce));
    r->n--;
    return 0;
}

/* una voce per riga, nel formato "nome : numero" */
void rubrica_stampa(const Rubrica *r, FILE *f) {
    for (size_t i = 0; i < r->n; i++)
        fprintf(f, "%s : %lld\n", r->v[i].nome, r->v[i].num);
}

/* legge un file "nome : numero"; segnala su stderr le righe errate; restituisce le voci lette */
int rubrica_carica(Rubrica *r, FILE *f) {
    char riga[128];
    int n = 0, nriga = 0;
    while (fgets(riga, sizeof riga, f) != NULL) {
        nriga++;
        riga[strcspn(riga, "\n")] = '\0';
        if (riga[0] == '\0') continue;
        char *sep = strstr(riga, " : ");
        if (sep == NULL || sep == riga || sep - riga >= LUNG_NOME) {
            fprintf(stderr, "riga %d: formato errato\n", nriga);
            continue;
        }
        *sep = '\0';
        char *fine;
        long long num = strtoll(sep + 3, &fine, 10);
        if (fine == sep + 3 || *fine != '\0') {
            fprintf(stderr, "riga %d: numero non valido\n", nriga);
            continue;
        }
        if (rubrica_inserisci(r, riga, num) == 0) n++;
    }
    return n;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "uso: %s file1 file2 < nomi\n", argv[0]);
        return 1;
    }
    FILE *f1 = fopen(argv[1], "r");
    if (f1 == NULL) { perror(argv[1]); return 1; }
    Rubrica r1, r2;
    rubrica_init(&r1); rubrica_init(&r2);
    rubrica_carica(&r1, f1);
    fclose(f1);

    char nome[128];
    while (fgets(nome, sizeof nome, stdin) != NULL) {
        nome[strcspn(nome, "\n")] = '\0';
        if (strcmp(nome, "Q") == 0) break;                   /* Q: fine */
        Voce v;
        if (rubrica_rimuovi(&r1, nome, &v) == 0)
            rubrica_inserisci(&r2, v.nome, v.num);           /* spostata da r1 a r2 */
        else
            fprintf(stderr, "%s: non trovato\n", nome);
    }

    FILE *f2 = fopen(argv[2], "w");
    if (f2 == NULL) { perror(argv[2]); return 1; }
    rubrica_stampa(&r2, f2);
    fclose(f2);
    rubrica_libera(&r1); rubrica_libera(&r2);
    return 0;
}

Alcuni punti da notare:

snprintf(dest, sizeof dest, "%s", s) copia troncando se serve e termina sempre con '\0': più sicuro di strcpy, e diverso da strncpy, che non aggiunge '\0' se la sorgente è lunga.
bsearch restituisce un puntatore dentro l'array: dopo un realloc o un memmove quel puntatore non è più valido. In rubrica_rimuovi lo si usa solo prima di modificare l'array, e l'indice si ricava con p - r->v.
In rubrica_inserisci la ricerca del posto è lineare per semplicità: l'inserimento è comunque $O(n)$ per lo spostamento, quindi non cambia l'ordine di grandezza; con una ricerca binaria del punto d'inserimento si risparmiano solo i confronti.

Prova ed esito

Compilato con cc -Wall -Wextra senza avvisi e provato così:

$ ./rubrica paperopoli.txt topolinia.txt < input.txt
Bassotti: non trovato                       (su standard error)
$ cat topolinia.txt
Gambadilegno : 3759483281
Minnie : 3762476513
Pippo : 3424987574
Topolino : 3874628761

Altre prove fatte: un file con righe vuote, senza separatore, con un numero non valido e con un nome ripetuto (Ada : 1 poi Ada : 9: resta Ada : 9; le righe errate sono segnalate con il loro numero e saltate); uno stress con 2000 righe casuali (nomi ripetuti) e tutti i nomi in ordine casuale in ingresso: il file di uscita coincide con la rubrica attesa, ordinata e senza duplicati.

Errori comuni

Usare long per i numeri di telefono: su Windows ha 32 bit e 4992348384 va in overflow; long long con %lld.
memcpy al posto di memmove per fare spazio o chiudere un buco.
bsearch su un array che non è ordinato con lo stesso confronto.
Usare un puntatore ottenuto da bsearch dopo aver modificato l'array.
Non togliere il '\n' letto da fgets: "Pippo\n" non coincide con "Pippo".
v = realloc(v, ...) senza usare un puntatore temporaneo: se realloc fallisce si perde il blocco.
Non liberare le rubriche: memory leak.

Versione ripasso

Prova di "appello simulato" di Fondamenti di Informatica (UniPD, in Java; adattato a C). Teoria: Ordinare e cercare in C - qsort, bsearch e puntatori a funzione, Strutture (struct) in C.

Dati. Voce { char nome[32]; long long num; } (long long: long è a 32 bit su Windows, 4992348384 va in overflow); Rubrica { Voce *v; size_t n, cap; } array ordinato per nome, capacità raddoppiata con realloc (puntatore temporaneo).

Operazioni.

cerca: bsearch con cmp_nome, $O(\log n)$ .
inserisci: nome presente → sostituisce il numero; altrimenti memmove per fare posto (zone sovrapposte, non memcpy), $O(n)$ .
rimuovi: bsearch, copia in *uscita, memmove per chiudere il buco.
stampa: nome : numero per riga. carica: fgets, strstr(riga, " : "), strtoll con controllo di fine; righe errate su stderr e saltate.

Programma. Argomenti file1 file2; nomi da stdin (fgets + strcspn per il '\n', Q termina); nome trovato → rimuovi da r1 e inserisci in r2; scrittura di r2 in file2; rubrica_libera per entrambe. Con paperopoli.txt e input.txt escono Gambadilegno, Minnie, Pippo, Topolino in ordine; Bassotti segnalato su stderr.

Errori comuni: long per i numeri; memcpy al posto di memmove; bsearch su array non ordinato; puntatore di bsearch usato dopo aver modificato l'array; '\n' non tolto; realloc senza temporaneo; memory leak.

Esercizio 18rubrica ordinata in C

Progetto

Codice

Prova ed esito

Errori comuni

Teoria collegata