cpp1.cpp

仅用数据结构中的单链表就可实现集合的交、并与两个集合之差

#include <iostream>
typedef int ElemType;
using namespace std;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LinkList;
void CreateListR(LinkList *&L,ElemType a[],int n)
{
	LinkList *s,*r;
	int i;
	L=(LinkList *)malloc(sizeof(LinkList));
	r=L;
	for(i=0;i<n;i++)
	{
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}
void DispList(LinkList *L)
{
	LinkList *p=L->next;
	if(p==NULL)
		cout<<"空集";
	else
	{
		while(p!=NULL)
		{
		cout<<p->data<<" ";
		p=p->next;
		}
	}
}
void sort(LinkList *&L)
{
	LinkList *p=L->next,*q,*r;
	if(p!=NULL)
	{
		r=p->next;
		p->next=NULL;
		p=r;
		while(p!=NULL)
		{
			r=p->next;
			q=L;
			while(q->next!=NULL && q->next->data<p->data)
				q=q->next;
			p->next=q->next;
			q->next=p;
			p=r;
		}
	}
}
void Diffence(LinkList *A,LinkList *B,LinkList *&C)  //求两个集合的差//
{
	LinkList *pa=A->next,*pb=B->next,*s,*r;
	C=(LinkList *)malloc(sizeof(LinkList));
	C->next=NULL;
	r=C;
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data<pb->data)
		{
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=NULL;
			r->next=s;
			r=s;
			pa=pa->next;
		}
		else if(pa->data>pb->data)
			pb=pb->next;
		    else 
			{
				pa=pa->next;
				pb=pb->next;
			}
	}
	while(pa!=NULL)             //将A余下的结点复制后链到C中//
	{
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=pa->data;
		s->next=NULL;
		r->next=s;
		r=s;
		pa=pa->next;
	}
	r->next=NULL;
}
void Union(LinkList *A,LinkList *B,LinkList *&C) 
{
	LinkList *pa=A->next,*pb=B->next,*s,*r;
	C=(LinkList *)malloc(sizeof(LinkList));
	C->next=NULL;
	r=C;
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data!=pb->data)
		{
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=NULL;
			r->next=s;
			r=s;
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pb->data;
			s->next=NULL;
			r->next=s;
			r=s;
			pa=pa->next;
			pb=pb->next;
		}
		else
		{
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=NULL;
			r->next=s;
			r=s;
			pa=pa->next;
			pb=pb->next;
		}
		
	}
	r->next=NULL;
}
void Intersection(LinkList *A,LinkList *B,LinkList *&C)      //求两个集合的交//
{
	LinkList *pa=A->next,*pb=B->next,*s,*r;
	C=(LinkList *)malloc(sizeof(LinkList));
	C->next=NULL;
	r=C;
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data<pb->data)
			pa=pa->next;	
		else if(pa->data>pb->data)
			pb=pb->next;
		else
		{
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=NULL;
			r->next=s;
			r=s;
			pa=pa->next;
			pb=pb->next;
		}
		r->next=NULL;
	}
}
void main()
{
	int a[10],b[10],n;
	LinkList *A,*B,*C;
	cout<<"请输入一个数";
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cout<<"请输入第"<<i<<"个数a"<<"["<<i<<"]";
		cin>>a[i];
		cout<<"请输入第"<<i<<"个数b"<<"["<<i<<"]";
		cin>>b[i];
	}
	CreateListR(A,a,n);
	CreateListR(B,b,n);
	sort(A);
	sort(B);
	Diffence(A,B,C);
	cout<<"A-B=";
	DispList(C);
	cout<<endl;
	Union(A,B,C);
	cout<<"A+B=";
	DispList(C);
	cout<<endl;
    Intersection(A,B,C);
    cout<<"A交B=";
	DispList(C);
	cout<<endl;
	system("pause");
}