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

@Fantom.AS · Регистрация: 17.11.2010

Author24 — интернет-сервис помощи студентам

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

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

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

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

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

//Set_list.h

C++

#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++

#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

ну судя по заданию, по тому что в скобочках написаны +-* то наверно требуется перегрузка операторов. Пишешь например

C++

1	Set_list const operator+(Set_list const& another) {...};

константа возвращается, чтобы не было курьёзов типа

C++

1	if (list1 = list2) ...

@Fantom.AS · 04.11.2011, 12:30 **[ТС]**

я перегрузку и предложил, мне сама реализация не очень понятна...

@~~LosAngeles~~ · 04.11.2011, 12:52

ну если ты хранишь множество в виде списка, то таких функций типа добавить в начало или в конец быть не должно, должна быть функция которая добавляет элемент между двумя соседними или как это правильно сказать, короче список должен быть отсортированным, тогда сложность объединения например будет О(н) вместо О(н*м). Тип алгоритма для отсортированного списка называется слиянием, псевдокод ли даже код думаю легко можно нагуглить

@Nameless One · 04.11.2011, 12:52

Fantom.AS, храни элементы в множестве в упорядоченном состоянии. Вот алгоритм добавления элемента:
Положим, у тебя сначала есть указатель на первый элемент списка. Цикл:

Если указатель указывает на NULL, то создаешь новый узел со значением добавляемого элемента и устанавливаешь текущий указатель на этот узел. Конец цикла
Если значение узла, на который указывает указатель, равно значению добавляемого элемента, то ничего не делаешь. Конец цикла
Если значения узла, на который указывает указатель, больше добавляемого значения, то создаешь новый узел со значением добавляемого элемента и помещаешь новый узел перед текущим указателем. Конец цикла
Если значение узла, на который указывает указатель, больше значения добавляемого элемента, то переходишь к следующему значению указателя и к следующей итерации цикла

@Fantom.AS · 04.11.2011, 14:27 **[ТС]**

Set_list(const Set_list & rhs); //конструктор копирования
Set_list& operator=(const Set_list & rhs); //конструктор присваивания

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

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

C++

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

зачем тебе она?

@Fantom.AS · 04.11.2011, 14:36 **[ТС]**

Сообщение от LosAngeles

зачем тебе она?

чтобы список был отсортированным? разве нет? или я что-то не понимаю....

Добавлено через 3 минуты
Nameless One, я наверное не очень понял алгоритм добавления элемента... но понял идею

@Nameless One · 04.11.2011, 14:56

Сообщение от Fantom.AS

чтобы список был отсортированным?

нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным

@Fantom.AS · 05.11.2011, 15:34 **[ТС]**

Сообщение от Nameless One

нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным

Я уже понял идею и что будет, но пока не понял, как это реализовать, хотя на интуитивном уровне алгоритм мне ясен...

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

Добавлено через 18 часов 59 минут

Сообщение от Nameless One

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

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

C++

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 · 05.11.2011, 15:47

Fantom.AS, в восьмой строчке:

C++

if(ptr->data>value)
{
   prev = ptr->prev;
   node* p = new node(value, ptr, prev);
   prev->next = p;
   ptr->prev = p;
   break;
}

как-то так

@Fantom.AS · 05.11.2011, 16:01 **[ТС]**

он на prev ругается

@Nameless One · 05.11.2011, 16:13

Fantom.AS, ну да, он-то не объявлен

C++

if(ptr->data>value)
{
   node* prev = ptr->prev;
   node* p = new node(value, ptr, prev);
   prev->next = p;
   ptr->prev = p;
   break;
}

@Fantom.AS · 05.11.2011, 16:18 **[ТС]**

Необработанное исключение в "0x774215ee" в "Set.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000".

не работает именно на этом условии

@Nameless One · 05.11.2011, 16:21

C++

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 · 05.11.2011, 16:36 **[ТС]**

нет, не работает.... та же ошибка

Добавлено через 12 минут
хотя с логической точки зрения все вроде нормально

@Nameless One · 05.11.2011, 19:39

Сделал наследование множества от двусвязного списка (может быть, не самое лучший вариант)

dllist.hpp

Содержит описание классов узла, двусвязного списка и простого forward-итератора для этого списка, с помощью которого можно организовать обход списка

C++

#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++

#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++

#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;
}

Программу особо не тестил, возможны баги

@Fantom.AS 2 / 1 / 2 Регистрация: 17.11.2010 Сообщений: 121
	04.11.2011, 12:30 [ТС]	3
	я перегрузку и предложил, мне сама реализация не очень понятна... 0

@~~LosAngeles~~ Заблокирован
	04.11.2011, 12:52	4
	ну если ты хранишь множество в виде списка, то таких функций типа добавить в начало или в конец быть не должно, должна быть функция которая добавляет элемент между двумя соседними или как это правильно сказать, короче список должен быть отсортированным, тогда сложность объединения например будет О(н) вместо О(н*м). Тип алгоритма для отсортированного списка называется слиянием, псевдокод ли даже код думаю легко можно нагуглить 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	04.11.2011, 12:52	5
	Fantom.AS, храни элементы в множестве в упорядоченном состоянии. Вот алгоритм добавления элемента: Положим, у тебя сначала есть указатель на первый элемент списка. Цикл: Если указатель указывает на NULL, то создаешь новый узел со значением добавляемого элемента и устанавливаешь текущий указатель на этот узел. Конец цикла Если значение узла, на который указывает указатель, равно значению добавляемого элемента, то ничего не делаешь. Конец цикла Если значения узла, на который указывает указатель, больше добавляемого значения, то создаешь новый узел со значением добавляемого элемента и помещаешь новый узел перед текущим указателем. Конец цикла Если значение узла, на который указывает указатель, больше значения добавляемого элемента, то переходишь к следующему значению указателя и к следующей итерации цикла 1

@~~LosAngeles~~ Заблокирован
	04.11.2011, 14:31	7
	зачем тебе она? 0

@Fantom.AS 2 / 1 / 2 Регистрация: 17.11.2010 Сообщений: 121
	04.11.2011, 14:36 [ТС]	8
	Сообщение от LosAngeles зачем тебе она? чтобы список был отсортированным? разве нет? или я что-то не понимаю.... Добавлено через 3 минуты Nameless One, я наверное не очень понял алгоритм добавления элемента... но понял идею 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	04.11.2011, 14:56	9
	Сообщение от Fantom.AS чтобы список был отсортированным? нет, это уже лишнее. У тебя функция добавления элемента будет обладать свойством, что результирующий список будет уже отсортированным 0

@Fantom.AS 2 / 1 / 2 Регистрация: 17.11.2010 Сообщений: 121
	05.11.2011, 16:01 [ТС]	12
	он на prev ругается 0

@Fantom.AS 2 / 1 / 2 Регистрация: 17.11.2010 Сообщений: 121
	05.11.2011, 16:18 [ТС]	14
	Необработанное исключение в "0x774215ee" в "Set.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000". не работает именно на этом условии 0

@Fantom.AS 2 / 1 / 2 Регистрация: 17.11.2010 Сообщений: 121
	05.11.2011, 16:36 [ТС]	16
	нет, не работает.... та же ошибка Добавлено через 12 минут хотя с логической точки зрения все вроде нормально 0