Prednáška 16

Oznamy

• Dnes budú zverejnené úlohy na cvičenia č. 9 (menej, než obvykle).
• Na testovači pribudlo zadanie tretej (a poslednej) domácej úlohy s odovzdaním do 4. decembra, 22:00.
• V úvode piatkových doplnkových cvičení bude krátka písomka zameraná predovšetkým na rekurziu a smerníky. Riešenia budete písať priamo do editovateľných zadaní vo formáte pdf a body za písomku budú riadnou súčasťou hodnotenia tohtotýždňových cvičení. Bližšie informácie k technickej relizácii písomky v stredu.

Príklad na prácu s textovými súbormi

• Prácu s textovými súbormi si zopakujeme na nasledujúcom príklade.
• Hlavný vstupný súbor vstup.txt má na prvom riadku názov výstupného súboru.
• Každý z niekoľkých ďalších riadkov obsahuje názov jedného vstupného súboru nasledovaný počtom čísel, ktoré z neho chceme načítať.
• Úlohou je prekopírovať z každého súboru zadaný počet čísel.

Napríklad vstup.txt

vystup.txt
a.txt 2
b.txt 1
a.txt 3

Súbor a.txt

1 2 3 4 5 6 7 8 9

Súbor b.txt

10 20 30 40 50 60 70 80 90

Výsledný súboru vystup.txt

1 2 10 1 2 3

Program uvedený nižšie pracuje v nasledujúcich krokoch:

• Otvorí hlavný vstupný súbor vstup.txt a prečíta z neho názov výstupného súboru.
• Otvorí výstupný súbor.
• Následne opakovane prečíta názov súboru a počet čísel N.
• Otvorí súbor s práve načítaným názvom, prekopíruje z neho N čísel do výstupného súboru a následne tento súbor zatvorí.
• Zatvorí hlavný vstupný súbor aj výstupný súbor.

Dĺžka načítavaných reťazcov bude vo volaniach funkcie fscanf obmedzená na 19 znakov

• to teda je maximálna dĺžka názvu súboru, s ktorou bude program vedieť pracovať

#include <cstdio>
#include <cassert>
using namespace std;

int main() {
    FILE *fr_main, *fr_part, *fw;
    int N, r, num;
    fr_main = fopen("vstup.txt", "r");
    assert(fr_main != NULL);
    
    char filename[20];
    r = fscanf(fr_main, "%19s", filename);
    assert(r == 1); 
    
    fw = fopen(filename, "w");
    assert(fw != NULL);
    while (!feof(fr_main)) {
        r = fscanf(fr_main, "%19s %d ", filename, &N);
        assert(r == 2);
        fr_part = fopen(filename, "r");
        assert(fr_part != NULL);
        for (int i = 0; i < N; i++) {
            r = fscanf(fr_part, "%d ", &num);
            assert(r == 1);
            fprintf(fw, "%d ", num);
        }
        fclose(fr_part);
    }
    fclose(fw);
    fclose(fr_main); 
}

Čítanie a zapisovanie po znakoch

Knižnica cstdio obsahuje aj funkcie na čítanie a zapisovanie súboru po znakoch.

• Funkcia int getc(FILE *f) načíta a vráti jeden znak zo súboru
  • Ak načítanie neprebehne úspešne, výslekdom je špeciálna konštanta EOF, ktorá je vždy rôzna od ľubovoľnej hodnoty typu char
  • Neukladajte výstupnú hodnotu funkcie getc do premennej typu char, lebo nebudet vedieť rozoznať koniec súboru.
• Funkcia int getchar() je skratka pre getc(stdin), načíta teda jeden znak z konzoly
  • Avšak rovnako ako pri scanf sa vstup začne spracovávať až potom, ako používateľ stlačí Enter, nie je takto možné reagovať priamo na stlačenie nejakej klávesy.

• Funkcia int putc(int c, FILE *f) zapíše znak c do súboru.
• Funkcia int putchar(int c) je skratkou pre putc(c, stdout), vypíše teda daný znak na konzolu.

Príklad: kopírovanie súboru

