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

Реализация класса множество через двусвязный список. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.63
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
04.11.2011, 12:21     Реализация класса множество через двусвязный список. #1
дали задание реализовать класс множество через двусвязный список.

Сам класс список мне реализовать вроде удалось, но стоит загвоздка в том, как реализовать некоторые функции для множества: пересечение множеств (*), объединение множеств(+), и разность множеств (-), поиск заданного элемента, удаление и добавление его.

для пересечение множеств (*), объединение множеств(+), и разность множеств (-) думаю стоит переопределять операции *, + и - соответственно.

пересечение: в новое множество идут только общие элементы двух мн-в.
объединение: в новое мн-во идут все элементы, причем они не должны повторяться.
разность: в новое мн-во идут элементы, которые есть в первом, но нет во втором.

вот что у меня пока реализовано.

//Set_list.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
#pragma once
#ifndef Set_list_h
#define Set_list_h
class Set_list
{
public:
    Set_list(void);
    ~Set_list(void);
 
 
    void push_begin(int value);             //добавление в начало списка
    void push_end(int value);               //добавление в конец списка
 
    void print_all();                       //печать списка
    void print_all_rev();                   //печать списка в обратном порядке
    
    int print_count();                      //размерность множества
    void clear();                           //очистить список
    bool clear_one(int num);                //удалить элемент
    
    int select(int num);                    //вывести элемент
 
 
protected:
    struct node
    {
        int data;
 
        node *next;
        node *prev;
 
        node(int value, node *n, node *p) : data(value), next(n), prev(p) {}
    };
 
    node *end;
    node *first;
    int count;
 
private:
    Set_list(const Set_list & rhs);                 //конструктор копирования
    Set_list& operator=(const Set_list & rhs);      //конструктор присваивания
};
 
#endif

//Set_list.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
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
#include "StdAfx.h"
#include "Set_list.h"
#include <iostream>
using namespace std;
 
Set_list::Set_list(void) : count(0), first(NULL), end(NULL)
{
}
 
 
Set_list::~Set_list(void)
{
    clear();
}
 
/* ------- */
/* ФУНКЦИИ */
/* ------- */
 
// добавление записи в начало списка
void Set_list::push_begin(int value)
{
    first = new node(value, first, 0);
    
    if(!count)
         end = first;
    
    node *ptr = first->next;
    if(ptr)
         ptr->prev = first;
 
    count++;
}
 
// добавление записи в конец списка
void Set_list::push_end(int value)
{
    end = new node(value, NULL, end);
    
    if (!count)
       first = end;
    
    node *ptr = end->prev;
    if (ptr)
       ptr->next = end;
 
    count++;
}
 
// печать списка
void Set_list::print_all()
{
    node *ptr = first;
    
    while (ptr)
    {
        cout<<ptr->data<<"\n";
        ptr = ptr->next;
    }
}
 
// печать списка в обратном порядке
void Set_list::print_all_rev()
{
    node *ptr = end;
    
    while (ptr)
    {
        cout<<ptr->data<<"\n";
        ptr = ptr->prev;
    }
}
 
// кол-во элементов
int Set_list::print_count()
{
     return count;
}
 
// выборка элемента по порядковому номеру
int Set_list::select(int num)
{
    if(!count || !num || num>count+1)
         return 0;
    
    int cnt=0;
         
    node *ptr = first;
    
    while (ptr)
    {
         cnt++;
         if (num==cnt)
              return ptr->data;
         ptr = ptr->next;
    }
}
 
// удаление произвольного элемента
bool Set_list::clear_one(int num)
{
    if(!count || !num || num>count+1)
         return false;
    
    int cnt=0;
         
    node *ptr = first;
    
    while (ptr)
    {
         cnt++;
         if (num==cnt) {
              node *ptr_prev = ptr->prev;
              node *ptr_next = ptr->next;
              
              if(ptr_prev)
                   ptr_prev->next = ptr_next;
              if(ptr_next)
                   ptr_next->prev = ptr_prev;
              
              delete ptr;
              
              count--;
              return true;
         }
         ptr = ptr->next;
    }
}
 
// удаление всего списка
void Set_list::clear()
{
     while (first)
     {
          node *ptr = first;
          first = ptr->next;
          delete ptr;
     }
     end = first;
     
     count = 0;
}


осталось дописать функции, о которых сказано выше, но я что-то не знаю, как это сделать....

