Ordinare e cercare in C - qsort, bsearch e puntatori a funzione

In questa pagina 5

In Python si scrive sorted(v, key=...) e bisect. In C la libreria standard (<stdlib.h>) offre qsort e bsearch, che lavorano su qualsiasi tipo di array e ricevono dal chiamante una funzione di confronto: serve quindi il puntatore a funzione (Puntatori in C, Funzioni in C).

Puntatori a funzione

Definizione (puntatore a funzione). Il nome di una funzione, senza parentesi, è il suo indirizzo. Un puntatore a funzione si dichiara indicando firma e nome tra parentesi tonde con *:
#include <stdio.h>

int somma(int a, int b) { return a + b; }
int prodotto(int a, int b) { return a * b; }

int applica(int (*f)(int, int), int x, int y) {   /* f: puntatore a funzione */
    return f(x, y);                                /* chiamata tramite il puntatore */
}

int main(void) {
    printf("%d %d\n", applica(somma, 3, 4), applica(prodotto, 3, 4));   /* 7 12 */
    return 0;
}

Esempio. Con int applica(int (*f)(int, int), int x, int y), applica(somma, 3, 4) restituisce 7 e applica(prodotto, 3, 4) restituisce 12.

int (*f)(int, int) è un puntatore a una funzione con due int che restituisce int; senza le parentesi, int *f(int, int) sarebbe una funzione che restituisce int *. Con typedef int (*Confronto)(const void *, const void *); il tipo ha un nome.

qsort

void qsort(void *base, size_t n, size_t dim, int (*cmp)(const void *, const void *));

Definizione (qsort e funzione di confronto)

base: indirizzo del primo elemento; n: numero di elementi; dim: dimensione in byte di un elemento (sizeof v[0]).

cmp(a, b) riceve puntatori agli elementi (come const void *) e restituisce un numero < 0, 0 o > 0 se *a va prima, pari o dopo *b. Si converte il puntatore al tipo vero dell'elemento.

Esempio. qsort(v, 4, sizeof v[0], cmp_int) su {5, -2, 9, 0} lascia {-2, 0, 5, 9}.

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

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);          /* mai x - y: può andare in overflow */
}

int cmp_str(const void *a, const void *b) {          /* array di char *: elementi di tipo char * */
    return strcmp(*(const char * const *)a, *(const char * const *)b);
}

typedef struct { char nome[32]; long num; } Voce;

int cmp_voce(const void *a, const void *b) {         /* per nome, poi per numero */
    const Voce *p = a, *q = b;
    int c = strcmp(p->nome, q->nome);
    return c != 0 ? c : (p->num > q->num) - (p->num < q->num);
}

int v[] = {5, -2, 9, 0};
qsort(v, 4, sizeof v[0], cmp_int);                    /* -2 0 5 9 */

const char *nomi[] = {"Zeno", "Ada", "Mia"};
qsort(nomi, 3, sizeof nomi[0], cmp_str);              /* Ada Mia Zeno */

Voce rubrica[100]; int n = 0;                         /* ... riempita ... */
qsort(rubrica, n, sizeof rubrica[0], cmp_voce);

qsort non è stabile (elementi uguali possono cambiare ordine relativo), costa tipicamente $O(n \log n)$ e usa la stessa funzione cmp per ogni coppia: deve essere un ordine coerente (cmp(a,b) e cmp(b,a) di segno opposto).

bsearch

void *bsearch(const void *chiave, const void *base, size_t n, size_t dim,
              int (*cmp)(const void *, const void *));

Definizione (bsearch). Ricerca binaria (Ricerca lineare e binaria) in $O(\log n)$ : restituisce il puntatore all'elemento trovato o NULL. L'array deve essere già ordinato con lo stesso cmp. La chiave è un puntatore a un elemento "di prova" (anche un Voce con solo il campo chiave riempito); l'indice si ricava con la differenza di puntatori.

Esempio. Su u = {-2, 0, 5, 9} ordinato con cmp_int, bsearch(&k, u, 4, sizeof u[0], cmp_int) con k = 9 restituisce u + 3, cioè l'indice 3.

int cmp_nome(const void *a, const void *b) {         /* confronta solo il campo chiave */
    return strcmp(((const Voce *)a)->nome, ((const Voce *)b)->nome);
}

qsort(rubrica, n, sizeof rubrica[0], cmp_nome);       /* ordinata per nome */
Voce cerca = { .nome = "Mia" };                       /* basta riempire il campo chiave */
Voce *p = bsearch(&cerca, rubrica, n, sizeof rubrica[0], cmp_nome);
if (p != NULL)
    printf("indice %ld, numero %ld\n", (long)(p - rubrica), p->num);

Con cmp_voce (che guarda anche num) la ricerca per solo nome fallirebbe: la chiave di prova viene confrontata con lo stesso cmp dell'ordinamento, quindi cmp deve guardare solo i campi che identificano l'elemento cercato.

Dizionario ordinato su array dinamico di struct

È l'analogo C del dizionario su array ordinato di Realizzare contenitori su array e liste: ricerca $O(\log n)$ con bsearch, inserimento $O(n)$ con memmove, capacità che raddoppia con realloc (Gestione della memoria in C).

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

typedef struct { char nome[32]; long num; } Voce;
typedef struct { Voce *v; 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); }

