Oznamy

Prednášky

  • Dnešná prednáška reťazce, v stredu práca so súbormi.
  • Budúci týždeň začíname preberať rekurziu.

Cvičenia a miniprojekt

  • Dnes rozcvička na papieri, potom ďalšie aktivity bez počítača (budú sa týkať polí a triedenia).
  • Nezabudnite si priniesť pero a papier.
  • V utorok budú bežné zadania na počitači.
  • Nezabudnite na miniprojekt do budúceho pondelka 26.10. 22:00.

V stredu 28.10. o 18:10 bude prvý semestrálny test.

  • Zverejnili sme podrobnejšie informácie a sylabus: Test 1
  • Ak máte záujem o strojový preklad zadaní, treba sa vopred zaregistrovať, viď stránka vyššie.

Z minulej prednášky

Znaky

  • Znakové premenné sú typu char, z anglického character.
  • Znaky majú svoje kódy uvedené v tabuľke ASCII.
  • Do premennej typu char môžeme priraďovať, jej obsah zapísať alebo prečítať. Znaky môžeme porovnávať pomocou ==, <= atď
  • Znakové premenné ukladajú kódy jednotlivých znakov, čo sú celé čísla. Preto medzi znakmi a celými číslami môžeme prechádzať úplne jednoducho.
    • Keď chceme aby výsledok bol konkrétneho typu, použijeme pretypovanie.
  • Znakové konštanty sa píšu v apostrofoch, napr. 'A'

Switch

  • Namiesto niekoľkých vnorených if s tou istou premennou v podmienke môžeme použiť switch.
  • Vo všeobecnosti obsahuje príkaz switch viacero rôznych prípadov vyhodnotenia výrazu v podmienke.
switch (výraz) {
    case k1: príkazy1; break;
    case k2: príkazy2; break;
    default: príkazyd;
}

Pozor: vykonávanie nekončí vykonaním posledného príkazu v prikazyi, ale pokračuje ďalej, kým nie je prerušené príkazom break.

  • Výhodou je, že môžeme zlúčiť viacero prípadov do jednej vetvy.

Využitie znakov

Pomocou načítania po znakoch si môžeme sami naprogramovať konverziu textu na číslo a skontrolovať či je na vstupe skutočne číslo ukončené medzerou alebo koncom riadku.

  • Niečo podobné robí aj funkcia scanf pri načítaní čísla, ale my si to teraz spravíme sami.
  • Pre jednoduchosť predpokladáme, že číslo je kladné a celé.
#include <stdio.h>

int main(void) {
    int N = 0;
    char c;

    printf("Zadajte cele kladne cislo: ");

    scanf("%c", &c);

    // kým je načítaný znak číslo (t.j. jedna cifra)
    while ((c >= '0') && (c <= '9')) { 

        // prevod z kódu znaku na cifru 0..9 
        // ('0' má kod 48)
        int cifra = c - '0';
        // upravíme číslo N 
        N = N * 10 + cifra; 
        // a načítame ďalší znak
        scanf("%c", &c); 
    }

    if ((c == ' ') || (c == '\n')) { 
        // ak sme skončili medzerou alebo koncom riadku, 
        // tak je to pekné číslo
        printf("Zadali ste %d\n", N);
    } else {
        // ak sme skončili niečim iným, asi to nebude ok
        printf("Toto je cele cislo?\n"); 
    }
}

Reťazce v jazyku C

Textový reťazec je v jazyku C štandardne uložený v poli ako postupnosť znakov (char) ukončená znakom s kódom 0.

  • Napr. reťazec “ABC” je uložený ako pole dĺžky 4 obsahujúci kódy 65, 66, 67, 0 (resp. znaky ‘A’, ‘B’, ‘C’, ‘\0’)
  • Pozor, rozdiel medzi znakom s kódom 0 (píše sa aj ‘\0’) a znakom pre cifru nula ‘0’ s kódom 48
  • Reťazce teda nemôžu obsahovať vo vnútri znak s kódom 0, ten je rezervovaný na ukončovanie
  • Na reťazec s n znakmi potrebujeme pole dĺžky aspoň n+1, lebo jeden znak sa minie na ukončovací symbol

Keď sme robili funkcie na prácu s poľom čísel, museli sme poslať pole aj počet prvkov. Pri reťazcoch nemusíme zvlášť udržiavať dĺžku, tá je daná pozíciou nuly v poli.

