2.cpp

集合运算器 数据结构问题 可实现叫、并、差集。判断元素、子集

#include <stdio.h>
#include <stdlib.h>
typedef struct List//节点的定义
{
	int data;
	struct List *next;
}List,*Link;
Link CreateList(Link head)//创建链表
{
	head=(Link)malloc(sizeof(List));
	head->next=NULL;
	while (1)
	{
		Link pointor=(Link)malloc(sizeof(List));
		scanf("%d",&pointor->data);
		if (pointor->data==0)
			break;
        pointor->next=head->next;
		head->next=pointor;
	}
	return head;
}
void sortList(Link head){ //对链表排序
	 //利用数据交换代替结点的交换
	 char e;
	 Link p,q,s;
	 if(head->next){
	 p=head->next;
	 q=p->next;
	 e=p->data;
	 s=p;
	 while(p->next){
	  while(q){
		if(q->data<e)
		  {e=q->data;
		   s=q;
		   q=q->next;}
		else
		   q=q->next;}
	  s->data=p->data;
	  p->data=e;
	  p=p->next;
	  q=p->next;
	  s=p;
	  e=p->data;}}
}

void PrintList(Link head)//输出集合
{
	Link newhead=head->next;
    do
    {
		sortList(head);
        printf("%d ",newhead->data);
	    newhead=newhead->next;
    }while (newhead!=NULL);
	printf("\n");
}
void SetIntersection(Link head1,Link head2)//集合的交集
{
   for(Link p=head1->next;p!=NULL;p=p->next)
   for(Link q=head2->next;q!=NULL;q=q->next)
   {
	   if (p->data==q->data)
	   {
		   sortList(head1);
		   printf("%d ",p->data);
	   }
   }
   printf("\n");
}
void SetAltogeter(Link head1,Link head2)//集合并集
{
	for (Link p=head1->next;p!=NULL;p=p->next)
	{
		
		 for (Link q=head2->next;q!=NULL;q=q->next)
		 {
			if(p->data!=q->data&&q->next==NULL)
			{
			    printf("%d ",p->data);
			}
			if(p->data==q->data)
			{
				break;
			}
		 }
	}
		   PrintList(head2);
		   printf("\n");
}
void SetMission(Link head1,Link head2)//集合的差
{
	printf("集合1-集合2:\n");
	for (Link p=head1->next;p!=NULL;p=p->next)
	{
		
		 for (Link q=head2->next;q!=NULL;q=q->next)
		 {
			if(p->data!=q->data&&q->next==NULL)
			{
				sortList(head1);
			    printf("%d ",p->data);
			}
			if(p->data==q->data)
				break;
		 }
	}
	printf("\n");
	printf("集合2-集合1:\n");
	for (Link m=head2->next;m!=NULL;m=m->next)
	{
		for (Link n=head1->next;n!=NULL;n=n->next)
		{
			if (m->data!=n->data&&n->next==NULL)
			{
				sortList(head2);
				printf("%d ",m->data);
			}
			if (m->data==n->data)
			{
				break;
			}
		}
	}
	printf("\n");
}
int ListFound_L(Link head,int e)
{
	Link p; 
	p=head->next;
	printf("请输入你要判别的元素:\n");
	scanf("%d",&e);
	if(p)
	{
		while(p!=NULL)
		{
			if(e==p->data)
			{
				printf("%d是集合中元素\n",e);
				printf("补集为:");
				for(p=head->next;p!=NULL;p=p->next)
				{
					if(e!=p->data)
					{
						sortList(head);
						printf("%d ",p->data);	
					}
				}	
				printf("\n");
				return 1;
			}	
			else 
				p=p->next;
		  }
	printf("%d非集合中元素\n",e);
	}
	else
	{
		printf("%d非集合中元素\n",e);
		return 1;
	}
	return 1;
}
void ListFound_L2(Link head)
{
	Link head3,p1,p3,p4;
	int i=0,n=0,j=0;
	printf("请输入你要判别的子集元素(以0结束)\n");
	head3=CreateList(head3);
	p4=p1=head->next;
	p3=head3->next;
	while(p4)
	{
		i++;
		p4=p4->next;
	}
	while(p3)
	{
		j++;
		p3=p3->next;
	}
	p3=head3->next;
	while(p3)
	{
		p1=head->next;
		while(p1)
		{
			if(p3->data!=p1->data)
				p1=p1->next;
			else
			{
				n++;
				break;
			}
		}
		p3=p3->next;
	}
	p3=head3->next;
	p1=head->next;
	if(j==n)
	{
		if(i>=n)
		{
			printf("该集合是原集合的子集!\n");
		    printf("补集为:");
			for(p1=head->next;p1!=NULL;p1=p1->next)
			{
				for(p3=head3->next;p3!=NULL;p3=p3->next)
				{
					if(p1->data!=p3->data&&p3->next==NULL)
					{
						sortList(head);
					    printf("%d ",p1->data);
					}
					if(p1->data==p3->data)
						break;
				}
			}
			printf("\n");
		}
		else
			printf("该集合非原集合子集!\n");
	}
	else
		printf("该集合非原集合子集!\n");
}
/*void BU(Link head1,Link head2,int i,int e)
{
	Link p,q;
	p=head1;q=head2;
	while(p->next)
	{
		if(e!=p->data)
			printf("%d",&e);
            p=p->next;
	}
	while(q->next) 
	{
		if(e!=q->data)
			printf("%d",&e);
	        q=q->next;
	}
}*/
void main()
{
	Link head1,head2;
	int e;
    printf("                 ---您好，欢迎进入集合运算器系统!---\n");
    printf("================================================================================\n");
	printf("以0结束\n");
    printf(" 1.创建列表head1\n");
    head1=CreateList(head1);
    printf(" 2.创建列表head2\n");
	head2=CreateList(head2);
    printf(" 3.输出链表1\n");
	PrintList(head1);
    printf(" 4.输出链表2\n");
	PrintList(head2);
    printf(" 5.集合的交集\n");
	SetIntersection(head1,head2);
    printf(" 6.集合的并集\n");
	SetAltogeter(head1,head2);
    printf(" 7.集合的差\n");
	SetMission(head1,head2);
	printf(" 8.与集合head1中元素的判断\n");
	ListFound_L(head1,e);
	printf(" 9.与head1集合子集的判断\n");
	ListFound_L2(head1);	
    printf("================================================================================\n");
}//主函数结束