CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
1

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

20.12.2016, 20:45. Показов 1651. Ответов 1

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

Не по теме:


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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.12.2016, 20:45
Ответы с готовыми решениями:

Передача общего вида страницы и данных для неё, Backbone.js
Как лучше передавать общий вид страницы на сайт? Под общим видом подразумеваю различные кнопки,...

Составить программу для решения квадратного уравнения общего вида
3)Составить программу для решения квадратного уравнения общего вида: ах^2+bx+c=0

Какие методы применяют для моделирования динамики механизмов общего вида?
Товарищи, какие методы обычно применяют для моделирования динамики механизмов общего види в...

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

1
104 / 98 / 40
Регистрация: 01.07.2012
Сообщений: 277
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
21.12.2016, 07:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.12.2016, 07:52
Помогаю со студенческими работами здесь

Применение стандартных интерфейсов в собственных классах. Реализация итератора для класса. Создание клона
Помогите, пожалуйста, сделать задачу Общая постановка задачи: Каждый разрабатываемый класс...

Применение стандартных интерфейсов в собственных классах. Реализация итератора для класса. Создание клона
Класс “Многочлен ax^2+bx+c”. Поля – a,b,c, а также имя многочлена и его id. Обязательно включить...

Применение стандартных интерфейсов в собственных классах. Реализация итератора для класса. Создание клона
Общая постановка задачи: Каждый разрабатываемый класс должен содержать: o скрытые данные...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru