typedef struct ArcCell{ VRType adj;//VRType是顶点关系类型.对无权图,用1或0表示相邻否 //对带权图,则为权值类型 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;
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 j,k,l; char filename[13]; VertexType va,vb; FILE *graphlist; cout<<"请输入文件名(f7-1.dat): "; cin>>filename; //graphlist=fopen(filename,"r"); fscanf(graphlist,"%d",&(*G).vexnum);//输入顶点数 fscanf(graphlist,&(*G).arcnum);//输入弧数 for(l=0;l<(*G).vexnum;++l)/*构造顶点向量*/ fscanf(graphlist,"%s",(*G).vexs[l]); for(int i=0;i<(*G).vexnum;++i)/*初始化邻接矩阵*/ for(int 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,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",vb);/* %*c吃掉回车符*/ i=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) {/*采用数组(邻接矩阵)表示法,构造有向网*/ int i,w,vb; printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,(*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",vb,&w);// %*c吃掉回车符 i=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) {/*采用数组(邻接矩阵)表示法,构造无向图*/ int i,vb; printf("请输入无向图G的顶点数,边数,边是否包含其它信息(是:1,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",vb);//%*c吃掉回车符 i=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1;//无向图 if(IncInfo) { printf("请输入该边的相关信息(<%d个字符):",s); (*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向 } } } (*G).kind=AG; return OK; }
Status CreateAN(MGraph *G) {/*采用数组(邻接矩阵)表示法,构造有向图*/ int i,vb; printf("请输入无向网G的顶点数,边是否含其它信息(是:1,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("请输入%条边的顶点1顶点2权值(以空格作为间隔):/n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k) { scanf("%s%s$d%*c",&w);//%*c吃掉回车符 i=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;//无向 if(IncInfo) { printf("请输入该边的相关信息(<%d个字符):",s); (*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向 } } } (*G).kind=AN; return OK; }
Status CreateGraph(MGraph *G) { /*采用数组(邻接矩阵)表示法,构造图G*/ 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 CreateDN(G);//构造无向图 case AN:return CreateAN(G);//构造无向网 default:return ERROR; } } (编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|