Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
sovaz1997
CEO SOVAZ Corp.
383 / 229 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
Завершенные тесты: 1
1

Создание итератора для дерева общего вида

20.12.2016, 20:45. Просмотров 478. Ответов 1

Возникла такая проблема: надо сделать итератор для дерева общего вида. Я не знаю, как его лучше сделать. Если кто-то с этим сталкивался, можете сказать, как вы это делали?

Не по теме:


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#ifndef NTREE_HPP
#define NTREE_HPP
 
#include <cstdio>
#include <memory>
#include <iostream>
#include "figure.hpp"
#include "iterator.hpp"
 
 
template<class T> class Iterator;
 
template<class T>
class NTree : public std::enable_shared_from_this<NTree<T> > {
private:
    std::shared_ptr<NTree<T> > parent;
    int nodeNumber;
 
  std::unique_ptr<std::shared_ptr<NTree<T> >[]>sons;
  std::shared_ptr<T> data;
  unsigned int sz;
 
    std::shared_ptr<NTree<T> > current;
 
    void printTree(std::ostream& os, unsigned int depth, std::shared_ptr<NTree<T> > cur) const {
        if(this == cur.get()) {
            data->printWithTab(os, depth, true);
        } else {
            data->printWithTab(os, depth, false);
        }
 
        for(unsigned int i = 0; i < size(); ++i) {
            sons[i]->printTree(os, depth + 1, cur);
        }
    }
    
    friend Iterator<T>;
public:
    NTree() : parent(nullptr), nodeNumber(0), data(nullptr), sz(0) {}
    NTree(std::shared_ptr<T> item) : data(item), sz(0) {}
    NTree(std::shared_ptr<T> item, std::shared_ptr<NTree<T> > prnt, int nodeNum) : parent(prnt), nodeNumber(nodeNum), data(item), sz(0) {}
    ~NTree() {}
 
    void pushSon(std::shared_ptr<T> item) {
        if(size() == 0) {
            sons = std::unique_ptr<std::shared_ptr<NTree<T> >[]>(new std::shared_ptr<NTree<T> >[1]);
        } else {
            std::unique_ptr<std::shared_ptr<NTree<T> >[]> new_sons = std::unique_ptr<std::shared_ptr<NTree<T> >[]>(new std::shared_ptr<NTree<T> >[sz + 1]);
            for(unsigned int i = 0; i < sz; ++i) {
                new_sons[i] = sons[i];
                new_sons[i]->setNodeNumber(i);
            }  
        
            sons = std::move(new_sons);
        }
        
        sons[size()] = std::shared_ptr<NTree<T> >(new NTree<T>(item, this->shared_from_this(), sz));
        
        ++sz;
    }
 
    void popSon(unsigned int pos) {
        if(pos < size()) {
          std::unique_ptr<std::shared_ptr<NTree>[]> new_sons = std::unique_ptr<std::shared_ptr<NTree<T> >[]>(new std::shared_ptr<NTree<T> >[sz - 1]);
         
          for(unsigned int it = 0, i = 0; i < sz; ++i) {
            if(i != pos) {
              new_sons[it] = sons[i];
              new_sons[it]->setNodeNumber(it);
              ++it;
            }
          }
          
          sons = std::move(new_sons);
          --sz;
        } else {
            std::cout << "Такого элемента нет!\n";
        }
    }
 
    std::shared_ptr<NTree<T> > getSon(unsigned int it) {
        if(it >= size()) {
            std::cout << "Такого элемента нет!\n";
            return std::shared_ptr<NTree<T> >(nullptr);
        }
 
        return sons[it];
    }
 
    std::shared_ptr<T> getItem() {
        return data;
    }
 
    void setItem(std::shared_ptr<T> item) {  
        data = item;
    }
 
    unsigned int size() const {
        return sz;
    }
 
    void setCurrent(std::shared_ptr<NTree<T> > cur) {
        current = cur;
    }
    
