Diskuze: C++ zásobník
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
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ě.
Jirka:14.1.2019 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
Petan:16.1.2019 3:59
Ahoj Odpověd
- 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].data=vstupniData;
a take
(*novyPrvek).data=vstupniData;
v tomto příipade jsou to instance
na druhy prvek by to bylo
novyPrvek[1].data=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=&nova[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=&nova[x+1];
}
nova[4].dalsi=NULL;
v příkladu
nova[0].dalsi=&nova[1];
nova[1].dalsi=&nova[2];
nova[2].dalsi=&nova[3];
nova[3].dalsi=&nova[4];
nova[4].dalsi=&nova[5]; //chyba nova[5] neexistuje
Doufám že je to trochu srozumitelné
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
Jirka:17.1.2019 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();
}Jirka:17.1.2019 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;
}Jirka:19.1.2019 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!
Jirka:20.1.2019 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;
}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á.
Patrik Valkovič:27.1.2019 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.
Zobrazeno 11 zpráv z 11.