LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> C/C++ (28) - Standardní knihovna potřetí

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 | Články autora | přečteno 17073×

Třídění a vyhledávání

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.

Pokračování příště

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.

Verze pro tisk

pridej.cz

 

DISKUZE

Prosba čtenářům o zpětnou vazbu 15.11.2005 11:04 Jan Němec
malloc 15.11.2005 12:33 Lukáš Jelínek
  |- Re: malloc 15.11.2005 12:45 Jan Němec
  L Re: malloc 15.11.2005 13:17 Aleš Hakl
    L Re: malloc & overcommit memory 3.12.2005 18:55 Tomáš "Atom" Klas




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

13.9.2017 8:00 /František Kučera

Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze