{{indexmenu_n>7}}
====== 7 - Dynamická alokace a struktury ======

  * [[courses:b0b36prp:internal:tutorialinstruction:07|pro vyučující]]



===== Cíle cvičení =====
  - Použití struktury.
  - Pointer na funkce.

===== Úkoly =====

  * Dokončení cvičení - [[courses:b0b36prp:labs:lab06|6 - Dynamická alokace a textové soubory]].
  * Definice struktury obsahujicí počet načtených řádků a načtené řádky.
  * Implementace výpisu řádků v náhodném pořadí.



==== Výpis načtených řádků v opačném pořadí ====

  * Implementujte program, který načte vstupní textový soubor, který následně vypíše v opačném pořadí načtených řádků.
  * Nejdříve implementujeme načtení řádků s dynamickou alokací. Předpokládáme, že vstup má řádky zakončeny znakem '''\n'''.
    * V případně chybějícího znaku ''\n'' načteme pouze jeden řádek, nebo reportujeme chybu vstupu.
  * Program vhodně dekomponujeme a uvažujte tři chybové stavy.
      * 100 - Chyba načtení.
      * 101 - Chyba alokace dynamické paměti.
      * 102 - Chyba výstupu. //Uvažujte, že tisk na standardní výstup může selhat//. 
  * V [[courses:b0b36prp:labs:lab06|lab06]] jsme datovou strukturu uvažovali jako dynamicky alokované pole ukazatelů na textové řetězce reprezentující postupně načtené řádky.
  * Program z předchozího cvičení rozšíříme o použítí složeného typu ''struct'', kterým nahradíme více argumentů, jedním argumentem.
      * Budeme uvažovat možnou dynamickou alokaci proměnné složeného typu. Proto budeme předávat proměnnou typu ukazatel na naší datovou strukturu řádků.


==== Výchozí (předpokládané) řešení ze 6. cvičení ====

  * Předpokládáme, že máme implementované funkce pro načtení jednoho řádku, případně více řádků a jejich tisk ++ dle rozhraní  |
<code c>
enum {
   ERROR_OK = EXIT_SUCCESS,
   ERROR_READ = 100,
   ERROR_MEM = 101,
   ERROR_OUT = 102,
};

// from stdin reads one line (ends \n); returns pointer to read array
char* read(FILE *fd, int *error);
char **read_lines(FILE *fd, size_t *n, int *error);

int print(char *line);
int print_lines(size_t n, char **lines);
void free_lines(size_t n, char ***lines);

void print_error(int error);
</code> 
++.

<note tip>Ve funkci ''free_lines'' nastavujeme hodnotu ukazatele alokované paměti na prokazatelně neplatnou adresu ''NULL'', proto předáváme ukazatel na datový typ proměnné, který je v našem případě ukazatel na ukazatel na char, proto tři hvězdičky.</note>

++++ Příklad implementace free_lines() |
<code c>
void free_lines(size_t n, char ***str)
{
   if (str && *str) {
      for (int i = 0; i < n; ++i) {
         free((*str)[i]);
      }
      free(*str);
   }
   *str = NULL;
}
</code>
++++

==== Definice složeného typu struct ====

++++ Proměnnou s počtem řádků a polem s řádky |
<code c>
size_t n = 0;
char ** lines = read_lines(fd, &n, &ret);
</code>
++++
nahradíme ++++složeným typem  struct |
<code c>
typedef struct lines {
   size_t n;
   char **lines;
} lines_s;
struct lines* read_lines(FILE *fd, int *error);
</code>
++++

Složený typ alokujeme ve funkci ''read_lines()'', nicméně z důvodu dynamické alokace ''lines->lines'' implementujeme alokaci složeného typu v samostatné funkce ''allocate_lines()'' 
++++ např. |
<code c>
static struct lines* allocate_lines(size_t sz)
{
   struct lines *lines = malloc(sizeof(struct lines));
   if (lines) {
      lines->n = 0;
      lines->lines = malloc(sizeof(char*) * sz);
      if (!lines->lines) {
	 free(lines); // allocation fail 
	 lines = NULL;
      }
   }
   return lines;
}
</code>
++++

Funkci použijeme 
++++ např |
<code c>
static struct lines* allocate_lines(size_t sz)
{
   struct lines *lines = malloc(sizeof(struct lines));
   if (lines) {
      lines->n = 0;
      lines->lines = malloc(sizeof(char*) * sz);
      if (!lines->lines) {
	 free(lines); // allocation fail 
	 lines = NULL;
      }
   }
   return lines;
}

</code>
++++


Kromě funkce ''read_lines()'', ve které alokujeme proměnnou složeného typu ''struct linies'' modifikujeme 

  * ''print_lines()'' na ''int print_lines(struct lines *lines);'' 
