数据结构图的遍历.doc
#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;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_hc kind;algraph_hc;int locatevex_hc(mgraph_hc*g,char v)int i,k=0;for(i=0;i<g->vexnum;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,&incinfo);printf("请输入顶点信息:");flushall();for(i=0;i<g->vexnum;+i)scanf("%c",&g->vexsi);for(i=0;i<g->vexnum;+i)for(j=0;j<g->vexnum;+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->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;i<g->vexnum;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;i<g->vexnum;i+)if(g->arcsvi.adj=1&&i>w)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;v<g->vexnum;v+)visv=FALSE;printf("输入遍历开始顶点:");flushall();scanf("%c",&f);i=locatevex_hc(g,f);printf("深度遍历结果为:");for(v=i;v<g->vexnum;v+)if(!visv)dfs_hc(g,v);for(v=0;v<i;v+)if(!visv)dfs_hc(g,v);int locatevexal_hc(algraph_hc*a,char v)int i,k=0;for(i=0;i<a->vexnum;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(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->kind=UDG;printf("请输入图顶点数、边数及该边相关信息:");scanf("%d %d %d",&a->vexnum,&a->arcnum,&incinfo);printf("请输入顶点信息:");flushall();for(i=0;i<a->vexnum;+i)scanf("%c",&a->verticesi.data);for(i=0;i<a->vexnum;+i)printf("输入%c的邻接点:",a->verticesi.data);flushall();scanf("%c",&v);a->verticesi.firstarc=(arcnode_hc*)malloc(sizeof(arcnode_hc);a->verticesi.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);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;i<a->vexnum;i+)visi=FALSE;printf("遍历开始顶点:");flushall();scanf("%c",&f);k=locatevexal_hc(a,f);printf("深度遍历结果:");for(i=k;i<a->vexnum;i+)if(!visk)dfsal_hc(a,a->verticesi.firstarc,i);for(i=0;i<k;i+)if(!visk)dfsal_hc(a,a->verticesi.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
