数据结构图的遍历.doc

《数据结构图的遍历.doc》由会员分享，可在线阅读，更多相关《数据结构图的遍历.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include stdlib.h#include stdio.h#include malloc.h#define INFINITY 32767#define MAX_VERTEX_NUM 20typedef enumFALSE,TRUEvisited_hc;typedef enumDG,DN,UDG,UDNgraphkind_hc;typedef struct arccell_hcint adj;int *info;arccell_hc,adjmatrix_hcMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar vexsMAX_VERTEX_NUM

2、;adjmatrix_hc arcs;int vexnum,arcnum;graphkind_hc kind;mgraph_hc;typedef struct arcnode_hcint adjvex;struct arcnode_hc *nextarc;int *info;arcnode_hc;typedef struct vnode_hcchar data;arcnode_hc *firstarc;vnode_hc,adjlist_hcMAX_VERTEX_NUM;typedef structadjlist_hc vertices;int vexnum,arcnum;graphkind_h

3、c kind;algraph_hc;int locatevex_hc(mgraph_hc*g,char v)int i,k=0;for(i=0;ivexnum;i+)if(g-vexsi=v)k=i;i=g-vexnum;return(k);mgraph_hc*createudg_hc()mgraph_hc*g;char v1,v2;int i,j,incinfo;g=(mgraph_hc*)malloc(sizeof(mgraph_hc);g-kind=UDG;printf(请输入图顶点数、边数及该边相关信息:);scanf(%d %d %d,&g-vexnum,&g-arcnum,&inc

4、info);printf(请输入顶点信息:);flushall();for(i=0;ivexnum;+i)scanf(%c,&g-vexsi);for(i=0;ivexnum;+i)for(j=0;jvexnum;+j)g-arcsij.adj=0;printf(输入一条边依附的顶点:n);flushall();scanf(%c%c,&v1,&v2);while(v1!=#&v2!=#)i=locatevex_hc(g,v1);j=locatevex_hc(g,v2);g-arcsij.adj=1;if(incinfo)g-arcsij.info=&incinfo;g-arcsji.adj=g

5、-arcsij.adj;g-arcsji.info=g-arcsij.info;flushall();scanf(%c%c,&v1,&v2);return(g);visited_hc visMAX_VERTEX_NUM;int firstadjvex_hc(mgraph_hc*g,int v)int i,k=-1;for(i=0;ivexnum;i+)if(g-arcsvi.adj=1)k=i;i=g-vexnum;return(k);int nextadjvex_hc(mgraph_hc*g,int v,int w)int i,k=-1;for(i=0;ivexnum;i+)if(g-arc

6、svi.adj=1&iw)k=i;i=g-vexnum;return(k);void dfs_hc(mgraph_hc*g,int v)int w;visv=TRUE; printf(%c,g-vexsv);for(w=firstadjvex_hc(g,v);w=0;w=nextadjvex_hc(g,v,w)if(!visw)dfs_hc(g,w);void dfstraverse_hc(mgraph_hc*g)int v,i;char f;for(v=0;vvexnum;v+)visv=FALSE;printf(输入遍历开始顶点:);flushall();scanf(%c,&f);i=lo

7、catevex_hc(g,f);printf(深度遍历结果为:);for(v=i;vvexnum;v+)if(!visv)dfs_hc(g,v);for(v=0;vi;v+)if(!visv)dfs_hc(g,v);int locatevexal_hc(algraph_hc*a,char v)int i,k=0;for(i=0;ivexnum;i+)if(a-verticesi.data=v)k=i;i=a-vexnum;return(k);char createlist_hc(algraph_hc*a,arcnode_hc*firstl,char v)arcnode_hc*nextl;if(

8、v!=n)nextl=(arcnode_hc*)malloc(sizeof(arcnode_hc);nextl-adjvex=locatevexal_hc(a,v);nextl-nextarc=NULL;nextl-info=firstl-info;firstl-nextarc=nextl;scanf(%c,&v);v=createlist_hc(a,nextl,v);return(v);algraph_hc*createaludg_hc()algraph_hc*a;int i,incinfo;char v;a=(algraph_hc*)malloc(sizeof(algraph_hc);a-

9、kind=UDG;printf(请输入图顶点数、边数及该边相关信息:);scanf(%d %d %d,&a-vexnum,&a-arcnum,&incinfo);printf(请输入顶点信息:);flushall();for(i=0;ivexnum;+i)scanf(%c,&a-verticesi.data);for(i=0;ivexnum;+i)printf(输入%c的邻接点:,a-verticesi.data);flushall();scanf(%c,&v);a-verticesi.firstarc=(arcnode_hc*)malloc(sizeof(arcnode_hc);a-vert

10、icesi.firstarc-adjvex=locatevexal_hc(a,v);a-verticesi.firstarc-nextarc=NULL;if(incinfo)a-verticesi.firstarc-info=&incinfo;scanf(%c,&v);v=createlist_hc(a,a-verticesi.firstarc,v);return(a);visited_hc visMAX_VERTEX_NUM;void dfsal_hc(algraph_hc*a,arcnode_hc*b,int k)visk=TRUE;printf(%c,a-verticesk.data);

11、while(b)k=b-adjvex;if(!visk)b=a-verticesk.firstarc;dfsal_hc(a,b,k);else b=b-nextarc;void dfstraverseal_hc(algraph_hc*a)char f;int i=0,k;for(i=0;ivexnum;i+)visi=FALSE;printf(遍历开始顶点:);flushall();scanf(%c,&f);k=locatevexal_hc(a,f);printf(深度遍历结果:);for(i=k;ivexnum;i+)if(!visk)dfsal_hc(a,a-verticesi.first

12、arc,i);for(i=0;iverticesi.firstarc,i);void main()algraph_hc*a;mgraph_hc*g;char c;printf(邻接矩阵(M)n);printf(邻接表(A)n);printf(请选择:);c=getchar();while(c!=E)if(c=M)g=createudg_hc();dfstraverse_hc(g);else if(c=A)a=createaludg_hc();dfstraverseal_hc(a);printf(n请选择:);flushall();c=getchar();printf(作者:黄晨);V4V1V3V5V2G2HEDCA