    void setNodeNumber(int number) {
        nodeNumber = number;
    }
    
    void setParent(std::shared_ptr<T> prnt) {
        parent = prnt;
    }
    
    void print(std::ostream& os) {
        data->printWithTab(os, 0, false);
    }
 
    friend std::ostream& operator<<(std::ostream& os, const NTree<T>& tree) {
        tree.printTree(os, 0, tree.current);
        return os;
    }
};
 
#endif



Добавлено через 2 часа 27 минут
up!
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2016, 20:45
Ответы с готовыми решениями:

Создание структуры итератора для работы с файлом
Всем здравствуйте! Пытаюсь создать итератор, чтоб выводить бинарные данные с файла. По моей идее,...

Дерево общего вида
Задание: Динамическое дерево произвольной размерности(ссылочная часть узла-список) знаю как...

Деревья общего вида
Дан указатель P1 на корень непустого дерева общего вида. Вывести значения всех вершин дерева в...

Ошибка в функции общего вида
Source.cpp: #include &quot;median.h&quot; #include &lt;vector&gt; #include &lt;iostream&gt; using namespace std;...

Дерево общего вида (да опять я)
Всеравно неработает уже 2 ночь не сплю. одни проблеммы с етой программой, но что то мне...

1
Vaiz
104 / 98 / 40
Регистрация: 01.07.2012
Сообщений: 277
Завершенные тесты: 1
21.12.2016, 07:52 2
На стеке (std::stack) можно итератор сделать.

ntreeiterator.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#pragma once
#include <stack>
#include "ntree.h"
 
template<typename T>
class NTreeIterator
{
    using NTreePtr = std::shared_ptr<NTree<T>>;
    using ItemPtr = std::shared_ptr<T>;
    using const_iter = typename std::vector<NTreePtr>::const_iterator;
 
    struct SPoint
    {
        NTreePtr m_ptrNode;
        const_iter m_currentSon;
        const_iter m_endSon;
 
        SPoint(NTreePtr ptrTree)
            : m_ptrNode(ptrTree)
            , m_currentSon(m_ptrNode->m_sons.cbegin())
            , m_endSon(m_ptrNode->m_sons.cend())
        {}
 
        NTreePtr Next()
        {
            if( m_currentSon == m_endSon )
                return nullptr;
 
            return *m_currentSon++;
        }
    };
 
    std::stack< SPoint > m_stack;
 
public:
    NTreeIterator( NTreePtr ptrTree )
    {
        m_stack.emplace(ptrTree);
    }
 
    NTreePtr Next()
    {
        while(!m_stack.empty())
        {
            SPoint &topPoint = m_stack.top();
            if(NTreePtr ptrTree = topPoint.Next())
            {
                m_stack.emplace(ptrTree);
                continue;
            }
 
            NTreePtr ptrTree = topPoint.m_ptrNode;
            m_stack.pop();
 
            return ptrTree;
        }
 
        return nullptr;
    }
};
ntree.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#pragma once
 
#include <cstdio>
#include <memory>
#include <iostream>
#include <vector>
//#include "figure.hpp"
//#include "iterator.hpp"
 
template<typename T>
class NTreeIterator;
 
template<typename T>
class NTree : public std::enable_shared_from_this<NTree<T> >
{
private:
    using NTreePtr = std::shared_ptr<NTree<T> >;
    using ItemPtr = std::shared_ptr<T>;
 
    NTreePtr parent;
    int nodeNumber;
 
    std::vector<NTreePtr> m_sons;
    ItemPtr m_ptrData;
 
    void printTree(std::ostream& os, unsigned int depth, std::shared_ptr<NTree<T> > cur) const {
        if(this == cur.get()) {
            m_ptrData->printWithTab(os, depth, true);
        } else {
            m_ptrData->printWithTab(os, depth, false);
        }
 
        for(unsigned int i = 0; i < size(); ++i) {
            m_sons[i]->printTree(os, depth + 1, cur);
        }
    }
 
