内蒙古工业大学信息工程学院
四、编译程序：
#include #include #define MAXSIZE 100
typedef char ElemType; typedef struct LNode
//定义单链表结点类型 {
ElemType data;
struct LNode *next; }LinkList;
LinkList *CreatlinkR(LinkList *L)
//用尾插法建立带头结点的单链表 {
LinkList *s, *r; char ch; r = (LinkList *)malloc(sizeof(LinkList));
//创建头结点
L = r; s = r; r->next = NULL; printf(\"单链表元素值为单个字符, 连续输入，$为结束字符:\"); while ((ch = getchar()) != \'$\') {
r = (LinkList *)malloc(sizeof(LinkList));
//创建新结点
r->data = ch;
r->next = NULL;
s->next = r;
s = r;
} r->next=NULL;
//终端结点
return (L); }
void Sort(LinkList *h)
//单链表元素排序 { LinkList *p=h->next,*q,*t;
if(p!=NULL) {
t=p->next;
p->next=NULL;
p=t;
while(p!=NULL)
{
t=p->next;
q=h;
第 页
内蒙古工业大学信息工程学院
while(q->next!=NULL&&q->next->data
q=q->next;
//在有序表中找插入*p的前驱结点*q
p->next=q->next;
//将*p插到*q之后
q->next=p;
p=t;
} } }
void DispList(LinkList *L)
//输出单链表L {
LinkList *p=L->next;
while(p!=NULL) {
printf(\"%c \",p->data);
p=p->next; } }
LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)
{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc; while(pa!=NULL&&pb!=NULL) {
if(pa->data
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
tc->next=s;
tc=s;
pb=pb->next;
}
else
{
第
页
//求两有序集合的并集 //复制结点
内蒙古工业大学信息工程学院
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
//重复元素只复制一个
pb=pb->next;
} } if(pb!=NULL)
//复制余下结点
pa=pb; while(pa!=NULL) {
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
} tc->next=NULL; return(Lc); }
LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的交集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL) {
pb=Lb->next;
while(pb!=NULL&&pb->data
pb=pb->next;
if(pb!=NULL&&pb->data==pa->data)
//若pa结点值在pb中
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next; }
tc->next=NULL; return(Lc);
第
页
内蒙古工业大学信息工程学院
}
LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的差集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL) {
pb=Lb->next;
while(pb!=NULL&&pb->data
pb=pb->next;
if(!(pb!=NULL&&pb->data==pa->data))
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next; } tc->next=NULL; return(Lc); }
void main() {
LinkList *La,*Lb,*Lc;
int num=0,loop,j; loop=1; La=CreatlinkR(La); Lb=CreatlinkR(Lb); Sort(La); Sort(Lb);
printf(\"有序集合A＝{ \");
DispList(La);
printf(\"}\\n\");
printf(\"有序集合B＝{ \");
DispList(Lb); printf(\"}\\n\"); while(loop) {
printf(\"请选择您要执行的操作：1.求并集
scanf(\"%d\",&j);printf(\"\\n%d\",j);
第
页
//若pa结点值不在pb中 2.求交集
3.求差集\\n\");
内蒙古工业大学信息工程学院
if(j>=1&&j
switch(j)
{
case 1: Lc=Union(La,La,Lc);
printf(\"集合A与集合B的并集C＝{ \");
DispList(Lc);
printf(\"}\\n\");
break;
case 2: Lc=InsterSect(La,Lb,Lc);
printf(\"集合A与集合B的交集C＝{ \");
DispList(Lc);
printf(\"}\\n\");
break;
case 3: Lc=Subs(La,Lb,Lc);
printf(\"集合A与集合B的差集C＝{ \");
DispList(Lc);
printf(\"}\\n\");
break;
} printf(\"0.结束
1.继续\\n\"); scanf(\"%d\",&loop); printf(\"\\n\"); } }
五、运行结果：
1．输入两个无序集合，排序后输出：
第
页
内蒙古工业大学信息工程学院
2．求集合的并集：
3．选1继续：
第
页
内蒙古工业大学信息工程学院
4．求集合的交集：
5．求集合的差集：
第
页
内蒙古工业大学信息工程学院
6．选0结束：
第
页
