mgraph.cpp

数据结构中所有算法的实现

#include "d:\cpp\head.h"
#define INFINITY 9999
#define MAX_VERTEX_NUM 20
#define VertexType char
#define VRType int
#define InfoType char
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef struct ArcCell{
  VRType adj;
  InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
  VertexType vexs[MAX_VERTEX_NUM];
  AdjMatrix arcs;
  int vexnum,arcnum;
  GraphKind kind;
}MGraph;
Status CreateUDN(MGraph &G){
  int IncInfo;
  int i,j,k;
  char v1,v2;
  int w;
  char t;
  printf("\nInput vexnum,arcnum,sign of the arcs's info(0,1):");
  scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);scanf("%c",&t);
  printf("\nInput vexs:");
  for(i=0;i<G.vexnum;++i)scanf("%c",&G.vexs[i]);scanf("%c",&t);
  for(i=0;i<G.vexnum;++i)
    for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;};
  for(k=0;k<G.arcnum;++k){
    printf("\nInput v1,v2,w:");
    scanf("%c,%c,%d",&v1,&v2,&w);    scanf("%c",&t);
    for(i=0;i<G.vexnum;++i)if(G.vexs[i]==v1)break; //LocateVex(G,v1);
    for(j=0;j<G.vexnum;++j)if(G.vexs[j]==v2)break; //LocateVex(G,v2);
    G.arcs[i][j].adj=w;
    if(IncInfo)scanf("%c",*G.arcs[i][j].info);
    G.arcs[j][i]=G.arcs[i][j];
  }
  return OK;
}//CreateUDN
Status CreateGraph(MGraph &G){
  printf("\nInput the kind of graph:");
  scanf("%d",&G.kind);
  switch(G.kind){
    //case DG: return CreateDG(G);
    //case DN: return CreateDN(G);
    //case UDG:return CreateUDG(G);
    case UDN:return CreateUDN(G);
    default: return ERROR;
  }//switch
}//CreateGraph
Status PrintGraph(MGraph G){
int i,j;
printf("\n-------THE INFO OF GRAPH G---------\n");
if(G.kind==UDN){
  printf("wu xiang wang.\n");
  printf("you %d ge ding dian: ",G.vexnum);
  for(i=0;i<G.vexnum;++i) printf("%5c",G.vexs[i]);
  printf("\nyou %d tiao bian: \n",G.arcnum);
  for(i=0;i<G.vexnum;++i)
    for(j=0;j<G.vexnum;++j)
      if(G.arcs[i][j].adj!=INFINITY && i<j){
	printf("%c%c",G.vexs[i],G.vexs[j]);
	printf("%5d\n",G.arcs[i][j].adj);
      }//if
}//if
if(G.kind==DG){}
if(G.kind==DN){}
if(G.kind==UDG){}
return OK;
}
void main(){
  MGraph G;
  CreateGraph(G);
  PrintGraph(G);
}//main