Problem A: 求集合的交并补集
Time Limit: 1 Sec Memory Limit: 4 MB
Description
任意给定两个包含1-30000个元素的集合A,B（集合中元素类型为任意整型数，且严格递增排列），求A交B、A并B、A-B和B-A集合。
Input
输入第一行为测试数据组数。每组测试数据两行，分别为集合A、B。每行第一个数n（1<=n<=30000）为元素数量，后面有n个严格递增的绝对值小于2^31代表集合中包含的数。
Output
对每组测试数据输出5行，第1行为数据组数，后4行分别为按升序输出两个集合的A交B、A并B、A-B和B-A集合。格式见样例。
Sample Input
1
3 1 2 5
4 2 3 5 8
Sample Output
Case #1:
2 5
1 2 3 5 8
1
3 8
HINT
考察知识点：有序表合并，时间复杂度O(n)，空间复杂度O(n)
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 60000
using namespace std;
typedef int ElemType; //定义元素类型
typedef int status; //定义返回类型
typedef struct{
ElemType *elem; // 顺序表基地址
int length;
}SqList;
///初始化
int InitListSq(SqList &L)
{
L.elem=new ElemType[MAX_SIZE];
if(!L.elem)
exit(-2);
L.length=0;
return 0;
}
///创建
int Create_SqList(SqList &L,int n)
{
//InitListSq(L);///加一句试试 // 没用
int i;
if(n>=MAX_SIZE)
return 0;
for(i=0;i<n;i++)
{
scanf("%d",&(L.elem[i]));/// ///////////////////////
}
L.length=n;
///进行一次排序，变为递增数列
// int j,k,m,g=0;
// m=L.length;
// for(j=1;j<L.length;j++)
// {
// m-=1;
// for(k=0;k<m;k++)
// {
// if(L.elem[k]>L.elem[k+1])
// {
// g=L.elem[k];
// L.elem[k]=L.elem[k+1];
// L.elem[k+1]=g;
// }
// }
// }
return 0;
}
///clear
void Delete_Sqlist(SqList &C)
{
delete[] C.elem;
C.length=0;
// 不加可能会内存超限 Memory Error
}
///交集
void Jiao_Sqlist(SqList &A,SqList &B)
{
int flag=0;
int i=0;
int j=0;
while(i<A.length&&j<B.length)
{
if(*(A.elem+i)<*(B.elem+j))
{
i++;
}
else if(*(A.elem+i)>*(B.elem+j))
{
j++;
}
else
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag=1;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
j++;
}
}
printf("\n");
}
///并集
void Bing_SqList(SqList &A,SqList &B)
{
int flag=0;
int i=0;
int j=0;
while(i<A.length&&j<B.length)
{
if(*(A.elem+i)<*(B.elem+j))
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag=1;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
}
else if(*(A.elem+i)>*(B.elem+j))
{
if(flag==0)
{
printf("%d",*(B.elem+j));
flag++;
}
else
{
printf(" %d",*(B.elem+j));
}
j++;
}
else
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag++;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
j++;
}
}
//i++;
if(i<A.length)
{
while(i<A.length)
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag=1;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
}
}
if(j<B.length )
{
while(j<B.length)
{
if(flag==0)
{
printf("%d",*(B.elem+j));
flag++;
}
else
{
printf(" %d",*(B.elem+j));
}
j++;
}
}
printf("\n");
}
/// 补集A_B
void A_B_SqList(SqList &A,SqList &B)
{
int flag=0;
int i=0;
int j=0;
while(i<A.length&&j<B.length)
{
if(*(A.elem+i)<*(B.elem+j))
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag=1;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
}
else if(*(A.elem+i)>*(B.elem+j))
{
j++;
}
else
{
i++;
j++;
}
}
//if(j==B.length-1 && i<A.length)
if(i<A.length)/// if(j==B.length-1 && i<A.length)
{
while(i<A.length)
{
if(flag==0)
{
printf("%d",*(A.elem+i));
flag=1;
}
else
{
printf(" %d",*(A.elem+i));
}
i++;
}
}
printf("\n");
}
///补集B_A
void B_A_SqList(SqList &A,SqList &B)
{
int flag=0;
int i=0;
int j=0;
while(i<A.length&&j<B.length)
{
if(*(A.elem+i)<*(B.elem+j))
{
i++;
}
else if(*(A.elem+i)>*(B.elem+j))
{
if(flag==0)
{
printf("%d",*(B.elem+j));
flag=1;
}
else
{
printf(" %d",*(B.elem+j));
}
j++;
}
else
{
i++;
j++;
}
}
if(j<B.length )
{
while(j<B.length)
{
if(flag==0)
{
printf("%d",*(B.elem+j));
flag=1;
}
else
{
printf(" %d",*(B.elem+j));
}
j++;
}
}
printf("\n");
}
int main()
{
int Case;
int i;
scanf("%d", &Case);
for(i=1;i<=Case;i++)
{
SqList A,B;
///初始化顺序表
InitListSq(A);
InitListSq(B);
///创建顺序表
int la;
scanf("%d",&la);
A.length=la;
Create_SqList(A,la);
int lb;
scanf("%d",&lb);
B.length=lb;
Create_SqList(B,lb);
printf("Case #%d:\n",i);
///交集
Jiao_Sqlist(A,B);
///并集
Bing_SqList(A,B);
///补集
A_B_SqList(A,B);
B_A_SqList(A,B);
///释放
Delete_Sqlist(A);
Delete_Sqlist(B);
}
return 0;
}
网友评论