數(shù)據(jù)結構圖的遍歷.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;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(請輸入圖頂點數(shù)、邊數(shù)及該邊相關信息:);scanf(%d %d %d,&g-vexnum,&g-arcnum,&incinfo);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)=&incinfo;g-arcsji.adj=g-arcsij.adj;=;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-arcsvi.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=locatevex_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(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(請輸入圖頂點數(shù)、邊數(shù)及該邊相關信息:);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-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;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.firstarc,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=ge