eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingJak usunąć najlepiej element z drzewa ?
Ilość wypowiedzi w tym wątku: 17

  • 1. Data: 2018-03-15 01:57:02
    Temat: Jak usunąć najlepiej element z drzewa ?
    Od: Borneq <b...@a...hidden.pl>

    podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego
    węzła.

    kod:
    #include <memory>
    #include <string>
    #include <vector>
    #include <assert.h>

    using namespace std;

    class Node
    {
    vector<shared_ptr<Node>> childs;
    Node* parent = nullptr;//not shared_ptr! because of memory leaks of
    circular dependency
    int level = 0;
    public:
    string name;
    Node(string name)
    {
    this->name = name;
    }
    ~Node()
    {
    printf("delete %s\n",name.c_str());
    }
    shared_ptr<Node> clone()
    {
    shared_ptr<Node> result = make_shared<Node>(name+"a");
    return result;
    }
    void erase()
    {
    printf("erase from %s\n", name.c_str());
    childs.clear();
    }
    void Add(shared_ptr<Node> node)
    {
    shared_ptr<Node> clone = node->clone();
    childs.push_back(clone);
    clone->parent = this;
    clone->level = level+1;
    for (size_t i = 0; i<node->childs.size(); i++)
    clone->Add(node->childs[i]);
    }
    shared_ptr<Node>& at(int index)
    {
    return childs[index];
    }
    void print()
    {
    for (int i = 0; i<level; i++)
    printf(" ");
    printf("%s->",name.c_str());
    if (parent) printf("%s", parent->name.c_str());
    printf("\n");
    for (size_t i=0; i<childs.size(); i++)
    childs[i]->print();
    }
    };

    int main()
    {
    shared_ptr<Node>root,rootB;
    root = make_shared<Node>("1");
    root->Add(make_shared<Node>("2"));
    root->Add(make_shared<Node>("3"));
    root->at(0)->Add(make_shared<Node>("4"));
    root->at(0)->Add(make_shared<Node>("5"));
    root->at(1)->Add(make_shared<Node>("6"));
    root->at(1)->Add(make_shared<Node>("7"));

    rootB = make_shared<Node>("1b");
    rootB->Add(make_shared<Node>("2b"));
    rootB->Add(make_shared<Node>("3b"));
    rootB->at(0)->Add(make_shared<Node>("4b"));
    rootB->at(0)->Add(make_shared<Node>("5b"));
    rootB->at(1)->Add(make_shared<Node>("6b"));
    rootB->at(1)->Add(make_shared<Node>("7b"));
    // node->Add(root);
    //root->print();printf("\n");
    //rootB->print(); printf("\n");
    root->at(0)->Add(rootB);
    rootB = nullptr;
    //rootB->at(0)->Add(rootB);//tu cykl?
    root->print();
    root->at(0)->erase();
    root->print();
    return 0;
    }


  • 2. Data: 2018-03-15 08:10:14
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Tomasz Kaczanowski <k...@p...onet.pl>

    W dniu 2018-03-15 o 01:57, Borneq pisze:
    > podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego
    > węzła.

    Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć
    samego siebie. Można to na kilka sposobów, w roocie dać root.remove(a),
    albo root.remove(indeks) (bo widzę, indeksami jakimiś tez się
    posługujesz). Które, czy oba, zależy od zastosowań.

    --
    http://kaczus.ppa.pl


  • 3. Data: 2018-03-15 11:35:48
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 15.03.2018 o 08:10, Tomasz Kaczanowski pisze:
    > Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć
    > samego siebie. Można to na kilka sposobów, w roocie dać root.remove(a),
    > albo root.remove(indeks) (bo widzę, indeksami jakimiś tez się
    > posługujesz). Które, czy oba, zależy od zastosowań.
    >

    root.remove(a) nie, bo a może nie być bezpośrednim dzieckiem roota.
    Jak chcę wołać 'a muszę zrobić a->parent.remove(a).
    Problem gdy chcę usunąć roota. Myślałem również aby element składał się
    ze stałej części i zmiennej (dla polimorfizmu), stała byłaby nadpisywana
    a zmienna wymieniana - dla podmiany elementu na poddrzewo, ale to
    działałoby tylko dla wymiany a nie usuwania. Choć można zrobić i to i
    to, podmiana by podmieniała część zmienną, usuwanie usuwało by
    a->parent.remove(a) a dla roota tylko ustawiało by część zmienną na nullptr.


  • 4. Data: 2018-03-15 12:30:31
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Tomasz Kaczanowski <k...@p...onet.pl>

    W dniu 2018-03-15 o 11:35, Borneq pisze:
    > W dniu 15.03.2018 o 08:10, Tomasz Kaczanowski pisze:
    >> Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć
    >> samego siebie. Można to na kilka sposobów, w roocie dać
    >> root.remove(a), albo root.remove(indeks) (bo widzę, indeksami jakimiś
    >> tez się posługujesz). Które, czy oba, zależy od zastosowań.
    >>
    >
    > root.remove(a) nie, bo a może nie być bezpośrednim dzieckiem roota.
    > Jak chcę wołać 'a muszę zrobić a->parent.remove(a).
    > Problem gdy chcę usunąć roota. Myślałem również aby element składał się
    > ze stałej części i zmiennej (dla polimorfizmu), stała byłaby nadpisywana
    > a zmienna wymieniana - dla podmiany elementu na poddrzewo, ale to
    > działałoby tylko dla wymiany a nie usuwania. Choć można zrobić i to i
    > to, podmiana by podmieniała część zmienną, usuwanie usuwało by
    > a->parent.remove(a) a dla roota tylko ustawiało by część zmienną na
    > nullptr.

    Zrob kontener i w nim odpowiednie metody.

    --
    http://kaczus.ppa.pl


  • 5. Data: 2018-03-15 13:34:47
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: "M.M." <m...@g...com>

    On Thursday, March 15, 2018 at 1:57:04 AM UTC+1, Borneq wrote:
    > podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego
    > węzła.

    Dlaczego nie można?

    Pozdrawiam


  • 6. Data: 2018-03-15 13:48:55
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Tomasz Kaczanowski <k...@p...onet.pl>

    W dniu 2018-03-15 o 13:34, M.M. pisze:
    > On Thursday, March 15, 2018 at 1:57:04 AM UTC+1, Borneq wrote:
    >> podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego
    >> węzła.
    >
    > Dlaczego nie można?

    bo pewnie wewnątrz metody musialby delete this wykonać...

    --
    http://kaczus.ppa.pl


  • 7. Data: 2018-03-15 14:17:21
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
    > Zrob kontener i w nim odpowiednie metody.

    Kontener w sensie, że na najwyższym poziomie będzie miał roota?



  • 8. Data: 2018-03-15 14:24:51
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Tomasz Kaczanowski <k...@p...onet.pl>

    W dniu 2018-03-15 o 14:17, Borneq pisze:
    > W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
    >> Zrob kontener i w nim odpowiednie metody.
    >
    > Kontener w sensie, że na najwyższym poziomie będzie miał roota?
    >
    >
    Ze na najwyższym poziomie będzie obiekt zarządzający całością. Taki
    podział na container i nodes. Można dzięki temu uzyskać tez szybszy
    dostęp do obiektów, bo możesz sobie pamiętać roota, ostatni i aktualny,
    co czasami może przyspieszyć wyszukiwanie choćby. Natomiast usuwanie
    roota, to ustawienie jako roota kolejnego elementu itd...

    --
    http://kaczus.ppa.pl


  • 9. Data: 2018-03-15 14:54:37
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 15.03.2018 o 14:24, Tomasz Kaczanowski pisze:
    > W dniu 2018-03-15 o 14:17, Borneq pisze:
    >> W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
    >>> Zrob kontener i w nim odpowiednie metody.
    >>
    >> Kontener w sensie, że na najwyższym poziomie będzie miał roota?

    Robię teraz dziedziczenie:
    mam klonowanie:
    shared_ptr<Node> clone()
    {
    shared_ptr<Node> result = make_shared<Node>();
    result->member1 = member1;
    result->member2 = member2;
    return result;
    }

    Teraz mam: class Num: Node
    mógłbym zrobić:
    shared_ptr<Node> clone()
    {
    shared_ptr<Num> result = make_shared<Num>(parameter);
    result->member1 = member1;
    result->member2 = member2;
    result->member3 = member3;
    return result;
    }

    ale powtarza mi się kod z member1 i member2 czy można zrobić jakąś
    fabrykę klas , nawet zrezygnować z parameter i zamiast
    shared_ptr<Num> result = make_shared<Num>();
    zrobić konstruktor wirtualny i

    shared_ptr<Node> result = make_shared<TypJakoParametr>();
    ?


  • 10. Data: 2018-03-15 18:43:22
    Temat: Re: Jak usunąć najlepiej element z drzewa ?
    Od: "M.M." <m...@g...com>

    On Thursday, March 15, 2018 at 2:54:39 PM UTC+1, Borneq wrote:
    > W dniu 15.03.2018 o 14:24, Tomasz Kaczanowski pisze:
    > > W dniu 2018-03-15 o 14:17, Borneq pisze:
    > >> W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
    > >>> Zrob kontener i w nim odpowiednie metody.
    > >>
    > >> Kontener w sensie, że na najwyższym poziomie będzie miał roota?
    >
    > Robię teraz dziedziczenie:
    > mam klonowanie:
    > shared_ptr<Node> clone()
    > {
    > shared_ptr<Node> result = make_shared<Node>();
    > result->member1 = member1;
    > result->member2 = member2;
    > return result;
    > }
    >
    > Teraz mam: class Num: Node
    > mógłbym zrobić:
    > shared_ptr<Node> clone()
    > {
    > shared_ptr<Num> result = make_shared<Num>(parameter);
    > result->member1 = member1;
    > result->member2 = member2;
    > result->member3 = member3;
    > return result;
    > }
    >
    > ale powtarza mi się kod z member1 i member2 czy można zrobić jakąś
    > fabrykę klas , nawet zrezygnować z parameter i zamiast
    > shared_ptr<Num> result = make_shared<Num>();
    > zrobić konstruktor wirtualny i
    >
    > shared_ptr<Node> result = make_shared<TypJakoParametr>();
    > ?

    Jakich cech brakuje Ci w standardowych implementacjach drzew, że
    implementujesz po swojemu?

    Pozdrawiam

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: