====== 11 - Struktury, union, výčtové typy, volání C z Javy ======

 /* * prezentace: [[.:prezentace]]
  * řešení: [[.:reseni:start]]*/
  * pro vyučující: [[private:tutorialinstruction:12:start|]]

===== Trocha teorie =====

==== Struktury a vytváření typů =====

Struktura je heterogenní datový typ, který slouží zejména ke spojení vzájemně souvisejících údajů (datových položek). Síla tohoto datového typu se obvykle projevuje v přehlednosti zdrojového kódu, ale lze ji i jednoduše využít pro návratové proměnné z funkcí.

=== Syntaxe struktury a příklad použití ===

<code c>
struct jménoStruktury {            struct student {
    typ jménoPoložky;                  char jmeno[20];
    typ jménoPoložky;                  char prijmeni[20];
    ...                                float prumer;
} proměnné;                        } Marketa, Pavel;
</code>

=== Vytvoření nového datového typu ===

Zavedení nového uživatelského datového typu je možné příkazem ''typedef''. Syntaxe příkazu je:

<code c>
typedef definice_typu identifikator_typu;
</code>

Nový datový typ můžeme vytvořit i pro stuktury (viz níže), což vede k pohodlnějšímu používání struktur.

=== Přístup k položkám struktury ===

K položkám struktury se přistupuje operátorem ''.'' (tečka). V případě ukazatele na strukturu pak operátorem ''->'' (šipka) - nahrazuje dereferenci s tečkovým operátorem (viz příklad).\\
Všimněte si, že funkce //vytvorStudenta// vrací ukazatel na strukturu a funkce //vypisStudenta// přijímá ukazatel na strukturu, tj. není vytvářena lokální kopie pro dané funkce a program je efektivnější.

<code c> 
typedef struct {
    char name[20]; /* jmeno studenta */
    float gpa; /* studijni prumer - grade point average */
} Student;

Student* create_student() {
    Student *student = (Student*) malloc(sizeof(*student)); /* v tomto jednoduchem pripade predpokladem uspesnou alokaci pameti */
    printf("Zadejte jmeno: ");
    scanf("%s", student->name); /* jmeno je typu pole znaku, ktere je reprezentovane adresou prvniho znaku */
    printf("Zadejte studijni prumer: ");
    scanf("%f", &student->gpa); /* scanf prijima v parametru adresu, proto referencni operator & */

    return student;
}

void print_student(Student *student) {
    printf("Vypis: %s, %.2f \n", student->name, student->gpa); /* stejne jako (*student).name a (*student).gpa */
}

int main(int argc, char* argv[]) {
    /* inicializace struktury pri deklaraci */
    Student student = {"Chuck Norris", 2};
    student.gpa = 0.5; /* preci jenom se jedna o Chucka, proto upravuje jeho studijni prumer */
    print_student (&student);

    print_student(create_student());
    return 1;
}
</code>

=== Typ union ===

Syntaxe typu union je stejná jako u struktury, místo struct používáme klíčkové slovo union. Hlavní rozdíl je v tom, že struktura alokuje paměť pro všechny položky, typ union zabírá v paměti pouze tolik místa, kolik je potřeba pro uložení největší položky. Z toho vyplývá, že lze použít v jednom okamžiku pouze jednu datovou položku unionu. 

<code c>
typedef union {
  int temperature; /* teplota ohrivace */
  char cooling;   /* stav chlazeni */
} Heater;

typedef struct {
  float temperature;
  Heater state; /* stav je union ve struktuře */
} Wheater; /* pocasi */
</code>

Teplota ohřívače je počítána jen když je teplota nízká, naopak stav chlazení je uváděn jen když je teplota vysoká; pokud je uvedena teplota, položka stav bude mít jen jednu hodnotu.

=== Výčtový typ enum ===

Výčtový typ //enum//, jehož podstata je stejná jako v jazyce Java, je v jazyce C chápán jako náhrada za konstanty vytvářené pomocí makra preprocesoru //#define//. Výčtovým typem je definována množina všech přípustných hodnot proměnné; vnitřně jsou pak tyto konstanty reprezentovány celými čísly zpravidla typu ''int'', případně nejmenšího znaménkového typu, který je schopen rozsah množiny obsáhnout.

<code c>
typedef enum {
  RED, GREEN, BLUE
} Color;
</code>

==== Spojové struktury =====

