B-PROG2 K štruktúram

K štruktúram

Dátový typ

Jazyk C je typový, a teda každá premenná musí mať určitý dátový typ. Čím je charakterizovaný dátový typ?

určuje, koľko miesta premenná zaberie v pamäti
- napr. typ int zaberá viac miesta ako typ char
- na zistenie potrebného miesta slúži operátor sizeof
určuje, ako interpretujeme dáta patriace do tejto premennej
- u celých čísel rozsah/znamienko: int, long int, unsigned short int, char (pozn.: aj char je v C-čku celočíselný typ)
- u desatinných čísel aj presnosť: float vs. double
- u smerníka typ údaju na adrese uloženej v smerníkovej premennej: int*, int**, void* (pozn.: posledný je typ beztypový smerník. Premenná tohto typu má typ void*, ale miesto, kam ukazuje je bez určeného typu, t.j. ľubovoľné!)
určuje, aké operácie sú platné pre premenné daného typ
- dá sa čítať hodnota premennej, a zapisovať nová hodnota (u premennej konštantného typu (napr. const int) sa hodnota po prvom zápise nedá zmeniť)
- nad celočíselnými premennými sa dajú prevádzať aritmetické, bitové a logické operácie
- pre float/double sú povolené aritmetické a logické operácie (ale nie napr. operácia %)
- pre typové smerníky sa vykonáva smerníková aritmetika (pripočítanie celého čísla ako posun adresy, rozdiel 2 smerníkov)

