ex14.cpp

设置一个静态堆栈

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define MAX_VERTEX_NUM 20
typedef int VertexType;
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int Status;

typedef struct
{  VertexType vex[MAX_VERTEX_NUM];
   AdjMatrix Dist;
   int vexnum,arcnum;
}MGraph;

typedef struct
{  int s[MAX_VERTEX_NUM];
   int top;
}SqStack;

Status InitStack(SqStack &S)
{  S.top=0;
   return OK;
}

Status StackEmpty(SqStack S)
{  return S.top==0;
}

Status Push(SqStack &S, int n)
{  if(S.top>=MAX_VERTEX_NUM) return ERROR;
   else
     S.s[S.top++]=n;
   return OK;
}

Status Pop(SqStack &S,int &n)
{  if(StackEmpty(S)) return ERROR;
   n=S.s[--S.top];
   return OK;
}

void CreateDN_M(MGraph &G,AdjMatrix &Path)
{  int i,j,k,w;
   printf("Input the vexnum and the arcnum:\n");
   scanf("%d%d",&G.vexnum,&G.arcnum);
   printf("Enter the vex in graph:\n");
   for(i=0;i<G.vexnum;i++)
     scanf("%d",&G.vex[i]);
   for(i=0;i<G.vexnum;i++)
     for(j=0;j<G.vexnum;j++)
     {  if(i==j)
	{  G.Dist[i][j]=0;
	   Path[i][j]=0;
	}
	else
	{  G.Dist[i][j]=999;
	   Path[i][j]=-1;
	}
     }
  printf("Enter the arcs and weight:\n");
   for (k=0;k<G.arcnum;k++)
   {  scanf("%d%d%d",&i,&j,&w);
      Path[i][j]=i;
      G.Dist[i][j]=w;
   }
}

void Floyd(MGraph &G, AdjMatrix &Path)
{ int i,j,k,n=G.vexnum;
  for(k=0; k<n; k++)
    for(i=0; i<n; i++)
      for(j=0; j<n; j++)
	if(G.Dist[i][k]+G.Dist[k][j] < G.Dist[i][j])
	    { G.Dist[i][j] = G.Dist[i][k]+G.Dist[k][j];
	      Path[i][j] = Path[k][j];
	    }
}


void Display(MGraph G,AdjMatrix Path )
{  int i=0,j=0,v,w;
   SqStack S;
   for(i=0;i<G.vexnum;i++)
     for(j=0;j<G.vexnum;j++)
     {  InitStack(S);
	w=G.Dist[i][j];
	Push(S,j);
	if(w!=0&&w!=999)
	for(v=Path[i][j];v!=i;v=Path[i][v])
	  Push(S,v);
	Push(S,i);
	 if(w==999||w==0)  printf("V%d->V%d:  \n",G.vex[i],G.vex[j]);
	 else
	 {  printf("V%d->V%d:  %2d       ",G.vex[i],G.vex[j],w);
	   while(S.top>1)
	    {  Pop(S,v);
	       printf("V%d->",G.vex[v]);
	    }
	    Pop(S,v);
	    printf("V%d",G.vex[v]);
	    printf("\n");
	 }
      }
}

void main()
{  MGraph g;
   AdjMatrix p;
   CreateDN_M(g,p);
   Floyd(g,p);
   Display(g,p);
}