ZPRO 2018

Předmět je vyučován s dotací 0+4, tzn. dvě cvičení týdně. Časy našich cvičení jsou v pondělí 9:30 (B-009) a ve středu 13:30 (T-115).

Podmínky pro zisk zápočtu

Materiály ke cvičení

1. a 2. cvičení

Důležité pojmy:

Probrané příklady:

  1. Hello, world! Nejjednodušší program v jazyce C, který na obrazovku vypíše text „Hello, world!“.

    #include <stdio.h>
    
    int main()
    {
        printf("Hello, world!\n");
        return 0;
    }
    
  2. Program demonstrující deklaraci proměnných celočíselného typu int a neceločíselného typu float, provedení operace sčítání a výpis výsledku pomocí funkce printf.

    #include <stdio.h>
    
    int main()
    {
        float a = 1.5;
        int b = 2;
        float c = a + b;
        printf("%f + %d = %f\n", a, b, c);
        return 0;
    }
    

    Proměnné jsou vypisovány pomocí speciálního symbolu pro daný datový typ (%d pro typ int a %f pro typ float). Přehled všech možností funkce printf bude ukázán později.

  3. Výpis sudých čísel. Program ukazuje využití cyklu for a podmínky.

    #include <stdio.h>
    
    int main()
    {
        for (int i = 0; i < 100; i++) {
            if (i % 2 == 0)
                printf("%d\n", i);
        }
        return 0;
    }
    

    Místo cyklu for lze ekvivalentně použít cyklus while:

    #include <stdio.h>
    
    int main()
    {
        int i = 0;
        while (i < 100) {
            if (i % 2 == 0)
                printf("%d\n", i);
            i++;
        }
        return 0;
    }
    

    Cyklus for je vhodné použít v případech, kdy předem známe počet opakování cyklu. Cyklus while je obecnější a hodí se pro situace, kdy dopředu neznáme počet opakování cyklu.

  4. Výpis prvočísel. Program ukazuje komplikovanější strukturu vnořených cyklů.

    #include <stdio.h>
    
    int main()
    {
        for (int i = 1; i < 100; i++) {
            int pocet_delitelu = 0;
    
            for (int j = 1; j <= i; j++) {
                if (i % j == 0)
                    pocet_delitelu += 1;
            }
    
            if (pocet_delitelu <= 2)
                printf("%d\n", i);
        }
        return 0;
    }
    

    O něco chytřejší verze využívá toho, že čísla j větší než polovina čísla i nemohou být děliteli čísla i. Stačí tedy procházet pouze čísla od 2 do i / 2.

    #include <stdio.h>
    
    int main()
    {
        for (int i = 1; i < 100; i++) {
            int pocet_delitelu = 1;
    
            for (int j = 2; j < i / 2; j++) {
                if (i % j == 0)
                    pocet_delitelu += 1;
            }
    
            if (pocet_delitelu == 1)
                printf("%d\n", i);
        }
        return 0;
    }
    

Stručný přehled jazyka C aneb základy jazyka C++

3. a 4. cvičení

Efektivní používání české klávesnice

Pro usnadnění programování a zrychlení psaní na české klávesnici doporučuji používat následující klávesové zkratky využívající klávesu AltGr:

V systému Linux navíc fungují následující zkratky využívající horní řadu znaků s diakritikou (speciální znaky jsou na těchto klávesách spolu s číslicemi nakresleny pro snazší zapamatování):

Pod ostatními klávesami se skrývají další, i když méně užitečné speciální znaky.

Dále velmi doporučuji procvičit si psaní všemi deseti, bude se vám to velmi hodit nejen při programování.

Přehled základních datových typů

Typ Velikost (bits) Minimální hodnota Maximální hodnota Poznámky
bool 8 0 1 Pro použití typu bool je třeba #include <stdbool.h>.
char 8 -128 127 7-bitové kódování znaků pomocí ASCII tabulky.
unsigned char 8 0 255
short 16 -32768 32767 Typ pro reprezentaci celých čísel.
unsigned short 16 0 65535 Typ pro reprezentaci nezáporných celých čísel.
int 32 -2147483648 2147483647 Typ pro reprezentaci celých čísel.
unsigned int 32 0 4294967295 Typ pro reprezentaci nezáporných celých čísel.
long 64 -9223372036854775808 9223372036854775807 Typ pro reprezentaci celých čísel.
unsigned long 64 0 18446744073709551615 Typ pro reprezentaci nezáporných celých čísel.
float 32 \(\approx 1.175 \times 10^{-38}\) \(\approx 3.402 \times 10^{38}\) Typ pro reprezentaci racionálních čísel.
double 64 \(\approx 2.225 \times 10^{-308}\) \(\approx 1.797 \times 10^{308}\) Typ pro reprezentaci racionálních čísel.

Při vyhodnocování aritmetických operací obsahujících proměnné různých typů dochází k implicitní konverzi proměnných na „ten větší“ ze zúčastněných typů. Tedy např. součet proměnné typu short a proměnné typu int proběhne tak, že se hodnota proměnné typu short převede na typ int a součet se provede pro typ int. Při výpočtech může dojít k chybám způsobeným přetečením nebo podtečením maximálního rozsahu hodnot pro daný typ.

Pozor: Celočíselné proměnné lze dělit pouze celočíselně. Pokud je potřeba neceločíselný výsledek, je třeba explicitně provést přetypování, např. (float) x / y.

Pozor: Konverze na typ bool funguje jinak než konverze na ostatní celočíselné typy. Výraz (bool) 0.5 dává 1, kdežto (int) 0.5 dává 0.

