Triedenie poľa štruktúr (riešené príklady)
Obsah
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 sú na stránke qsort.
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.