++++ např. na |
<code c>
int print_lines(struct lines *lines)
{
   int ret = ERROR_OK;
   // Since i is of the size_t type, we might have to avoid "underflow" to negative values. Note that over/underflow of unsigned integers is defined in C/C++; however, for educative purposes, think about it! 
   if (lines)  { // we protect access to lines->n 
      for (size_t i = lines->n; ret == ERROR_OK && i > 0; --i) {
         ret = print(lines->lines[i-1]); //we rely on correct data structure lines
      }
   }
   return ret;
}
</code>
++++

  * a ''free_lines()'' na <code c>void free_lines(struct lines **lines);</code>
++++ např. jako |
<code c>
void free_lines(struct lines **lines)
{
   if (lines && *lines) {
      for (size_t i = 0; (*lines)->lines && i < (*lines)->n; ++i) {
         if ((*lines)->lines[i]) {
            free((*lines)->lines[i]);
         }
      }
      free((*lines)->lines);
      free(*lines);
      *lines = NULL;
   }
}
</code>
++++


++++ Příklad možných změn vůči řešení lab06 |

{{:courses:b0b36prp:labs:lab07-init-diff1.png?800|}}
{{:courses:b0b36prp:labs:lab07-init-diff2.png?800|}}
++++
==== Vytvoření náhodné permutace ====

  * Program rozšiřte o výpis řádků v náhodném pořadí.
  * Nejdříve si vyzkoušejte implementaci vytvoření permutace posloupnosti čísel 0 až n, viz ''man 3 rand''.
  * Vytvoření permutace následně integrujte do programu.
  * Můžete dále přidat argument programu (parametr z příkazové řádky), který bude modifikovat chování.



=== Náhodná permutace ===

  - Implementujte tři funkce ''init'', ''print'', ''permute'', 
++++ např.|
<code c>
#ifndef MAX_NUM
#define MAX_NUM 10
#endif

#define SEED 42

void init(unsigned int n, unsigned int a[n]);
void print(unsigned int n, unsigned int a[n]);
void permute(unsigned int n, unsigned int a[n]);
</code>
++++

  - Funkce použijte v např. v jednoúčelovém programu pro inicializaci pole celých čísel, jeho vytištění, permutování a znovu vytištění na ''stdout''.


Implementace ''init()'' a ''print()'' je relativně 
++++ přímočará |
<code c>

void init(unsigned int n, unsigned int a[n])
{
   for (unsigned int i = 0; i < n; i++) {
      a[i] = i;
   }
}

void print(unsigned int n, unsigned int a[n])
{
   for (unsigned int i = 0; i < n; i++) {
      printf("%d ", a[i]);
   }
   printf("\n");

}
</code>
++++


Ve funkci ''permute()'' můžeme inicializovat generátor pseudonáhodných čísel pevných číslem, nebo aktuálním časem ''time()''.
++++ např. |
<code c>
void permute(unsigned int n, unsigned int a[n]) 
{
   //srand(SEED);
   srand(time(NULL));
   unsigned int d = 0;
   unsigned int tmp = 0;
   for (unsigned int i = n; i > 0; i--) {
      d = rand() % i;
      // swap
      tmp = a[d];
      a[d] = a[i-1];
      a[i-1] = tmp;
   }
}
</code>
++++

++++ Příklad hlavní funkce main | 
<code c>
int main(int argc, char const *argv[])
{
   unsigned int n = MAX_NUM;
   unsigned int a[n];

   init(n, a);
   print(n, a);

   permute(n, a);

   print(n, a);
}
</code>
++++

++++ Příklad výstupu s definováním délky sekvence při kompilaci |
<code>
clang -DMAX_NUM=5 perm.c -o perm && ./perm
0
1
2
3
4
Randomized array
3
0
4
2
1
</code>
++++


==== Použití náhodné permutace ====

Vytvoření náhodné permutace využijeme k výpisu řádků v náhodném pořadí. 
Z důvodu použití typu ''size_t'' zaměníme předchozí typ ''unsigned int'' právě za ''size_t''.
++++ Použití size_t |
<code c>
void init(size_t n, size_t a[n]);
void permute(size_t n, size_t a[n]);
</code>
++++


++++ Například ve funkci print_lines_rand() |
<code c>
int print_lines_rand(struct lines *lines)
{
   int ret = ERROR_OK;
   if (lines)  { // we protect access to lines->n 
      size_t perm[lines->n];
      init(lines->n, perm);
      permute(lines->n, perm);

      for (size_t i = lines->n; ret == ERROR_OK && i > 0; --i) {
         ret = print(lines->lines[perm[i-1]]);
      }
   }
   return ret;
}
</code>
++++

++++ Alternativně můžeme pole náhodných čísel alokovat dynamicky|
<code c>
size_t* init(size_t n);
void permute(size_t n, size_t *a);

size_t* init(size_t n)
{
   size_t *a = malloc(sizeof(size_t) * n);
   if (a) {
      for (size_t i = 0; i < n; i++) {
         a[i] = i;
      }
   }
   return a;
}

void permute(size_t n, size_t *a)
{
   //srand(SEED);
   srand(time(NULL));
   size_t d = 0;
   size_t tmp = 0;
   for (size_t i = n; i > 0; --i) {
      d = rand() % i; // However, function rand() returns int!!!
                      // swap
      tmp = a[d];
      a[d] = a[i-1];
      a[i-1] = tmp;
   }
}

int print_lines_rand(struct lines *lines)
{
   int ret = ERROR_OK;
   if (lines)  { // we protect access to lines->n 
      size_t *perm = init(lines->n);
      if (!perm) {
         return ERROR_MEM;
      }
      permute(lines->n, perm);

      for (size_t i = lines->n; ret == ERROR_OK && i > 0; --i) {
         ret = print(lines->lines[perm[i-1]]);
      }
      free(perm);
   }
   return ret;
}
</code>
++++

<note important>Ve funkci ''perm()'' používáme volání ''rand()'', které vrací celé číslo v rozsahu ''int''. Fakticky pracujeme s polem a6 do velikosti ''size_t''. Striktně vzato tak progam nebude fungovat správně pokud bude řádků více než je rozsahu typu ''int''. Což můžeme detekovat, např. dle hodnoty ''INT_MAX''.</note>


==== Přepínání chování výstupu programu ====
  * Program můžeme dále rozšířit o 2. argument, který v případně hodnoty ''"rand"'' výpíše načtené řádky v náhodném pořadí.
  * Protože funkce ''print_lines()'' a ''print_lines_rand()'' mají stejnou návratovou hodnotu a argumenty, můžeme použít proměnnou ukazatel na funkci.
++++ Příklad ukazatele na funkci|
<code c>
int (*print_l)(struct lines *) = print_lines; //pointer to a function
</code>
++++

Hodnotu ukazatele na funkci nastavíme na ''print_lines_rand'', pokud je zadán druhý argument a jeho hodnota je ''"rand"'', což ověříme funkcí ''strcmp()'' z knihovny ''<string.h>''.
++++ Ověření hodnoty druhého argumentu programu |
<code c>
   if (argc > 2 && strcmp(argv[2], "rand") == 0) {
      print_l = print_lines_rand; // print lines in random order
   }
</code>
++++

++++ Volání funkce zajistíme přes ukazatel |
<code c>
   if (fd) {
      struct lines *lines = read_lines(fd, &ret);
      if (lines) {
         ret = print_l(lines); // calling function according to the value of print_l
         free_lines(&lines);
      }
      if (argc > 1) {
         fclose(fd);
      }
   } else if (argc > 1) {
      ret = ERROR_READ;
   }
</code>
++++

Program můžeme dále rozšířit o výpis chyby v případně, že druhý argument nemá hodnotu ''"rand"''.
/*
==== Pointerová aritmetika ====
++++ Příklady na ukazatelovou aritmetiku |

  - Určete výsledek a ověřte programem:
<code c>
int *up, **uup, array[] = {5, -6, 0, 8, -9, 3, 1, -4};

up = array;
uup = &up;

printf("array[1] = %d \n", array[1]);
printf("array[1] + 4 = %d \n", array[1] + 4);
printf("(array + 1)[2] = %d \n", (array + 1)[2]);

printf("*up = %d \n", *up);
printf("*up + 4 = %d \n", *up + 4);
printf("*(up + 1) = %d \n", *(up + 1));

printf("**uup = %2d \n", **uup);
printf("*(*uup + 2) = %2d \n", *(*uup + 2));
printf("**uup + 4 = %2d \n", **uup + 4);
</code>
++++


==== Teoretická příprava ====

  * [[courses:b0b36prp:tutorials:coding:c_dyn_mem|Dynamická alokace paměti v C]]
  * [[https://en.wikipedia.org/wiki/Standard_deviation|Smerodatna odchylka]]

*/

==== Další úlohy k procvičení ====

  * 2D pole a příprava na násobení matic nebo ukazatelová (pointerová) aritmetika.

  - Napište funkci, která formátovaně vypíše obecné pole reálných čísel.
  - Napište funkci, která vypočte směrodatnou odchylku z prvků zadaného pole.
  - Napište funkci, která zajistí načtení n prvků z klávesnice do pole a toto pole předá do volající funkce. Počet prvků bude zadán jako parametr funkce. 
  - Společně s cvičícím si předveďte použití Valgrindu pro diagnostiku přístupů do paměti a správné alokace.
  - Aplikujte funkce pro výpis a výpočet směrodatné odchylky na pole získané načítací funkcí. Nezapomeňte na dealokaci pole při ukončení programu!
  - Upravte předchozí funkci tak, aby byla schopna načíst libovolnou posloupnost reálných čísel do pole ukončenou vhodnou zarážkou nebo lépe pomocí EOF, umí-li to vaše konzole.
  - Upravte předchozí kód tak, aby bylo možné načíst od uživatele více datových řad a pro každou zvlášť spočítat směrodatnou odchylku. Jednoduše to zařídíte tak, že vytvoříte dvourozměrné pole, které ale může mít různé délky řádků. Nezapomeňte zajistit i dealoakaci celého pole!
  - Vždy kontrolujte program na přístup do paměti a alokaci nástrojem [[http://www.valgrind.org/|valgrind]].