/////////////////////////
////集合的并交差////////
///////////////////////
#include<iostream>
#include<malloc.h>
using namespace std;
typedef struct Node
{
int data;//数据域
struct Node* pNext;//指针域
}NODE,*PNODE;
PNODE creat_list();
void jiaoji(PNODE Head1,PNODE Head2,int a[],int& s);//求交集,相同的元素
void travers_list(PNODE pHead); //遍历，输出链表。
void sort_list(PNODE pHead);//排序
void chaji(PNODE Head1,int a[],int s);//Head1-Head2的差集。
int length_list(PNODE pHead);//求集合（链表）的长度
//////////////////////////////////////////////////////////
int main(void)
{
cout<<"第一个集合"<<endl;
PNODE Head1=creat_list();//第一个集合的头指针
cout<<"第二个集合"<<endl;
PNODE Head2=creat_list();//第二个集合的头指针
sort_list(Head1); //排序
sort_list(Head2);
int n=length_list(Head1);
int a[n];
int s=0;
cout<<"两个集合的交集为："<<endl;
jiaoji(Head1,Head2,a,s);
cout<<"差集为："<<endl;
chaji(Head1,a,s);
cout<<endl;
cout<<"并集为："<<endl;
travers_list(Head2);
chaji(Head1,a,s);
return 0;
}
//////////////////////////////////////////////////////////////
PNODE creat_list()
{
int len;//这个表示有效节点的个数。
int val;//用来存放一个节点的值。
PNODE pHead=(PNODE)malloc(sizeof(NODE));
if(NULL==pHead)
{
cout<<"分配内存失败，程序终止！"<<endl;
exit(-1);
}
PNODE pTail=pHead;//构造一个尾节点。
pTail->pNext=NULL;//尾节点的指针域为空。
cout<<"请输入集合的中元素的个数"<<endl;
cin>>len;
for(int i=0;i<len;i++)
{
cout<<"请输入第"<<i+1<<"个元素的值："<<endl;
cin>>val;
PNODE pNew=(PNODE)malloc(sizeof(NODE));//生成新的节点。
if(NULL==pNew)
{
cout<<"分配内存失败，程序终止！"<<endl;
exit(-1);
}
pNew->data=val;
pTail->pNext=pNew;
pNew->pNext=NULL;
pTail=pNew;
}
return pHead;
}
//////////////////////////////////////////////////////////////////////////////
void sort_list(PNODE pHead)
{
int i, j, t;
int len = length_list(pHead);
PNODE p, q;
for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext)
{
for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext)
{
if (p->data > q->data)  //类似于数组中的:  a[i] > a[j]
{
t = p->data;//类似于数组中的:  t = a[i];
p->data = q->data; //类似于数组中的:  a[i] = a[j];
q->data = t; //类似于数组中的:  a[j] = t;
}
}
}
return;
}
//////////////////////////////////////////////////////////////////////////////////////
int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int len = 0;
while (NULL != p)
{
++len;
p = p->pNext;
}
return len;
}
/////////////////////////////////////////////////////////////////////////////////////////
void travers_list(PNODE pHead)//遍历
{
PNODE p=pHead->pNext;
while(NULL!=p)
{
cout<<p->data<<" ";
p = p->pNext;
}
}
////////////////////////////////////////////////////////////////////////////////////////////
void jiaoji(PNODE Head1,PNODE Head2,int a[],int& s)//交集
{
PNODE p,q,t;
p=Head1->pNext;q=Head2->pNext,t=q;
for(int i=0;i<length_list(Head1);i++)
{
q=t;
if(p->data < t->data)//Head1的每一位与Head2的第一位比较
{
p=p->pNext;
continue;
}
else
{
for(int j=0;j<length_list(Head2);j++)
{
if(p->data==q->data)
{
a[s]=p->data;
cout<<p->data<<" ";
s++;
}
q=q->pNext;
p=p->pNext;
}
}
}cout<<endl;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
void chaji(PNODE Head1,int a[],int s)
{
PNODE p;
p=Head1;
for(int i=0;i<length_list(Head1);i++)
{  p=p->pNext;
int j;
for( j=0;j<s;j++)
{
if(p->data==a[j])
{
break;
}
}
if(j==s)
{
cout<<p->data<<" ";
}
}
}