Java týden Java týden
Pouze tento týden sleva až 80 % na celý Java e-learning!
Brno? Vypsali jsme pro vás nové termíny školení OOP v Brně!

Diskuze: C++ zásobník

Aktivity (2)
Avatar
Dominik Baričák:18.12.2018 19:19

Ahoj,
Mám problém s pochopením zásobníku. Učitel nám zadal úkol vytvořit zásobník. Zde je jeho kód:

#include <iostream>

using namespace std;


struct uzel{
    int data;
    uzel *dalsi=NULL; /*prostor pro adresu dalsiho prvku*/
};

uzel *vrchol=NULL; /*NULL je kvuli inicializaci zasobniku*/

void push(int vstupniData){
    uzel *novyPrvek =new uzel; /*pomocna promenna pro vytvoreni prvku*/
    cout<<"vytvarim dalsi prvek:"<<novyPrvek<<endl;
    novyPrvek->data=vstupniData;
    novyPrvek->dalsi=vrchol; /*napojeni noveho prvku na vrchol*/
    vrchol=novyPrvek; /*vrchol posuneme na novy prvek*/
    cout<<vrchol->data<<" "<<endl;
}


void print(uzel *vstup){
    cout<<endl;
    cout<<"************"<<endl;
    while(vstup!=NULL){
        cout<<vstup->data<<" ";
        cout<<vstup<<endl;
        vstup=vstup->dalsi;
    }
    cout<<endl<<"************"<<endl;
}


int main()
{



    for(int i=0;i<=50;i++){
       push(i);
    }

    print(vrchol);




}

Chápu princip, ale nedokážu pořádně pobrat co se přesně v jednotlivých krocích dějě. Za úkol máme napsat ještě jednu funkci, která bude jednotlivé prvky mazat. Abych něco takového mohl napsat musím pochopit pořádně všechny kroky. Zkusím vám tedy napsat jak jednotlivé kroky chápu já:

Ve funkci push:
vytvořím instanci struktury s názvem novyPrvek ve které se budou data rovnat jednotlivým iteracím cyklu. Další kroky si neumím pořádně vysvětlit a představit. Moc by mi pomohlo, kdyby mi někdo popsal co se ve funkci push děje dál.

Jelikož jsem si tohle představit nedokázal snažil jsem se stejného výsledku docílit jiným kódem:

#include <iostream>

using namespace std;

struct struktura{
int data=0;
struktura *dalsi;
}nazev;

struktura *ukazatel;

int main()
{
struktura* nova=new struktura[5];

for(int x=0;x<=5;x++){
nova[x].data=x;
}

for(int x=0;x<=5;x++){ //nefunguje
nova[x].dalsi=&no­va[x++];

}

nova[0].dalsi=&no­va[1];
nova[1].dalsi=&no­va[2];
nova[2].dalsi=&no­va[3];
nova[3].dalsi=&no­va[4];
nova[4].dalsi=&no­va[5];

ukazatel=&nova[0];

cout<<ukazatel->dalsi->dalsi->dalsi->data;

}

**Zde nechápu dvě věci: **

1)
Když vytvořím jen jednu instatnci na heapu: struktura* nova=new struktura; (přistupuje se k jednotlivých prvkům přes dereferenci ->). Pokud však vytvořím více instancí: struktura* nova=new struktura[5]; (musím již k prvkům přistupovat pomocí tečky). Proč?

2)
for(int x=0;x<=5;x++){ //nefunguje
nova[x].dalsi=&no­va[x++];

}

nova[0].dalsi=&no­va[1];
nova[1].dalsi=&no­va[2];
nova[2].dalsi=&no­va[3];
nova[3].dalsi=&no­va[4];
nova[4].dalsi=&no­va[5];

ukazatel=&nova[0];

Cyklus má dělat přesně to co je pod ním. Avšak pokud smažu vše pod cyklem kromě: ukazatel=&nova[0]; kód nefunguje. Netuším proč.

Děkuji za všechny rady

Zkusil jsem: Přijít na to sám

Chci docílit: Vytvořit zásobník instancí.

 
Odpovědět 18.12.2018 19:19
Avatar
SolusLupusUmbra
Redaktor
Avatar
SolusLupusUmbra:19.12.2018 16:21

Ahoj, nevím, jak hluboké jsou tvé znalosti, tak se předem omlouvám, jestli budu vysvětlovat něco, co znáš.
Tvoje implementace je založena na poli, tudíž nepotřebuješ odkaz na předchozí prvek. Učitelův kod je spojitý seznam (LinkedList). V následujícím odstavci se pokusím vysvětlit rozdíl.

  • Pole je struktura, kde se můžeš na každý prvek dostat pomocí jeho indexu, o indexy se pole stará samo. U spojitého listu má každý prvek odkaz na prvek předchozí.
  • Zásobník funguje obdobně jako zásobník u zbraně - svrchu do něj postupně dáváš náboje. Vždy vidíš jen ten poslední, ten také bude vystřelen.

### Jak funguje učitelova funkce push
na začátku máš připravený první "náboj", proměnná vrchol, ten by nyní byl vystřelený. Pokud zavoláš push s daty, vytvoří se nový "náboj" (uzel *novyPrvek =new uzel;), naplní se daty (novyPrvek->data=vstupniData;) a nastaví se, že po něm je na řadě ten původní (novyPrvek->dalsi=vrchol;). Nakonec se nastaví, že první - navrchu zásobníku - je ten nový "náboj" ( vrchol=novyPrvek; ) a ten je také v proměnné vrchol.
ve funkci push nevytvoříš instanci struktury s názvem novyPrvek ve které se budou data rovnat jednotlivým iteracím cyklu. Funkcí push k existující struktuře přidáváš další prvky.
Doufám, že jsem to vysvětlil srozumitelně.

 
Nahoru Odpovědět  +1 19.12.2018 16:21
Avatar
Jirka
Člen
Avatar
Odpovídá na Dominik Baričák
Jirka:14. ledna 7:40

Ahoj,

zkus omrknout takovýto kód dvou zásobníčků v Javě, která vychází z C++.

První zásobník využívá pevně alokované pole, takže může "přetéci". Druhé pole jen tak nepřeteče, protože si samo alokuje případné další místo v paměti, ale zase je o něco pomalejší.

package itn.forum;

class Zasobnik {
private int[] data = new int[20];
private int hloubka;
public int count() { return hloubka; }
public Zasobnik() { hloubka = 0; }
public void push(int value) {
        if(hloubka + 1 == data.length) {
                throw new java.lang.StackOverflowError("Preteceni zasobniku");
        }
        data[hloubka] = value;
        hloubka ++;
}
public int pop() {
        if(hloubka == 0) {
                throw new java.lang.IllegalStateException("Zasobnik je prazdny, nelze vybrat.");
        }
        hloubka --;
        return data[hloubka];
}
public int peek() { return data[hloubka]; }
}

class Uzel2 {
private int val;
private Uzel2 nasl;
public Uzel2 nasledujici() { return nasl; }
public int dejHodnotu() { return val; }
public Uzel2(int value, Uzel2 nasledujici) { val = value; nasl = nasledujici; }
}

class Zasobnik2 {
private Uzel2 prvni;
private int hloubka;
public int count() { return hloubka; }
public Zasobnik2() { prvni = null; hloubka = 0; }
public void push(int value) {
        prvni = new Uzel2(value, prvni.nasledujici());
        hloubka ++;
}
public int pop() {
        if(hloubka == 0) {
                throw new java.lang.IllegalStateException("Zasobnik je prazdny, nelze vybrat.");
        }
        hloubka --;
        int docasnaHodnota = prvni.dejHodnotu();
        prvni = prvni.nasledujici();
        return docasnaHodnota;
}
public int peek() { return prvni.dejHodnotu(); }

public static void main(String[] args) {
}
}

