最优化.cpp

这是一个最优化程序代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
#define MAX_CH_LONG 5

typedef struct ArcNode {
   int            adjvex;  /*该弧所指向的顶点的位置*/
   struct ArcNode *nextarc; /*指向下一条弧的指针*/
   float          cost;     /*该弧的权值*/
}ArcNode;
typedef struct VNode {
   char      vextex[MAX_CH_LONG];            /*顶点信息*/
   ArcNode   *firstarc;      /*指向第一条依附该顶点的弧的指针*/
   float     mincost;        /*记录该结点到目标结点的最优值*/
}VNode,AdjList[MAX_VERTEX_NUM];

float MinCost(AdjList A,int i,FILE *fp)
/*用动态规划法求从源结点到目标结点的最优路径*/
{float u,temp;
 ArcNode *p;

 if(A[i].firstarc==NULL)   { A[i].mincost=0;return 0;}
 else
   { p=A[i].firstarc;
     u=MinCost(A,p->adjvex,fp)+p->cost;
   }
 while(p->nextarc!=NULL)
   { p=p->nextarc;
     temp=MinCost(A,p->adjvex,fp)+p->cost;
     if(u>temp)
       u=temp;
   }
 A[i].mincost=u;
 return u;
}//end MinCost

int MinPath(AdjList A,int path[])
/*求最优路径*/
{ int i=1;
  ArcNode *p;
  VNode *q;

  path[0]=0;
  q=&A[0];
  while(q->firstarc!=NULL)
    { p=q->firstarc;
      while(p!=NULL)
       { if(q->mincost==A[p->adjvex].mincost+p->cost)
	   { path[i]=p->adjvex;
	     q=&A[p->adjvex];
	     i++;
	     break;
	   }
	 p=p->nextarc;
       }//end while1
    }//end while2
  return i;
}//end MinPath

void InitAdjList(FILE *fp,AdjList A)
{ VNode *r;
  ArcNode *p;
  float cost;
  char ch;
  char vextex[MAX_CH_LONG];
  int i,j,find;

  while(!feof(fp))
   /*先读取每一行的第一个顶点号*/     
      {  do { fscanf(fp,"%c",&ch);
	      }while(ch==' ');

	 i=0;j=0;find=0;
	 while(ch!=' '&&ch!='(')
	      { vextex[i]=ch;
		fscanf(fp,"%c",&ch);
		i++;
	      }

	 vextex[i]='\0';
       /*在寻找邻结表中是否有该顶点，如没有则生成*/
	 while(1)
	    { if(strcmp("\0",A[j].vextex)==0)   break;
	      else
		{ if(strcmp(vextex,A[j].vextex)==0)
		     { find=1;break;}
		  j++;
		}
	    }
	 if(find==0)
	     { strcpy(A[j].vextex,vextex);
	       A[j].firstarc=NULL;
	     }
	 r=&A[j];
/*读取每一行第一个顶点以后的顶点号和该点与第一个顶点相连的权值*/
	 do{ while(ch!='('&&ch!='\n'&&!feof(fp))
		{ fscanf(fp,"%c",&ch);}
	     if(ch=='\n'||feof(fp))  break;

	     fscanf(fp,"%f",&cost);

	     do { fscanf(fp,"%c",&ch);
		 }while(ch==' ');

	     i=0;j=0;find=0;
	     while(ch!=' '&&ch!=')')
		 { vextex[i]=ch;
		   fscanf(fp,"%c",&ch);
		   i++;
		  }

	     vextex[i]='\0';
             /*在寻找邻结表中是否有该顶点，如没有则生成*/
	     while(1)
		 { if(strcmp("\0",A[j].vextex)==0)   break;
		   else
		      { if(strcmp(vextex,A[j].vextex)==0)
			  { find=1;break;}
			j++;
		      }
		}
	    if(find==0)
		{ strcpy(A[j].vextex,vextex);
		  A[j].firstarc=NULL;
		 }
             /*生成弧结点*/
	     p=(ArcNode *)malloc(sizeof(ArcNode));
	     p->nextarc=r->firstarc;
	     r->firstarc=p;
	     p->cost=cost;
	     p->adjvex=j;

	    while(ch!=')')
	      { fscanf(fp,"%c",&ch);}
	  }while(!feof(fp));
    }//end while
}//end InitAdjList

void DestroyAdjList(AdjList A)
{ int i;
  ArcNode *p,*q;

  for(i=0;i<MAX_VERTEX_NUM;i++)
      { p=A[i].firstarc;
	while(p!=NULL)
	   { q=p;
	     p=p->nextarc;
	     free(q);
	   }
	A[i].firstarc=NULL;
      }
}//end DestroyAdjList
/////////////////////////////////////////////////

main()
{ int i,vexnum;
  char ch;
  int path[MAX_VERTEX_NUM];
  float cost;
  AdjList Adj;
  FILE *fpIn,*fpOut;

  if((fpIn=fopen("zyh.txt","r"))==NULL)
   {
     printf("File (zuiyouhua) cannot be opened.\n");
     exit(1);
   }

  if((fpOut=fopen("zyhdata.txt","w"))==NULL)
   {
     printf("File (zyhdata) cannot be opened.\n");
     exit(1);
   }

 for(i=0;i<MAX_VERTEX_NUM;i++)
    { strcpy(Adj[i].vextex,"\0");
      Adj[i].firstarc==NULL;
    }


 InitAdjList(fpIn,Adj);

 MinCost(Adj,0,fpIn);
 vexnum=MinPath(Adj,path);

 fprintf(fpOut,"最优路径为:\n%s(%f)",Adj[0].vextex,Adj[0].mincost);

 for(i=1;i<vexnum;i++)
    fprintf(fpOut,"->%s(%f)",Adj[path[i]].vextex,Adj[path[i]].mincost);
 fprintf(fpOut,"\n从%s到%s的最优路径值为：%f",
              Adj[0].vextex,Adj[path[vexnum-1]].vextex,Adj[0].mincost);
 DestroyAdjList(Adj);
 fclose(fpIn);
 fclose(fpOut);
 return 0;
}