85问答库 > 求集合的交集并集。。用C语言数组实现。要求效率高点的。。最好有注释。。谢谢啦。。超高分。。

求集合的交集并集。。用C语言数组实现。要求效率高点的。。最好有注释。。谢谢啦。。超高分。。

2025-03-04 22:38:41

推荐回答（1个）

回答1：

#include 
#include 

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("%d ",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;
}

植物的组织培养技术的原理是什么？

行为主义心理学派的代表人物带英文名字

宽带连不上错误代码678是什么意思

问一部电影，主角是一公司的总裁，遇到一个黑人乞丐；一天一觉醒来后，发现自己成了老百姓，而乞丐成了总

我想问下，，我嘴唇上总是起白皮，就是一层皮像是脱落。。还有，我常常坐在开暖气的房里，会不会和这个有

我家泰迪剪毛超级凶怎么办

西安哪有买新疆炒米粉的材料！

天书奇谈换帮会时帮贡会清零么？

DELL服务器怎么安装网卡驱动跟其他驱动（Power Edge R510 ）