Добавлено через 42 минуты
забыл добавить, элементами множества являются целые числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LosAngeles
Заблокирован
04.11.2011, 12:29     Реализация класса множество через двусвязный список. #2
ну судя по заданию, по тому что в скобочках написаны +-* то наверно требуется перегрузка операторов. Пишешь например
C++
1
Set_list const operator+(Set_list const& another) {...};
константа возвращается, чтобы не было курьёзов типа
C++
1
if (list1 = list2) ...
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
04.11.2011, 12:30  [ТС]     Реализация класса множество через двусвязный список. #3
я перегрузку и предложил, мне сама реализация не очень понятна...
LosAngeles
Заблокирован
04.11.2011, 12:52     Реализация класса множество через двусвязный список. #4
ну если ты хранишь множество в виде списка, то таких функций типа добавить в начало или в конец быть не должно, должна быть функция которая добавляет элемент между двумя соседними или как это правильно сказать, короче список должен быть отсортированным, тогда сложность объединения например будет О(н) вместо О(н*м). Тип алгоритма для отсортированного списка называется слиянием, псевдокод ли даже код думаю легко можно нагуглить
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
04.11.2011, 12:52     Реализация класса множество через двусвязный список. #5
Fantom.AS, храни элементы в множестве в упорядоченном состоянии. Вот алгоритм добавления элемента:
Положим, у тебя сначала есть указатель на первый элемент списка. Цикл:
  1. Если указатель указывает на NULL, то создаешь новый узел со значением добавляемого элемента и устанавливаешь текущий указатель на этот узел. Конец цикла
  2. Если значение узла, на который указывает указатель, равно значению добавляемого элемента, то ничего не делаешь. Конец цикла
  3. Если значения узла, на который указывает указатель, больше добавляемого значения, то создаешь новый узел со значением добавляемого элемента и помещаешь новый узел перед текущим указателем. Конец цикла
  4. Если значение узла, на который указывает указатель, больше значения добавляемого элемента, то переходишь к следующему значению указателя и к следующей итерации цикла
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
04.11.2011, 14:27  [ТС]     Реализация класса множество через двусвязный список. #6
Set_list(const Set_list & rhs); //конструктор копирования
Set_list& operator=(const Set_list & rhs); //конструктор присваивания

и еще, я конструкторы копирования и присваивания объявил, но не реализовал, тут тоже заминка вышла

Добавлено через 46 минут
вот функция сортировки, правильно реализована?

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
void Set_list::sort()
{
    int a=0;
node *last, *temp ;
node *sort_beg , *sort_end ; 
//for (temp = first; temp != end; temp = temp->next)
//{
//a++;
//}
do {
for (sort_end = end; sort_end!= first->next ; sort_end = sort_end->prev) {
if ((sort_end->prev)->data > sort_end->data) {
(sort_end->next)->prev=sort_end->prev;
(sort_end->prev)->next = sort_end->next;
(sort_end->prev)->prev = sort_end;
((sort_end->prev)->prev)->next = sort_end;
last = sort_end;
}
}
 
first = last->next;
 
for (sort_beg = first; sort_beg != end->prev ; sort_beg = sort_beg->next) {
if ((sort_beg->next)->data > sort_beg->data) {
(sort_beg->prev)->next=sort_beg->next;
(sort_beg->next)->prev = sort_beg->prev;
(sort_beg->next)->next = sort_beg;
((sort_beg->next)->next)->prev = sort_beg;
last = sort_beg;
}
}
end = last->prev;
} while (sort_beg != sort_end);
 
node *pv = first->next;
int i =0;
//while (i<a){
//i++;
//printf("%d ", pv->data);
//pv = pv->next;
//}
//printf("\n");
}
LosAngeles
Заблокирован
04.11.2011, 14:31     Реализация класса множество через двусвязный список. #7
зачем тебе она?
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
04.11.2011, 14:36  [ТС]     Реализация класса множество через двусвязный список. #8
Цитата Сообщение от LosAngeles Посмотреть сообщение
зачем тебе она?
чтобы список был отсортированным? разве нет? или я что-то не понимаю....