Podobně jako v jsme si ukazovali v Javě, tak i v C můžeme vytvořit spojový seznam. Místo referenční proměnné využijeme však v C ukazatel na další prvek jako proměnnou typu ukazatel na strukturu.

<code c>
typedef struct _student { /* musime deklarovat typ, abychom se mohli na nej odkaze v deklaraci polozky next */
    char name[30];
    float gpa;
    struct _student *next; /* Ukazatel na sebe sama, Student jeste neni znam proto pouzivame _student */
} Student; /* Student je jmeno zavedeneho typu struktury */

Student *create_student(Student *next) {
    Student *tmp = (Student*) malloc(sizeof (Student));
    printf("Zadejte jmeno: \n");
    scanf("%s", tmp->name);
    printf("Zadejte studijni prumer: \n");
    scanf("%f", &tmp->gpa);
    tmp->next = next;
    return tmp;
}

void print_student(Student *student) {
    printf("%s, %.2f \n", student->name, student->gpa);
}

int main(int argc, char* argv[]) {
    Student *start = NULL, *cur;
    int i;

    for (i = 0; i < 3; i++) /* vytvoreni tri studentu */
        start = create_student(start);

    cur = start;
    while (cur) { /* vypis vytvorenych studentu */
        print_student(cur);
        cur = cur->next;
    }

    return (EXIT_SUCCESS);
}
</code>

===== Úlohy k procvičení =====

==== Struktury ====

  - Vytvořte strukturu popisující entitu osoba s položkami jméno (name), příjmení (surname), typ osoby (type), datum narození (birthdate) a studijní průměr (gpa).
  - Vytvořte výčtový typ enum definující typ osoby - student, učitel (teacher), apod.
  - Napište funkci, která vytvoří jednu osobu na základě dat načtených od uživatele.
  - Vytvořte program, který bude umět:
    - seřadit studenty podle abecedy,
    - seřadit studenty podle studijního průměru,
    - rozdělit studenty na prospěchově podprůměrné a nadprůměrné,
    - vypsat studenty.
 Použijte vhodné dělení do funkcí. Pro řazení si můžete naprogramovat svoji funkci, nebo lépe použijte funkci **qsort** z knihovny stdlib.
