Cvičení 5: Reťazce
Autor zadání [xstanko2]
Kostra úkolu
Vzorové řešení

V tomto cvičení máte za úlohu precvičiť si prácu s reťazcami a hlavičkovým súborom string.h

Práca s reťazcami

V rámci prvej úlohy si naimplementujete vybrané funkcie na precvičenie práce s reťazcami.

Pri riešení úloh číslo 1 a 2 nepoužívajte funkcie z hlavičkového súboru string.h!

Úloha 1: String length

Naimplementujte funkciu string_length(), ktorá zistí dĺžku zadaného reťazca.

Všimnite si, že predávame ukazovateľ na konštantný reťazec. Funkcia nemení obsah reťazca. Vďaka tomu môže prekladač robiť rôzne optimalizácie a funkcia dokáže prijať aj reťazcový literál alebo reťazec, ktorý sme si alokovali na zásobníku.

V prípade, že vstupom je NULL, funkcia zlyhá kvôli nesplnenej vstupnej podmienke.

Vstupné podmienky môžete kontrolovať pomocou makra assert(expr), ktoré máte preddefinované a testy kontrolujú jeho použitie. 
size_t string_length(const char *str);

// example usage:

size_t length = string_length("Hello world!");
assert(length == 12); // should return 12
// Note: using just (char *) would cause a warning since
// you are trying to pass to the function something that is constant,
// but it expects non constant

Úloha 2: String copy

Naimplementujte funkciu string_copy(), ktorá skopíruje obsah druhého reťazca do prvého. Ako výsledok vráti hodnotu ukazovateľa result (podobne, ako to robí štandardná funkcia strcpy(3)).

V prípade, že ktorýkoľvek argument je NULL, funkcia zlyhá kvôli nesplnenej vstupnej podmienke.

char *string_copy(char *result, const char *original);

// example usage:

char buffer[7];
string_copy(buffer, "Hello!"); // buffer will contain string "Hello!"
assert(strcmp(buffer, "Hello!") == 0);
// Note here: result isn't const, you will change the memory where that pointer points to because
// you will copy characters from the original string there

Úloha 3: String count character

Naimplementujte funkciu string_count_char(), ktorá spočíta počet výskytov znaku v reťazci. Pri implementácii môžete využiť funkciu strchr(3).

Funkcia má vstupnú podmienku, že reťazec nie je NULL. V prípade, že hľadaný znak je \0, funkcia vráti 0.

size_t string_count_char(const char *string, char ch);

// example usage:

size_t count_a = string_count_char("abba123 a", 'a'); // will return 3

Úloha 4: String edit

Niekedy sa určite stretnete s tým, že chcete nejakým spôsobom upraviť každý znak reťazca. Príkladom môže byť prevedenie reťazca na reťazec s veľkými písmenami.

Naimplementujte funkciu string_edit(), ktorá na každý znak reťazca aplikuje transformačnú funkciu danú parametrom fn. Výsledok tejto transformačnej funkcie následne uloží na pôvodné miesto v reťazci. Funkcia nakoniec vráti hodnotu ukazovateľa string.

Funkcia predpokladá, že na vstupe nedostane ani jeden argument NULL.

Príklad transformačnej funkcie, ktorá prevedie malé písmená na veľké a jej použitie:

char *string_edit(char (*fn)(char), char *string);

char edit_up(char c)
{
    return toupper(c);
}

// example usage:

char string[] = "Hello!";
string_edit(&edit_up, string);
assert(strcmp(string, "HELLO!") == 0);

Určite ste si všimli, že prvý parameter funkcie string_edit() vyzerá trochu inak ako ostatné parametre. Jedná sa o ukazovateľ na funkciu, ktorá má jeden parameter typu char a jej návratová hodnota je taktiež typu char.

Takýto ukazovateľ viete používať ako klasickú funkciu, teda ju viete aj zavolať: fn(CHAR).