Nasledujúci program skopíruje obsah súboru original.txt do súboru kopia.txt.

#include <cstdio>
using namespace std;

int main() {
    FILE *fr = fopen("original.txt", "r");
    FILE *fw = fopen("kopia.txt", "w");

    int c = getc(fr);
    while (c != EOF) {
        putc(c, fw);
        c = getc(fr);
    }

    fclose(fr);
    fclose(fw);
}

Cvičenie: čo robí nasledujúci program?

• výsledkom priradenia c = getc(fr) je hodnota priradená do premennej c

#include <cstdio>
using namespace std;

int main() {
    FILE *fr;
    int c;

    fr = fopen("vstup.txt", "r");
    while ((c = getc(fr)) != '\n') {
        putchar(c);
    }
    putchar(c);         
    fclose(fr);
}

Funkcia ungetc

• Často sa stáva, že pri načítavaní znakov nájdeme koniec práve načítavaného úseku až po načítaní znaku, ktorý už nie je žiadúce prečítať.
• Vtedy je užitočné posunúť sa v načítavaní o jeden krok nazad.
• Túto úlohu realizuje funkcia int ungetc(int c, FILE * f).
• Väčšinou ako c použijeme posledne načítaným znak zo súboru f
• Môžeme však použiť aj iný znak, ktorý bude virtuálne pridaný na začiatok neprečítanej časti súboru. Súbor sa reálne nemení, ale pri nasledujúcom čítaní z neho sa ako prvý prečíta znak c.
• V prípade úspechu ungetc(c,f) vráti hodnotu c; v prípade neúspechu je výstupom EOF.
• Takéto správanie funkcie ungetc je však garantované len ak sa táto funkcia nevolá viackrát za sebou.

Príklad č. 1: Nasledujúci kus programu skonvertuje reťazec pozostávajúci zo znakov '0' až '9' na zodpovedajúcu číselnú hodnotu. Keď narazí na prvý znak, ktorý nie je cifra, vráti ho, aby sa dal použiť pri ďalšom spracovávaní.

    int hodnota = 0;
    int c = getchar();
    while (c >= '0' && c <= '9') {
        hodnota = hodnota * 10 + (c - '0');
        c = getchar();
    }
    ungetc(c, stdin);

Príklad č. 2: Nasledujúci program prečíta číslo pomocou funkcie fscanf, predtým však musí prečítať neznámy počet znakov '$'.

#include <cstdio>
using namespace std;

int main() {
    FILE *fr = fopen("vstup.txt", "r");
    int c = getc(fr);
    while (c == '$') {
        c = getc(fr);
    }
    ungetc(c, fr);

    int hodnota;
    fscanf(fr, "%d", &hodnota);
    printf("%d\n", hodnota);
   
    fclose(fr);
}

Čítanie a zapisovanie po riadkoch

V knižnici cstdio je definovaná funkcia

char *fgets(char *str, int n, FILE * f);

pomocou ktorej možno načítať zo súboru, na ktorý ukazuje smerník f, práve jeden riadok (alebo nejakú jeho časť, ak je tento riadok príliš dlhý). Vstupnými argumentmi funkcie fgets sú:

• Pole znakov str, do ktorého sa v prípade úspechu riadok načíta.
• Číslo n určujúce maximálny počet znakov skopírovaných do poľa str. Presnejšie: do poľa str sa z daného riadku súboru skopíruje najviac n-1 znakov a reťazec str sa následne ukončí znakom \0. Pri typickom volaní funkcie fgets je teda n rovné dĺžke poľa str.
• Smerník f na súbor, z ktorého sa má riadok prečítať.

Funkcia fgets na týchto argumentoch postupne načítava znaky zo súboru, na ktorý ukazuje smerník f, pričom ich ukladá do str. To robí až dovtedy, kým narazí na koniec riadku (\n) alebo koniec súboru, prípadne kým sa zo súboru neprečíta n-1 znakov. Prípadný znak \n na konci riadku sa (pokiaľ nebolo načítaných príliš veľa znakov) nezahodí, ale pridá sa na koniec reťazca str. Výstupom funkcie fgets je v prípade načítania aspoň jedného znaku načítaný reťazec str; v prípade „nárazu” na koniec súboru je výstupom NULL a reťazec str ostáva nezmenený.

