7 - Dynamická alokace a struktury

• pro vyučující

1. Použití struktury.
2. Pointer na funkce.

• Dokončení cvičení - 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í.

• 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 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ů.

• Předpokládáme, že máme implementované funkce pro načtení jednoho řádku, případně více řádků a jejich tisk dle rozhraní

  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);

  .

Příklad implementace free_lines()

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;
}

Proměnnou s počtem řádků a polem s řádky

size_t n = 0;
char ** lines = read_lines(fd, &n, &ret);

nahradíme

složeným typem struct

typedef struct lines {
   size_t n;
   char **lines;
} lines_s;
struct lines* read_lines(FILE *fd, int *error);

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ř.

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;
}

Funkci použijeme

např

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;
}

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

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;
}

• a free_lines() na

  void free_lines(struct lines **lines);

např. jako

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;
   }
}

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

• 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í.

1. Implementujte tři funkce init, print, permute,

např.

#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]);

1. 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á

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");
 
}

Ve funkci permute() můžeme inicializovat generátor pseudonáhodných čísel pevných číslem, nebo aktuálním časem time().

např.

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;
   }
}

Příklad hlavní funkce main

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);
}

Příklad výstupu s definováním délky sekvence při kompilaci

clang -DMAX_NUM=5 perm.c -o perm && ./perm
0
1
2
3
4
Randomized array
3
0
4
2
1

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

void init(size_t n, size_t a[n]);
void permute(size_t n, size_t a[n]);

Například ve funkci print_lines_rand()

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;
}

Alternativně můžeme pole náhodných čísel alokovat dynamicky

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;
}

• 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

int (*print_l)(struct lines *) = print_lines; //pointer to a function

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

   if (argc > 2 && strcmp(argv[2], "rand") == 0) {
      print_l = print_lines_rand; // print lines in random order
   }

Volání funkce zajistíme přes ukazatel

   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;
   }

Program můžeme dále rozšířit o výpis chyby v případně, že druhý argument nemá hodnotu “rand”.

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

1. Napište funkci, která formátovaně vypíše obecné pole reálných čísel.
2. Napište funkci, která vypočte směrodatnou odchylku z prvků zadaného pole.
3. 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.
4. Společně s cvičícím si předveďte použití Valgrindu pro diagnostiku přístupů do paměti a správné alokace.
5. 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!
6. 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.
7. 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!
8. Vždy kontrolujte program na přístup do paměti a alokaci nástrojem valgrind.