Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/29: Рейтинг темы: голосов - 29, средняя оценка - 4.55
1 / 1 / 1
Регистрация: 14.02.2015
Сообщений: 16
1

Реализация класса "Множество" и операций над множествами

05.03.2016, 09:49. Показов 5946. Ответов 11
Метки нет (Все метки)

нужно реализовать класс множество и операции над множествами в виде его методов естественно, собсно приведенный ниже код работает, однако есть пара вопросов:
1. можете оценить код, есть ли какие-нибудь замечания? может чего-то я не учла, что-то можно было сделать проще?
2. будет ли правильным создать public функцию AddList с одним параметром (входным списком) и из нее вызывать уже существующую AddList, но ее обозначить как private, как в случае с print?
3. и самое важное!! сейчас элементы множества - только целые числа и множества целых чисел, можно ли сделать как-то так чтобы элементами множества могли быть и символы и данные других типов, и одно множество могло содержать в себе элементы разных типов?

вот код:
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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
#include <iostream>
 
using namespace std;
struct member        //множество будет храниться в списке, соответственно для этого создаем структуру
{
    int value;       // хранимое значение
    member * down;
    member * next;   // указатель на следующий элемент списка
};
class heap_
{
public:
    member *head;    //голова списка
 
public:
    heap_()          //конструктор без параметров, создает пустое множество
    {
        head = new member;
        head->down = head->next = NULL;
        head->value = -1;
    }
    heap_(member *source)  //конструктор принимающий в качестве параметра список
    {
        head = new member;
        head->down = head->next = NULL;
        head->value = -1;
        AddList(head,source);
    }
    void print() // метод для отображения
    {
        cout << " heap : ";
        print(head); // просто чтобы при вызове метода для множества не передавать его голову, и сделать перенос
        cout << endl;
    }
    void operator = (heap_ Rop) // перегружаем оператор присваивания. собсно принимает на вход он объект класса который надо переписать
    {
        head->down = NULL;
        head->next = NULL;
        if (Rop.head->down != NULL)
            AddList(head, Rop.head->down);
    }
    heap_ operator +(heap_ Rop) // плюс перегружаем как объединение A+B значит что вызван метод объекта А, а входящий - В
    {
        heap_ NewList; // то что будем возвращать
        if (head->down == NULL) //если А - пустое
        {
            if (Rop.head->down != NULL) // а вот В - не пустое
                AddList(NewList.head, Rop.head->down); // просто переписываем В
        }
        else // в А что-то есть
        {
            AddList(NewList.head, head->down); // значит А полностью перепишем и..
            if (Rop.head->down != NULL) // если и в В что-то есть
            {
                member *p, *t, *tmp;
                p = Rop.head->down; // просмотрим каждый элемент из В
                while(p != NULL)
                {
                    t = NewList.head->down; // просмотрим все новое множество Н которое равно А + те из В которы не в А
                    while (1)
                    {
                        if (ElemCompare(p,t)) // и если для текущего элемента из В в Н есть такой же
                        {
                            //cout << "  not add: " << p->down->value << " , " << p->down->next->value << "  ####";
                            p = p->next; // то мы не будем его добавлять, перейдем к следующему
                            t = NewList.head->down; // и для него снова сначала посмотрим список Н
                            if (p == NULL) // если все уже из В посмотрели - выходим
                            {
                                break;
                            }
                        }
                        else if (t->next == NULL) break; // костыль (постусловие) чтобы по выходу t стоял на хвосте Н
                            else t = t->next;
                    }
                    if (p != NULL) // если найден такой неравный
                    {
                        AddElem(t, p); // втыкаем его в хвост Н
                        p = p->next;
                    }
                    else break; // если весь В просмотрели - выходим
                    //print(NewList.head);
                }
            }
        }
        return NewList; //это новое множество возвращаем
    }
    heap_ operator *(heap_ Rop) // A*B - пересечение.
    {
        heap_ NewList;   //все так же создаем новое множество
        if ((head->down != NULL)&&(Rop.head->down != NULL)) // если А и В не пустые
        {
            member *p, *t, *n_tail, *tmp;
            n_tail = NewList.head->down;
            p = head->down;
            while(p != NULL)
            {
                t = Rop.head->down;
                while (t != NULL)
                {
                    if (ElemCompare(t,p)) // смотрим оба, находим общий, пишем в новый
                    {
                        AddElem(n_tail, p);
                        if (NewList.head->down == NULL) NewList.head->down = n_tail;
                        p = p->next;
                        t = Rop.head->down;
                        if (p == NULL) break;
                    }
                    else t = t->next;
                }
                p = p->next;
            }
        }
        return NewList;
    }
    heap_ operator -(heap_ Rop) //А-В - разность(дополнение)
    {
        heap_ NewList;
        if (head->down != NULL)
        {
            if (Rop.head->down != NULL)
            {
                member *p, *t, *n_tail, *tmp;
                n_tail = NewList.head->down;
                p = head->down;
                while (p != NULL)
                {
                    t = Rop.head->down;
                    while (t != NULL)
                    {
                        if (ElemCompare(p,t)) // если оба не пустые то пролистываем А пока не найдем такой которого нет в В
                        {
                            p = p->next;
                            t = Rop.head->down;
                        }
                        else t = t->next;
                        if (p == NULL) break;
                    }
                    if (p != NULL)
                        {
                            AddElem(n_tail, p); // и его добавляем в новый
                            if (NewList.head->down == NULL) NewList.head->down = n_tail;
                        }
                    else break;
                    p = p->next;
                }
            }
            else AddList(NewList.head, head->down); // если В пуст - дополнение = А
        }
        return NewList;
    }
    heap_ operator /(heap_ Rop) // A/B - симметричная разность
    {
        heap_ NewList; // здесь по правилу - А/В = А-В + В-А
        heap_ Temp; // нужна будет временная переменная
        AddList(Temp.head, head->down);// в нее пишем А потому что перегруженный оператор не работает с this, интересно почему..
        if (head->down != NULL)
        {
            if (Rop.head->down != NULL)
            {
                NewList = Temp - Rop; // А - В
                Temp = Rop - Temp; // В-А
                AddList(NewList.head, Temp.head->down); //А-В здесь уже есть, пишем В-А
            }
            else AddList(NewList.head, head->down);// если В = 0, то А/В = А
        }
        else if (Rop.head->down != NULL) AddList(NewList.head, Rop.head->down); // если А = 0, то А/В = В
        return NewList;
    }
    heap_ operator %(heap_ Rop) // и последнее - декартово произведение A и B
    {
        heap_ NewList; //создаем новое множество
        if (head->down != NULL)
        {
            if (Rop.head->down != NULL)
            {
                member *p, *t, *n_tail, *n_head, *tmp;
                p = head->down;
                n_tail = NewList.head->down;
                while (p != NULL) // для каждого элемента из А
                {
                    t = Rop.head->down;
                    while (t != NULL)
                    {
                        //print(NewList.head);
                        //cout << endl;
                        if (ElemCompare(p,t))
                        {
                            t = t->next;
                        }
                        else
                        {
                            tmp = new member;
                            tmp->next = NULL;
                            tmp->value = -1;
                            AddElem(n_tail, tmp); // создаем в новом списке подмножество
                            if (NewList.head->down == NULL) NewList.head->down = n_tail;
                            n_head = n_tail;
                            tmp = n_head->down;
                            AddElem(tmp, p); // пишем туда сначала элемент из А
                            n_head->down = tmp;
                            AddElem(tmp, t); // а следом элемент из В
                            t = t->next;
                        }
                    }
                    p = p->next;
                }
            }
            else AddList(NewList.head, head->down);
        }
        else if (Rop.head->down != NULL) AddList(NewList.head, Rop.head->down);
        return NewList;
    }
    void AddList(member *&Head, member *Source)
    {
        member *tmp, *Tail;
        Tail = Head->down;
        if (Tail != NULL)
            while (Tail->next != NULL)
                Tail = Tail->next;
        while (Source != NULL)
        {
            if (Source->down == NULL)
            {
                AddElem(Tail, Source);
                if (Head->down == NULL) Head->down = Tail;
            }
            else
            {
                tmp = new member;
                tmp->value = -1;
                AddElem(Tail, tmp);
                if (Head->down == NULL) Head->down = Tail;
                AddList(Tail,Source->down);
            }
        Source = Source->next;
        }
    }
 
private:
    void AddElem (member *&Position, member *source)
    {
        member *Element;
        Element = new member;
        Element->value = source->value;
        if (source->down != NULL)
        {
            Element->down = NULL;
            Element->next = NULL;
            if (Position != NULL) Position->next = Element;
            Position = Element;
            AddList(Position,source->down);
        }
        else if (Position == NULL)
            {
                Position = Element;
                Position->next = NULL;
                Position->down = NULL;
            }
            else
            {
                Position->next = Element;
                Position = Element;
                Position->down = NULL;
                Position->next = NULL;
            }
    }
    bool ElemCompare(member *X1, member *X2)
    {
        if (X1->down == NULL)
        {
            if (X2->down == NULL)
            {
                if (X1->value != X2->value)
                {
                    return false;
                }
            }
            else return false;
        }
        else if (X2->down != NULL)
              {
                  if (!ListCompare(X1->down,X2->down)) return false;
              }
             else return false;
        return true;
    }
    bool ListCompare(member *X1, member *X2)
    {
        member *a = X1, *b = X2;
        while (a != NULL)
        {
            b = X2;
            while (b != NULL)
            {
                if (ElemCompare(a,b)) break;
                else b = b->next;
            }
            if (b == NULL) return false;
            else a = a->next;
        }
        return true;
    }
    void print(member *Head) //рекурсивная функция для обхода и вывода структуры
    {
        member *point;
        point = Head;
        while (point != NULL) // проходим весь список
        {
            if (point->down == NULL)
                cout << point->value;
            else
            {
                cout << "{";
                print(point->down);
                cout << "}";
            }
            if (point->next != NULL)
                cout << ",";
            point = point->next;
        }
    }
};
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.03.2016, 09:49
Ответы с готовыми решениями:

