Question

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

Answer 1

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