    friend class NTreeIterator<T>;
public:
    //NTree() : parent(nullptr), nodeNumber(0), m_ptrData(nullptr) {}
    NTree(ItemPtr item) : m_ptrData(item) {}
    NTree(ItemPtr item, NTreePtr prnt, int nodeNum) : parent(prnt), nodeNumber(nodeNum), m_ptrData(item) {}
    ~NTree() {}
 
    void pushSon(ItemPtr item) {
        NTreePtr ptrThis = this->shared_from_this();
        m_sons.push_back( std::make_shared<NTree<T>>(item, ptrThis, m_sons.size()) );
    }
 
    void popSon(unsigned int pos) {
        if(pos < size()) {
            m_sons.erase(pos);
            for( size_t i = 0; i < m_sons.size(); ++i )
            {
                m_sons[i]->setNodeNumber(i);
            }
        } else {
            std::cout << "Такого элемента нет!\n";
        }
    }
 
    NTreePtr getSon(unsigned int it) {
        if(it >= size()) {
            std::cout << "Такого элемента нет!\n";
            return NTreePtr(nullptr);
        }
 
        return m_sons[it];
    }
 
    ItemPtr getItem() {
        return m_ptrData;
    }
 
    void setItem(ItemPtr item) {
        m_ptrData = item;
    }
 
    size_t size() const {
        return m_sons.size();
    }
 
    void setNodeNumber(int number) {
        nodeNumber = number;
    }
 
    void setParent(NTreePtr prnt) {
        parent = prnt;
    }
 
    void print(std::ostream& os) {
        m_ptrData->printWithTab(os, 0, false);
    }
 
    friend std::ostream& operator<<(std::ostream& os, const NTree<T>& tree) {
        tree.printTree(os, 0, tree.shared_from_this() );
        return os;
    }
};
main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
 
#include "ntree.h"
#include "ntreeiterator.h"
 
using namespace std;
using NTree_t = NTree<size_t>;
using NTreePtr_t = std::shared_ptr<NTree_t>;
 
void InitSons( const NTreePtr_t &ptrTree, size_t sonsCount, size_t startValue )
{
    for(size_t i = 0; i < sonsCount; ++i)
        ptrTree->pushSon( std::make_shared<size_t>(startValue + i) );
}
 
size_t InitSonsOfSons(const NTreePtr_t &ptrTree, size_t sonsCount, size_t startValue)
{
    for(size_t i = 0; i < ptrTree->size(); ++i)
    {
        NTreePtr_t ptrSon = ptrTree->getSon(i);
        InitSons(ptrSon, sonsCount, startValue);
        startValue += sonsCount;
    }
 
    return startValue;
}
 
int main()
{
    NTreePtr_t ptrTree = std::make_shared<NTree_t>( std::make_shared<size_t>( 0 ) );
    InitSons(ptrTree, 10, 11);
 
    InitSonsOfSons(ptrTree, 5, 101);
 
    size_t startValue = 1001;
    for(size_t i = 0; i < ptrTree->size(); ++i)
    {
        NTreePtr_t ptrSon = ptrTree->getSon(i);
        startValue = InitSonsOfSons(ptrSon, 3, startValue);
    }
 
    NTreeIterator<size_t> iter(ptrTree);
    while (NTreePtr_t ptrNode = iter.Next()) {
        std::cout << *ptrNode->getItem() << std::endl;
    }
 
    return 0;
}
1
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2016, 07:52

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

Построить дерево общего вида по строке
Господа, есть такое задание: Дана строка, описывающая дерево общего вида. Построить дерево по...

Программирование с использованием подпрограмм общего вида
Вот эта задача: Заданы матрицы A= (i=1, 2, 3; j=1, 2, 3), B= (i=1, 2, 3; j=1, 2, 3), то есть...

Объект общего вида (Object) в консольном приложении
Всем привет. Не смог понять одной вещи: есть ли возможность создать функцию с аргументом типа...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.