数据结构--c语言链表实现集合的（并，交，补）运算！

数据结构–c语言链表实现集合的（并，交，补）运算！

**前言：**
	*进入了大二，有同学说学习数据结构像学习数学（但这里不仅仅高中数学运算那么简单！更多是逻辑和思维的训练吧！）。而本宝宝刚开始面对这门课程是却是有点措手不及，对一些结构的理解还达不到所谓的人题合一！仅仅靠老师课堂上的讲解是不够的，一定要下来搞懂，不管是以后工作，还是以后考研，这门课程的重要性是不言而喻的！（啰嗦几句 哈哈哈哈！！！）*

要求如图：

这些是功能界面，相当于一个菜单吧！

#include<stdio.h>
#include<stdlib.h>
#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 <= n;i ++)
	{
		//printf("请输入集合的第%d个数：",i);
		p=(LinkList)malloc(sizeof(LNode));
		if(p!=NULL)
		{
			scanf("%d",&p->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:printf("请输入集合A要插入的个数：\n");scanf("%d",&x);input(La,x);
					printf("请按回车继续！\n");
				    getchar();getchar();system("cls");break;
			case 2: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]，祝大家编程愉快！完！