[数据结构与算法] 离散数学：求集合的并、交、差、环和（c语言链表实现）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 离散数学：求集合的并、交、差、环和（c语言链表实现） -> 正文阅读

[数据结构与算法]离散数学：求集合的并、交、差、环和（c语言链表实现）

题目描述：

????????给定两个集合A，B，求其并、交、差、环和。

输入格式：

?????? 输入分为两行，第一行输入集合A,第二行输入集合B, 其中各包括若干个元素,每个元素用“，”隔开，用“{}”表示空集。元素按照字典序排列。

输出格式：

????????输出分为4行，第一行输出A∪B的集合，第二行输出A∩B的集合，第三行输出A-B的集合，第四行输出A⊕B的集合。元素按照字典序排列。

输入样例：

????????????? {a,b,c,d}

????????????? {c,d,e,f}

输出样例：
????????????? {a,b,c,d,e,f}

????????????? {c,d}

????????????? {a,b}

????????????? {a,b,e,f}

概念：

? ? ? ? 1.设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A-B分别定义如下：

????A∪B={x|x∈A\/x∈B}；

?A∩B={x|x∈A/\x∈B}；

A-B={x|x∈A/\x?B}

? ? ? ? 2.设A，B为集合，则A与B的对称差是

A⊕B=(A-B)∪(B-A)

? ? ? ? A与B的对称差还有一个等价的定义，即

A⊕B=(A∪B)-(?A∩B)

思路：

首先定义一个结构体

#define MAXSIZE 100
typedef struct Collection{
    char c;  // 表示集合中的元素
    struct Collection *next;
}*collection;

从输入的字符串中获得元素，顺便返回元素个数，获得只有元素的数组

int createmember(char *x,char *y)
{
    char *c=x;
    int num=0;
    while(*c)
    {
        if ((*c>='a'&&*c<='z')||(*c>='A'&&*c<='Z')||(*c>='0'&&*c<='9'))
        {
            *y=*c;
            y++;
            num++;
        }
        c++;
    }
    return num;
}

?题目上说输入时元素按字典序排列，但也可以自己再排序，可有可无（选择排序）

void sort(char x[MAXSIZE],int len)
{
    int min=0;
    for(int i=0;i<len;i++)
    {
        int start=i;
        min=start;
        while(start<len)
        {
            if (x[start]<x[min])
                min=start;
            start++;
        }
        char c=x[i];
        x[i]=x[min];
        x[min]=c;
    }
}

对集合链表进行初始化

collection init(collection c)
{
    c=(collection)malloc(sizeof(struct Collection));
    c->next=NULL;
    return c;
}

将输入的集合元素的字符串转换为链表

collection createinit(collection c,char z[MAXSIZE],int n)
{
    collection p=c;
    for(int i=0;i<n;i++)
    {
        collection q=(collection)malloc(sizeof(struct Collection));
        q->c=z[i];
        p->next=q;
        p=q;
    }
    p->next=NULL;
    return c;
}

计算并集

collection bing(collection b,char x[MAXSIZE],char y[MAXSIZE])
{
    int flag=0;  // 判断元素是否相等的标志
    createinit(b,x,n1);
    collection p1=b->next;
    for(int i=0;i<n2;i++)
    {
        while(p1!=NULL)
        {
            if (y[i]==p1->c)
            {
                flag=1;
                break;  // A与B的元素要是相等就退出，遍历下一个A集合的元素
            }
            p1=p1->next;
        }
        p1=b->next;
        if (flag==0)
        {
            collection q=(collection)malloc(sizeof(struct Collection));
            q->c=y[i];
            if (p1==NULL)  // A集合有可能是空集
            {
                b->next=q;
                q->next=NULL;
            }
            else
            {
                while (p1!=NULL)
                {
                    if (q->c<p1->c)  // B集合要插入的元素比A集合所有的元素都小
                    {
                        q->next=p1;
                        b->next=q;
                        break;
                    }
                    else if (q->c>=p1->c)
                    {
                        if (p1->next!=NULL&&q->c<p1->next->c)  // 要插入的位置在中间
                        {
                            q->next=p1->next;
                            p1->next=q;
                            break;
                        }
                        else if (q->c>=p1->c&&p1->next==NULL)  // 要插入的位置在最后
                        {
                            p1->next=q;
                            p1=q;
                            p1->next=NULL;
                        }
                    }
                    p1=p1->next;
                }
            }
        }
        flag=0;  // 重置存在标志
    }
    return b;
}