Taktiež si môžete skúsiť implementovať transformačnú funkciu na prevod veľkých písmen na malé alebo transformačnú funkciu počítajúcu Cézarovu šifru s nejakým fixným kľúčom.

Zložitejšie funkcie

V tejto úlohe odporúčame využiť funkcie z predošlej úlohy a funkcie z hlavičkového súboru string.h.

Úloha 5: String count substring

Naimplementujte funkciu string_count_substr(), ktorá spočíta, koľkokrát sa druhý podreťazec nachádza v prvom reťazci, podreťazce sa môžu prekrývať. Pri implementácii môžete využiť funkciu strstr(3).

V prípade, že ktorýkoľvek z argumentov je prázdny reťazec, funkcia vráti 0. Ďalej má ako vstupnú podmienku predpoklad, že žiaden z argumentov nie je NULL.

size_t string_count_substr(const char *original, const char *substring);

Úloha 6: Count occurrences of string in strings array

Naimplementujte funkciu string_count_string_in_array(), ktorá spočíta, koľkokrát sa nachádza reťazec v poli reťazcov.

Za posledným prvkom v poli reťazcov je NULL.

Funkcia predpokladá, že na vstupe nedostane ani jeden argument NULL.

size_t string_count_string_in_array(const char *array[], const char *string);

Úloha 7: String Split

Vyskúšate si implementovať funkciu, ktorá rozdelí reťazec na podreťazce a tie uloží do poľa. Delenie prebehne na základe deliaceho znaku.

Naimplementujte funkciu string_split(), ktorá rozdelí reťazec na základe deliaceho znaku na podreťazce. Funkcia bude obmedzená tým, že maximálna veľkosť podreťazca bude 255 znakov a maximálny počet podreťazcov bude 50.

V prípade, že vstupný reťazec je prázdny, hodnota size je nastavená na 0. Funkcia predpokladá, že žiadny z argumentov nie je NULL.

Argumenty funkcie:

  • pôvodný reťazec

  • pole podreťazcov, kam zapíšete výsledky

  • počet nájdených podreťazcov, ktorý zapíše táto funkcia

  • znak, podľa ktorého dôjde k rozdeleniu pôvodného reťazca

Deliaci znak sa vo výslednej matici nachádzať nebude.

void string_split(const char *string, char result[50][256], size_t *size, char delim);

Všimnite si, že maximálna dĺžka reťazca je 255 znakov a v matici deklarujeme 256. Zamyslite sa, prečo to tak je.

Bonusy

Vypracovanie bonusov nie je povinné, no skúste sa nad nimi zamyslieť a doma si ich vypracovať. Programovať sa najlepšie naučíte praxou!

Bonus 1: Insert Sort

V tejto úlohe si vyskúšate prácu s ukazovateľmi na funkcie.

Zadanie

Naimplementujte Insert Sort, ktorý bude slúžiť na usporiadanie znakov v reťazci. Ako prvý argument funkcia vezme samotný reťazec, druhým argumentom je komparátor. Komparátor je funkcia, ktorá vezme 2 argumenty a navzájom ich porovná. V prípade, že sú zhodné, vráti 0; ak je prvý prvok väčší, vráti kladnú hodnotu; inak vráti zápornú hodnotu.

(strcmp(3) je príklad komparátora, ktorý porovnáva reťazce)

Predpis funkcie:

void string_insert_sort(char *string, int (*comparator)(char, char));

Pseudokód:

A - vstupný reťazec
L - veľkosť poľa = string_length(A)
F - komparátor

for i = 1 to L - 1
    x = A[i]
    j = i
    while j > 0 and (F(A[j - 1], x) > 0)
        A[j] = A[j - 1]
        j = j - 1
    end while
    A[j] = x
 end for

Príklad komparátora:

// simple comparator:
int cmp(char a, char b)
{
    return a - b;
}

// insert sort call
string_insert_sort(string, cmp);

// call of the comparator in insert sort
...
while (j > 0 && (cmp(array[j - 1], array[i]) > 0))
...

Bonus 2: String map

