离散数学实验二c语言(输出关系矩阵，输出矩阵性质，输出自反闭包，对称闭包，传递闭包，判断矩阵是否为等价关系，相容关系，偏序关系)

🕗 发布于 2024-10-16 10:00 c语言 矩阵算法离散数学大作业

离散数学实验二

一、算法描述，算法思想

（一）相关数据结构

typedef struct Set *S; //存放集合
struct Set
{
    int size; //集合的元素个数
    char *A;   //存放该集合的元素
};

Set存放有限集合A，该集合的元素个数为size，size可以用来判断该集合是否为空集，然后集合中的元素就放在A数组里。

typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
    int x, y;
};

Confirm存放一个序偶<x, y>。

typedef struct Relation *R; //存放关系矩阵
struct Relation
{
    int n, size;   // n行 n列矩阵，序偶个数为size
    int r[10][10]; //关系矩阵
    C c;           //存放该关系的序偶
};

Relation存放集合A的关系，r为一个n行，n列的关系矩阵，size为其中的序偶数，c即存放该关系的所有序偶。

int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反，flagfz判断是否为反自反，
// flagd判断是否为对称，flagfd判断是否为反对称，flagc判断是否为传递

设置全局变量，方便判断矩阵关系。

（二）相关算法实现

1、输出关系矩阵R

void PrintRelation(R re) //打印关系矩阵
{
    printf("关系矩阵如下：\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
            printf("%d ", re->r[i][j]);
        printf("\n");
    }
    printf("\n");
}

用户输入的为一个关系矩阵，只要将其存储下，然后直接输出即可，注意换行。

2、输出R具有的性质

void PrintCharacter(S s, R re) //判断该矩阵的性质

if (s->size == 0) //空集，关系具有所有性质
    {
        printf("该关系具有以下性质：\n");
        printf("自反性\n");
        printf("反自反性\n");
        printf("对称性\n");
        printf("反对称性\n");
        printf("传递性\n");
        return;
    }

（1）首先是判断该集合是否为空，如果集合为空集，则具有所有的性质。

for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j && !re->r[i][j]) //不可能为自反关系
                flagz = 0;
            if (i == j && re->r[i][j]) //不可能为反自反关系
                flagfz = 0;
            if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
                flagd = 0;
            if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
                flagfd = 0;
        }
    }

（2）确定该集合不为空后，接下来先根据矩阵来判断自反性，反自反性，对称性，反对称性。

如果出现横纵坐标相同的点，但是其不为1，说明该集合存在a属于集合s，但不具有<a, a>序偶，则该矩阵不可能具有自反关系，将flagz = 0;

如果出现横纵坐标相同的点，但是其为1，说明该集合存在a属于该集合，且有<a, a>序偶，则该矩阵不可能具有反自反关系，将flagfz = 0;

如果出现横纵坐标不相同，且相反的两点，但是其为1，说明该集合存在a,b属于该集合，且有<a, b>,<b,a>序偶，则该矩阵不可能具有反对称关系，将flagfd = 0;

如果出现横纵坐标不相同，且相反的两点，但是其只有一个为1，说明该集合存在a,b属于该集合，且有<a, b>,没有<b,a>序偶，则该矩阵不可能具有对称关系，将flagd = 0;

    for (int i = 1; i <= re->size; i++) //判断是否具有传递性
    {
        if (!flagc)
        break;
        int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
        if (x == y)
            continue;
        for (int j = 0; j < n; j++) //找<y, j>
        {
            if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
            {
                flagc = 0;
                break;
            }
        }
    }

（3）接下来是根据矩阵中为1的点，即该集合所具有的序偶来判断是否具有传递关系。

若存在<x, y>,我们去找<y, j>,看是否存在<x, j>，如果不存在则不具有传递关系，flagc = 0。

（4）最后将所有关系输出即可。

3、输出R的自反闭包，对称闭包，传递闭包