Pozor: Hodnoty typu char (znaky) je třeba ve zdrojovém kódu zapisovat pomocí jednoduchých uvozovek, tedy 'a', 'b', 'c' apod. Pomocí dvojitých uvozovek se zapisují textové řetězce, kterými se budeme zabývat později.

Důležité pojmy

Čtení vstupních dat z konzole

Pro čtení vstupních dat z konzole budeme používat funkci scanf, která přečte vstupní řetězec zadaný v terminálu po stisknutí klávesy Enter, pokusí se ho převést na data odpovídajícího datového typu a výsledek uloží na zadanou adresu. Nejjednodušší vysvětlení na příkladu:

#include <stdio.h>

int main()
{
    // text pro uzivatele
    printf("Zadej cele cislo: ");

    // precteni vstupu
    int cislo;
    scanf("%d", &cislo);

    // vypis precteneho cisla
    printf("zadane cislo = %d\n", cislo);

    return 0;
}

Zkompilování a spuštění programu může dopadnout např. takto:

$ gcc -std=c99 -Wall scanf.c -o scanf
$ ./scanf
Zadej cele cislo: -4
zadane cislo = -4

Důležité poznámky:

Pomocí jednoho příkazu lze přečíst data pro libovolný pevný počet proměnných, např. příkaz scanf("%d %f %f", &cislo1, &cislo2, &cislo3); přečte jedno celé číslo a dvě desetinná čísla oddělená mezerami.

