VPF::Помогите оптимизировать - Форум программистов

toxx

Дата 26.4.2010, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

Есть структура данных n- мерного дерева

Код


struct Tree
{
    int d;
    Vector<Tree *> Trees;
};

я создаю дерево в 2 шага
1.Создаю корень

Код


Tree* first(int d)
{
    Tree *pv=new Tree;
    pv->d=d;
    cout<<"Kol-vo vershin y  kornya"<<endl;
    int count;
    cin>>count;
    pv->Trees.resize(count);
    return pv;
}

2. Остальное дерево

Код


Tree* insert(Tree* root)
{
    Tree* pv=root,*prev=root;
    Tree* pTree;
    prev=pv;
    if(pv->Trees.size()!=0)
    {
        for(size_t i=0;i<pv->Trees.size();i++)
        {
            pTree=new Tree;
            cout<<"i= "<<i<<endl;
            cout<<"znach: ";
            int x;
            cin>>x;
            pTree->d=x;
            cout<<"kol-vo sinovei: ";
            cin>>x;
            pTree->Trees.resize(x);
            pv->Trees[i]=pTree;
        }
        for(size_t i=0;i<prev->Trees.size();i++)
                insert(pv->Trees[i]);
    }
    return pv;
}

Код


int main()
{
    Tree* root=first(1);
    insert(root);
    print(root,0);
    return 0;
}

Как мне объединить эти 2 функции в одну и что можно оптимизировать?

Хочу переделать эту конструкцию потом под конструктор класса...

Это сообщение отредактировал(а) toxx - 26.4.2010, 21:31

mes

Дата 26.4.2010, 21:41 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 20:17

)

Есть структура данных n- мерного дерева

это структура описывает не дерево, а его стык, а следовательно название не Tree

Цитата(toxx @ 26.4.2010, 20:17

)

я создаю дерево в 2 шага
1.Создаю корень

а где у Вас корень ? навису ? заведите структуру/класс Tree, которая будет хранить корень и иметь нужные операции, такие как

Цитата(toxx @ 26.4.2010, 20:17

)

insert

--------------------

http://opendots.net

toxx

Дата 26.4.2010, 21:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

mes

Цитата

это структура описывает не дерево, а его стык, а следовательно название не Tree

Как не дерево?

Цитата

а где у Вас корень ? навису ?

Нет нет он не на вису...
я его(корень) создаю, задаю количество сыновей, потом вызываю insert для этих сыновей, который в свою очередь создаёт дерево всё...

Это сообщение отредактировал(а) toxx - 26.4.2010, 21:51

mes

Дата 26.4.2010, 21:55 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 20:51

)

я его(корень) создаю,

Это си стиль, где создается корень и последующее правильное его использование лежит на плечах программиста,
А вы, я так полагаю, хотите выразить в С++ стиле, для этого должны общаться не с корнем, а с самим деревом.

посмотрите дизайн того же std::list, и сравните его с C-листом.

Это сообщение отредактировал(а) mes - 26.4.2010, 21:57

--------------------

http://opendots.net

toxx

Дата 26.4.2010, 22:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

mes
вы меня щас так запутали вот деревьями в стиле си и си++, что щас придётся очень много поменять.... я даже не знал об таком когда делал это дерево даже близко я был уверен, что стиль он один...
т.е. как я понимаю нужно создать структуру данных

Код


struct tree_m
{
    int d;
    Vector<tree_m *> Trees;
};

потом создать класс... с этими данными?

Код


class Tree
{
    tree_m root;
public:
    Tree();
    tree_m* first(int );
    tree_m* insert(tree_m* );
    void print(tree_m*,size_t );
};

Цитата

посмотрите дизайн того же std::list, и сравните его с C-листом.

эмм, а где это можно посмотреть... всегда было интересно, но не знаю где( знаю гдето в библиотеках вижл студио...)

Это сообщение отредактировал(а) toxx - 26.4.2010, 22:09

mes

Дата 26.4.2010, 22:23 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 21:09

)

эмм, а где это можно посмотреть... всегда было интересно, но не знаю где( знаю гдето в библиотеках вижл студио...)

