Triedenie(riešené príklady)

Algoritmy a programovanie - zbierka úloh

---

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie
 ::Triedenie poľa komplexných čísel
 ::Triedenie poľa smerníkov na komplexné čísla
 ::Triedenie poľa štruktúr
 ::Triedenie poľa smerníkov

Lineárny zoznam

Binárny strom

Numerické algoritmy

Triedenie poľa štruktúr

Zadanie

Zostavte program, ktorý bude triediť dáta uložené v súbore na základe užívateľom zadaného kritéria. Program po spustení načíta dáta zo súboru a uloží ich do poľa štruktúr. Následne na monitor zobrazí výzvu, v ktorej bude mať užívateľ možnosť vybrať kritérium triedenia. Pre jednoduchosť uvažujme príklad, v ktorom budeme triediť zamestnancov nejakej fiktívnej firmy podľa mena, priezviska alebo podľa roku jeho narodenia. Dáta v súbore nech sú uložené vo formáte kde jednotlivé položky sú oddelené medzerami čiarkami v tvare:

Meno Priezvisko , Rok_narodenia 

Metodický komentár

Cieľom tejto úlohy je precvičiť prácu so štruktúrami v jazyku C, použitie funkcie rýchleho triedenia (quick sort) z knižnice stdlib.h, načítavanie dát zo súboru, a pomôcť osvojiť si základné znalosti pri práci s ukazovateľmi (predávanie ako parameter do funkcie, pretypovávanie).

Vzorové dáta

Janko Maly , 1978
Martin Starsi , 1939
Andrea Mlada , 1990
Jozko Cierny , 1985
Alenka Biela , 1985
Janko Maly , 1983
Alzbetka Mudra , 1978

Zjednodušujúce predpoklady

Dĺžka mena ani priezviska neprekračuje rozsah 20 znakov. V zdrojovom súbore sa nebude nachádzať viac ako 100 záznamov. Zdrojový súbor sa nachádza v tom istom adresáry ako samotný program (*.exe súbor) a jeho názov je: data.txt.

Vzorová výzva programu

Vyber kriterium triedenia.
  Meno                     1
  Priezvisko               2
  Rok narodenia            3
  Pre ukoncenie programu   0
Volba: _

Vzorový vstup

1	

Vzorový výstup

--------------------------------------------------------
 ZAMESTNANEC                               ROK NARODENIA
--------------------------------------------------------
 Alenka               Biela                    1985
 Alzbetka             Mudra                    1978
 Andrea               Mlada                    1990
 Janko                Maly                     1983
 Janko                Maly                     1978
 Jozko                Cierny                   1985
 Martin               Starsi                   1939
--------------------------------------------------------

Návod ako začať

Zo zadania vyplýva, že hlavným účelom programu je triediť (vzostupne príp. zostupne zoradzovať) zamestnancov podľa triediaceho kritéria (meno, priezvisko, rok). Aby sme pri manipulácii (triedení) s jednotlivými zamestnancami pracovali ucelene so všetkými dátami vzťahujúcimi sa ku konkrétnemu zamestnancovi naraz, bude výhodné použiť štruktúru, ktorá nám tieto dáta takpovediac "zabalí". Takto budeme mať údaje o jednom zamestnancovi pohromade a budeme môcť s nimi pohodlne manipulovať. Týmto sme vyriešili problém ako reprezentovať jedného zamestnanca. Teraz sa vynára otázka ako efektívne pracovať s celým súborom zamestnancov. Pretože vieme, že v zdrojovom súbore sa nebude nachádzať viac ako 100 zamestnancov, bude vcelku výhodné použiť statické pole štruktúr na pamätanie všetkých zamestnancov. Dĺžka tohto poľa bude 100 položiek. Jedna položka poľa potom bude predstavovať jedného konkrétneho zamestnanca. Utriedenie zamestnancov potom budeme realizovať utriedením tohto poľa. Pre triedenie poľa ponúka knižnica stdlib.h funkciu rýchleho triedenia qsort. Parametre a použitie funkcie qsort z knižnice stdlib.h si teraz vysvetlíme.

