Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

public:pb071:cviceni04 [2017/03/13 16:48]
Jirka Slaby [Na pozícii const záleží]
public:pb071:cviceni04 [2018/02/24 19:10]
Řádek 1: Řádek 1:
-====== 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: ==== 
- 
-<code c> 
-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'​ 
-</​code>​ 
-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ť ==== 
- 
-<code c> 
-*pointer == pointer[0]; // This is equivalent 
-// More general rule: 
-*(pointer + i) == pointer[i] // i is an integer 
-</​code>​ 
- 
-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ží ==== 
- 
-<code c> 
-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 
-</​code>​ 
-**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 ===== 
- 
-<​note>​ 
-Kostru zadania si môžete stiahnut tu: {{ :​public:​pb071:​cviceni:​cv04.zip | Kostra}} alebo na [[https://​gitlab.fi.muni.cz/​pb071/​pb071-seminars | GitLab]] 
-</​note>​ 
- 
-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. 
- 
-<code c> 
-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 
-</​code>​ 
-=== Funkcia: stringCopy === 
- 
-Naimplementujte funkciu ''​%%stringCopy%%'',​ ktorá skopíruje obsah druhého reťazca do prvého. 
- 
-<code c> 
-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 
-</​code>​ 
- 
-=== Funkcia: stringCountChar === 
- 
-Naimplementujte funkciu ''​%%stringCountChar%%'',​ ktorá spočíta počet výskytov znaku v reťazci. 
- 
-<code c> 
-size_t stringCountChar(const char *string, char ch); 
- 
-//main: 
-size_t countOfA = stringCountChar("​abba123 a", '​a'​);​ // will return 3 
-</​code>​ 
- 
-=== 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. 
- 
-<code c> 
-int stringCompare(const char *first, const char *second); 
-</​code>​ 
- 
-=== 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.) 
- 
-<code c> 
-int stringCompareN(const char *first, const char *second, size_t n); 
-</​code>​ 
- 
----- 
- 
-==== Ú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. 
- 
-<code c> 
-size_t stringCountSubstring(const char *original, const char *substring);​ 
-// Note: Try to use stringCompare to make it easier for you 
-</​code>​ 
-=== 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%%''​. 
- 
-<code c> 
-const char *stringFindChar(const char *original, const char ch); 
-</​code>​ 
- 
-=== 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%%''​. 
- 
-<code c> 
-const char *stringFindSubstring(const char *orig, const char *sub); 
-</​code>​ 
- 
-=== 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. 
- 
-<code c> 
-char *stringToUpper(const char *origin, char *result); 
-</​code>​ 
- 
-=== 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. 
- 
-<code c> 
-char *stringToLower(const char *origin, char *result); 
-</​code>​ 
-===== 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:** 
- 
-<code c> 
-void stringInsertSort(char *string, int (*comparator)(char , char)); 
-</​code>​ 
- 
-**Pseudokód:​** 
- 
-<​code>​ 
-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], A[i]) > 0) 
-        A[j] = A[j-1] 
-        j = j - 1 
-    end while 
-    A[j] = x 
- end for 
-</​code>​ 
- 
-Príklad komparátoru:​ 
- 
-<code c> 
-// jednoduchý komparátor:​ 
-int cmp(char a, char b) 
-{ 
-    return a - b; 
-} 
- 
-// volanie insert sortu: 
-stringInsertSort(string,​ cmp); 
- 
-// volanie komaprátoru v insert sorte: 
-... 
-while (j > 0 && ((*comparator)(array[j-1],​ array[i]) > 0)) 
-... 
-</​code>​ 
-=== Zaujímavé odkazy === 
- 
-  * [[http://​www.cplusplus.com/​reference/​cstring/​|Referenčná príručka string.h]] 
-  * [[http://​www.cplusplus.com/​reference/​cstdlib/​qsort/​|Referenčná príručka qsort]] 
-  * [[https://​opensource.apple.com/​source/​xnu/​xnu-1456.1.26/​bsd/​kern/​qsort.c|Implementácia qsort]] 
-  * [[https://​github.com/​antirez/​sds|Simple Dynamic Strings]] - malá ale zaujímavá knižnica pre prácu s reťazcami. 
-  * [[http://​stackoverflow.com/​questions/​890535/​what-is-the-difference-between-char-const-and-const-char|Konštantné ukazatele]] 
- 
- 
----- 
- 
-Ú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)