Question

用线性表La和Lb分别表示集合A和集合B，现要求一个新的集合A＝AUB。

如图，可是图中好像不完整，里面的j没有定义过，老师让我们写如题这个程序，可是我不会，请帮我把程序写出来好么？很急。

Answer 1

#include <stdio.h>
#include <stdlib.h>

typedef int SElemType;

typedef struct set {
	SElemType data;
	struct set *next;
}*Set,*pSet;

pSet GetNewNode() {
	pSet newnode = (pSet)malloc(sizeof(struct set));
	if(newnode == NULL) {
		printf("内存耗尽。\n");
		exit(1);
	}
	return newnode;
}

Set InitSet() { // 初始化
	pSet S = GetNewNode();
	S->data = 0;
	S->next = NULL;
	return S;
}

Set CreateSet(SElemType a[],int n) { // 用数组创建集合
	int i;
	pSet S,p;
	S = p = InitSet();
	for(i = 0; i < n; ++i) {
		p->next = GetNewNode();
		p->next->data = a[i];
		p = p->next;
	}
	p->next = NULL;
	return S;
}

void CreateSet2(Set S) { // 用键盘输入数据创建集合
	SElemType data;
	pSet p = S;
	while(scanf("%d",&data) == 1) { // 键入任意字母(串)结束创建
		p->next = GetNewNode();
		p->next->data = data;
		p = p->next;
	}
	p->next = NULL;
}

void SortSet(Set S) { // 排序(增)
	pSet p,q,pt;
	for(p = S; p->next; p = p->next) {
		q = p->next;
		while(q->next) {
			if(p->next->data > q->next->data) {
				pt = p->next;
				p->next = q->next;
				q->next = p->next->next;
				p->next->next = pt;
			}
			else q = q->next;
		}
	}
}

void ElemSwaraj(Set S) { // 元素单一化:集合中不能含有相同的元素
	pSet p,q,pt;
	for(p = S; p->next; p = p->next) {
		q = p->next;
		while(q->next) {
			if(p->next->data == q->next->data) {
				pt = q->next;
				q->next = pt->next;
				free(pt);
			}
			else q = q->next;
		}
	}
}

void ShowSet(Set S) {
	pSet p;
	if(S == NULL || S->next == NULL) {
		printf("{\"空\"}\n");
		return;
	}
	printf("{%d",S->next->data);
	for(p = S->next->next; p; p = p->next)
		printf(",%d",p->data);
	printf("}\n");
}

Set CopySet(Set S) { // 集合复制
	pSet T,p,q;
	T = q = InitSet();
	p = S->next;
	while(p) {
		q->next = GetNewNode();
		q->next->data = p->data;
		p = p->next;
		q = q->next;
	}
	q->next = NULL;
	return T;
}

void InsertSet(Set S,SElemType x) { // 插入元素x到集合中(有序)
	pSet p,q;
	q = GetNewNode();
	q->data = x;
	if(S->next == NULL) {
		S->next = q;
		q->next = NULL;
		return;
	}
	for(p = S; p->next; p = p->next) {
		if(p->next->data == x) return;
		if(p->next->data > x) {
			q->next = p->next;
			p->next = q;
			return;
		}
	}
	p->next = q;
	q->next = NULL;
}

Set MergeSet(Set A, Set B) { // 返回A和B的并集:A∪B
	Set p,C = CopySet(A);
	for(p = B->next; p; p = p->next)
		InsertSet(C,p->data);
	return C;
}

Set MutualSet(Set A, Set B) { // 返回A和B的交集:A∩B
	pSet C,p,q;
	C = InitSet();
	for(p = A->next; p; p = p->next) {
		for(q = B->next; q; q = q->next) {
			if(p->data == q->data)
				InsertSet(C,p->data);
		}
	}
	return C;
}

int LengthSet(Set S) {
	pSet p = S->next;
	int len = 0;
	if(S == NULL || S->next == NULL) return 0;
	while(p) {
		p = p->next;
		++len;
	}
	return len;
}

void FreeSet(Set S) { // 释放动态堆内存
	pSet q,p = S;
	while(p) {
		q = p;
		p = q->next;
		free(q);
	}
}
	
int main() {
	Set a[4]; 
	SElemType s[] = {3,6,7,2,3,8};
	SElemType t[] = {3,6,2,9,4,7};
	int i,n = sizeof(s)/sizeof(s[0]);
	int len,m = sizeof(t)/sizeof(t[0]);
	a[0] = CreateSet(s,n);
	SortSet(a[0]);
	a[1] = CreateSet(t,m);
	SortSet(a[1]);
	ElemSwaraj(a[0]);
	ElemSwaraj(a[1]);
	a[2] = MergeSet(a[0], a[1]);
	a[3] = MutualSet(a[0], a[1]);
	for(i = 0; i < 4; ++i) {
		len = LengthSet(a[i]);
		printf("集合a[%d](%d):",i,len);
		ShowSet(a[i]);
		FreeSet(a[i]);
	}
	return 0;
}