Príklad: nasledujúci program spočíta počet riadkov v súbore vstup.txt (za predpokladu, že žiaden z týchto riadkov nie je dlhší ako 100 znakov vrátane znaku \n na konci riadku):

#include <cstdio>
using namespace std;

const int maxN = 101;

int main(void) {
    char str[maxN];
    int num = 0;
    
    FILE *fr = fopen("vstup.txt", "r");
    while (fgets(str, maxN, fr) != NULL) {
        num++;
    }
    fclose(fr);
    
    printf("%d\n",num);
    
    return 0;
}

Cvičenie: Zistite, ako sa správa uvedený program, keď posledným znakom v súbore je resp. nie je znak \n. Zistite, čo program vypíše na výstup pre súbor, ktorý obsahuje jediný riadok o 200 znakoch.

Výstupným náprotivkom funkcie fgets je funkcia

int fputs(const char *str, FILE *f);

ktorá do súboru, na ktorý ukazuje smerník f, vypíše reťazec str. Vypisovaný reťazec str pritom môže obsahovať ľubovoľný (aj nulový) počet výskytov symbolu \n pre koniec riadku. V prípade úspechu vráti funkcia fputs nezáporné celé číslo; v prípade neúspechu vráti konštantu EOF.

Prístupy k spracovaniu textového vstupu

Vstup môže byť v textovom súbore zadaný v rôznych formátoch. V závislosti od formátu potom môžu byť výhodnými rôzne spôsoby jeho spracovania. Často používanými prístupmi k spracovaniu textového vstupu sú napríklad nasledujúce:

• Pomocou funkcie fscanf postupne načítať jednotlivé čísla, slová, a podobne. Tento prístup býva zvyčajne výhodný vtedy, keď sa všetky biele znaky považujú za ekvivalentné oddeľovače.
• Pomocou funkcie getc spracovať vstupný súbor po znakoch. Tu ide o relatívne univerzálny spôsob spracovania vstupu, ktorý je však v niektorých situáciách pomerne prácny.
• Pomocou funkcie fgets postupne prečítať jednotlivé riadky do reťazca a tento reťazec následne spracovať. Tento prístup je výhodný najmä vtedy, keď má koniec riadku funkciu prirodzeného oddeľovača vstupov a keď je dĺžka riadku predom obmedzená.

Často môže byť užitočné horeuvedené prístupy aj navzájom kombinovať.

Príklad č. 1: predpokladajme, že potrebujeme nájsť dĺžku najdlhšieho riadku v súbore (vrátane symbolu \n, ktorý sa môže vyskytovať na jeho konci). Nasledujúce dva programy túto úlohu riešia dvoma odlišnými spôsobmi:

• Prvý program postupne načítava riadky do reťazca, ktorý následne spracúva (problém, ak je riadok príliš dlhý).
• Druhý program číta súbor po znakoch, pričom si udržiava premennú pocet uchovávajúcu informáciu o tom, koľko písmen sa už v momentálne spracovávanom riadku načítalo.

#include <cstdio>
#include <cstring>
using namespace std;

const int maxN = 100;

int main(void) {
    FILE *fr = fopen("vstup.txt", "r");
    int maxDlzka = 0;
    char str[maxN];
    while (fgets(str, maxN, fr) != NULL) {
        int dlzka = strlen(str);
        if (dlzka > maxDlzka) {
            maxDlzka = dlzka;
        }
    }
    fclose(fr);
    printf("Najdlhsi riadok ma dlzku %d\n", maxDlzka);
    return 0;
}

#include <cstdio>
using namespace std;

int main(void) {
    FILE *fr = fopen("vstup.txt", "r");
    int maxDlzka = 0;
    int dlzka = 0;
    int c = getc(fr);
    while (c != EOF) {
        dlzka++;
        if (c == '\n') {
            if (dlzka > maxDlzka) {
                maxDlzka = dlzka;
            }
            dlzka = 0;
        }
        c = getc(fr);
    }
    if (dlzka > maxDlzka) { // Posledny riadok nemusi koncit symbolom \n.
        maxDlzka = dlzka;
    }
    fclose(fr);
    printf("Najdlhsi riadok ma dlzku %d\n", maxDlzka);
    return 0;
}

Príklad č. 2: nasledujúci program spracúva vstupný súbor obsahujúci čísla oddelené bielymi znakmi (medzery, tabulátory, konce riadkov,...), pričom medzi dvoma číslami môže byť aj viac ako jeden oddeľovač. Pre každý riadok program vypíše súčet čísel, ktoré sa v tomto riadku vyskytujú (predpokladá pritom, že každý – t. j. aj posledný – riadok vstupného súboru je ukončený symbolom \n).

Vzhľadom na to, že tu ide o pomerne nepríjemnú kombináciu rozlišovania koncov riadku od iných bielych znakov a čítania formátovaných hodnôt (čísel), kombinuje nasledujúci program čítanie po znakoch s využívaním funkcie fscanf. Pracuje pritom nasledovne:

• Kým sú na vstupe biele znaky, spracúva ich pomocou funkcie getc. Ak je niektorý z týchto znakov koncom riadku, vypíše zistený súčet čísel.
• Po „náraze” na prvý nebiely znak použije funkciu ungetc na jeho vrátenie do vstupného prúdu. Následne prečíta číslo pomocou funkcie fscanf a na základe prečítanej hodnoty aktualizuje súčet.
• Na zistenie, či je prečítaný znak biely, využíva nasledujúci program funkciu isspace z knižnice cctype.

#include <cstdio>
#include <cctype>
using namespace std;

int main(void) {
    FILE *fr = fopen("vstup.txt", "r");
    int sucet = 0;
    int hodnota;
    while (!feof(fr)) {
        int c = getc(fr);
        while (c != EOF && isspace(c)) { // Precitaj biele znaky po najblizsi nebiely.
            if (c == '\n') {             // Na konci riadku vypis sucet.
                printf("Sucet %d\n", sucet);
                sucet = 0;
            }
            c = getc(fr);
        }
        if (c == EOF) {                  // Pri naraze na koniec suboru nepokracuj dalej.
            break;
        }                
        ungetc(c, fr);                   // Posledny precitany znak nebol biely; vrat ho do vstupneho prudu.
        fscanf(fr, "%d", &hodnota);      // Precitaj cislo a pripocitaj ho k suctu.
        sucet += hodnota;
    }
    fclose(fr);
    return 0;
}

Cvičenie: upravte program tak, aby pracoval správne aj v prípade, že posledný riadok nie je ukončený symbolom \n.

Jednoduché šifrovanie

Prácu so súbormi si v nasledujúcom precvičíme na dvoch jednoduchých šifrách.

Caesarova šifra

Caesarova šifra je šifra, pri ktorej sa každé písmeno vstupného reťazca posunie cyklicky o K miest v abecednom poradí, kde K je zadaný parameter šifry (tzv. posun).

• Napríklad pre K=2 sa písmeno A zmení na C, písmeno b sa zmení na d a písmeno Z sa zmení na B.
• Ukážeme si jej použitie pre anglickú abecedu (t. j. znaky 'a' až 'z' a 'A' až 'Z' bez diakritiky); je ju ale možné upraviť napríklad aj tak, aby pracovala s ASCII kódmi.

Zašifrovanie súboru realizuje nasledujúci program:

#include <cstdio>
#include <cassert>
using namespace std;

void encryptCaesar(FILE *fr, FILE *fw, int shift) {
    assert(shift >= 0 && shift <= 25);
    int c;
    while ((c = getc(fr)) != EOF) {
        if ((c >= 'A') && (c <= 'Z')) {
            c = c + shift;
            if (c > 'Z') {
                c -= 26;
            }
        } else if ((c >= 'a') && (c <= 'z')) {
            c = c + shift;
            if (c > 'z') {
                c -= 26;
            }
        }
        putc(c, fw);
    }
}

