资源描述:
《数据结构图的遍历.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#include"stdlib.h"#include"stdio.h"#include"malloc.h"#defineINFINITY32767#defineMAX_VERTEX_NUM20typedefenum{FALSE,TRUE}visited_hc;typedefenum{DG,DN,UDG,UDN}graphkind_hc;typedefstructarccell_hc{intadj;int*info;}arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MA
2、X_VERTEX_NUM];adjmatrix_hcarcs;intvexnum,arcnum;graphkind_hckind;}mgraph_hc;typedefstructarcnode_hc{intadjvex;structarcnode_hc*nextarc;int*info;}arcnode_hc;typedefstructvnode_hc{chardata;arcnode_hc*firstarc;}vnode_hc,adjlist_hc[MAX_VERTEX_NUM];typedefstruct{adjlist_hcvertices;intvexnum,arcn
3、um;graphkind_hckind;}algraph_hc;intlocatevex_hc(mgraph_hc*g,charv){inti,k=0;for(i=0;ivexnum;i++)if(g->vexs[i]==v){k=i;i=g->vexnum;}return(k);}mgraph_hc*createudg_hc(){mgraph_hc*g;charv1,v2;inti,j,incinfo;g=(mgraph_hc*)malloc(sizeof(mgraph_hc));g->kind=UDG;printf("请输入图顶点数、边数及该边相关信息:");sc
4、anf("%d%d%d",&g->vexnum,&g->arcnum,&incinfo);printf("请输入顶点信息:");flushall();for(i=0;ivexnum;++i)scanf("%c",&g->vexs[i]);for(i=0;ivexnum;++i)for(j=0;jvexnum;++j)g->arcs[i][j].adj=0;printf("输入一条边依附的顶点:");flushall();scanf("%c%c",&v1,&v2);while(v1!='#'&&v2!='#'){i=locatevex_hc(g,v1
5、);j=locatevex_hc(g,v2);g->arcs[i][j].adj=1;if(incinfo)g->arcs[i][j].info=&incinfo;g->arcs[j][i].adj=g->arcs[i][j].adj;g->arcs[j][i].info=g->arcs[i][j].info;flushall();scanf("%c%c",&v1,&v2);}return(g);}visited_hcvis[MAX_VERTEX_NUM];intfirstadjvex_hc(mgraph_hc*g,intv){inti,k=-1;for(i=0;iv
6、exnum;i++)if(g->arcs[v][i].adj==1){k=i;i=g->vexnum;}return(k);}intnextadjvex_hc(mgraph_hc*g,intv,intw){inti,k=-1;for(i=0;ivexnum;i++)if(g->arcs[v][i].adj==1&&i>w){k=i;i=g->vexnum;}return(k);}voiddfs_hc(mgraph_hc*g,intv){intw;vis[v]=TRUE;printf("%c",g->vexs[v]);for(w=firstadjvex_hc(g,v);
7、w>=0;w=nextadjvex_hc(g,v,w))if(!vis[w])dfs_hc(g,w);}voiddfstraverse_hc(mgraph_hc*g){intv,i;charf;for(v=0;vvexnum;v++)vis[v]=FALSE;printf("输入遍历开始顶点:");flushall();scanf("%c",&f);i=locatevex_hc(g,f);printf("深度遍历结果为:");for(v=i;vvexnum;v++)if(!vis[v])