Probrané příklady

  1. Výpočet faktoriálu pomocí rekurzivní funkce. Pro příliš vysoké hodnoty proměnné n dojde při výpočtu k tzv. přetečení rozsahu pro daný typ (zde long) a program vrátí špatný výsledek.

    #include <stdio.h>
    
    long factorial(int n)
    {
        if (n == 1)
            return 1;
        else
            return n * factorial(n - 1);
    }
    
    int main()
    {
        int n = 10;
        long f = factorial(n);
        printf("%d! = %ld\n", n, f);
        return 0;
    }
    

    Nerekurzivní funkci pro výpočet faktoriálu lze zapsat např. pomocí cyklu for:

    long factorial(int n)
    {
        long vysledek = 1;
        for (int i = 2; i <= n; i++)
            vysledek *= i;
        return vysledek;
    }
    

    Nebo pomocí cyklu while:

    long factorial(int n)
    {
        long vysledek = 1;
        while (n > 1) {
            vysledek *= n;
            n--;
        }
        return vysledek;
    }
    
  2. Výpočet členů Fibonacciho posloupnosti. Rekurzivní verze je jednoduchá, ale velmi pomalá (i výpočet prvních 200 členů trvá dlouho):

    #include <stdio.h>
    
    int fibonacci(int n)
    {
        if (n == 1)
            return 1;
        else if (n == 2)
            return 1;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
    
    int main()
    {
        for (int i = 1; i <= 200; i++)
            printf("fibonacci(%d) = %d\n", i, fibonacci(i));
        return 0;
    }
    

    Nerekurzivní verze je komplikovanější, ale mnohem rychlejší. Efektivitu výpočtu zdůvodňovat nebudeme, to bude náplní předmětu ZALG v letním semestru.

    int fibonacci(int n)
    {
        // dve pomocne promenne pro predchozi cleny posloupnosti
        int f_i_minus_1 = 1;
        int f_i_minus_2 = 1;
    
        for (int i = 3; i <= n; i++) {
            // vypocet aktualniho clenu
            int f_i = f_i_minus_1 + f_i_minus_2;
            // posun promennych pro dalsi iteraci
            f_i_minus_2 = f_i_minus_1;
            f_i_minus_1 = f_i;
        }
    
        // vysledek (clen f_n) je v promenne f_i_minus_1
        return f_i_minus_1;
    }
    
  3. Úprava předchozích příkladů, aby vstupní data (např. počet členů posloupnosti) četly z terminálu. Program pro výpočet obvodu a obsahu kruhu.

5. cvičení

Program pro výpočet řešení kvadratické rovnice. Pro výpočet odmocniny použijeme funkci sqrtf z hlavičkového souboru math.h.

#include <stdio.h>
#include <math.h>

int main()
{
    printf("Zadej parametry a, b, c kvadraticke rovnice a*x^2 + b*x + c = 0:\n");
    float a, b, c;
    scanf("%f %f %f", &a, &b, &c);

    float d = b*b - 4*a*c;
    if (d > 0) {
        float x1 = (-b - sqrtf(d)) / (2*a);
        float x2 = (-b + sqrtf(d)) / (2*a);
        printf("Reseni rovnice jsou x_1 = %g a x_2 = %g.\n", x1, x2);
    }
    else if (d == 0) {
        float x = -b / (2*a);
        printf("Reseni rovnice je x = %g.\n", x);
    }
    else {
        printf("Rovnice nema zadne realne reseni.\n");
    }

    return 0;
}

Při překladu pomocí kompilátoru gcc v systému Linux je potřeba přidat parametr -lm, tedy např:

gcc -std=c99 -Wall -lm rovnice.c -o rovnice

6. cvičení

Pole je základní datová struktura sloužící k uložení \(N\) prvků stejného datového typu. Počet prvků \(N\) může být buď konstanta nebo hodnota nějaké proměnné. Deklarace pole se provede podobně jako deklarace proměnné, pouze za název proměnné se do hranatých závorek napíše počet prvků pole:

int pole[7];

Nebo s délkou určenou hodnotou proměnné:

int n = 7;
int pole2[n];

Jednotlivé prvky pole jsou v paměti počítače uloženy těsně za sebou, takže pro přístup k prvkům pole stačí znát adresu prvního prvku a celkový počet prvků. Pro přístup k prvkům pole se opět používají hranaté závorky, např. pole[i] představuje i-tý prvek pole. Indexování prvků funguje tak, že od základní adresy pole se posuneme o daný počet prvků (hodnota zadaná v hranatých závorkách) doprava – první prvek má tedy index 0 a poslední prvek má index n - 1.

Stejně jako v případě normálnímich proměnných i prvky pole je nejprve potřeba inicializovat. Např. pro vynulování včech prvků pole délky n lze použít cyklus:

for (int i = 0; i < n; i++)
    pole[i] = 0;

Podobně lze přečíst hodnoty prvků z terminálu pomocí funkce scanf:

for (int i = 0; i < n; i++)
    scanf("%d", &pole[i]);

Nebo vypsat zadané hodnoty pomocí funkce printf:

for (int i = 0; i < n; i++)
    printf("%d. prvek ma hodnotu %d\n", i, pole[i]);

Probrané příklady

  1. Nalezení nejmenší a největší hodnoty.

    #include <stdio.h>
    
    int min(int n, int* pole)
    {
        // pokud ma pole kladnou delku, muzeme hledat minimum
        if (n > 0) {
            // inicializace dosavadniho minima na prvni prvek pole
            int m = pole[0];
            // porovnani s ostatnimi prvky pole
            for (int i = 1; i < n; i++) {
                if (pole[i] < m)
                    m = pole[i];
            }
            // vraceni vysledneho minima
            return m;
        }
        else {
            // minimum prazdneho pole dava nesmyslny vysledek
            return 2147483647;
        }
    }
    
    int max(int n, int* pole)
    {
        // pokud ma pole kladnou delku, muzeme hledat maximum
        if (n > 0) {
            // inicializace dosavadniho maxima na prvni prvek pole
            int m = pole[0];
            // porovnani s ostatnimi prvky pole
            for (int i = 1; i < n; i++) {
                if (pole[i] > m)
                    m = pole[i];
            }
            // vraceni vysledneho maxima
            return m;
        }
        else {
            // maximum prazdneho pole dava nesmyslny vysledek
            return -2147483648;
        }
    }
    
    int main()
    {
        printf("Zadej delku pole: ");
        int n;
        scanf("%d", &n);
    
        printf("Zadej %d celych cisel:\n", n);
        int pole[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &pole[i]);
    
        // nalezeni nejmensiho a nejvetsiho cisla
        int nejmensi = min(n, pole);
        int nejvetsi = max(n, pole);
    
        printf("Nejmensi zadane cislo je %d a nejvetsi zadane cislo je %d.\n", nejmensi, nejvetsi);
    
        return 0;
    }
    

    Program obsahuje funkce max a min, které vrací největší a nejmenší prvek daného pole. Návratový typ těchto funkcí je tedy shodný s typem prvků pole (int). Parametry těchto funkcí jsou int n (délka pole) a int* pole (adresa prvního prvku pole).

  2. (pro pokročilé) Seřazení prvků pole od největšího po nejmenší pomocí jednoduchého algoritmu dle vlastní volby.

7. cvičení

Probrané příklady:

  1. Program pro převod čísel z desítkové do dvojkové soustavy.

    Algoritmus výpočtu je pěkně vysvětlen zde.

    #include <stdio.h>
    
    int main()
    {
        int cislo;
        printf("Zadej cislo v desitkove soustave: ");
        scanf("%d", &cislo);
    
        // pomocne pole pro mezivysledky binarnich cifer
        int bin[32];
    
        // pomocna promenna pro vysledny pocet binarnich cifer
        int pocet_cifer = 0;
    
        // vypocet binarnich cifer
        while (cislo > 0) {
            bin[pocet_cifer] = cislo % 2;
            cislo /= 2;    // cislo = cislo / 2;
            pocet_cifer++;
        }
    
        // zpetny vypis binarnich cifer
        for (int j = pocet_cifer - 1; j >= 0; j--)
            printf("%d", bin[j]);
    
        // konec radku za vysledkem
        printf("\n");
    
        return 0;
    }
    

8. cvičení

Vektory lze v počítači přirozeně reprezentovat pomocí pole. Např. vektor \(v \in \mathbb R^n\) můžeme reprezentovat pomocí pole délky n s typem prvků float. Deklaraci můžeme provést např. takto:

int n = 13;  // nebo nacist pomoci funkce scanf
float vektor[n];

Pro přístup k prvkům vektoru platí stejná pravidla jako pro přístup k prvkům pole (viz výše).

Probrané příklady:

  1. Funkce pro součet dvou vektorů. Funkci je třeba předat dva vstupní vektory (a, b), jeden výstupní vektor (c) a délku vektorů (n, stená pro všechny vektory).

    void secti_vektory(int n, float* a, float* b, float* c)
    {
        for (int i = 0; i < n; i++)
            c[i] = a[i] + b[i];
    }
    

    Připomínám, že při volání funkce záleží na pořadí parametrů, nikoliv na pojmenování proměnných. Proto např. pokud máme deklarovány vektory a, b, c délky m, pak následující příkaz spočítá součet c = b + a:

    secti_vektory(m, b, a, c);
    

    A následující příkaz spočítá součet a = c + b:

    secti_vektory(m, c, b, a);
    
  2. Funkce pro rozdíl dvou vektorů.

  3. Funkce pro výpočet skalárního součinu dvou vektorů. Na rozdíl od předchozího příkladu má funkce návratový typ float namísto výstupního parametru. V případě součtu dvou vektorů bylo potřeba použít výstupní parametr, protože pomocí návratového typu nelze vrátit pole vytvořené uvnitř dané funkce.

    float skalarni_soucin(int n, float* a, float* b)
    {
        float s = 0;
        for (int i = 0; i < n; i++)
            s = s + a[i] * b[i];
        return s;
    }
    

    Funkci lze použít např. takto:

    int soucin = skalarni_soucin(m, vektor1, vektor2);
    
  4. Vektorový součin. Funkce provede výpočet pouze pro vektory délky 3, v ostatních případech se neprovede nic (výsledek není definován).

    void vektorovy_soucin(int n, float* a, float* b, float* c)
    {
        if (n == 3) {
            c[0] = a[1]*b[2] - a[2]*b[1];
            c[1] = a[2]*b[0] - a[0]*b[2];
            c[2] = a[0]*b[1] - a[1]*b[0];
        }
    }
    

9. cvičení

Cvičení bylo zrušeno z důvodu nepřístupné místnosti B-009.

10. cvičení

Matice lze v počítači reprezentovat pomocí dvourozměrného pole. Pole s m řádky a n sloupci (matice \(m \times n\)) lze deklarovat takto:

float matice[m][n];

Ve skutečnosti jsou prvky dvourozměrného pole uloženy jako (jednorozměrné) pole délky \(m \times n\), přičemž prvky jsou uloženy po řádcích. Dvourozměrné pole však zahrnuje indexování prvků pomocí dvojice indexů. Deklaraci lze snadno zobecnit pro libovolnou dimenzi pole, např. 4-rozměrné pole \(2 \times 3 \times 4 \times 5\) můžeme deklarovat takto:

float pole[2][3][4][5];

Pro přístup k prvkům vícerozměrného pole je třeba použít odpovídající počet hranatých závorek. Např. \(i,j\)-tý prvek výše deklarované matice je matice[i][j].

Dvourozměrné pole je zobecněním jednorozměrného pole, ale předávání dvourozměrného pole jako parametr funkce je o poznání komplikovanější. Typ parametru totiž nemůže být float* (čili adresa prvního prvku), protože tím by se ztratila informace o indexování pomocí dvojice indexů. Parametr funkce je tedy potřeba specifikovat takto:

void funkce(int m, int n, float matice[m][n]);

Pomocí dvojice hranatých závorek říkáme, že matice je matice o m řádcích a n sloupcích, přičemž m a n jsou dříve specifikované parametry funkce. Na čísle v první hranaté závorce však nezáleží, podstatný je pouze počet sloupců. Funkci tedy lze ekvivalentně deklarovat takto:

void funkce(int m, int n, float matice[][n]);

nebo takto:

void funkce(int m, int n, float matice[100][n]);

Pro přehlednost je však vhodné používat výhradně první variantu, kde počet řádků odpovídá skutečnosti.

Tento způsob předávání vícerozměrného pole lze zkonkrétnit i pro jednorozměrné pole:

void funkce(int n, float pole[n]);

Nebo ekvivalentně:

void funkce(int n, float pole[]);

Probrané příklady

  1. Součet dvou matic. Program ukazuje práci s dvourozměrným polem - načítání prvků, předání do funkce, přístup k prvkům během výpočtu a výpis prvků.

    #include <stdio.h>
    
    void secti_matice(int m, int n, float A[m][n], float B[m][n], float C[m][n])
    {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] + B[i][j];
            }
        }
    }
    
    int main()
    {
        printf("Zadej pocet radku a pocet sloupcu: ");
        int m, n;
        scanf("%d%d", &m, &n);
    
        // matice m x n
        float A[m][n];
        float B[m][n];
        float C[m][n];
    
        printf("Zadej prvky matice A (po radcich):\n");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%f", &A[i][j]);
            }
        }
    
        printf("Zadej prvky matice B (po radcich):\n");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%f", &B[i][j]);
            }
        }
    
        // spocitat C = A + B
        secti_matice(m, n, A, B, C);
    
        // vypis matice C
        printf("Matice C = A + B je:\n");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                printf("%f\t", C[i][j]);
            }
            printf("\n");
        }
    }
    
  2. Násobení matice a vektoru. Načítání prvků matice a vektoru lze snadno převzít z přechozích příkladů, proto zde uvádím pouze funkci pro výpočet součinu \(c = A \cdot b\), kde \(A\) je matice \(m \times n\), \(b\) je vektor délky \(n\) a \(c\) je vektor délky \(m\).

    void matice_krat_vektor(int m, int n, float A[m][n], float b[], float c[])
    {
        for (int i = 0; i < m; i++) {
            float s = 0;
            for (int j = 0; j < n; j++) {
                s += A[i][j] * b[j];
            }
            c[i] = s;
        }
    }
    
  3. Domácí úkol: program pro násobení dvou (obdélníkových) matic.

