數(shù)據(jù)結(jié)構(gòu)圖的遍歷5頁(yè)

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;t

2、ypedef 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 ve

3、rtices;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(&

4、quot;請(qǐng)輸入圖頂點(diǎn)數(shù)、邊數(shù)及該邊相關(guān)信息:");scanf("%d %d %d",&g->vexnum,&g->arcnum,&incinfo);printf("請(qǐng)輸入頂點(diǎn)信息:");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(

5、"輸入一條邊依附的頂點(diǎn):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->=&incinfo;g->arcsji.adj=g->arcsij.adj;g->=g->;flu

6、shall();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(

7、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+)v

8、isv=FALSE;printf("輸入遍歷開(kāi)始頂點(diǎn):");flushall();scanf("%c",&f);i=locatevex_hc(g,f);printf("深度遍歷結(jié)果為:");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

9、->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=ne

10、xtl;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("請(qǐng)輸入圖頂點(diǎn)數(shù)、邊數(shù)及該邊相關(guān)信息:");scanf("%d %d %d",&a->vexnum,&a->arcnum,&incinf

11、o);printf("請(qǐng)輸入頂點(diǎn)信息:");flushall();for(i=0;i<a->vexnum;+i)scanf("%c",&a->verticesi.data);for(i=0;i<a->vexnum;+i)printf("輸入%c的鄰接點(diǎn):",a->verticesi.data);flushall();scanf("%c",&v);a->verticesi.firstarc=(arcnode_hc*)malloc(sizeof(arcnode_

12、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

13、,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("遍歷開(kāi)始頂點(diǎn):");flushall()

14、;scanf("%c",&f);k=locatevexal_hc(a,f);printf("深度遍歷結(jié)果:");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("請(qǐng)選擇:");c=getchar();wh