VPF::рекурсия для обхода н-арного дерева

tonchitos

Дата 13.3.2008, 20:37 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

В общем господа, мне надо добраться до каждого узла и вызвать для каждого узла ф-ию его печати.
Причем не просто обойти, ав определенном порядке, тк текст надо вывести структурированно
примерно так:

Код



node
    node
    node
        node
            node
        node
        node
            node
            node
        node
    node
        node
            node
            node
        node
    node
node
node
    node
        node
    node

В опщем есть тут любители алгоритмов?

Код


FileWrite(GUI::Node * Root, int ind)
{
    Root.printFile(fopen)
    if (Root.childs.size!=0)&&(ind<=Root.childs.size)
    {
        ind++;
        return (Root.childs[ind], ind)
    }
    else 
        if ...// если парент имеет детей
        {
            indParnt++;
            ind=0;

            return(следующего ребенка парента);
        }
        else
    

}

мой класс дерево:

Код



namespace GUI
{
    class Node 
    {
        std::vector<Node> childs;
        std::string Name;
        int pole1;
        int pole2;
        int level = 0;
        

    public:

    Node * parent;
    Node();

    Node (const Node &obj)
    {
        childs = obj.childs;
        Name = obj.Name;

    }

    void printFile(FILE * myFile)
    {
        for (int i=0; i<level ;i++;)
        {
            fprintf(myFile, "%c",' ');
        }
        fprintf(myFile, "Name: [%s]/n",Name);
        fprintf(myFile, "pole1:[%d]/n",pole1);
        fprintf(myFile, "pole2:[%d]/n",pole2);
        fprintf(myFile, "level:[%d]/n",level);
    }

    void LoadData(std::string str)
    {
        Name=str;
    }
    
    int GetNumChilds ()
    {
        return childs.size();
    }
    const Node & GetChild (int pos) const
    {
        return childs[pos];
    }
    Node & GetChild (int pos)
    {
        return childs[pos];
    }


    bool insertChild (int pos, Node & element );
    bool removeChild (int pos);
    
    Node & operator = (const Node & from);

    ~Node();

    };



}

Это сообщение отредактировал(а) tonchitos - 13.3.2008, 20:40

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 13.3.2008, 22:19 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Проблема возникла из-за того, что метод printFile делает не совсем то, что надо. я бы его реализовал так:

Код

void GUI::Node::printFile(FILE *file, unsigned tab = 0) const
{
    for(unsigned i = 0; i < tab; ++i)
        fputc(' ', file);
    fprintf(file, "Name: [%s]\n", name.c_str());
    fprintf(file, "Pole1:  [%d]\n", pole1);
    fprintf(file, "Pole2:  [%d]\n", pole2);
    fprintf(file, "Level:  [%d]\n", level);
    for(std::vector<Node>::const_iterator i = childs.begin(), end = childs.end(); i != end; ++i)
       i->printFile(file, tab + 1);
}

И вообще, я бы в программе на С++ FILE, fprintf и пр. не использовал без крайней на то необходимости. В данном случае все можно легко организовать через std::ostream и operator<<(). Да и иерархию представил бы в виду чего-то XML-подобного...

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

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 14.3.2008, 00:29 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

так она пробегает одну ветку, чет не то...или я недопоняла?

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 14.3.2008, 00:42 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Если ты вызовешь метод printFile() у корневого нода, то будут распечатаны все ноды рекурсивно и с отступами (по идее, на самом деле читай в конце).
А тебе точно нужно выводить в FILE, а не в std::ostream? А то для С++ это не очень естественно. Например:

Код

std::ostream& GUI::Node::printFile(std::ostream &stream, unsigned tab = 0) const
{
    for(unsigned i = 0; i < tab; ++i)
        stream << ' ';
    stream << "<Node name=\"" << name << "\" ";
    stream << "pole1=\"" << pole1 << "\" ";
    stream << "pole2=\"" << pole2 << "\" ";
    stream << "level=\"" << level << "\" >\n";
    for(std::vector<Node>::const_iterator i = childs.begin(), end = childs.end(); i != end; ++i)
       i->printFile(stream, tab + 1);
    for(unsigned i = 0; i < tab; ++i)
        stream << ' ';
    stream << "</Node>\n"
    return stream;
}

Кстати, я в предыдущем варианте с отступами ошибся. Там нужно цикл пихать перед каждым fprintf (ну или заранее сгенерировать строку)...

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 14.3.2008, 00:58 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

bsa,

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

ведь если функция проходит ветку:

Цитата

Node
   Node
      Node
         Node
            Node
         Node
             Node
      Node
    Node
       Node
Node

Трудность в том как остальные ветки пробежать.

Ведь бежать он должен так, иначе не запишет как надо

user posted image

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 14.3.2008, 01:19 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

tonchitos, рекомендую откомпилировать и пройтись отладчиком.
На самом деле схема немного иная (т.е. стрелки немного иначе рисовать надо), но порядок тот же.
Это рекурсия. Смысл ее такой, нод выводит свои данные, затем последовательно говорит своим потомкам (тоже нодам!) вывести свои. Они выводят в том же порядке (т.е. свои и своих потомков). И все повторяется...

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 14.3.2008, 15:57 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

