Форум программистов, компьютерный форум CyberForum.ru

Бинарные деревья - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа на С http://www.cyberforum.ru/cpp-beginners/thread306356.html
Доброго времени суток. Помогите пожалуйста с программкой на C Задача такая: Создать программу которая содержит динамическую информацию про наличие автобусов в авто. парке. Ведомость про каждый автобус содержит: номер автобус , ФИО водителя , номер маршрута. Програма должна обеспечивать: - первичную формировку данных про все автобусы в виде списка. - при выезде автобуса из парка вводиться...
C++ Динамические массивы структур;Классы. Класс массивы структур;Классы. Класс динамического массива структур. Здраствуйте.Помогите с практичкой мое задание 4.3. Строка таблицы данных содержит следующую информацию о владельцах авто: ф.и.о. владельца, марка авто, год выпуска, страна производитель. Требуется найти: 4.3.1) перечень владельцев с указанием числа их авто; в методичках указаны шаблоны. Огромное Спасибо за помощь! http://www.cyberforum.ru/cpp-beginners/thread306352.html
C++ неправильное значение переменной
вот код #include "stdafx.h" #include <cstdlib> #include <iostream> #include <cmath> using namespace std; int _tmain(int argc, _TCHAR* argv){ setlocale(LC_CTYPE,"rus"); int m,n,koeff,a; cout<<"Введите степень уравнения ";
C++ Абракадабровый C++
Вся проблема в чём - при вводе на русском я пишу какой-то абракадброй вроде иероглифов. Следствие установило, что эта хрень начинается после цикла do. Вот сам код, чистый консольный проект вин32: #include <iostream> #include <conio.h> using namespace std; enum itsaWord { NO, YES }; int main() { setlocale(0,""); itsaWord isWord=NO; char ch='a';
C++ Программа удаляет из строки слово с заданным номером. http://www.cyberforum.ru/cpp-beginners/thread306298.html
Помогите! нужно написать программу на "С". "Программа удаляет из строки слово с заданным номером!"(как объяснял преподаватель например 2 строки "скоро курсовая работа(20 символов в этой строке) пользователь задает удалить например 2 слово 6-14 символ, программа должна вывести скоро работа") Заранее спасибо.
C++ Расчетно-графическая работа Помогите пожалуйста. Необходимо написать расчетно-графическую работу которая будет состоять из: 1) заставки(любая картинка или несложная анимация) 2) и программы Задание по программе: построить кривые по заданному параметрическому представлению улитка Паскаля x=a*(cos(t))^2 + b*(cos(t)) y=b*cos(t)*sin(t) + b*(sin(t)); a>0, b>0, t принадлежит Рассмотреть... подробнее

Показать сообщение отдельно
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
27.05.2011, 21:30     Бинарные деревья
Шаблонный класс двоичного дерева. Операции - добавление, удаление элементов с сохранением свойства упорядоченности; проверка, содержится ли элемент в дереве; является ли дерево пустым; очистка дерева; симметричный обход дерева. Файл tree.hpp:
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#ifndef TREE_HPP
#define TREE_HPP
 
#include <stdexcept>
#include <vector>
#include <functional>
 
namespace my
{
    template <class T>
    class node
    {
    public:
    T value;
    node<T>* left;
    node<T>* right;
    };
    
    template <class T, class comp = std::less<T> >
    class tree
    {
    private:
    comp cmp;
    
    node<T>* root;
    void init(node<T>*&, const node<T>*&);
    void destruct(node<T>*&);
    void insert_leaf(node<T>*&, const T&);
    bool member(const node<T>*, const T&) const;
    void remove(node<T>*&, const T&) throw (std::runtime_error);
    const node<T>* findRightMost(const node<T>*);
    void traverse_symmetric(const node<T>*, std::vector<T>&) const;
    
    public:
    tree();
    tree(const tree<T, comp>&);
    ~tree();
    void insert(const T&);
    bool member(const T&) const;
    void remove(const T&) throw (std::runtime_error);
    bool empty() const;
    void clear();
    std::vector<T> traverse_symmetric() const;
    
    };
 
    template <class T, class comp>
    void tree<T, comp>::init(node<T>*& self, const node<T>*& p_node)
    {
    if(p_node == NULL)
        self = NULL;
    else
    {
        self = new node<T>;
        self->value = p_node->value;
        init(self->left, p_node->left);
        init(self->right, p_node->right);
    }
    }
 
    template <class T, class comp>
    void tree<T, comp>::destruct(node<T>*& p_node)
    {
    if(p_node)
    {
        destruct(p_node->left);
        destruct(p_node->right);
        delete p_node;
        p_node = NULL;
    }
    }
 
    template <class T, class comp>
    void tree<T, comp>::insert_leaf(node<T>*& p_node, const T& val)
    {
    if(p_node == NULL)
    {
        p_node = new node<T>;
        p_node->value = val;
        p_node->left = NULL;
        p_node->right = NULL;
    }
    else if(p_node->value == val)
        return;
    else if(cmp(p_node->value, val))
        insert_leaf(p_node->right, val);
    else if(cmp(val, p_node->value))
        insert_leaf(p_node->left, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::member(const node<T>* p_node, const T& val) const
    {
    if(p_node == NULL)
        return false;
    else if(p_node->value == val)
        return true;
    else if(cmp(val, p_node->value))
        return member(p_node->left, val);
    else if(cmp(p_node->value, val))
        return member(p_node->right, val);
 
    // Этот код никогда не должен выполниться
    return false;
    }
 
    template <class T, class comp>
    void tree<T, comp>::remove(node<T>*& p_node, const T& val) throw (std::runtime_error)
    {
    if(p_node == NULL)
        throw std::runtime_error("Tree remove: no such element");
 
    if(p_node->value == val)
    {
        if(p_node->left == NULL)
        {
        node<T>* ptr = p_node;
        p_node = ptr->right;
        delete ptr;
        ptr = NULL;
        }
        else if(p_node->right == NULL)
        {
        node<T>* ptr = p_node;
        p_node = ptr->left;
        delete ptr;
        ptr = NULL;
        } else {
        const node<T>* rm = findRightMost(p_node->left);
        p_node->value = rm->value;
        remove(p_node->left, rm->value);
        }
    }
 
    else if(cmp(val, p_node->value))
        remove(p_node->left, val);
    else if(cmp(p_node->value, val))
        remove(p_node->right, val);
    }
 
    template <class T, class comp>
    const node<T>* tree<T, comp>::findRightMost(const node<T>* p_node)
    {
    if(p_node->right == NULL)
        return p_node;
    return findRightMost(p_node->right);
    }
 
    template <class T, class comp>
    void tree<T, comp>::traverse_symmetric(const node<T>* p_node,
                       std::vector<T>& vec) const
    {
    if(p_node == NULL)
        return;
    traverse_symmetric(p_node->left, vec);
    vec.push_back(p_node->value);
    traverse_symmetric(p_node->right, vec);
    }
    
    template <class T, class comp>
    tree<T, comp>::tree()
    : root(NULL)
    {
    }
 
    template <class T, class comp>
    tree<T, comp>::tree(const tree<T, comp>& rhs)
    {
    init(root, rhs.root);
    }
 
    template <class T, class comp>
    tree<T, comp>::~tree()
    {
    destruct(root);
    }
 
    template <class T, class comp>
    void tree<T, comp>::insert(const T& val)
    {
    insert_leaf(root, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::member(const T& val) const
    {
    return member(root, val);
    }
 
    template <class T, class comp>
    void tree<T, comp>::remove(const T& val) throw (std::runtime_error)
    {
    remove(root, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::empty() const
    {
    return root == NULL;
    }
 
    template <class T, class comp>
    void tree<T, comp>::clear()
    {
    destruct();
    }
 
    template <class T, class comp>
    std::vector<T> tree<T, comp>::traverse_symmetric() const
    {
    std::vector<T> vec;
    traverse_symmetric(root, vec);
    return vec;
    }
}
 
#endif
Класс битовой строки. Файл bits.hpp:
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
#ifndef BITS_HPP
#define BITS_HPP
 
#include <vector>
#include <stdexcept>
#include <iosfwd>
 
namespace my
{
    class bits
    {
    private:
    std::vector<bool> b;
 
    public:
    typedef std::vector<bool>::iterator iterator;
    typedef std::vector<bool>::const_iterator const_iterator;
    typedef std::vector<bool>::reference reference;
    typedef std::vector<bool>::const_reference const_reference;
    typedef std::vector<bool>::size_type size_type;
    typedef std::vector<bool>::difference_type difference_type;
    typedef std::vector<bool>::value_type value_type;
    typedef std::vector<bool>::allocator_type allocator_type;
    typedef std::vector<bool>::pointer pointer;
    typedef std::vector<bool>::const_pointer const_pointer;
    typedef std::vector<bool>::reverse_iterator reverse_iterator;
    typedef std::vector<bool>::const_reverse_iterator const_reverse_iterator;
                
    bits();
    bits(const bits&);
    bits(std::initializer_list<bool> lst);
    
    reference operator [] (size_t) throw (std::range_error);
    const_reference operator [] (size_t) const throw (std::range_error);
    
    size_t size() const;
    bool empty() const;
 
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
 
    bool operator == (const bits&) const;
    bool operator <  (const bits&) const;
    };
}
 
std::ostream& operator << (std::ostream&, const my::bits&);
 
#endif
Файл bits.cc:
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
#include "bits.hpp"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
namespace my
{
    bits::bits()
    : b()
    {
    }
 
    bits::bits(const bits& rhs)
    : b(rhs.b)
    {
    }
 
    bits::bits(std::initializer_list<bool> lst)
    : b(lst.begin(), lst.end())
    {
    }
 
    bits::reference bits::operator [] (size_t idx) throw (std::range_error)
    {
    if(idx >= b.size())
        throw std::range_error("Bits: index is out of range");
 
    return b[idx];
    }
 
    bits::const_reference bits::operator [] (size_t idx) const throw (std::range_error)
    {
    if(idx >= b.size())
        throw std::range_error("Bits: index is out of range");
 
    return b[idx];
    }    
 
    size_t bits::size() const
    {
    return b.size();
    }
 
    bool bits::empty() const
    {
    return b.empty();
    }
        
    bits::iterator bits::begin()
    {
    return b.begin();
    }
 
    bits::const_iterator bits::begin() const
    {
    return b.begin();
    }
 
    bits::iterator bits::end()
    {
    return b.end();
    }
 
    bits::const_iterator bits::end() const
    {
    return b.end();
    }
 
    bool bits::operator == (const bits& rhs) const
    {
    return (size() == rhs.size() && std::equal(begin(), end(), rhs.begin()));
    }
 
    bool bits::operator <  (const bits& rhs) const
    {
    return std::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end());
    }
}
 
std::ostream& operator << (std::ostream& os, const my::bits& rhs)
{
    std::copy(rhs.begin(), rhs.end(), std::ostream_iterator<bool>(os, ""));
    return os;
}
Класс линейного многочлена. Файл linear_polynom.hpp:
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
#ifndef LINEAR_POLYNOM_HPP
#define LINEAR_POLYNOM_HPP
 
#include <iosfwd>
 
namespace my
{
    class linear_polynom
    {
    private:
    double a, b;
    
    public:
    linear_polynom();
    linear_polynom(double, double);
    linear_polynom(const linear_polynom&);
 
    double& first();
    const double& first() const;
    double& second();
    const double& second() const;
 
    bool operator == (const linear_polynom&) const;
    bool operator <  (const linear_polynom&) const;
    };
}
 
std::ostream& operator << (std::ostream&, const my::linear_polynom&);
 
#endif
Файл linear_polynom.cc:
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
#include "linear_polynom.hpp"
 
#include <iostream>
 
namespace my
{
    linear_polynom::linear_polynom()
    : a(), b()
    {
    }
 
    linear_polynom::linear_polynom(double f, double s)
    : a(f), b(s)
    {
    }
 
    linear_polynom::linear_polynom(const linear_polynom& rhs)
    : a(rhs.a), b(rhs.b)
    {
    }
 
    double& linear_polynom::first()
    {
    return a;
    }
 
    const double& linear_polynom::first() const
    {
    return a;
    }
    
    double& linear_polynom::second()
    {
    return b;
    }
 
    const double& linear_polynom::second() const
    {
    return b;
    }
 
    bool linear_polynom::operator == (const linear_polynom& rhs) const
    {
    return a == rhs.a && b == rhs.b;
    }
 
    bool linear_polynom::operator <  (const linear_polynom& rhs) const
    {
    if(a < rhs.a)
        return true;
    if(rhs.a < a)
        return false;
    return b < rhs.b;
    }    
}
 
std::ostream& operator << (std::ostream& os,
               const my::linear_polynom& rhs)
{
    double a = rhs.first();
    double b = rhs.second();
    if(a == 0)
    {
    if(b == 0)
        os << 0;
    else
        os << b;
    }
    else
    {
    os << a << "x";
    if(b > 0)
        os << " + " << b;
    else if(b < 0)
        os << " - " << -b;
    }
    return os;
}
Главный файл программы main.cc:
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
#include <iostream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
 
#include "tree.hpp"
#include "bits.hpp"
#include "linear_polynom.hpp"
 
int main()
{
    my::tree<int> itree;
 
    std::cout << "Operations with tree of numbers:" << std::endl;
    
    for(int num: {25, 10, 40, 14, 22, 33, 9, 13, 2, 5, 7, 24, 18})
    {
    std::cout << "Adding number: " << num << std::endl;
    itree.insert(num);
    }
 
    std::vector<int> vec = itree.traverse_symmetric();
    std::cout << "Traversing initial integer tree:" << std::endl;
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl << std::endl;
 
    for(int num: {40, 13, 22, 6, 100500})
    {
    std::cout << "Removing number: " << num << std::endl;
    try
    {
        if(!itree.member(num))
        std::cout << "Warning: number " << num << " is not in tree; "
              << "an exception will be thrown" << std::endl;
        
        itree.remove(num);
    }
    catch(std::exception& e)
    {
        std::cerr << "Failed to remove number " << num << ": "
              << e.what() << std::endl;
    }
    }
 
    vec = itree.traverse_symmetric();
    std::cout << "Traversing integer tree with removed numbers:" << std::endl;
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl << std::endl;
 
    std::cout << "Operations with tree of bits:" << std::endl;
    
    my::bits bits[] = {{true, false, false, true},
               {true, false, true},
               {true},
               {true, false, true, true, false, true},
               {true, true, true},
               {true, false, false, false},
               {true, true, true, true, true, false, true},            
               {true, true, true, false, true}};
 
    my::tree<my::bits> btree;
 
    
    for(auto bit: bits)
    {
    std::cout << "Adding bit: " << bit << std::endl;
    btree.insert(bit);
    }
 
    std::vector<my::bits> bvec = btree.traverse_symmetric();
    
    std::cout << "Traversing initial bits tree:" << std::endl;
    
    for(auto bit: bvec)
    {
    std::cout << bit << std::endl;
    }
    
    std::cout << std::endl;
 
    std::cout << "Operations with tree of linear polynoms (lp-tree):" << std::endl;
 
    my::tree<my::linear_polynom> lptree;
 
    std::vector<my::linear_polynom> lpvec;
    
    lpvec.push_back(my::linear_polynom());
    lpvec.push_back(my::linear_polynom(0, 3));
    lpvec.push_back(my::linear_polynom(4, 5));
    lpvec.push_back(my::linear_polynom(2, 2));
    lpvec.push_back(my::linear_polynom(2, -3));
    lpvec.push_back(my::linear_polynom(4, 1));
    lpvec.push_back(my::linear_polynom(2, 0));
    lpvec.push_back(my::linear_polynom(-3, 2));
    lpvec.push_back(my::linear_polynom(5, 1));
    lpvec.push_back(my::linear_polynom(-1, 0));
    lpvec.push_back(my::linear_polynom(-4, -5));
    lpvec.push_back(my::linear_polynom(0, -5));
    
    for(auto lp: lpvec)
    {
    std::cout << "Adding linear polynom: " << lp << std::endl;
    lptree.insert(lp);
    }
 
    std::cout << "Traversing initial lp-tree:" << std::endl;
    lpvec = lptree.traverse_symmetric();
    for(auto lp: lpvec)
    {
    std::cout << lp << std::endl;
    }
    
    std::cout << std::endl;
    
    return 0;
}
Кстати, никто не подскажет, почему мне не удается вывести элементы векторов bvec, lpvec с помощью алгоритма std::copy?
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru