Discussione esercizio 30:

#include <stdlib.h>

/* Inserisce l'elemento e nella lista ordinata L e ritorna la lista modificata. */
List insord_elem(List L, Elem *e) {
    int val = e->val;
    if (L == NULL || val <= L->val) {
        e->next = L;
        return e;
    } else {
        Elem *prec = L;
        while (prec->next != NULL && (prec->next)->val < val)
            prec = prec->next;
        e->next = prec->next;
        prec->next = e;
        return L;
    }
}

/* Crea e inserisce un nuovo elemento con valore val nella lista ordinata L e 
 * ritorna la lista modificata. */
List insord(List L, int val) {
    Elem *e = malloc(sizeof (Elem));
    e->val = val;
    return insord_elem(L, e);
}

---

Discussione esercizio 31:

/* Inverte la lista L. Usa il seguente algoritmo: inverte il primo elemento,
 * poi i primi due, poi i primi tre, e così via. Al k-esimo passo, avendo
 * invertito i primi k-1 elementi della lista, per invertire i primi k deve
 * solamente mettere il k-esimo elemento in testa alla lista già invertita
 * dei primi k-1 elementi. Se la lista è 1 -> 2 -> 3 -> 4 -> 5 allora i passi
 * sono i seguenti:
 * 1                       2 -> 3 -> 4 -> 5
 * 2 -> 1                  3 -> 4 -> 5
 * 3 -> 2 -> 1             4 -> 5
 * 4 -> 3 -> 2 -> 1        5
 * 5 -> 4 -> 3 -> 2 -> 1
 */
List reverse(List L) {
    List R = L;
    L = NULL;
    while (R != NULL) {     //finchè ci sono elementi nella lista R
        Elem *e = R;        //prendi il primo elemento di R,
        R = R->next;        //sgancialo da R e
        e->next = L;        //mettilo in testa alla lista invertita.
        L = e;
    }
    return L;
}

/* versione ricorsiva della funzione reverse() */
List reverse_r(List L) {
    if (L == NULL || L->next == NULL)
        return L;
    Elem *first = L;
    L = reverse_r(L->next);
    (first->next)->next = first;
    first->next = NULL;
    return L;
}

---

Discussione esercizio 32:

/**************************** FILE archivio_mem.c *****************************/
/* Implementazione in memoria primaria tramite liste */
#include "archivio_mem.h"
#include <stdlib.h>

typedef struct DElem {    //elemento della lista (archivio)
    Dipendente    d;      //dipendente contenuto in un elemento della lista
    struct DElem *next;
} DElem, *DList;        

static DList *archivio = NULL;
static int numDipendenti = 0;


void open_archivio() {}

void add_dipendente(Dipendente d) {
    DElem *new = malloc(sizeof(DElem));
    new->d = d;
    new->next = archivio;
    archivio = new;
    numDipendenti++;
}

int num_dipendenti() {
    return numDipendenti;
}

Dipendente get_dipendente(int i) {
    DElem *p = archivio;
    while (i > 0) {
        p = p->next;
        i++;
    }
    return p->d;
}

void close_archivio() {
    while (archivio != NULL) {
        DElem *p = archivio->next;
        free(archivio);
        archivio = p;
    }
}

---

Algoritmo insertion-sort per ordinare una lista di interi:

List insord_elem(List L, Elem *e);

List insertion_sort(List L) {
    List R = L;
    L = NULL;
    while (R != NULL) {
        Elem *e = R;
        R = R->next;
        L = insord_elem(L, e);
    }
    return L;
}

Esempio di uso di liste: programma che conta le occorrenze delle parole distinte lette dallo standard input. Possibilità di usare la redirezione (operatore di redirezione < da terminale) per ridirigere lo standard input da file. Discussione circa i vantaggi della progettazione top-down del programma: prima si determina la decomposizione del programma in funzioni, si specifica cosa deve fare ogni funzione e il relativo prototipo, si scrive il main usando le funzioni in accordo alle specifiche, e infine si implementano le funzioni. Il programma usa una lista per mantenere le parole distinte e i relativi conteggi delle occorrenze. Le specifiche della lista, delle funzioni e il main:

