传递闭包程序

《应用程序设计课程设计》报告班级：学号：姓名：指导教师:成绩评定:太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院20122012年01月目录1、 计算机求解关系R的传递闭包2、 通讯录管理3、 校园导游咨询实验一、计算机求解关系R的传递闭包、设计方案简介设计一个程序实现求解关系R的传递闭包、设计题目实现（1）需求分析用户要自己计算岀二元关系的矩阵形式，输入时要按矩阵输入，从第一排第一个开始输入，直到第一排全部输入（每两个数字之间要输入一个空格） ，然后按回车转换到下一行，以同样的形式输入该行数字，全部输入完成后按回车。然后会输岀一个矩阵就是所求的关系 R的传递闭包矩阵。程序可以求任意关系R的传递闭包，但必须按要求输入正确的关系矩阵形式，现在的程序可以计算 10维以内的，如果需要可以修改维数，计算更高维数的关系矩阵的传递闭包。测试数据:‘‘010R=001严'01001010‘‘010R=001严'01001010R=00010000■‘111t(R)=111^11t(R)=彳11111110001^000011000000001000110000000010000000100R=010000000000000000000.000000001010000000100t(R)=0101000000000000000000000000(2)概要设计在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。 R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用 B表示定义在具有n个元素的集合X上关系R的nxn二值矩阵，则传递闭包的矩阵 B+可如下计算：+ 23 nB=B+B+B+……+(B)式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为 B,B(B),B(BB),B(BBB),……，所以在运算的每一步我们只需简单地把现有结果乘以 B,完成矩阵的n次乘法即可。函数调用关系Nain()Work()详细设计voidwork(intR[10][10],intn){求矩阵R[][]的传递闭包定义一个矩阵M将输入的矩阵R赋值给矩阵M用M的行乘以R的列得到Rn，并将Rn赋值给M最后将R1R2R3R4…….Rn相加的结果赋给 R//将矩阵R[][]中非0元素置换为1输出传递闭包

主程序{"请输入关系矩阵的维数请输入关系矩阵调用work函数return0;}（4）测试分析本次作业比较简单，只有一个核心算法，即求计算机求解关系 R的传递闭包，所以可以使用一个主函数实现，不需要调用函数。只是编写 Warshall算法时比较麻烦，一开始我只是计算出来R的n次方，输出时没有把每一次的结果加到一起，出现了错误，后来我又用另一个数组把每次结果相加，最终输出了正确结果。但是程序还存在一定的缺陷，没有实现在不关闭界面的情况下，重复输入矩阵求取传递闭包。（5） 使用说明进入演示程序后，即显示文本方式的用户界面，先输入矩阵的维数，按回车，继续输入一个矩阵，按回车即可得到所求结果。（6） 测试结果请输入关系矩阵的络数<n<10>鲁输入关系矩阵班010001130传递闭包关系矩阵t<R>：111111111请按任意键继续・・・犢输入关系矩阵的维数<n<10>3请输入关系矩阵职010001130传递闭包关系矩阵“2：111111111请按任意键继续・・・~ I计Z1001X%建文件^\ninc4\Deluc\ninc4.exe*请输入关系矩阵的维数<n<18>7请输入关系矩阵肥110000000010000000100P100000000000000000诃000000传递闭包关系矩阵“呀1101000H1010冏0000010001010W0R0000R0000000800080请按任意锥继续・・・附录1:参考资料数据结构（严蔚敏版）C语言程序设计（谭浩强版）附录2:源程序#include"stdafx.h"#include"stdio.h"#include"stdlib.h"voidwork(intR[10][10],intn){ //求矩阵R[][]的传递闭包inti,j,k,m;intM[10][10];inta=0;for(i=0;ivn;i++){for(j=0;jvn;j++)M[i][j]=R[i][j]；}for(m=1;m<n;m++){for(i=0;ivn;i++){for(j=0;jvn;j++){for(k=0;kvn;k++){a=a+M[i][k]*R[k][j];}M[i][j]=a;R[i][j]=R[i][j]+M[i][j];a=0;}}}for(i=0;ivn;i++) //将矩阵R[][]中非0元素置换为1for(j=0;jvn;j++){if(R[i][j]==0){continue;}else{R[i][j]=1;}}printf(传递闭包关系矩阵t:”)；for(i=0;ivn;i++){for(j=0;jvn;j++){printf("%d”,R[i][j]);}printf("\n");}}intmain(intargc,char*argv[|){intR[10][10];intn,i,j;\n");printf("请输入关系矩阵