Dnes si ukážeme, jak setřídit pole knihovní funkcí qsort pomocí libovolně definovaného uspořádání a jak v setříděném poli nalézt konkrétní záznam. Příklady jsou trochu náročnější na přetypování ukazatelů, rovněž mohou posloužit jako příklad užitečnosti uživatelem definovaných callback funkcí volaných z knihovny.
15.11.2005 07:00 | Jan Němec | přečteno 20582×
Třídění pole na základě porovnávání dvojic prvků je oblíbenou úlohou snad všech učitelů informatiky, neboť rozvíjí algoritmické myšlení studentů a umožňuje krátkou exkurzi do teorie složitosti. Nejjednodušší algoritmy mají kvadratickou složitost, lepší a složitější n * log(n). Jeden z těch (v průměrném případě) velmi rychlých se jmenuje quicksort a je implementovaný ve standardní knihovně jazyka C.
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (* compar)(const void *, const void *));
Funkce qsort je navržena obecně, tak aby mohla třídit pole jakékoli velikosti a typu prvků podle uživatelem definovaného uspořádání. Parametr base je ukazatel na začátek pole, nmemb počet tříděných prvků a size velikost jednoho prvku v bytech. Poslední parametr compar je ukazatel na porovnávací funkci definovanou programátorem. Funkce musí vracet záporné, nulu nebo kladné číslo pokud je první z dvojice porovnávaných prvků menší, rovný nebo větší než druhý. Parametry třídící i porovnávací funkce jsou typu void *, při skutečném použití bude třeba hojně přetypovávat. Ukážeme si to nejjednodušším na příkladu, třídění náhodně vygenerovaných čísel typu unsigned int.
#include <stdio.h> #include <stdlib.h> #include <time.h> /* Velikost pole */ #define POCET 200 /* Porovnávací funkce, parametry jsou ukazatele na porovnávané prvky. */ int cmp(const void *a, const void *b) { /* Parametry musíme nejprve přetypovat z void * na unsigned *, potom dereferencovat na unsigned a teprve potom porovnat. */ if ( *((unsigned *) a) < *((unsigned *) b) ) { /* První prvek je menší. */ return -1; } if ( *((unsigned *) a) > *((unsigned *) b) ) { /* První prvek je větší. */ return 1; } /* Ani menší ani větší. V úplném uspořádání zbývá jedině rovnost. */ return 0; } int main(void) { /* Tříděné pole */ unsigned pole[POCET]; int i; /* Inicializace generátoru náhodných čísel */ srand(time(NULL)); /* Naplnění pole náhodnými čísly od nuly do 1000 */ for (i = 0; i < POCET; i++) { pole[i] = rand() % 1000; } /* Výpis nesetříděného pole */ puts("Nesetříděno:"); for (i = 0; i < POCET; i++) { printf("%u ", pole[i]); } /* Vlastní třídění */ qsort((void *) pole, POCET, sizeof(unsigned), cmp); /* Výpis setříděného pole */ puts("\n\nSetříděno:"); for (i = 0; i < POCET; i++) { printf("%u ", pole[i]); } /* Odřádkování na závěr */ puts(""); return 0; }
V praxi se obvykle netřídí čísla ale záznamy podle nějakého klíče. Funkce qsort je dostatečně obecná i pro tento případ. Ukážeme si, jak setřídit zaměstnance firmy podle mzdy. Každý zaměstnanec má v našem příkladu jen jméno a plat, ale ve skutečném případě by měl ještě další položky, například nějaké id, adresu, rodné číslo, místo v kanceláři, nadřízeného atd. Bylo by možné definovat přímo pole struktur Zamestnanec a třídit toto pole. Tato implementace by ale byla poněkud neefektivní, neboť sizeof(Zamestnanec) není zanedbatelné číslo a v průběhu třídění se budou prvky pole prohazovat, což by vedlo k opakovanému kopírování větších bloků paměti. Lepší je definovat pole ukazatelů na zaměstnance a třídit toto pole, neboť se budou prohazovat pouze několikabytové ukazatele.
#include <stdio.h> #include <stdlib.h> #include <time.h> /* Velikost pole */ #define POCET 10 typedef struct { unsigned plat; char jmeno[64]; } Zamestnanec; /* Porovnávací funkce, parametry jsou ukazatele na ukazatele na porovnávané typy Zamestnanec. */ int cmp(const void *a, const void *b) { /* Parametry musíme nejprve přetypovat z void * na Zamestnanec **, potom dereferencovat na Zamestnanec *, operátorem -> získat mzdu a teprve potom porovnat. */ if ( (*((Zamestnanec **) a))->plat < (*((Zamestnanec **) b))->plat ) { /* První prvek je menší. */ return -1; } if ( (*((Zamestnanec **) a))->plat > (*((Zamestnanec **) b))->plat ) { /* První prvek je větší. */ return 1; } /* Ani menší ani větší. V úplném uspořádání zbývá jedině rovnost. */ return 0; } int main(void) { /* Tříděné pole */ Zamestnanec * pole[POCET]; int i; /* Inicializace generátoru náhodných čísel */ srand(time(NULL)); /* Naplnění pole náhodnými zaměstnanci s platem od 10 do 60 tisíc */ for (i = 0; i < POCET; i++) { Zamestnanec *pz; pz = (Zamestnanec *) malloc(sizeof(Zamestnanec)); if (!pz) { /* Ve skutečných programech takhle opatrný nejsem, ale tohle je výuka... */ int j; fputs("Málo paměti!\n", stderr); for (j = 0; j < i; j++) { free(pole[j]); } return 1; } pz->plat = 10000 + rand() % 50001; sprintf(pz->jmeno, "Zaměstnanec%03i", i); pole[i] = pz; } /* Výpis nesetříděného pole */ puts("Nesetříděno:"); for (i = 0; i < POCET; i++) { printf("jméno: %s, plat:%u\n", pole[i]->jmeno, pole[i]->plat); } /* Vlastní třídění */ qsort((void *) pole, POCET, sizeof(Zamestnanec *), cmp); /* Výpis setříděného pole */ puts("\n\nSetříděno:"); for (i = 0; i < POCET; i++) { printf("jméno: %s, plat:%u\n", pole[i]->jmeno, pole[i]->plat); } /* Dealokace */ for (i = 0; i < POCET; i++) { free(pole[i]); } /* Odřádkování na závěr */ puts(""); return 0; }
Podobnou syntaxi jako qsort má i funkce bsearch, která hledá půlením intervalu (tedy s logaritmickou časovou složitostí) v setříděném poli konkrétní záznam.
#include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
int (* compar)(const void *, const void *));
Parametr key je něco jako kopie hledaného záznamu, přesně řečeno ukazatel, jehož porovnání funkcí compar s hledaným záznamem vrací 0. V případě zaměstnanců vyhledávaných a setříděných podle mzdy by se zřejmě jednalo o ukazatel na strukturu Zamestnanec s vyplněnou položkou plat, na hodnotě položky jmeno nezáleží. Funkce vrací ukazatel do pole na hledaný záznam nebo NULL, pokud v poli není. Zbytek je stejný jako u funkce qsort. Na konec minulého příkladu před cyklus s dealokací tak můžeme přidat následující kód:
{
Zamestnanec z, *pz, **ppz;
z.plat = 30000;
pz = &z;
/*
Návratová hodnota bsearch je ukazatel na prvek pole tedy ukazatel
na ukazatel na Zamestnanec. Musíme ji přetypovat z void *
na Zamestnanec **, ověřit, zda není NULL, dereferencí získat jednoduchý
ukazatel na Zamestnanec a teprve potom operátorem -> přistupovat
k položkám. Rovněž pozor na první vstupní parametr. Nejde zadat &z,
tedy Zamestnanec *. Je třeba stejný typ, jako je ukzatel na prvek pole,
tedy Zamestnanec **.
Práce s ukazateli dělá občas problémy i zkušeným programátorům v C.
*/
ppz = (Zamestnanec **) bsearch(&pz, pole, POCET, sizeof(Zamestnanec *),
cmp);
if (!ppz) {
printf("Plat přesně %u nemá nikdo.\n", z.plat);
} else {
printf("Plat přesně %u má %s a možná ještě někdo další.\n", z.plat,
(*ppz)->jmeno);
}
}
Všimněte si výpisu v případě úspěšného hledání. Náš příklad se trochu podobá vyhledávání v databázi, ale narozdíl od příkazu SELECT v SQL může bsearch i v případě duplicit vrátit pouze jedinou hodnotu.
Vyhledávání zaměstnanců nám dnešní díl poněkud roztáhlo, proto se ke slíbené práci se znaky dostaneme až příště a povíme si i něco o ladícím makru assert.