7 - Dynamická alokace a struktury
Cíle cvičení
Použití struktury.
Pointer na funkce.
Úkoly
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
'.
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.
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
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
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 <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”
.
Další úlohy k procvičení
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
valgrind.