Inicializácia reťazcov

  • Chceme vytvoriť premennú str obsahujúce reťazec Ahoj spolu s koncom riadku
  • Prvý spôsob je zdĺhavý:
    char str[6];
    str[0] = 'A';
    str[1] = 'h';
    str[2] = 'o';
    str[3] = 'j';
    str[4] = '\n'; // znak pre koniec riadku
    str[5] = 0;
  • Alebo ako inicializácia poľa: char str[10]={'A','h','o','j','\n',0};

  • Namiesto toho sa používa špeciálna skratka: char str[6]="Ahoj\n";

  • Ako vytvoríme prázdny reťazec?

Reťazec je naozaj pole

Znaky reťazca môžeme meniť

char a[100] = "vlk";
char ch = a[0]; // ch obsahuje hodnotu 'v'
char b[100] = "pes";

b[0] = ch;     // Výsledkom je 'ves'.
b[0] = 'd';    // Výsledkom je 'des'. 
b[0] = a[1];   // Výsledkom je 'les'.

Reťazec sa nedá kopírovať jednoduchým priradením, nemôžeme teda spraviť

char a[100];
a = "Ahoj";           // chyba
char b[100] = "Ahoj"; // ok - inicializacia
a = b;                // chyba

Reťazce sa nedajú ani porovnávať pomocou ==, !=, < atď

Kopírovanie a porovnávanie si musíme naprogramovať cez cykly, alebo použiť hotové funkcie z knižníc.

Knižnica string.h

Obsahuje mnohé funkcie na prácu s reťazcami, napríklad tieto:

  • strlen(retazec): vráti dĺžku reťazca
  • strcpy(kam, co): skopíruje reťazec co do reťazca kam (pole kam musí byť dosť dlhé)
  • strcat(kam, co): za koniec reťazca kam pridá reťazec co (pole kam musí byť dosť dlhé)
  • strcmp(retazec1, retazec2): vráti nulu ak sa reťazce rovnajú, kladné číslo keď je prvý neskôr v abecednom poradí, záporné číslo, ak je skôr. Pozor, to či je skôr alebo neskôr sa berie podľa kódov znakov, takže napr. 'Z' je skôr ako 'a'.

Všetky tieto funkcie by sme si však vedeli naprogramovať aj sami. Tu je napríklad výpočet dĺžky:

int myStrLen(char a[]) {
    int n = 0; 
    while (a[n] != 0) { n++; }
    return n;
}
  • čo bude funkcia robiť, ak reťazcu chýba na konci 0?

Ukážeme si tri verzie kopírovania:

void myStrCpy(char a[], char b[]) {
    /* Skopíruj obsah reťazca b do reťazca a.
     * Pole a musí mať dosť miesta. */
    int n = 0;
    while (b[n] != 0) {
        a[n] = b[n];
        n++;
    }
    a[n] = 0; // reťazec musí končiť 0
}

Druhá verzia využíva funkciu strlen, ale je neefektívna. Prečo?

void myStrCpy2(char a[], char b[]) {
    for (int i = 0; i <= strlen(b); i++) {
        a[i] = b[i];
    }
}

Lepšie by bolo uložiť si dĺžku do premennej a použiť ju v cykle.

void myStrCpy3(char a[], char b[]) {
    int len = strlen(b);
    for (int i = 0; i <= len; i++) {
        a[i] = b[i];
    }
}
  • Aká je zložitosť týchto funkcií ako funkcia dĺžky reťazca n?

Namiesto strcmp naprogramujeme len test na rovnosť:

