欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序表实现集合的并集、交集、差集

程序员文章站 2022-07-13 09:07:13
...

题目内容

基本要求:

实现顺序表的各种基本运算的算法,求集合的并集、交集、差集:

测试案例:

线性表A的元素为:1 2 3 4
线性表B的元素为:2 3 5 6 7
A∪B为:1 2 3 4 5 6 7
A∩B为:2 3
A-B为:1 4
B-A为:5 6 7

算法描述

A:A的特有元素+AB共有元素;
B:B的特有元素+AB共有元素;
A∪B:将A、B的所有元素合到一起构成的集合C,相同的数字只取一次;
A∩B:将A、B的共有元素放入集合C中;
A-B:将A集合中特有的元素放入集合C中;
B-A:将B集合中特有的元素放入集合C中;

其中难点为:特有元素、共有元素的获取:
使用LocateElem函数(即查找函数): 在L1中寻找L2中的元素L2->data[i],也就是找共有元素,如果找到了,就返回i-1,没找到就返回0。

if(!(LocateElem(L1,L2->data[i])))
	ListInsert(L3,L3->length+1,L2->data[i]);
if语句中加了‘!’,即此时找的为L2的特有元素,再把这个L2特有元素添加到L3中,则L3为并集

代码部分

定义结构

#define MAX 20
typedef char ElemType;
typedef struct
{
	ElemType data [MAX];
	int length;
}SqList;

顺序表的10个功能构建

//1.建立顺序表
void CreateList(SqList *&L,ElemType a[],int n)
{
	for(int i=0;i<n;++i)
		L->data[i]=a[i];
	L->length=n;
}

//2.初始化顺序表
void InitList(SqList *&L)
{
	L=new SqList;
	L->length=0;
 } 

//3.销毁一个顺序表 
void DestroyList(SqList *L)
{
	delete L;
}

//4.判断是否为空表
bool ListEmpty(SqList *L)
{
	return(0==L->length);
}

//5.求顺序表的长度
int ListLength(SqList *L)
{
	return(L->length);
}

//6.求一个数据的元素值 
bool GetElem(SqList *&L,int i,ElemType &e)
{
	if(i<1||i>L->length)
		return false;
	else
	{
		e=L->data[i-1];
		return true;
	}
}

//7.输出顺序表
void DispList(SqList *L)
{
	if(ListEmpty(L))
		return;
	for(int i=0;i<L->length;++i)
		cout<<L->data[i]<<"\t";
	cout<<endl;
}

//8.插入数据元素 
bool ListInsert(SqList *&L,int i,ElemType e)
{
	if(i<0||i>L->length+1)
		return false;
		i--;
	for(int k=L->length;k>i;--k)
		L->data[k]=L->data[k-1];
	L->data[i]=e;
	L->length++;
	return true; 
}

//9.删除数据元素
bool ListDelete(SqList *&L,int i,ElemType &e)
{
	if(i<1||i>L->length)
		return false;
	i--;
	e=L->data[i];
	for(;i<L->length;++i)
		L->data[i]=L->data[i+1];
	L->length--;
	return true;
}

//10.按元素值查找
int LocateElem(SqList *L,ElemType e)
{
	int i=0;
	while(i<L->length&&L->data[i]!=e)
		i++;
	if(i>=L->length) 
		return 0;
	else
		return i+1;
}

集合的并集、交集、差集*

//11.A∪B的求解
void BinList(SqList *L1,SqList *L2,SqList *&L3)
{
	L3->length=0;		//初始化C表 
	CreateList(L3,L1->data,L1->length);
	for(int i=0;i<L2->length;++i)	
		if(!(LocateElem(L1,L2->data[i])))
			ListInsert(L3,L3->length+1,L2->data[i]);
} 

//12.A∩B的求解
void JiaoList(SqList *L1,SqList *L2,SqList *&L3)
{
	L3->length=0;		//初始化C表
	for(int i=0;i<L1->length;++i)
		if((LocateElem(L2,L1->data[i])))
			ListInsert(L3,L3->length+1,L1->data[i]);
}  

//13.A-B的求解
void A_BJianList(SqList *L1,SqList *L2,SqList *&L3)
{
	L3->length=0;		//初始化C表
	for(int i=0;i<L1->length;++i)
		if(!(LocateElem(L2,L1->data[i])))
			ListInsert(L3,L3->length+1,L1->data[i]);
} 

//14.B-A的求解
void B_AJianList(SqList *L1,SqList *L2,SqList *&L3)
{
	L3->length=0;		//初始化C表
	for(int i=0;i<L2->length;++i)
		if(!(LocateElem(L1,L2->data[i])))
			ListInsert(L3,L3->length+1,L2->data[i]);
} 

主函数部分

int main()
{
	ElemType a[]={'1','2','3','4'};
	SqList *L_A; 
	InitList(L_A);
	CreateList(L_A,a,4);
	cout<<"A集合的元素为:"; DispList(L_A); 
	ElemType b[]={'2','3','5','6','7'};
	SqList *L_B; 
	InitList(L_B);
	CreateList(L_B,b,5);
	cout<<"\nB集合的元素为:"; DispList(L_B);
	SqList *L_C; 
	InitList(L_C);
	BinList(L_A,L_B,L_C);
	cout<<"\nA∪B集合的元素为:"; DispList(L_C);
	JiaoList(L_A,L_B,L_C);
	cout<<"\nA∩B集合的元素为:"; DispList(L_C);
	A_BJianList(L_A,L_B,L_C);
	cout<<"\nA-B集合的元素为:"; DispList(L_C);
	B_AJianList(L_A,L_B,L_C);
	cout<<"\nB-A集合的元素为:"; DispList(L_C);
	DestroyList(L_A);		//释放ABC表 
	DestroyList(L_B);
	DestroyList(L_C); 
}

运行结果

顺序表实现集合的并集、交集、差集

可改进部分

1. 上面的A-B与B-A可以用一个函数解决,但是在这里就不再做合并的展示;
2. 上述主函数对A、B集合的元素提前定义好了,可以再增加一个输入元素的函数;
3. 欢迎各位大佬提出问题。
相关标签: 顺序表