| xk2243098xk |
2008-10-22 19:25 |
下面是这个程序是数据结构的，这个是别人的，有没有哪位高手可以帮我改一下（就是改成看不出是抄袭的那种）。没办法，本人天生就怕编程，看到就晕了，实在编不出来，才出此下策。希望有人帮我看下，在此先谢过了！
题目描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
功能要求及说明：(主要使用的知识: 图)
（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；
（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；并且利用文件对数据进行提取。
（3）输出最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
（4）采用模块化设计；
程序如下，也可到链接下载
#define MAXVEX 40
#define MAXCOST 10000
#define N 6
#include<stdio.h>
void main()
{
FILE *p; /*定义一个指向文件的指针*/
int i=1,j,m,mx[MAXVEX][MAXVEX];char ch;
void zxscs_sh(int c[MAXVEX][MAXVEX],int n); /*函数声明*/
printf("\n!!ATTENTION: \n 1),Please create a right file and put it in the right place.\n");
printf(" 2),Please rewrite the 'N' which means the numbers in each line.\n"); /*提示信息*/
printf(" 3),Have you done it ? y(YES) or n(NO) : "); /*输出提示信息*/
getchar();
if((p=fopen("D:\\int5.txt","r"))==NULL)/*判断打开文件成功与否*/
{
printf(" !The file can not be opened\n");/*输出提示信息*/
exit(1);
}
for(m=1;m<=N;m++)
{
for(j=1;j<=N;j++)
fscanf(p,"%d",&mx[j]); /*从路径指明的文本文件中调取整型数据，并赋给数组元素*/
i++;
}
for (i=1;i<=N;i++)
for (j=1;j<=N;j++)
if(mx[j]==0)/*判断数据，若为零，则表示城市之间不相通或同一城市*/
mx[j]=MAXCOST;
printf("\n The 'zhuixiaoshenchenshu' is :\n ");
zxscs_sh(mx,N);/*调用函数*/
printf("\n Do you want to see the file? y / n : ");/*输出提示信息*/
getchar();
ch=getchar();
if(ch=='y')/*判断输入条件，若为Y，则表示选择显示文本文件的内容*/
{
for (i=1;i<=N;i++)
{
printf(" ");
for (j=1;j<=N;j++)
{
if(mx[j]==MAXCOST)
mx[j]=0;
printf(" %d ",mx[j]);/*输出数据*/
}
printf("\n");
}
getchar();/*控制显示*/
printf(" !EXIT by any input.");/*输出提示信息*/
getchar();
}
else
{
printf(" !EXIT by any input.");/*输出提示信息*/
getchar();
getchar();
}
}
void zxscs_sh(int c[MAXVEX][MAXVEX],int n) /*zxscs:最小生成树；给定网的顶点，数组表示对应边的权值，打印最小生成树的边和代价*/
{
int i,j,k,min,sum=0,lc[MAXVEX],location[MAXVEX];
for (i=1;i<=n;i++)
{
lc=c[1];
location=1;
} /*初始化数组*/
location[1]=0;
for (i=2;i<=n;i++)/*从U之外求离U中某一点顶点最近的顶点*/
{
min=MAXCOST; /*将MAXCOST赋给变量min*/
j=1;k=i;
while (j<=n)
{
if (lc[j]<min && location[j]!=0)
{
min=lc[j];
k=j;
}
j++;
}
sum=sum+min;/*累加求和*/
printf("\n Bian %d is :(v%d,v%d). The cost of this bian is: ( %d );\n",i-1,location[k],k,min); /*打印最小生成树的边，每条边对应的权值*/
location[k]=0; /*将顶点k并入到U中去*/
for (j=2;j<=n;j++)
if (location[j]!=0 && c[k][j]<lc[j])/*比较权的大小*/
{
lc[j]=c[k][j];
location[j]=k;
}
}
printf("\n The whole cost are: %d\n",sum);
} |
|