void PrintBibao(R re) //计算自反闭包，对称闭包，传递闭包矩阵

    //自反闭包
    int n = re->n;
    R tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
        tmp->r[i][i] = 1;
    printf("自反闭包矩阵：\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

（1）计算自反闭包，首先将原矩阵复制到tmp中，将所有横纵坐标相同的点都该为1，即为自反闭包。

    //对称闭包
    tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && tmp->r[i][j])
            {
                tmp->r[j][i] = 1;
            }
        }
    }
    printf("对称闭包矩阵：\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

（2）计算对称闭包，首先将原矩阵复制到tmp中，将横纵坐标不同的的，原矩阵中存在的为1的点，将其的对称点也改为1，即为对称闭包。

    //传递闭包
    tmp = CopyRelation(re);
    R ans = InitRelationTmp(n);
    AddRelation(ans, re);

    for (int i = 0; i < n-1; i++)
    {
        tmp = Multiply(tmp, re); //最多乘n次
        AddRelation(ans, tmp);
    }
    printf("传递闭包矩阵：\n");
    PrintRelation(ans);
    DestoryRelation(tmp);
    free(ans);

（3）计算传递闭包，首先将原矩阵复制到tmp中，将tmp与原矩阵乘矩阵的行(列)数次，将每次计算的大于1的数改为1，每次将矩阵相加，返回即可。

4、判断R是否为等价关系，相容关系，偏序关系

void PanRelation(R re) //判断矩阵的关系
{
    printf("具有的关系为：\n");
    if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反，对称，传递则为等价关系
        printf("等价关系\n");
    if (flagz == 1 && flagd == 1) //若为自反，对称则为相容关系
        printf("相容关系\n");
    if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反，反对称，传递为偏序关系
        printf("偏序关系\n");
}

（1）等价关系：若R具有自反性，对称性，传递性。

（2）相容关系：若R具有自反性，对称性。

（3）偏序关系：若R具有自反性，反对称性，传递性。

（三）流程图

main()函数

void PrintRelation(R re) 打印关系矩阵

void PrintCharacter(S s, R re) 判断该关系矩阵的性质

void PrintBibao(R re) 计算自反闭包，对称闭包，传递闭包矩阵

void PanRelation(R re) 判断矩阵的关系

（四）程序运行截图与样例说明

输入：元素个数、集合的每个元素（用单个字符表示）、该集合的关系矩阵。

输出：关系矩阵、关系矩阵性质、自反闭包、对称闭包、传递闭包矩阵、关系矩阵的关系。

分析：该关系矩阵的序偶为<1,2>,<2,1>,<2,3>,<3,4>。

可以看出该关系矩阵不具有自反性，对称性，反对称性，传递性。

具有反自反性。

且计算的自反闭包，对称闭包，传递闭包与答案相同。

判断的关系也正确。

（五）代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
    int x, y;
};
typedef struct Relation *R; //存放关系矩阵
struct Relation
{
    int n, size;   // n行 n列矩阵，序偶个数为size
    int r[10][10]; //关系矩阵
    C c;           //存放该关系的序偶
};
typedef struct Set *S; //存放集合
struct Set
{
    int size; //集合的元素个数
    char *A;   //存放该集合的元素
};
int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反，flagfz判断是否为反自反，
// flagd判断是否为对称，flagfd判断是否为反对称，flagc判断是否为传递

S InitSet(int size) //创建集合
{
    S s = (S)malloc(sizeof(struct Set));
    s->A = (char *)malloc(sizeof(char) * size);
    s->size = size;

    printf("注意：集合的每个元素用单个字符来表示\n");
    for (int i = 0; i < size; i++)
        scanf("%d", &s->A[i]);
    return s;
}
R InitRelation(int n) //创建关系矩阵
{
    int now = 0;
    R re = (R)malloc(sizeof(struct Relation));
    re->n = n;
    re->c = (C)malloc(sizeof(struct Confirm) * n);
    
    printf("请输入该集合的关系矩阵(n*n)：\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
        {
            scanf("%d", &re->r[i][j]);
            if (re->r[i][j])
            {
                re->c[++now].x = i;
                re->c[now].y = j;
            }
        }
    }
    re->size = now;
    return re;
}
R InitRelationTmp(int n)
{
    R tmp = (R)malloc(sizeof(struct Relation));
    tmp->n = n;
    for (int i=0; i<tmp->n; i++)
    {
        for (int j=0; j<tmp->n; j++)
        tmp->r[i][j] = 0;
    }
    return tmp;
}

void DestorySet(S s) //释放集合内存
{
    free(s->A);
    free(s);
}
void DestoryRelation(R re) //释放关系矩阵内存
{
    free(re->c);
    free(re);
}

void PrintRelation(R re) //打印关系矩阵
{
    printf("关系矩阵如下：\n");
    for (int i = 0; i < re->n; i++)
    {
        for (int j = 0; j < re->n; j++)
            printf("%d ", re->r[i][j]);
        printf("\n");
    }
    printf("\n");
}
R Multiply(R re, R re2) //计算两矩阵相乘，且将相乘后的大于1的数改为1
{
    int n = re->n, tmp = 0, i, j;
    R ans = InitRelationTmp(n);
    for (i = 0; i < n; i++) //每一行
    {
        for (j = 0; j < n; j++) //该行的列
        {
            tmp = 0;
            for (int k = 0; k < n; k++)
            {
                tmp += re->r[i][k] * re2->r[k][j];
            }
            if (tmp >= 1)
                {
                    ans->r[i][j] = 1;
                }
        }
    }
    return ans; //返回得出的矩阵
}
void AddRelation(R re1, R re2)
{
    int n = re1->n;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            re1->r[i][j] += re2->r[i][j];
            if (re1->r[i][j]>1)
            re1->r[i][j] = 1;
        }
    }
}