/* Programma che legge dallo standard input le parole contenute in un testo
 * (fino a che incontra EOF), costruisce una lista delle parole distinte e
 * per ognuna di esse mantiene il numero di occorrenze. Si può usare
 * la redirezione: ad esempio, se il programma si chiama words, il comando
 * words < testo.txt fa sì che lo standard input del programma sia rediretto
 * al file testo.txt (sia sotto Windows che Linux e affini). */

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

typedef struct WElem {
    char *        word;       //una parola (stringa allocata dinamicamente)
    int           count;      //il numero di occorrenze della parola
    struct WElem *next;
} WElem, *WList;

/* Legge dallo standard input la prossima parola e la ritorna in una stringa
 * allocata dinamicamente. Se incontra EOF prima di aver letto qualche carattere
 * della parola, ritorna NULL. */
char *next_word();

/* Aggiunge la parola w alla lista L. Se non era già presente usa w nel nuovo
 * elemento che aggiunge alla lista, altrimenti libera la memoria di w. Inoltre,
 * aggiorna il conteggio delle occorrenze di w. */
WList wl_add(WList L, char *w);

int wl_count(WList L);    //Ritorna il numero di parole (distinte) in L

void wl_print(WList L);   //Stampa la lista L

void wl_free(WList L);    //Libera la memoria di L

int main() {
    char *word;
    WList L = NULL;
    while ((word = next_word()) != NULL)
        L = wl_add(L, word);
    printf("Numero parole distinte: %d\n", wl_count(L));
    wl_print(L);
    wl_free(L);
}

Implementazione di tutte le funzioni:

#include <ctype.h>
#include <string.h>

char *next_word() {
    char *w = NULL;
    int c, n = 0;
    do {
        c = getchar();
        if (isalpha(c)) {
            w = realloc(w, n + 2);
            w[n++] = c;
        }
    } while (c != EOF && (n == 0 || isalpha(c))) ;
    if (w != NULL) w[n] = '\0';
    return w;
}

/* Ogni nuova parola viene aggiunta in coda alla lista. Questo permette di avere
 * le parole della lista in ordine di apparizione. Inoltre, le parole più
 * frequenti tenderanno a trovarsi nelle prime posizioni della lista mentre
 * quelle più rare tenderanno verso le ultime posizioni, così la ricerca di
 * parole già presenti nella lista risulterà in media più veloce. */
WList wl_add(WList L, char *w) {
    WElem *p = L, *last = NULL;
    while (p != NULL && strcmp(p->word, w) != 0) {
        last = p;
        p = p->next;
    }
    if (p == NULL) {
        WElem *new = malloc(sizeof(WElem));
        new->word = w;
        new->count = 1;
        new->next = NULL;
        if (last == NULL) L = new;
        else last->next = new;
    } else
        p->count++;
    return L;
}

int wl_count(WList L) {
    int n = 0;
    while (L != NULL) {
        L = L->next;
        n++;
    }
    return n;
}

void wl_print(WList L) {
    while (L != NULL) {
        printf("%4d  %s\n", L->count, L->word);
        L = L->next;
    }
}

void wl_free(WList L) {
    while (L != NULL) {
        WElem *next = L->next;
        free(L->word);
        free(L);
        L = next;
    }
}

Dai siti Progetto Manuzio e Project Gutenberg si possono scaricare tantissimi libri, italiani e stranieri, in file di testo che possono essere dati in input al programma.
Esercizio 33    Scrivere una funzione WList wl_sort(WList L) che ordina la lista di parole L rispetto al campo word e ritorna il puntatore alla lista ordinata.
Esercizio 34    Scrivere una funzione int wl_equal(WList L1, WList L2) che ritorna vero se le due liste di parole L1 e L2 sono uguali. Per uguali si intende che devono avere la stessa lunghezza e gli elementi in posizioni corrispondenti devono avere lo stesso contenuto.