计算交集

collection jiao(collection j,char x[MAXSIZE],char y[MAXSIZE])
{
    collection j1=init(j1),j2=init(j2);
    createinit(j1,x,n1);
    createinit(j2,y,n2);
    collection p=j,p1=j1->next,p2=j2->next;
    while (p1!=NULL)
    {
        while(p2!=NULL)
        {
            if (p1->c==p2->c)  // 要是元素相等就加入集合
            {
                collection q=(collection)malloc(sizeof(struct Collection));
                q->c=p1->c;
                p->next=q;
                p=q;
            }
            p2=p2->next;
        }
        p1=p1->next;
        p2=j2->next;
    }
    p->next=NULL;
    clear(j1);
    clear(j2);
    return j;
}

计算相对补集

collection cha(collection c,char x[MAXSIZE],char y[MAXSIZE])
{
    int flag=0;  // 判断元素是否相等的标志
    collection c1=init(c1),c2=init(c2);
    createinit(c1,x,n1);
    createinit(c2,y,n2);
    collection p=c,p1=c1->next,p2=c2->next;
    while (p1!=NULL)
    {
        while(p2!=NULL)
        {
            if (p1->c==p2->c)
            {
                flag=1;
                break;
            }
            p2=p2->next;
        }
        if (flag==0)  // A集合中存在而B集合中不存在
        {
            collection q=(collection)malloc(sizeof(struct Collection));
            q->c=p1->c;
            p->next=q;
            p=q;
        }
        p1=p1->next;
        p2=c2->next;
        flag=0;  // 重置元素相等标志
    }
    p->next=NULL;
    clear(c1);
    clear(c2);
    return c;
}

计算对称差（利用第二个等价定义）

