用C语言实现： 已知两个集合A,B（成员为整数），求两个集合的交集，并集，结果存 放于A中，按递增排列。

发布网友 发布时间：2022-05-27 13:57

我来回答

共1个回答

热心网友 时间：2023-10-26 18:57

#include <stdio.h>
#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;
}