#include<iostream>
#include<malloc.h>
#include<stdlib.h>
//#include<stdio.h>
//#include<string>
using namespace std;
#define MAXSIZE 50//存储空间初始分配量
#define OK 1//定义常用判断词为整型数值
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;//定义Status为整型类型
typedef int ElemType;//ElemType类型可根据实际情况改变首先定义ElemType为整型类型
typedef struct
{
ElemType data[MAXSIZE];//数组存储数据元素,最大存储MAXSIZE
int length;//纪录数组当前长度
} Sqlist; //线性表结构体声明
//函数声明
Sqlist* InitList();//线性表初始化
Status ListEmpty(Sqlist *L);
//判断线性表是否为空
int ListLength(Sqlist *L);//获取线性表的长度
int GetElem(Sqlist *L,int i,ElemType &e);//将线性表L中的弟i个位置元素值返回给e
int LocateElem(Sqlist *L,ElemType e);//在线性表中查找与给定值e相等的第一个元素
Status ListInsert(Sqlist *L,int i,ElemType e);//在线性表的第i个位置插入值为e的元素
Status ListDelete(Sqlist *L,int i,ElemType &e);//删除线性表中第i个位置的元素,并用e返回其值
void AvoidList(Sqlist *L);//除掉集合中重复的元素
void DispList(Sqlist *L);//打印集合中所有的元素
void IntersectSqlist(Sqlist *La,Sqlist *Lb);//求两个集合的交集并打印这个交集的所有元素
void UnionSqlist(Sqlist *La,Sqlist *Lb);//求两个集合的并集并打印这个并集的所有元素
//函数定义
//线性表初始化
Sqlist* InitList()
{
Sqlist *L;
L = (Sqlist*)malloc(sizeof(Sqlist));//开辟空间存储线性表
//if(L == NULL)
//return ERROR;
L->length=0;
return L;//返回这个线性表的指针
}
//判断线性表是否为空,并返回判断结果
Status ListEmpty(Sqlist *L)
{
if(L->length==0)
return 0;
else
return 1;
}
//获取线性表的长度并返回
int ListLength(Sqlist *L)
{
return L->length;
}
//在线性表中查找与给定值e相等的第一个元素,如果查找成功,返回该元素在表中序号表示成功;否则返回0表示失败
int LocateElem(Sqlist *L,ElemType e)
{
int i=0;
while(i<L->length&&L->data[i]!= e)//遍历线性表中的元素
{
i++;
}
if(i>=L->length)
return FALSE;
else
return i+1;
}
//将线性表L中的弟i个位置元素值返回给e
int GetElem(Sqlist *L,int i,ElemType &e)
{
if(i<1 || i>L->length)
return 0;
e = L->data[i-1];
return 1;
}
//在线性表中的第i个位置插入值为e的元素
Status ListInsert(Sqlist *L,int i,ElemType e)
{
if(L->length==MAXSIZE)// 如果顺序线性表已满则无法插入
return ERROR;
if(i<0||i>L->length+1)//如果插入位置不在范围内则无法插入
{
return ERROR;
}
if(i<=L->length)//若插入数据不在表尾
{
for(int j=L->length-1; j>=i-1; j--)
{
L->data[j+1]=L->data[j];//将第i个及之后的元素全部向后串一个
}
L->data[i-1]=e;//将第i个值返回给e
L->length++;//更新线性表长度
return OK;
}
if(i==L->length+1) //若在表尾插入
{
L->data[L->length]=e;
L->length++;//更新线性表长度
return OK;
}
}
//删除线性表中第i个位置的元素,并用e返回其值
Status ListDelete(Sqlist *L,int i,ElemType &e)
{
if(L->length==0)//判断是否删除位置不合理
return ERROR;
if(i<1||i>L->length)
{
return ERROR;
}
if(i==L->length)//如果删除的是最后一个元素,长度减一返回删除的值
{
e=L->data[i-1];
L->length--;
return OK;
}
if(0<1&&i<L->length)//如果删除的不是最后一个元素,则将其后的元素往前赋值挪动
{
e=L->data[i-1];
for(int j=i; j<L->length; j++)
{
L->data[j-1]=L->data[j];
}
L->length--;
return OK;
}
}
//除掉集合中重复的元素
void AvoidList(Sqlist *L)
{
ElemType e;
for(int i=0; i<(L->length - 1); i++)//以前一个元素的值为基准,让其后的每一个值与它比较。
{
for( int j=i+1; j<L->length; j++)
{
if(L->data[i]==L->data[j])//如果相同则删除其后的这个元素,继续判断这个位置的元素与这个元素比较,否则让后一个位置的元素与这个元素比较
{
ListDelete(L,j+1,e);
j--;
}
}
}
}
//打印集合中所有的元素
void DispList(Sqlist *L)
{
for(int i =0; i<L->length; i++)
{
cout<<" \t"<<L->data[i];
}
cout<<endl;
}
//求两个集合的交集并打印这个交集的所有元素
void IntersectSqlist(Sqlist *La,Sqlist *Lb)
{
Sqlist *Lc;//将两个线性表共有的元素存入新创建的空线性表
Lc = InitList();
ElemType e;
for(int i=0; i<La->length; i++)//遍历La和Lb中的所有元素比较元素值
{
GetElem(La,i+1,e);
for(int j=0; j<Lb->length; j++)
{
if(e==Lb->data[j])
{
ListInsert(Lc,Lc->length+1,e);
}
}
}
if(ListEmpty(Lc)==0) //判断Lc中是否仍为空,如果是则交集为空集
{
cout<<"空集 ";
}
DispList(Lc);//打印交集Lc
}
//求两个集合的并集并打印这个并集的所有元素
void UnionSqlist(Sqlist *La,Sqlist *Lb)
{
for(int i=1; i<=Lb->length; i++)//将线性表Lb的元素依次插入La中
{
ElemType e;
GetElem(Lb,i,e);
int temp = La->length + 1;
ListInsert(La,temp,e);
}
AvoidList(La);//对线性表La进行除重操作
DispList(La);//打印并集La
}
int main()
{
Sqlist *La;//声明两个指向线性表类型的指针
Sqlist *Lb;
La = InitList();//初始化线性表La
cout<<"******请输入第一组数据的个数:****** "<<endl;
cin>>La->length;//获取集合A的元素个数赋值给线性表的长度
if(La->length<0||La->length>50)//检测输入个数是否不合法,如不合法则重新调用main函数继续进行。
{
if(La->length<0)
{
cout<<"---数据个数不能为负,请重试!---"<<endl;
cout<<endl;
main();
return 0;
}
if(La->length>50)
{
cout<<"---数据个数溢出,请重试!---"<<endl;
cout<<endl;
main();
return 0;
}
}
cout<<"******输入你的第一组数据:****** "<<endl;
for( int i=0; i<La->length; i++) //将输入的元素存入线性表La中
{
cin>>La->data[i];
}
cout<<"----经重复检测后的集合La为:---- "<<endl;
AvoidList(La);//对线性表La进行除重操作
DispList(La);//打印除重后的线性表La
Lb = InitList();//初始化线性表Lb
cout<<"******请输入第二组数据的个数:****** "<<endl;
cin>>Lb->length;//获取集合B的元素个数赋值给线性表的长度
if(Lb->length<0||Lb->length>50)//检测输入个数是否不合法,如不合法则重新调用main函数继续进行。
{
if(Lb->length<0)
{
cout<<"---数据个数不能为负,请重试!---"<<endl;
cout<<endl;
main();
return 0;
}
if(Lb->length>50)
{
cout<<"---数据个数溢出,请重试!---"<<endl;
cout<<endl;
main();
return 0;
}
}
cout<<"******输入你的第二组数据:****** "<<endl;
for(int i=0; i<Lb->length; i++)//将输入的元素存入线性表Lb中
{
cin>>Lb->data[i];
}
cout<<"----经重复检测后的集合La为:---- "<<endl;
AvoidList(Lb);//对线性表Lb进行除重操作
DispList(Lb);//打印除重后的线性表Lb
if(ListEmpty(La)==0||ListEmpty(Lb)==0)//判断线性表La和Lb中是否存在为空,若存在为空,则输出两集合的交集为空集
cout<<"***交集为空***"<<endl;
if(ListEmpty(La)!=0&&ListEmpty(Lb)!=0)//判断线性表La和Lb中是否都不为空,若成立,则调用求交集函数
{
cout<<"***交集为:";
IntersectSqlist(La,Lb);
}
/*CreateList(Sqlist *La,ElementType a[],sizeA);
CreateList(Sqlist *Lb,ElementType b[],sizeB*/
if(ListEmpty(La)==0||ListEmpty(Lb)==0)////判断线性表La和Lb中是否存在为空,若存在为空,继续判断是否两个都为空
{
if(ListEmpty(La)==0&&ListEmpty(Lb)==0)//若两个线性表都为空,则并集为空
{
cout<<"***并集为空***"<<endl;
}
if(ListEmpty(La)==0)//如果只有La为空,并集集为Lb
{
DispList(Lb);
}
if(ListEmpty(Lb)==0)//如