Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Помогите оптимизировать

Автор: toxx 26.4.2010, 21:17

Есть структура данных 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 функции в одну и что можно оптимизировать?

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

Автор: mes 26.4.2010, 21:41

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

)

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

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

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

)

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

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

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

)

insert

Автор: toxx 26.4.2010, 21:51

mes

Цитата

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

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

Цитата

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

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

Автор: mes 26.4.2010, 21:55

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

)

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

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

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

Автор: toxx 26.4.2010, 22:09

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-листом.

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

Автор: mes 26.4.2010, 22:23

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

)

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

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

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

)

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

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

Автор: toxx 26.4.2010, 22:29

Цитата

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

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

Цитата

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

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

Автор: mes 26.4.2010, 22:39

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

)

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

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

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

)

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

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

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

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

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

Автор: toxx 26.4.2010, 22:48

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

Цитата(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;

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

Автор: toxx 26.4.2010, 23:47

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

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

Код


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);

Автор: mes 27.4.2010, 00:59

Цитата(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 секунд
для начала в любом случае надо представить удобную систему представления..
так как перемещаться у вас по древу можно и от соседа к соседу, и вглубь..

Автор: toxx 27.4.2010, 07:44

mes

Цитата

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

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

Цитата

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

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

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

Автор: toxx 27.4.2010, 18:23

Код


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;
}

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

Автор: azesmcar 28.4.2010, 21:21

Не совсем понимаю суть вопроса, можно немного прояснить в общих чертах.
что попалось на глаза

Цитата

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

такой конструктор копирование не имеет смысла, компилятор сам сгенерирует что-то вроде

Код


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

в чем смысл этой конструкции?

Код


if(root->Trees.size()!=0)
...
return root;

т.е. если список пустой то он ничего нового туда не добавит?

Автор: toxx 28.4.2010, 21:41

Цитата

Не совсем понимаю суть вопроса, можно немного прояснить в общих чертах.

Хочу переделать моё n-мерное дерево в стиле Cи(мой 1й пост темы) на дерево в стиле C++.
Попытки предпринял, но мне кажется получилось тоже что у меня и было.

Но пока до конца не понимаю в какую сторону мне делать...

Цитата

в чем смысл этой конструкции?

если количество сыновей у вершины не нулевое функция добавляет вершины...делаю рекурсией эти действия

Код


if(root->Trees.size()!=0)
...
return root;

Автор: azesmcar 28.4.2010, 21:55

Цитата(toxx @ 28.4.2010, 21:41

)

Хочу переделать моё n-мерное дерево в стиле Cи(мой 1й пост темы) на дерево в стиле C++.

а где тогда итераторы?

Цитата(toxx @ 28.4.2010, 21:41

)

если количество сыновей у вершины не нулевое функция добавляет вершины...делаю рекурсией эти действия

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

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

Цитата(toxx @ 28.4.2010, 21:41

)

Но пока до конца не понимаю в какую сторону мне делать...

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

Автор: toxx 28.4.2010, 22:00

azesmcar

Цитата

а где тогда итераторы?

На полу-C++... итераторы я не изучал, стараюсь без STL делать(поэтому полу-C++), но мне mes посоветовал без них пока сделать.

т.е. не одна из реализации из этого http://forum.vingrad.ru/forum/topic-298754/0.html# не подходит? =(

Автор: mes 28.4.2010, 23:24

Цитата(toxx @ 28.4.2010, 21:00

)

но мне mes посоветовал без них пока сделать.

не посоветовал, а согласился что для начала без них.. Доступ будет тогда осуществляться на прямую к структуре, как и в си стиле,
также как и гарантом правильности все также программист. Отличие в "полу-С++" будет фактически лишь в организация кода по классам..

Добавлено через 2 минуты и 50 секунд

Цитата(toxx @ 28.4.2010, 20:41

)

Хочу переделать моё n-мерное дерево в стиле Cи(мой 1й пост темы) на дерево в стиле C++.

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

Добавлено через 4 минуты и 59 секунд

Цитата(toxx @ 28.4.2010, 21:00

)

т.е. не одна из реализации и

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

Автор: azesmcar 28.4.2010, 23:48

Цитата(toxx @ 28.4.2010, 22:00

)

На полу-C++... итераторы я не изучал, стараюсь без STL делать(поэтому полу-C++), но мне mes посоветовал без них пока сделать.

ну сделайте через Java-Style итераторы, типа этого

Код


while (tree.hasNext())
   tree.next();
...

Автор: toxx 30.4.2010, 17:35

mes

Цитата

а чего не получается то ?

Я 2й день перечитывал тему, читал посты темы, прикидывал ... и наконец все таки отвечу
1.Я не понимаю как можно в один класс записать всё моё дерево.
2.Подумал и решил, что все таки для моей простенькой задачи шашек попроще применить моё дерево в стиле...
3.Я давно уже определился со структурой дерева и интерфейсом, у меня никак не выходит реализация (1) пункта
Структура данных и интерфейс у меня будет такой

Код


class AI
{
private:
    int rang;// насколько удачный ход для компьютера
    Vector<AI*> ai_Trees;// указатели на следующие игровые ситуации
    point** points;// моё игровое поле
public:
    int ai_move_rating(point**,size_t ); // оценка хода компьютера
    point** ai_copy_swap(point**,size_t ,size_t,size_t ,size_t ); // определение возможных ходов компьютера
    AI* first(int ); // первая вершина, и первый ход человека.
    AI* insert(AI* ); // добавление в дерево возможных ходов.
    void print(AI*,size_t ); // вывод дерева
};

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

Добавлено через 9 минут и 12 секунд
По сути я хочу реализовать вот такую картинку
http://www.valar.ru/gallery/0410/ai.jpg

Автор: mes 30.4.2010, 17:52

Цитата(toxx @ 30.4.2010, 16:35

)

Я не понимаю как можно в один класс записать всё моё дерево.

в один никак.. Один класс/структура - ветвь/итератор , другой класс - набор функционала

Цитата(toxx @ 30.4.2010, 16:35

)

Структура данных и интерфейс у меня будет такой

ммм... сейчас немного занят.. но тут есть поле для разворота
smile

Автор: toxx 30.4.2010, 18:01

mes

Цитата

в один никак.. Один класс/структура - ветвь/итератор , другой класс - набор функционала

ой не дорос я еще до этого...всё таки нужно использовать, что я намудрил своим си- деревом =)

Цитата

ммм... сейчас немного занят.. но тут есть поле для разворота

эмм, поле для разворота в смысле тема для беседы?=)

Автор: mes 30.4.2010, 18:07

Цитата(toxx @ 30.4.2010, 17:01

)

эмм, поле для разворота в смысле тема для беседы?=)

ага.. терь хоть понятно что Вам требуется..
smile