2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|||||||||||
1 | |||||||||||
Реализация класса множество через двусвязный список.04.11.2011, 12:21. Показов 9713. Ответов 16
Метки нет (Все метки)
дали задание реализовать класс множество через двусвязный список.
Сам класс список мне реализовать вроде удалось, но стоит загвоздка в том, как реализовать некоторые функции для множества: пересечение множеств (*), объединение множеств(+), и разность множеств (-), поиск заданного элемента, удаление и добавление его. для пересечение множеств (*), объединение множеств(+), и разность множеств (-) думаю стоит переопределять операции *, + и - соответственно. пересечение: в новое множество идут только общие элементы двух мн-в. объединение: в новое мн-во идут все элементы, причем они не должны повторяться. разность: в новое мн-во идут элементы, которые есть в первом, но нет во втором. вот что у меня пока реализовано. //Set_list.h
//Set_list.cpp
осталось дописать функции, о которых сказано выше, но я что-то не знаю, как это сделать.... Добавлено через 42 минуты забыл добавить, элементами множества являются целые числа
0
|
04.11.2011, 12:21 | |
Ответы с готовыми решениями:
16
Реализация класса «двусвязный список» Множество через двусвязный список. Реализация класса "Двусвязный список" Класс: Реализация через битовое поле класса "Множество" |
Заблокирован
|
|||||||||||
04.11.2011, 12:29 | 2 | ||||||||||
ну судя по заданию, по тому что в скобочках написаны +-* то наверно требуется перегрузка операторов. Пишешь например
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|
04.11.2011, 12:30 [ТС] | 3 |
я перегрузку и предложил, мне сама реализация не очень понятна...
0
|
Заблокирован
|
|
04.11.2011, 12:52 | 4 |
ну если ты хранишь множество в виде списка, то таких функций типа добавить в начало или в конец быть не должно, должна быть функция которая добавляет элемент между двумя соседними или как это правильно сказать, короче список должен быть отсортированным, тогда сложность объединения например будет О(н) вместо О(н*м). Тип алгоритма для отсортированного списка называется слиянием, псевдокод ли даже код думаю легко можно нагуглить
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
04.11.2011, 12:52 | 5 |
Fantom.AS, храни элементы в множестве в упорядоченном состоянии. Вот алгоритм добавления элемента:
Положим, у тебя сначала есть указатель на первый элемент списка. Цикл:
1
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
||||||
04.11.2011, 14:27 [ТС] | 6 | |||||
Set_list(const Set_list & rhs); //конструктор копирования
Set_list& operator=(const Set_list & rhs); //конструктор присваивания и еще, я конструкторы копирования и присваивания объявил, но не реализовал, тут тоже заминка вышла Добавлено через 46 минут вот функция сортировки, правильно реализована?
0
|
Заблокирован
|
|
04.11.2011, 14:31 | 7 |
зачем тебе она?
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|
04.11.2011, 14:36 [ТС] | 8 |
чтобы список был отсортированным? разве нет? или я что-то не понимаю....
Добавлено через 3 минуты Nameless One, я наверное не очень понял алгоритм добавления элемента... но понял идею
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
04.11.2011, 14:56 | 9 |
нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
||||||
05.11.2011, 15:34 [ТС] | 10 | |||||
Я уже понял идею и что будет, но пока не понял, как это реализовать, хотя на интуитивном уровне алгоритм мне ясен...
Добавлено через 5 часов 37 минут Nameless One, и все же до меня не может дойти, как реализовать твой алгоритм добавления элемента Добавлено через 18 часов 59 минут Вот, я реализовал добавление элемента. надеюсь правильно
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
||||||
05.11.2011, 15:47 | 11 | |||||
Fantom.AS, в восьмой строчке:
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|
05.11.2011, 16:01 [ТС] | 12 |
он на prev ругается
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
||||||
05.11.2011, 16:13 | 13 | |||||
Fantom.AS, ну да, он-то не объявлен
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|
05.11.2011, 16:18 [ТС] | 14 |
Необработанное исключение в "0x774215ee" в "Set.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000".
не работает именно на этом условии
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
||||||
05.11.2011, 16:21 | 15 | |||||
0
|
2 / 1 / 2
Регистрация: 17.11.2010
Сообщений: 121
|
|
05.11.2011, 16:36 [ТС] | 16 |
нет, не работает.... та же ошибка
Добавлено через 12 минут хотя с логической точки зрения все вроде нормально
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
||||||||||||||||
05.11.2011, 19:39 | 17 | |||||||||||||||
Сделал наследование множества от двусвязного списка (может быть, не самое лучший вариант)
dllist.hpp
Содержит описание классов узла, двусвязного списка и простого forward-итератора для этого списка, с помощью которого можно организовать обход списка
set.hpp
Содержит описание класса множества (унаследован от dllist). Интересующий тебя метод - это метод insert (остальные операции над множеством реализуются аналогично)
main.cc
Главная функция с тестовым примером
Программу особо не тестил, возможны баги
0
|
05.11.2011, 19:39 | |
05.11.2011, 19:39 | |
Помогаю со студенческими работами здесь
17
Составить двусвязный список на основе класса, объекты которого будут формировать этот список Шаблон класса двусвязный список Шаблон класса двусвязный список Кольцевой двусвязный список шаблон класса ошибки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |