LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> 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 21020×

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ů

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

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

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

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