Úplný funkčný prototyp funkcie qsort je nasledovný:

void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *));

Ako vidíme funkcia má štyri parametre, ktorých význam je:

• base - ukazovateľ typu void ukazujúci na nultý element triedeného poľa
• nelem - počet elementov v triedenom poli
• width - veľkosť jedného elementu v bajtoch
• fcmp - ukazovateľ na porovnávaciu funkciu, ktorá porovnáva dva elementy triedeného poľa

Porovnávacia funkcia vyžaduje dva argumenty - ukazovatele typu const void *. Označme tieto argumenty elem1 a elem2. Potom úplný funkčný prototyp porovnávacej funkcie bude:

int (*fcmp)(const void *elem1, const void *elem2);

Od funkcie fcmp sa vyžaduje aby vracala celé číslo v závislosti od výsledku porovnania argumentov elem1 a elem2 nasledovne:

• ak *elem1 < *elem2 potom fcmp vráti celé číslo < 0
• ak *elem1 == *elem2 potom fcmp vráti 0
• ak *elem1 > *elem2 potom fcmp vráti celé číslo > 0

Pri porovnávaní elementov elem1 a elem2 symbol < znamená, že elem1 je menší ako elem2 v tom zmysle, že v utriedenom poli sa elem1 nachádza pred elem2. Podobne pre symbol >. Ak sú porovnávané elementy z pohľadu triediaceho kritéria ekvivalenté (symbol ==) potom funkcia vráti nulu. Napríklad ak porovnávame dva reťazce a kritériom je abcedné usporiadanie, potom reťazec "Alexandra" je menší ako reťazec "Zora". Ak by sme však chceli triediť podľa dĺžky reťazca, potom reťazec "Alexandra" je väčší ako reťazec "Zora".

Triedenie poľa sa potom realizuje volaním funkcie qsort s patričnými parametrami.

