数据结构大作业-寻径问题

#include<stdio.h> #include<ctype.h> #define nMax 20 /*村庄的最大值(理论上没有限制，但为了控制问题的规模和手工输入的不便，故控制在20*/ #define WeighMax 65535 /*村庄之间距离的最大值，也是int型的最大值*/ int n; /*公共变量用于存放村庄的个数*/ int final[nMax]; /*用于存放距离最远的最好村庄情况*/ int Adj[nMax][nMax]; /*二维数组，用于存放村庄之间的初始距离*/ int ShortAdj[nMax][nMax]; /*二维数组，用于存放村庄之间的最短距离*/ void Floyd(); /*最核心的算法，弗络伊德算法O(n^3)，用于计算村庄之间的最短距离*/ void Input_Output(); /*用于手工输入村庄之间距离，和输入相应数值的函数*/ void Out(); /*用于输出最终结果的函数*/ void ShortestPath(); /*计算离医院最远的村庄到医院的距离最短的函数,是对Floyd的后续处理*/ void main(){ /*主函数*/ Input_Output(); Floyd(); ShortestPath(); Out(); } void Input_Output(){ int i,j; printf("请输入村庄的数目（范围为2-50）:"); scanf("%2d", &n); while(n<=2||n>nMax){ printf("您的输入有误，请再次输入:"); /*根据空间复杂度，人为的限制手工输入的次数*/ scanf("%2d",&n);} for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ if(i==j) Adj[i][j] = ShortAdj[i][j] = 0; /*此算法只考虑有向图的情况,如果是无向图的话，for循环中i,j的值<=n/2*/ else{int PathWeigh = WeighMax; /*初始化输入的值为int型的最大值*/ printf("\n请输入从第%d个村庄到第%d个村庄的距离：", i, j); scanf("%d",&PathWeigh); /*未能处理非数字输入的问题*/ if(PathWeigh>WeighMax) Adj[i][j]=WeighMax; /*如果输入比int型数值大，则取其上限*/ else Adj[i][j]=PathWeigh; printf("村庄%d到村庄%d的距离是：%d\n", i, j, Adj[i][j]); ShortAdj[i][j] = Adj[i][j];} /*同时将输入的值存到ShortAdj中，用于下面Floyd函数的处理中*/ } } printf("\n村庄之间路径的距离(矩阵):\n"); for(i=1;i<=n;i++){ /*输出手工输入的数值，以矩阵的方式来显示，更加直观*/ for(j=1;j<=n;j++) printf("\t%d",Adj[i][j]); printf("\n");} } void Floyd(){ /*弗络伊德算法，求多源点的最短路径*/ int i,j,tmp; for(tmp=1;tmp<=n;tmp++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ /*三次循环*/ if(Adj[i][j]>ShortAdj[i][tmp]+ShortAdj[tmp][j]) /*如果通过中间路径，比原来存于数组里的值小，则代换!*/ ShortAdj[i][j]=ShortAdj[i][tmp]+ShortAdj[tmp][j];} printf("\n村庄之间路径的最短距离（矩阵）：\n"); for(i=1;i<=n;i++){ /*打印村庄之间的最短路径,同样以矩阵的形式显示*/ for(j=1;j<=n;j++) printf("\t%d",ShortAdj[i][j]); printf("\n");} } void ShortestPath(){ /*计算离医院最远的村庄到医院的最短距离*/ int i,j; for(i=1;i<=n;i++){ /*找出每一组最短距离中的最大值!*/ final[i]=ShortAdj[i][1]; for(j=2;j<=n;j++) if(final[i]<ShortAdj[i][j]) final[i]=ShortAdj[i][j]; } printf("\n村庄\t最长距离\n"); /*打印每组的最长距离*/ for(i=1;i<=n;i++) printf("%d\t%d\n",i,final[i]); } void Out(){ /*计算最终结果，并输出*/ int i,tmp=1; for(i=2;i<=n;i++) if(final[tmp]>final[i]) tmp=i; printf("\n建设医院的最佳位置是村庄%d\n",tmp); }