Voce *rubrica_cerca(const Rubrica *r, const char *nome) {      /* O(log n) */
    Voce chiave;
    strncpy(chiave.nome, nome, sizeof chiave.nome - 1);
    chiave.nome[sizeof chiave.nome - 1] = '\0';
    return bsearch(&chiave, r->v, r->n, sizeof(Voce), cmp_nome);
}

int rubrica_inserisci(Rubrica *r, const char *nome, long num) {   /* O(n); 0 = ok */
    Voce *p = rubrica_cerca(r, nome);
    if (p != NULL) { p->num = num; return 0; }                     /* nome presente: sostituisce */
    if (r->n == r->cap) {                                          /* pieno: raddoppia */
        size_t nuova = r->cap ? 2 * r->cap : 4;
        Voce *t = realloc(r->v, nuova * sizeof(Voce));
        if (t == NULL) return -1;
        r->v = t; r->cap = nuova;
    }
    size_t i = 0;                                                  /* posto: primo elemento >= nome */
    while (i < r->n && strcmp(r->v[i].nome, nome) < 0) i++;
    memmove(&r->v[i + 1], &r->v[i], (r->n - i) * sizeof(Voce));    /* sposta a destra (memmove, non memcpy) */
    strncpy(r->v[i].nome, nome, sizeof r->v[i].nome - 1);
    r->v[i].nome[sizeof r->v[i].nome - 1] = '\0';
    r->v[i].num = num;
    r->n++;
    return 0;
}

int main(void) {
    Rubrica r; rubrica_init(&r);
    rubrica_inserisci(&r, "Zeno", 3);
    rubrica_inserisci(&r, "Ada", 1);
    rubrica_inserisci(&r, "Mia", 2);
    rubrica_inserisci(&r, "Ada", 9);                               /* sostituisce */
    for (size_t i = 0; i < r.n; i++) printf("%s %ld\n", r.v[i].nome, r.v[i].num);
    Voce *p = rubrica_cerca(&r, "Mia");
    printf("%s\n", p ? "trovata" : "assente");
    rubrica_libera(&r);
    return 0;
}

Output: Ada 9, Mia 2, Zeno 3, trovata. Il posto d'inserimento è cercato qui in modo lineare per brevità; con una ricerca binaria "del punto d'inserimento" (come bisect_left) l'intero inserisci resta comunque $O(n)$ per lo spostamento.

Errori tipici

Funzione di confronto che restituisce x - y: overflow con interi grandi.
Dimenticare il cast del void * al tipo vero, o usare un livello di puntatore sbagliato (negli array di stringhe l'elemento è un char *, il confronto riceve char **).
Chiamare bsearch su un array non ordinato o ordinato con un confronto diverso: risultato imprevedibile.
Passare a qsort il numero di byte invece del numero di elementi, o sizeof v (dimensione dell'array intero) al posto di sizeof v[0].
Usare memcpy per spostare zone che si sovrappongono: serve memmove.
Perdere il vecchio puntatore con v = realloc(v, ...) quando realloc fallisce (restituisce NULL): si usa un puntatore temporaneo.

Versione ripasso

Puntatore a funzione: int (*f)(int, int) è un puntatore a funzione che prende due int e restituisce int (senza parentesi, int *f(int, int) sarebbe una funzione che restituisce int *). Il nome della funzione è il suo indirizzo, e f(x, y) la chiama (Puntatori in C, Funzioni in C).
qsort: qsort(base, n, sizeof base[0], cmp), con cmp(const void *a, const void *b) che riceve puntatori agli elementi e restituisce <0, 0 o >0. Esempio: qsort(v, 4, sizeof v[0], cmp_int) su $\{5,-2,9,0\}$ dà $\{-2,0,5,9\}$ .
Confronto sicuro: (x > y) - (x < y), mai x - y, che può andare in overflow.
Stringhe e struct: in un array di char * il confronto riceve char **, quindi strcmp(*(const char * const *)a, *(const char * const *)b). Per una struct si confronta il campo chiave, eventualmente con più campi in cascata.
Proprietà di qsort: non è stabile; costo $O(n\log n)$ ; cmp(a,b) e cmp(b,a) devono avere segno opposto.
bsearch: bsearch(&chiave, base, n, sizeof base[0], cmp) restituisce il puntatore all'elemento o NULL, in $O(\log n)$ (Ricerca lineare e binaria). L'array deve essere ordinato con lo stesso cmp; l'indice è p - base. La chiave di prova passa per lo stesso cmp: se cmp guarda anche num, la ricerca per solo nome fallisce. Basta riempire il campo chiave, come in Voce cerca = {.nome = "Mia"}.
Dizionario ordinato su array dinamico: struct {Voce *v; size_t n, cap;}. cerca usa bsearch in $O(\log n)$ . inserisci: se il nome c'è sostituisce il numero; se l'array è pieno realloc raddoppia la capacità, con un puntatore temporaneo; poi memmove fa posto. Costo $O(n)$ per l'inserimento (Realizzare contenitori su array e liste, Gestione della memoria in C).
Output dell'esempio: con Ada 9, Mia 2, Zeno 3 inseriti in quest'ordine, la ricerca di Mia dà trovata.
Errori tipici: confronto x - y; cast o livello di puntatore sbagliato; bsearch su array non ordinato o con un altro cmp; sizeof v al posto di sizeof v[0]; memcpy su zone sovrapposte (serve memmove); v = realloc(v, ...) che perde il blocco se fallisce.

Esercizi su questo argomento

Esercizio 18 · rubrica ordinata in C