Poznámka: Pri porovnávaní porovnávame obsahy argumentov elem1 a elem2, to znamená, že píšeme napr. *elem1 < *elem2 namiesto elem1 < elem2. Zápis elem1 < elem2 by totiž znamenal, že máme porovnať hodnotu elem1 a elem2 čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných elem1 a elem2 (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie elem1 < elem2 by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.

Použitie funkcie qsort ilustrujeme na nasledujúcom jednoduchom príklade:

#include <stdio.h>
#include <stdlib.h>
#define POCET_PRVKOV 6

int pole[POCET_PRVKOV] = { 45, 11, 100, 30, 20, 27 };

int Porovnaj_cele_cisla (const void * a, const void * b)
{
   // Parameter "a" je ukazovateľ typu "const void *". Preto ho pred použitím musíme pretypovať na poiter na "int". Čiže: "(int *)a". 
   // Pretože zápis "(int *)a" predstavuje ukazovateľ a my chceme porovnávať celé číslo, ktoré je uložené tam kde tento ukazovateľ ukazuje
   // musíme ďalej napísať: "*(int *)a". Týmto zápisom sa dostaneme k hodnote čísla na ktoré ukazuje predaný parameter "const void * a".
   // Podobne pre parameter "b".
   return ( *(int*)a - *(int*)b );  
}

int main ()
{
  int n;
  // Vzostupné utriedenie poľa:
  qsort (pole, POCET_PRVKOV, sizeof(int), Porovnaj_cele_cisla);

  // Výpis na monitor:
  for (n=0; n<POCET_PRVKOV; n++)
     printf ("%d ",values[n]);
  return 0;
}

Možné riešenie v jazyku C

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<conio.h>
  4 #include<string.h>
  5 
  6 #define NAZOV_SUBORU "data.txt"
  7 
  8 // Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
  9 struct ZAMESTNANEC {
 10    char meno[21];
 11    char priezvisko[21];
 12    int rok_narodenia;
 13    };
 14 
 15 // Uplne funkcne prototypy pouzivanych funkcii:
 16 
 17 // Nacitanie jedineho zamestnanca zo suboru
 18 int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V);	 
 19 
 20 // Vypisanie jedineho zamestnanca na monitor
 21 void vypisZAMESTNANEC(ZAMESTNANEC V);			 
 22 
 23 // Porovnanie dvoch zamestnancov podla roku narodenia
 24 int porovnajROK(const void *V1, const void *V2);	 
 25 
 26 // Porovnanie dvoch zamestnancov podla mena
 27 int porovnajMENO(const void *V1, const void *V2); 	 
 28 
 29 // Porovnanie dvoch zamestnancov podla priezviska
 30 int porovnajPRIEZV(const void *V1, const void *V2);      
 31 
 32 // Hlavna funkcia programu:
 33 int main(int argc, char* argv[])
 34 {
 35    ZAMESTNANEC pole[100];         // pole struktur pre uchovavanie jednotlivych zamestnancov
 36    int Pocet_zamestnancov = 0;    // pocet nacitanych zamestnancov
 37    int volba;                     // kriterium triedenia / ukoncenia programu
 38    FILE *fr;                      // pointer na subor
 39    int i;                         // pomocna premenna
 40    
 41    // Otvorenie zdrojoveho suboru v rezime "read"
 42    if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
 43    {
 44       printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
 45       system("pause");
 46       exit(1);
 47    }
 48 
 49    // Nacitanie vsetkych zamestnancov zo suboru
 50    for(i=0; nacitajZAMESTNANEC(fr,&pole[i]); i++)
 51    {
 52       ;
 53    }
 54    Pocet_zamestnancov = i;
 55    fclose(fr); // zatvorenie suboru, data uz su nacitane..
 56    fr = NULL;  // zaroven nastavime na NULL pre pripad aby sme 
 57                // v pripade chybneho pouzitia tohto poitera boli vcas varovani
 58    
 59    // Hlavny cyklus programu 
 60    do{
 61       printf("\n Vyber kriterium triedenia. \n"
 62                "   Meno                     1\n"
 63 	       "   Priezvisko               2\n"
 64 	       "   Rok narodenia            3\n\n"
 65 	       "   Pre ukoncenie programu   0\n\n"
 66                " Volba: ");
 67       scanf("%d",&volba);
 68       
 69       switch(volba)
 70       {
 71          case 0: break;
 72          case 1: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajMENO);   break; 
 73                                     // namiesto sizeof(ZAMESTNANEC) mozeme pouzit sizeof(pole[0])
 74          case 2: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajPRIEZV); break;
 75          case 3: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajROK);    break;
 76          default:
 77             printf("\n Neocakavany vstup. Program bude ukonceny.\n");
 78             volba=0;
 79       }
 80       if(volba) // Vypisanie utriedeneho pola na monitor
 81       {
 82          clrscr(); //vycistime si obrazovku
 83          printf("--------------------------------------------------------\n");
 84          printf(" ZAMESTNANEC                               ROK NARODENIA\n");
 85          printf("--------------------------------------------------------\n");
 86          for(i=0; i<Pocet_zamestnancov; i++)
 87             vypisZAMESTNANEC(pole[i]);
 88          printf("--------------------------------------------------------\n");
 89       }
 90    }while(volba);
 91 
 92    system("pause");
 93    return 0;
 94 }
 95 
 96 // Definicie pouzivanych funkcii:
 97 //---------------------------------------------------------------------------
 98 int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
 99 {
100    int a;
101    a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
102    if(a == EOF) a = 0;
103    return a;
104 }
105 //---------------------------------------------------------------------------
106 void vypisZAMESTNANEC(ZAMESTNANEC V)
107 {
108    printf(" %-20s %-20s     %d\n", V.meno, V.priezvisko, V.rok_narodenia);
109 }
110 //---------------------------------------------------------------------------
111 int porovnajROK(const void *V1, const void *V2)
112 {
113    return ((ZAMESTNANEC*)V1)->rok_narodenia - ((ZAMESTNANEC*)V2)->rok_narodenia;
114 }
115 //---------------------------------------------------------------------------
116 int porovnajMENO(const void *V1, const void *V2)
117 {
118    return strcmp(((ZAMESTNANEC*)V1)->meno, ((ZAMESTNANEC*)V2)->meno);
119 }
120 //---------------------------------------------------------------------------
121 int porovnajPRIEZV(const void *V1, const void *V2)
122 {
123    return strcmp(((ZAMESTNANEC*)V1)->priezvisko, ((ZAMESTNANEC*)V2)->priezvisko);
124 }

