数据结构C语言版 图的邻接表存储表示和实现.doc

数据结构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;/ 字符串类型 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;/ 头结点 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,则返回该顶点在图中位置;否则返回-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).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);else / 图 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*)malloc(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) / 网 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为顶点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-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(*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(p = (*G).verticesi.firstarc) / 待删结点是第1个结点 (*G).verticesi.firstarc = p-nextarc;if(*G).kind % 2)/ 网 free(p-info);free(p);p = (*G).verticesi.firstarc;if(*G).kind nextarc = p-nextarc;if(*G).kind%2)/ 网 free(p-info);free(p);p = q-nextarc;if(*G).kind adjvex j)p-adjvex-; / 修改表结点的顶点位置值(序号) q = p;p = p-nextarc;return 1;/ 在G中增添弧,若G是无向的,则还增添对称弧。int InsertArc(ALGraph *G,VertexType v, VertexType w)ArcNode *p;int w1,i,j;i=LocateVex(*G,v); / 弧尾或边的序号 j=LocateVex(*G,w); / 弧头或边的序号 if(i 0 | j adjvex=j;if(*G).kind%2) / 网 p-info=(int*)malloc(sizeof(int);*(p-info)=w1;elsep-info = NULL;p-nextarc = (*G).verticesi.firstarc; / 插在表头 (*G).verticesi.firstarc = p;if(*G).kind = 2)/ 无向,生成另一个表结点 p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = i;if(*G).kind = 3) / 无向网 p-info = (int*)malloc(sizeof(int);*(p-info) = w1;elsep-info=NULL;p-nextarc=(*G).verticesj.firstarc; / 插在表头 (*G).verticesj.firstarc=p;return 1;/ 在G中删除弧,若G是无向的,则还删除对称弧。int DeleteArc(ALGraph *G,VertexType v,VertexType w)ArcNode *p,*q;int i,j;i = LocateVex(*G,v); / i是顶点v(弧尾)的序号 j = LocateVex(*G,w); / j是顶点w(弧头)的序号 if(i 0 | j adjvex!=j) / p不空且所指之弧不是待删除弧 / p指向下一条弧 q=p;p=p-nextarc;if(p&p-adjvex=j) / 找到弧 if(p=(*G).verticesi.firstarc) / p所指是第1条弧 (*G).verticesi.firstarc=p-nextarc; / 指向下一条弧 elseq-nextarc=p-nextarc; / 指向下一条弧 if(*G).kind%2) / 网 free(p-info);free(p); / 释放此结点 (*G).arcnum-; / 弧或边数减1 if(*G).kind=2) / 无向,删除对称弧 p=(*G).verticesj.firstarc; / p指隙鉾的第一条出弧 while(p&p-adjvex!=i) / p不空且所指之弧不是待删除弧 / p指向下一条弧 q=p;p=p-nextarc;if(p&p-adjvex=i) / 找到弧 if(p=(*G).verticesj.firstarc) / p所指是第1条弧 (*G).verticesj.firstarc=p-nextarc; / 指向下一条弧 elseq-nextarc=p-nextarc; / 指向下一条弧 if(*G).kind=3) / 无向网 free(p-info);free(p); / 释放此结点 return 1;int visitedMAX_VERTEX_NUM;/ 访问标志数组(全局量) void(*VisitFunc)(char* v);/ 函数变量(全局量) /算法7.5 P169/从第v个顶点出发递归地深度优先遍历图G。void DFS(ALGraph G,int v)int w;VertexType v1,w1;strcpy(v1,*GetVex(G,v);visitedv = 1;/ 设置访问标志为1(已访问) VisitFunc(G.verticesv.data); / 访问第v个顶点 for(w = FirstAdjVex(G,v1); w = 0;w = NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)if(!visitedw)DFS(G,w);/ 对v的尚未访问的邻接点w递归调用DFS /算法7.4 P169/对图G作深度优先遍历。void DFSTraverse(ALGraph G,void(*Visit)(char*)int v;/ 使用全局变量VisitFunc,使DFS不必设函数指针参数VisitFunc = Visit; for(v = 0; v G.vexnum; v+)visitedv = 0;/ 访问标志数组初始化 for(v = 0; v next = NULL;/队头指针指向空，无数据域，这样构成了一个空队列return 1;/ 插入元素e为Q的新的队尾元素。int EnQueue(LinkQueue *Q, QElemType e)QueuePtr p = (QueuePtr)malloc(sizeof(QNode);if( !p )/ 存储分配失败 exit(0);/ 生成一个以为e为数据域的队列元素p-data = e;p-next = NULL;/将该新队列元素接在队尾的后面(*Q).rear-next = p;(*Q).rear = p;return 1;/ 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0。int DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if(*Q).front=(*Q).rear)return 0;p=(*Q).front-next;/队头元素*e=p-data;(*Q).front-next=p-next;if(*Q).rear=p)(*Q).rear=(*Q).front;free(p);return 1;/若Q为空队列,则返回1,否则返回0。int QueueEmpty(LinkQueue Q)if(Q.front = Q.rear)return 1;elsereturn 0;/算法7.6 P170/按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。void BFSTraverse(ALGraph G,void(*Visit)(char*)int v,u,w;VertexType u1,w1;LinkQueue Q;for(v = 0; v G.vexnum; +v)visitedv=0;/ 置初值 InitQueue(&Q);/ 置空的辅助队列Q for(v = 0; v = 0; w = NextAdjVex(G, u1, strcpy(w1, *GetVex(G,w)if(!visitedw)/ w为u的尚未访问的邻接顶点 visitedw = 1;Visit(G.verticesw.data);EnQueue(&Q,w);/ w入队 printf(n);/输出图的邻接表G。void Display(ALGraph G)int i;ArcNode *p;switch(G.kind)case DG: printf(有向图n);break;case DN: printf(有向网n);break;case AG: printf(无向图n);break;case AN: printf(无向网n);printf(%d个顶点：n,G.vexnum);for(i = 0; i G.vexnum; +i)printf(%s ,G.verticesi.data);printf(n%d条弧(边):n, G.arcnum);for(i = 0; i G.vexnum; i+)p = G.verticesi.firstarc;while(p)if(G.kind adjvex.data);if(G.kind = DN) / 网 printf(:%d , *(p-info);else/ 无向(避免输出两次) if(i adjvex)printf(%s%s ,G.verticesi.data,G.verticesp-adjvex.data);if(G.kind = AN)/ 网 printf(:%d ,*(p-info);p=p-nextarc;printf(n);void print(char *i)printf(%s ,i);int main()int i,j,k,n;ALGraph g;VertexType v1,v2;printf(请选择有向图n);CreateGraph(&g);Display(g);printf(删除一条边或弧，请输入待删除边或弧的弧尾 弧头：);scanf(%s%s,v1,v2);DeleteArc(&g,v1,v2);Display(g);printf(修改顶点的值，请输入原值 新值: );scanf(%s%s,v1,v2);PutVex(&g,v1,v2);Display(g);printf(插入新顶点，请输入顶点的值: );scanf(%s,v1);InsertVex(&g,v1);Display(g);printf(插入与新顶点有关的弧或边，请输入弧或边数目: );scanf(%d,&n);for(k=0;kn;k+)printf(请输入另一顶点的值: );scanf(%s,v2);printf(对于有向图，请输入另一顶点的方向(0:弧头 1:弧尾): );scanf(%d,&j);if(j)InsertArc(&g,v2,v1);elseInsertArc(&g,v1,v2);Display(g);printf(删除顶点及相关的弧或边，请输入顶点的值: );scanf(%s,v1);DeleteVex(&g,v1);Display(g);printf(深度优先搜索的结果:n);DFSTraverse(g,print);printf(广度优先搜索的结果:n);BFSTraverse(g,print);DestroyGraph(&g);#if 0 printf(请顺序选择有向网,无向图,无向网n);for(i=0;i3;i+) / 验证另外3种情况 CreateGraph(&g);Display(g);p