傳遞閉包程序

《應用程序設計課程設計》報告班級：學號：姓名：指導教師:成績評定:太原理工大學計算機科學與技術學院太原理工大學計算機科學與技術學院20122012年01月目錄1、 計算機求解關系R的傳遞閉包2、 通訊錄管理3、 校園導游咨詢實驗一、計算機求解關系R的傳遞閉包、設計方案簡介設計一個程序實現(xiàn)求解關系R的傳遞閉包、設計題目實現(xiàn)（1）需求分析用戶要自己計算岀二元關系的矩陣形式，輸入時要按矩陣輸入，從第一排第一個開始輸入，直到第一排全部輸入（每兩個數(shù)字之間要輸入一個空格） ，然后按回車轉換到下一行，以同樣的形式輸入該行數(shù)字，全部輸入完成后按回車。然后會輸岀一個矩陣就是所求的關系 R的傳遞閉包矩陣。程序可以求任意關系R的傳遞閉包，但必須按要求輸入正確的關系矩陣形式，現(xiàn)在的程序可以計算 10維以內的，如果需要可以修改維數(shù)，計算更高維數(shù)的關系矩陣的傳遞閉包。測試數(shù)據:‘‘010R=001嚴'01001010‘‘010R=001嚴'01001010R=00010000■‘111t(R)=111^11t(R)=彳11111110001^000011000000001000110000000010000000100R=010000000000000000000.000000001010000000100t(R)=0101000000000000000000000000(2)概要設計在集合X上的二元關系R的傳遞閉包是包含R的X上的最小的傳遞關系。 R的傳遞閉包在數(shù)字圖像處理的圖像和視覺基礎、圖的連通性描述等方面都是基本概念。一般用 B表示定義在具有n個元素的集合X上關系R的nxn二值矩陣，則傳遞閉包的矩陣 B+可如下計算：+ 23 nB=B+B+B+……+(B)式中矩陣運算時所有乘法都用邏輯與代替，所有加法都用邏輯或代替。上式中的操作次序為 B,B(B),B(BB),B(BBB),……，所以在運算的每一步我們只需簡單地把現(xiàn)有結果乘以 B,完成矩陣的n次乘法即可。函數(shù)調用關系Nain()Work()詳細設計voidwork(intR[10][10],intn){求矩陣R[][]的傳遞閉包定義一個矩陣M將輸入的矩陣R賦值給矩陣M用M的行乘以R的列得到Rn，并將Rn賦值給M最后將R1R2R3R4…….Rn相加的結果賦給 R//將矩陣R[][]中非0元素置換為1輸出傳遞閉包

主程序{"請輸入關系矩陣的維數(shù)請輸入關系矩陣調用work函數(shù)return0;}（4）測試分析本次作業(yè)比較簡單，只有一個核心算法，即求計算機求解關系 R的傳遞閉包，所以可以使用一個主函數(shù)實現(xiàn)，不需要調用函數(shù)。只是編寫 Warshall算法時比較麻煩，一開始我只是計算出來R的n次方，輸出時沒有把每一次的結果加到一起，出現(xiàn)了錯誤，后來我又用另一個數(shù)組把每次結果相加，最終輸出了正確結果。但是程序還存在一定的缺陷，沒有實現(xiàn)在不關閉界面的情況下，重復輸入矩陣求取傳遞閉包。（5） 使用說明進入演示程序后，即顯示文本方式的用戶界面，先輸入矩陣的維數(shù)，按回車，繼續(xù)輸入一個矩陣，按回車即可得到所求結果。（6） 測試結果請輸入關系矩陣的絡數(shù)<n<10>魯輸入關系矩陣班010001130傳遞閉包關系矩陣t<R>：111111111請按任意鍵繼續(xù)???犢輸入關系矩陣的維數(shù)<n<10>3請輸入關系矩陣職010001130傳遞閉包關系矩陣“2：111111111請按任意鍵繼續(xù)???~ I計Z1001X%建文件^\ninc4\Deluc\ninc4.exe*請輸入關系矩陣的維數(shù)<n<18>7請輸入關系矩陣肥110000000010000000100P100000000000000000訶000000傳遞閉包關系矩陣“呀1101000H1010冏0000010001010W0R0000R0000000800080請按任意錐繼續(xù)???附錄1:參考資料數(shù)據結構（嚴蔚敏版）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("請輸入關系矩陣