bool rovnostRetazcov(char a[], char b[]) {
    /* vráti true ak sú reťazce a, b rovnaké, inak vráti false */

    for (int i = 0; a[i] != 0 || b[i] != 0; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}
  • Ako bude prebiehať funkcia, ak jeden reťazec je začiatkom druhého?

Načítavanie a vypisovanie reťazcov

  • Funkcia scanf s parametrom %s načíta zo vstupu jedno slovo do poľa znakov.
    • Preskočí biele znaky (medzery, konce riadkov, tabulátory), potom prečíta všetko po ďalší biely znak (alebo koniec vstupu). Prečítané slovo uloží do zadaného poľa a ukončí ho nulou.
    • Pri čítaní je vhodné nastaviť maximálny počet znakov na načítanie, aby sme nevyšli z poľa. Napr. scanf("%10s", str) načíta najviac 10 znakov do poľa str, toto pole by teda malo mať aspoň 11 prvkov (10 znakov + 0 na konci).
  • Na načítanie jedného riadku je možné použiť funkciu fgets(str, maxN, stdin).
    • str je pole znakov, do ktorého sa načítava,
    • maxN je maximálny počet znakov na načítanie (vrátane ukončovacieho 0), t.j. dĺžka poľa
    • stdin znamená, že čítame z konzoly, t.j. zo štandardného vstupu
    • Funkcia nechá v poli str aj znak konca riadku, ktorý sa načítal spolu s textom. Odstrániť ho môžeme príkazom str[strcspn(str, "\n")] = 0; O funkcii strcspn si môžete prečítať v dokumentácii k C knižnici.
  • Vypisovanie funguje pomocou printf("%s", str) alebo fputs(str, stdout), kde stdout znamená štandardný výstup (konzolu).

Ukážka načítania a funkcií z knižnice string.h

Nasledujúci program načíta od používateľa dva reťazce obsahujúce meno a priezvisko (bez diakritiky, každé jedno slovo) a potom vytvorí nový reťazec, ktorý obsahuje meno aj priezvisko oddelené medzerou. Na záver v tomto reťazci zmení všetky veľké písmená na malé. Tu je ukážka beho programu:

Zadaj krstne meno: Janko
Zadaj priezvisko: Hrasko
Meno a priezvisko spolu: "Janko Hrasko"
Meno a priezvisko malymi pismenami: "janko hrasko"

#include <stdio.h>
#include <string.h>

#define NMAX 100

int main(void) {
    char meno[NMAX], priezvisko[NMAX];

    // načítanie dvoch reťazcov (čítame vždy po ďalší biely znak)
    printf("Zadaj krstne meno: ");
    scanf("%99s", meno);

    printf("Zadaj priezvisko: ");
    scanf("%99s", priezvisko);

    // pole na spojené reťazce musí byť dosť veľké
    char spolu[2 * NMAX  + 1];

    // do reťazca spolu najskôr nakopírujeme meno
    // potom na koniec pridáme medzeru
    // a potom pridáme priezvisko
    strcpy(spolu, meno);
    strcat(spolu, " ");
    strcat(spolu, priezvisko);

    // vypíšeme spojené meno
    printf("Meno a priezvisko spolu: \"%s\"\n", spolu);

    // veľké písmena zmeníme na malé
    int n = strlen(spolu);
    for (int i = 0; i < n; i++) {
        // testujeme, je či je i-ty znak veľké písmeno
        if (spolu[i] >= 'A' && spolu[i] <= 'Z') {
            int order = spolu[i] - 'A';  // poradové číslo písmena 0..25
            spolu[i] = order + 'a';      // prepočítame na malé písmeno
        }
    }

    printf("Meno a priezvisko malymi pismenami: \"%s\"\n", spolu);
}

Čo ak chceme povoliť aj mená pozostávajúce z viacerých slov (napr. “Jan Amos”)?

  • Meno aj priezvisko načítame pomocou fgets, aby sme načítali celý riadok.
  • Potom odstránime koniec riadku, ktorý sa načítal spolu s textom.
  • Načítanie mena a priezviska by teda vyzeralo takto:
    printf("Zadaj krstne meno: ");
    fgets(meno, NMAX, stdin);
    meno[strcspn(meno, "\n")] = 0;  // odstránime koniec riadku

    printf("Zadaj priezvisko: ");
    fgets(priezvisko, NMAX, stdin);
    priezvisko[strcspn(priezvisko, "\n")] = 0; // odstránime koniec riadku

Cvičenie: Ak by sme vo verzii programu s fgets zmenili NMAX na 3, priebeh programu môže vyzerať takto:

Zadaj krstne meno: Janko
Zadaj priezvisko: Meno a priezvisko spolu: "Ja nk"
Meno a priezvisko malymi pismenami: "Ja nk"

Čo sa presne v programe stalo a prečo sa takto správal?

Algoritmy s reťazcami

Prácu s reťazcami si precvičíme na niekoľkých príkladoch.

Vyhľadávanie podreťazca

Chceme zistiť, či a kde sa v reťazci nachádza určité slovo alebo iná vzorka.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define NMAX 2000

int find(char text[], char pattern[]) {
    /* Vráti polohu prvého výskytu reťazca pattern 
     * v reťazci text, alebo -1 ak sa nevyskytuje. */

    int n = strlen(text);
    int m = strlen(pattern);
    for (int i = 0; i < n - m + 1; i++) {
        bool zhoda = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
               zhoda = false;
               break;
            }
        }
        if (zhoda) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    char text[NMAX], pattern[NMAX];

    printf("Zadaj text: ");
    fgets(text, NMAX, stdin);
    text[strcspn(text, "\n")] = 0;  // odstránime koniec riadku

    printf("Zadaj vzorku: ");
    fgets(pattern, NMAX, stdin);
    pattern[strcspn(pattern, "\n")] = 0; // odstránime koniec riadku
    printf("%d\n", find(text, pattern));
}
  • Predpočítame si dĺžky a uložíme do premenných, aby sa zbytočne nerátali znova a znova
  • Ako by sme zmenili program aby hľadal posledný výskyt namiesto prvého?
  • Vedeli by sme do poľa uložiť polohy všetkých výskytov?
  • Neskôr si ukážeme, že vyhľadávanie podreťazca sa dá robiť aj knižničnou funkciou strstr.

