Triedenie poľa smerníkov (riešené príklady)
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.
Alokácia pamäti
Pre alokáciu pamäti je možné využiť funkciu malloc (funkcia jazyka C), alebo new (operátor jazyka C++). Uvedieme definície týchto spôsobov:
malloc
Funkcia malloc definovaná v knižnici stdlib.h:
void * malloc ( size_t size );
- size
- veľkosť pamäti, ktorá sa alokuje
- Návratová hodnota
- V prípade úspechu vráti smerník na alokovanú pamäť, v prípade neúspechu vráti NULL. Návratová hodnota je smetník na void, preto si ho treba pretypovať na želaný typ.
new
Operátor new je definovaný v knižnici iostream.h nasledovne:
[::] new [placement] new-type-name [new-initializer]
[::] new [placement] ( type-name ) [new-initializer]
Operátor new alokuje mapäť pre premenné (resp. objekty) alebo pole premenných, ktoré sú typu type-name a vracia ukazovateľ na túto alokovanú pamäť. Ukazovateľ je na rozdiel od funkcie malloc už pretypovaný na správny typ. Pri neúspechu vyvolá výnimku. Spracovanie vyvolanej výnimky je v nasledujúcom kóde:
int * i_arr;
try {
i_arr = new int[0x3fffffff];
}
catch(...) {
cout<<"Vynimka: nedostatok pamati pre alokaciu";
}
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 pamete!\n");
71 system("pause");
72 exit(1);
73 }
74 //**********************************************************************
75 //* Pomocou operatora new sa kod na riadkoch 68 az 73 zapise nasledovne
76 //* try{
77 //* pole=new (ZAMESTNANEC*)[maxPocet_zamestnancov];
78 //* }
79 //* catch(...)
80 //* { cout<<"Nedostatok pamete";
81 //* exit(1);
82 //* }
83 //*********************************************************************
84
85 // Najprv si musime alokovat priestor pre prveho zamestnanca
86 // (aby data, ktore nacitame sme mali kam ulozit)
87 if((pole[0]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
88 {
89 printf("\n Nedostatok pamete...\n");
90 exit(1);
91 }
92
93 //**********************************************************************
94 //* Pomocou operatora new sa kod na riadkoch 87 az 91 zapise nasledovne
95 //* try{
96 //* pole[0]=new ZAMESTNANEC;
97 //* }
98 //* catch(...)
99 //* { cout<<"Nedostatok pamete";
100 //* exit(1);
101 //* }
102 //*********************************************************************
103 // Nacitanie vsetkych zamestnancov zo suboru
104 for(i=0; nacitajZAMESTNANEC(fr,pole[i]); i++)
105 {
106 //Alokujeme si miesto pre dalsieho zamestnanca:
107 if((pole[i+1]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
108 {
109 printf("\n Nedostatok pamete pre pridanie dalsieho zamestnanca...\n");
110 system("pause");
111 exit(1);
112 }
113
114 // V pripade potreby realokujeme pole pinterov: (Tato situacia nastane
115 // ak pocet zamestnancov v subore je vacsi ako aktualne nastavna hodnota
116 // premennej maxPocet_zamestnancov)
117 if(i == maxPocet_zamestnancov-2)
118 {
119 maxPocet_zamestnancov += KROK_REALOKACIE; // Zvysime maximalny pocet zamestnancov
120 //printf("...realokujem...");
121 if((pole=(ZAMESTNANEC**)realloc(pole,maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
122 {
123 printf(" Nedostatok pamate pre realokaciu pola pointerov!\n");
124 system("pause");
125 exit(1);
126 }
127 }
128 }
129 Pocet_zamestnancov = i;
130 fclose(fr); // zatvorenie suboru, data uz su nacitane..
131 fr = NULL; // zaroven nastavime na NULL pre pripad aby
132 // sme v pripade chybneho pouzitia tohto poitera boli vcas varovani
133
134 // Hlavny cyklus programu
135 do{
136 printf("\n Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)\n"
137 " Meno, Priezvisko, Rok 1\n"
138 " Priezvisko, Meno, Rok 2\n"
139 " Rok, Meno, Priezvisko 3\n"
140 " Rok, Priezvisko, Meno 4\n\n"
141 " Pre ukoncenie programu 0\n\n"
142 " Volba: ");
143 scanf("%d",&volba);
144
145 switch(volba)
146 {
147 case 0: break;
148 case 1: sortFun = porovnajMENO_PRIEZV_ROK; break;
149 case 2: sortFun = porovnajPRIEZV_MENO_ROK; break;
150 case 3: sortFun = porovnajROK_MENO_PRIEZV; break;
151 case 4: sortFun = porovnajROK_PRIEZV_MENO; break;
152 default:
153 printf("\n Neocakavany vstup. Program bude ukonceny.\n");
154 volba=0;
155 }
156 if(volba) // Vypisanie utriedeneho pola na monitor
157 {
158 // Utriedenie zamestnancov:
159 qsort((void*)pole,Pocet_zamestnancov,sizeof(pole[0]),sortFun);
160
161 clrscr(); //vycistime si obrazovku
162 printf("--------------------------------------------------------\n");
163 printf(" ZAMESTNANEC ROK NARODENIA\n");
164 printf("--------------------------------------------------------\n");
165 for(i=0;i<Pocet_zamestnancov;i++)
166 vypisZAMESTNANEC(*pole[i]);
167 printf("--------------------------------------------------------\n");
168 }
169 }while(volba);
170
171 // Na zaver nasleduje uvolnenie pamate, ktoru sme alokovali.
172 // Najprv musime uvolnit pamet, ktoru sme alokovali pre jednotlivych zamestnancov.
173
174 //Pocet alokovanych zamestnancov je o jednehoneho viac...
175 for(i=0; i<skutocnyPocet_zamestnancov + 1;i++)
176 free(pole[i]);
177
178 //Potom uvolnime pamat alokovanu pre pointre
179 free(pole);
180 poleStud = NULL; // a nastavime na NULL (nie je nevyhnutne potrebne)
181
182 system("pause");
183 return 0;
184 }
185
186 // Definicie pouzivanych funkcii:
187 //---------------------------------------------------------------------------
188 int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
189 {
190 int a;
191 a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
192 if(a == EOF) a = 0;
193 return a;
194 }
195 //---------------------------------------------------------------------------
196 void vypisZAMESTNANEC(ZAMESTNANEC V)
197 {
198 printf(" %-20s %-20s %d\n", V.meno, V.priezvisko, V.rok_narodenia);
199 }
200 //---------------------------------------------------------------------------
201 int porovnajROK(const void *V1, const void *V2)
202 {
203 return (*(ZAMESTNANEC**)V1)->rok_narodenia - (*(ZAMESTNANEC**)V2)->rok_narodenia;
204 }
205 //---------------------------------------------------------------------------
206 int porovnajMENO(const void *V1, const void *V2)
207 {
208 return strcmp((*(ZAMESTNANEC**)V1)->meno, (*(ZAMESTNANEC**)V2)->meno);
209 }
210 //---------------------------------------------------------------------------
211 int porovnajPRIEZV(const void *V1, const void *V2)
212 {
213 return strcmp((*(ZAMESTNANEC**)V1)->priezvisko, (*(ZAMESTNANEC**)V2)->priezvisko);
214 }
215 //---------------------------------------------------------------------------
216 int porovnajPRIEZV_MENO(const void *V1, const void *V2)
217 {
218 int a = porovnajPRIEZV(V1, V2);
219 if(a == 0) a = porovnajMENO(V1, V2);
220 return a;
221 }
222 //---------------------------------------------------------------------------
223 int porovnajMENO_PRIEZV(const void *V1, const void *V2)
224 {
225 int a = porovnajMENO(V1, V2);
226 if(a == 0) a = porovnajPRIEZV(V1, V2);
227 return a;
228 }
229 //---------------------------------------------------------------------------
230 int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2)
231 {
232 int a = porovnajMENO_PRIEZV(V1, V2);
233 if(a == 0) a = porovnajROK(V1, V2);
234 return a;
235 }
236 //---------------------------------------------------------------------------
237 int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2)
238 {
239 int a = porovnajPRIEZV_MENO(V1, V2);
240 if(a == 0) a = porovnajROK(V1, V2);
241 return a;
242 }
243 //---------------------------------------------------------------------------
244 int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2)
245 {
246 int a = porovnajROK(V1, V2);
247 if(a == 0) a = porovnajPRIEZV_MENO(V1, V2);
248 return a;
249 }
250 //---------------------------------------------------------------------------
251 int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2)
252 {
253 int a = porovnajROK(V1, V2);
254 if(a == 0) a = porovnajMENO_PRIEZV(V1, V2);
255 return a;
256 }
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);
