Cvičení

Cvičení probíhají u počítačů v učebně UL409. Nenahrazují výklad – cílem cvičení je ověřit si znalosti nabyté na přednášce (příp. samostudiem) v praxi naprogramováním řešení zadaných úkolů. Cvičit je tedy možné i doma (účast na cvičení není povinná). Na cvičení se tedy píšou krátké programy v jazyce C, a oproti samostatné práci doma zde máte možnost konzultovat správnost "svého" přístupu k řešení se cvičícím a s kolegy. K získání zápočtu a úspěšnému složení zkoušky z předmětu Programování v jazyce C není účast na cvičení nutná, ale může významně napomoci. Dlouhodobě se potvrzuje významná korelace mezi účastí na cvičení a výslednou známkou.

Rozpis cvičení

Uvedená čísla týdnů jsou pouze orientační – v důsledků změn v rozvrhu (např. z důvodů státních svátků, apod.) se mohou uvedené úlohy řešit v jiném kalendářním týdnu.

 Cvičení   Týden   Úkoly 
1. 38. Úvodní informace, seznámení s předmětem, vstupní test.
2. 39. Ovládání překladačů jazyka C (Bloodshed Dev-C++ 5.0, Microsoft Visual Studio 2008, GCC); tvorba jednoduchého programu ve stylu HelloWorld - základní řídicí konstrukce jazyka; překlad a sestavování jednoduchých programů (s cílem dokonale pochopit mechanismus překladu modulů a jejich propojení linkerem);stručný úvod do LaTeXu (volitelně).
3. 40. Psaní jednoduchých programů s využitím základních datových typů a řídicích konstrukcí jazyka C; převody čísel mezi polyadickými soustavami; převody reprezentací čísel (IEEE float a bitový zápis) - využití ukazatelů na základní datové typy; práce s polem.
4. 41. Procvičení práce s ukazateli - na typ funkce (program "jednoduchá kalkulačka") a na typ struktura (jednosměrně zřetězený spojový seznam).
5. 42. Překlad výrazů s prefixovým/postfixovým operátorem snížení/zvýšení hodnoty - ověření chování překladače; dynamická správa paměti, práce s pointery, binární vyhledávací strom.
6. 43. make, hlubší procvičení práce s ukazateli - tvorba knihovny maticových operací a demonstrační program, který ověří její správnou funkčnost.
7. 44. Implementace zásobníku, práce s řetězci, převod textu na číslo, zpracování aritmetických výrazů - konstrukce jednoduchého zásobníkově orientovaného parseru.
8. 45. Linkování modulů v různých jazycích na úrovni .obj souborů, práce s debuggerem obecně, OllyDbg (nebo Open Watcom Debugger, Turbo Debugger, či podobný), základy reverzního inženýrství – lokalizace určitého úseku kódu, jeho úprava/odstranění.
9. 46. Příprava externího modulu v assembleru, slinkování s programem v C, ověření funkčnosti a porovnání výkonu pomocí debuggeru/disassembleru.
10. 47. Použití standardního rozšíření jazyka ANSI C - funkcí void *bsearch(...) a void qsort(...) z knihovny stdlib.h, práce s rozsáhlejšími soubory dat.
11. 48. rezerva (obsah bude upřesněn)
12. 49. rezerva (obsah bude upřesněn)
13. 50. "zkouška na nečisto"

Zadání úkolů k samostatnému procvičení

Řešení (nebo jeho nástin) níže uvedených úkolů na jednotlivá cvičení najdete na konci této stránky – v části Řešení úkolů. K co nejlepšímu zvládnutí jazyka C je však žádoucí, abyste úkoly zpracovávali opravdu pokud možno samostatně a přiložená řešení použili až jako poslední pomoc nebo k ověření správnosti svého postupu.

Úkoly k samostatnému procvičení – 2
  1. Napište minimalistický program hello.c, který nedělá nic – pouze vrací nějakou návratovou hodnotu pomocí příkazu return ve funkci int main(). Otestujte návratovou hodnotu (vypsáním na obrazovku) v dávkovém souboru. Vyzkoušejte tento program přeložit různými dostupnými překladači.
  2. Upravte program hello.c tak, aby návratovou hodnotu převzal jako parametr z příkazového řádku.
  3. Prozkoumejte důkladně mechanismus překladu a sestavování spustitelného souboru. Připravte dva zdrojové soubory v jazyce C. První nechť obsahuje pouze funkci int main(), v níž se volá zatím nikde nedefinovaná funkce int disp(). Druhý soubor nechť obsahuje pouze funkci int disp(). Ověřte, že oba tyto programy lze přeložit a po sestavení do spustitelného souboru i spustit (linker převedl tzv. symboly na adresy skutečného výkonného kódu).
  4. Napište program na konverzi teploty ze stupňů Fahrenheita na stupně Celsia. Program si vyžádá vstup číselného údaje o teplotě ve stupních Fahrenheita a následně vypíše ekvivalentní hodnotu ve stupních Celsia. Převodní vztah lze nalézt např. na Wikipedii.
[Nahoru]

Úkoly k samostatnému procvičení – 3
  1. Napište program, který bude převádět celé dekadické číslo předané jako parametr na příkazové řádce do binární soustavy. Je-li parametr na příkazové řádce ve špatném formátu (není to číslo, obsahuje nesmyslné znaky, apod.), nechť program vypíše srozumitelné chybové hlášení. K převodu ze znakové reprezentace (char *argv[i]) do celočíselné můžete využít funkci int atoi(const char *str); z knihovny stdlib.h.
  2. Napište program, který bude převádět dekadické číslo s pohyblivou desetinnou čárkou ve formátu IEEE (datový typ float) předané jako parametr na příkazové řádce do šestnáctové a dvojkové soustavy. Je-li parametr na příkazové řádce ve špatném formátu (není to číslo, obsahuje nesmyslné znaky, apod.), nechť program vypíše srozumitelné chybové hlášení. K převodu ze znakové reprezentace do číselné využijte funkci double atof(const char *str); z knihovny stdlib.h. V binární reprezentaci odlište (např. svislou čárou) bity náležející znaménku, exponentu a mantise.
  3. Kdo by se nudil, může si zkusit naprogramovat i převod opačný, tj. z šestnáctkové reprezentace na reálné číslo.
  4. Napište program bubble.c, který bude řadit prvky (typu int) pole o velikosti aspoň 20 položek algoritmem Bubble Sort. Hodnoty prvků pole vygenerujte náhodně pomocí funkcí void srand(unsigned seed) a int rand(void) z knihovny stdlib.h.
  5. Kdo by se nudil, může si zkusit naprogramovat i jiné metody řazení (např. Quick Sort).
[Nahoru]

Úkoly k samostatnému procvičení – 4
  1. Na rozcvičení napište během maximálně 10 minut funkci void swap(...), která bude navzájem zaměňovat obsah svých dvou argumentů typu int. Správnou činnost funkce ověřte jednoduchým programem.
  2. Napište program calc.c, který bude vykonávat základní matematické operace (sčítání, odčítání, násobení, dělení, umocnění) a to tak, že využijete možností datového typu funkce vracející T. Nadefinujete 5 funkcí pro sčítání, odčítání, atd. se dvěma parametry. V hlavním cyklu výpočtu se podle uvedeného znaménka početní operace přiřadí do proměnné typu ukazatel na funkci vracející T příslušná funkce (např. float (*comp_fn) (float a, float b); ... comp_fn = &add;). Výpočetní mechanismus bude tedy stále (bez ohledu na zvolenou operaci) volat tutéž funkci - vlastně proměnnou typu ukazatel na funkci vracející T (např. result = comp_fn(a, b);)
  3. Napište program, který bude spravovat jednosměrný spojový seznam (seznam dynamicky zřetězených prvků). Položkou seznamu bude záznam struct person { char name[32]; int age; ... }. Program bude umět záznamy přidávat, rušit a vypisovat a rušit celý seznam.
  4. Kdo by se nudil, doprogramuje do úlohy z předchozího bodu řazení seznamu metodou zatřiďování.