Komentár k uvedenému riešeniu

V programe sa na prvý pohľad nachádza zopár zvláštností. Prvou je prázdne telo cyklu for pri načítavaní zamestnancov zo súboru - pozri riadok xx programu (nachádza sa tam len bodkočiarka za účelom zdôraznenia vedomého vypustenia tela funkcie). Dôvodom je, že samotné načítanie zamestnancov sa nachádza v porovnávacej (testovacej) časti cyklu for. Ak sa úspešne načíta nejaký zamestnanec zo súboru potom funkcia nacitajZAMESTNANEC vracia nenulové kladné číslo, v opačnom prípade nulu a cyklus for sa skončí. Druhou zvláštnosťou je spôsob načítavania položiek "meno", "priezvisko" a "rok_narodenia" v tele definicie funkcie nacitajZAMESTNANEC - pozri riadok xx. V tomto prípade s výhodou využívame možností funkcie fscanf, pričom využívame skutočnosť, že jednotlivé položky sú oddelené medzerou a čiarkou. Treťou zvláštnosťou je použitie typu const void * v parametroch a následné pretypovávanie v tele na pointer na pomenovanú štruktúru ZAMESTNANEC vo všetkých troch porovnávacích funkciách - porovnajMENO, porovnajPRIEZV a porovnajROK. Toto priamo súvisí s požiadavkou na parametre porovnávacej funkcie, ktorá musí vyhovovať funkčnému prototypu funkcie triedenia - qsort.

Nedostatky uvedeného riešenia a námety na zlepšenie

Program nie je vhodný na triedenie väčšieho množstva dát. Pri triedení sa manipuluje s celými položkami (štruktúra ZAMESTNANEC), ktoré majú v tomto prípade veľkosť sizeof(ZAMESTNANEC) == 48 Bajtov. Funkcia qsort tak musí pri triedení kopírovať celý obsah, čo môže byť časovo náročné. Ak by navyše jednotlivé položky uchovávali ešte väčie množstvo dát (ďalšie údaje o zamestnancovi, ako napríklad pracovné zaradenie, osobné hodnotenie zamestnanca, kontaktné informácie a pod.) bola by situácia ešte horšia. Podobný nedostatok má aj funkcia vypisZAMESTNANEC. V tomto prípade však tento problém nie je kritický. Prvou možnosťou ako zefektívniť triedenie je redukovanie veľkosti štruktúry ZAMESTNANEC. To sa dá docieliť použitím dynamicky alokovanej pamäte pre uchovávanie mena a priezviska zamestnanca. V tomto prípade by mohla štruktúra ZAMESTNANEC vyzerať nasledovne:

struct ZAMESTNANEC {
   char *meno;
   char *priezvisko;
   int rok_narodenia;
   };

Potom by sa pamäťové nároky na uchovávanie redukovali na 12 Bajtov. Je však nevyhnutné pamätať na to, že adresy uchovávané v položkách "meno" a "priezvisko" môžu byť ľubovolné (sú neinicializované) a preto môžu ukazovať na ľubovolné miesto v pamäti. Preto treba použiť dynamickú alokáciu pamäte (funkcia malloc, resp. operátor new) a ukazovatele "meno" a "priezvisko" správne nastaviť (využitím návratovej hodnoty funkcie malloc, resp. operátora new).

Ďalšou možnosťou ako zefektívniť triedenie je použitie poľa ukazovateľov na prvky typu ZAMESTNANEC. Ukazovateľ na typ ZAMESTNANEC (či už pôvodný alebo tu uvedený) má veľkosť 4 Bajty. Z pohľadu triedenia funkciou qsort je preto tento spôsob ešte výhodnejší.

Použitím kombinácie oboch možností (dynamicky alokovaný priestor pre uchovávenie jednotlivých záznamov typu ZAMESTNANEC a použitie poľa ukazovateľov na prvky typu ZAMESTNANEC pre účely triedenia) je možné dosiahuť hospodárne využitie pamäte a zároveň efektívne triedenie rozsiahlejšieho súboru dát.

