Matematické Fórum

↑ Stýv: No, chci, aby se v průběhu hodnota ukazatele mohla měnit.

↑ Stýv: Šlo, ale měl bych ukazatel na ukazatel. Vzhledem k rekurzivní povaze mé metody Add se toho trochu bojím, nejsem zase tak zkušený programátor. Chytré pointery neznám. Myslíš, že by mému problému nějak pomohly? (zatím neřeším mazání)

↑ Stýv: Pokouším se objektově implementovat binární vyhledávací strom. Když se pokouším vložit nový prvek, podívám se, jestli v daném vrcholu je prázdno nebo není. Pokud je tam prázdno, uložím prvek do daného vrcholu. Pokud není, podívám se, jestli hodnota klíče je menší/větší než klíč v daném vrcholu. Podle toho pak zavolám metodu Add rekurzivně na levý nebo pravý podstrom. Přitom jeden z parametrů Add je právě ukazatel na vrchol daného podstromu. Kdyby tam ale bylo prázdno, vlastně chci tento vrchol měnit, takže to musím předat jako referenci. Proto ta reference na ukazatel.
No a ten implicitní parametr chci proto, že když volám funkci na celý strom, jako parametr se vezme kořen stromu, jehož ukazatel je jeden z atributů stromu. Jenže samozřejmě nikomu nic do žádné adresy kořene není, tam chci jen říct "přidej prvek X do stromu Y". A právě na to použiju implicitní parametr.
(Poznámka: ano, vím, že by šly použít kontejnery a iterátory, ale to není point, chci se na tom spíš učit.)

↑ Stýv: Koukám, že ty bys nevyráběl v rámci stromu nový vrchol, ale rovnou celý podstrom ... to mě nenapadlo. Na ty chytré ukazatele kouknu.

Koukám, pojmenoval jsem tu třídu hloupě Strom, nikoliv Tree; taky jsem přejmenoval NodeNULL na Nic, aby to bylo kompaktnější - občas mám problém vymýšlet názvy pro své třídy a proměnné. Nic to ale na problému nemění.

Poznámka: metody Remove, RemoveMax, RemoveMin nejsou zatím napsané.

Můj kód zatím:

#include <iostream>
#include <conio.h>

using namespace std;

struct Node
{
int obsah;
Node* lSyn;
Node* pSyn;
};

Node* Nic; //Není zapouzdřeno!

class Strom
{
private:
Node* Koren;
int PocetVrcholu;

public:
Strom();
bool Neprazdny();
void Add(int Cislo, Node*& root=Nic, bool Vnejsi=true);
void Remove(int Cislo);
bool Find(int Cislo, Node* root=Nic, bool Vnejsi=true);
void List(Node* root=Nic, bool Vnejsi=true);
int Min(Node* root=Nic);
int Max(Node* root=Nic);
void RemoveMin();
void RemoveMax();
};

Strom::Strom()
{
Koren = NULL;
PocetVrcholu = 0;
};


bool Strom::Neprazdny()
{
if(PocetVrcholu != 0) return true;
 else return false;
};

void Strom::Add(int Cislo, Node*& root, bool Vnejsi)
{
if(Vnejsi) root=Koren;
if(root==NULL) 
 {
 Node* Vrchol = new Node;
 Vrchol->obsah = Cislo;
 Vrchol->lSyn = NULL;
 Vrchol->pSyn = NULL;
 root = Vrchol;
 PocetVrcholu++; 
 cout << "Prave ukladam cislo " << Cislo << " do stromu!" << endl;
 if(PocetVrcholu==1) Koren = root;
 }
 else if(Cislo == (root->obsah)) cout << "Cislo " << Cislo << " jiz bylo ve stromu ulozeno!" << endl;
  else if (Cislo < (root->obsah)) Add(Cislo, root->lSyn, false);
   else Add(Cislo, root->pSyn, false);
};


bool Strom::Find(int Cislo, Node* root, bool Vnejsi)
{
if(Vnejsi) root=Koren;
if(root==NULL) return false;
if(Cislo==(root->obsah)) return true;
 else if(Cislo < (root->obsah)) Find(Cislo, root->lSyn, false);
  else Find(Cislo, root->pSyn, false);
};


int Strom::Max(Node* root)
{
if(root==Nic) root = Koren;
if(root==NULL)
 {
 cout << "Chybne pouziti metody Max() na prazdny strom!";
 exit(0);
 };
if(root->pSyn != NULL) return Max(root->pSyn);
 else return (root->obsah);
};


int Strom::Min(Node* root)
{
if(root==Nic) root = Koren;
if(root==NULL)
 {
 cout << "Chybne pouziti metody Min() na prazdny strom!";
 exit(0);
 };
if(root->lSyn != NULL) return Min(root->lSyn);
 else return (root->obsah);
};


void Strom::List(Node* root, bool Vnejsi)
{
if(Vnejsi) cout << "Tento strom obsahuje "<< PocetVrcholu << " vrcholu: ";
if(root==Nic) root = Koren;
if(root!=NULL) 
 {
 List(root->lSyn, false);
 cout << root->obsah << " ";
 List(root->pSyn, false);
 };
if(Vnejsi) cout << endl;
};

/*
void Strom::Remove(int Cislo, Node*& root, bool Vnejsi)
{

}; */