Táto úloha je upravenou verziou štvrtej úlohy. Niekedy totiž ani upravenie reťazca na mieste nestačí a výsledok chcete uložiť do iného poľa alebo s ním chcete robiť iné transformácie. Príkladom môže byť prevedenie reťazca na reťazec s veľkými písmenami. V tejto úlohe si vyskúšate implementovať univerzálnu funkciu string_map().

Zadanie úlohy

Prvým argumentom funkcie bude pole, nad ktorým bude aplikovaná. Ako druhý argument vezme void* ukazovateľ, do ktorého bude vložený výsledok. Tretím argumentom bude transformačná funkcia.

void string_map(const char *string, void *result, void (*func)(void *, int, const char));

Funkcia prejde pole znakov a každý znak s jeho príslušným indexom predá transformačnej funkcii.

Transformačná funkcia vezme ako svoj prvý argument výsledok (result), ako druhý vezme pozíciu (index), na ktorej sa predávaný znak nachádza a tretí argument bude konkrétny znak.

Príklad transformačnej funkcie:

/*
 * Function will transform all the lowercase characters in the input string
 * to the uppercase letters.
 */
void transform_up(void *out, int i, const char ch)
{
    char *result = (char *) out;
    result[i] = toupper(ch);
}


/*
 * Function will count how many case insensitive 'A' are in the string.
 * We did not use the index (i), we do not have to use all the input parameters.
 */
void count_letter_a(void *out, int i, const char ch)
{
   if (tolower(ch) == 'a') {
      *((int *) out) += 1;
   }

}

Skúste si implementovať vlastnú transformačnú funkciu, ktorá spočíta počet písmen v reťazci.

Trochu teórie

Motivácia

Na tomto cvičení budete pracovať so statickými reťazcami a ukazovateľmi. Reťazec je pole znakov, ktoré je ukončené nulovým znakom (bytom hodnoty 0). Tento znak je na koniec reťazcových literálov pridávaný automaticky. Treba dbať na to, aby ste mali alokované dostatočné množstvo pamäte. (Na reťazec dĺžky 20 znakov je potrebné 21-znakové pole.) Vďaka nulovému bytu je možné ľahko zistiť, kde reťazec končí (dĺžka reťazca).

Na prednáške bolo vysvetlené, čo je ukazovateľ: typ premennej, ktorá uchováva adresu ukazujúcu do logického adresného priestoru aplikácie. Vďaka nemu je možné k tejto pamäti pristupovať, čítať ju, prepisovať, dokonca na danú adresu skočiť a začať vykonávať inštrukcie (funkčný ukazovateľ).

Na pozícii const záleží

Konštantný ukazovateľ char * const je ukazovateľ, priradená adresa sa po inicializácii už nedá meniť. Hodnotu, ktorá sa na danej adrese nachádza, ale zmeniť môžeme.

Ukazovateľ na konštantnú pamäť const char * (prípadne iný typ miesto char) znamená, že ukazovateľ ukazuje na nemennú pamäť. Na adrese, ktorá je v ňom uložená, sa môže nachádzať kus pamäte, ktorý meniť nechceme alebo nemôžeme. Samotnú adresu, kam ukazovateľ ukazuje, ale zmeniť môžeme.

const char *string;        // Pointer to constant memory  (const string)
char const * string;       // Same as above
char * const string;       // Constant pointer to non-constant memory
const char * const string; // Constant pointer to constant memory

Prvé dva prípady sú ekvivalentné kvôli tomu, že const sa viaže najprv zľava (ak je to možné). Keďže sa v prvom prípade nemá na čo naviazať, naviaže sa to, čo je prvé napravo.

Posledný prípad nehovorí nič iné než to, že nejde zmeniť ani adresa, na ktorú ukazuje ukazovateľ, ani pamäť, na ktorú sa ukazuje.

Používajte const všade tam, kde hodnotu nemeníte a meniť nebudete, najmä pri ukazovateľoch.

Zaujímavé odkazy