集合的交、并、差运算
【问题描述】
编制一个能演示执行集合的交、并和差运算的程序。
【任务要求】
1)集合元素用字符串
2)算法要点：利用单链表表示集合；理解好三种运算的含义
【测试数据】
自行设定，注意边界等特殊情况。
如有帮助，请采纳。点击我回答右上角【采纳】按钮。
参考如下：
#include "F:/SqList.cpp"
#include<iostream.h>
#include<string.h>
void UnionList(SqList *LA,SqList *LB,SqList *&LC)//并集
{
int i=0,j=0,k=0; //i、j、k分别作为LA、LB、LC的下标
LC=(SqList *)malloc(sizeof(SqList));
LC->length=0;
while (i<LA->length && j<LB->length)
{
if (LA->data[i]<LB->data[j])
{
LC->data[k]=LA->data[i];
i++;k++;
}
else if(LA->data[i]==LB->data[j])
{
LC->data[k]=LA->data[i];
i++;k++;j++;
}
else if(LA->data[i]>LB->data[j])
{
LC->data[k]=LB->data[j];
k++;j++;
}
}
while (i<LA->length) //LA尚未扫描完,将其余元素插入LC中
{
LC->data[k]=LA->data[i];
i++;k++;
}
while (j<LB->length) //LB尚未扫描完,将其余元素插入LC中
{
LC->data[k]=LB->data[j];
j++;k++;
}
LC->length=k;
}
void Commnode(SqList *LA,SqList *LB,SqList *&LC)//交集
{
int i=0,j=0,k=0;
LC=(SqList *)malloc(sizeof(SqList));
LC->length=0;
while(i<LA->length&&j<LB->length)
{
if(LA->data[i]<LB->data[j])
{
i++;
}
else if(LA->data[i]==LB->data[j])
{
LC->data[k]=LA->data[i];
i++;j++;k++;
}
else if(LA->data[i]>LB->data[j])
{
j++;
}
}
LC->length=k;
}
void Subtraction(SqList *LA,SqList *LB,SqList *&LC)//差集
{
int i=0,j=0,k=0;
LC=(SqList *)malloc(sizeof(SqList));
LC->length=0;
while(i<LA->length&&j<LB->length)
{
if(LA->data[i]<LB->data[j])
{
LC->data[k]=LA->data[i];
i++;k++;
}
else if(LA->data[i]==LB->data[j])
{
i++;j++;
}
else if(LA->data[i]>LB->data[j])
{
j++;
}
}
while(i<LA->length)
{
LC->data[k]=LA->data[i];
i++;k++;
}
LC->length=k;
}
void main()
{ char a[10],b[10];
SqList *L1,*L2,*L3;
int a1,b1;
InitList(L1);
InitList(L2);
InitList(L3);
int A=0;
do{
cout<<"请输入集合A:";
cin>>a;
a1=strlen(a);
for(int i=0;i<a1;i++)
ListInsert(L1,a[i]);
if(a1>ListLength(L1))
{
cout<<"注意 ! 元素有重复"<<endl;
DestroyList(L1);InitList(L1);
}
else if(a1==ListLength(L1))A=1;
}while(A==0);
int B=0;
do{
cout<<"请输入集合B:";
cin>>b;
b1=strlen(b);
for(int j=0;j<b1;j++)
ListInsert(L2,b[j]);
if(b1>ListLength(L2))
{
cout<<"注意 ! 元素有重复"<<endl;
DestroyList(L2);InitList(L2);
}
else if(b1==ListLength(L2)) B=1;
}while(B==0);
cout<<"集合A的长度:"<<a1<<endl;
cout<<"集合B的长度:"<<b1<<endl;
cout<<"集合A在顺序表中的结构:"<<endl;
DispList(L1);
cout<<"集合B在顺序表中的结构:"<<endl;
DispList(L2);
cout<<"并集:"<<endl;
UnionList(L1,L2,L3);
DispList(L3);
cout<<"交集:"<<endl;
Commnode(L1,L2,L3);
DispList(L3);
cout<<"差集:"<<endl;
Subtraction(L1,L2,L3);
DispList(L3);
}
//SqList.cpp文件
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{ ElemType data[MaxSize]; //存放顺序表元素
int length; //存放顺序表的长度
} SqList; //顺序表的类型定义
void CreateList(SqList *&L,ElemType a[],int n) //建立顺序表
{
int i;
L=(SqList *)malloc(sizeof(SqList));
for (i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void InitList(SqList *&L) //初始化线性表
{
L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L->length=0;
}
void DestroyList(SqList *&L) //销毁线性表
{
free(L);
}
int ListEmpty(SqList *L) //判线性表是否为空表
{
return(L->length==0);
}
int ListLength(SqList *L) //求线性表的长度
{
return(L->length);
}
void DispList(SqList *L) //输出线性表
{
int i;
if (ListEmpty(L)) return;
for (i=0;i<L->length;i++)
printf("%c ",L->data[i]);
printf("/n");
}
int GetElem(SqList *L,int i,ElemType &e) //求线性表中某个数据元素的值
{
if (i<1 || i>L->length)
return 0;
e=L->data[i-1];
return 1;
}
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;
}
int ListInsert(SqList *&L,int i,ElemType e) //插入数据元素
{
int j;
if (i<1 || i>L->length+1)
return 0;
i--; //将顺序表位序转化为elem下标
for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++; //顺序表长度增1
return 1;
}
int ListInsert(SqList *&L,ElemType e) //有序表
{
int i=0,j;
while(i<L->length&&L->data[i]<e)i++;
if(L->data[i]==e)return 0;
for(j=ListLength(L);j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return 1;
}
int ListDelete(SqList *&L,int i,ElemType &e) //删除数据元素
{
int j;
if (i<1 || i>L->length)
return 0;
i--; //将顺序表位序转化为elem下标
e=L->data[i];
for (j=i;j<L->length-1;j++) //将data[i]之后的元素前移一个位置
L->data[j]=L->data[j+1];
L->length--; //顺序表长度减1
return 1;
}