можно и там (в инклудах), но я имел ввиду ознакомиться с описанием в руководстве..

Цитата(toxx @ 26.4.2010, 21:09

)

потом создать класс... с этими данными?

для начала нужно узнать , есть ли у вас опыт работы с стд контейнером (напр. вектором) посредством итератора ?

--------------------

http://opendots.net

toxx

Дата 26.4.2010, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

Цитата

можно и там (в инклудах), но я имел ввиду ознакомиться с описанием в руководстве..

а где это руководство взять? не разу просто не смотрел ничего подобного.

Цитата

для начала нужно узнать , есть ли у вас опыт работы с стд контейнером (напр. вектором) посредством итератора ?

нет нету... что такое итераторы представляю только теоретически... это очень сильно влияет на то, смогу ли я сделать класс?(если это для этого нужно изучу)

mes

Дата 26.4.2010, 22:39 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 21:29

)

а где это руководство взять? не разу просто не смотрел ничего подобного.

ну для краткой информации с примером можно использовать cplusplus.com
для более подробной есть книги (где то на форуме есть тема им посвященная и не одна)

Цитата(toxx @ 26.4.2010, 21:29

)

что такое итераторы представляю только теоретически... это очень сильно влияет на то, смогу ли я сделать класс?

да, без понимания что это и какая от этого польза будет трудно понять что требуется от класса.

но с другой стороны, для начала, можно сделать древо в "полу-С++" стиле, т.е без итераторов..

Добавлено через 6 минут и 51 секунду
В общем общая схема С++ стиля выглядит следующим образом :

1. есть некая структура данных (не struct) представляющая нашу модель, она является подслоем - все элементы ее представляющие недоступны конечному пользователю..
2. Есть некоторые инструменты, которые знают как пользоваться структурой о предоставляют некий интерфейс конечному пользователю.

--------------------

http://opendots.net

toxx

Дата 26.4.2010, 22:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

mes
т.е. на данном уровне я должен написать без итераторов написать моё дерево...
используя вот такую структуру данных

Код


struct tree_m
{
    int d;
    Vector<tree_m *> Trees;
};

и добавить её в класс и соответственно реализовать методы заполнения и вывода?
и класс этот будет выглядеть примерно так:

Код


class Tree
{
    tree_m root;
public:
    Tree();
    tree_m* insert();
    void print(size_t );
};

Мне просто с фронтом работы определиться, я надеялся на одно а получил сразу так сказать "в лоб" то, что я хотел делать как раз после слияния моих функций...

mes

Дата 26.4.2010, 23:06 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 21:48

)

struct tree_m

не дерево, а узел/стык
struct Node

Цитата(toxx @ 26.4.2010, 21:48

)

т.е. на данном уровне я должен написать без итераторов написать моё дерево...

угу..

Цитата(toxx @ 26.4.2010, 21:48

)

void print(size_t );

не красиво для контейнера делать print членом класса..

Добавлено через 6 минут и 7 секунд

Цитата(toxx @ 26.4.2010, 21:48

)

Vector<tree_m *> Trees;

вектор хранит указатели, поэтому желательно, чтоб такой вектор был упрятан подальше в класс, который будет заботиться о правильном удалении элементов и проксировать нужные методы вектора..

--------------------

http://opendots.net

toxx

Дата 26.4.2010, 23:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

mes

Цитата

не дерево, а узел/стык
struct Node

ага...

Код


struct Node
{
    int key;
    Vector<Node *> Nodes;
};

Код


class Tree
{
    Node root;
public:
    Tree();
    Node* insert();
};

Теперь я не знаю как этим всем пользоваться...эхх и озадачили вы меня(даже конструктор написать не могу).

Добавлено через 47 секунд

Цитата

вроде бы итак спрятан в структуре...

toxx

Дата 27.4.2010, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

конструктор такой вот получился...для корня

Код


Tree::Tree()
{
    cout<<"znach: "<<endl;
    int d;
    cin>>d;
    root.key=d;
    cout<<"Kol-vo vershin y  kornya"<<endl;
    size_t count;
    cin>>count;
    root.Nodes.resize(count);
}

