5.c

文件用于计算学分和先后的选修课 用于数据结构的递归思想!

#include <stdio.h>
int note[6][6]={100,2,5,1,100,100,
                2,100,3,2,100,100,
				5,3,100,3,1,5,
				1,2,3,100,1,100,
				100,100,1,1,100,2,
				100,100,5,100,2,100
				}; //初始化网络拓扑图  ,100表示同一结点或结点无连接
char name[6]={'A','B','C','D','E','F'};//结点的标识
int D[6],p[6];
int N[6];       //数组定义与课本相同

void loop(int j){    //链路选择算法实现
	int i,v;
	int min=100;  //min表示最小代价
	for(i=0;i<6;i++)
	if(p[i]==N[j-1]&&D[i]<min)//判断结点的前趋结点是否为上一迭代结点
	  {min=D[i];v=i;}          //找出当前最小代价结点作为迭代结点
    printf("%d,%d\n",min,v);
    N[j]=v;//记录迭代结点
	for(i=1;i<6;i++)
		if(D[i]>(D[v]+note[i][v]))   //判断原有代价与从迭代点出发代价的大小
		{
			D[i]=D[v]+note[i][v];       //若小于，生成新的最小代价
			printf("%d,%d,%d,i=%d,v=%d\n",D[i],D[v],note[i][v],i,v);   //查看状态
			p[i]=v;                    //生成新的前趋结点
			printf("cost is%d,last point is %d,now point is %d\n",D[i],p[i],N[j]); //查看状态
			}
	for(i=0;i<6;i++)
		printf("%d %d %d\n",D[i],p[i],N[i]);   //查看状态
	printf("*********************************\n");
	}

void main(){
	int i,m;
	for(i=0;i<6;i++) {D[i]=note[0][i];p[i]=0;N[i]=0;}    //初始化各数组，完成步骤0
	for(i=0;i<5;i++) loop(i);//做5次迭代
	for(i=1;i<6;i++)
	   {
	    printf("\nFrom A to %c ,mincost is: %d\n",name[i],D[i]);  //输出
	    printf("the way is:");
	    m=i; printf("%c ",name[m]);
	    while(m!=0)
        {
         m=p[m];
         printf("%c ",name[m]); }  //输出最小代价路径所经历的结点
	      }
	}