这个程序主要实现对一个集合上的二元关系的自反性、对称性、传递性、反自反性、反对称性的判定。
存储结构是用一个由动态分配的二维数组实现的n*n的邻接矩阵表示的有向图mGraph存储集合上的二元关系。
貌似听到老师还额外要求实现关系的闭包运算（自反闭包、对称闭包、对称闭包），自反闭包就是把a[i][i]置为1，对称闭包就是if(a[i][j]==1) a[j][i]=1,传递闭包依次类推。so easy,so lazy
代码如下
NO COPY
NO CHEATING
THANKS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
#define ERROR 0
#define OK 1
typedef struct//图的自定义
{
ElemType **a;//邻接矩阵
int n;//图的当前顶点数
int e;//图的当前边数
ElemType noEdge;//两顶点间无边时的值
}mGraph;
Status Init(mGraph *mg,int nSize,ElemType noEdgeValue)
{
int i,j;
mg->n=nSize;
mg->e=0;
mg->noEdge=noEdgeValue;
mg->a=(ElemType**)malloc(nSize*sizeof(ElemType*));
if(!mg->a)
return ERROR;
for(i=0;i<mg->n;i++)
{
mg->a[i]=(ElemType*)malloc(nSize*sizeof(ElemType));
for(j=0;j<mg->n;j++)
mg->a[i][j]=mg->noEdge;
mg->a[i][i]=0;
}
return OK;
}
void zifan(mGraph *mg)//判断自反性
{
bool flag = true;
for(int i=0;i<mg->n;i++)
{
if(mg->a[i][i]==0)
{
flag=false;
break;
}
}
if(flag==true)
printf("满足自反性n");
else
printf("不满足自反性n");
}
void fanzifan(mGraph *mg)//判断反自反性
{
bool flag = true;
for(int i=0;i<mg->n;i++)
{
if(mg->a[i][i]==1)
{
flag=false;
break;
}
}
if(flag==true)
printf("满足反自反性n");
else
printf("不满足反自反性n");
}
void duicheng(mGraph *mg)//判断对称性
{
bool flag = true;
for(int i=0;i<mg->n;i++)
{
for(int j=0;j<mg->n;j++)
{
if(mg->a[i][j]==1)
{
if(mg->a[j][i]==0)
{
flag=false;
break;
}
}
}
}
if(flag==true)
printf("满足对称性n");
else
printf("不满足对称性n");
}
void fanduicheng(mGraph *mg)//判断传递性
{
bool flag = true;
for(int i=0;i<mg->n;i++)
{
for(int j=0;j<mg->n;j++)
{
if(mg->a[i][j]==1)
{
if(mg->a[j][i]==1)
{
if(i!=j)
{
flag=false;
break;
}
}
}
}
}
if(flag==true)
printf("满足反对称性n");
else
printf("不满足反对称性n");
}
void chuandi(mGraph *mg)
{
bool flag=true;
for(int i=0;i<mg->n;i++)
{
for(int j=0;j<mg->n;j++)
{
for(int k=0;k<mg->n;k++)
{
if(mg->a[i][j]==1&&mg->a[j][k]==1)
{
if(mg->a[i][k]!=1)
{
flag=false;
break;
}
}
}
}
}
if(flag==true)
printf("满足传递性n");
else
printf("不满足传递性n");
}
int main()
{
int num,p=0,q;//元素个数
printf("请输入集合中的元素个数：n");
scanf("%d",&num);
mGraph x;
Init(&x,num,0);//先初始化一个n*n的各个元素皆为0的二维数组
printf("请输入集合上的关系(结束输入后输入元素个数)：");
scanf("%d %d",&p,&q);
while(p!=num)
{
x.a[p][q]=1;
scanf("%d %d",&p,&q);
}
zifan(&x);//判断是否满足自反性
fanzifan(&x);//判断是否满足反自反性
duicheng(&x);//判断是否满足对称性
fanduicheng(&x);//判断是否满足反对称性
chuandi(&x);//判断是否满足传递性
return 0;
}
|
近期评论