51CTO下载-C++编写warshall算法的传递闭包.docVIP

1.利用求传递闭包的Warshall算法，给定关系R，编写求R的可传递闭包的C语言程序并利用下列数据测试。 测试数据为： 0，1，0，0， 0，0，1，0， 0，0，0，1， 0，0，0，0 #include stdio.h #include stdlib.h #define N 20 #define M 20 main() { int i,j,k,m,n; int r1[M],r2[M],a[N],mr[N][N]={0}; FILE * fp; printf(程序自动调用c:/stone2.txt文件内相应数据\n); fp=fopen(c:\\stone2.txt,r); fscanf(fp,%d,n); /*读取集合元素个数*/ for(i=0;in;i++) /*读取集合元素*/ fscanf(fp,%d,a[i]); fscanf(fp,%d,m); /*读取关系个数*/ for(k=0;km;k++) fscanf(fp,%d,%d,r1[k],r2[k]); /*读取关系*/ fclose(fp); printf(自反闭包r(R):\n{); for(i=0;in;i++) printf(%d,%d,,a[i],a[i]); /*输出自反闭包*/ for(k=0;km;k++) { if(r1[k]!=r2[k]) printf(%d,%d,,r1[k],r2[k]); else continue; } printf(\b}\n); printf(对称闭包s(R):\n{); /*输出对称闭包*/ for(k=0;km;k++) { if(r1[k]!=r2[k]) printf(%d,%d,%d,%d,,r1[k],r2[k],r2[k],r1[k]); else printf(%d,%d,,r1[k],r2[k]); } printf(\b}\n); k=0; for(i=0;in,km;i++) { if(r1[k]!=a[i]) continue; else { for(j=0;jn,km;j++) /*关系转换成矩阵*/ { if(r2[k]!=a[j]) continue; else { mr[i][j]=1; k++; i=0;j=0; break; } } } } printf(关系所对应的关系矩阵:\n); for(i=0;in;i++) { /*打印关系矩阵*/ for(j=0;jn;j++) printf(%5d,mr[i][j]); printf(\n); } for(k=0;kn;k++) for(i=0;in;i++) /*warshall*/ for(j=0;jn;j++) mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j]; for(i=0;in;i++) for(j=0;jn;j++) { /*把mr[]非0项赋值为1*/ if(!mr[i][j]) continue; else mr[i][j]=1; } printf(传递闭包对应关系矩阵:\n); for(i=0;in;i++) { /*输出传递闭包对应的关系矩阵*/ for(j=0;jn;j++) printf(%5d,mr[i][j]); printf(\n); } system(PAUSE); } 自己写的,三个闭包都有,包括传递闭包,看注释就知道了,还是用文件读写,方便数据输入