Esercizio 28C, palindromi in una lista

Richiami

Liste concatenate in C, aggiunta in coda con Nodo ** e ricorsione sulle liste (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 per riferimento (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 add(Nodo **lista, char c) {                  /* aggiunge in coda */
    while (*lista != NULL)
        lista = &(*lista)->next;                  /* avanza il puntatore al puntatore */
    Nodo *n = malloc(sizeof(Nodo));
    n->value = c;
    n->next = NULL;
    *lista = n;
}

int compareLists(Nodo *a, Nodo *b) {
    if (a == NULL && b == NULL) return 1;         /* finite insieme: uguali */
    if (a == NULL || b == NULL) return 0;         /* lunghezze diverse */
    if (a->value != b->value) return 0;
    return compareLists(a->next, b->next);
}

void copyReversed(Nodo *src, Nodo **copy) {
    if (src == NULL)
        return;
    copyReversed(src->next, copy);                /* prima il resto della lista... */
    add(copy, src->value);                        /* ...poi il primo carattere, in coda */
}

int checkPalindrome(Nodo *lista) {
    Nodo *inv = NULL;
    copyReversed(lista, &inv);
    int r = compareLists(lista, inv);
    while (inv != NULL) {                         /* libera la copia temporanea */
        Nodo *t = inv->next;
        free(inv);
        inv = t;
    }
    return r;
}

Perché la chiamata ricorsiva viene prima di add

add inserisce in coda. Per costruire la lista inversa il primo elemento da accodare deve essere l'ultimo della lista originale. Con la chiamata ricorsiva prima di add, la ricorsione scende fino al fondo e gli add avvengono risalendo: l'ultimo nodo viene accodato per primo, poi il penultimo, e così via fino al primo, che viene accodato per ultimo. Per "ciao": le chiamate scendono su c, i, a, o; risalendo si aggiungono o, a, i, c: la copia è oaic (verificato). Se add fosse prima della chiamata ricorsiva si otterrebbe una copia identica all'originale (ciao) e ogni parola risulterebbe palindroma.

Complessità

• compareLists: $\Theta(\min(n_a, n_b) + 1)$, al più $\Theta(n)$ (una chiamata per coppia di nodi).
• add: $\Theta(k)$ se la lista ha già $k$ nodi (scorre fino alla coda). Quindi copyReversed esegue $n$ add su liste di lunghezza $0, 1, \dots, n-1$: $\sum_{k=0}^{n-1} (k + 1) = \Theta(n^2)$.
• checkPalindrome: $\Theta(n^2)$ per la copia più $\Theta(n)$ per il confronto: $\Theta(n^2)$ in tempo, $\Theta(n)$ in spazio (la copia e lo stack della ricorsione).

Si può scendere a $\Theta(n)$ inserendo in testa (addHead, $\Theta(1)$): scorrendo la lista originale dall'inizio e inserendo ogni carattere in testa alla copia si ottiene l'ordine inverso senza ricorsione.

Prove eseguite

checkPalindrome restituisce $1$ per anna, bob, a, abcba, abccba e la lista vuota (vuota: due liste vuote sono uguali); $0$ per ciao, bod, ab, abcda.

Errori comuni

• Invertire l'ordine ricorsione/add in copyReversed: la copia non è invertita.
• In compareLists confrontare i valori senza controllare prima che nessuno dei due puntatori sia NULL (dereferenzia NULL), o dimenticare il caso di liste di lunghezza diversa ("ab" e "abc").
• In add usare Nodo * invece di Nodo **: quando la lista è vuota la testa del chiamante non viene aggiornata.
• Non inizializzare n->next = NULL nel nuovo nodo.
• Non liberare la copia temporanea (perdita di memoria).