Prevod čísla na reťazec

Máme danú premennú x typu int, chceme ju uložiť v desiatkovej sústave do reťazca.

  • Aj na toto existuje knižničná funkcia sprintf, ale my si to spravíme sami.
  • Zvyšok po delení 10 je posledná cifra, uložíme si ju do reťazca, vydelíme x desiatimi
  • Opakujeme, kým nespracujeme celé číslo.
  • Prevod z čísla c (0..9) na cifru: ‘0’+c
  • Nezabudneme na ukončovací znak 0
  • Dostaneme číslo v opačnom poradí, napr pre x=12 budeme mať reťazec {‘2’, ‘1’, 0}
  • Preto ešte celé číslo otočíme naopak.
void reverse(char a[]) {
    int n = strlen(a);
    int i = 0;
    int j = n - 1;
    while (i < j) {
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++; j--;
    }
}

void int2str(int x, char a[]) {
    /* prevedie kladné celé číslo x na reťazec,
     * výsledok uloží do reťazca a, ktorý musí mať dosť miesta. */
    assert(x > 0);

    int n = 0;
    while(x > 0) {
        a[n] = '0' + x % 10;
        x /= 10;
        n++;
    }
    a[n] = 0;  /* ukončovací znak 0 */

    /* teraz je číslo naopak, treba otočiť */
    reverse(a);
}
  • Ako upravíme funkciu, aby fungovala aj pre x=0, prípadne záporné x?
  • Pozor na rozdiel medzi znakom 0 a ‘0’ (a medzi reťazcom “0”)

Formátovanie čísla

  • Chceme číslo zapísať do reťazca a doplniť naľavo medzerami na šírku width.
void formatInt(int x, char A[], int width) {
    /* číslo x konvertujeme na reťazec
     * a uložíme do poľa A zarované doprava na šírku width */

    /* najprv x uložíme do pomocného reťazca B a zrátame jeho dĺžku n */
    char B[NMAX];
    int2str(x, B);
    int n = strlen(B);

    /* do A dáme width-n medzier a ukončovaciu 0 */
    assert(n <= width);
    int i;
    for (i = 0; i < width - n; i++) {
        A[i] = ' ';
    }
    A[i] = 0;

    /* za A prikopírujeme B */
    strcat(A, B);
}
  • Čo by sa stalo, ak by sme nedali do A ukončovaciu 0?
  • Vedeli by ste prepísať program, aby pracoval priamo v poli A (bez poľa B)?

Využijeme na vypísanie pekne zarovnanej tabuľky faktoriálov:

#include <stdio.h>
#include <string.h>
#include <assert.h>

#define NMAX 100

void reverse(char a[]) {
  // ... (funkcia z predchádzajúceho príkladu)
}

void int2str(int x, char a[]) {
  // ... (funkcia z predchádzajúceho príkladu)
}

void formatInt(int x, char A[], int width) {
  // ... (funkcia z predchádzajúceho príkladu)
}


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

int main(void) {
    char A[NMAX];
    for (int i = 1; i <= 12; i++) {
        int x = factorial(i);
        formatInt(i, A, 2);
        printf("%s! = ", A);
        formatInt(x, A, 10);
        printf("%s\n", A);
    }
}

 1! =          1
 2! =          2
 3! =          6
 4! =         24
 5! =        120
 6! =        720
 7! =       5040
 8! =      40320
 9! =     362880
10! =    3628800
11! =   39916800
12! =  479001600

Dalo by sa aj jednoduchšie pomocou nastavenia šírky v printf:

int main(void) {
    for (int i = 1; i <= 12; i++) {
        int x = factorial(i);
        printf("%2d! = %10d\n", i, x);
    }
}

Zalamovanie riadkov

