WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

Rückruffunktionen in C: Vergleichsfunktion für `qsort`

Übergib eine Vergleichsfunktion als typisierten Funktionszeiger, vergleiche den gesamten `int`-Wertebereich ohne Überlauf und erhalte die Reihenfolge gleicher Schlüssel.

Version: ISO C23; implementation support may vary

Syntax

#include <stdlib.h>

typedef int (*compare_fn)(const void *, const void *);
int compare_items(const void *left, const void *right);

/* For a writable array named items, inside a function: */
compare_fn callback = compare_items;
qsort(items, sizeof items / sizeof items[0], sizeof items[0], callback);

Eine Rückruffunktion (Callback) ist eine Funktion, die du anderem Code übergibst, damit dieser sie aufruft. qsort aus <stdlib.h> sortiert ein beschreibbares Array direkt und gibt keinen Wert zurück. Es erwartet die Startadresse, die Anzahl der Elemente, die Größe eines Elements in Byte und einen Funktionszeiger vom Typ int (*)(const void *, const void *). Übergib compare_items, nicht compare_items(...): Der Funktionsname wird hier in einen Zeiger umgewandelt, der zweite Ausdruck ruft die Funktion auf. Passe keinen inkompatiblen Funktionszeiger durch einen Cast an; ein Aufruf über einen inkompatiblen Zeigertyp hat undefiniertes Verhalten.

Die Argumente vom Typ const void * zeigen auf die zu vergleichenden Elemente. Weise sie vor dem Lesen der Felder Zeigern auf den tatsächlichen, const-qualifizierten Elementtyp zu. Ändere das Array in der Vergleichsfunktion nicht und verwende nicht die aktuellen Positionen: Die Bibliothek darf Elemente zwischen Aufrufen verschieben. Definiere eine konsistente Ordnung: Ein negatives Ergebnis, null oder ein positives Ergebnis bedeutet, dass das erste Element kleiner, gleichwertig oder größer ist. Nur das Vorzeichen zählt.

INT_MIN und INT_MAX aus <limits.h> sind die Grenzen von int. Gib nicht a->key - b->key zurück: INT_MAX - INT_MIN passt beispielsweise nicht in int, und ein Überlauf bei vorzeichenbehafteten Ganzzahlen hat undefiniertes Verhalten. Verwende stattdessen relationale Vergleiche. In -1 negiert das unäre Minus die 1; die Negation von INT_MIN selbst hat in C23 ebenfalls undefiniertes Verhalten.

Eine stabile Sortierung erhält die Eingabereihenfolge der Elemente, die als gleich verglichen werden. qsort garantiert das nicht. Verwende bei gleichen Schlüsseln die gespeicherte ursprüngliche Position als zweites Kriterium oder nutze eine stabile Sortierung, wenn die Vergleichsfunktion diese Elemente weiterhin als gleichwertig einstufen soll.

In einem Array mit Endmarkierung kennzeichnet NULL das Ende der Tokenzeiger; es ist nicht das Zeichen \0. Zähle die Endmarkierung beim Sortieren nicht mit. Prüfe beim Suchen vor dem Lesen die Arraygrenze und achte darauf, dass ein int-Zähler INT_MAX auch beim Erhöhen nicht überschreitet. Das Suchergebnis -1 bedeutet „nicht gefunden“ und ist kein negatives Vergleichsergebnis.

Beispiele

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

struct item {
    int key;
    int original;
    const char *token;
};

typedef int (*compare_fn)(const void *, const void *);

static int compare_items(const void *left, const void *right)
{
    const struct item *a = left;
    const struct item *b = right;

    if (a->key < b->key) return -1;
    if (a->key > b->key) return 1;
    return (a->original > b->original) - (a->original < b->original);
}

static int find_token(const struct item *items, int capacity, const char *token)
{
    for (int i = 0; i < capacity && items[i].token != NULL; ++i) {
        if (strcmp(items[i].token, token) == 0) return i;
    }
    return -1;
}

int main(void)
{
    struct item items[] = {
        {INT_MAX, 0, "high"},
        {0,       1, "first"},
        {INT_MIN, 2, "low"},
        {0,       3, "second"},
        {0,       0, NULL}
    };
    enum { CAPACITY = sizeof items / sizeof items[0] };
    compare_fn callback = compare_items;

    qsort(items, CAPACITY - 1, sizeof items[0], callback);
    for (int i = 0; i < CAPACITY - 1; ++i) {
        puts(items[i].token);
    }
    printf("missing index: %d\n", find_token(items, CAPACITY, "missing"));
    return 0;
}

Ergebnis

low
first
second
high
missing index: -1

`first` und `second` haben denselben Schlüssel. Ihre Reihenfolge ergibt sich aus `original`, nicht aus einer Stabilitätsgarantie von `qsort`. Die Suche hält bei `NULL` an und liefert `-1`.

Zugehörige Lektionen

  • C · Lektion 88 · Fortgeschritten · Version: 3
  • C · Lektion 90 · Fortgeschritten · Version: 3

Quellen