数据结构-用单链表实现集合的并运算和交运算

【问题描述】

有A，B两个集合，分别用两个单链表存放，假设集合中无重复的元素，要求编写两个独立的函数分别实现集合的并运算和交运算，运算结果存放在第3个链表中（运算不能改变原来的A, B链表），假设单链表中的元素值均为正整数，建立链表时，输入-1时停止创建新结点，可以采用前插或后插的形式建立链表。注意，输出函数和main函数在HINT中给出，并运算和交运算的函数原型如下：

void Union(List<T> LA, List<T>LB, List<T>&LC)       //集合并运算

void Intersection(List<T> LA, List<T>LB, List<T>&LC)   //集合交运算

【输入形式】第一行输入集合A的元素，即若干个正整数（无重复数据），各个整数之间用空格分开，最后输入-1；第二行输入集合B的元素。

【输出形式】第一行输出两个集合并运算的结果，第二行输出两个集合交运算的结果。

【样例输入】

1 3 5 7-1

2 3 4 6 -1

【样例输出】

{ 1 3 5 7 2 4 6 }

{ 3 }

//Drink
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
	T data;				//数据域 
	LinkNode<T> *link;	//指针域 
	LinkNode(LinkNode<T> *ptr=NULL)
	{
		link = ptr;		//仅初始化指针成员的构造函数	
	}
	LinkNode(const T &item,LinkNode<T> *ptr=NULL)
	{
		link = ptr;		//初始化指针成员和数据的构造函数 
		data = item;
	}
}; 
template<class T>
class List
{
	protected: LinkNode<T> *first;			
	
	public: 
		List(){first = new LinkNode<T>;};	//构造函数创建空的单链表，并创建first 
		void inputRear(T endTag);			//endTag为结束标志 
		void output();                      //输出链表
		bool findX(T x);                    //在链表中找到x
		void insert(T &x);                  //在链表尾部插入数值为x的结点
		LinkNode<T>* getfirst()             //从类外获取头指针,（返回值需要加*）
		{	
			return first;
		};
};
template<class T>
void List<T>::inputRear(T endTag)//输入链表中的值
{	
	
	LinkNode<T> *newNode;
	LinkNode<T> *last;
	T val;
	cin>>val;
	last = first;	
	while(val != endTag)
	{
	
		newNode = new LinkNode<T>(val); 
		
	
		last->link = newNode;	//将新结点连接到表尾 

		last = newNode;			//新链表表尾变为地址变为newNode
		cin>>val;				//输入下一个结点得值 
	
	}
	last->link=NULL; 
}
template<class T>
bool List<T>::findX(T x)        //在链表中找到x
{
	LinkNode<T>* current=first->link;
	while(current!=NULL)
	{
		if(current->data==x)
		return 1;	
		current=current->link;
	}	
	return 0;
} 

template<class T>
void List<T>::insert(T &x)      //在链表最后插入一个结点 
{
	LinkNode<T> *newNode,*last;
	newNode = new LinkNode<T> (x);
	last = first;
	
	while(last->link!=NULL)     //通过循环将last指针指到表尾
	last=last->link;
	
	last->link=newNode;
	last=newNode;
}
//----------------------------------------------------------
template<class T>
void Union(List<T> LA, List<T> LB, List<T> &LC)//求并集
{
	LinkNode<T> *a,*b;
	a=LA.getfirst();
	b=LB.getfirst();
	a=a->link;
	b=b->link;
	while(a!=NULL)
	{
		LC.insert(a->data);			//先将链表acopy到c中 
		a=a->link;
	}
	while(b!=NULL)					
	{			
		if(!LC.findX(b->data))		//再在链表c中找b的值如果找不到则将该值插入c中 
		{
			LC.insert(b->data);
		}
		b=b->link;
	}
}
//---------------------------------------------------------------
template<class T> 
void Intersection(List<T> LA, List<T>LB, List<T>&LC)//求交集
{
	LinkNode<T> *a = LA.getfirst();
	a=a->link;
	while(a!=NULL)
	{
	
		if(LB.findX(a->data))//在b中找链表a的值若找到了则放入c中c最后为ab的交集 
		{
	 		LC.insert(a->data); 
		}	
		a=a->link;	
	}	
}
template <class T>  
void List<T>::output()       // 以集合形式输出数据
{
       LinkNode<T> *p=first->link;
        cout<<"{ ";
        while(p!=NULL)
        {     cout<<p->data<<" ";

               p=p->link;   

         }
       cout<<"}"<<endl;
}

int main()
{
       List<int> A,B,C,D;
       A.inputRear(-1);
	   B.inputRear(-1);
       Union(A,B,C);         //集合并运算
       C.output();
       Intersection(A,B,D);  //集合交运算
       D.output();
	
return 0;
}