Špecifickým údajovým typom je zložený údajový typ – štruktúra, viď napr.: (http://en.wikipedia.org/wiki/Struct_%28C_programming_language%29)

Štruktúrový typ podporuje priradenie (čítanie/zápis), ale nepodporuje aritmetické a logické operácie. Ak potrebujeme operácie, musíme si pripraviť v jazyku C vlastné funkcie.

Príklad zo skúšky

Napíšte deklaráciu zloženého dátového typu s názvom Point s 2 zložkami x, y (celé čísla).

Použijeme klasickú deklaráciu s typedef, aby sme nemuseli všade ďalej písať struct:

typedef struct _point {
  int x, y;
} Point;

typedef struct _point {

int x, y;

} Point;

Napíšte funkciu, ktorej vstupom sú 2 body (t.j. typ je novo zadefinovaný Point), a výstupom je ich (Euklidovská) vzdialenosť (t.j. VZOREC, kde x1, y1 a x2, y2 sú príslušné súradnice bodov).

Akonáhle nový typ zadefinujeme, už ho môžeme používať na deklaráciu premenných úplne klasicky. Funkcia dostane 2 body (povedzme A, a vyrobí desatinné číslo (odmocnina vo vzorci!). Kým v matematickom vzorci vystupujú x1, y1 a x2,y2, pre nás to budú x-ová a y-ová zložka bodov A, a B. Pri umocňovaní na druhú spravíme optimalizáciu s medzipremennou. Výsledok je:

double dist( Point A, Point B ) {
   double dx = A.x - B.x; //t.j. x1 - x2 
   double dy = A.y - B.y; //t.j. y1 - y2 
   return sqrt(dx*dx + dy*dy);    //Pytagorova veta
}

double dist( Point A, Point B ) {

double dx = A.x - B.x; //t.j. x1 - x2

double dy = A.y - B.y; //t.j. y1 - y2

return sqrt(dx*dx + dy*dy); //Pytagorova veta

}

Všimnite si prototyp:

double dist( Point A, Point B );

1	double dist( Point A, Point B );

Programátor, čo chce funkciu použiť, vie, že musí pripraviť 2 body a ona mu vypočíta ich vzdialenosť. Nemusí pracovať so 4 vstupmi, ale iba s dvomi. Nemusí sa zaoberať, v akom poradí sú súradnice, použiť (x1, x2, y1, y2) alebo radšej (x1, y1, x2, y2), alebo na preskáčku? Na otestovanie stačí:

int main() { 
  Point pt1 = {1, 3}, pt2 = {5, 7};
  printf("Dist = %lf\n", dist(pt1, pt2));
}

int main() {

Point pt1 = {1, 3}, pt2 = {5, 7};

printf("Dist = %lf\n", dist(pt1, pt2));

}

Keby sme chceli použiť 3D priestor, stačí ľahká úprava:

typedef struct _point3d {
  int x, y, z;
} Point3D;

double dist3d( Point3D A, Point3D B ) {
   double dx = A.x - B.x; //t.j. x1 - x2 
   double dy = A.y - B.y; //t.j. y1 - y2 
   double dz = A.z - B.z; //t.j. z1 - z2 

   return sqrt(dx*dx + dy*dy + dz*dz);
}

int main() { 
  Point3D pt1 = {1, 3, 0}, pt2 = {5, 7, 2};
  printf("Dist = %lf\n", dist(pt1, pt2));
}

typedef struct _point3d {

int x, y, z;

} Point3D;

double dist3d( Point3D A, Point3D B ) {

double dx = A.x - B.x; //t.j. x1 - x2

double dy = A.y - B.y; //t.j. y1 - y2

double dz = A.z - B.z; //t.j. z1 - z2

return sqrt(dx*dx + dy*dy + dz*dz);

}

int main() {

Point3D pt1 = {1, 3, 0}, pt2 = {5, 7, 2};

printf("Dist = %lf\n", dist(pt1, pt2));

}

Napíšte deklaráciu zloženého dátového typu Triangle s 3 zložkami A,B,C (typu Point).

Toto je vlastne príklad na vnorenú štruktúru. Využíva sa fakt, že v štruktúre môže byť ľubovoľný počet zložiek ľubovoľných typov. U nás sú to tri body, t.j.

typedef struct _triangle {
  Point A, B, C;
} Triangle;

typedef struct _triangle {

Point A, B, C;

} Triangle;

Napíšte funkciu, ktorej vstupom je trojuholník (typ Triangle) a výstupom je jeho obvod.

Tu využijeme extrémne zjednodušenie poskytnuté štruktúrami. Namiesto uvažovania so 6 vstupmi (v 2D priestore: po 2 súradnice 3 bodov, v 3D priestore by to bolo až 9 vstupov), stačí uvažovať jediný vstup – celý trojuholník. Výstupom je obvod, a teda desatinné číslo. Obvod je súčet dĺžok strán. Dĺžku strany ale vieme jednoducho vypočítať pomocou funkcie dist. Riešenie je teda:

double perimeter( Triangle t ) {
   return dist(t.A, t.B) + dist(t.B, t.C) + dist(t.C, t.A);
}

int main() { 
  Triangle t1 = {{0, 0}, {0,1}, {1,0}};
  printf("Obvod = %lf\n", perimeter(t1));
}

double perimeter( Triangle t ) {

return dist(t.A, t.B) + dist(t.B, t.C) + dist(t.C, t.A);

}

int main() {

Triangle t1 = {{0, 0}, {0,1}, {1,0}};

printf("Obvod = %lf\n", perimeter(t1));

}

Úprava na 3D priestor je ešte triviálnejšia ako v predošlom prípade:

typedef struct _triangle3d {
  Point A, B, C;
} Triangle3D;

double perimeter3d( Triangle3D t ) {
   return dist3d(t.A, t.B) + dist3d(t.B, t.C) + dist3d(t.C, t.A);
}

int main() { 
  Triangle3D t1 = {{0, 0, 0}, {0,1,0}, {1,0,1}};
  printf("Obvod = %lf\n", perimeter3d(t1));
}

typedef struct _triangle3d {

Point A, B, C;

} Triangle3D;

double perimeter3d( Triangle3D t ) {

return dist3d(t.A, t.B) + dist3d(t.B, t.C) + dist3d(t.C, t.A);

}

int main() {

Triangle3D t1 = {{0, 0, 0}, {0,1,0}, {1,0,1}};

printf("Obvod = %lf\n", perimeter3d(t1));

}

Úloha: (POZOR, MATEMATIKA ) Napíšte funkciu, ktorej vstupom sú dva trojuholníky (2D). Funkcia zistí, či sa prekrývajú (vráti pravda/nepravda).

Zložitejší príklad

Štruktúry sa dajú využívať podobne ako základné typy na vytvorenie poľa, štruktúry vieme vracať z funkcie, dajú sa používať smerníky na štruktúry. Pozrime sa na nasledujúci príklad: Vstupom funkcie je pole trojuholníkov. Funkcia vráti trojuholník s najväčším obvodom.

Napíšme si najprv klasickú funkciu na nájdenie najväčšieho čísla v poli:

//PRE: pocet > 0
int maximum( int pole[], int pocet )
{
  int i, max;   

  max = pole[0];
  for (i = 1; i < pocet; i++)
  {
     if (pole[i] > max)
        max = pole[i];
  }
  
  return max;
}

//PRE: pocet > 0

int maximum( int pole[], int pocet )

{

int i, max;

max = pole[0];

for (i = 1; i < pocet; i++)

{

if (pole[i] > max)

max = pole[i];

}

return max;

}

Čo treba zmeniť? Pracujeme nie s číslami (int), ale s trojuholníkmi (Triangle):

//PRE: pocet > 0
Triangle maximum( Triangle pole[], int pocet )
{
  int i;        //i je index, zostane cele cislo
  Triangle max; //max je ale trojuholnik  

  max = pole[0];
  for (i = 1; i < pocet; i++)
  {
     if (pole[i] > max)
        max = pole[i];
  }
  
  return max;
}

//PRE: pocet > 0

Triangle maximum( Triangle pole[], int pocet )

{

int i; //i je index, zostane cele cislo

Triangle max; //max je ale trojuholnik

max = pole[0];

for (i = 1; i < pocet; i++)

{

if (pole[i] > max)

max = pole[i];

}

return max;

}

Horeuvedený kód by sa ale nemal dať skompilovať, keďže trojuholníky nevieme porovnávať operátorom >. Nemáme však porovnávať trojuholníky, ale ich obvod, čiže píšeme:

//PRE: pocet > 0
Triangle maximum( Triangle pole[], int pocet )
{
  int i;        //i je index, zostane cele cislo
  Triangle max; //max je ale trojuholnik  

  max = pole[0];
  for (i = 1; i < pocet; i++)
  {
     if (perimeter(pole[i]) > perimeter(max))
        max = pole[i];
  }
  
  return max;
}

//PRE: pocet > 0

Triangle maximum( Triangle pole[], int pocet )

{

int i; //i je index, zostane cele cislo

Triangle max; //max je ale trojuholnik

max = pole[0];

for (i = 1; i < pocet; i++)

{

if (perimeter(pole[i]) > perimeter(max))

max = pole[i];

}

return max;

}

Nevýhoda tohto riešenia je, že vždy nanovo počítame obvod trojuholníka max. Ak nám záleží na efektivite, kód vieme ďalej upraviť pomocou pomocných premenných:

//PRE: pocet > 0
Triangle maximum( Triangle pole[], int pocet )
{
  int i;        //i je index, zostane cele cislo
  Triangle max; //max je ale trojuholnik
  double p, pmax;  //pomocne premenne - obvod aktualny a zapamatany maximalny

  max  = pole[0];
  pmax = perimeter(max);
  for (i = 1; i < pocet; i++)
  {
     p = perimeter(pole[i]);
     if (p > pmax) {
        max = pole[i];
        pmax = p; 
     }
  }
  
  return max;
}

//PRE: pocet > 0

Triangle maximum( Triangle pole[], int pocet )

{

int i; //i je index, zostane cele cislo

Triangle max; //max je ale trojuholnik

double p, pmax; //pomocne premenne - obvod aktualny a zapamatany maximalny

max = pole[0];

pmax = perimeter(max);

for (i = 1; i < pocet; i++)

{

p = perimeter(pole[i]);

if (p > pmax) {

max = pole[i];

pmax = p;

}

return max;

}

Posledný zdroj neefektivity spočíva v príkaze max = pole[i]. Týmto príkazom sa skopíruje 6 súradníc z trojuholníka pole[i] do premennej max. Namiesto toho si nám stačí zapamätať index v poli (alebo pointer!):

//PRE: pocet > 0
Triangle maximum( Triangle pole[], int pocet )
{
  int i;           //i je index, zostane cele cislo
  int imax;        //imax je index trojuholnik s najvacsim (doteraz) obvodom
  double p, pmax;  //pomocne premenne - obvod aktualny a zapamatany maximalny

  imax  = 0;
  pmax = perimeter(pole[imax]);
  for (i = 1; i < pocet; i++)
  {
     p = perimeter(pole[i]);
     if (p > pmax) {
        imax = i;
        pmax = p; 
     }
  }
  
  return pole[imax];
}

//PRE: pocet > 0

Triangle maximum( Triangle pole[], int pocet )

{

int i; //i je index, zostane cele cislo

int imax; //imax je index trojuholnik s najvacsim (doteraz) obvodom

double p, pmax; //pomocne premenne - obvod aktualny a zapamatany maximalny

imax = 0;

pmax = perimeter(pole[imax]);

for (i = 1; i < pocet; i++)

{

p = perimeter(pole[i]);

if (p > pmax) {

imax = i;

pmax = p;

}

return pole[imax];

}