数据结构C/C++版源代码 严蔚敏

/* bo7-1.c 图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作(21个)，包括算法7.1、 */ /* 7.2、算法7.4～7.6 */ 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; } void CreateFUDG(MGraph *G) { /* 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向图G */ int i,j,k; char filename[13]; VertexType va,vb; FILE *graphlist; printf("请输入数据文件名(f7-1.txt或f7-2.txt)："); scanf("%s",filename); graphlist=fopen(filename,"r");/* 打开数据文件，并以graphlist表示 */ 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=UDG; } void CreateFUDN(MGraph *G) { /* 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向网G */ int i,j,k,w; char filename[13]; VertexType va,vb; FILE *graphlist; printf("请输入数据文件名："); scanf("%s",filename); graphlist=fopen(filename,"r"); /* 打开数据文件，并以graphlist表示 */ 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=INFINITY; /* 网 */ (*G).arcs[i][j].info=NULL; /* 没有相关信息 */ } for(k=0;k<(*G).arcnum;++k) { fscanf(graphlist,"%s%s%d",va,vb,&w); i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向网 */ } fclose(graphlist); /* 关闭数据文件 */ (*G).kind=UDN; } void CreateDG(MGraph *G) { /* 采用数组(邻接矩阵)表示法，构造有向图G */ int i,j,k,l,IncInfo; char s[MAX_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) { (*G).arcs[i][j].info=(char*)malloc((l+1)*sizeof(char)); /* 有向 */ strcpy((*G).arcs[i][j].info,s); } } } (*G).kind=DG; } void CreateDN(MGraph *G) { /* 采用数组(邻接矩阵)表示法，构造有向网G */ int i,j,k,w,IncInfo; char s[MAX_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) { (*G).arcs[i][j].info=(char*)malloc((w+1)*sizeof(char)); /* 有向 */ strcpy((*G).arcs[i][j].info,s); } } } (*G).kind=DN; } void CreateUDG(MGraph *G) { /* 采用数组(邻接矩阵)表示法，构造无向图G */ int i,j,k,l,IncInfo; char s[MAX_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) { (*G).arcs[i][j].info=(*G).arcs[j][i].info=(char*)malloc((l+1)*sizeof(char)); /* 无向，两个指针指向同一个信息 */ strcpy((*G).arcs[i][j].info,s); } } } (*G).kind=UDG; } void CreateUDN(MGraph *G) { /* 采用数组(邻接矩阵)表示法，构造无向网G。算法7.2 */ int i,j,k,w,IncInfo; char s[MAX_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) { (*G).arcs[i][j].info=(*G).arcs[j][i].info=(char*)malloc((w+1)*sizeof(char)); /* 无向，两个指针指向同一个信息 */ strcpy((*G).arcs[i][j].info,s); } } } (*G).kind=UDN; } void CreateGraph(MGraph *G) { /* 采用数组(邻接矩阵)表示法，构造图G。算法7.1改 */ printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&(*G).kind); switch((*G).kind) { case DG: CreateDG(G); /* 构造有向图 */ break; case DN: CreateDN(G); /* 构造有向网 */ break; case UDG:CreateUDG(G); /* 构造无向图 */ break; case UDN:CreateUDN(G); /* 构造无向网 */ } } void DestroyGraph(MGraph *G) { /* 初始条件：图G存在。操作结果：销毁图G */ int i,j,k=0; if((*G).kind%2) /* 网 */ k=INFINITY; /* k为两顶点之间无边或弧时邻接矩阵元素的值 */ for(i=0;i<(*G).vexnum;i++) /* 释放弧或边的相关信息(如果有的话) */ if((*G).kind<2) /* 有向 */ { for(j=0;j<(*G).vexnum;j++) if((*