Добавлено через 3 минуты
Nameless One, я наверное не очень понял алгоритм добавления элемента... но понял идею
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
04.11.2011, 14:56     Реализация класса множество через двусвязный список. #9
Цитата Сообщение от Fantom.AS Посмотреть сообщение
чтобы список был отсортированным?
нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 15:34  [ТС]     Реализация класса множество через двусвязный список. #10
Цитата Сообщение от Nameless One Посмотреть сообщение
нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным
Я уже понял идею и что будет, но пока не понял, как это реализовать, хотя на интуитивном уровне алгоритм мне ясен...

Добавлено через 5 часов 37 минут
Nameless One, и все же до меня не может дойти, как реализовать твой алгоритм добавления элемента

Добавлено через 18 часов 59 минут
Цитата Сообщение от Nameless One Посмотреть сообщение
Fantom.AS, храни элементы в множестве в упорядоченном состоянии. Вот алгоритм добавления элемента:
Положим, у тебя сначала есть указатель на первый элемент списка. Цикл:
Если указатель указывает на NULL, то создаешь новый узел со значением добавляемого элемента и устанавливаешь текущий указатель на этот узел. Конец цикла
Если значение узла, на который указывает указатель, равно значению добавляемого элемента, то ничего не делаешь. Конец цикла
Если значения узла, на который указывает указатель, больше добавляемого значения, то создаешь новый узел со значением добавляемого элемента и помещаешь новый узел перед текущим указателем. Конец цикла
Если значение узла, на который указывает указатель, больше значения добавляемого элемента, то переходишь к следующему значению указателя и к следующей итерации цикла
__________________



Вот, я реализовал добавление элемента. надеюсь правильно

