#ifndef LINKEDSET_H
#define LINKEDSET_H
template <class T>
struct SetNode {								//集合的結(jié)點(diǎn)類定義
	T data;										//每個(gè)成員的數(shù)據(jù)
	SetNode<T> *link;							//鏈接指針
	SetNode() : link(NULL){};					//構(gòu)造函數(shù)
	SetNode(const T& x, SetNode<T> *next = NULL) 
		: data(x), link(next){};			//構(gòu)造函數(shù)
};

template <class T>
class LinkedSet {								//集合的類定義
private:
	SetNode<T> *first, *last;					//有序鏈表表頭指針, 表尾指針
public:
	LinkedSet() {first = last = new SetNode<T>;}	//構(gòu)造函數(shù)
	LinkedSet(LinkedSet<T>& R);						//構(gòu)造函數(shù) 
	~LinkedSet() {makeEmpty();  delete first;}		//析構(gòu)函數(shù)
	void makeEmpty();								//置空集合
	bool addMember(const T& x);						//把新元素x加入到集合中
	bool delMember(const T& x);						//把集合中成員x刪去
	LinkedSet<T> operator + (LinkedSet<T>& R);		//求集合this與R的并
	LinkedSet<T> operator * (LinkedSet<T>& R);		//求集合this與R的交
	LinkedSet<T> operator - (LinkedSet<T>& R);		//求集合this與R的差
	bool Contains(const T x);						//判x是否集合的成員
	bool operator == (LinkedSet<T>& R);			//判集合this與R相等
	void show();  //輸出
};

template <class T>
LinkedSet<T>::LinkedSet(LinkedSet<T>& R) {			//復(fù)制構(gòu)造函數(shù)
	SetNode<T> *srcptr = R.first->link;			//源鏈表指針
	first = last = new SetNode<T>;					//創(chuàng)建附加頭結(jié)點(diǎn)
	while (srcptr != NULL) {						//逐個(gè)結(jié)點(diǎn)復(fù)制
		last->link = new SetNode<T>(srcptr->data);
		last = last->link;
		srcptr = srcptr->link;
	}
	last->link = NULL;
};
template <class T>
bool LinkedSet<T>::Contains(const T x) {
	//測(cè)試函數(shù): 如果x是集合的成員, 則函數(shù)返回true, 否則返回false。
	SetNode<T> *temp = first->link;						//鏈的掃描指針
	while (temp != NULL && temp->data < x) 				//循鏈搜索
		temp = temp->link;	
	if (temp != NULL && temp->data == x) return true;	//找到
	else return false;									//未找到
};

template <class T>
bool LinkedSet<T>::addMember(const T& x) {
	//把新元素x加入到集合之中。若集合中已有此元素, 則函數(shù)返回false, 否則函數(shù)返回true。
	SetNode<T> *p = first->link, *pre = first;	//p是掃描指針, pre是p的前驅(qū)
	while (p != NULL && p->data < x) 				//循鏈掃描
	{pre = p;  p = p->link;}		
	if (p != NULL && p->data == x) return false;	//集合中已有此元素
	SetNode<T> *s = new SetNode<T>(x);					//創(chuàng)建值為x的結(jié)點(diǎn)
	s->link = p;  pre->link = s;					//鏈入
	if (p == NULL) last = s;						//鏈到鏈尾時(shí)改鏈尾指針
	return true;
};

template <class T>
bool LinkedSet<T>::delMember(const T& x) {
	//把集合中成員x刪去。若集合不空且元素x在集合中, 則函數(shù)返回ture, 否則返回false。
	SetNode<T> *p = first->link,  *pre = first;
	while (p != NULL && p->data < x) 				//循鏈掃描
	{pre = p;  p = p->link;}		
	if (p != NULL && p->data == x) {				//找到,可以刪除結(jié)點(diǎn)p
		pre->link = p->link;						//重新鏈接,摘下p
		if (p == last) last = pre;					//刪去鏈尾時(shí)改鏈尾指針
		delete p;  return true;						//刪除含x結(jié)點(diǎn)
	}
	else return false;								//集合中無此元素
};

template <class T>
void LinkedSet<T>::makeEmpty()
{
	SetNode<T> *q;
	while (first->link != NULL) {
		q = first->link;              //保存被刪結(jié)點(diǎn)
		first->link = q->link;    //從鏈上摘下該結(jié)點(diǎn)
		delete q;		        //刪除
	}
};

template <class T>
void LinkedSet<T>::show()
{
	if(first->link != NULL)
	{
		cout<<"集合元素：";
		SetNode<T> *q = first->link;
		while (q != NULL) {
			cout<<q->data<<' ';
			q = q->link;              //保存被刪結(jié)點(diǎn)
		}
		cout<<endl;
	}
	else cout<<"空集合"<<endl;
};

