#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<string.h>
#define MAX_NAME 5//顶点字符串的最大长度+1
#define MAX_INFO 20//相关信息字符串的最大长度+1
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX // 用整型最大值代替∞
#define MAX_VEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef struct
{
VRType adj;//顶点关系类型。对无权图，用1(是)或0(否)表示相邻否;对带权图，c则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];
typedef struct
{
VertexType vexs[MAX_VEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;//当前顶点数和弧数
GraphKind kind;
}MGraph;
/* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
/*获取定点在定点向量中的位置 如果出错就终止运行*/
int LocateVex(MGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
/* 采用数组(邻接矩阵)表示法,构造有向图G */
int createDG(MGraph *G)
{
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向图的顶点数，弧数，弧是否含有其他信息(是:1,否:0):\n");
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个字符):\n",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 1;
}
/* 采用数组(邻接矩阵)表示法,构造有向网G */
int createDN(MGraph *G)
{
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向网G的顶点数，弧数，弧是否含有其他信息(是:1,否:0)\n");
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 1;
}
/* 采用数组(邻接矩阵)表示法,构造无向图G */
int createUDG(MGraph *G)
{
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向图G的顶点数，边数，边是否含有其他信息(是:1,否:2):\n");
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=UDG;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int createUDN(MGraph *G)
{
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n");
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=UDN;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造图G*/
int createGraph(MGraph *G)
{
printf("请输入G的类型(有向图:0,有向网:1,无向图:2,无向网:3):\n");
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 0;
}
}
/* 输出邻接矩阵G */
void displayGraph(MGraph G)
{
int i,j;
char s[7],s1[3];
switch(G.kind)
{
case DG:
strcpy(s,"有向图\0");
strcpy(s1,"弧\0");
break;
case DN:
strcpy(s,"有向网\0");
strcpy(s1,"弧\0");
break;
case UDG:
strcpy(s,"无向图\0");
strcpy(s1,"边\0");
break;
case UDN:
strcpy(s,"无向网\0");
strcpy(s1,"边\0");
break;
}
printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s);
for(i=0;i<G.vexnum;++i) /* 输出G.vexs */
printf("G.vexs[%d]=%s\n",i,G.vexs[i]);
printf("G.arcs.adj:\n"); /* 输出G.arcs.adj */
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%6d",G.arcs[i][j].adj);
printf("\n");
}
printf("G.arc.info:\n");//输出G.arcs.info
printf("顶点1(弧尾) 顶点2(弧头) 该%s信息：\n",s1);
if(G.kind<2)//有向
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].info)
printf("%5s%11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
else//无向
{
for(i=0;i<G.vexnum;i++)
for(j=i+1;j<G.vexnum;j++)
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
}
/*初始化条件:图G存在*/
/*操作结果:销毁图G*/
void destroyGraph(MGraph *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||(*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;
printf("图销毁成功!");
printf("\n\n");
}
int main()
{
int i;
MGraph G;
for(i=0;i<3;i++)
{
createGraph(&G);
displayGraph(G);
destroyGraph(&G);
}
return 0;
}
分享到：
相关推荐
这个是我学数据结构是老师留的上机作业，主要就是图的创建与输出，分四种分别为有向图，无向图，有向网，无向网，通过选择类型来选择图的种类
无向图 有向图 有向网 无向网 深度优先遍历 Ｃ语言 用户操纵界面
有向和无向的区别：有向直接标出谁指向谁，无向是有向的特例，,v2>有弧，说明,v1>也有弧。 构图： ① 确定顶点数，弧数，是否有权值 ② 输入每个顶点，弧<弧尾，弧头>，权值 ③ 若是无向，则需实现弧,v1>与,v2>的...
邻接矩阵构造无向图、网，有向图、网，在各版本vs下可运行
根据网络邻接矩阵画出有向图或无向图 可用于交通、电能等网络的可视化
含代码和报告 ...3. 项目三：任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
对任意给定的图（顶点数不小于20，边数不少于30，图的类型可以是有向图、无向图、有向网、无向网），能够输入图的顶点和边（或弧）的信息，并存储到相应存储结构（邻接矩阵、邻接表、十字链表、邻接多重表，任选其中...
这里有一点一定要注意，因为为无向图，因此邻接矩阵一定要是关于对角线对称的，即Aij=Aji（且对角线上元素Aii=0），两点之间相互无向连接，有向图可以不为对称矩阵（有方向） 方法及函数： 1.推荐matlab一个图论很...
问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题． 基本要求：用邻接矩阵表示...
无向图的基本操作及应用： 创建无向图的邻接矩阵（5.1.1）； ② 创建无向图的邻接表（5.1.2）； ③ 无向图的深度优先遍历（5.1.3）； ④ 无向图的广度优先遍历（5.1.4）。 2． 无向网的基本操作及应用 ① 创建无向...
图的基本存储结构和运算算法的实现； 构建无向图，有向图，无向网，有向网； 插入或删除一个元素；
有向图，无向图，有向网，无向网任选一种。 2、深度优先遍历以及广度优先遍历 问题描述：从键盘输入数据建立图并打印深度优先遍历序列和广度优先遍历序列。 实验提示: 图的存储可采用邻接矩阵或邻接表； 有向图...
有向图，无向图，有向网，无向网任选一种。 2、深度优先遍历以及广度优先遍历 问题描述：从键盘输入数据建立图并打印深度优先遍历序列和广度优先遍历序列。 实验提示: 图的存储可采用邻接矩阵或邻接表； 有向图...
图的算法的基本训练 1、 图的存储结构的定义和图的创建图的种类有：有向图、无向图、有向网、无向网。图的存储结构可采用：邻接矩阵、邻接表。要求：分别给出邻接矩阵和邻接表在某一种图上的创建算法 2、 图的遍历：...
图论的基本知识：无向图与有向图、树和二叉树、赋权图与 网络。 图的搜索算法：二叉树与一般树的搜索算法（先根次序、中 根次序与后根次序）、图的搜索算法（宽度优先与深度优先）、 连通图的深度优先与宽度优先...
有向图 B．无向图 C．AOV网 D．AOE网 2．在边表示活动的AOE网中，关键活动的最迟开始时间（ ） 最早开始时间。 A．> B．< C．>= D．= 3．带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ） 。 A...
数据结构最短路径算法实现，可实现有向图，无向图，有向网，无向网四种最短路径求解，最后打印路径，和路径长度。
数据结构图的创建及遍历，矩阵表示，邻接表表示，无向图，无向网，有向图，有向网
请输入建图类型(1:无权有向图、2:带权有向网、3:无权无向图、4:带权无向网): 3 建立无权无向图，请依次输入总结点数、总边数、是否包含信息: 8 8 0 请为从1至n个结点命名: V1 V2 V3 V4 V5 V6 V7 V8 请输入8组相互...
C++实现图的深搜/广搜。有向图，有向网，无向图，无向网，结构创建与搜索遍历均实现。