123.cpp

使用顺序表实现的交集并集问题

#include<iostream.h>
const int Max_length=100; //设最大长度为100;
template<class ELEM>
class List    //顺序表类模板List，模板参数ELEM
{
public:
	List(int Msize=Max_length);	//constructor算子,创建一个空的线性表
	virtual ~List(); //destructor算子, 从计算机存储空间删除线性表
	int length(); //求线性表的长度
	void insert(int pos, ELEM item); //插入算子,在表的第i个位置插入元素item
	void viewlist(); //遍历线性表
	int locate(ELEM aim);
	ELEM remove(int i); //删除算子，删除表中第i个元素
	void append(ELEM item);
	ELEM fetch(int pos);
                  void viewList();

private:
	int msize;   //顺序表实例的最大长度
	int curr_len;   //顺序表实例的当前长
	ELEM *nodelist;  //存储顺序表实例的一维数组

};
template<class ELEM>
List<ELEM>::List(int Msize) //构造函数
{
	msize=Msize; //数据最大长度为Msize-1
	nodelist=new ELEM[msize];  //申请内存空间, 存放顺序表实例的元素
	curr_len=0;//当前顺序表长度为0
}

template<class ELEM> 
List<ELEM>::~List() //析构函数
{
	delete []nodelist; //释放顺序表占用的空间
}

template<class ELEM>
int List<ELEM>::length()//求顺序表的长度
{
	return curr_len;// 返回线性表中包含的元素个数
}

template<class ELEM>
void List<ELEM>::insert(int pos,ELEM item) //插入元素
{
	//if((curr_len>=msize)||(pos<0)||(pos>curr_len-1)) cout << "错误"; 
	for(int i=curr_len; i>=pos; i--) nodelist[i] = nodelist[i-1];//从表尾curr_len-1起往右移动元素直到pos
	nodelist[pos-1] = item; //将新元素插入到pos-1处
	curr_len++;  //顺序表的长度加1
}

template <class ELEM>
void List<ELEM>::append(ELEM item)  //在线性表的尾部追加一个元素item
{
    int i=curr_len;
	nodelist[i] = item;//将元素item插入到顺序表的尾部
	curr_len++;//顺序表的长度加1
}

template<class ELEM>
ELEM List<ELEM>::fetch(int pos) //取表中pos位置的元素值
{
	ELEM temp = nodelist[pos-1];
	return temp;
}

template<class ELEM>
ELEM List<ELEM>::remove(int pos) //删除元素
{
	//if((length())||(pos>=0)||(pos<=curr_len-1));//表不能为空;  pos的值必须大于或等于零并且小于curr_len-1
	ELEM temp = nodelist[pos-1]; //将被删除元素保存到temp中
	for(int i=pos-1; i<curr_len; i++) nodelist[i] = nodelist[i+1]; // 从pos-1开始, 右边的元素依次向左移动一位
	curr_len--; //顺序表的长度减1
	return temp; //被删除元素返回给调用函数
}

template<class ELEM>
int List<ELEM>::locate(ELEM aim) //取表中pos位置的元素值
{
	if(length()==0)
	{
		cout << "空表" << endl;
		return 0;
	}
	for(int i=0;i<curr_len;i++)
		if(nodelist[i]==aim) return(i+1);
	return 0;
}

template<class ELEM>
void List<ELEM>::viewList()//输出顺序表
{
	if(length()==0)
	{
		cout << "空表" << endl;
		return;
	}
	cout <<"顺序表中的元素为: ";
	for(int i=0;i<curr_len;i++) cout << nodelist[i] << "  ";//依次输出顺序表中元素的值
}
void Union(List<int> &A, List<int> &B , List<int> &C);
void Intersection(List<int> &A, List<int> &B ,List<int> &D);

void main()
{
	int MaxSize = 50,temp,n;
	List<int> A(MaxSize),B(MaxSize),C(MaxSize),D(MaxSize);
	cout << "请输入集合A元素个数:" << endl;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cout<<"请输入集合A元素:"<<endl;
		cin >> temp;
		A.append(temp);
	}
	cout<<"A";
	A.viewList();
    cout<<endl;
	cout << "请输入集合B元素个数:" << endl;
	cin >> n;
	for(i = 0; i < n; i++)
	{
		cout<<"请输入集合A元素:"<<endl;
		cin >> temp;
		B.append(temp);
	}
    cout<<"B";
	B.viewList();
	cout<<endl;
	Union(A,B,C);
	cout << "A∪B ";
	C.viewList();
	Intersection(A,B,D);
	cout << "A∩B ";
	D.viewList();
}

void Union(List<int> &A, List<int> &B , List<int> &C)
{
	int n = A.length();
	int m = B.length();
	for (int i = 1; i <= n; i++ )
	{
		int x = A.fetch(i);  //将A中元素, 全部复制到D中
		C.append(x);
	}

	for(i = 1; i <= m; i++)
	{
		int x = B.fetch(i);  //从A中取一元素x
		int k = A.locate(x);  //查找B中是否存在x
		if( k == 0) C.append (x);  //若找到插入到C中
	}
}

void Intersection(List<int> &A, List<int> &B ,List<int> &D)
{
	int n = A.length ();
	int m = B.length ();
	for (int i = 1; i <= n; i++ )
	{
		int x = A.fetch(i);  //将A中元素, 全部复制到D中
		D.append(x);
	}
	for (i = 1; i <= n; i++)
	{
		int x = A.fetch(i);
		int k = B.locate(x);     //查找B中是否存在x
		if ( k == 0 ) D.remove(D.locate(x));     //若未找到插入到D中
	}
}