#include?<malloc.h>
typedef?struct?node?{
int?num;
struct?node?*next;
}AGG;
AGG?*CreateList()?{?//?創建單循環鏈表，返回鏈表頭
AGG?*head,*p;
int?i,n;
printf("結點個數n?=?");
scanf("%d",&n);
head?=?p?=?(AGG?*)malloc(sizeof(AGG));?//?專用頭結點
head->num?=?0;
printf("輸入?%d?整數(空格隔開):\n",n);
for(i?=?0;?i?<?n;?++i)?{
p->next?=?(AGG?*)malloc(sizeof(AGG));
scanf("%d",&p->next->num);
p?=?p->next;
}
p->next?=?head;
return?head;
}
void?RiseSort(AGG?*head)?{?//?上升排序
AGG?*p,*s,*pt;?
p?=?head;
s?=?p->next;
while(p->next?!=?head)?{
while(s->next?!=?head)?{
if(p->next->num?>?s->next->num)?{
pt?=?p->next;
p->next?=?s->next;
s->next?=?p->next->next;
p->next->next?=?pt;
}
else?s?=?s->next;
}
p?=?p->next;
s?=?p->next;
}
}
void?Simplification(AGG?*head)?{?//?去除相同的集合元素
AGG?*p,*q,*s;
p?=?head->next;
q?=?p->next;
while(q?!=?head)?{
if(p->num?==?q->num)?{
p->next?=?q->next;
s?=?q;
q?=?q->next;
delete?s;
}
else?{
p?=?p->next;
q?=?q->next;
}
}
}
AGG?*CreateAgg()?{
AGG?*head;
head?=?CreateList();
RiseSort(head);;
Simplification(head);
return?head;
}
void?InsertNode(AGG?*head,int?num)?{
AGG?*t,*p?=?head;
while(p->next?!=?head)?{
if(p->next->num?==?num)?return;?
if(p->next->num?<?num)?p?=?p->next;
else?{
t?=?(AGG?*)malloc(sizeof(AGG));
t->num?=?num;
t->next?=?p->next;
p->next?=?t;
return;
}
}
t?=(AGG?*)malloc(sizeof(AGG));
t->num?=?num;
p->next?=?t;?
t->next?=?head;?//?插入在鏈表尾的處理
}
AGG?*MergeAgg(AGG?*A,AGG?*B)?{?//?A∪B
AGG?*head,*pa,*pb,*pc,*qc;
head?=?pc?=?(AGG?*)malloc(sizeof(AGG));
pa?=?A->next;
while(pa?!=?A)?{
qc?=?(AGG?*)malloc(sizeof(AGG));
qc->num?=?pa->num;
pc->next?=?qc;
pc?=?qc;
pa?=?pa->next;
}
pc->next?=?head;
pb?=?B->next;
while(pb?!=?B)?{
InsertNode(head,pb->num);
pb?=?pb->next;
}
return?head;
}
AGG?*MutualAgg(AGG?*A,AGG?*B)?{?//?A∩B
AGG?*C,*pa,*pb,*pc,*qc;
C?=?pc?=?(AGG?*)malloc(sizeof(AGG));
pc->num?=?0;
pa?=?A->next;
pb?=?B;
while(pa?!=?A)?{
pb?=?B->next;
while(pb?!=?B)?{
if(pb->num?==?pa->num)?{
qc?=?(AGG?*)malloc(sizeof(AGG));
qc->num?=?pb->num;
pc->next?=?qc;
pc?=?qc;
}
pb?=?pb->next;
}
pa?=?pa->next;
}
pc->next?=?C;
return?C;
}
AGG?*DifferAgg(AGG?*A,AGG?*B)?{?//?返回A、B的差集?A－B
AGG?*head,*p,*q,*r;
int?tag;
head?=?r?=?(AGG?*)malloc(sizeof(AGG));
for(p?=?A->next;?p?!=?A;?p?=?p->next)?{
tag?=?1;
for(q?=?B->next;?q?!=?B?&&?tag;?q?=?q->next)
tag?=?p->num?!=?q->num;
if(tag)?{
r->next?=?(AGG?*)malloc(sizeof(AGG));
r?=?r->next;
r->num?=?p->num;
}
}
for(p?=?B->next;?p?!=?B;?p?=?p->next)?{
tag?=?1;
for(q?=?A->next;?q?!=?A?&&?tag;?q?=?q->next)
tag?=?p->num?!=?q->num;
if(tag)?{
r->next?=?(AGG?*)malloc(sizeof(AGG));
r?=?r->next;
r->num?=?p->num;
}
}
r->next?=?head;
RiseSort(head);
return?head;
}
void?PrintList(AGG?*head)?{
AGG?*p?=?head->next;
short?counter?=?0;
while(p?!=?head)?{
if(counter?&&?counter%10?==?0)?printf("\n");
printf("%5d",p->num);
counter++;
p?=?p->next;
}
if(counter?%?10)?printf("\n");
}
void?freeheap(AGG?*head)?{
AGG?*p,*q;
p?=?head;
q?=?p->next;
while(q?!=?head)?{
p?=?q;
q?=?p->next;
free(p);
}
free(head);
}
int?main()?{
AGG?*A,*B,*C,*D,*E;
printf("創建集合?A:\n");
A?=?CreateAgg();
printf("創建集合?B:\n");
B?=?CreateAgg();
printf("集合A的元素有:\n");
PrintList(A);
printf("集合B的元素有:\n");
PrintList(B);
C?=?MutualAgg(A,B);
printf("交集?C?=?A∩B:\n");
PrintList(C);
printf("並集?D?=?A∪B?:\n");
D?=?MergeAgg(A,B);
PrintList(D);
printf("差集?D?=?A－B?:\n");
E?=?DifferAgg(A,B);
PrintList(E);
freeheap(A);
freeheap(B);
freeheap(C);
freeheap(D);
freeheap(E);
printf("\n\n");
return?0;
}