Druhou možnosťou sa zaoberá nasledujúca časť - Triedenie poľa ukazovateľov.

Triedenie poľa ukazovateľov alebo Triedime štruktúry efektívne

Zadanie

Uvažujme rovnaké zadanie ako v predošlom. Navyše požadujme viacúrovňové (vnorené) triedenie podľa triediaceho kritéria s nižšou prioritou ak sú položky podľa aktuálneho triediaceho kritéria ekvivalentné. V našom jednoduchom príklade to znamená, že ak napríklad triedime zamestnancov podľa krstného mena a mená niektorých zamestnancov sú rovnaké, potom budú títo utriedení podľa priezviska. Naopak, ak budeme triediť podľa priezviska a priezviská niektorých zamestnancov budú rovnaké, potom ich utriedime podľa krstného mena. Túto situáciu môžeme rozšíriť aj o triedenie podľa roku narodenia. V tomto prípade môžeme definovať prioritu jednotlivým triediacim kritériam a triediť následne podľa priorít.

Metodický komentár

Cieľom tejto úlohy v porovaní s predchádzajúcou je efektívne triediť dáta použitím ukazovateľov a poukázať na ďalšie možnosti pri ich triedení. Využijú sa pokročilejšie techniky práce s ukazovateľmi, dynamická alokácia a realokácia pamäte.

Vzorové dáta

Ako v predošlom.

Zjednodušujúce predpoklady

Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte.

V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.

Vzorová výzva programu

Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)
  Meno, Priezvisko, Rok    1
  Priezvisko, Meno, Rok    2
  Rok, Meno, Priezvisko    3
  Rok, Priezvisko, Meno    4
  Pre ukoncenie programu   0
Volba: _

Vzorový vstup

1	

Vzorový výstup

--------------------------------------------------------
 ZAMESTNANEC                               ROK NARODENIA
--------------------------------------------------------
 Alenka               Biela                    1985
 Alzbetka             Mudra                    1978
 Andrea               Mlada                    1990
 Janko                Maly                     1978
 Janko                Maly                     1983
 Jozko                Cierny                   1985
 Martin               Starsi                   1939
--------------------------------------------------------

Návod ako začať

Prvým významným rozdielom v porovnaní s predchádzajúcim zadaním je skutočnosť, že počet záznamov (zamestnancov) v súbore nie je obmedzený a je vopred neznámy. Z toho dôvodu je použitie statického poľa štruktúr neefektívne. Riešením je dynamická alokácia pamäte. Mohli by sme tak dynamicky alokovať pole štruktúr podľa aktuálnej potreby programu. Ak sa však zamyslíme nad požiadavkou efektívneho triedenia zamestnancov prichádzame k záveru, že ani toto riešenie by nebolo vhodné. Dôvodom je činnosť funkcie qsort, ktorá pri triedení manipuluje s celými položkami poľa, ktoré by v tomto prípade boli štruktúry (keďže by sa jednalo o pole štruktúr či už staticky alebo dynamicky alokované). Funkcia qsort by tak musela pracovať pri triedení s pomerne veľkým objemom dát. Riešením tejto situácie je použitie dynamicky alokovaného poľa ukazovateľov. Jednotlivé položky poľa by potom už neboli samotné štruktúry, ale adresy týchto štruktúr. Ako vieme, veľkosť adresy je 4 bajty (resp. 8B v 64-bitovom OS). Takže funkcia qsort bude triediť pole adries tak aby po zotriedení boli splnené požiadavky triedenia dané prioritami triediacich kritérií. Ak zhrnieme doteraz povedané, tak pre pamätanie celého súboru zamestnancov je výhodné použiť dynamicky alokované pole ukazovateľov, v ktorom pre každý prvok poľa budeme dynamicky alokovať pamäťový priestor pre pamätanie štruktúry uchovávajúcej údaje o jednom konkrétnom zamestnancovi.