collection huan(collection h,collection j,char x[MAXSIZE],char y[MAXSIZE])
{
    collection h1=init(h1),h2=j->next,p,q,r;
    h1=bing(h1,x,y);
    p=h1;
    q=h1->next;
    while(h2!=NULL)
    {
        while(q!=NULL)
        {
            if (h2->c==q->c)
            {
                r=q;
                q=q->next;
                p->next=q;
                free(r);
                break;
            }
            else
            {
                q=q->next;
                p=p->next;
            }
        }
        h2=h2->next;
    }
    h=h1;
    return h;
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
int n1=0,n2=0;
typedef struct Collection{char c;struct Collection *next;}*collection;
void clear(collection c)
{
    collection p=c->next,q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;
        free(q);
    }
    c->next=NULL;
}
void sort(char x[MAXSIZE],int len)
{
    int min=0;
    for(int i=0;i<len;i++)
    {
        int start=i;
        min=start;
        while(start<len)
        {
            if (x[start]<x[min])
                min=start;
            start++;
        }
        char c=x[i];
        x[i]=x[min];
        x[min]=c;
    }
}
collection init(collection c)
{
    c=(collection)malloc(sizeof(struct Collection));
    c->next=NULL;
    return c;
}
int createmember(char *x,char *y)
{
    char *c=x;
    int num=0;
    while(*c)
    {
        if ((*c>='a'&&*c<='z')||(*c>='A'&&*c<='Z')||(*c>='0'&&*c<='9'))
        {
            *y=*c;
            y++;
            num++;
        }
        c++;
    }
    return num;
}
collection createinit(collection c,char z[MAXSIZE],int n)
{
    collection p=c;
    for(int i=0;i<n;i++)
    {
        collection q=(collection)malloc(sizeof(struct Collection));
        q->c=z[i];
        p->next=q;
        p=q;
    }
    p->next=NULL;
    return c;
}
collection bing(collection b,char x[MAXSIZE],char y[MAXSIZE])
{
    int flag=0;
    createinit(b,x,n1);
    collection p1=b->next;
    for(int i=0;i<n2;i++)
    {
        while(p1!=NULL)
        {
            if (y[i]==p1->c)
            {
                flag=1;
                break;
            }
            p1=p1->next;
        }
        p1=b->next;
        if (flag==0)
        {
            collection q=(collection)malloc(sizeof(struct Collection));
            q->c=y[i];
            if (p1==NULL)
            {
                b->next=q;
                q->next=NULL;
            }
            else
            {
                while (p1!=NULL)
                {
                    if (q->c<p1->c)
                    {
                        q->next=p1;
                        b->next=q;
                        break;
                    }
                    else if (q->c>=p1->c)
                    {
                        if (p1->next!=NULL&&q->c<p1->next->c)
                        {
                            q->next=p1->next;
                            p1->next=q;
                            break;
                        }
                        else if (q->c>=p1->c&&p1->next==NULL)
                        {
                            p1->next=q;
                            p1=q;
                            p1->next=NULL;
                        }
                    }
                    p1=p1->next;
                }
            }
        }
        flag=0;
    }
    return b;
}
collection jiao(collection j,char x[MAXSIZE],char y[MAXSIZE])
{
    collection j1=init(j1),j2=init(j2);
    createinit(j1,x,n1);
    createinit(j2,y,n2);
    collection p=j,p1=j1->next,p2=j2->next;
    while (p1!=NULL)
    {
        while(p2!=NULL)
        {
            if (p1->c==p2->c)
            {
                collection q=(collection)malloc(sizeof(struct Collection));
                q->c=p1->c;
                p->next=q;
                p=q;
            }
            p2=p2->next;
        }
        p1=p1->next;
        p2=j2->next;
    }
    p->next=NULL;
    clear(j1);
    clear(j2);
    return j;
}
collection cha(collection c,char x[MAXSIZE],char y[MAXSIZE])
{
    int flag=0;
    collection c1=init(c1),c2=init(c2);
    createinit(c1,x,n1);
    createinit(c2,y,n2);
    collection p=c,p1=c1->next,p2=c2->next;
    while (p1!=NULL)
    {
        while(p2!=NULL)
        {
            if (p1->c==p2->c)
            {
                flag=1;
                break;
            }
            p2=p2->next;
        }
        if (flag==0)
        {
            collection q=(collection)malloc(sizeof(struct Collection));
            q->c=p1->c;
            p->next=q;
            p=q;
        }
        p1=p1->next;
        p2=c2->next;
        flag=0;
    }
    p->next=NULL;
    clear(c1);
    clear(c2);
    return c;
}
collection huan(collection h,collection j,char x[MAXSIZE],char y[MAXSIZE])
{
    collection h1=init(h1),h2=j->next,p,q,r;
    h1=bing(h1,x,y);
    p=h1;
    q=h1->next;
    while(h2!=NULL)
    {
        while(q!=NULL)
        {
            if (h2->c==q->c)
            {
                r=q;
                q=q->next;
                p->next=q;
                free(r);
                break;
            }
            else
            {
                q=q->next;
                p=p->next;
            }
        }
        h2=h2->next;
    }
    h=h1;
    return h;
}
void output(collection C)
{
    collection head=C->next;
    printf("{");
    while(head!=NULL)
    {
        if (head->next==NULL)
            printf("%c",head->c);
        else
            printf("%c,",head->c);
        head=head->next;
    }
    printf("}");
}
int main()
{
    char a[MAXSIZE],b[MAXSIZE],a1[MAXSIZE],b1[MAXSIZE];
    collection B=init(B),J=init(J),C=init(C),H=init(H);
    scanf("%s",a);
    scanf("%s",b);
    n1=createmember(a,a1);
    n2=createmember(b,b1);
    sort(a1,n1);
    sort(b1,n2);
    B=bing(B,a1,b1);
    J=jiao(J,a1,b1);
    C=cha(C,a1,b1);
    H=huan(H,J,a1,b1);
    output(B);
    printf("\n");
    output(J);
    printf("\n");
    output(C);
    printf("\n");
    output(H);
    clear(B);
    clear(J);
    clear(C);
    clear(H);
    return 0;
}