Pre zaujímavosť: ukážka trochu dlhšieho programu na prácu s textom

  • Máme reťazec s nejakým textom, v ktorom sa vyskytujú rôzne biele znaky, napríklad medzery a konce riadkov. Máme danú šírku riadku W, napr. 80 znakov. Úlohou je ho upraviť tak aby:
    • na každom riadku bolo najviac W znakov, pričom nový riadok začína tam, kde by už ďalšie slovo presahovalo cez W,
    • medzi dvoma slovami má byť vždy buď jedna medzera alebo jeden koniec riadku.
    • Predpokladáme, že žiadne slovo nemá viac ako W znakov.

Príklad vstupu a výstupu programu:

Zadavaj text ukonceny prazdnym riadkom.
A AA A AAA 
A  A AA AAA
AAA A AA AA  A

Zadaj sirku riadku:
5
Sformatovany odstavec:
A AA
A AAA
A A
AA
AAA
AAA A
AA AA
A

Zadavaj text ukonceny prazdnym riadkom.
Martin Kukucin: Do skoly.    Vakacie sa koncia. Ondrej Rybar sa vse zamysli nad marnostou sveta i vsetkeho, co je v nom. 
Predstupuje mu tu i tu pred oci profesor, ako stoji pred ciernou tabulou, drziac kruzidlo v ruke a demonstruje pamatnu poucku Pytagorovu. 
A zimomriavky naskakuju na chrbat, lebo s geometriou stoji od pociatku na nohe valecnej. 
Ani matematika nenie lepsia, menovite odvtedy, co sa do nej vplichtili miesto cisel vsakove litery. 
Neraz hutal, naco ich ucenci vpustili do matematiky - ved i bez nich je dost strapata: ci sa im malilo cisel a tak preto vsantrocili medzi ne a a b a ci fantazia sa im tak rozihrala, 
ze prekrocila hranice cisel celych, zlomkov obycajnych i desatinnych i bohvieakych, a zabludila na nivy, kde rastu nestastne litery? 
 ,Uz akokolvek,' huta Ondro, ,litery tam nemaju co hladat. Tazko je uverit, ze a/b = c, lebo nevies, co je a, alebo b.' 

Zadaj sirku riadku:
50
Sformatovany odstavec:
Martin Kukucin: Do skoly. Vakacie sa koncia.
Ondrej Rybar sa vse zamysli nad marnostou sveta i
vsetkeho, co je v nom. Predstupuje mu tu i tu pred
oci profesor, ako stoji pred ciernou tabulou,
drziac kruzidlo v ruke a demonstruje pamatnu
poucku Pytagorovu. A zimomriavky naskakuju na
chrbat, lebo s geometriou stoji od pociatku na
nohe valecnej. Ani matematika nenie lepsia,
menovite odvtedy, co sa do nej vplichtili miesto
cisel vsakove litery. Neraz hutal, naco ich ucenci
vpustili do matematiky - ved i bez nich je dost
strapata: ci sa im malilo cisel a tak preto
vsantrocili medzi ne a a b a ci fantazia sa im tak
rozihrala, ze prekrocila hranice cisel celych,
zlomkov obycajnych i desatinnych i bohvieakych, a
zabludila na nivy, kde rastu nestastne litery? ,Uz
akokolvek,' huta Ondro, ,litery tam nemaju co
hladat. Tazko je uverit, ze a/b = c, lebo nevies,
co je a, alebo b.'

Plán: úlohu si rozdelíme na viac častí

  • Prerobíme reťazec tak, aby sme všetky biele znaky nahradili medzerami. Na rozpoznanie bielych znakov použijeme funkciu isspace z knižnice <ctype.h>.
  • Každý súvislý úsek medzier nahradíme práve jednou medzerou, zmažeme medzery na začiatku a na konci.
    • Viac možností na riešenie, napríklad znaky presýpame do nového poľa. My ale použijeme len jedno pole.
  • Niektoré medzery nahradíme koncom riadku, aby každý riadok mal šírku najviac W.
  • Spravíme načítanie a vypísanie.

Program sa nachádza v zvláštnom súbore formatovanie.c

Zhrnutie

  • Reťazec je pole znakov, za posledným znakom reťazca dáme špeciálny znak s kódom 0
  • V knižnici string.h sú funkcie na porovnávanie a kopírovanie reťazcov atď. a pomocou scanf a printf môžeme reťazce načítavať a vypisovať.
  • Ďalšie funkcie si vieme naprogramovať aj sami, zvyčajne jednoduchá práca s poľom