집합(차집합, 교집합, 합집합) - cpp

신중히 생각해서 나누지 않고 바로 코딩에 들어갔더니 역시 구성이 마음에 들지 않는다. 쩝..
사소한 것을 코딩하더라도 천천히 생각해보고 하도록 하자!!

static을 사용해서 집합연산을 만들어봤는데 static에 관한 문법이 다른 언어들과 달라서 멈칫했었다.

element.h

/******************************************
/* element.h
/* 목적 : 링크드리스트 구성을 위한 구성요소
/* 작성 : bluelimn
/******************************************/

#ifndef element_H
#define element_H

class Element
{
private:
 int data;
 Element* link;
public:
 Element():data(0),link(NULL){}
 Element(int data, Element* link = NULL):data(data), link(link){}
 int getData(){return data;}
 void setData(int value){data = value;}
 Element* getLink(){return link;}
 void setLink(Element* link){this->link = link;}
};

#endif

mySet.h

/******************************************
/* mySet.h
/* 목적 : 집합구성과 연산
/* 작성 : bluelimn
/******************************************/

#ifndef mySets_H
#define mySets_H
#include "element.h"
class MySets
{
private:
 Element* root;
public:
 MySets(){root = new Element();}
 MySets(Element* root):root(root)
 {
  if(root == NULL) root = new Element();
 }
 ~MySets();
 Element* getRoot(){return root;}
 bool insertElement(int value);
 bool deleteElement(int value);
 bool isEmpty();
 void viewElements();
};

static class SetsOperator
{
public:
 static MySets* setsUnion(MySets* set1, MySets* set2);
 static MySets* setsIntersection(MySets* set1, MySets* set2);
 static MySets* setsRelativeComplement(MySets* set1, MySets* set2);
};
#endif

mySet.cpp

/******************************************
/* mySet.cpp
/* 목적 : 집합구성과 연산
/* 작성 : bluelimn
/******************************************/
#include <iostream>
#include "mySets.h"
using namespace std;

/**********************************************
/* MySets 클레스 구현
**********************************************/
MySets::~MySets()
{
 Element* current = root;
 Element* pre_node = current;
 while(current != NULL)
 {
  current = current->getLink();
  delete pre_node;
  pre_node = current;
 }
}

bool MySets::isEmpty()
{
 if(root->getLink() == NULL) return true;
 return false;
}

//heap으로 구현하는 것이 적당하나 이 source에서는 linked list로 구현
bool MySets::insertElement(int value)
{
 Element* current = root;
 Element* pre_node = current;
 // 오름차순으로 insert sorting한다
 // 새로운 값이 들어갈 자리 확인(입력할 값보다 큰값 앞이거나 리스트의 마지막
 while((current != NULL) && (current->getData() < value))
 {
  pre_node = current;
  current = current->getLink();
 }
 Element* newNode = new Element(value, pre_node->getLink());  //입력할 노드
 pre_node->setLink(newNode);
 return true;
}

//리스트에서 같은 값을 찾아 가장 먼저 나오는 값을 지운다
bool MySets::deleteElement(int value)
{
 Element* current = root;
 Element* pre_node = current;
 while((current->getLink() != NULL) && (current->getData() < value))
 {
  pre_node = current;
  current = current->getLink();
 }

if(current->getData() != value) return false;     //찾는 값이 리스트에 없음

pre_node->setLink(current->getLink());
 delete current;
 return true;
}

void MySets::viewElements()
{
 Element* current = root->getLink();
 while(current != NULL)
 {
  cout << current->getData() << "  ";
  current = current->getLink();
 }
 cout << endl;
}


/**********************************************
/* SetsOperator 클레스 구현
**********************************************/
//합집합
MySets* SetsOperator::setsUnion(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   temp = temp->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   temp->setLink(new Element(root2->getData(), NULL));
   root2 = root2->getLink();
   temp = temp->getLink();
  }
  else
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   root2 = root2->getLink();
   temp = temp->getLink();
  }
 }
 if(root1 == NULL && root2 != NULL) temp->setLink(root2);
 else if(root2 == NULL && root1 != NULL) temp->setLink(root1);

return new MySets(result);
}
//교집합
MySets* SetsOperator::setsIntersection(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   root1 = root1->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   root2 = root2->getLink();
  }
  else
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   root2 = root2->getLink();
   temp = temp->getLink();
  }
 }

return new MySets(result);
}
//차집합
MySets* SetsOperator::setsRelativeComplement(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   temp = temp->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   temp->setLink(new Element(root2->getData(), NULL));
   root2 = root2->getLink();
   temp = temp->getLink();
  }
  else
  {
   root1 = root1->getLink();
   root2 = root2->getLink();
  }
 }
 if(root1 == NULL && root2 != NULL) temp->setLink(root2);
 else if(root2 == NULL && root1 != NULL) temp->setLink(root1);

return new MySets(result);
}

insertSortWithSets.cpp

/******************************************
/* insertSortWithSets.cpp
/* 목적 : 두 집합의 차집합, 합집합, 교집합 연산
/* 작성 : bluelimn
/******************************************/

#include <iostream>
#include "mySets.h"
using namespace std;

int main()
{
 MySets* x = new MySets();
 MySets* y = new MySets();
 x->insertElement(10);
 x->insertElement(20);
 x->insertElement(70);
 x->insertElement(50);
 x->insertElement(30);
 x->insertElement(40);
 x->deleteElement(40);
 x->insertElement(41);
 cout << "x : ";
 x->viewElements();
 
 y->insertElement(20);
 y->insertElement(70);
 y->insertElement(10);
 y->insertElement(30);
 y->insertElement(40);
 y->deleteElement(50);
 y->deleteElement(70);
 y->insertElement(-50);
 cout << "y : ";
 y->viewElements();

 cout << "합집합 : ";
 MySets* tmp_uni = SetsOperator::setsUnion(x,y);
 tmp_uni->viewElements();

 cout << "교집합 : ";
 MySets* tmp_int = SetsOperator::setsIntersection(x,y);
 tmp_int->viewElements();

 cout << "차집합 : ";
 MySets* tmp_rel = SetsOperator::setsRelativeComplement(x,y);
 tmp_rel->viewElements();

 return 0;
}