int main()
{
Strom T;
T.List();
//cout << "Maximum ve stromu: " << T.Min() << endl;
T.Add(4);
T.Add(4);
T.Add(2);
T.Add(1);
T.Add(6);
T.Add(5);
T.Add(8);

for(int i=0; i<10; i++) 
 if(T.Find(i)) cout << "Cislo " << i << " nalezeno!" << endl; 

T.List();

return 0;
};

Promiň, já ten příspěvek vždycky chvilku edituju a opravuju si po sobě chyby.
A ještě: kde se dělá syntax highlighting?

Tady vidím velký špatný...

1) Tvůj problém se vyřeší sám, když se zbavíš zbytečný třídy Strom a metody přesuneš do třídy Node.

2)
a) Vyhoď #include <conio.h>
b) Místo NULL používej nullptr.
c) Místo hloupých ukazatelů použij chytré ukazatele.

3)
a) Zvykni si používat anglické názvy. Čeština ve zdrojáku jednak vypadá divně, jednak tomu nebude skoro nikdo kromě tebe rozumět.
b) Neboj se plýtvat místem, je to pak přehlednější. Tj. např. místo

if(Cislo==(root->obsah)) return true;
 else if(Cislo < (root->obsah)) Find(Cislo, root->lSyn, false);
  else Find(Cislo, root->pSyn, false);

piš

if(Cislo==(root->obsah))
{
    return true;
}
else if(Cislo < (root->obsah))
{
    Find(Cislo, root->lSyn, false);
}
else
{
    Find(Cislo, root->pSyn, false);
}

↑ edison: Fakt to není přehlednější. Když jsem se na to podíval, viděl jsem hned větev pro případ root==NULL a divil jsem se, kde jsou ty ostatní případy. Až když jsem to začal hodně podrobně studovat, zjistil jsem, že jsou zdrcnutý tam dole.

No a co se týká jednořádkových bloků – taky jsem to dělal dřív podobně, ale co když si usmyslíš, že tam chceš přidat třeba nějakej výpis typu "Hodnota už je ve stromu." nebo cokoliv jinýho? Najednou tam ty závorky budeš muset přidat. A nebo na ně zapomeneš, a vyrobíš bug. Proto je lepší i tyhle jednořádkový bloky už od začátku obalit závorkama.

Whitespacy přidávají na přehlednosti. Pokud je nějaká metoda s tímhle formátováním příliš dlouhá (víc než třeba dvě obrazovky), tak je nejspíš blbě napsaná.

Tohle nemám z vlastní hlavy, ale z přednášky Dopručené postupy v programování.

Pokud jde o to formátování, existujou samozřejmě různý konvence, který se v detailech liší, ale ten princip je všude stejnej.

↑ Anonymystik: Pokud ti "hrozně nabobtnává kód a tvoří se šílené vrstvy závorek", tak je problém někde jinde. Coding-style pro linuxový kernel mino jiné říká, že se odsazuje o 8 mezer (sic!) a funkce by se měla vejít na dvě stránky, které mají 80*24 znaků.

Now, some people will claim that having 8-character indentations makes the code move too far to the right, and makes it hard to read on a 80-character terminal screen. The answer to that is that if you need more than 3 levels of indentation, you’re screwed anyway, and should fix your program.

Strom = kořenový vrchol. Pokud opravdu nezbytně potřebuješ počítat vrcholy se složitostí o(1), můžeš udělat nad kořenovým vrcholem tenkou obálku, kde si to budeš pamatovat, nicméně i tak by metoda Tree.Add(n) měla v podstatě jenom volat metodu root.Add(n). Problém tohohle přístupu ovšem je, že pak podstromy toho stromu samy o sobě nejsou stromy, což je poněkud divný.

Na češtinu zapoměň. Pokud budeš někdy něco doopravdy programovat, dřív nebo později na ty zdrojáky bude koukat někdo jinej (kolega z druhýho konce světa, nezávislej vývojář opensource nebo třeba někdo, kdo ti bude chtít poradit na stackoverflow a nebude tomu rozumět). Příklad rozumné konvence je začínat typy a funkce velkým písmenem a proměnné a instance malým.

Z čeho se to C++ učíš? Zřejmě z nějakého zastaralého zdroje, jelikož C++ se zásadně změnilo ve verzi C++11 (z roku 2011).

Používat něco jako Add(Cislo, root->lSyn, false) není OOP. Mělo by to vypadat zhruba jako lSyn.Add(Cislo). Až na ty český názvy.

I když si programuješ pr sebe, měl by ses snažit to dělat pořádně.;-) A stackoverflow by se ti tím spíš mohlo hodit.

Znám akorát toho Průvodce labyrintem algoritmů, podle toho se učí na matfyzu.
Z toho matouška jsem našel jenom krátičkou ukázku, ael podle obsahu je tam zmínka o chytrých ukazatelích až někde vzadu, takže to moc moderním dojmen nepůsobí (přestože je to vydané 2018).

Taky neznám, ale podle obrázků to vypadá obojí dost old-schoolově. Já používám Visual Studio, které rozhodně můžu doporučit.

Možná Code Complete: A Practical Handbook of Software Construction, podle které byla koncipovaná ta přednáška  na Doporučené postupy v programování. Není jenom o OOP, vlastně ani nevím, jak moc se tam OOP reozebírá, ale určitě je tam plno užitečných informací o výrobě softwaru.