《数据结构C语言版 图的邻接表存储表示和实现.doc》由会员分享，可在线阅读，更多相关《数据结构C语言版 图的邻接表存储表示和实现.doc（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构C语言版 图的邻接表存储表示和实现.txt如果青春的时光在闲散中度过，那么回忆岁月将是一场凄凉的悲剧。杂草多的地方庄稼少，空话多的地方智慧少。即使路上没有花朵，我仍可以欣赏荒芜。/*数据结构C语言版 图的邻接表存储表示和实现P163 编译环境：Dev-C+ 4.9.9.2日期：2011年2月15日 */#include / 图的邻接表存储表示 #define MAX_NAME 3/ 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20typedef int InfoType;/ 存放网的权值 typedef char VertexTypeMAX_NAME;/ 字
2、符串类型 typedef enumDG,DN,AG,ANGraphKind; / 有向图,有向网,无向图,无向网 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 InfoType *info;/ 网的权值指针） ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结
3、点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 ALGraph;typedef int QElemType; / 队列类型 / 单链队列队列的链式存储结构 typedef struct QNodeQElemType data;/数据域struct QNode *next;/指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素rear;/队尾指针，指向队尾元素LinkQueue;/ 若G中存在顶点u,则返回该
4、顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u)int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.verticesi.data)=0)return i;return -1;/ 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。int CreateGraph(ALGraph *G)int i,j,k;int w;/ 权值 VertexType va,vb;ArcNode *p;printf(请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): );scanf(%d,&(*G)
5、.kind);printf(请输入图的顶点数和边数:（空格）n);scanf(%d%d, &(*G).vexnum, &(*G).arcnum);printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i = 0; i (*G).vexnum; +i)/ 构造顶点向量 scanf(%s, (*G).verticesi.data);(*G).verticesi.firstarc = NULL;if(*G).kind = 1 | (*G).kind = 3) / 网 printf(请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):n);e
6、lse / 图 printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n);for(k = 0;k adjvex = j;if(*G).kind = 1 | (*G).kind = 3) / 网 p-info = (int *)malloc(sizeof(int);*(p-info) = w;elsep-info = NULL; / 图 p-nextarc = (*G).verticesi.firstarc; / 插在表头 (*G).verticesi.firstarc = p;if(*G).kind = 2) / 无向图或网,产生第二个表结点 p = (ArcNode*)mal
7、loc(sizeof(ArcNode);p-adjvex = i;if(*G).kind = 3) / 无向网 p-info = (int*)malloc(sizeof(int);*(p-info) = w;elsep-info = NULL; / 无向图 p-nextarc = (*G).verticesj.firstarc; / 插在表头 (*G).verticesj.firstarc = p;return 1;/ 销毁图G。void DestroyGraph(ALGraph *G)int i;ArcNode *p,*q;for(i = 0;i nextarc;if(*G).kind%2)
8、 / 网 free(p-info);free(p);p=q;(*G).vexnum=0;(*G).arcnum=0; / 返回v的值。VertexType* GetVex(ALGraph G,int v)if(v=G.vexnum|v -1) / v是G的顶点 strcpy(*G).verticesi.data,value);return 1;return 0;/ 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。int FirstAdjVex(ALGraph G,VertexType v)ArcNode *p;int v1;v1 = LocateVex(G,v); / v1
9、为顶点v在图G中的序号 p = G.verticesv1.firstarc;if(p)return p-adjvex;elsereturn -1;/ 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个/ 邻接点,则返回-1。int NextAdjVex(ALGraph G,VertexType v,VertexType w)ArcNode *p;int v1,w1;v1 = LocateVex(G,v); / v1为顶点v在图G中的序号 w1 = LocateVex(G,w); / w1为顶点w在图G中的序号 p = G.verticesv1.firstarc;while(p&p-
10、adjvex != w1) / 指针p不空且所指表结点不是w p = p-nextarc;if(!p|!p-nextarc) / 没找到w或w是最后一个邻接点 return -1;else / p-adjvex=w / 返回v的(相对于w的)下一个邻接顶点的序号 return p-nextarc-adjvex;/ 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)。void InsertVex(ALGraph *G,VertexType v) strcpy(*G).vertices(*G).vexnum.data,v); / 构造新顶点向量 (*G).vertices
11、(*G).vexnum.firstarc=NULL;(*G).vexnum+; / 图G的顶点数加1 / 删除G中顶点v及其相关的弧。int DeleteVex(ALGraph *G,VertexType v)int i,j;ArcNode *p,*q;j=LocateVex(*G,v);/ j是顶点v的序号 if(j nextarc;if(*G).kind % 2)/ 网 free(q-info);free(q);(*G).arcnum-;/ 弧或边数减1 (*G).vexnum-;/ 顶点数减1 for(i = j; i (*G).vexnum; i+)/ 顶点v后面的顶点前移 (*G).verticesi = (*G).verticesi+1;/ 删除以v为入度的弧或边且必要时修改表结点的顶点位置值for(i = 0; i adjvex = j)/ 是以v为入度的边。if
