Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

Povratne funkcije u C-u: komparator za `qsort`

Proslijedite komparator kao pokazivač na funkciju odgovarajućeg tipa, usporedite cijeli raspon tipa `int` bez preljeva i sačuvajte redoslijed zapisa s jednakim ključem.

Verzija: ISO C23; implementation support may vary

Sintaksa

#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);

Povratna funkcija (callback) funkcija je koju prosljeđujete drugom kôdu da je on pozove. qsort iz <stdlib.h> sortira polje koje se može mijenjati izravno na mjestu i ne vraća vrijednost. Prima početnu adresu, broj elemenata, veličinu jednog elementa u bajtovima i pokazivač na funkciju tipa int (*)(const void *, const void *). Proslijedite compare_items, a ne compare_items(...): naziv funkcije ovdje se pretvara u pokazivač, dok drugi izraz poziva funkciju. Nemojte prisilnom pretvorbom prilagođavati nekompatibilan pokazivač na funkciju; poziv preko nekompatibilnog tipa pokazivača ima nedefinirano ponašanje.

Argumenti const void * pokazuju na elemente koji se uspoređuju. Prije čitanja članova dodijelite ih pokazivačima na stvarni tip elementa s kvalifikatorom const. Nemojte mijenjati polje u komparatoru niti temeljiti rezultat na trenutačnim položajima: biblioteka može premještati elemente između poziva. Definirajte dosljedan poredak: vratite negativnu vrijednost, nulu ili pozitivnu vrijednost ako je prvi element manji, ekvivalentan odnosno veći od drugoga. Važan je samo predznak.

INT_MIN i INT_MAX iz <limits.h> granice su tipa int. Ne vraćajte a->key - b->key: primjerice, INT_MAX - INT_MIN nije moguće prikazati tipom int, a preljev cijelog broja s predznakom ima nedefinirano ponašanje. Upotrijebite relacijske usporedbe. U izrazu -1 unarni minus mijenja predznak broju 1; promjena predznaka samog INT_MIN također ima nedefinirano ponašanje u C23.

Stabilno sortiranje čuva ulazni redoslijed elemenata koji se pri usporedbi pokažu ekvivalentnima. qsort to ne jamči. Pri jednakim ključevima upotrijebite spremljeni izvorni položaj ili odaberite stabilno sortiranje ako komparator te elemente i dalje mora smatrati ekvivalentnima.

U polju sa završnom oznakom NULL označuje kraj pokazivača na tokene i nije znak \0. Završnu oznaku nemojte ubrajati među elemente za sortiranje. Pri pretraživanju provjerite granicu polja prije čitanja i pripazite da brojač tipa int ne prijeđe INT_MAX ni pri povećavanju. Rezultat pretraživanja -1 znači „nije pronađeno” i nije negativan rezultat usporedbe.

Primjeri

#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;
}

Rezultat

low
first
second
high
missing index: -1

`first` i `second` imaju jednak ključ. Njihov redoslijed određuje `original`, a ne stabilnost funkcije `qsort`. Pretraživanje se zaustavlja na `NULL` i vraća `-1`.

Povezane lekcije

  • C · Lekcija 88 · Napredno · Verzija: 3
  • C · Lekcija 90 · Napredno · Verzija: 3

Izvori