Cvičenie 04: Reťazce, časť 1.

Trocha teórie

Motivácia

V nasledujúcich 3 cvičeniach budete implementovať jednoduchú knižnicu na prácu s reťazcami.

Na tomto cvičení budete pracovať so statickými reťazcami a ukazateľmi. Reťazec je pole znakov, ktoré je ukončené nulovým znakom (bytom hodnoty 0). Tento znak je na koniec reťazcov 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 odvodiť, kde reťazec končí (dĺžka reťazca).

V jazyku C sa nekontroluje pretečenie poľa: treba si dať pozor aby nedošlo k zápisu alebo čítaniu mimo pridelenú pamäť.

Na prednáške bolo vysvetlené, čo je ukazateľ: 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ý ukazateľ).

Deklarácia poľa:

int myIntArray[5] = {1, 2, 3, 4, 5};   // declaration with initialization
sizeof(myIntArray) == 5 * sizeof(int); // 5 * 4 = 20
 
char myString[] = "hello world!";
// what is the array name (the symbol) myString? 
printf("0x%16lx\n", myString); // it would be an address, but address of what?
printf("%c\n", *myString); // it would print 'h'

Pozorovanie: Meno deklarovaného pola (myString), sa správa ako ukazateľ, obsahuje adresu prvého prvku poľa.

Dereferencia: Dereferencovaním mena poľa pristúpime k hodnote prvého prvku poľa.

Zaujímavosť

*pointer == pointer[0]; // This is equivalent
// More general rule:
*(pointer + i) == pointer[i] // i is an integer

Pozor, index síce môže byť negatívny, ale správa sa to inak ako v jazykoch typu Python. Nepoužívajte preto záporné indexy, kým presne nerozumiete ukazateľovej aritmetike.

Na pozícii const záleží

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

Konštatný ukazateľ je ukazateľ, ktorého raz priradená adresa sa už nedá meniť. Hodnotu, ktorá sa na danej adrese nachádza, ale zmeniť môžeme.
Ukazateľ na konštantnú pamať const char * (prípadne iný typ miesto char) znamená, že ukazateľ ukazuje na nemennú pamäť. Na adrese, ktorá je v ňom uložená, sa može nachádzať kus pamäte, ktorý meniť nechceme alebo ktorý meniť nie je možné.

Prvé dva prípady sú ekvivalentné kvôli tomu, že const sa viaže najprv zľava (ak je to možné). Kedže sa v prvom prípade sa 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 ukazateľ, ani pamäť na ktorú ukazuje.

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

Úlohy

Kostru zadania si môžete stiahnut tu: Kostra alebo na GitLab

Pri riešení nasledujúcich úloh nepouživajte funkcie z hlavičkového súboru string.h.

Úloha 1. - Funkcie na prácu s reťazcami

V rámci prvej úlohy si naimplementujete základné funkcie na precvičenie práce s reťazcami. Všetky tieto základné funkcie nám síce ponúka štandarná knižnica, ale cieľom cvičenia je pochopiť, ako dané funkcie pracujú a že ich princíp je jednoduchý.

Funkcia: stringLength

Naimplementujte funkciu stringLength, ktorá zistí dĺžku zadaného reťazca. Typ size_t je typ definovaný v hlavičkovom súbore stdlib.h alebo stddef.h.

Všimnite si, predávame ukazateľ 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ú konštantu, aj reťazec, ktorý sme si alokovali niekde na zásobníku.

size_t stringLength(const char *str);
// example of use:
stringLength("Hello world!"); // should return 12
// Note: using just (char *) would cause a warning as
// you are trying to pass to the function something that is constant, 
// but it expects non constant

Funkcia: stringCopy

Naimplementujte funkciu stringCopy, ktorá skopíruje obsah druhého reťazca do prvého.

char *stringCopy(char *result, const char *origin);
// example of use:
stringCopy(someString, "Hello!"); // someString will contain string "Hello"
// Note here: result isn't const, as the function will change the memory where that pointer points to

Funkcia: stringCountChar

Naimplementujte funkciu stringCountChar, ktorá spočíta počet výskytov znaku v reťazci.

size_t stringCountChar(const char *string, char ch);
 
//main:
size_t countOfA = stringCountChar("abba123 a", 'a'); // will return 3

Funkcia: stringCompare

Reťazce v jazyku C nie je možné porovnávať operátorom ==. Ak chceme porovnať dva reťazce, je potrebné porovnať jednotlivé znaky na rovnakých pozíciach.

Naimplementujte funkciu stringCompare, ktorá lexikograficky porovná 2 zadané reťazce. Ak sú rovnaké, vráti 0, ak je prvý reťazec lexikograficky menší, vráti zápornú hodnotu, inak vráti kladnú hodnotu.

int stringCompare(const char *first, const char *second);

Funkcia: stringCompareN

Naimplementujte funkciu stringCompareN, ktorá je podobná stringCompare. Táto funkcia ale bude porovnávať len prvých n znakov daných reťazcov. (Ak je n väčšie ako dĺžka samotných reťazcov, porovnáva len po dĺžku kratšieho z nich.)

int stringCompareN(const char *first, const char *second, size_t n);

Úloha 2. - Zložitejšie funkcie

V tejto úlohe odporúčame využiť funkcie z predošlej úlohy.

Funkcia: stringCountSubstring

Naimplementujte funkciu stringCountSubstring, ktorá spočíta, koľkokrát sa zadaný podreťazec nachádza v pôvodnom reťazci.

size_t stringCountSubstring(const char *original, const char *substring);
// Note: Try to use stringCompare to make it easier for you

Funkcia: stringFindChar

Naimplementujte funkciu stringFindChar, ktorá vráti ukazateľ na prvý výskyt zadaného znaku. Ak sa znak v reťazci nenachádza, vráti NULL.

const char *stringFindChar(const char *original, const char ch);

Funkcia: stringFindSubstring

Naimplementujte funkciu stringFindSubstring, ktorá vám vráti ukazateľ na prvý výskyt zadaného podreťazca. Ak sa podreťazec nenachádza v reťazci, tak funkcia vráti NULL.

const char *stringFindSubstring(const char *orig, const char *sub);

Funkcia: stringToUpper

Naimplementujte funkciu stringToUpper, ktorá všetky malé písmená zadaného reťazca zmení na veľké. Funkcia vráti ukazateľ na výsledný reťazec.

char *stringToUpper(const char *origin, char *result);

Funkcia: stringToLower

Naimplementujte funkciu stringToLower, ktorá vám všetky veľké písmená zadaného reťazca zmení na malé. Funkcia vráti ukazateľ na výsledný reťazec.

char *stringToLower(const char *origin, char *result);

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 ukazateľ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 zápornú hodnotu, inak vráti kladnú hodnotu.

(stringCompare je tiež komparátor, ktorý porovnáva reťazce)

Predpis funkcie:

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

Pseudokód:

A - vstupny retazec
L - veľkosť poľa = stringLength(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átoru:

// jednoduchý komparátor:
int cmp(char a, char b)
{
    return b - a;
}
 
// volanie insert sortu:
stringInsertSort(string, cmp);
 
// volanie komaprátoru v insert sorte:
...
while (j > 0 && ((*comparator)(array[j-1], array[i]) > 0))
...

Zaujímavé odkazy


Úlohu připravil Peter Stanko – stanko@mail.muni.cz.
V prípade pripomienok a otázok sa neváhajte ozvat do fóra alebo na mail.

QR Code
QR Code public:pb071:cviceni04 (generated for current page)