Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Prednáška 24

Z Programovanie
Prejsť na: navigácia, hľadanie

Nepreberané črty jazykov C a C++

Na dnešnej prednáške si stručne ukážeme niektoré črty jazykov C a C++, ktoré sme počas semestra nepreberali. Nebudeme preberať väčšie detaily; cieľom je, aby ste neboli príliš prekvapení pri štúdiu existujúcich programov, resp. poskytnúť inšpiráciu pre ďalšie samoštúdium.

Tento materiál nebude vyžadovaný na skúške a ani vám neodporúčame tieto črty jazyka používať, ak ste sa s nimi dostatočne pred skúškou neoboznámili. Dnes vynecháme objektovo-orientované programovanie v jazyku C++. Objektovo-orientovanému programovaniu (v jazyku Java) sa budeme venovať budúci semester.

Jazyk C

  • Jazyk C existuje v rôznych verziách.
  • V starších verziách nefungujú mnohé veci z jazyka C++, ktoré sme bežne používali, napr. komentáre vo forme //, všetky deklarácie premenných musia byť na začiatku funkcie a pod.

Ďalšie typy premenných

  • Celé čísla: short int, long int, unsigned int, ...
    • Veľkosť jednotlivých typov závisí od kompilátora a platformy
  • Desatinné čísla: float (menej presný ako double)
  • V staršom C-čku nie je bool, používa sa int, ktorý má hodnotu 0 pre false a nenulovú (napr. 1) pre true.
  • Typ enum: vymenujeme možné hodnoty, tie sa stanú celočíselnými konštantami: enum farby {biela, cierna, cervena};
  • Zložený typ union: v tom istom mieste v pamäti môže byť jedna z alternatívnych premenných, napr. pri aritmetickom strome by sme mohli uložiť buď smerníky na deti, alebo hodnotu v liste a ušetriť tak trochu pamäti

Príklad: vrchol stromu pre aritmetické výrazy pomocou union (zapísaný v mierne skrátenej syntaxi z C++)

  • Na mojom počítači pôvodná aj nová verzia zaberá 32 bajtov.
    • Smerník aj double zaberajú 8 bajtov, bool aj char 1 bajt
    • Teoreticky by teda mohlo stačiť 18 bajtov s union vs. 25 bajtov bez union
    • Ale kompilátor umiestňuje časti structov na miesta s rýchlejším prístupom.
  • Ak by sme namiesto bool isValue použili rovno char op, zaberala by štruktúra iba 24 bajtov.
#include <iostream>
#include <vector>
using namespace std; 

struct origNode {   /* vrchol stromu z prednasky */
    double val;     /* ciselna hodnota */
    char op;        /* operator '+', '-', '*', '/', 
                     * alebo ' ' ak ide o hodnotu */
    origNode * left;    /* lavy podvyraz alebo NULL */
    origNode * right;   /* pravy podvyraz alebo NULL */
};

struct nodeWithUnion;

struct operatorNode {
    char op;
    nodeWithUnion * left;    /* lavy podvyraz alebo NULL */
    nodeWithUnion * right;   /* pravy podvyraz alebo NULL */
};

struct nodeWithUnion {   /* vrchol stromu pomocou union */
  bool isValue;
  union {
    double val;     /* ciselna hodnota */
    operatorNode o;
  };
};

nodeWithUnion * createOp(char op, nodeWithUnion *left, nodeWithUnion *right) {
    nodeWithUnion *v = new nodeWithUnion;
    v->isValue = false;
    v->o.left = left;
    v->o.right = right;
    v->o.op = op;
    return v;
}

nodeWithUnion * createNum(double val) {
    nodeWithUnion *v = new nodeWithUnion;
    v->isValue = true;
    v->val = val;
    return v;
}

int main() 
{
  cout << "velkost vrchola z prednasky " << sizeof(origNode) <<endl;
  cout << "velkost vrchola s union " << sizeof(nodeWithUnion) << endl;

  nodeWithUnion *v = createNum(1.5);
  cout << v->val << endl;  // spravne pouzitie 
  cout << v->o.op << endl;  // zle pouzitie, nenajde kompilator ani valgrind
}

Operátory

Okrem operátorov, ktoré sme bežne používali, existuje niekoľko ďalších, napríklad:

  • Bitové operátory pracujú s celým číslom ako s poľom bitov (vhodnejšie sú unsigned typy):
    • << a >> posúvajú bity doľava a doprava, zodpovedajú násobeniu a deleniu mocninami dvojky
    • & (and po bitoch), | (or po bitoch), ^ (xor po bitoch), ~ (negácia po bitoch)
  • Ternárny operátor ?: má tvar (podmienka)?(hodnota pre true):(hodnota pre false), napr.
 cout << x << " je " << ((x%2==0) ? "parne" : "neparne") << endl;
  • Pozor na rozdiel medzi a[i++]=0 a a[++i]=0, prehľadnejšie použiť dva príkazy: a[i]=0; i++ alebo i++; a[i] = 0;

Príkaz do-while

Nasledujúce dva spôsoby písania cyklu sú viac-menej ekvivalentné:

do { 
  prikazy;
} while(podmienka)

while(true) {
  prikazy;
  if(!podmienka) break;
}

Makrá a konštanty

  • V C-čku nie sú klasické konštanty, robia sa pomocou makier. Nasledujúce dva riadky majú podobný význam:
#define MAXN 100
const int MAXN=100;
  • Okrem konštánt môžeme definovať aj zložitejšie makrá s parametrami:
/* definicia makra: */
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

/* priklad pouzitia: */
cout << MIN(a*a, b+5);
/* preprocesor dosadi, dostane: */
cout << ((a*a) < (b+5) ? (a*a) : (b+5));
  • Treba dať kopu zátvoriek, aby nedošlo k interakcii s okolím použitia príkazu max

Delenie programu na súbory

  • Väčší program chceme rozdeliť na viac súborov
  • Chceme vytvárať a používať vlastné knižnice - skupiny funkcií s podobným účelom
    • Napríklad knižnica implementujúca funkcie pracujúce so zásobníkom
  • Knižnicu rozdelíme na dva súbory, napr. stack.h a stack.c resp. stack.cpp
  • V hlavičkovom súbore (header file) zadeklarujeme funkcie, ale neuvádzame ich kód, napr.:
typedef int dataType;
struct stack {
    int top;  /* pozicia vrchného prvku zásobníka */
    dataType *items; /* pole prvkov */
};
void init(stack &s);
bool isEmpty(stack &s);
void push(stack &s, dataType data); 
dataType pop(stack &q);
  • Programy, ktoré chcú použiť stack, použijú include na tento súbor
#include "stack.h"
  • V súbore stack.cpp uvedieme kód funkcií, napr.
#include "stack.h"
const int maxN = 100;
void init(stack &s) {
    s.top = -1;
    s.items = new dataType[maxN];
}
...
  • Všimnite si, že v include dávame meno štandardných knižníc v <>, našich vlastných v ""
  • Pri štandardných knižniciach sa v C-čku používa prípona h, v C++ sa namiesto toho väčšinou pridá c na začiatok (že je to knižnica z čistého C)
    • Napr. <cmath> vs. <math.h>
  • Ako zabrániť, aby sa vložilo include viackrát?
    • #ifndef IDENTIFIKATOR #define IDENTIFIKATOR ... #endif
    • Preprocesor umožňuje okrem toho aj ďalšie podmienené príkazy #if VYRAZ ... #else ... #endif alebo #ifdef IDENTIFIKATOR ... #else ... #endif

C nemá posielanie parametrov referenciou

  • ... používame teda smerníky
void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