Druhým významným rozdielom je požiadavka na viacúrovňové triedenie. Pri písaní porovnávacích funkcií zohľadňujúcich tri úrovne priorít triediacih kritérií je výhodné začať od písania funkcií pre jednoúrovňové triedenie (pozri predchádzajúci príklad), tieto ďalej využiť pri písaní dvojúrovňových, a tieto spolu zasa pri písaní trojúrovňových. Takto môžeme veľmi jednoducho a prehľadne podľa potreby napísať rôzne mnohoúrovňové porovnávacie funkcie.

Možné riešenie v jazyku C

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<conio.h>
  4 #include<string.h>
  5 
  6 #define NAZOV_SUBORU "data.txt"
  7 #define KROK_REALOKACIE 100
  8 
  9 // Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
 10 struct ZAMESTNANEC {
 11    char meno[21];
 12    char priezvisko[21];
 13    int rok_narodenia;
 14    };
 15 
 16 // Uplne funkcne prototypy pouzivanych funkcii:
 17 
 18 // Nacitanie jedineho zamestnanca zo suboru
 19 int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V);	      
 20 
 21 // Vypisanie jedineho zamestnanca na monitor
 22 void vypisZAMESTNANEC(ZAMESTNANEC V);			      
 23 
 24 // Porovnanie dvoch zamestnancov podla roku narodenia
 25 int porovnajROK(const void *V1, const void *V2);	      
 26 
 27 // Porovnanie dvoch zamestnancov podla mena
 28 int porovnajMENO(const void *V1, const void *V2); 	      
 29 
 30 // Porovnanie dvoch zamestnancov podla priezviska
 31 int porovnajPRIEZV(const void *V1, const void *V2);           
 32 
 33 // Porovnanie najprv podla priezviska potom podla mena
 34 int porovnajPRIEZV_MENO(const void *V1, const void *V2);      
 35 int porovnajMENO_PRIEZV(const void *V1, const void *V2);      // podobne dalej...
 36 int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2);
 37 int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2);
 38 int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2);
 39 int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2);
 40 
 41 // Hlavna funkcia programu:
 42 int main(int argc, char* argv[])
 43 {
 44    // Pozor, zmena v porovnani s predchadzajucim riesenim! 
 45    ZAMESTNANEC **pole;               
 46 
 47    // Pocet nacitanych zamestnancov            
 48    int Pocet_zamestnancov = 0;                  
 49    // Prednastaveny maximalny pocet zamestnancov
 50    int maxPocet_zamestnancov = 100;             
 51    // kriterium triedenia / ukoncenia programu
 52    int volba;                                   
 53    // pointer na zdrojovy subor, z ktoreho budeme nacitavat zamestnancov
 54    FILE *fr;                                    
 55    // pointer na funkciu, pomocou ktorej budeme triedit
 56    int (*sortFun)(const void *,const void *);   
 57    int i;      // pomocna premenna
 58    
 59    // Otvorenie zdrojoveho suboru v rezime "read"
 60    if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
 61    {
 62       printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
 63       system("pause");
 64       exit(1);
 65    }
 66 
 67    // Prvotna alokacia pamate pre pole pointrov na pomenovanu strukturu ZAMESTNANEC
 68    if((pole=(ZAMESTNANEC**)malloc(maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
 69    {
 70       printf(" Nedostatok pamate!\n");
 71       system("pause");
 72       exit(1);
 73    }
 74 
 75    // Najprv si musime alokovat priestor pre prveho zamestnanca 
 76    // (aby data, ktore nacitame sme mali kam ulozit)
 77    if((pole[0]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
 78    {
 79       printf("\n Nedostatok pamete...\n");
 80       exit(1);
 81    }
 82 
 83    // Nacitanie vsetkych zamestnancov zo suboru
 84    for(i=0; nacitajZAMESTNANEC(fr,pole[i]); i++)
 85    {
 86 		//Alokujeme si miesto pre dalsieho zamestnanca:
 87       if((pole[i+1]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
 88       {
 89          printf("\n Nedostatok pamete pre pridanie dalsieho zamestnanca...\n");
 90          system("pause");
 91          exit(1);
 92       }
 93 
 94       // V pripade potreby realokujeme pole pinterov: (Tato situacia nastane
 95       // ak pocet zamestnancov v subore je vacsi ako aktualne nastavna hodnota
 96       // premennej maxPocet_zamestnancov)
 97       if(i == maxPocet_zamestnancov-2)
 98       {
 99          maxPocet_zamestnancov += KROK_REALOKACIE;  // Zvysime maximalny pocet zamestnancov
100          //printf("...realokujem...");
101          if((pole=(ZAMESTNANEC**)realloc(pole,maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
102          {
103             printf(" Nedostatok pamate pre realokaciu pola pointerov!\n");
104             system("pause");
105             exit(1);
106          }
107       }
108    }
109    Pocet_zamestnancov = i;
110    fclose(fr); // zatvorenie suboru, data uz su nacitane..
111    fr = NULL;  // zaroven nastavime na NULL pre pripad aby 
112                // sme v pripade chybneho pouzitia tohto poitera boli vcas varovani
113    
114    // Hlavny cyklus programu 
115    do{
116       printf("\n Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)\n"
117 	       "   Meno, Priezvisko, Rok    1\n"
118 	       "   Priezvisko, Meno, Rok    2\n"
119 	       "   Rok, Meno, Priezvisko    3\n"
120                "   Rok, Priezvisko, Meno    4\n\n"
121 	       "   Pre ukoncenie programu   0\n\n"
122 	       " Volba: ");
123       scanf("%d",&volba);
124       
125       switch(volba)
126       {
127          case 0: break;
128          case 1: sortFun = porovnajMENO_PRIEZV_ROK;   break;
129          case 2: sortFun = porovnajPRIEZV_MENO_ROK;   break;
130          case 3: sortFun = porovnajROK_MENO_PRIEZV;   break;
131          case 4: sortFun = porovnajROK_PRIEZV_MENO;   break;
132          default:
133             printf("\n Neocakavany vstup. Program bude ukonceny.\n");
134             volba=0;
135       }
136       if(volba) // Vypisanie utriedeneho pola na monitor
137       {
138          // Utriedenie zamestnancov:
139          qsort((void*)pole,Pocet_zamestnancov,sizeof(pole[0]),sortFun);
140 
141          clrscr(); //vycistime si obrazovku
142          printf("--------------------------------------------------------\n");
143          printf(" ZAMESTNANEC                               ROK NARODENIA\n");
144          printf("--------------------------------------------------------\n");
145          for(i=0;i<Pocet_zamestnancov;i++)
146             vypisZAMESTNANEC(*pole[i]);
147          printf("--------------------------------------------------------\n");
148       }
149    }while(volba);
150 
151    // Na zaver nasleduje uvolnenie pamate, ktoru sme alokovali.
152    // Najprv musime uvolnit pamet, ktoru sme alokovali pre jednotlivych zamestnancov.
153 
154    //Pocet alokovanych zamestnancov je o jednehoneho viac...
155    for(i=0; i<skutocnyPocet_zamestnancov + 1;i++) 
156       free(pole[i]);
157 
158    //Potom uvolnime pamat alokovanu pre pointre
159    free(pole);
160    poleStud = NULL;  // a nastavime na NULL (nie je nevyhnutne potrebne)
161    
162    system("pause");
163    return 0;
164 }
165 
166 // Definicie pouzivanych funkcii:
167 //---------------------------------------------------------------------------
168 int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
169 {
170    int a;
171    a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
172    if(a == EOF) a = 0;
173    return a;
174 }
175 //---------------------------------------------------------------------------
176 void vypisZAMESTNANEC(ZAMESTNANEC V)
177 {
178    printf(" %-20s %-20s     %d\n", V.meno, V.priezvisko, V.rok_narodenia);
179 }
180 //---------------------------------------------------------------------------
181 int porovnajROK(const void *V1, const void *V2)
182 {
183    return (*(ZAMESTNANEC**)V1)->rok_narodenia - (*(ZAMESTNANEC**)V2)->rok_narodenia;
184 }
185 //---------------------------------------------------------------------------
186 int porovnajMENO(const void *V1, const void *V2)
187 {
188    return strcmp((*(ZAMESTNANEC**)V1)->meno, (*(ZAMESTNANEC**)V2)->meno);
189 }
190 //---------------------------------------------------------------------------
191 int porovnajPRIEZV(const void *V1, const void *V2)
192 {
193    return strcmp((*(ZAMESTNANEC**)V1)->priezvisko, (*(ZAMESTNANEC**)V2)->priezvisko);
194 }
195 //---------------------------------------------------------------------------
196 int porovnajPRIEZV_MENO(const void *V1, const void *V2)
197 {
198    int a = porovnajPRIEZV(V1, V2);
199    if(a == 0) a = porovnajMENO(V1, V2);
200    return a;
201 }
202 //---------------------------------------------------------------------------
203 int porovnajMENO_PRIEZV(const void *V1, const void *V2)
204 {
205    int a = porovnajMENO(V1, V2);
206    if(a == 0) a = porovnajPRIEZV(V1, V2);
207    return a;
208 }
209 //---------------------------------------------------------------------------
210 int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2)
211 {
212    int a = porovnajMENO_PRIEZV(V1, V2);
213    if(a == 0) a = porovnajROK(V1, V2);
214    return a;
215 }
216 //---------------------------------------------------------------------------
217 int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2)
218 {
219    int a = porovnajPRIEZV_MENO(V1, V2);
220    if(a == 0) a = porovnajROK(V1, V2);
221    return a;
222 }
223 //---------------------------------------------------------------------------
224 int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2)
225 {
226    int a = porovnajROK(V1, V2);
227    if(a == 0) a = porovnajPRIEZV_MENO(V1, V2);
228    return a;
229 }
230 //---------------------------------------------------------------------------
231 int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2)
232 {
233    int a = porovnajROK(V1, V2);
234    if(a == 0) a = porovnajMENO_PRIEZV(V1, V2);
235    return a;
236 }

Komentár k uvedenému riešeniu

Bude zverejnený neskôr.

Nedostatky uvedeného riešenia a námety na zlepšenie

Program nie je vhodný na triedenie extrémne rozsiahlych dát. Riešením tohto nedostatku je použitie iných triediacich funkcií, ktoré pracujú na princípe triedenia triedeného súboru po častiach. Ďalším nedostatkom je výpis utriedených dát na monitor. Táto operácia môže byť pri väčšom počte záznamov časovo veľmi zdĺhavá. Oveľa výhodnejšie a zároveň rýchlejšie je zapisovať výsledky do súboru. V tomto prípade by postačovalo modifikovať funkciu vypisZAMESTNANEC tak, aby vyhovovala tomuto účelu.

vypisZAMESTNANEC(FILE *fw, ZAMESTNANEC *V)
{
   // Zaroven efektivnejsie pristupujeme k polozkam zamestnanca (parameter V je pointer...)
   fprintf(fw," %-20s %-20s     %d\n", V->meno, V->priezvisko, V->rok_narodenia);  
}

Ak by sme si ďalej zadefinovali funkciu na výpis všetkých zamestnancov celý program by sme zjednodušili a výpis zamestnancov by bol univerzálnejší v tom zmysle, že výpis zamestnancov či už do súboru alebo na monitor by mal jednotnú podobu. Funkcia na výpis všetkých zamestnancov by mohla vyzerať nasledovne:

vypisZAMESTNANCOV(FILE *fw, ZAMESTNANEC **pole, int Pocet_zamestnancov)
{
   printf("--------------------------------------------------------\n");
   printf(" ZAMESTNANEC                               ROK NARODENIA\n");
   printf("--------------------------------------------------------\n");
   for(i=0;i<Pocet_zamestnancov;i++)
      vypisZAMESTNANEC(fw, pole[i]);
   printf("--------------------------------------------------------\n");
}

Potom by jednoducho stačilo otvoriť nejaký súbor v režime "write" a zavolať túto funkciu na zápis všetkých zamestnancov do súboru. Ak by sme však chceli vypísať zamestnancov na monitor, potom namiesto ukazovateľa na otvorený súbor zadáme stdout. Čiže do programu vložíme riadok:

   vypisZAMESTNANCOV(stdout,pole,Pocet_zamestnancov);