[Nahoru]

Úkoly k samostatnému procvičení – 5
  1. Prozkoumejte chování překladače při práci s výrazy, ve kterých je obsažen operátor inkrement (++) a dekrement (--):
    1. i = i++;
    2. i = ++i;
    3. if (i++ == ++i) ...
    4. if (i++ && ++i) ...
    5. j = (j++ * --i) + ++j;
    6. apod.
    Cílem tohoto úkolu je uvědomit si nebezpečnost používání tohoto operátoru v komplexnejších výrazech vzhledem k mnohdy neočekávanému výsledku. Pokuste se nejprve odhadnout výsledek a pak teprve spusťte testovací program.
  2. Napište program bst.c, který bude pracovat s binárním vyhledávacím stromem. Naprogramujte v odděleném modulu tree.c funkce na vkládání, vyhledávání a rušení uzlu stromu. Zajistěte "rozumné" (textové pochopitelně) zobrazení stromu v konzoli.
  3. Zbude-li Vám čas, doplňte modul tree.c o funkce na vyvažování binárního vyhledávacího stromu tak, aby vytvářený strom splňoval podmínky AVL stromu.
[Nahoru]

Úkoly k samostatnému procvičení – 6
  1. Vytvořte knihovnu operací s maticemi matrix.c a k ní příslušný hlavičkový soubor matrix.h. Knihovna bude obsahovat vhodnou datovou strukturu struct matrix {...};, která umožní uchovávání matice libovolné velikosti v paměti (matice má vždy 2 rozměry - řádky a sloupce), funkce na vytvoření (alokaci) nové matice, zrušení matice, umístění prvku do matice a dále matematické funkce realizující základní maticové operace, tj. sčítání, násobení a transpozice, a pochopitelně také funkci, která matici v čitelné podobě zobrazí na konzoli. Prvky matice uvažujte reálné, tj. datový typ double. Pokud nemáte v maticích úplně jasno, zkuste odkaz http://en.wikipedia.org/wiki/Matrix_operation.
  2. Překlad a sestavení celého cvičného projektu provádějte nástrojem make. Vytvořte v pracovním adresáři projektu soubor makefile podle pokynů z přednášky. Nástroj make musí zajistit překlad knihovny i demonstračního programu a následné slinkování .obj souborů.
  3. Doplňte do makefile cíl clean, který odstraní po překladu z adresáře nepotřebné soubory.
[Nahoru]

Úkoly k samostatnému procvičení – 7
  1. Vytvořte knihovnu pro práci se zásobníkem stack.c. Nechť prvkem zásobníku je libovolný datový typ daný pouze svojí velikostí v bytech. Tato velikost bude předána funkci stack *createstack(int size, int itemlen);, která vytvoří dynamicky zásobník o size položkách, přičemž každá bude mít velikost itemlen. Samozřejmostí je implementace dvou základních funkcí zásobníku - void push(stack *s, void *data); a void pop(stack *s, void *data);
  2. Napište program, který bude pomocí zásobníku - a tedy výše popsané knihovny - zpracovávat aritmetické výrazy. Nejprve naprogramujte vyhodnocování tzv. postfixových výrazů, např. "2 3 + 5 5 + *", jehož výsledkem je 50.
  3. Až odladíte jednodušší variantu pro postfixové výrazy, naprogramujte také zpracování tzv. infixových výrazů, tedy běžných aritmetických výrazů typu "9 + 5 / 8 - 3 * 2", kde je priorita výpočtu dána prioritou operátorů.
  4. Doplňte předchozí variantu programu o zpracování priority operací, tj. naprogramujte analýzu uzávorkovaných výrazů (uvažujte pouze jeden druh závorek - kulaté).
[Nahoru]

Úkoly k samostatnému procvičení – 8
  1. POZOR! Tato úloha vyžaduje použití balíku Microsoft Visual C/C++. V GCC nelze program bez úprav přeložit; GCC používá jiné konvence při předávání argumentů funkcím a také linker pracuje jinak.
  2. Stáhněte si zdrojové soubory v archivu [Uložit]sem8.zip - soubor qsortdemo.c je program řadící náhodně vygenerované pole 20 prvků vzestupně metodou QuickSort; využívá externí funkci void swap(int *x, int *y), která je zapsaná v assembleru v souboru swap.asm.
  3. Proveďte překlad assemblerem Microsoft Macro Assembler z balíku Microsoft Visual Studio 2008 zadáním příkazu ml swap.asm /c a posléze přeložte C-soubor příkazem cl s přepínačem /Zi, který zajišťuje přidání ladicích informací a slinkujte s objektovým souborem swap.obj.
  4. V případě nejasností se pokuste vyhledat příslušné informace na Internetu nebo v nápovědě MSDN.
  5. Vyzkoušejte si práci s debuggery [Uložit]Open Watcom Debugger a [Uložit]OllyDbg podle pokynů vyučujícího nebo podle nápovědy debuggerů či na Internetu.
  6. Dopište do programu v C ochranu heslem (stačí primitivní pomocí funkce int strcmp(const char *str1, const char *str2);) nebo si stáhněte [Uložit]tento program s heslem zahashovaným algoritmem MD5, program přeložte bez ladicích informací, takže v debuggeru nebudete mít k dispozici zdrojový kód, ale pouze assembler. Pokuste se nalézt strojový kód podmínky if (...) ... a zabránit přepsáním příslušných instrukcí skoku do negativní větve v případě zadání špatného hesla.
[Nahoru]

Úkoly k samostatnému procvičení – 9
  1. Naprogramujte v assembleru externí modul, který bude hlavnímu programu v C poskytovat funkci long int hsmul(long int a, long int b). Tato funkce bude provádět velmi rychlé násobení dvou celých čísel pomocí bitových posunů. Využijte instrukcí SHL/SHR, JC/JNC ..., LOOP ..., apod. Detailní popis všech instrukcí procesoru i80x86 je k dispozici v této [Uložit]referenční příučce.
  2. Napište v C ověřovací program, kterým ověříte funkčnost naprogramovaného modulu v assembleru.
  3. Pomocí debuggeru prověřte, že je váš kód lépe optimalizovaný, než při běžném násobení tak, jak ho přeloží překladač.
[Nahoru]

Úkoly k samostatnému procvičení – 10
  1. Naprogramujte aplikaci, na které si vyzkoušíte práci se standardním rozšířením ANSI C - funkcemi void *bsearch(...) a void qsort(...) z knihovny stdlib.h. Vaše aplikace nechť načte data ze seznamu studentů uloženého v souboru [Uložit]slist.csv ve formátu CSV (Comma-Separated Values). Uložte načtená data do vnitřní struktury vašeho programu (může to být pro jednoduchost statické pole prvků typu struct student { char id[6], char name[32], char surname[64], int t_pts, int e_pts, int w_pts, char date[10]}). Nadefinujte potřebné porovnávací funkce pro funkce void *bsearch(...) a void qsort(...).
  2. Zajistěte seřazení souboru podle příjmení studentů a uložení takto seřazeného souboru.
  3. Naprogramujte vyhledávání záznamu podle osobního čísla studenta.
[Nahoru]

Řešení úkolů k samostatnému procvičení

V archivu se nachází vypracované úkoly ze cvičení 2 až 7. Jedná se o variany, které byly naprogramované společně na cvičení. Neznamená to, že by u řady úloh nebyl možný jiný postup – právě naopak, předložená řešení představují často jen jednu z mnoha možností.

[Uložit] Řešení úkolů – archiv ZIP – 9 KB