集合交并及差运算及实现.doc

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <string.h> // 顺序表定义

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define IN_THIS_LIST 1
#define NOT_IN_THIS_LIST 0 //宏定义

typedef char Elemtype;
typedef int Status;
typedef struct List
{
Elemtype data;
struct List *next;
}LNode,*LinkList; //结构体定义

Status InitList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode));
if(!L) exit(OVERFLOW);
L->data=NULL;L->next=NULL;
return OK;
} //构造表头

Status PrintList(LinkList L)
{
LinkList PrintList=L->next;
if(!L->next) {cout<<"该集合为空！"<<endl;return ERROR;}
while(PrintList->next)
{
cout<<PrintList->data<<",";
PrintList=PrintList->next;
}
cout<<PrintList->data;
cout<<endl;
return OK;
} //输出表中元素

Status InsertList(LinkList &L,Elemtype e)
{
if((int)e<97||(int)e>122) return ERROR;
LinkList compare=(LinkList)malloc(sizeof(LNode));
LinkList insertdata=(LinkList)malloc(sizeof(LNode));
compare=L;
while(compare->next)
{
if(e==compare->next->data) return TRUE;
else if(e<(compare->next->data))
{
insertdata->next=compare->next;
insertdata->data=e;
compare->next=insertdata;
return OK;
}
compare=compare->next;
}
insertdata->data=e;
compare->next=insertdata;
insertdata->next=NULL;
return OK;
} //向表中增加元素

Status DeleteList_data(LinkList &L,Elemtype e)
{
LinkList Deletedata=L->next;
while(Deletedata->next)
{
if(!(Deletedata->next->next)&&(Deletedata->next->data==e))
{Deletedata->next=NULL; return OK;}
if(Deletedata->next->data==e)
{
Deletedata->next=Deletedata->next->next;
return OK;
}
Deletedata=Deletedata->next;
}
Deletedata=L->next;
if(Deletedata->data==e)
{
L->next=Deletedata->next;
return OK;
}
return ERROR;
}
Status jiaoji(LinkList La,LinkList Lb,LinkList &L)
{
LinkList Pa=La->next;
LinkList Pb=Lb->next;
while(Pa)
{
while(Pb)
{
if(Pb->data==Pa->data)
InsertList(L,Pa->data);
Pb=Pb->next;
}
Pb=Lb->next;
Pa=Pa->next;
}

return OK;
} //求交集函数

Status chaji(LinkList La, LinkList Lb,LinkList &L)
{
Status compare=0;
LinkList Pa,Pb;
Pa=La->next;
Pb=Lb->next;
while(Pa)
{
while(Pb)
{
if(Pa->data==Pb->data) compare++;
Pb=Pb->next;
}
if(!compare) InsertList(L,Pa->data);
compare=0;
Pb=Lb->next;
Pa=Pa->next;
}
return OK;
} //差集函数

Status bingji(LinkList La,LinkList Lb,LinkList &L)
{
LinkList Pa=La->next;
LinkList Pb=Lb->next;
while(Pa){
InsertList(L,Pa->data); Pa=Pa->next;}
while(Pb){
InsertList(L,Pb->data); Pb=Pb->next;}
return OK;
} //并集函数

Status buji(LinkList L,LinkList &List)
{
Status set=97;
while(set<=122)
{
InsertList(List,(Elemtype)set);
set++;
}
LinkList PL=L->next;
LinkList P=List->next;
while(PL)
{
while(P)
{
if(P->data==PL->data)
DeleteList_data(List,P->data);
P=P->next;
}
P=List->next;
PL=PL->next;
}
return OK;
} //补集函数

Status compare(LinkList L,Elemtype e)
{
LinkList P=L->next;
while(P)
{
if(P->data==e) return IN_THIS_LIST;
P=P->next;
}
return NOT_IN_THIS_LIST;
} //判定函数

Status ziji(LinkList La,LinkList Lb)
{
LinkList Pb=Lb->next;
while(Pb)
{
if(!compare(La,Pb->data)) return FALSE;
Pb=Pb->next;
}
return TRUE;
}

Status menu(LinkList A,LinkList B)
{
int i;
do{
system("cls");
cout<<" * * * * * * 集合的计算 * * * * *\n";
cout<<" * <1>:输入集合信息 *\n";
cout<<" * <2>:输出交集信息 *\n";
cout<<" * <3>:输出差集信息 *\n";
cout<<" * <4>:输出并集信息 *\n";
cout<<" * <5>:判定是否子集 *\n";
cout<<" * <6>:输出补集信息 *\n";
cout<<" * <0>:退出管理系统 *\n";
cout<<" * * * * * * * 程尧 制作 * * * * * * *\n";
cout<<"请选择操作(1-6):";
cin>>i;
if(A->next&&B->next) {cout<<"集合A:"; PrintList(A); cout<<"集合B:"; PrintList(B);}
}while(i<0||i>6);
return i;
}
int main()
{
LinkList A; InitList(A);
LinkList B; InitList(B);
LinkList J; InitList(J);
LinkList K; InitList(K);
LinkList L; InitList(L);
LinkList M; InitList(M);
Elemtype a;

do{
switch(menu(A,B))
{
case 1:cout<<"请输入集合元素，以“0”结束"<<endl;
cout<<"输入集合A：";
cin>>a;
while(a!='0')
{
InsertList(A,a);
cin>>a;
}
cout<<"输入集合B：";
cin>>a;
while(a!='0')
{
InsertList(B,a);
cin>>a;
}
break;
case 2: jiaoji(A,B,J);
cout<<"两集合的交集：";
PrintList(J);
cout<<"输入任意键返回主菜单"<<endl;
cin>>a;
break;
case 3: chaji(A,B,K);
cout<<"集合A关于集合B的差集：";
PrintList(K);
cout<<"输入任意键返回主菜单"<<endl;
cin>>a;

break;
case 4:bingji(A,B,L);
cout<<"两集合的并集：";
PrintList(L);
cout<<"输入任意键返回主菜单"<<endl;
cin>>a;
break;
case 5:if(ziji(A,B)) {
cout<<"集合B是集合A的子集"<<endl;
}
else cout<<"集合B不是集合A的子集"<<endl;
cout<<"输入任意键返回主菜单"<<endl;
cin>>a;
break;
case 6:buji(A,M);
cout<<"集合A关于全集的补集：";
PrintList(M); cout<<"输入任意键返回主菜单"<<endl;
cin>>a;
break;
case 0: return OK;
break;
}
}while(1);

return OK;
}