hth

Nahoru Odpovědět 14. ledna 7:40
Kdo nic nedělá, nic nezkazí.
Avatar
Petan
Člen
Avatar
Odpovídá na Dominik Baričák
Petan:16. ledna 3:59

Ahoj Odpověd

  1. na adresu objektu se chodi přes -> a instanci přes tečku

Návratová hodnota dynamicky vytvořeného objeku je adresa (příkazy Objekt* pObj = new Objekt. malloc ...] nebo adresa na prvni objekt (Objekt* pObj = new Objekt[10];)
a statickeho je instance (Objekt obj) nebo adresa na prvni objekt (Objekt pObj[10];)
index adresy objektu je instance pObj[0] = prvni instance objeku a je totožna s (*pObj) třeti instance je pObj
[2]
přiklad
uzel *novyPrvek =new uzel;vytvoreni dynamicke instance obkektu uzel novyPrvek je adresa
totožne
uzel *novyPrvek =new uzel[1];
vytvoreni dynamicke instance obkektu uzel novyPrvek je adresa
novyPrvek->data=vstupniData;
lze zapsat teoreticky i
novyPrvek[0].da­ta=vstupniData;
a take
(*novyPrvek).da­ta=vstupniData;
v tomto příipade jsou to instance
na druhy prvek by to bylo
novyPrvek[1].da­ta=vstupniData;
nebo divočejší
(&novyPrvek[1])->data=vstupniData;

Bod 2
for(int x=0;x<=5;x++){ //nefunguje i predchazejici for zde se prochazi 6 instanci (vytvorených je 5) !
nova[x].dalsi=&no­va[x++]; //tedy nelze použít v indexu x++ ale x+1

}
by mělo být
for(int x=0;x<4;x++)
{
nova[x].dalsi=&no­va[x+1];
}
nova[4].dalsi=NULL;

v příkladu
nova[0].dalsi=&no­va[1];
nova[1].dalsi=&no­va[2];
nova[2].dalsi=&no­va[3];
nova[3].dalsi=&no­va[4];
nova[4].dalsi=&no­va[5]; //chyba nova[5] neexistuje

Doufám že je to trochu srozumitelné

 
Nahoru Odpovědět 16. ledna 3:59
Avatar
Jirka
Člen
Avatar
Jirka:17. ledna 18:33

Ahoj,

ještě bych tu pro tebe měl jednu verzičku, aby sis jí prošel a ev. vyzkoušel.

class Uzel
{
private:
    int hod;
    Uzel* nasl;
public:
    Uzel(int hodnota, Uzel* nasledujici)
    {
        hod = hodnota;
        nasl = nasledujici;
    }
    Uzel(int hodnota)
    {
        hod = hodnota;
        nasl = nullptr;
    }
    ~Uzel(void) {}
    Uzel* nasledujici()
    {
        return nasl;
    }
    int dejHodnotu(void)
    {
        return hod;
    }
};

class Zasobnik
{
private:
    Uzel* prvni = nullptr;
public:
    void vloz(int hodnota) //push
    {
        prvni = new Uzel(hodnota, prvni);
    }
    int vrchol(void) //peek
    {
        return prvni;
    }
    int vezmi(void) //pop
    {
        int docasnaHodnota = prvni->dejHodnotu();
        Uzel* odstranovanyVrchol = prvni;
        prvni = prvni->nasledujici();
        delete odstranovanyVrchol;
        return docasnaHodnota;
    }
    void tiskni(void)
    {
        cout << std::endl;
        Uzel* docasnyUkazatel;
        while((docasnyUkazatel = prvni->nasledujici()) != nullptr)
        {
            cout << std::endl << "hodnota je: " << std::to_string(docasnyUkazatel->dejHodnotu());
        }
    }
};