int main(void) {
    int shift;
    scanf("%d", &shift);
    
    FILE *fr = fopen("plaintext.txt", "r");
    FILE *fw = fopen("ciphertext.txt", "w");
    
    encryptCaesar(fr, fw, shift);
    
    fclose(fr);
    fclose(fw);
    
    return 0;
}

Dešifrovanie súboru zašifrovaného Caesarovou šifrou realizuje tento program:

#include <cstdio>
#include <cassert>
using namespace std;

void decryptCaesar(FILE *fr, FILE *fw, int shift) {
    assert(shift >= 0 && shift <= 25);
    int c;
    while ((c = getc(fr)) != EOF) {
        if ((c >= 'A') && (c <= 'Z')) {
            c = c - shift;
            if (c < 'A') {
                c += 26;
            }
        } else if ((c >= 'a') && (c <= 'z')) {
            c = c - shift;
            if (c < 'a') {
                c += 26;
            }
        }
        putc(c, fw);
    }
}

int main(void) {
    int shift;
    scanf("%d", &shift);
    
    FILE *fr = fopen("ciphertext.txt", "r");
    FILE *fw = fopen("plaintext2.txt", "w");
    
    decryptCaesar(fr, fw, shift);
    
    fclose(fr);
    fclose(fw);
    
    return 0;
}

Vigenèrova šifra

Vigenèrova šifra je veľmi podobná Caesarovej; posun už ale nie je konštantný a realizuje sa podľa kľúča.

• Kľúčom je reťazec zložený z písmen A až Z, pričom tieto predstavujú posuny o 0 až 25 pozícií v abecede.
• Pri šifrovaní aj dešifrovaní sa jednotlivé abecedné posuny realizujú podľa kľúča. Prvý symbol otvoreného textu je tak zašifrovaný podľa prvého symbolu kľúča, druhý symbol podľa druhého symbolu kľúča, atď. Po vyčerpaní celého kľúča sa pokračuje cyklicky, opäť od jeho začiatku.

Zašifrovanie súboru realizuje nasledujúci program:

#include <cstdio>
using namespace std;

const int maxKeyLength = 100;

void encryptVigenere(FILE *fr, FILE *fw, char *key) {
    int c;
    int i = 0;
    while ((c = getc(fr)) != EOF) {
        if ((c >= 'A') && (c <= 'Z')) {
            c = c + (key[i] - 'A');
            if (c > 'Z') {
                c -= 26;
            }
            i++;
        } else if ((c >= 'a') && (c <= 'z')) {
            c = c + (key[i] - 'A');
            if (c > 'z') {
                c -= 26;
            }
            i++;
        }
        if (key[i] == 0) {
            i = 0;
        }
        putc(c, fw);
    }
}

int main(void) {
    char key[maxKeyLength];
    scanf("%s", key);
    
    FILE *fr = fopen("plaintext.txt", "r");
    FILE *fw = fopen("ciphertext.txt", "w");
    
    encryptVigenere(fr, fw, key);
    
    fclose(fr);
    fclose(fw);

    return 0;
}

Dešifrovanie súboru zašifrovaného Vigenèrovou šifrou realizuje tento program:

#include <cstdio>
#include <cassert>
using namespace std;

const int maxKeyLength = 100;

void decryptVigenere(FILE *fr, FILE *fw, char *key) {
    int c;
    int i = 0;
    while ((c = getc(fr)) != EOF) {
        if ((c >= 'A') && (c <= 'Z')) {
            c = c - (key[i] - 'A');
            if (c < 'A') {
                c += 26;
            }
            i++;
        } else if ((c >= 'a') && (c <= 'z')) {
            c = c - (key[i] - 'A');
            if (c < 'a') {
                c += 26;
            }
            i++;
        }
        if (key[i] == 0) {
            i = 0;
        }
        putc(c, fw);
    }
}

int main(void) {
    char key[maxKeyLength];
    scanf("%s", key);
    
    FILE *fr = fopen("ciphertext.txt", "r");
    FILE *fw = fopen("plaintext2.txt", "w");
    
    decryptVigenere(fr, fw, key);
    
    fclose(fr);
    fclose(fw);
    
    return 0;
}