11. cvičení

Všechny datové typy, se kterými jsme doposud pracovali, byly tzv. jednoduché datové typy, které reprezentovaly jednu hodnotu (např. číslo nebo znak). Pro definici komplikovanějších, tzv. složených datových typů slouží v jazyce C struktury. Existuje asi 5 různých způsobů definice struktury, my si ukážeme jeden:

typedef struct
{
    float x;
    float y;
}
point2d;

Definice obsahuje dvě nová klíčová slova, typedef a struct, která říkají, že definujeme strukturu a chceme s ní pracovat jako s typem. Následuje seznam deklarací složek struktury ve složených závorkách (to můžou být jednoduché datové typy, ale i dříve definované struktury) a nakonec název struktury.

Proměnnou typu point2d můžeme deklarovat stejným způsobem, jako dříve:

point2d a;

Ke složkám x a y můžeme přistupovat pomocí operátoru . (tečka):

a.x = 1;
a.y = 2;

Novou proměnnou také můžeme inicializovat pomocí existující proměnné stejného typu, přičemž se odpovídajícím způsobem překopírují všechny složky (x do x, y do y atd.):

point2d b = a;

Další způsob inicializace struktury spočívá v zadání konkrétních hodnot ve složených závorkách:

point2d c = {2, 3};

Zde jsou jednotlivé složky inicializovány popořadě, tedy v našem případě složka x bude mít hodnotu 2 a složka y hodnotu 3.

