Juraj na 20:28, 16. august 2010

2010-08-16T20:28:21Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Skripta programovanie (zbierka úloh)}} ==Triedenie poľa štruktúr== ===Zadani…“

2010-03-08T14:10:53Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Skripta programovanie (zbierka úloh)}} ==Triedenie poľa štruktúr== ===Zadani…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Skripta programovanie (zbierka úloh)}}

==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 (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
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.

← Staršia verzia		Verzia zo dňa a času 20:28, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:jazyk C]]~~
	{{Skripta programovanie (zbierka úloh)}}		{{Skripta programovanie (zbierka úloh)}}

Triedenie poľa štruktúr (riešené príklady) - História úprav

Juraj na 20:28, 16. august 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Skripta programovanie (zbierka úloh)}} ==Triedenie poľa štruktúr== ===Zadani…“