int main()
{
        Zasobnik* zasobnik = new Zasobnik();
        zasobnik->tiskni();
        zasobnik->vloz(0);
        zasobnik->vloz(1);
        zasobnik->vloz(2);
        zasobnik->tiskni();
        cout << std::endl << "tato hodnota je nyni na vrcholu: " << std::to_string(zasobnik->vrchol());
        zasobnik->tiskni();
        zasobnik->vezmi();
        zasobnik->vezmi();
        zasobnik->vezmi();
        zasobnik->tiskni();
        return 0;
}

HTH

Editováno 17. ledna 18:36
Nahoru Odpovědět 17. ledna 18:33
Kdo nic nedělá, nic nezkazí.
Avatar
Jirka
Člen
Avatar
Odpovídá na Jirka
Jirka:17. ledna 18:42

Omlouvám se,

ještě oprava; ve třídě Zasobnik, metoda vrchol, má být zdrojový text takto:

int vrchol(void) //peek
{
        return prvni->dejHodnotu();
}
Nahoru Odpovědět 17. ledna 18:42
Kdo nic nedělá, nic nezkazí.
Avatar
Jirka
Člen
Avatar
Odpovídá na Jirka
Jirka:17. ledna 18:54

Ještě jsem objevil chybku ve fci main:

int main()
{
        Zasobnik* zasobnik = new Zasobnik();
        zasobnik->tiskni();
        zasobnik->vloz(0);
        zasobnik->vloz(1);
        zasobnik->vloz(2);
        zasobnik->tiskni();
        cout << std::endl << "tato hodnota je nyni na vrcholu: " << std::to_string(zasobnik->vrchol());
        zasobnik->tiskni();
        zasobnik->vezmi();
        zasobnik->vezmi();
        zasobnik->vezmi();
        zasobnik->tiskni();
        delete zasobnik;
        return 0;
}
Nahoru Odpovědět 17. ledna 18:54
Kdo nic nedělá, nic nezkazí.
Avatar
Jirka
Člen
Avatar
Odpovídá na Dominik Baričák
Jirka:19. ledna 21:06

Ahoj.

Tak jsem to konečně nějak zpracoval v C++. Musíš to ještě zkouknout, dodělat jeden destruktor tridy Stack, který ale je svoji strukturou velice podobný Stack-metodě print. Držím palce!

class Node
{
private:
        int val;
        Node* prev;
        Node* nxt;
public:
        Node(Node* previous, Node* next, int value)
        {
                prev = previous;
          nxt = next;
                val = value;
        }
        ~Node(void) {}
        Node* getPrevious(void) { return prev; }
        void setPrevious(Node* previous) { prev = previous; }
        Node* getNext(void) { return nxt; }
        void setNext(Node* next) { nxt = next; }
        int get(void) { return val; }
        void set(int value) { val = value; }
};

class Stack
{
private:
  Node* first;
  Node* last;
public:
        Stack(void) { first = nullptr; last = nullptr; }
        ~Stack(void) {
                // chybi kod, ktery odebere vsechny alokovane Nody
        }
        void push(int value) {
                first = new Node(nullptr, first, value);
        }
        int peek(void) {
                return first->get();
        }
        int pop(void) {
                if(first == nullptr) { cout << endl << "Chyba, vyber z prazdneho zasobniku."; }
                int navratovaHodnota = first->get();

                Node* temp = first->getNext(); // temp ukazuje pod prvni, ktery je novy aktualni
                if(temp != nullptr) {
                        temp->setPrevious(nullptr); // prvni odebirame
                }

                delete temp;
                return navratovaHodnota;
        }
        void print(void) {
                cout << std::endl;
                Node* ptr = first;
                while(ptr != nullptr) {
                        cout << std::endl << "hodnota je: " << std::to_string(ptr->get());
                        ptr = ptr->getNext();
                }
        }
};

int main()
{
        Stack* st = new Stack();
        st->print();
        st->push(0);
        st->push(1);
        st->push(2);
        st->print();
        cout << std::endl << "tato hodnota je nyni na vrcholu: " << std::to_string(st->peek());
        st->print();
        st->pop();
        st->pop();
        st->pop();
        st->print();
        delete st; // zde zatim nehotovo a konci chybou
        return 0;
}

HTH!

Nahoru Odpovědět 19. ledna 21:06
Kdo nic nedělá, nic nezkazí.
Avatar
Jirka
Člen
Avatar
Odpovídá na Dominik Baričák
Jirka:20. ledna 16:07

Ahoj.

Tak jsem to poladil a funguje mi to, včetně pop a destruktoru. Hodně štěstí.

class Node
{
private:
        int val;
        Node* prev;
        Node* nxt;
public:
        Node(Node* previous, Node* next, int value)
        {
                prev = previous;
                nxt = next;
                val = value;
        }
        ~Node(void) {}
        Node* getPrevious(void) { return prev; }
        void setPrevious(Node* previous) { prev = previous; }
        Node* getNext(void) { return nxt; }
        void setNext(Node* next) { nxt = next; }
        int get(void) { return val; }
        void set(int value) { val = value; }
};

class Stack
{
private:
  Node* first;
//  Node* last;
public:
        Stack(void) { first = nullptr; }
        ~Stack(void) {
                cout << std::endl << "Uvolnuji pamet zasobniku.";
                Node* ptr = first;
                Node* tptr;
                while(ptr != nullptr) {
                    tptr = ptr;
                    ptr = ptr->getNext();
                    delete tptr;
                }
        }
        void push(int value) {
                first = new Node(nullptr, first, value);
        }
        int peek(void) {
                return first->get();
        }
        int pop(void) {
                if(first == nullptr) { cout << endl << "Chyba, vyber z prazdneho zasobniku."; }
                int navratovaHodnota = first->get();

                Node* ptr = first->getNext(); // bude vrcholem
                if(ptr != nullptr) {
                        ptr->setPrevious(nullptr);
                }
                else {
            first = nullptr;
//              last = nullptr;
                }

                delete first;
                first = ptr;
                return navratovaHodnota;
        }
        void print(void) {
                cout << std::endl;
                Node* ptr = first;
                while(ptr != nullptr) {
                        cout << std::endl << "hodnota je: " << std::to_string(ptr->get());
                        ptr = ptr->getNext();
                }
        }
};

int main()
{
        Stack* st = new Stack();
        st->print();
        st->push(0);
        st->push(1);
        st->push(2);
        st->print();
        cout << std::endl << "tato hodnota je nyni na vrcholu: " << std::to_string(st->peek());
        st->print();
        st->pop();
        st->pop();
        st->pop();
        st->print();
        delete st;
        return 0;
}
Nahoru Odpovědět 20. ledna 16:07
Kdo nic nedělá, nic nezkazí.
Avatar
Dominik Baričák:27. ledna 13:17

Děkuji všem za pomoc! S vaší pomocí a hromadou čtění o ukazatelích jsem si nakonec svůj zásobník i s odstraňovaním prvků udělal a myslím, že ho z většiny chápu. Ale přecejenom jsem nazil na pár problémů, které si nedokážu vysvětlit. Zásobník jsem pro moji jednoduchost psal jen se strukturou a bez funkcí. Moje otázka zní: jaký je rozdíl mezi třemi cykly dole ve zdrojáku? V každém z nich jsem se snažil vytváření prvků a jejich propojení rozchodit trochu jinak. Ke každému z nich napíšu co se v něm podle mého děje a co nechápu.

Zásobník:

#include <iostream>

using namespace std;

struct struktura{
    int data;
    struktura*dalsi;
};

struktura*ukazatel;

int main()
{
      struktura*objekt=new struktura; //vytvořím první dynamicky vytvořený objekt

      for(int x=0;x<=10;x++){
        objekt++;  /*při každé iteraci posunu adresu objektu do paměti někam jinam např. 01, 02*/
        objekt->data=x; /*objekt na adrese 01 bude mít v datech 0, objekt na adrese 01 bude mít v datech 1*/
        objekt->dalsi=ukazatel; /*objekt na adrese 01 bude mít v ukazateli dalsi hodnotu NULL, objekt na adrese 02
        bude mít v ukazateli dalsi adresu objektu 02*/
        ukazatel=objekt; /*ukazatel bude nyní ukazovat na adresu objektu 01, ukazatel bude nyní ukazovat na adresu
        objektu 02*/
    } /*timto jsem vlastne propojil jednotlivé objekty diky ukazateli, který mi vždy podrzel predchozi objekt. Otázka:
        co se stane s kazdym nove vytvořeným objektem při každé iteraci? Zmizí? Proč nemůžu napsat: cout<<objekt[5].data? Jediné co můžu napsat je: cout<<objekt->dalsi->dalsi->data;*/


        for(int x=0;x<=10;x++){ /*tohle je dle mě stejné jako předchozí cyklus. Je to tak? S tím rozdílem, že nemůžu
        napsat: cout<<objekt->dalsi->dalsi->data; jelikož je uvnitř cyklu */
        struktura*objekt=new struktura;
        objekt->data=x;
        objekt->dalsi=ukazatel;
        ukazatel=objekt;
    }



      struktura*objekt=new struktura[10]; /*zde jsem vyresil problem při kterém nemuzu napsat:
      cout<<objekt[5].data; ale pro změnu nemuzu přes ukazatel přistoupit k dalšímu prvku.*/
      for(int x=0;x<=10;x++){
        objekt[x].data=x;
        objekt[x].dalsi=ukazatel; /*zde me jeste napadlo udelat to takhle: objekt[x].dalsi=objekt+1;*/
        ukazatel=objekt;
    }
     cout<<objekt[5].data;



    cout<<"kolik prvku chces odstranit?: "<<endl;
    int pocet;
    cin>>pocet;

    for(int x=0;x<pocet;x++){
        cout<<"odstranujes tyto prvky: "<<ukazatel->data<<endl;
        ukazatel=ukazatel->dalsi;
    }

    while(ukazatel!=NULL){
        cout<<ukazatel->data;
        ukazatel=ukazatel->dalsi;
    }


}

Děkuji za vysvětlení aspoň pár části těch blbostí a nesmyslů co jsem vytvořil. Omlouvám se za přehlednost, ale mám z toho v hlavě guláš a podle toho to vypadá.

Editováno 27. ledna 13:19
 
Nahoru Odpovědět 27. ledna 13:17
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Dominik Baričák
patrik.valkovic:27. ledna 16:37

První cyklus je úplně špatně. Za prví při volání objekt++ ztratíš ukazatel na původní objekt, nemůžeš ho tedy uvolnit a máš memory leak. Ale hlavně, příkazem objekt++ se dostaneš do paměti, kterou jsi nealokoval, nevíš tedy co na ní je ani jestli do ní můžeš zapisovat. Divím se, že program nehavaroval.

Ve druhém cyklu je zase memory leak (objekt vytvořený nahoře není uvolněn). V příkazu objekt->dalsi = ukazatel přiřazuješ prvnímu vytvořenému objektu ukazatel, ale ten není inicializovaný. Dle standardu je inicializován na NULL,ale stejně bych jej raději inicializoval.

Ve třetím případě vytváříš pole. Nemusíš mít tedy ukazatel na další prvek, protože ten je další v poli (jak jsi v komentáři podotknul). Nicméně zase neuvolníš původní objekt, takže máš memory leak. Btw taky si všimni, že spojový seznam inicializuješ obráceně (tj, poslední prvek listu s hodnotou 0 je na indexu 0).

No a jak jsem několikrát řekl, ani jednou neuvolníš paměť, takže máš memory leak a program drží více paměti než potřebuje.

Nahoru Odpovědět  +1 27. ledna 16:37
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 11 zpráv z 11.