C++题目：定义集合的ADT并实现之（包括集合的交,并,判定是否为空,求长度等等运算）.请大神给出设计思路,

Question

C++题目：定义集合的 ADT 并实现之（包括集合的交,并,判定是否为空,求长度等等运算）.
请大神给出设计思路,

Answer 1

#include 
#include 

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;
}

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]);
}
return 0;
}