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

С++ для начинающих

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

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

04.11.2011, 12:21. Просмотров 3319. Ответов 16
Метки нет (Все метки)

дали задание реализовать класс множество через двусвязный список.

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

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

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

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

//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 минуты
забыл добавить, элементами множества являются целые числа
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2011, 12:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация класса множество через двусвязный список. (C++):

Реализация класса «двусвязный список» - C++
потребовалось выполнить такое задание, вот только не могу сообразить с чего начать и как собственно будет выглядеть код (в связи с тем, что...

Множество через двусвязный список. - C++
Необходимо реализовать класс множество через двусвязный список. Но проблема у меня стоит в том, что тему списки я не очень понял, когда...

Реализация класса "Двусвязный список" - C++
Ребята, привет! Прошу помощи... Есть вот такая задача и код:

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

Составить двусвязный список на основе класса, объекты которого будут формировать этот список - C++
Составить двусвязный список на основе класса, объекты которого будут формировать этот список. В описание класса должны входить данные для...

Шаблон класса двусвязный список - C++
Доброго времени суток! Препод дал задание реализовать шаблон класса двусвязный список. Сам класс написал, но не знаю как сделать из него...

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

Добавлено через 3 минуты
Nameless One, я наверное не очень понял алгоритм добавления элемента... но понял идею
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
04.11.2011, 14:56 #9
Цитата Сообщение от 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
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 16:01  [ТС] #12
он на prev ругается
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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
2 / 1 / 0
Регистрация: 17.11.2010
Сообщений: 121
05.11.2011, 16:18  [ТС] #14
Необработанное исключение в "0x774215ee" в "Set.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000".

не работает именно на этом условии
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2011, 16:21
Привет! Вот еще темы с ответами:

Шаблон класса двусвязный список - C++
Для решения задачи описать и использовать шаблон класса &quot;двусвязный список&quot;. Необходимо составить программу которая содержит...

Кольцевой двусвязный список шаблон класса ошибки - C++
Код выдаёт некоторые ошибки (прикрепили, на картинке): Что исправить? #include &quot;StdAfx.h&quot; #ifndef __list #define...

Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список» - C++
Всем добрый вечер! Помогите пожалуйста с лабораторной работой, дело в том что скоро сдавать, а я в С++ новичок. и совсем не понимаю как это...

Двусвязный список через абстрактный класс - C++
Здравствуйте, пожалуйста помогите со следующим кодом. Застрял на добавлении элементов в двусвязный список (метод void DList::Push(int data)...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.11.2011, 16:21
Ответ Создать тему
Опции темы

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