about-tu.cpp

数据结构中关于图的程序。这部分是数据结构中的重点知识。老师要求的是要很好的理解。

#include   <iostream.h>   
#include   <stdlib.h>   
#define   INFINITY   0   
#define   MAX_VERTEX_NUM   10         //最大顶点数   
#define   MAX_EDGE_NUM   40       //最大边数  
 
typedef   enum   {DG,DN,UDG,UDN}Graphkind;//{有向图，有向网，无向图，无向网}  书p161 
typedef   char   VertexType;           //顶点数据类型     
typedef   struct   ArcCell   
{     
  int   adj;             //无权图，1或0表示相邻否；带权图则是权值。   
  //int   *info;   
  }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   
  typedef   struct     
  {     
	  VertexType   vexs[MAX_VERTEX_NUM];           //顶点向量   
      AdjMatrix   arcs;       //邻接矩阵   
      int   vexnum,arcnum;                         //图的当前顶点数和弧数。   
      Graphkind   kind;   
  }MGraph;   
    
  int   LocateVex(MGraph   G,VertexType   v1)   
  {   
  int   i;   
  for(i=0;i<G.vexnum;i++)   
  if(G.vexs[i]==v1)   
  return   i;   
  return   -1;   
  }   
    
  int   CreatUDN(MGraph   &G)   
  //   采用数组表示法，构造无向网   G   
  {   
  VertexType   v1,v2;   
  int   w,j;   
  cout<<"输入图的顶点数"<<endl;   
  cin>>G.vexnum;   
  cout<<"输入图的弧数"<<endl;   
  cin>>G.arcnum;   
  for(int   i=0;i<G.vexnum;i++)   
  {   
  cout<<"输入顶点向量"<<endl;   
  cin>>G.vexs[i];   
  }   
  for(i=0;i<G.vexnum;i++)   
  for(j=0;j<G.vexnum;j++)   
  {   
  G.arcs[i][j].adj=INFINITY;   
  }   
  for(int   k=0;k<G.arcnum;++k)                 //构造邻接矩阵   
  {   
  cout<<"输入边依附的两个顶点"<<endl;   
  cin>>v1>>v2;   
  cout<<"输入此边的权值"<<endl;   
  cin>>w;   
  i=LocateVex(G,v1);   
  j=LocateVex(G,v2);   
  G.arcs[i][j].adj=w;   
  G.arcs[j][i].adj=G.arcs[i][j].adj;   
  }   
  return   1;   
  }   
    
  void   dispMGraph(MGraph   G)   
  {   
  cout<<"图的邻接矩阵图是："<<endl;   
  for(int   i=0;i<G.vexnum;i++)   
  {   
  for(int   j=0;j<G.vexnum;j++)   
  cout<<" "<<G.arcs[i][j].adj;   
  cout<<endl;   
  }   
  }     
  void   main()   
  {   
  MGraph   G;   
  CreatUDN(G);   
  dispMGraph(G);   
  }