linkedset.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef LINKEDSET_H
#define LINKEDSET_H
template <class T>
struct SetNode {								//集合的结点类定义
	T data;										//每个成员的数据
	SetNode<T> *link;							//链接指针
	SetNode() : link(NULL){};					//构造函数
	SetNode(const T& x, SetNode<T> *next = NULL) 
		: data(x), link(next){};			//构造函数
};

template <class T>
class LinkedSet {								//集合的类定义
private:
	SetNode<T> *first, *last;					//有序链表表头指针, 表尾指针
public:
	LinkedSet() {first = last = new SetNode<T>;}	//构造函数
	LinkedSet(LinkedSet<T>& R);						//构造函数 
	~LinkedSet() {makeEmpty();  delete first;}		//析构函数
	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) {			//复制构造函数
	SetNode<T> *srcptr = R.first->link;			//源链表指针
	first = last = new SetNode<T>;					//创建附加头结点
	while (srcptr != NULL) {						//逐个结点复制
		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) {
	//测试函数: 如果x是集合的成员, 则函数返回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加入到集合之中。若集合中已有此元素, 则函数返回false, 否则函数返回true。
	SetNode<T> *p = first->link, *pre = first;	//p是扫描指针, pre是p的前驱
	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);					//创建值为x的结点
	s->link = p;  pre->link = s;					//链入
	if (p == NULL) last = s;						//链到链尾时改链尾指针
	return true;
};

template <class T>
bool LinkedSet<T>::delMember(const T& x) {
	//把集合中成员x删去。若集合不空且元素x在集合中, 则函数返回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) {				//找到,可以删除结点p
		pre->link = p->link;						//重新链接,摘下p
		if (p == last) last = pre;					//删去链尾时改链尾指针
		delete p;  return true;						//删除含x结点
	}
	else return false;								//集合中无此元素
};

template <class T>
void LinkedSet<T>::makeEmpty()
{
	SetNode<T> *q;
	while (first->link != NULL) {
		q = first->link;              //保存被删结点
		first->link = q->link;    //从链上摘下该结点
		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;              //保存被删结点
		}
		cout<<endl;
	}
	else cout<<"空集合"<<endl;
};

template <class T>
LinkedSet<T> LinkedSet<T>::operator + (LinkedSet<T>& R) {
	//求集合this与集合R的并, 计算结果通过临时集合temp返回，this集合与R集合不变。
	SetNode<T> *pb = R.first->link;					//R集合的链扫描指针
	SetNode<T> *pa = first->link;					//this集合的链扫描指针
	LinkedSet<T> temp;								//创建空结果链表
	SetNode<T> *p, *pc = temp.first;				//结果链的存放指针
	while (pa != NULL && pb != NULL) {				//两链数据两两比较
		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) {								//向结果链逐个复制
		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的交, 计算结果通过临时集合temp返回，this集合与R集合不变。
	SetNode<T> *pb = R.first->link;					//R集合的链扫描指针
	SetNode<T> *pa = first->link;					//this集合的链扫描指针
	LinkedSet<T> temp;
	SetNode<T> *pc = temp.first;					//结果链的存放指针
	while (pa != NULL && pb != NULL) {				//两链数据两两比较
		if (pa->data == pb->data) {					//两集合公有的元素
			pc->link = new SetNode<T>(pa->data);	//链入结果链表尾部
			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的差, 计算结果通过临时集合temp返回，this集合与R集合不变。
	SetNode<T> *pb = R.first->link;					//R集合链扫描指针
	SetNode<T> *pa = first->link;					//this集合链扫描指针
	LinkedSet<T> temp;
	SetNode<T> *pc = temp.first;					//结果链的存放指针
	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;							//不要,向前继续检测
	}
	while (pa != NULL) {							//向结果链逐个复制
		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) {
	//当且仅当集合this与集合R相等时, 函数返回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)					//相等, 继续检测
		{pa = pa->link;  pb = pb->link;}
		else return false;							//扫描途中不等时退出
		if (pa != NULL || pb != NULL) return false;	//链不等长时,返回0
		return true;
};


#endif;