// jihe.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"

typedef struct node
{
	int data;
	struct node *next;
}PNode;

PNode *creat_jihe(int n);
void print_jihe(PNode *h);
PNode *jiaoji(PNode *pa,PNode *pb);
PNode *bingji(PNode *pa,PNode *pb);
PNode * JueDuiBu(PNode *a,PNode *e);



int main(int argc, char* argv[])
{
	PNode *Ha,*Hb,*Hc;
	int la,lb,lc;
	cout <<"請輸入集合A的個數:";
	cin >> la;	
	cout <<"創建集合A:"<<endl;
	Ha=creat_jihe(la);//建鏈表集合一
	cout <<"集合 A={";
	print_jihe(Ha);
	cout <<"}";
	cout <<endl<<endl;

	cout <<"請輸入集合B的個數:";
	cin >> lb;
    cout <<"創建集合B:"<<endl;
	Hb=creat_jihe(lb);//建鏈表集合二
	cout <<"集合 B={";
	print_jihe(Hb);
	cout <<"}";
	cout <<endl<<endl;

	cout <<"請輸入全集E的個數:";
	cin >> lc;
    cout <<"創建全集E:"<<endl;
	Hc=creat_jihe(lc);//建鏈表集合E
	cout <<"全集 E={";
	print_jihe(Hc);
	cout <<"}";
	cout <<endl<<endl;

	PNode *s=jiaoji(Ha,Hb);//交集
	cout <<"集合A與集合B的交集={";
	print_jihe(s);
	cout <<"}";
	cout <<endl;

    PNode *b=bingji(Ha,Hb);//并集
	cout <<"集合A與集合B的并集={";
	print_jihe(b);
	cout <<"}";
	cout <<endl;
    
	PNode *e=JueDuiBu(Ha,Hc);//絕對補集
	cout <<"集合A的絕對補集={";
	print_jihe( e);
	cout <<"}";
	cout <<endl;

    PNode *j3=Ha;//相對補集
	PNode *j4=s;
	PNode *e1=JueDuiBu(j4->next  ,j3->next );
	cout <<"集合A與集合B的相對補集={";
	print_jihe( e1);
	cout <<"}";
	cout <<endl;

    PNode *j5=s;//對稱差
	PNode *j6=b;
	PNode *e2=JueDuiBu(j5->next ,j6->next );
	cout <<"集合A與集合B的對稱差={";
	print_jihe( e2);
	cout <<"}";
	cout <<endl;

	
	return 0;
}

PNode *creat_jihe(int n)
{//創造鏈表	
	PNode *head=new PNode;
	head->next=NULL;
	PNode *p=head;
	printf("請輸入數據:\n");
	for(int i=1;i<=n;i++)
	{
		PNode *s=new PNode;
		cin >> s->data;
		s->next=NULL;
		p->next=s;
		p=s;
	}
	return(head);
}

void print_jihe(PNode *h)
{//打印輸出
	PNode *p=h->next;
	while(p)
	{
		cout <<p->data<<" ";
		p=p->next;
	}	
}

PNode *jiaoji(PNode *pa,PNode *pb)
{//集合的交集運算
	
	PNode *qa=pa->next;
	PNode *qb=pb->next;
	PNode *head=new PNode;
	head->next=NULL;
	PNode *p=head;	
	while(qa)
	{
		qb=pb->next;
		while(qb)
		{
			if(qa->data  == qb->data)
			{
				PNode *q=new PNode;
			    q->data=qa->data;
			    q->next=NULL;
			    p->next =q;
			    p=q;				
			}
			qb=qb->next;
		}
		qa=qa->next ;
	}		
		
	return head;
}

PNode *bingji(PNode *pa,PNode *pb)
{//集合的并集運算
	
	PNode *qa,*qb,*head,*p,*s;
	head=new PNode;
	head->next=NULL;
	p=head;
	qa=pa->next ;
	while(qa)
	{
		PNode *q=new PNode;
	    q->data=qa->data;
		q->next=NULL;
	    p->next =q;
		p=q;		
		qa=qa->next;
	}
    qb=pb->next;
	while(qb)
	{
		PNode *w=new PNode;
	    w->data=qb->data;
		w->next=NULL;
	    p->next =w;
		p=w;
		qb=qb->next;
	}
	s=head->next ;
	while(s)
	{
		PNode *r=s->next;
		while(r)
		{
			if(s->data ==r->data)
			{
				PNode *t=head;
				while(t->next !=r)
					t=t->next;
				
				PNode *x=t->next ; 
				t->next =x->next;
				delete x;
				r=t;
			}
			r=r->next;			
		}
		s=s->next;
	}
	return head;
}

PNode * JueDuiBu(PNode *a,PNode *e)
{//集合的絕對補運算
	
	PNode *qa=a->next;
	PNode *head=new PNode;
	head->next=NULL;
    head=e;
    PNode *s=head->next ;
	

	if(qa==NULL)
	{
		cout <<"集合A的絕對補={";  
	    
	while(s)
		{
		    cout <<s->data ;
			s=s->next ;
	}
	cout <<"}";
	cout <<endl;
	}
		else 
		{
	while(qa)
	{
		PNode *r=s;
		while(r)
		{
			if(r->data ==qa->data)
			{
				PNode *t=s;				
				while(t->next !=r)
					t=t->next;
                PNode *x=t->next ; 
				t->next =x->next;
				delete x;
				r=t;				
			}
			r=r->next;			
		}
		qa=qa->next;
	}
	
  return head;	
}
}		

/*
PNode * JueDui(PNode *a,PNode *e)
{//集合的絕對補運算
	
	PNode *qa=a->next;
	PNode *h=new PNode;
	h->next=NULL;
    h=e;
    PNode *s=h->next ;
	if(s==NULL)
	{
		cout <<"集合A與集合B的相對補集={";  
	    
	while(s)
		{
			cout <<s->data ;
			s=s->next ;
	}
	cout <<"}";
	cout <<endl;
	}
		else 
		{
	while(qa)
	{
		PNode *r=s;
		while(r)
		{
			if(r->data ==qa->data)
			{
				PNode *t=s;				
				while(t->next !=r)
					t=t->next;
                PNode *x=t->next ; 
				t->next =x->next;
				delete x;
				r=t;				
			}
			r=r->next;			
		}
		qa=qa->next;
	}
	return h;
	
}
}	
*/