|
数据结构–c语言链表实现集合的（并，交，补）运算！
要求如图：  这些是功能界面，相当于一个菜单吧（声明：集合只适用于时数字）！
#include
#include
#define ERROR -1
#define OK 1
typedef int Status; //要加分号
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//创建空链表
Status Init_LinkList(LinkList &L)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p)
return ERROR;
L=p;
L->next=NULL;
return OK;
}
int x,y;
void show()
{
printf("\t\t*********单链表(头插法)集合运算************\n");
printf("\n");
printf("\t\t\t1 集合A数据输入\n");
printf("\t\t\t2 集合B数据输入\n");
printf("\t\t\t3 集合A数据显示\n");
printf("\t\t\t4 集合B数据显示\n");
printf("\t\t\t5 集合A和集合B的并集\n");
printf("\t\t\t6 集合A和集合B的交集\n");
printf("\t\t\t7 集合A和集合B的差集\n");
printf("\t\t\t0 退出系统\n");
printf("\n");
printf("\t\t*********单链表(头插法)集合运算*************\n");
printf("\n");
}
// 输入
Status input(LinkList &L,int n) //不能写成input(LinkList L,int n)，这样的值不会改变
{
LinkList p;
int i;
for(i = 1;i data);
p->next = L->next; //头插法
L->next = p;
}
else
return ERROR;
}
printf("集合输入完成！\n");
return OK;
}
//输出
void Output(LinkList L)
{
LinkList p; //定义一个指针p
//p=(LinkList)malloc(sizeof(LNode));
if(L->next==NULL)
printf("该链表是空链表!\n");
else
{
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
printf("\n");
}
}
//实现链表的清空
Status ClearList_L(LinkList &L)
{
LinkList p,q; //定义两个指针p,q
p=L->next;
if(!p) //如果p指向的链表L是一个空表 就直接返回OK
return OK;
while(p) //当p指向的链表L不是空表 则进行以下语句，赋给另外一个指针
{
q=p;
p=p->next;
free(q); //释放链表结点的空间
}
L->next=NULL; //将L链表的next指针域 置为 NULL 空
return OK;
}
//并集 (先清空C，C中的数据会在后面的循环中不断插入！就是A与C找比较，C中没有A的就插入；B与C找比较，C中没有B的就插入（遍历完，即==NULL的时候插入）)
void and_set(LinkList La,LinkList Lb,LinkList &Lc)
{
if(Lc->next!=NULL) //如果Lc链表不为空则就要进行链表清空
ClearList_L(Lc);
LinkList p,q,s;//p指针用来遍历A,B q用来控制C的结点
//对链表A插入C中
p=La->next; //指针p控制扫描La的每一个结点（元素）
while(p)
{
q=Lc->next;
while(q && (q->data!=p->data))//C中不为空，且数据不相等
q=q->next;
if(q==NULL) //当q遍历完一次都没有找到的话，即q的最后为空时就可以将A中的一个元素插入C中
{
s=(LinkList)malloc(sizeof(LNode)); //s指针用来控制C中的数据
s->data=p->data; //头插法
s->next=Lc->next;
Lc->next=s;
}
p=p->next;
}
//对链表B插入C中
p=Lb->next; //指针p控制扫描Lb的每一个结点（元素）
while(p)
{
q=Lc->next;
while(q && (q->data!=p->data))C中不为空，且数据不相等
q=q->next;
if(q==NULL) //当q遍历完一次都没有找到的话，即q的最后为空时就可以将A中的一个元素插入C中
{
s=(LinkList)malloc(sizeof(LNode)); //s指针用来控制C中的数据
s->data=p->data; //头插法
s->next=Lc->next;
Lc->next=s;
}
p=p->next;
}
/*
//插A
while(p!=NULL)
{
q=Lc->next; //指针q控制扫描链表Lc的每一个结点（元素）
while(q && (q->data != p->data))
q=q->next;
if(!q) //La中没找到与Lc链表中相同的结点时，就把La上结点在Lc上插入（把集合La的元素填入集合Lc）
{
s=(LinkList)malloc(sizeof(LNode));
s->data=p->data;
s->next=Lc->next; //插入到头部
Lc->next=s;
}
p=p->next; //指向下一个结点
}
p=Lb->next;
*/
//插B
/*while(p!=NULL)
{
q=Lc->next;
while(q && (q->data != p->data)) //如果找到Lb中的元素与Lc中的元素相同则就继续循环否则就结束循环
q=q->next;
if(!q) //满足没找到相同元素的情况
{
s=(LinkList)malloc(sizeof(LNode)); //创建一个新的结点
s->data=p->data; //将Lb中的元素赋给s结点
s->next=Lc->next; //然后插入到Lc表的头部
Lc->next=s;
}
p=p->next;
}*/
}
//交集 (先清空C链表，再A与B中找相同的break（不为空，记录），再与C中比较（与并集同理插入）插入C中即可)
void intersection(LinkList La,LinkList Lb,LinkList &Lc)
{
LinkList p,q,s,k; //p是遍历A，q是遍历B，s是遍历C，k是赋值指针
if(Lc->next)
ClearList_L(Lc);
//A
p=La->next;
while(p) //A中不为空时
{
q=Lb->next;
while(q)
{
if(p->data==q->data)//找到了就可以break，也可以定义t进行计数操作,但是这样不好计算链表长度，当然也可以定义全局变量
break;
else
q=q->next;
}
if(q) //p不为空
{
s=Lc->next;
//寻找C中是否含有相同数据
while(s)
{
if(s->data==p->data)
break;
else
s=s->next;
}
if(s==NULL)
{
k=(LinkList)malloc(sizeof(LNode));
k->data=p->data;
k->next=Lc->next;
Lc->next=k;
}
}
p=p->next;
}
/*
p=La->next;
while(p)
{
q=Lb->next;
while(q)
{
if(q->data==p->data)
break;
else
q=q->next;
}
if(q)
{
s=Lc->next;
//寻找C中是否含有相同数据
while(s!=NULL)
{
if(s->data==p->data)
break;
else
s=s->next;
}
if(s==NULL)
{
k=(LinkList)malloc(sizeof(LNode));
k->data=p->data;
k->next=Lc->next;
Lc->next=k;
}
}
p=p->next;
}*/
}
//差集 （先清空C后，找A中与B中不同的，找到B最后，即==NULL的时候插入即可！）
void difference_set(LinkList La,LinkList Lb,LinkList &Lc)
{
LinkList p,q,s,k;
if(Lc->next)
ClearList_L(Lc);
p=La->next;
while(p!=NULL)
{
q=Lb->next;
while(q!=NULL)
{
if(q->data==p->data)
break;
else
q=q->next;
}
if(q==NULL)
{
s=Lc->next;
//寻找C中是否含有相同数据
while(s!=NULL)
{
if(s->data==p->data)
break;
else
s=s->next;
}
if(s==NULL)
{
k=(LinkList)malloc(sizeof(LNode));
k->data=p->data;
k->next=Lc->next;
Lc->next=k;
}
}
p=p->next;
}
}
int main()
{
//定义
int choice;
LinkList La,Lb,Lc;
//初始化
Init_LinkList(La);
Init_LinkList(Lb);
Init_LinkList(Lc);
//功能
while(1)
{
show();
printf("请输入要选择的功能：\n");
scanf("%d",&choice);
switch(choice)
{
case 1:ClearList_L(La);printf("请输入集合A要插入的个数：\n");scanf("%d",&x);input(La,x);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 2:ClearList_L(Lb);printf("请输入集合B要插入的个数：\n");scanf("%d",&y);input(Lb,y);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 3:printf("集合A为：\n");
Output(La);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 4:printf("集合B为：\n");
Output(Lb);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 5:printf("集合A与集合B的并集为：\n");
and_set(La,Lb,Lc);
Output(Lc);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 6:printf("集合A与集合B的交集为：\n");
intersection(La,Lb,Lc);
Output(Lc);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 7:printf("集合A与集合B的并集为：\n");
difference_set(La,Lb,Lc);
Output(Lc);
printf("请按回车继续！\n");
getchar();getchar();system("cls");break;
case 0:printf("成功退出系统!\n");exit(0);
getchar();getchar();system("cls");break;
default:printf("输入有误!\n"); exit(0);break;
}
}
return 0;
}
最后，相关步骤注意清空，代码中含有一些注释（大佬们若感觉很白痴请自动忽略），另外我所写得代码中的集合A，B的是完全依赖于高中的定义（即三个性质：确定性，互异性，无序性），若代码中存在错误，请评论留言，或者联系qq邮箱：[email protected]，祝大家编程愉快！完！
|