а нормально, что получается так вот?

Код


root.Nodes.resize(count);

Это сообщение отредактировал(а) toxx - 27.4.2010, 00:32

mes

Дата 27.4.2010, 00:59 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(toxx @ 26.4.2010, 23:32

)

а нормально, что получается так вот?

не очень )

Цитата(toxx @ 26.4.2010, 22:47

)

вроде бы итак спрятан в структуре...

как же спрятан ? если к нему извне resize применяете..

Цитата(toxx @ 26.4.2010, 23:32

)

конструктор такой вот получился...для корня

ну cin и cout там только для теста ? я надеюсь

Цитата(toxx @ 26.4.2010, 22:47

)

и озадачили вы меня(даже конструктор написать не могу).

ну так в С++-стиле без итераторов дерево не получится.. я предлагал для начала сделать в полу-С++ стиле.. т.е. тот же С но с классами..

Добавлено через 4 минуты и 11 секунд
для начала в любом случае надо представить удобную систему представления..
так как перемещаться у вас по древу можно и от соседа к соседу, и вглубь..

--------------------

http://opendots.net

toxx

Дата 27.4.2010, 07:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

mes

Цитата

как же спрятан ? если к нему извне resize применяете..

вечером исправлю

Цитата

ну cin и cout там только для теста ? я надеюсь

ага, это всё само будет заполнятся и для других данных =)меня просто на этом форуме научили идти от простого к сложному...

как что новое, так как баран на новые ворота....

Это сообщение отредактировал(а) toxx - 27.4.2010, 14:20

toxx

Дата 27.4.2010, 18:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13

Код


class Tree
{
    int key;
    Vector<Tree *> Trees;
public:
    //Tree(int d,size_t size);
    Tree* first();
    Tree* insert(Tree *root);
};

Код


Tree* Tree::first()
{
    Tree* pv=new Tree;
    cout<<"key: "<<endl;
    int key;
    cin>>key;
    pv->key=key;
    cout<<"Kol-vo vershin y  kornya"<<endl;
    int count;
    cin>>count;
    pv->Trees.resize(count);
    return pv;
}
Tree* Tree::insert(Tree *root)
{
    Tree* pTree;
    if(root->Trees.size()!=0)
    {
        for(size_t i=0;i<root->Trees.size();i++)
        {
            pTree=new Tree;
            cout<<"i= "<<i<<endl;
            cout<<"znach: ";
            int x;
            cin>>x;
            pTree->key=x;
            cout<<"kol-vo sinovei: ";
            cin>>x;
            pTree->Trees.resize(x);
            root->Trees[i]=pTree;
        }
         for(size_t i=0;i<root->Trees.size();i++)
                root->insert(root->Trees[i]);
    }
    return root;
}

Код


int main()
{
    Tree *p=p->first();
    p->insert(p);

    return 0;
}

Сделал так...опять в стиле си похоже, никак не могу сообразить как сделать конструктор он у меня получается какой-то странный..

Еще есть идея

Код


class Tree
{
    int key;
    Vector<Tree *> Trees;
public:
    Tree(int d,size_t size);
    Tree(const Tree &b);
    Tree* insert(Tree *root);
};

Cделать конструктор

Код


Tree::Tree(int d,size_t size)
{
    key=d;
    Trees.resize(size);
}

Конструктор-копирования

Код


Tree::Tree(const Tree &b)
{
    key=b.key;
    Trees=b.Trees;
}

и insert

Код


Tree* Tree::insert(Tree *root)
{
    if(root->Trees.size()!=0)
    {
        for(size_t i=0;i<root->Trees.size();i++)
        {
            cout<<"i= "<<i<<endl;
            cout<<"znach: ";
            int x,y;
            cin>>x;
            cout<<"kol-vo sinovei: ";
            cin>>y;
            Tree pTree(x,y);
            root->Trees[i]=&pTree;
        }
         for(size_t i=0;i<root->Trees.size();i++)
                root->insert(root->Trees[i]);
    }
    return root;
}

Но почему то эта идея не работает...

Это сообщение отредактировал(а) toxx - 27.4.2010, 19:36

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »