{{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í |
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);
++.
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.
++++ 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;
}
++++
==== Definice složeného typu struct ====
++++ 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 |
{{: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ř.|
#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]);
++++
- 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
++++
==== 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 |
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;
}
++++
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''.
==== 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|
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 ''''.
++++ 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"''.
/*
==== Pointerová aritmetika ====
++++ Příklady na ukazatelovou aritmetiku |
- Určete výsledek a ověřte programem:
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);
++++
==== 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]].