<code c>
 void qsort( void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
</code>
Funkce ''qsort'' řadí algoritmem quicksort souvislé pole libovolného typu, na které ukazuje //base// o //nmemb// položkách velikosti //size//. K třídění je použita funkce, na kterou ukazuje //compar//. Funkci //compar()// budou při volání předávány jako argumenty dva prvky z pole //base//. Funkce //compar()// musí vracet zápornou hodnotu, pokud je první argument menší než druhý, nulovou hodnotu pokud se rovnají a kladnou hodnotu pokud je první argument větší než druhý. 

Pro porovnání textových řetězců si napište vlastní funkci nebo využijete funkci ''strcmp'' z knihovny ''string.h''.

 <code c>
int strcmp(const char *s1, const char *s2);
</code>

Pro jednoduchost předpokládejte, že všechny řetězce vždy končí znakem '\0' a jsou správně alokovány.
 
=== Pro pokročilé ===
    - Rozšiřte program o možnost načíst, v programu uchovat a uložit seznam struktur ze souboru (použijte textové i binární soubory).
 
== Příklad uložení/načtení osoby/pole osob typu struktura do/z souboru ==
<code c>
#define FNAME "osoby.txt"

int write_person(Person *person, int number) {
    FILE *f;

    /* otevreni binarni souboru pro zapis */
    if ((f = fopen(FNAME, "wb")) == NULL) {
        printf("Chyba zapisu do souboru %s.\n", FNAME);
        return 1;
    }

    if (number != fwrite(person, sizeof(Person), number, f)) {
        fclose(soubor);
        return 1;
    }

    fclose(f);
    return 0;
}

int read_person(Person *person) {
    FILE *f;
    Person tmp;
    int index = 0;

    /* otevreni binarniho souboru pro cteni */
    if ((f = fopen(FNAME, "rb")) == NULL) {
        printf("Chyba cteni souboru %s.\n", FNAME);
        return 1;
    }

    while (fread(&tmp, sizeof(Person), 1, f) == 1) {
        person[index++] = tmp; /* vyuzivame operatoru prirazeni nad strukturou */
    }

    fclose(f);
    return 0;
}
</code>

Uvedený příklad neřeší alokaci struktury a bude správně fungovat pouze pro jedinou osobu nebo dle alokované paměti odkazované předávanou proměnnou ''person''.

==== Spojové struktury ====

=== Spojový seznam ===

== Jednoduché úlohy ==

Vytvořte spojový seznam uchovávající seznam obdélníků s vlastnostmi šířka, výška a textovým popisem obsahujícím barvu. Seznam si bude uchovávat ukazatel na začátek i ukazatel na konec.
Napište funkce pro   
  - vytvoření prázdného seznamu,
  - zjištění, zda je daný seznam prázdný,
  - vložení jednoho obdélníka na začátek,
  - vložení jednoho obdélníka na konec,
  - výpis seznamu, 
  - zjištění počtu prvků seznamu,
  - zjištění, zda a popř. kolikrát se daný obdélník v seznamu vyskytuje,
  - odebrání jednoho prvku a to:
    - ze začátku,
    - od konce,
    - odebrání prvku, který bude vstupním parametrem funkce. 

== Mírně těžší úlohy ==

Implementujte předchozí úlohy s použitím seřazeného zřetězeného seznamu, od nejmenšího (plošně) po největší obdélník. Tedy například funkce pro vkládání prvku x bude vkládat na příslušnou pozici.

== Středně pracné úlohy ==

Pro seznamy z předchozích kapitol implementujte funkci, která spojí dva seznamy, resp. spojí dva seřazené seznamy v jeden nový, seřazený.

=== Stromy ===

Binární vyhledávací strom (BVT) je datová struktura založená na binárním stromu, v němž jsou jednotlivé prvky  uspořádány tak, aby v tomto stromu bylo možné rychle vyhledávat danou hodnotu. To zajišťují tyto vlastnosti:
  * Jedná se o binární strom, každý uzel tedy má nanejvýš dva syny − levého a pravého.
  * Každému uzlu je přiřazen určitý klíč, my budeme používat celá čísla. Podle hodnot těchto klíčů jsou uzly uspořádány.
  * Levý podstrom uzlu obsahuje pouze klíče menší než je klíč tohoto uzlu.
  * Pravý podstrom uzlu obsahuje pouze klíče větší než je klíč tohoto uzlu.

Příklad BVT ukazuje následující obrázek:

{{:courses:a0b36pr2:labs:bvt.png|}}

Napište a vyzkoušejte funkce pro práci s BVT:
  - vytvoření prázdného BVT,
  - výpis BVT vzestupně a sestupně (použijte rekurzi),
  - vložení jednoho prvku,
  - zjištění existence prvku s daným klíčem,
  - odebrání jednoho prvku,
  - sloučení dvou stromů,
  - nalezení průniku a sjednocení dvou stromů,
  - vyvážení stromu (BVT strom je vyvážený pokud nejvyšší list není výše než nejhlubší list + 1).

===== Volání C z Javy (Java Native Interface) =====

Součástí Java platformy je rozhraní JNI (Java Native Interface), které umožňuje propojit kód běžící na virtuálním stroji Javy s nativními programy a knihovnami napsanými v jiných programovacích jazycích (např. C). Hlavními výhodami jsou zvýšení výkonu v některých low-level úlohách (např. Math.sqrt(double a)) a umožnění komunikace s hardwarovými zařízeními (Bluetooth, apod.). Nevýhodou je především ztráta platformní nezávislosti, protože takový program využívá knihovny zkompilované pro daný operační systém.

{{:courses:a0b36pr2:labs:jni.png?600|}}

Implementace nativní knihovny a propojení s Javou je znázorněno na obrázku výše. Příklad ilustruje vytvoření C knihovny, která vypisuje text "Hello World!" a její volání z Java aplikace. Celý proces implementace je možné shrnout do několika kroků:

  - Vytvoření třídy s deklaracemi nativních metod:
 
<code java>
class HelloWorld {

    static { /* statický inicializátor */
        System.loadLibrary("HelloWorld"); /* načtení dynamické knihovny vytvořené v jazyku C */
    }

    private native void print(); /* deklarace nativní metody */

    public static void main(String[] args) {
        new HelloWorld().print();
    }
}
</code>
    * metoda **loadLibrary(String libname)** slouží k načtení externí systémové knihovny, parametr //libname// zastupuje cestu ke knihovně, 
    * příkazy uvnitř **statického inicializátoru** (static { }) se provádí po zavedení třídy do paměti, ještě před voláním konstruktoru => nejprve se načte externí knihovna a až poté se zpracovává kód třídy,
    * **native** je klíčové slovo pro označení nativní metody, tj. metody vytvořené v jazyku C, kterou budeme volat.
  - Kompilace Java programu:
    * zkompilujte vytvořenou třídu: buď v NetBeans kliknout pravým tlačítkem na název projektu a vybrat "Clean and Build" nebo externím nástrojem javac,
    * v podadresáři "build\classes" projektového adresáře se vytvoří bytecode (.class).
  - Generování hlavičkového souboru:
    * aplikujte nástroj javah (součástí JDK, typicky v C:\Program Files\Java\jdk\bin) na bytecode Java třídy ke generování C hlavičkového souboru (.h) s deklaracemi nativních funkcí. Název bytecode souboru zadejte bez přípony .class: <code>javah -jni HelloWorld</code>
    * ve vytvořeném hlavičkovém souboru je nejdůležitější vygenerovaná deklarace C funkce, která je propojena s Java nativní metodou: <code c>
JNIEXPORT void JNICALL Java_HelloWorld_print (JNIEnv *, jobject);
</code>
  - Implementace deklarovaných funkcí v C: 
    * V NetBeans zvolte //New Project// -> //C/C++ Dynamic Library//.
    * Vytvořený projekt je třeba propojit s JNI knihovnami: 
      * v NetBeans klikněte pravým tlačítkem na název projektu a zvolte //Properties//,
      * na záložce //C Compiler// vyplňte do //Include Directories// cesty k JNI (typicky C:/Program Files/Java/jdk/include a C:/Program Files/Java/jdk/include/win32),
      * na stejné záložce ještě vyplňte //Additional Options// hodnou: <code>-Wl,--add-stdcall-alias -mno-cygwin -shared -m32 -Wall -pedantic</code> 
        * **-Wl,--add-stdcall-alias** nastavuje pro linker přepínač --add-stdcall-alias, který zaručí vytvoření knihovny pro Windows,
        * **-mno-cygwin** zaručí vytvoření knihovny nezávislé na Cygwin,
        * **-shared** indikuje vytvoření dynamické knihovny namísto spustitelného souboru (pokud nepoužíváte NetBeans nebo jste nevytvořili //C/C++ Dynamic Library//),
        * **-m32** indikuje vytvoření 32b knihovny (má význam jen pokud používáte 64b GCC a 32b JDK),
        * **-Wall -pedantic** zaručí výpis všech varovných hlášení a důslednou kontrolu zdrojového kódu podle striktní normy.
    * Do vytvořeného projektového adresáře nakopírujte vygenerovaný hlavičkový soubor a propojte ho s projektem (klikněte pravým tlačítkem myši na //Source Files// a vyberte //Add Existing Item//).
    * Klikněte pravým tlačítkem myši na //Source Files//, vyberte //New// a poté //C Source File//.
    * Do nově vytvořeného souboru přidejte //#include// na JNI, na vytvořený hlavičkový soubor a implementujte deklarované funkce: <code c>
#include <jni.h>
#include <stdio.h>
#include "HelloWorld.h"

JNIEXPORT void JNICALL
Java_HelloWorld_print(JNIEnv *env, jobject obj) {
    printf("Hello World!\n");
    return;
}
</code>
  - Kompilace C programu a generování nativní knihovny:
    * v NetBeans klikněte pravým tlačítkem myši na název projektu a vyberte //Clean and Build//,
    * v podadresáři //dist// projektového adresáře se vytvoří nativní dynamická knihovna (ve Windows .dll, v Unix .so).
  - Spuštění programu java interpretrem
    * překopírujte vytvořenou knihovnu (.dll nebo .so) do Java projektového adresáře nebo do adresáře kde je umístěn spustitelný soubor Java aplikace,
    * bude-li knihovna v jiném adresáři, musíte definovat cestu v metodě loadLibrary(),
    * spusťte Java aplikaci a na obrazovce shlédněte výpis textu „Hello World!“ definovaný v C.

<note tip>
Více informací o JNI můžete nalézt např. v knize [[http://java.sun.com/docs/books/jni/|Java Native Interface: Programmer's Guide and Specification]].
</note>