C++
1
2
3
4
5
6
7
8
9
10
11
void Set_list::push(int value)
{
    node *ptr = first;
    while(true)
    {   
        if (ptr=NULL){ push_end(value); break;}
        if (ptr->data==value) break;
        if (ptr->data>value) { ptr= new node(value, ptr->next, ptr->prev); break;  }
        if (ptr->data<value) {ptr=ptr->next; }
    }
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
05.11.2011, 15:47     Реализация класса множество через двусвязный список. #11
Fantom.AS, в восьмой строчке:
C++
1
2
3
4
5
6
7
8
if(ptr->data>value)
{
   prev = ptr->prev;
   node* p = new node(value, ptr, prev);
   prev->next = p;
   ptr->prev = p;
   break;
}
как-то так
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 16:01  [ТС]     Реализация класса множество через двусвязный список. #12
он на prev ругается
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
05.11.2011, 16:13     Реализация класса множество через двусвязный список. #13
Fantom.AS, ну да, он-то не объявлен
C++
1
2
3
4
5
6
7
8
if(ptr->data>value)
{
   node* prev = ptr->prev;
   node* p = new node(value, ptr, prev);
   prev->next = p;
   ptr->prev = p;
   break;
}
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 16:18  [ТС]     Реализация класса множество через двусвязный список. #14
Необработанное исключение в "0x774215ee" в "Set.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000".

не работает именно на этом условии
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
05.11.2011, 16:21     Реализация класса множество через двусвязный список. #15
C++
1
2
3
4
5
6
7
8
9
if(ptr->data>value)
{
   node* prev = ptr->prev;
   node* p = new node(value, ptr, prev);
   if(prev != NULL)
      prev->next = p;
   ptr->prev = p;
   break;
}
Fantom.AS
 Аватар для Fantom.AS
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 16:36  [ТС]     Реализация класса множество через двусвязный список. #16
нет, не работает.... та же ошибка

Добавлено через 12 минут
хотя с логической точки зрения все вроде нормально
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2011, 19:39     Реализация класса множество через двусвязный список.
Еще ссылки по теме:

Класс: Реализация через битовое поле класса "Множество" C++
C++ - Реализация класса «двусвязный список» C++
C++ Шаблон класса двусвязный список

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

Или воспользуйтесь поиском по форуму:
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
05.11.2011, 19:39     Реализация класса множество через двусвязный список. #17
Сделал наследование множества от двусвязного списка (может быть, не самое лучший вариант)
dllist.hpp

Содержит описание классов узла, двусвязного списка и простого forward-итератора для этого списка, с помощью которого можно организовать обход списка
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
#ifndef DLLIST_HPP
#define DLLIST_HPP
 
#include <cstdlib>
#include <stdexcept>
#include <cstddef>
 
template <class T>
class node
{
public:
    T value;
    node* next;
    node* prev;
    node(const T&, node<T>*, node<T>*);
};
 
template <class T>
node<T>::node(const T& val, node<T>* n, node<T>* p)
    : value(val), next(n), prev(p)
{
}
 
template <class T>
class dllist;
 
template <class T>
class dllist_iterator
{
private:
    friend class dllist<T>;
 
    dllist_iterator(node<T>*);
 
    void assert_is_valid() const;
 
    node<T>* pnode;
 
public:
 
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef size_t size_type;
    typedef std::forward_iterator_tag iterator_category;
    
    dllist_iterator();
    dllist_iterator(const dllist_iterator<T>&);
 
    dllist_iterator& operator = (const dllist_iterator<T>&);
 
    bool operator == (const dllist_iterator<T>&) const;
    bool operator != (const dllist_iterator<T>&) const;
 
    T& operator * ();
    T* operator -> ();
 
    dllist_iterator<T>& operator ++ ();
    dllist_iterator<T> operator ++ (int);
 
    bool is_valid() const;
};
 
template <class T>
dllist_iterator<T>::dllist_iterator(node<T>* p)
    : pnode(p)
{
}
 
template <class T>
dllist_iterator<T>::dllist_iterator()
    : pnode(NULL)
{
}
 
template <class T>
dllist_iterator<T>::dllist_iterator(const dllist_iterator<T>& rhs)
    : pnode(rhs.pnode)
{
}
 
template <class T>
dllist_iterator<T>& dllist_iterator<T>::operator = (const dllist_iterator<T>& rhs)
{
    pnode = rhs.pnode;
}
 
template <class T>
bool dllist_iterator<T>::operator == (const dllist_iterator<T>& rhs) const
{
    return pnode == rhs.pnode;
}
 
template <class T>
bool dllist_iterator<T>::operator != (const dllist_iterator<T>& rhs) const
{
    return pnode != rhs.pnode;
}
 
template <class T>
T& dllist_iterator<T>::operator * ()
{
    assert_is_valid();
    return pnode->value;
}
 
template <class T>
T* dllist_iterator<T>::operator -> ()
{
    assert_is_valid();
    
    return &(pnode->value);
}
 
template <class T>
dllist_iterator<T>& dllist_iterator<T>::operator ++ ()
{
    assert_is_valid();
    
    pnode = pnode->next;
    return *this;
}
 
template <class T>
dllist_iterator<T> dllist_iterator<T>::operator ++ (int)
{
    assert_is_valid();
 
    dllist_iterator<T> tmp = *this;
 
    ++(*this);
 
    return tmp;
}
 
template <class T>
void dllist_iterator<T>::assert_is_valid() const
{
    if(!is_valid())
    throw std::runtime_error("Invalid iterator");
}
 
template <class T>
bool dllist_iterator<T>::is_valid() const
{
    return pnode != NULL;
}
 
template <class T>
class dllist
{
protected:
    node<T>* head;
    node<T>* tail;
 
public:
    typedef dllist_iterator<T> iterator;
        
    dllist();
    dllist(const dllist<T>&);
 
    void push_back(const T&);
    void push_front(const T&);
 
    T pop_front();
    T pop_back();
 
    bool empty () const;
 
    dllist<T>& operator = (const dllist<T>&);
 
    iterator begin();
    iterator end();
    
    ~dllist();
};
 
template <class T>
dllist<T>::dllist()
    : head(NULL), tail(NULL)
{
}
 
template <class T>
dllist<T>::dllist(const dllist<T>& rhs)
    : head(NULL), tail(NULL)
{
    for(node<T>* pnode = rhs.head;
    pnode != NULL; pnode = pnode->next)
    push_back(pnode->value);
}
 
template <class T>
void dllist<T>::push_back(const T& value)
{
    node<T>* pnode = new node<T>(value, NULL, tail);
 
    if(tail != NULL)
    tail->next = pnode;
    else
    head = pnode;
    
    tail = pnode;
}
 
template <class T>
void dllist<T>::push_front(const T& value)
{
    node<T>* pnode = new node<T>(value, head, NULL);
 
    if(head != NULL)
    head->prev = pnode;
    else
    tail = pnode;
 
    head = pnode;
}
 
template <class T>
T dllist<T>::pop_back()
{
    if(tail == NULL)
    throw std::runtime_error("Empty list");
 
    node<T>* pnode = tail;
    T value = pnode->value;
 
    tail = tail->prev;
    
    delete pnode;
 
    if(tail == NULL)
    head = NULL;
    else
    tail->next = NULL;
 
    return value;
}
 
template <class T>
T dllist<T>::pop_front()
{
    if(head == NULL)
    throw std::runtime_error("Empty list");
 
    node<T>* pnode = head;
    T value = pnode->value;
 
    head = head->next;
    
    delete pnode;
 
    if(head == NULL)
    tail == NULL;
    else
    head->prev = NULL;
 
    return value;
}
 
template <class T>
bool dllist<T>::empty() const
{
    return head == NULL;
}
    
 
template <class T>
dllist<T>& dllist<T>::operator = (const dllist<T>& rhs)
{
    head = tail = NULL;
 
    for(node<T>* pnode = rhs.head;
    pnode != NULL; pnode = pnode->next)
    push_back(pnode->value);
 
    return *this;
}
 
template <class T>
dllist<T>::~dllist()
{
    while(head != NULL)
    {
    node<T>* pnode = head;
    head = head->next;
    delete pnode;
    }
}
 
template <class T>
typename dllist<T>::iterator dllist<T>::begin()
{
    return iterator(head);
}
 
template <class T>
typename dllist<T>::iterator dllist<T>::end()
{
    return iterator();
}
 
#endif

set.hpp
Содержит описание класса множества (унаследован от dllist). Интересующий тебя метод - это метод insert (остальные операции над множеством реализуются аналогично)
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
#ifndef SET_HPP
#define SET_HPP
 
#include "dllist.hpp"
 
template <class T>
class set: protected dllist<T>
{
public:
 
    typedef typename dllist<T>::iterator iterator;
 
    set();
    set(const set<T>&);
    ~set();
 
    set<T>& operator = (const set<T>&);
 
    void insert(const T&);
 
    bool empty() const;
 
    iterator begin();
    iterator end();
};
 
template <class T>
set<T>::set()
    : dllist<T>()
{
}
 
template <class T>
set<T>::set(const set<T>& rhs)
    : dllist<T>()
{
    for(node<T>* pnode = rhs.head; pnode != NULL; pnode = pnode->next)
    push_back(pnode->value);
}
 
template <class T>
set<T>::~set()
{
    while(dllist<T>::head != NULL)
    {
    node<T>* pnode = dllist<T>::head;
    dllist<T>::head = dllist<T>::head->next;
    delete pnode;
    }
}
 
template <class T>
set<T>& set<T>::operator = (const set<T>& rhs)
{
    dllist<T>::head = dllist<T>::tail = NULL;
        
    for(node<T>* pnode = rhs.head; pnode != NULL; pnode = pnode->next)
    push_back(pnode->value);
 
    return *this;
}
 
template <class T>
void set<T>::insert(const T& value)
{
    node<T>* pnode = dllist<T>::head;
 
    while(true)
    {
    if(pnode == NULL)
    {
        push_back(value);
        break;
    }
    
    else if(pnode->value > value)
    {
        node<T>* newnode = new node<T>(value, pnode, pnode->prev);
 
        node<T>* prev = pnode->prev;
 
        if(prev != NULL)
        prev->next = newnode;
        else
        dllist<T>::head = newnode;
        
        pnode->prev = newnode;
 
        break;
    }
    
    else if(pnode->value == value)
        break;
 
    else
        pnode = pnode->next;
    }
}
 
template <class T>
bool set<T>::empty() const
{
    return dllist<T>::empty();
}
 
template <class T>
typename set<T>::iterator set<T>::begin()
{
    return dllist<T>::begin();
}
 
template <class T>
typename set<T>::iterator set<T>::end()
{
    return dllist<T>::end();
}
 
#endif

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
#include <iostream>
#include <algorithm>
#include <iterator>
#include <ctime>
 
#include "dllist.hpp"
#include "set.hpp"
 
int main(int argc, char* argv[])
{
    srand((size_t) time(NULL));
 
    set<int> s;
 
    for(size_t i = 0; i < 5; ++i)
    {
    int n = rand() % 16;
    
    s.insert(n);
    
    std::cout << "Step #" << i + 1 << ". Inserting "
          << n << ".\nSet: ";
        
    std::copy(s.begin(), s.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    }
            
    return 0;
}

Программу особо не тестил, возможны баги
Yandex
Объявления
05.11.2011, 19:39     Реализация класса множество через двусвязный список.
Ответ Создать тему
Опции темы

Текущее время: 16:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru