//?下面的程序代碼用於集合的交、並運算，請仔細閱讀。
#include?<iostream>
#include?<iomanip>
#include?<time.h>
using?namespace?std;
typedef?struct?link?{
short?num;
struct?link?*next;
}AGG;
AGG?*CreateList(int?n)?{?//?創建結點數為n的鏈表，返回鏈表頭
AGG?*head,*p,*q;
head?=?p?=?new?AGG;
head->num?=?0;
for(short?i?=?0;i?<?n;i++)?{
q?=?new?AGG;
q->num?=?(unsigned)rand()?%?n?+?n/2;
p->next?=?q;
p?=?q;
}
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(int?n)?{
AGG?*head;
head?=?CreateList(n);
RiseSort(head);;
Simplification(head);
return?head;
}
void?InsertNode(AGG?*head,short?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?=?new?AGG[1];
t->num?=?num;
t->next?=?p->next;
p->next?=?t;
return;
}
}
t?=?new?AGG[1];
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?=?new?AGG;
pa?=?A->next;
while(pa?!=?A)?{
qc?=?new?AGG[1];
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?=?new?AGG;
pc->num?=?0;
pa?=?A->next;
pb?=?B;
while(pa?!=?A)?{
pb?=?B->next;
while(pb?!=?B)?{
if(pb->num?==?pa->num)?{
qc?=?new?AGG;
qc->num?=?pb->num;
pc->next?=?qc;
pc?=?qc;
}
pb?=?pb->next;
}
pa?=?pa->next;
}
pc->next?=?C;
return?C;
}
void?PrintList(AGG?*head)?{
AGG?*p?=?head->next;
short?counter?=?0;
while(p?!=?head)?{
if(counter%10?==?0)?cout?<<?endl;
cout<<setw(5)<<?p->num;
counter++;
p?=?p->next;
}
cout?<<?endl;
}
void?freeheap(AGG?*head)?{
AGG?*p,*q;
p?=?head;
q?=?p->next;
while(q?!=?head)?{
p?=?q;
q?=?p->next;
delete?p;
}
free(head);
}
int?main()?{
AGG?*A,*B,*C,*D;
srand(time(NULL));
A?=?CreateAgg(50);
cout?<<?"集合A的元素有:";
PrintList(A);
B?=?CreateAgg(50);
cout?<<?endl?<<?endl?<<?"集合B的元素有:";
PrintList(B);
C?=?MutualAgg(A,B);
cout?<<?endl?<<?endl?<<?"C?=?A∩B:"?<<?endl;
PrintList(C);
cout?<<?endl?<<?endl?<<?"D?=?A∪B?:?"?<<?endl;
D?=?MergeAgg(A,B);
PrintList(D);
freeheap(A);
freeheap(B);
freeheap(C);
freeheap(D);
printf("\n\n");
return?0;
}