bsa, а с функцией чтения не поможете? smile

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

tonchitos

Дата 14.3.2008, 17:34 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

народ, если я верно поняла то ф-ия чтения из файл классу принадлежать не могет.
Кароч. Хотя в принципе могет.

в общем примерно че я насоображала на скорую руку (не ругайте, сама знаю что фигово)

Код


readFile(GUI::Node & root, GUI::Node & parent, std::ostream & stream,int lev, unsigned tab = 0) const
{
    char buf;
        std::string Name;
        int pole1;
        int pole2;
        int level;
    for(unsigned i = 0; i < tab+8; ++i)
        stream >> buf ;
    int j=0;
    do
    {
        stream >> Name[j];
        j++;
    }
    while (Name[j]!='"');
    Name[j]=0;

    for(unsigned k = 0; k < 11; ++k)
        stream >> buf;
    stream >> pole1;

    for(k = 0; k < 11; ++k)
        stream >> buf;
    stream >> pole2 ;

    for(k = 0; k < 11; ++k)
        stream >> buf;
    stream >> level;
    
    for(k = 0; k < 6; ++k)
        stream >> buf;

    Root.Name=Name;
    Root.pole1=pole1;
    Root.pole2=pole2;
    Root.level=level;

    if (level > tab)
    {
        tab++;
        root.insertChild(0,Root);
        return(Root.childs[0], Root,stream,lev, tab);

    }
    else
    {
        if (lev<tab)
            tab=lev;
        tab--;
        lev=tab;
        pos++;
        parent.insertChild(pos,Root);
        return(parent.childs[pos], parent,stream,lev, tab);
    }

}

предложите плиз более изящный вариант

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 14.3.2008, 19:33 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Вопрос, а для чего это нужно? Если это курсовая/домашнее задание, то можно это сделать записывая количество потомков у каждого чилда (быстрое и простое решение)...
А вот если это работа и речь идет о каком-то проекте, то надо поступать более универсально (с использованием сторонних библиотек). И в этом случае, дерево (т.е. нод) надо тоже переписывать. Имхо.

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 17.3.2008, 01:20 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

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

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 17.3.2008, 01:35 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Если тебе можно пользоваться сторонними библиотеками, то рекомендую в данном случае использовать TinyXML. Очень легко все записывается и считывается из файла. Да и файл хорошо отформатирован по умолчанию.
Если нельзя, то делай так:

Код

std::ostream& GUI::Node::writeFile(std::ostream &stream) const
{
    stream << Name << '\n';
    stream << pole1 << '\n';
    stream << pole2 << '\n';
    stream << level << '\n';
    stream << childs.size() << '\n';
    for(std::vector<Node>::const_iterator i = childs.begin(), end = childs.end(); i != end; ++i)
        i->writeFile(stream);
    return stream;
}
std::istream& GUI::Node::readFile(std::istream &stream)
{
     std::getline(stream, Name);
     std::size_t size;
     stream >> pole1 >> pole2 >> level >> size >> std::ws;
     childs.resize(size);
     for(std::vector<Node>::const_iterator i = childs.begin(), end = childs.end(); i != end; ++i)
         i->readFile(stream);
     return stream;
}

Хотя, какой после этого из тебя работник? smile

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 17.3.2008, 18:29 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

вот ф-ия для чтения в файл. Меня в ней выкидывает почему то

Код



std::istream & GUI::Node::readFile(std::istream &stream)
{
    char ch;
    stream >> ch;
    int i=0;
    while (ch==' ')
    {
        stream.ignore(1);
        stream >>ch;
        i++;
    }
    stream.ignore(7);
    stream >> Name;
    stream.ignore(10+i);
    stream >> pole1; 
    stream.ignore(11+i);
    stream >> pole2;
    stream.ignore(11+i);
    stream >> level; 
    stream.ignore(17+i);
    stream >> size; 
    stream.ignore(3);
    Node cld;
    childs.resize(size);

    for(std::vector<Node>::iterator i= childs.begin(), end = childs.end(); i != end; ++i)
    {
        
        i->readFile(stream);
    }
    
    return stream;
}

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

bsa

Дата 17.3.2008, 18:49 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

вообще-то есть стандартный манипулятор для пропуска пробельных символов - std::ws. Зачем было изобретать велосипед?
Что произойдет, если я руками воткну пробел в файл? Очень плохо затачиваться на определенное количество пробелов. Поэтому, забудь про ignore().
Если тебе очень нужно красиво оформить файл (отступы сделать), то сделай так, чтобы начало данных на строке характеризовал какой-то определенный символ:

Код

>name-1
>pole1-1
>pole2-1
>level-1
>2
 >name-1-1
 >pole1-1-1
 >pole2-1-1
 >level-1-1
 >1
  >name-1-1-1
  >pole1-1-1-1
  >pole2-1-1-1
  >level-1-1-1
  >0
 >name-1-2
 >pole1-1-2
 >pole2-1-2
 >level-1-2
 >0

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

tonchitos

Дата 17.3.2008, 19:38 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

без игнора накак, надо же символы пропускать перед и после интов

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

tonchitos

Дата 17.3.2008, 19:54 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 40

а за std::ws спасибо большое.

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

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

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