bo7-1.cpp

清华大学《数据结构》教材第二版对应的C++教学程序

 // bo7-1.cpp 图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作(20个)
 int LocateVex(MGraph G,VertexType u)
 { // 初始条件:图G存在,u和G中顶点有相同特征
   // 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.vexs[i])==0)
       return i;
   return -1;
 }

 Status CreateFAG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G
   int i,j,k;
   char filename[13];
   VertexType va,vb;
   FILE *graphlist;
   printf("请输入数据文件名(f7-1.dat)：");
   scanf("%s",filename);
   graphlist=fopen(filename,"r");
   fscanf(graphlist,"%d",&G.vexnum);
   fscanf(graphlist,"%d",&G.arcnum);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     fscanf(graphlist,"%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL; // 没有相关信息
     }
   for(k=0;k<G.arcnum;++k)
   {
     fscanf(graphlist,"%s%s",va,vb);
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 无向图
   }
   fclose(graphlist);
   G.kind=AG;
   return OK;
 }

 Status CreateDG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,构造有向图G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO],*info;
   VertexType va,vb;
   printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%*c",va,vb);  // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=1; // 有向图
     if(IncInfo)
     {
       printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         info=(char*)malloc((l+1)*sizeof(char));
         strcpy(info,s);
         G.arcs[i][j].info=info; // 有向
       }
     }
   }
   G.kind=DG;
   return OK;
 }

 Status CreateDN(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,构造有向网G
   int i,j,k,w,IncInfo;
   char s[MAX_INFO],*info;
   VertexType va,vb;
   printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   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;
     }
   printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%d%*c",va,vb,&w);  // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=w; // 有向网
     if(IncInfo)
     {
       printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       w=strlen(s);
       if(w)
       {
         info=(char*)malloc((w+1)*sizeof(char));
         strcpy(info,s);
         G.arcs[i][j].info=info; // 有向
       }
     }
   }
   G.kind=DN;
   return OK;
 }

 Status CreateAG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,构造无向图G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO],*info;
   VertexType va,vb;
   printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%*c",va,vb); // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 无向图
     if(IncInfo)
     {
       printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         info=(char*)malloc((l+1)*sizeof(char));
         strcpy(info,s);
         G.arcs[i][j].info=G.arcs[j][i].info=info; // 无向
       }
     }
   }
   G.kind=AG;
   return OK;
 }

 Status CreateAN(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,构造无向网G。算法7.2
   int i,j,k,w,IncInfo;
   char s[MAX_INFO],*info;
   VertexType va,vb;
   printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   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;
     }
   printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=w; // 无向
     if(IncInfo)
     {
       printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       w=strlen(s);
       if(w)
       {
         info=(char*)malloc((w+1)*sizeof(char));
         strcpy(info,s);
         G.arcs[i][j].info=G.arcs[j][i].info=info; // 无向
       }
     }
   }
   G.kind=AN;
   return OK;
 }

 Status CreateGraph(MGraph &G)
 { // 采用数组(邻接矩阵)表示法,构造图G。算法7.1
   printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
   scanf("%d",&G.kind);
   switch(G.kind)
   {
     case DG: return CreateDG(G); // 构造有向图
     case DN: return CreateDN(G); // 构造有向网
     case AG: return CreateAG(G); // 构造无向图
     case AN: return CreateAN(G); // 构造无向网
     default: return ERROR;
   }
 }

 void DestroyGraph(MGraph &G)
 { // 初始条件: 图G存在。操作结果: 销毁图G
   int i,j;
   if(G.kind<2) // 有向
     for(i=0;i<G.vexnum;i++) // 释放弧的相关信息(如果有的话)
     {
       for(j=0;j<G.vexnum;j++)
         if(G.arcs[i][j].adj==1&&G.kind==0||G.arcs[i][j].adj!=INFINITY&&G.kind==1) // 有向图的弧||有向网的弧
           if(G.arcs[i][j].info) // 有相关信息
           {
             free(G.arcs[i][j].info);
             G.arcs[i][j].info=NULL;
           }
     }
   else // 无向
     for(i=0;i<G.vexnum;i++) // 释放边的相关信息(如果有的话)
       for(j=i+1;j<G.vexnum;j++)
         if(G.arcs[i][j].adj==1&&G.kind==2||G.arcs[i][j].adj!=INFINITY&&G.kind==3) // 无向图的边||无向网的边
           if(G.arcs[i][j].info) // 有相关信息
           {
             free(G.arcs[i][j].info);
             G.arcs[i][j].info=G.arcs[j][i].info=NULL;
           }
   G.vexnum=0;
   G.arcnum=0;
 }

 VertexType& GetVex(MGraph G,int v)
 { // 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值
   if(v>=G.vexnum||v<0)
     exit(ERROR);
   return G.vexs[v];
 }

 Status PutVex(MGraph &G,VertexType v,VertexType value)
 { // 初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value
   int k;
   k=LocateVex(G,v); // k为顶点v在图G中的序号
   if(k<0)
     return ERROR;
   strcpy(G.vexs[k],value);
   return OK;
 }

 int FirstAdjVex(MGraph G,VertexType v)
 { // 初始条件: 图G存在,v是G中某个顶点