void PrintCharacter(S s, R re) //判断该矩阵的性质
{
    int n = re->n;
    if (s->size == 0) //空集，关系具有所有性质
    {
        printf("该关系具有以下性质：\n");
        printf("自反性\n");
        printf("反自反性\n");
        printf("对称性\n");
        printf("反对称性\n");
        printf("传递性\n");
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j && !re->r[i][j]) //不可能为自反关系
                flagz = 0;
            if (i == j && re->r[i][j]) //不可能为反自反关系
                flagfz = 0;
            if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
                flagd = 0;
            if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
                flagfd = 0;
        }
    }
    for (int i = 1; i <= re->size; i++) //判断是否具有传递性
    {
        if (!flagc)
        break;
        int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
        if (x == y)
            continue;
        for (int j = 0; j < n; j++) //找<y, j>
        {
            if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
            {
                flagc = 0;
                break;
            }
        }
    }
    //输出性质
    printf("该关系具有以下性质：\n");
    if (flagz == 1)
        printf("自反性\n");

    if (flagfz == 1)
        printf("反自反性\n");

    if (flagd == 1)
        printf("对称性\n");

    if (flagfd == 1)
        printf("反对称性\n");

    if (flagc == 1)
        printf("传递性\n");

    if (!flagz&&!flagfz&&!flagd&&!flagfd&&!flagc)
    printf("该关系矩阵不具有自反、反自反、对称、反对称、传递性\n");
}
R CopyRelation(R re) //复制关系矩阵，方便计算
{
    R tmp = (R)malloc(sizeof(struct Relation));
    tmp->n = re->n;
    tmp->size = re->size;
    tmp->c = (C)malloc(sizeof(struct Confirm) * tmp->size);
    for (int i = 0; i < tmp->n; i++)
    {
        for (int j = 0; j < tmp->n; j++)
            tmp->r[i][j] = re->r[i][j];
    }
    for (int i = 1; i <= tmp->size; i++)
    {
        tmp->c[i].x = re->c[i].x;
        tmp->c[i].y = re->c[i].y;
    }
    return tmp; //返回该复制的矩阵
}
void PrintBibao(R re) //计算自反闭包，对称闭包，传递闭包矩阵
{
    //自反闭包
    int n = re->n;
    R tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
        tmp->r[i][i] = 1;
    printf("自反闭包矩阵：\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

    //对称闭包
    tmp = CopyRelation(re);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && tmp->r[i][j])
            {
                tmp->r[j][i] = 1;
            }
        }
    }
    printf("对称闭包矩阵：\n");
    PrintRelation(tmp);
    DestoryRelation(tmp);

    //传递闭包
    tmp = CopyRelation(re);
    R ans = InitRelationTmp(n);
    AddRelation(ans, re);

    for (int i = 0; i < n-1; i++)
    {
        tmp = Multiply(tmp, re); //最多乘n次
        AddRelation(ans, tmp);
    }
    printf("传递闭包矩阵：\n");
    PrintRelation(ans);
    DestoryRelation(tmp);
    free(ans);
}
void PanRelation(R re) //判断矩阵的关系
{
    int flag = 0;
    printf("具有的关系为：\n");
    if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反，对称，传递则为等价关系
    {
        printf("等价关系\n");
        flag = 1;
    }
    if (flagz == 1 && flagd == 1) //若为自反，对称则为相容关系
    {
        printf("相容关系\n");
        flag = 1;
    }
    if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反，反对称，传递为偏序关系
    {
        printf("偏序关系\n");
        flag = 1;
    }
    if (!flag)
    printf("该关系矩阵不具有等价、相容、偏序关系\n");
}

int main()
{
    int size;
    printf("请输入该集合的元素个数：\n");
    scanf("%d", &size);

    S s = InitSet(size);       //输入集合
    R re = InitRelation(size); //输入关系矩阵

    PrintRelation(re);     //打印关系矩阵
    PrintCharacter(s, re); //打印矩阵性质
    PrintBibao(re);        //打印闭包矩阵
    PanRelation(re);       //判断矩阵的关系

    DestorySet(s); //释放内存
    DestoryRelation(re);

    return 0;
}

原文地址：https://blog.csdn.net/m0_60531106/article/details/142938336

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：科研绘图系列：R语言散点相关系数图（scatter plot）
下一篇：C语言题目练习3

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

离散数学实验二c语言(输出关系矩阵，输出矩阵性质，输出自反闭包，对称闭包，传递闭包，判断矩阵是否为等价关系，相容关系，偏序关系)