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.


Cvičenia 9

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

Cieľom dnešného cvičenia je precvičiť si prácu so spájanými zoznamami.

Smerníky na struct

Majme nasledujúce definície premenných:

struct volaco { 
    int x;
    int *y;
};
volaco * a[3];  // pole 3 smernikov na volaco
volaco v;       
volaco *p;     

Akých typov sú nasledovné výrazy? (t.j. do premennej akého typu by sme ich mohli priradiť?)

  • *(p->y)
  • &(v.x)
  • &(a[2])
  • p->y[p->x]

Skúste inicializovať premenné a, v a p (a príslušné časti štruktúr volaco) tak, aby všetky tieto výrazy pracovali len s platnými miestami v pamäti.

Funkcie so spájanými zoznamami

Do kostry programu nižšie doprogramujte požadované funkcie na prácu s jednosmernými spájanými zoznamami. V kostre už je naprogramované načítanie dvoch zoznamov, zavolanie týchto funkcií, výpis výsledkov a uvoľnenie pamäte. Pri hľadaní chýb vo vašom programe môžete skúsiť použiť aj nástroj valgrind. Môžete použiť aj ďalšie funkcie na prácu so zoznamom z prednášky 16.

  • Napíšte funkciu vyhod(linkedList &z), ktorá z jednosmerného spájaného zoznamu vyhodí všetky záznamy, v ktorých má položka data nulovú hodnotu. Pozor, takéto záznamy sa môžu vyskytovať aj na začiatku zoznamu. Vyhodené položky zoznamu treba odalokovať.
  • Napíšte funkciu kopiruj(linkedList &kam, linkedList &odkial), ktorá vytvorí kópiu zoznamu odkial a uloží ju do zoznamu kam (zoznam kam je na začiatku prázdny).
  • Napíšte funkciu zip(linkedList &z1, linkedList &z2, linkedList &z3), ktorá vytvorí z dvoch zoznamov ich "zips" - vo výslednom zozname sa budú postupne striedať prvky z prvého a druhého zoznamu. Pokiaľ má jeden zoznam viac prvkov ako ten druhý, tak jeho zvyšné prvky budú na konci zoznamu.
 zip({1,2,3}, {10,11,12,13,14}) = {1,10,2,11,3,12,13,14}
  • Napíšte funkciu zip2, ktorá podobne vytvorí zips dvoch zoznamov, ale prvky iba preusporiada (nebude ich kopírovať a vytvárať nové node-y). Node-y teda treba iba presunúť zo z1 a z2 do z3 a vhodne zmeniť pointre.
  • Napíšte funkciu reverse(linkedList &z), ktorá otočí poradie prvkov v zozname (jednosmernom spájanom).

Kostra programu pre precvičenie spájaných zoznamov

#include <iostream>
#include <cassert>
using namespace std;

/* štruktúra pre uzol jednosmerného zoznamu */
struct node {
    int data;  // data v uzle
    node* next;  // dalsi uzol v zozname
};

/* štruktúra pre jednosmerný spájaný zoznam */
struct linkedList {
    node* first;  // smerník na prvý prvok
};

/* inicializacia prazdneho zoznamu */
void init(linkedList &z) {
    z.first = NULL;
}

/* vypis zoznamu */
void print(const linkedList &z) {
    node* x = z.first;
    while (x != NULL) {
        cout << " " <<  x->data;
        x = x->next;
    }
    cout << endl;
}

/* nacitanie zoznamu zo vstupu */
void read(linkedList &z) {
    assert(z.first == NULL);
    int x;
    cin >> x;
    node **v = &(z.first);  // v je smernik na posledny smenrik v zozname
    while (x != -1) { // kym uzivatel nezada -1
        (*v) = new node;
        (*v)->data = x;
        (*v)->next = NULL;
        v = &((*v)->next);
        cin >> x;
    }
}

/* uvolnenie pamati pre zoznam */
void destroy(linkedList &z) {
    while (z.first != NULL) {
        node* p = z.first;
        z.first = z.first->next;
        delete p;
    }
}

/* funkcia zo zoznamu vyhodí všetky záznamy, v ktorých je data==0 */
void vyhod(linkedList &z) {
    // TODO: VAS KOD TU
}

/* funkcia vytvorí kópiu zoznamu odkial a uloží ju do zoznamu kam
 * (zoznam kam je na začiatku prázdny) */
void kopiruj(linkedList &kam, linkedList &odkial) {
    // TODO: VAS KOD TU
}

/* funkcia vytvorí z dvoch zoznamov ich "zips":
 * vo výslednom zozname sa striedajú prvky z prvého a druhého zoznamu.
 * Ak je jeden zoznam dlhší, jeho zvyšné prvky budú na konci zoznamu. */
void zip(linkedList &z1, linkedList &z2, linkedList &z3) {
    // TODO: VAS KOD TU
}

/* funkcia otočí poradie prvkov v zozname */
void reverse(linkedList &z) {
    // TODO: VAS KOD TU
}

int main(void) {
    linkedList z1;
    init(z1);
    cout << "Zadaj zoznam z1 ukonceny -1: ";
    read(z1);

    linkedList z2;
    init(z2);
    cout << "Zadaj zoznam z2 ukonceny -1: ";
    read(z2);

    cout << "Vyhadzujem nuly z z1:";
    vyhod(z1);
    print(z1);

    linkedList z3;
    init(z3);
    cout << "Kopirujem z1 do z3:";
    kopiruj(z3, z1);
    print(z3);

    linkedList z4;
    init(z4);
    cout << "Zipsujem z1 a z2 do z4:";
    zip(z1, z2, z4);
    print(z4);

    cout << "Otacam z1:";
    reverse(z1);
    print(z1);

    destroy(z1);
    destroy(z2);
    destroy(z3);
    destroy(z4);
}