Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > рекурсия для обхода н-арного дерева


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


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

    };



}

Автор: bsa 13.3.2008, 22:19
Проблема возникла из-за того, что метод 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-подобного...

Автор: tonchitos 14.3.2008, 00:29
так она пробегает одну ветку, чет не то...или я недопоняла?

Автор: bsa 14.3.2008, 00:42
Если ты вызовешь метод 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
bsa, 

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

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

Цитата

Node
   Node
      Node
         Node
            Node
         Node
             Node
      Node
    Node
       Node
Node


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

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

user posted image

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

Автор: tonchitos 14.3.2008, 15:57
smile  bsa, а с функцией чтения не поможете?   smile 

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

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

Код

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

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

Автор: bsa 17.3.2008, 01:35
Если тебе можно пользоваться сторонними библиотеками, то рекомендую в данном случае использовать 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
вот ф-ия для чтения в файл. Меня в ней выкидывает почему то
Код


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
вообще-то есть стандартный манипулятор для пропуска пробельных символов - http://www.cplusplus.com/reference/iostream/manipulators/ws.html. Зачем было изобретать велосипед?
Что произойдет, если я руками воткну пробел в файл? Очень плохо затачиваться на определенное количество пробелов. Поэтому, забудь про 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
без игнора накак, надо же символы пропускать перед и после интов

Автор: tonchitos 17.3.2008, 19:54
а за std::ws спасибо большое.

Автор: bsa 17.3.2008, 20:48
надеюсь теперь, ты знаешь, как пропускать символы без игнора.  smile 
Кстати, на том сайте еще много чего описано.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)