Přiřazení je však jediná operace se strukturami, kterou lze v jazyce C provést automaticky (viz b = a výše). Ostatní běžné operace jako např. sčítání (+), odčítání (-) a porovnávání (==, !=) pro struktury nejsou definovány a místo nich je potřeba definovat vlastní funkce. Např. funkce pro porovnávání dvou proměnných typu point2d lze definovat tyto funkce:

#include <stdbool.h>

bool point2d_eq(point2d p1, point2d p2)
{
    return p1.x == p2.x && p1.y == p2.y;
}

bool point2d_ne(point2d p1, point2d p2)
{
    return ! (p1 == p2);
}

Připomínám, že #include <stdbool.h> je potřeba pro zpřístupnění klíčového slova bool. Názvy funkcí obsahují prefix point2d, aby bylo jasné, se kterým typem pracuje (kdybychom měli např. typ point3d pro reprezentaci bodů v prostoru, tak by bylo potřeba definovat jiné funkce). Suffixy eq (zkráceně equal) a ne (not equal) pak označují, co daná funkce dělá.

Probrané příklady

  1. Funkce pro výpočet vzdálenosti bodu od počátku.
  2. Funkce pro výpočet vzdálenosti dvou bodů.
  3. Funkce pro výpočet plochy obecného trojúhelníka daného souřadnícemi trojice vrcholů. Pro výpočet lze použít např. Heronův vzorec.

12. cvičení

Ukazatel (anglicky pointer) je proměnná speciálního typu, která nereprezentuje žádnou hodnotu, ale obsahuje adresu nějaké jiné proměnné v paměti počítače. Každý ukazatel má fixní velikost 64 bitů (resp. 32 bitů na 32-bitovém počítači). Ukazatele se tedy hodí pro správu dat o velkém objemu (např. polí), aby se zabránilo vytváření zbytečných kopií (to by vedlo ke spotřebování zbytečně velkého množství paměti a celkové neefektivitě programu).

Ukazatel lze deklarovat pomocí typu proměnné, na kterou se odkazuje, a hvězdičky. Např. ukazatel na proměnnou typu float lze deklarovat takto:

float* ukazatel;

Pokud dále vytvoříme proměnnou typu float, můžeme její adresu získat pomocí (unárního) operátoru & a zapsat do proměnné ukazatel:

float a = 1;
ukazatel = &a;

Pokud chceme pomocí ukazatele přistoupit k hodnotě, na kterou ukazuje, musíme ho tzv. dereferencovat pomocí (unárního) operátoru *:

*ukazatel = 2;

Nyní jsme do políčka v paměti, na kterou ukazuje ukazatel, zapsali hodnotu 2 typu float. Toto políčko je stejné, jako má proměnná a, takže pomocí ukazatele jsme změnili hodnotu proměnné a.

Pro ukazatele dále funguje aritmetika sčítání a odčítání, která je ale trošku jiná než pro klasické datové typy. Nejlépe je to vidět na příkladu s jednorozměrným polem:

int pole[20];

// vynulovani pole
for (int i = 0; i < 20; i++)
    pole[i] = 0;

// ukazatel na 0. prvek
int* ukazatel = pole;

// zapise 1 na 0. pozici
*ukazatel = 1;

// zapise 1 na 7. pozici
*(ukazatel + 7) = 1;

// ukazatel na 13. pozici
ukazatel = ukazatel + 13;

// zapise 1 na 15. a 11. pozici
*(ukazatel + 2) = 1;
*(ukazatel - 2) = 1;

// hranate zavorky lze pouzit i na ukazatel, nejenom na pole
ukazatel[1] = 1;
ukazatel[-1] = 1;

// vypis pole
for (int i = 0; i < 20; i++)
    printf("%d ", pole[i]);

Všimněte si, že hranaté závorky fungují stejně, jako přičtení celého čísla k ukazateli a následná dereference (výraz ukazatel[i] je ekvivalentní výrazu *(ukazatel + i)). Aritmetika ukazatelů tedy nefunguje po bytech, ale po políčkách o velikosti odpovídající datovému typu, na který ukazatel ukazuje.

Pokud máme ukazatel na nějakou strukturu, pro přístup k jejím složkám pomocí ukazatele lze použít operátor ->:

point2d a;
a.x = 1;
a.y = 2;

point2d* ukazatel = &a;
ukazatel->x = ukazatel->y;
ukazatel->y = 3;

Ukazatele se hodí např. v následujících případech:

Práce se soubory

Pro práci se soubory v jazyce C slouží struktura FILE a několik funkcí definovaných v hlavičkovém souboru stdio.h:

Pro zápis dat do souboru a čtení dat ze souboru existují funkce analogické funkcím pro zápis a čtení dat z terminálu:

Všechny funkce pro práci se soubory jsou popsány např. zde.

13. cvičení

Textový řetěžec (anglicky string) je v podstatě pole znaků (typ char) s tím rozdílem, že textový řetězec je dle konvence ukončen speciálním znakem \0. Řetězce lze zapisovat ve dvojitých uvozovkách, např. "Hello, world!" je řetězec délky 13 znaků, ale pro jeho uložení v paměti počítače je třeba pole délky alespoň 14 znaků, protože 14. znak bude \0. Znak \0 nemusí být pouze na konci daného pole znaků, např. "Hello,\0 world!" je platný textový řetězec o délce 6 znaků a je ekvivalentní s textovým řetězcem "Hello,".

S řetězci zadanými přímo ve zdrojovém kódu pomocí dvojitých uvozovek můžeme pracovat s využitím ukazatelů typu const char*:

const char* string = "Hello, world!";
printf("string = \"%s\"\n", string);
printf("prvni pismeno = '%c'\n", string[0]);

Tyto řetězce však nelze modifikovat, protože jsou po spuštění programu uloženy v části paměti, kam program nemá oprávnění zapisovat. To je vyjádřeno pomocí kvalifikátoru const. Pokud bychom v předchozím vynechali const a přidali např. příkaz string[6] = '\0', program by sice šel zkompilovat, ale při spuštění by skončil s chybovou hláškou segmentation fault.

Deklaraci modifikovatelného textového řetězce je třeba provést trochu jinak, aby kompilátor vytvořil pole v modifikovatelné oblasti paměti a textový řetězec ze dvojitých uvozovek do něj překopíroval:

char string[] = "Hello, world!";
string[6] = '\0';
printf("string = \"%s\"\n", string);

Předchozí příkazy by měly vypsat text string = "Hello,".

Funkce pro práci s textovými řetězci

Ve standardní knihovně jazyka C existuje řada funkcí pro práci s textovými řetězci. Ze seznamu všech funkcí zmíním zejména tyto:

Pro použití těchto funkcí je třeba includovat hlavičkový soubor string.h.

Důležité poznámky

Probrané příklady

  1. Program demonstrující základní práci s textovými řetězci (viz jednotlivé příkazy výše).
  2. Program pro určení počtu slov v textovém souboru.

    #include <stdio.h>
    #include <ctype.h>
    #include <stdbool.h>
    
    int main()
    {
        FILE* soubor = fopen("text.txt", "r");
        if (soubor == NULL) {
            printf("chyba otevreni souboru\n");
            return 1;
        }
    
        int pocet = 0;
    
        char predchozi_znak = '\0';
        char znak = '\0';
        bool za_prvnim_slovem = false;
    
        while (true) {
            znak = fgetc(soubor);
            if (znak == EOF)
                break;
    
            if (!isspace(znak))
                za_prvnim_slovem = true;
    
            // mezery zacneme pocitat az za prvnim slovem, pomoci promenne
            // predchozi_znak ignorujeme po sobe jdouci mezery
            if (za_prvnim_slovem && isspace(znak) && !isspace(predchozi_znak))
                pocet++;
    
            predchozi_znak = znak;
        }
    
        // pokud na konci neni mezera, tak jeste pricist 1
        if (!isspace(predchozi_znak))
            pocet++;
    
        printf("pocet slov = %d\n", pocet);
    
        fclose(soubor);
    
        return 0;
    }
    

    Cyklus while, který jsme použili pro čtení souboru znak po znaku, lze zapsat ekvivalentně i jinými způsoby, např.

    for (znak = fgetc(soubor); znak != EOF; ) {
        if (!isspace(znak))
            za_prvnim_slovem = true;
    
        // mezery zacneme pocitat az za prvnim slovem, pomoci promenne
        // predchozi_znak ignorujeme po sobe jdouci mezery
        if (za_prvnim_slovem && isspace(znak) && !isspace(predchozi_znak))
            pocet++;
    
        predchozi_znak = znak;
    }
    

    nebo

    while ((znak = fgetc(soubor)) != EOF) {
        if (!isspace(znak))
            za_prvnim_slovem = true;
    
        // mezery zacneme pocitat az za prvnim slovem, pomoci promenne
        // predchozi_znak ignorujeme po sobe jdouci mezery
        if (za_prvnim_slovem && isspace(znak) && !isspace(predchozi_znak))
            pocet++;
    
        predchozi_znak = znak;
    }
    
  3. Domácí úkol: program pro určení délky nejdelšího slova v souboru.

14. cvičení

(Polo)zápočtový domácí úkol

Tento domácí úkol je nutné splnit nejpozději do 25. 11. 2018, 24:00 a jeho vypracování je nutnou podmínkou pro zisk zápočtu dle varianty Standard na konci semestru. Vypracované programy zasílejte na mou emailovou adresu (odevzdávejte pouze zdrojový kód, nikoliv zkompilovaný program).

Stručné zadání: Napište program, který ze vstupního souboru načte seznam bodů v prostoru \(\mathbb R^3\) zadaných pomocí kartézských souřadnic, ověří, jestli všechny tyto body leží v jedné rovině, a v kladném případě spočítá obvod a obsah konvexního mnohoúhelníku s vrcholy umístěnými do načtených bodů.

Podrobnější zadání:

Testovací data: Program si můžete vyzkoušet s tímto souborem, pro který by měl vyjít obsah \(S = 4\) a obvod \(o = 2 + 4 \sqrt{2} \approx 7.656854\). Kvůli počítání v aritmetice s konečnou přesností se výsledky můžou mírně lišit.

15. cvičení

Datová struktura je organizované úložiště pro reprezentaci dat v paměti počítače. Nejjednodušší datovou strukturou, se kterou jsme zatím pracovali, je pole, kde lze ukládat fixní počet prvků stejného typu. Pole je tedy statická datová struktura, neboť jeho velikost je pevně daná a nelze ji po vytvoření měnit (nelze tedy přidávat nebo odebírat prvky). V dalších cvičeních se budeme zabývat vytvářením dynamických datových struktur, kde není třeba předem znát počet prvků a prvky lze přidávat a odebírat i po vytvoření datové struktury.

Pro vytváření dynamických datových struktur slouží dynamická alokace, která umožňuje vyhradit paměť pro libovolný počet prvků libovolného typu. Na rozdíl od „klasických“ proměnných není životnost dynamicky alokovaných proměnných vázána na žádnou funkci, dynamicky alokovaná data jsou k dispozici dokud je programátor ručně nedealokuje.

Dynamická alokace se provede pomocí funkce malloc, která má jeden parametr udávající požadovaný počet bytů a vrací ukazatel na nově alokovaná data. Např. alokaci jedné proměnné typu int a 10 proměnných typu float (tj. pole délky 10) lze provést takto:

int* ukazatel = malloc(sizeof(int));
float* pole = malloc(10*sizeof(float));

Po skončení práce s dynamicky alokovanými proměnnými je třeba ručně provést dealokaci pomocí funkce free, aby se zabránilo úniku paměti (tzv. memory leak):

free(ukazatel);
free(pole);

Poznámka: Pro použití funkcí malloc a free je třeba includovat hlavičkový soubor stdlib.h:

#include <stdlib.h>

Probrané příklady

Nejjednodušší dynamickou datovou strukturou je tzv. dynamické pole, u kterého lze měnit velikost. Pro jeho reprezentaci použijeme strukturu, která obsahuje ukazatel na data a aktuální velikost pole:

typedef struct
{
    float* data;
    int pocet;
}
dynamicke_pole;

Pro vytvoření pole můžeme vytvořit samostatnou funkci, která má jeden parametr udávající počet prvků a vrací hodnotu typu dynamicke_pole:

dynamicke_pole vytvor_pole(int pocet)
{
    dynamicke_pole pole;
    pole.data = malloc(pocet*sizeof(float));
    pole.pocet = pocet;
    return pole;
}

Při změně velikosti je potřeba alokovat nové pole s požadovanou velikostí, překopírovat prvky ze starého pole do nového a dealokovat původní pole:

void zvetsi_pole(dynamicke_pole* pole, int pocet)
{
    // alokace vetsiho pole
    float* nova_data = malloc((pole->pocet + pocet)*sizeof(float));
    // prekopirovani starych prvku
    for (int i = 0; i < pole->pocet; i++)
        nova_data[i] = pole->data[i];
    // dealokace starych dat
    free(pole->data);
    // prepsani ukazatele
    pole->data = nova_data;
    pole->pocet += pocet;
}

Funkce zvetsi_pole musí mít jako parametr ukazatel na strukturu reprezentující dynamické pole, protože chceme, aby modifikace této struktury měly efekt i vně této funkce. Pokud bychom strukturu dynamicke_pole předali hodnotou, pak by se vytvořila lokální kopie dané proměnné a ukazatel na nově alokovaná data by se nedostal do vnější proměnné.

16. cvičení

Spojový seznam je dynamická datová struktura podobná poli, ale jednotlivé prvky nejsou v paměti počítače umístěny těsně vedle sebe. Namísto toho jsou jednotlivé prvky alokovány samostatně a zřetězeny pomocí ukazatelů. Běžně se používají dvě varianty spojového seznamu:

Práce s dvousměrně zřetězeným seznamem je jednodušší, proto se budeme v následujících cvičeních zabývat jednosměrně zřetězeným seznamem.

Pro práci se spojovým seznamem je potřeba definovat struktury pro reprezentaci jednotlivých prvků seznamu (těm budeme říkat uzel) a pro reprezentaci celého seznamu (struktura spojovy_seznam). Struktura uzel bude definována rekurzivně, protože kvůli zřetězení musí uzel obsahovat ukazatel na sebe sama. V jazyce C je tedy potřeba nejprve provést tzv. dopřednou deklaraci (v jazyce C++ to není potřeba):

// dopredna deklarace
typedef struct uzel uzel;

Poté můžeme definovat strukturu uzel, která obsahuje data (např. cislo1 a cislo2) a ukazatel na následující prvek seznamu (naslednik):

struct uzel
{
    float cislo1;
    float cislo2;
    uzel* naslednik;
};

Struktura pro reprezentaci celého seznamu bude obsahovat pouze ukazatel na první prvek (dopředná deklarace není potřeba):

typedef struct
{
    uzel* zacatek;
} spojovy_seznam;

Prázdný spojový seznam vytvoříme tak, že vytvoříme proměnnou typu spojovy_seznam a ukazatel na první prvek nastavíme na NULL:

spojovy_seznam s;
s.zacatek = NULL;

Pro další operace se spojovým seznamem budeme vytvářet samostatné funkce, protože operace budou komplikovanější a budeme je používat častěji. Nejjednodušší operace se spojovým seznamem je přidání prvku na začátek, které lze provést pomocí následujících kroků:

  1. zapamatování si prvního prvku,
  2. vytvoření nového prvku na začátku seznamu,
  3. nastavení dat pro nový prvek,
  4. nastavení následníka nového prvku na původní první prvek.

Výsledná funkce může vypadat např. takto:

void pridej_na_zacatek(spojovy_seznam* seznam, float cislo1, float cislo2)
{
    uzel* stary_zacatek = seznam->zacatek;
    seznam->zacatek = malloc(sizeof(uzel));
    seznam->zacatek->cislo1 = cislo1;
    seznam->zacatek->cislo2 = cislo2;
    seznam->zacatek->naslednik = stary_zacatek;
}

Poznámka: Parametr seznam je potřeba předat pomocí ukazatele, protože dochází ke změně položky seznam->zacatek, která má být viditelná i mimo tuto funkci.

Při přidání nového prvku na konec seznamu je potřeba odlišit situaci, kdy je seznam prázdný a kdy už obsahuje nějaké prvky. V prvním případě jednoduše vytvoříme první prvek seznamu, ve druhém je nejprve potřeba najít konec seznamu:

void pridej_na_konec(spojovy_seznam* seznam, float cislo1, float cislo2)
{
    if (seznam->zacatek == NULL) {
        seznam->zacatek = malloc(sizeof(uzel));
        seznam->zacatek->cislo1 = cislo1;
        seznam->zacatek->cislo2 = cislo2;
        seznam->zacatek->naslednik = NULL;
    }
    else {
        // najit konec seznamu
        uzel* konec = seznam->zacatek;
        while (konec->naslednik != NULL) {
            konec = konec->naslednik;
        }

        konec->naslednik = malloc(sizeof(uzel));
        konec->naslednik->cislo1 = cislo1;
        konec->naslednik->cislo2 = cislo2;
        konec->naslednik->naslednik = NULL;
    }
}

Při dealokaci spojového seznamu je třeba postupně dealokovat všechny prvky seznamu. Začneme funkcí pro smazání prvního prvku seznamu: pokud nějaký prvek existuje, je třeba nejprve si zapamatovat první prvek, přepsat začátek seznamu na jeho následníka a provést dealokaci zapamatovaného prvku.

void smaz_prvni_prvek(spojovy_seznam* seznam)
{
    if (seznam->zacatek != NULL) {
        // zapamatovat si prvni prvek
        uzel* prvni_prvek = seznam->zacatek;
        // prepsani zacatku
        seznam->zacatek = prvni_prvek->naslednik;
        // zrusit prvni prvek
        free(prvni_prvek);
    }
}

Při dealokaci celého seznamu můžeme postupně mazat první prvek, dokud to jde:

void zrus_seznam(spojovy_seznam* seznam)
{
    while (seznam->zacatek != NULL)
        smaz_prvni_prvek(seznam);
}

Nyní můžeme spojový seznam začít používat, např.:

int main()
{
    spojovy_seznam s;
    s.zacatek = NULL;

    smaz_prvni_prvek(&s);
    pridej_na_konec(&s, 1.0, 2.0);
    pridej_na_konec(&s, 3.0, 4.0);
    pridej_na_konec(&s, 5.0, 4.0);
    smaz_prvni_prvek(&s);
    pridej_na_konec(&s, 6.0, 4.0);
    pridej_na_zacatek(&s, 7.0, 4.0);

    // vypis prvku
    uzel* u = s.zacatek;
    while (u->naslednik != NULL) {
        printf("%f, %f\n", u->cislo1, u->cislo2);
        u = u->naslednik;
    }
    printf("%f, %f\n", u->cislo1, u->cislo2);

    // dealokace
    zrus_seznam(&s);

    return 0;
}

17. cvičení

Nedefinované chování (undefined behaviour) je situace při zpracování programu, ve které není dle standardu jazyka C (nebo C++) definováno, jak se má program chovat. Nedefinované chování se může projevit několika způsoby: program může buď fungovat správně (v závislosti na překladači, operačním systému apod.), nebo se může chovat náhodně, nebo může skončit s nějakou chybovou hláškou, nebo může vypnout počítač, nebo může naformátovat disk…

V předchozích cvičeních jsme mohli narazit na následující případy nedefinovaného chování, kterým je třeba se vyhnout:

Probrané příklady

Pokračovali jsme v implementaci spojového seznamu, popis jsem sloučil s textem k předchozímu cvičení.

18. cvičení

Na předchozím cvičení jsme naprogramovali funkci pro smazání prvního prvku ze spojového seznamu. Pokud chceme z jednosměrně zřetězeného seznamu smazat nějaký prostřední prvek, nelze to provést jednoduše, protože k předchozímu prvku, kde je třeba aktualizovat ukazatel na následníka, nemáme přímý přístup. Proto se používá následující trik:

  1. Prostřední prvek, který chceme smazat, označíme jako u, jeho následníka označíme jako n1 a následníka prvku n1 označíme jako n2.
  2. Přesuneme data z prvku n1 do prvku u (tím „smažeme“ původní data prvku u, čehož jsme chtěli dosáhnout).
  3. Aktualizujeme ukazatel, aby následník prvku u byl prvek n2.
  4. Dealokujeme prvek n1.

Tímto postupem lze smazat libovolný prvek jednosměrně zřetězeného spojového seznamu s výjimkou posledního prvku. Aby bylo možné smazat libovolný prvek spojového seznamu s platnými daty, používá se modifikace obsahující jeden „prázdný“ prvek na konci seznamu. Pro tuto modifikaci je potřeba upravit všechny doposud naprogramované funkce. Výsledný program ze cvičení si můžete stáhnout zde: modifikovany_spojovy_seznam.c.

19. a 20. cvičení

Aplikace spojového seznamu pro vytvoření jednoduché databáze lidí obsahující jméno, příjmení, rodné číslo, telefon apod.

Výsledný program ze cvičení: seznam_lidi.c.

Last updated: Tue 11 December 2018