|
|
| (3 medziľahlé úpravy od rovnakého používateľa nie sú zobrazené.) |
| Riadok 1: |
Riadok 1: |
| − | [[Kategória:Študijné materiály]]
| |
| − | [[Kategória:Programovanie]]
| |
| − | [[Kategória:jazyk C]]
| |
| | {{Draft}} | | {{Draft}} |
| | {{Skripta programovanie (zbierka úloh)}} | | {{Skripta programovanie (zbierka úloh)}} |
| | + | |
| | + | ==Triedenie poľa komplexných čísel== |
| | + | ===Zadanie=== |
| | + | Vytvorte program, ktorý usporiada pole komplexných čísel. Úlohu riešte pomocou algoritmu Quicksort (definovaného v quicksort) a pomocou vstavanej funkcie jazyka C qsort. Porovnajte dosiahnuté výsledky (rýchlosť výpočtu). |
| | + | |
| | + | Viac na [[Triedenie poľa komplexných čísel (riešené príklady)]] |
| | + | |
| | | | |
| | ==Triedenie poľa štruktúr== | | ==Triedenie poľa štruktúr== |
| Riadok 11: |
Riadok 15: |
| | ===Metodický komentár=== | | ===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). | | 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 (jazyk C)|qsort]].
| |
| − |
| |
| − | ===Možné riešenie v jazyku C===
| |
| − | <source lang="c" line >
| |
| − | #include<stdio.h>
| |
| − | #include<stdlib.h>
| |
| − | #include<conio.h>
| |
| − | #include<string.h>
| |
| − |
| |
| − | #define NAZOV_SUBORU "data.txt"
| |
| − |
| |
| − | // Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
| |
| − | struct ZAMESTNANEC {
| |
| − | char meno[21];
| |
| − | char priezvisko[21];
| |
| − | int rok_narodenia;
| |
| − | };
| |
| − |
| |
| − | // Uplne funkcne prototypy pouzivanych funkcii:
| |
| | | | |
| − | // Nacitanie jedineho zamestnanca zo suboru
| + | Viac na [[Triedenie poľa štruktúr (riešené príklady)]] |
| − | int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V);
| |
| | | | |
| − | // Vypisanie jedineho zamestnanca na monitor
| |
| − | void vypisZAMESTNANEC(ZAMESTNANEC V);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla roku narodenia
| |
| − | int porovnajROK(const void *V1, const void *V2);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla mena
| |
| − | int porovnajMENO(const void *V1, const void *V2);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla priezviska
| |
| − | int porovnajPRIEZV(const void *V1, const void *V2);
| |
| − |
| |
| − | // Hlavna funkcia programu:
| |
| − | int main(int argc, char* argv[])
| |
| − | {
| |
| − | ZAMESTNANEC pole[100]; // pole struktur pre uchovavanie jednotlivych zamestnancov
| |
| − | int Pocet_zamestnancov = 0; // pocet nacitanych zamestnancov
| |
| − | int volba; // kriterium triedenia / ukoncenia programu
| |
| − | FILE *fr; // pointer na subor
| |
| − | int i; // pomocna premenna
| |
| − |
| |
| − | // Otvorenie zdrojoveho suboru v rezime "read"
| |
| − | if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
| |
| − | {
| |
| − | printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
| |
| − | system("pause");
| |
| − | exit(1);
| |
| − | }
| |
| − |
| |
| − | // Nacitanie vsetkych zamestnancov zo suboru
| |
| − | for(i=0; nacitajZAMESTNANEC(fr,&pole[i]); i++)
| |
| − | {
| |
| − | ;
| |
| − | }
| |
| − | Pocet_zamestnancov = i;
| |
| − | fclose(fr); // zatvorenie suboru, data uz su nacitane..
| |
| − | fr = NULL; // zaroven nastavime na NULL pre pripad aby sme
| |
| − | // v pripade chybneho pouzitia tohto poitera boli vcas varovani
| |
| − |
| |
| − | // Hlavny cyklus programu
| |
| − | do{
| |
| − | printf("\n Vyber kriterium triedenia. \n"
| |
| − | " Meno 1\n"
| |
| − | " Priezvisko 2\n"
| |
| − | " Rok narodenia 3\n\n"
| |
| − | " Pre ukoncenie programu 0\n\n"
| |
| − | " Volba: ");
| |
| − | scanf("%d",&volba);
| |
| − |
| |
| − | switch(volba)
| |
| − | {
| |
| − | case 0: break;
| |
| − | case 1: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajMENO); break;
| |
| − | // namiesto sizeof(ZAMESTNANEC) mozeme pouzit sizeof(pole[0])
| |
| − | case 2: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajPRIEZV); break;
| |
| − | case 3: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajROK); break;
| |
| − | default:
| |
| − | printf("\n Neocakavany vstup. Program bude ukonceny.\n");
| |
| − | volba=0;
| |
| − | }
| |
| − | if(volba) // Vypisanie utriedeneho pola na monitor
| |
| − | {
| |
| − | clrscr(); //vycistime si obrazovku
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | printf(" ZAMESTNANEC ROK NARODENIA\n");
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | for(i=0; i<Pocet_zamestnancov; i++)
| |
| − | vypisZAMESTNANEC(pole[i]);
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | }
| |
| − | }while(volba);
| |
| − |
| |
| − | system("pause");
| |
| − | return 0;
| |
| − | }
| |
| − |
| |
| − | // Definicie pouzivanych funkcii:
| |
| − | //---------------------------------------------------------------------------
| |
| − | int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
| |
| − | {
| |
| − | int a;
| |
| − | a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
| |
| − | if(a == EOF) a = 0;
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | void vypisZAMESTNANEC(ZAMESTNANEC V)
| |
| − | {
| |
| − | printf(" %-20s %-20s %d\n", V.meno, V.priezvisko, V.rok_narodenia);
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajROK(const void *V1, const void *V2)
| |
| − | {
| |
| − | return ((ZAMESTNANEC*)V1)->rok_narodenia - ((ZAMESTNANEC*)V2)->rok_narodenia;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajMENO(const void *V1, const void *V2)
| |
| − | {
| |
| − | return strcmp(((ZAMESTNANEC*)V1)->meno, ((ZAMESTNANEC*)V2)->meno);
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajPRIEZV(const void *V1, const void *V2)
| |
| − | {
| |
| − | return strcmp(((ZAMESTNANEC*)V1)->priezvisko, ((ZAMESTNANEC*)V2)->priezvisko);
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − | ===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:
| |
| − | <source lang="c" >
| |
| − | struct ZAMESTNANEC {
| |
| − | char *meno;
| |
| − | char *priezvisko;
| |
| − | int rok_narodenia;
| |
| − | };
| |
| − | </source>
| |
| − | 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== | | ==Triedenie poľa ukazovateľov alebo Triedime štruktúry efektívne== |
| | ===Zadanie=== | | ===Zadanie=== |
| Riadok 199: |
Riadok 23: |
| | ===Metodický komentár=== | | ===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. | | :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 [http://www.cplusplus.com/reference/clibrary/cstdlib/malloc/ malloc] definovaná v knižnici stdlib.h:
| |
| − | <source lang="c">
| |
| − | void * malloc ( size_t size );
| |
| − | </source>
| |
| − | ;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 [http://msdn.microsoft.com/en-us/library/kewsb8ba%28VS.71%29.aspx new] je definovaný v knižnici iostream.h nasledovne:
| |
| − | <source lang="c">
| |
| − | [::] new [placement] new-type-name [new-initializer]
| |
| − | [::] new [placement] ( type-name ) [new-initializer]
| |
| − | </source>
| |
| − | 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:
| |
| − | <source lang="c">
| |
| − | int * i_arr;
| |
| − | try {
| |
| − | i_arr = new int[0x3fffffff];
| |
| − | }
| |
| − | catch(...) {
| |
| − | cout<<"Vynimka: nedostatok pamati pre alokaciu";
| |
| − | }
| |
| − | </source>
| |
| − | ===Možné riešenie v jazyku C===
| |
| − | <source lang="c" line >
| |
| − | #include<stdio.h>
| |
| − | #include<stdlib.h>
| |
| − | #include<conio.h>
| |
| − | #include<string.h>
| |
| − |
| |
| − | #define NAZOV_SUBORU "data.txt"
| |
| − | #define KROK_REALOKACIE 100
| |
| − |
| |
| − | // Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
| |
| − | struct ZAMESTNANEC {
| |
| − | char meno[21];
| |
| − | char priezvisko[21];
| |
| − | int rok_narodenia;
| |
| − | };
| |
| − |
| |
| − | // Uplne funkcne prototypy pouzivanych funkcii:
| |
| − |
| |
| − | // Nacitanie jedineho zamestnanca zo suboru
| |
| − | int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V);
| |
| − |
| |
| − | // Vypisanie jedineho zamestnanca na monitor
| |
| − | void vypisZAMESTNANEC(ZAMESTNANEC V);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla roku narodenia
| |
| − | int porovnajROK(const void *V1, const void *V2);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla mena
| |
| − | int porovnajMENO(const void *V1, const void *V2);
| |
| − |
| |
| − | // Porovnanie dvoch zamestnancov podla priezviska
| |
| − | int porovnajPRIEZV(const void *V1, const void *V2);
| |
| − |
| |
| − | // Porovnanie najprv podla priezviska potom podla mena
| |
| − | int porovnajPRIEZV_MENO(const void *V1, const void *V2);
| |
| − | int porovnajMENO_PRIEZV(const void *V1, const void *V2); // podobne dalej...
| |
| − | int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2);
| |
| − | int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2);
| |
| − | int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2);
| |
| − | int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2);
| |
| − |
| |
| − | // Hlavna funkcia programu:
| |
| − | int main(int argc, char* argv[])
| |
| − | {
| |
| − | // Pozor, zmena v porovnani s predchadzajucim riesenim!
| |
| − | ZAMESTNANEC **pole;
| |
| − |
| |
| − | // Pocet nacitanych zamestnancov
| |
| − | int Pocet_zamestnancov = 0;
| |
| − | // Prednastaveny maximalny pocet zamestnancov
| |
| − | int maxPocet_zamestnancov = 100;
| |
| − | // kriterium triedenia / ukoncenia programu
| |
| − | int volba;
| |
| − | // pointer na zdrojovy subor, z ktoreho budeme nacitavat zamestnancov
| |
| − | FILE *fr;
| |
| − | // pointer na funkciu, pomocou ktorej budeme triedit
| |
| − | int (*sortFun)(const void *,const void *);
| |
| − | int i; // pomocna premenna
| |
| − |
| |
| − | // Otvorenie zdrojoveho suboru v rezime "read"
| |
| − | if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
| |
| − | {
| |
| − | printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
| |
| − | system("pause");
| |
| − | exit(1);
| |
| − | }
| |
| − |
| |
| − | // Prvotna alokacia pamate pre pole pointrov na pomenovanu strukturu ZAMESTNANEC
| |
| − | if((pole=(ZAMESTNANEC**)malloc(maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
| |
| − | {
| |
| − | printf("Nedostatok pamete!\n");
| |
| − | system("pause");
| |
| − | exit(1);
| |
| − | }
| |
| − | //**********************************************************************
| |
| − | //* Pomocou operatora new sa kod na riadkoch 68 az 73 zapise nasledovne
| |
| − | //* try{
| |
| − | //* pole=new (ZAMESTNANEC*)[maxPocet_zamestnancov];
| |
| − | //* }
| |
| − | //* catch(...)
| |
| − | //* { cout<<"Nedostatok pamete";
| |
| − | //* exit(1);
| |
| − | //* }
| |
| − | //*********************************************************************
| |
| − |
| |
| − | // Najprv si musime alokovat priestor pre prveho zamestnanca
| |
| − | // (aby data, ktore nacitame sme mali kam ulozit)
| |
| − | if((pole[0]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
| |
| − | {
| |
| − | printf("\n Nedostatok pamete...\n");
| |
| − | exit(1);
| |
| − | }
| |
| − |
| |
| − | //**********************************************************************
| |
| − | //* Pomocou operatora new sa kod na riadkoch 87 az 91 zapise nasledovne
| |
| − | //* try{
| |
| − | //* pole[0]=new ZAMESTNANEC;
| |
| − | //* }
| |
| − | //* catch(...)
| |
| − | //* { cout<<"Nedostatok pamete";
| |
| − | //* exit(1);
| |
| − | //* }
| |
| − | //*********************************************************************
| |
| − | // Nacitanie vsetkych zamestnancov zo suboru
| |
| − | for(i=0; nacitajZAMESTNANEC(fr,pole[i]); i++)
| |
| − | {
| |
| − | //Alokujeme si miesto pre dalsieho zamestnanca:
| |
| − | if((pole[i+1]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
| |
| − | {
| |
| − | printf("\n Nedostatok pamete pre pridanie dalsieho zamestnanca...\n");
| |
| − | system("pause");
| |
| − | exit(1);
| |
| − | }
| |
| − |
| |
| − | // V pripade potreby realokujeme pole pinterov: (Tato situacia nastane
| |
| − | // ak pocet zamestnancov v subore je vacsi ako aktualne nastavna hodnota
| |
| − | // premennej maxPocet_zamestnancov)
| |
| − | if(i == maxPocet_zamestnancov-2)
| |
| − | {
| |
| − | maxPocet_zamestnancov += KROK_REALOKACIE; // Zvysime maximalny pocet zamestnancov
| |
| − | //printf("...realokujem...");
| |
| − | if((pole=(ZAMESTNANEC**)realloc(pole,maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
| |
| − | {
| |
| − | printf(" Nedostatok pamate pre realokaciu pola pointerov!\n");
| |
| − | system("pause");
| |
| − | exit(1);
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | Pocet_zamestnancov = i;
| |
| − | fclose(fr); // zatvorenie suboru, data uz su nacitane..
| |
| − | fr = NULL; // zaroven nastavime na NULL pre pripad aby
| |
| − | // sme v pripade chybneho pouzitia tohto poitera boli vcas varovani
| |
| − |
| |
| − | // Hlavny cyklus programu
| |
| − | do{
| |
| − | printf("\n Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)\n"
| |
| − | " Meno, Priezvisko, Rok 1\n"
| |
| − | " Priezvisko, Meno, Rok 2\n"
| |
| − | " Rok, Meno, Priezvisko 3\n"
| |
| − | " Rok, Priezvisko, Meno 4\n\n"
| |
| − | " Pre ukoncenie programu 0\n\n"
| |
| − | " Volba: ");
| |
| − | scanf("%d",&volba);
| |
| − |
| |
| − | switch(volba)
| |
| − | {
| |
| − | case 0: break;
| |
| − | case 1: sortFun = porovnajMENO_PRIEZV_ROK; break;
| |
| − | case 2: sortFun = porovnajPRIEZV_MENO_ROK; break;
| |
| − | case 3: sortFun = porovnajROK_MENO_PRIEZV; break;
| |
| − | case 4: sortFun = porovnajROK_PRIEZV_MENO; break;
| |
| − | default:
| |
| − | printf("\n Neocakavany vstup. Program bude ukonceny.\n");
| |
| − | volba=0;
| |
| − | }
| |
| − | if(volba) // Vypisanie utriedeneho pola na monitor
| |
| − | {
| |
| − | // Utriedenie zamestnancov:
| |
| − | qsort((void*)pole,Pocet_zamestnancov,sizeof(pole[0]),sortFun);
| |
| − |
| |
| − | clrscr(); //vycistime si obrazovku
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | printf(" ZAMESTNANEC ROK NARODENIA\n");
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | for(i=0;i<Pocet_zamestnancov;i++)
| |
| − | vypisZAMESTNANEC(*pole[i]);
| |
| − | printf("--------------------------------------------------------\n");
| |
| − | }
| |
| − | }while(volba);
| |
| − |
| |
| − | // Na zaver nasleduje uvolnenie pamate, ktoru sme alokovali.
| |
| − | // Najprv musime uvolnit pamet, ktoru sme alokovali pre jednotlivych zamestnancov.
| |
| − |
| |
| − | //Pocet alokovanych zamestnancov je o jednehoneho viac...
| |
| − | for(i=0; i<skutocnyPocet_zamestnancov + 1;i++)
| |
| − | free(pole[i]);
| |
| − |
| |
| − | //Potom uvolnime pamat alokovanu pre pointre
| |
| − | free(pole);
| |
| − | poleStud = NULL; // a nastavime na NULL (nie je nevyhnutne potrebne)
| |
| − |
| |
| − | system("pause");
| |
| − | return 0;
| |
| − | }
| |
| − |
| |
| − | // Definicie pouzivanych funkcii:
| |
| − | //---------------------------------------------------------------------------
| |
| − | int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
| |
| − | {
| |
| − | int a;
| |
| − | a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
| |
| − | if(a == EOF) a = 0;
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | void vypisZAMESTNANEC(ZAMESTNANEC V)
| |
| − | {
| |
| − | printf(" %-20s %-20s %d\n", V.meno, V.priezvisko, V.rok_narodenia);
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajROK(const void *V1, const void *V2)
| |
| − | {
| |
| − | return (*(ZAMESTNANEC**)V1)->rok_narodenia - (*(ZAMESTNANEC**)V2)->rok_narodenia;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajMENO(const void *V1, const void *V2)
| |
| − | {
| |
| − | return strcmp((*(ZAMESTNANEC**)V1)->meno, (*(ZAMESTNANEC**)V2)->meno);
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajPRIEZV(const void *V1, const void *V2)
| |
| − | {
| |
| − | return strcmp((*(ZAMESTNANEC**)V1)->priezvisko, (*(ZAMESTNANEC**)V2)->priezvisko);
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajPRIEZV_MENO(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajPRIEZV(V1, V2);
| |
| − | if(a == 0) a = porovnajMENO(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajMENO_PRIEZV(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajMENO(V1, V2);
| |
| − | if(a == 0) a = porovnajPRIEZV(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajMENO_PRIEZV(V1, V2);
| |
| − | if(a == 0) a = porovnajROK(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajPRIEZV_MENO(V1, V2);
| |
| − | if(a == 0) a = porovnajROK(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajROK(V1, V2);
| |
| − | if(a == 0) a = porovnajPRIEZV_MENO(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | //---------------------------------------------------------------------------
| |
| − | int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2)
| |
| − | {
| |
| − | int a = porovnajROK(V1, V2);
| |
| − | if(a == 0) a = porovnajMENO_PRIEZV(V1, V2);
| |
| − | return a;
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − |
| |
| − | ===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.
| |
| − | <source lang="c">
| |
| − | 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);
| |
| − | }
| |
| − | </source>
| |
| | | | |
| − | 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:
| + | Viac na [[Triedenie poľa smerníkov (riešené príklady)]] |
| − | <source lang="c">
| |
| − | 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");
| |
| − | }
| |
| − | </source>
| |
| − | 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:
| |
| − | <source lang="c">
| |
| − | vypisZAMESTNANCOV(stdout,pole,Pocet_zamestnancov);
| |
| − | </source>
| |
