CKTIS / C
Povratne funkcije v C: primerjalna funkcija za `qsort`
Podaj primerjalno funkcijo s kazalcem ustreznega tipa, primerjaj celoten obseg tipa `int` brez prekoračitve in ohrani vrstni red zapisov z enakimi ključi.
Različica: 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) je funkcija, ki jo predaš drugi kodi, da jo ta pokliče. qsort iz <stdlib.h> uredi zapisljivo tabelo na mestu in ne vrne vrednosti. Sprejme začetni naslov, število elementov, velikost enega elementa v bajtih in kazalec na funkcijo tipa int (*)(const void *, const void *). Podaj compare_items, ne compare_items(...): ime funkcije se tu pretvori v kazalec, drugi izraz pa funkcijo pokliče. Ne vsiljuj pretvorbe nezdružljivega kazalca na funkcijo; klic prek nezdružljivega tipa kazalca ima nedefinirano obnašanje.
Argumenta const void * kažeta na elementa, ki se primerjata. Pred branjem polj ju priredi kazalcema na dejanski tip elementov s kvalifikatorjem const. V primerjalni funkciji ne spreminjaj tabele in ne določi rezultata glede na trenutni mesti elementov: knjižnica ju lahko med klici premakne. Določi dosleden vrstni red: vrni negativno vrednost, nič ali pozitivno vrednost, če je prvi element manjši, enakovreden oziroma večji od drugega. Pomemben je samo predznak.
INT_MIN in INT_MAX iz <limits.h> sta meji tipa int. Ne vračaj a->key - b->key: na primer, INT_MAX - INT_MIN ni predstavljiv kot int, prekoračitev predznačenega celoštevilskega tipa pa ima nedefinirano obnašanje. Uporabi relacijske primerjave. V -1 unarni minus spremeni predznak vrednosti 1; negacija samega INT_MIN ima v C23 prav tako nedefinirano obnašanje.
Stabilno urejanje ohrani vhodni vrstni red elementov, ki se pri primerjavi izkažejo za enakovredne. qsort tega ne zagotavlja. Ob enakih ključih uporabi shranjeni prvotni položaj ali izberi stabilno urejanje, če mora primerjalna funkcija te elemente še naprej obravnavati kot enakovredne.
V tabeli s končno oznako NULL označuje konec kazalcev na žetone in ni znak \0. Končne oznake ne prištevaj med elemente za urejanje. Pri iskanju preveri mejo tabele pred branjem in poskrbi, da števec tipa int nikoli ne preseže INT_MAX, tudi ob povečanju. Rezultat iskanja -1 pomeni, da žetona ni, in ni negativni rezultat primerjave.
Primeri
#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` in `second` imata enak ključ. Njun vrstni red določa `original`, ne stabilnost `qsort`. Iskanje se ustavi pri `NULL` in vrne `-1`.
Povezane lekcije
- C · Lekcija 88 · Napredna · Različica: 3
- C · Lekcija 90 · Napredna · Različica: 3