用两个单链表实现集合的交并，标注一下代码内容及代码思路

Question

#include <stdio.h>

#include <stdlib.h>

#define OK 1

typedef int Status;

typedef struct LNode

{

char data;

struct LNode *next;

}LNode,*LinkList;

 

LinkList InitList()

{//建立链表

LinkList L, p,q;

char d;

L = (LinkList)malloc(sizeof(LNode));

p = L;

scanf("%c", &d);

while (d != '#')

{

    p=p->next=(LinkList)malloc(sizeof(LNode));

p->data = d;

scanf("%c", &d);

}

p->next=NULL;

q=L;

L=L->next;

free(q);

return L;

}

 

LinkList Intersection(LinkList a, LinkList b)

{//求交集

LinkList LA, LB,q;

LA =(LinkList)malloc(sizeof(LNode));

LB = LA;

while (a!=NULL)

{

    q=b;

while (q!=NULL)

{

if (q->data == a->data)

{

LB=LB->next=(LinkList)malloc(sizeof(LNode));

LB->data = a->data;

break;

}

q = q->next;

}

a = a->next;

}

LB->next=NULL;

LinkList p;

p = LA;

LA = LA->next;

free(p);

return LA;

}

 

LinkList Unionset(LinkList a, LinkList b)

{//求并集

LinkList L,q;

L=b;

while (a!=NULL)

{

while (b)

{

    q=b;

if(a->data==b->data)

break;

b=b->next;

}

if(b==NULL)

        {

            q=q->next=(LinkList)malloc(sizeof(LNode));

            q->data=a->data;

            q->next=NULL;

        }

        b=L;

a=a->next;

}

return L;

}

 

Status traverselist(LinkList a)

{//遍历链表

    while(a!=NULL)

    {

        printf("%3c",a->data);

        a=a->next;

    }

    return OK;

}

 

int main()

{

LinkList A,B,INT,UNION;

printf("请输入集合A的值（输入#结束）：");

A = InitList();

printf("请输入集合B的值（输入#结束）：");

    B = InitList();

INT=Intersection(A,B);

    printf("\n所求交集为：");

traverselist(INT);

UNION=Unionset(A,B);

printf("\n所求并集为：");

traverselist(UNION);

return 0;

}

Answer 1

交集：就是求2个链表里面相同的元素；

并集：就是合并2个链表，相同的只留一个元素。

LinkList Intersection(LinkList a, LinkList b)

{//求交集

LinkList LA, LB,q;

LA =(LinkList)malloc(sizeof(LNode));

LB = LA;

while (a!=NULL)

{
    q=b;

while (q!=NULL)

{
if (q->data == a->data) //判断2个链表的元素是否相等，

{
LB=LB->next=(LinkList)malloc(sizeof(LNode));
//相等就为交集，保存到LB
LB->data = a->data;

break;

}

q = q->next;

}

a = a->next;

}

LB->next=NULL;

LinkList p;

p = LA;

LA = LA->next;

free(p);

return LA;

}

 

LinkList Unionset(LinkList a, LinkList b)

{//求并集

LinkList L,q;

L=b;

while (a!=NULL)

{
while (b)

{
    q=b;

if(a->data==b->data)  //判断2个链表的元素是否相等，相等就表示a里面已经存在，相同的只要一个，废弃

break;

b=b->next;

}

if(b==NULL) //不相同的加到a里面

        {
            q=q->next=(LinkList)malloc(sizeof(LNode));

            q->data=a->data;

            q->next=NULL;

        }

        b=L;

a=a->next;

}

return L;

}