Класс: Реализация через битовое поле класса "Множество"
Реализация через битовое поле. Как сделать ввод и вывод множества и так чтобы элементы хранились в...

Шаблонный класс "множества". Операции над множествами
Доброго времени суток. Суть моего задания заключается в создании шаблонного класса &quot;множества&quot; и...

Реализация класса "Студент" и наследование от него класса "Аспирант"
Помогите, пожалуйста! Создать абстрактный базовый класс Person, описывающий обычного человека....

Объяснить что такое "раздельная компиляция", что такое "интерфейс класса" и "реализация класса" на примере
Есть класс, содержащий объекты и конструктор. Конструктор объявляется в одном из cpp файлов(их...

11
5 / 5 / 7
Регистрация: 15.02.2016
Сообщений: 19
05.03.2016, 14:11 2
Впринципе, одно множество может содержать в себе элементы разных типов. Мне кажется, что самым легким способом будет создание класса данных с чистой виртуальной функцией и породить от этого класса другие классы с нужными Вам типами данных( как бы абстрактные типы данных). Value будет иметь тип - указатель на базовый класс. После чего, уже при вводе будет определяться или вводиться пользователем нужный тип данных, а с помощью new и уже нужного в данный момент конструктора класса будет создаваться элемент(указатели на порожденные классы совместимы по типу с указателем на базовый, а виртуальная функция позволит компилятору смотреть не на тип указателя, а на объект на который он указывает, что в свою очередь позволит вам написать одноименные методы для вывода в каждом порожденном классе) В "ООП в C++" Р.Лафоре вроде это очень хорошо описывается при реализации стека с разными типами данных
1
52 / 52 / 24
Регистрация: 24.12.2011
Сообщений: 133
05.03.2016, 14:45 3
1) вроде бы всё нормально
2) да, в функции не должно быть лишних параметров, то есть если добавляем список, то этот список и должен быть единственным параметром; с другой стороны, лучше называй все функции по-разному, чтобы не путаться
3) можно, например, использовать полиморфизм, но для этого придётся определять классы для данных самому; вот, например, так:
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
// Example program
#include <iostream>
#include <string>
 
using namespace std;
 
class abstract_data
{
    public:
    virtual void print() = 0;    
};
 
class my_int: public abstract_data
{
    int i;
    
    public:
    my_int(int _i)
    {
        i = _i;
    }
    
    virtual void print()
    {
        cout << i;    
    }
};
 
class my_double: public abstract_data
{
    double d;
    
    public:
    my_double(double _d)
    {
        d = _d;
    }
    
    virtual void print()
    {
        cout << d;    
    }
};
 
int main()
{
    abstract_data *p1, *p2;
 
    p1 = new my_int(777);
    p2 = new my_double(3.142);
    
    p1->print(); // 777
    cout << endl;
    p2->print(); // 3.142
    
    return 0;
}
Здесь объекты одинакового типа по факту хранят объекты разного типа.
1
1 / 1 / 1
Регистрация: 14.02.2015
Сообщений: 16
05.03.2016, 21:31  [ТС] 4
хмм.. спасибо, попробую так)
0
1363 / 1000 / 316
Регистрация: 28.07.2012
Сообщений: 2,769
05.03.2016, 21:49 5
Цитата Сообщение от enanthamelle Посмотреть сообщение
может чего-то я не учла
Деструктор, конструктор копирования.
0
1 / 1 / 1
Регистрация: 14.02.2015
Сообщений: 16
05.03.2016, 22:22  [ТС] 6
ну деструктор, я так поняла, не всегда необходим.. но в принципе да, забыла, тем более там где есть new, должен быть delete.. а конструктор копирования - это как? не совсем поняла..
0
52 / 52 / 24
Регистрация: 24.12.2011
Сообщений: 133
05.03.2016, 23:21 7
enanthamelle, это конструктор вида my_class(my_class &). Он вызывается, например, во время присваивания:
C++
1
2
my_class c1();
my_class c2 = c1; // вот здесь
0
Don't worry, be happy
17272 / 10144 / 1963
Регистрация: 27.09.2012
Сообщений: 25,378
Записей в блоге: 1
06.03.2016, 01:34 8
Цитата Сообщение от Juffin Посмотреть сообщение
Он вызывается, например, во время присваивания:
Во время присваивания вызывается operator=,
а не конструктор копирования.
Цитата Сообщение от Juffin Посмотреть сообщение
C++
1
my_class c2 = c1; // вот здесь
Это не присваивание.
0
52 / 52 / 24
Регистрация: 24.12.2011
Сообщений: 133
06.03.2016, 02:00 9
Да, прошу прощения, я тут напутал всё, что можно.
0
1 / 1 / 1
Регистрация: 14.02.2015
Сообщений: 16
07.03.2016, 14:53  [ТС] 10
а что значит вот эта строка?
Цитата Сообщение от Juffin Посмотреть сообщение
virtual void print() = 0;
0
BrainOverflow
125 / 129 / 64
Регистрация: 31.03.2013
Сообщений: 556
07.03.2016, 14:54 11
enanthamelle, виртуальная функция, делает класс абстрактным.
Абстрактные классы
1
Don't worry, be happy
17272 / 10144 / 1963
Регистрация: 27.09.2012
Сообщений: 25,378
Записей в блоге: 1
07.03.2016, 14:58 12
Цитата Сообщение от Sabnik18 Посмотреть сообщение
виртуальная функция
pure virtual
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.03.2016, 14:58

Перегрузка операций АТД "Множество элементов типа char"
Нужен код С++ Порядок выполнения работы. 1. Выбрать класс абстрактного типа данных (АТД) в...

Класс "Множество" и операции над ним
Не хватает опыта понять ошибку Здравствуйте! Никак не получается тот же результат хотя проверял...

Перегрузка операций методами класса "Круг"
Класс – круг на плоскости: Переопределить методами класса операции:  Объект1=Объект2...

Перегрузка операций для класса "Полином"
Не знаю как делать задания( Прошу помощи 1) Ввести класс для работы с объектом «полином»....


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

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

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