자료구조 및 실습 - [5] 집합 실습문제 (파이썬으로 합집합, 교집합, 차집합, 소속과 부분집합 구현)(2)

두 개의 집합 A와 B를 입력받아, A가 B의 부분집합인지 검사하는 프로그램과 교집합, 합집합, 차집합을 구하는 프로그램을 헤더 & 트레일러 이중연결리스트 형태로 구축하시오.

 

어려워 보일수 있지만 이전 게시글의 의사코드를 참고한다면 쉽게 구축할 수 있다.

https://mainyoung.tistory.com/25

class Node:
  def __init__(self,data,prev=None,next = None):
    self.data = data
    self.prev = prev
    self.next = next

#이중연결리스트로 구성된 집합
class DLset:
  def __init__(self):
    self.header = Node("Header")
    self.trailer = Node("Trailer",self.header)
    self.header.next = self.trailer
    self.setsize = 0

  def isEmpty(self):
    if self.setsize ==0:
      return True
    else:
      return False

  def printset(self):
    if self.setsize == 0:
      print("공집합")
    else:
      target = self.header
      for i in range(self.setsize):
        target = target.next
        print(target.data,end=" <=> ")

  # def member(self,e):
  #   if self.setsize == 0:
  #     return False

  #   else:
  #     target = self.header
  #     for i in range(self.setsize):
  #       target = target.next
  #       if target.data == e:
  #         return True
  #   return False
  def member(self,e):
    if self.setsize ==0:
      return False
    target = self.header.next
    while True:
      a = target.data
      if a<e:
        if target.next == None:
          return False
        else:
          target = target.next
      elif a>e:
        return False
      else:
        return True
  
  def addelem(self,e):
    # if self.setsize==0:
    #   newnode = Node(e,self.header,self.trailer)
    #   self.header.next= newnode
    #   self.trailer.prev = newnode

    
    # else:
    #   target = self.header
    #   newnode = Node(e) #삽입할거 생성
    #   for i in range(self.setsize):
    #     target = target.next
    #   target.next.prev
    #   target.next = newnode #연결1
    #   newnode.prev = target #연결2

    # print(f"before : {self.trailer.prev.prev.data}")#" <=> {self.trailer.prev.data}")" <=> {self.trailer.data}")
    newnode = Node(e,None,self.trailer)#Newnode_prev : None / Newnode_next = trailer
    prev_trailer = self.trailer.prev
    newnode.prev = prev_trailer#Newnode_prev : 전에 trailer에 연결됐었던 노드  / Newnode_next = trailer
    prev_trailer.next = newnode
    self.trailer.prev = newnode #trailer설정완료
    #print(f"After : {self.trailer.prev.prev.data} <=> {self.trailer.prev.data} <=> {self.trailer.data}")

    
    self.setsize +=1
    

  def removeElem(self, e):
    if self.setsize==0:
      print("Invalid position")
    
    else:
      target = self.header
      for i in range(self.setsize):
        target = target.next
        if target.data == e:
          break
      prevnode = target.prev
      nextnode = target.next
      d = target.data
      prevnode.next = nextnode
      nextnode.prev = prevnode
      del(target)
      self.setsize -=1

  def union(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        c.append(a)
        self.removeElem(a)
      elif a>b:
        c.append(b)
        B.removeElem(b)
      else:
        c.append(a)
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      c.append(a)
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      c.append(b)
      B.removeElem(b)
    return c
  
  def intersect(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        self.removeElem(a)
      elif a>b:
        B.removeElem(b)
      else:
        c.append(a)
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      B.removeElem(b)
    return c

  def subtract(self,B):
    c = []
    while (not self.isEmpty()) and (not B.isEmpty()):
      a = self.header.next.data
      b = B.header.next.data
      if a<b:
        c.append(a)
        self.removeElem(a)
      elif a>b:
        B.removeElem(b)
      else:
        self.removeElem(a)
        B.removeElem(b)
    
    while not self.isEmpty():
      a = self.header.next.data
      c.append(a)
      self.removeElem(a)
    
    while not B.isEmpty():
      b = B.header.next.data
      B.removeElem(b)
    return c
  
  def subset(self,B):
    if self.setsize ==0:
      return True
    target = self.header.next
    while True:
      if B.member(target.data):
        if target.next == None:
          return True
        else:
          target = target.next
      else:
        return False

https://mainyoung.tistory.com/25

>>> A = DLset()
>>> B = DLset()
>>> A.addelem(1)
>>> A.addelem(2)
>>> A.addelem(3)
>>> B.addelem(2)
>>> B.addelem(3)
>>> B.addelem(4)
>>> A.union(B)

[1, 2, 3, 4]

구성하는 도중, 이중연결을 잘 구성하지 못해 약간의 오류가 있었지만 각 과정에서 출력을 함으로써 어느 부분이 잘못되었는지 확인할 수 있었다!! 혹시 구현이 잘 안된다면 과정을 출력해보자.