template <class T>
LinkedSet<T> LinkedSet<T>::operator + (LinkedSet<T>& R) {
	//求集合this與集合R的并, 計(jì)算結(jié)果通過臨時(shí)集合temp返回，this集合與R集合不變。
	SetNode<T> *pb = R.first->link;					//R集合的鏈掃描指針
	SetNode<T> *pa = first->link;					//this集合的鏈掃描指針
	LinkedSet<T> temp;								//創(chuàng)建空結(jié)果鏈表
	SetNode<T> *p, *pc = temp.first;				//結(jié)果鏈的存放指針
	while (pa != NULL && pb != NULL) {				//兩鏈數(shù)據(jù)兩兩比較
		if (pa->data == pb->data) {					//兩集合共有元素
			pc->link = new SetNode<T>(pa->data);
			pa = pa->link;  pb = pb->link;
		}
		else if (pa->data < pb->data) {				//this中元素值小
			pc->link = new SetNode<T>(pa->data);
			pa = pa->link;
		} else {									//R集合中元素值小
			pc->link = new SetNode<T>(pb->data);
			pb = pb->link;
		}
		pc = pc->link;
	}
	if ( pa != NULL ) p = pa;						//this集合未掃完
	else p = pb;									//或R集合未掃完
	while (p != NULL) {								//向結(jié)果鏈逐個(gè)復(fù)制
		pc->link = new SetNode<T>(p->data);
		pc = pc->link;  p = p->link;
	}
	pc->link = NULL;  temp.last = pc;				//鏈表收尾
	return temp;
};

template <class T>
LinkedSet<T> LinkedSet<T>::operator * (LinkedSet<T>& R) {
	//求集合this與集合R的交, 計(jì)算結(jié)果通過臨時(shí)集合temp返回，this集合與R集合不變。
	SetNode<T> *pb = R.first->link;					//R集合的鏈掃描指針
	SetNode<T> *pa = first->link;					//this集合的鏈掃描指針
	LinkedSet<T> temp;
	SetNode<T> *pc = temp.first;					//結(jié)果鏈的存放指針
	while (pa != NULL && pb != NULL) {				//兩鏈數(shù)據(jù)兩兩比較
		if (pa->data == pb->data) {					//兩集合公有的元素
			pc->link = new SetNode<T>(pa->data);	//鏈入結(jié)果鏈表尾部
			pc = pc->link;
			pa = pa->link;  pb = pb->link;
		}
		else if (pa->data < pb->data) pa = pa->link;	//this集合元素值小
		else pb = pb->link;					//R集合中元素值小
	}
	pc->link = NULL;  temp.last = pc; 				//置鏈尾指針
	return temp;								
};

template <class T>
LinkedSet<T> LinkedSet<T>::operator - (LinkedSet<T>& R) {
	//求集合this與集合R的差, 計(jì)算結(jié)果通過臨時(shí)集合temp返回，this集合與R集合不變。
	SetNode<T> *pb = R.first->link;					//R集合鏈掃描指針
	SetNode<T> *pa = first->link;					//this集合鏈掃描指針
	LinkedSet<T> temp;
	SetNode<T> *pc = temp.first;					//結(jié)果鏈的存放指針
	while (pa != NULL && pb != NULL) {				//兩兩比較
		if (pa->data == pb->data)					//兩集合共有的元素
		{pa = pa->link;  pb = pb->link;}
		else if (pa->data < pb->data) {				//this集合值小, 保留
			pc->link = new SetNode<T>(pa->data);
			pc = pc->link;  pa = pa->link;
		}
		else pb = pb->link;							//不要,向前繼續(xù)檢測(cè)
	}
	while (pa != NULL) {							//向結(jié)果鏈逐個(gè)復(fù)制
		pc->link = new SetNode<T>(pa->data);
		pc = pc->link;  pa = pa->link;
	}
	pc->link = NULL;  temp.last = pc;				//鏈表收尾
	return temp;
}; 

template <class T>
bool LinkedSet<T>::operator == (LinkedSet<T>& R) {
	//當(dāng)且僅當(dāng)集合this與集合R相等時(shí), 函數(shù)返回true, 否則返回false。
	SetNode<T> *pb = R.first->link;					//R集合的鏈掃描指針
	SetNode<T> *pa = first->link;					//this集合的鏈掃描指針
	while (pa != NULL && pb != NULL)
		if (pa->data == pb->data)					//相等, 繼續(xù)檢測(cè)
		{pa = pa->link;  pb = pb->link;}
		else return false;							//掃描途中不等時(shí)退出
		if (pa != NULL || pb != NULL) return false;	//鏈不等長(zhǎng)時(shí),返回0
		return true;
};


#endif;