void swap(int *a, int *b) {
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

Zopár užitočných funkcií

Alokácia pamäte

  • V C-čku sa nepoužíva new a delete, resp. new[] a delete[]
  • Pamäť sa alokuje funkciou malloc, ktorá alokuje kus pamäte s daným počtom bajtov
    • Ak sa nepodarilo, vráti NULL
    • Inak vráti pointer na void, treba pretypovať
    • Veľkosť spočítame operátorom sizeof
#include <stdlib.h>

/* vytvorime pole 100 int-ov */
int *a = (int *)malloc(sizeof(int) * 100);
/* odalokujeme pole a */
free(a);

Triedenie

  • Funkcia qsort z knižnice stdlib.h
  • Dostane pole, počet jeho prvkov, veľkosť každého prvku a funkciu, ktorá porovná dva prvky
    • Funkciu teda posielame ako parameter
    • Táto porovnávacia funkcia dostane smerníky na dva prvky v type void *
    • Vráti záporné číslo, ak prvý prvok je menší, nulu, ak sú rovnaké a kladné číslo, ak prvý je väčší
  • Ak si napíšeme porovnávaciu funkciu, môžeme triediť prvky hocijakého typu
int compare (const void * a, const void * b) {
  return (*(int*)a - *(int*)b);
}
int a[] = {5, 3, 2, 4, 1};
qsort (a, 5, sizeof(int), compare);
  • Podobne je aj funkcia bsearch na binárne vyhľadávanie v utriedenom poli

Odbočka: argumenty typu const

  • v príklade vyššie máme funkciu s hlavičkou int compare (const void * a, const void * b)
  • argument typu const void * a znamená, že programátor sľubuje, že pamäť, kam a ukazuje, nebude meniť
  • ak by sme mali funkciu void f(const int *a) { a = 5; }, kompilátor by vyhlásil chybu
  • ak by sme naopak pri triedení chceli použiť funkciu s hlavičkou int compare (void * a, void * b), kompilátor tiež vyhlási chybu, lebo qsort očakáva const void*, nie void*.
  • preto pri použití štandardných knižníc potrebujete občas na vhodné miesta pridať const
    • dobrá prax je konzistentne dávať const na všetky parametre typu smerník alebo referencia, ktoré funkcia nepotrebuje meniť

Jazyk C++

Generické funkcie

  • Niekedy chceme napísať algoritmus, ktorý by mohol fungovať na veľa rôznych typoch
  • Napr. triediť môžeme celé alebo desatinné čísla, reťazce, zložitejšie štruktúry s určitým kľúčom a pod.
  • Funkcia qsort nám to umožňuje, ale musíme sa zapodievať veľkosťami a pretypovaním, kde sa dajú ľahko narobiť chyby.
  • V C++ sa dajú písať funkcie, ktoré majú typ ako parameter:
template <class T>
T max (T a, T b) {
  return (a>b)? a : b;
}

int i=3;
int j=5;
int k=max<int>(i,j);
  • O generických funkciách sa budeme viac učiť budúci semester.

Preťaženie operátorov

  • Pre naše typy si vieme zadefinovať nové operátory
  • Napr. dve mená porovnávame najskôr podľa priezviska, pri zhode podľa krstného mena
struct meno {
    char *krstne, *priezvisko;
};

bool operator < (const meno &x, const meno &y) {
    return strcmp(x.priezvisko, y.priezvisko)<0
            || strcmp(x.priezvisko, y.priezvisko)==0
            && strcmp(x.krstne, y.krstne)<0;
}
  • Podobne môžeme zadefinovať napr. operátor + a * pre structy reprezentujúce trebárs polynómy alebo komplexné čísla...
  • cout << "Hello" používa preťažený operátor << ak na ľavej strane je stream a na pravej reťazec

String

  • Okrem klasických C-čkových reťazcov môžeme použiť aj typ string z C++.
  • Má elegantnejšie používanie, sám si určuje potrebnú veľkosť pamäte
  • Sú to objekty, do funkcií odovzdávame väčšinou referenciou (cez &)
  • K jednotlivým znakom pristupujeme pomocou [] (ako u polí) alebo pomocou metódy at
#include <string>
using namespace std;

int main(void) {

    char cstr[100] = "Ahoj\n";
    string str = "Ako sa mas?\n";
    string str2;

    /* mozeme priradovat konstantne retazce, C-ckove retazce (polia znamkov)
      aj C++ stringy. */
    str2 = "Ahoj\n";
    str2 = cstr;
    str2 = str;
    /* meranie dlzky */
    cout << "Dlzka je: " << str.length() << endl;

    /* Funguje porovnanie pomocou ==, !=, <,...
     * (bud dvoch C++ stringov, alebo C++ stringu a C stringu)
     * Znamienko + znamená zreťazenie. */
    str2 = cstr + str;
    str2.push_back('X');
    str2.push_back('\n');
    cout << str2;

    if (str < str2) {
        cout << "Prvy je skor" << endl;
    } else if (str == str2) {
        cout << "Rovnaju sa" << endl;
    } else {
        cout << "Druhy je skor" << endl;
    }
}
  • Pomocou funkcie c_str() vieme získať zo stringu premennú typu const char*

Stream

  • Každý textový súbor môžeme chápať ako postupnosť znakov (podobne ako vstup/výstup z konzoly). Teda aj textový súbor je vlastne stream, ktorý môžeme postupne (zľava doprava) čítať alebo do neho zapisovať.
  • Textové súbory teda môžeme načítávať alebo zapisovať pomocou analógie k cin a cout
  • Budeme využívať typy a funkcie zadefinované v knižnici fstream.
#include <fstream>

using namespace std;

int main (void) {
  ofstream o;
  o.open ("test.txt");     // otvorenie súboru
  o << 'z';                // zapíše 1 znak
  o << "Toto je retazec";  // zapíše reťazec 
  o << endl;               // zapíše znak nového riadku
  o << "10*32=" << 10*32 << endl;          // zapíše reťazec a hodnotu výrazu
  o << "1 rovna sa 4? " << (1==4) << endl; // pozor na priority operátorov ... 1==4 musí byť v zátvorkách !!!
  o.close ();              // zatvorenie súboru
}
  • ofstream tiež umožňuje formátovanie výstupu napríklad pomocou modifikátorov fixed,setprecision(),setfill(),setw()
  • Podobne môžeme otvoriť aj súbor, z ktorého budeme čítať vstup. V príklade načítame pole celých čísel.
#include <fstream>
#include <iostream>

using namespace std;
const int MAX=100;

int main (void) {
  ifstream f;
  int pocet, A[MAX];
  
  f.open ("vstup.txt");
  if (f.fail ()) return 1;  // return = návrat z funkcie – koniec programu
  f >> pocet;
  for (int i=0; i<pocet; i++) {
    f >> A[i];
  }

  for (int i=0; i<pocet; i++) {
    cout<< A[i] << " ";
  }
  f.close();
}
  • Pri načítaní sme sa už stretli s funkciou f.fail(), ktorá vrátila true, ak vznikla chyba (väčšinou pri otvorení neexistujúceho súboru). Druhou možnosťou je testovať správne otvorenie pomocou testovania premennej typu ofstream alebo ifstream.
    • technicky ide o preťaženie operátora konverzie na bool resp. na void*, robí negáciu funkcie fail
  ifstream fin("vstup.txt"); // input
  if(!fin) {
    cout << "Cannot open vstup.txt file.\n";
    return 1;
  }

  ofstream fout("vystup.txt"); // output, normal file
  if(!fout) {
    cout << "Cannot open vystup.txt file.\n";
    return 1;
  }
  • Testovanie konca súboru môžeme robiť pomocou funkcie eof
ifstream fin("VSTUP.txt"); // input
char c;

while(!fin.eof()) {
  fin>>c;
  cout<<c;
}
  • Pre streamy je praktická funkcia getline, ktorá načíta zo streamu celý riadok. Nasledovný príklad spočíta v jednotlivých riadkoch počet bodiek.
int main(void){
ifstream f("VSTUP.txt");;
string line;
int poc;

while (getline(f,line)){
 poc=0;
 for (int i=0; i<line.length(); i++){
   if (line[i]=='.') poc++;
 }
 cout << poc <<endl;
}

Niektoré užitočné štruktúry z knižnice STL

STL (standard template library)

  • Veľká knižnica rôznych dátových štruktúr
  • Manuál napr. http://www.cplusplus.com/reference/stl/
  • Generické štruktúry, ktoré môžu uchovávať dáta rôznych typov
    • elegantnejšie ako naše riešenie s dataType
    • v jednom programe môžeme mať štruktúry uchovávajúce rôzne typy
  • Budúci semester sa naučíme pracovať s podobnými štruktúrami v Jave

Štruktúra vector [1]

  • Pole s dynamickou alokáciou pamäte, čo znamená, že ak nestačí pôvodne alokovaný priestor, alokuje si sám väčší.
  • Podobne ako keď sme si to programovali sami počas semestra
  • Deklarovať vector môžeme jedným z nasledujúcich spôsobov
vector<int> A;       //vytvorí pole celých čísel
vector<int> A(10);   //vytvorí pole 10 celých čísel, ktoré všetky nastaví na default hodnotu
vector<int> A(5,1);  //vytvorí pole 5 celých čísel, ktoré nastaví na 1
  • Prístup k prvkom vectora je možný dvoma spôsobmi
    • klasicky pomocou A[index] - podobne ako pri poliach nekontroluje rozsah
    • A.at(index) - v prípade indexu mimo rozsahu program hneď spadne (presnejšie vyhodí výnimku) - nenarobí chaos v pamäti, kde sa potom ťažko hľadá chyba
  • V obidvod prípadoch môžeme aj priraďovať A[index]=value; A.at(index)=value;
  • Vkladanie nových prvkov na koniec uloženej postupnosti
    • A.push_back(x) vloží hodnotu x, podľa potreby alokuje nové polia, presúva a pod.
    • A.size() vráti počet prvkov v poli
    • A.resize(n) alebo A.resize(n, value) zmení počet prvkov v poli na n, pričom buď zahodí nadbytočné prvky alebo pridá nové - tie budú mať hodnotu value alebo default
    • A.capacity() nám povie dĺžku alokovaného poľa a A.reserve(n) nám ju umožní zväčšiť, ale väčšinou sa o tieto implementačné detaily nestaráme
  • Ako generická dátová štruktúra:
  vector<int> A;
  for (int i=0; i<10; i++){
    A.push_back(i);
  }
  for (int i=0; i<A.size(); i++){
    cout << A[i] << endl;     // alebo A.at(i)
  }

Štruktúra map

  • implementuje slovník, pričom zadáme dva typy: kľúč a hodnota
  map <string, string> zoznam;
  zoznam["Jozko Mrkvicka"] = "02/12345678";
  zoznam["Janko Hrasko"] = "02/87654321";
  if(zoznam.count("Jozko Mrkvicka") > 0) {
    cout << zoznam["Jozko Mrkvicka"] << endl;
  }
  // prejdenie vsetkych zaznamov v slovniku pomocou iteratora
  cout << "Vsetky zaznamy:" << endl;
  for(map <string, string>::iterator i=zoznam.begin();
      i!=zoznam.end(); i++) {
    // i->first je meno, i->second je cislo
    cout << i->first << " " << i->second << endl;
  }

Štruktúra dequeue

  • implementuje zásobník aj rad naraz (double-ended queue)
  deque <int> a;
  a.push_back(0);
  a.push_front(1);
  cout << a.back() << endl;
  cout << a.front() << endl;
  a.pop_back();
  a.pop_front();

Algoritmus na triedenie

  • v knižnici <algorithm>
//triedime normalne pole
int A[6] = {1, 4, 2, 8, 5, 7};
sort(A, A + 6);

//triedime vektor
vector <int> A;
sort(A.begin(), A.end());

//triedime podla nasej porovnavacej funkcie, napr. podla absolutnej hodnoty
struct cmp {
    bool operator()(int x, int y) { return abs(x) < abs(y); }
};
cmp c;
sort(A.begin(), A.end(), c);

Range-based for loop (v štandarde C++11)

  • Špeciálny cyklus cez prvky vektora a pod.
    • nepotrebujeme zavádzať premennú pre index
    • podobný for cyklus uvidíme podrobnejšie v Jave
  • Štandard C++11 musíme zapnúť v kompilátore, napr. g++ -std=c++11
    • Implementácia tohto štandardu ešte nemusí byť úplná
#include <iostream>
#include <vector>
using namespace std; 

void vypis(const vector<int> &a) {
  // vypise vsetky prvky vektora a
  for (const int &value : a) { 
    cout << value << ' ';
  }
  cout << '\n';  
}

int main() 
{
  vector<int> a;

  // do vektora a vlozi prvky 0,..,5
  for(int value : {0,1,2,3,4,5}) {
    a.push_back(value);
  }

  vypis(a);  // vypise 0 1 2 3 4 5
 
  // zvysi kazdy prvok vektora o 1
  for (int &value : a) { 
    value++;
  }

  vypis(a); // vypise 1 2 3 4 5 6
}