数据结构实验图的遍历.docVIP

南昌大学实验报告 学生姓名： 李木子 学 号： 8000113146 专业班级： 软工133 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩： 实验项目名称 图的遍历 实验目的 学会图的结构体定义,图的创建,图的深度遍历与广度遍历 实验基本原理 主要仪器设备及耗材 电脑，VC6.0 五、实验步骤 #includestdio.h #includestdlib.h #includemalloc.h #define M 20 typedef char datatype; /**************************************/ /* 图的结构体定义 */ /**************************************/ typedef struct node{ int adjvex; struct node *next; }edgenode; typedef struct vnode{ datatype vertex; edgenode *firstedge; }vertexnode; typedef struct { vertexnode adjlist[M]; int n,e; }linkedgraph; typedef vertexnode adjlist[M]; int visited[M]; /**************************************/ /* 函数声明 */ /**************************************/ void creat(linkedgraph *g,int c) ; void dfs(linkedgraph g,int i) ; void dfsTra(linkedgraph g) ; void Bfstr(linkedgraph *G,int k) ; int Bfs(linkedgraph *G) ; /**************************************/ /* 创建函数 */ /**************************************/ void creat(linkedgraph *g,int c) { int i,j,k; edgenode *s; printf(请输入顶点个数和边的个数：\n); scanf(%d%d,g-n,g-e); printf(输入各顶点的值:\n); for(i=0;ig-n;i++) { scanf(%1s,g-adjlist[i].vertex); g-adjlist[i].firstedge=NULL; } printf(输入各边的关系：\n); for(k=0;kg-e;k++) { printf(边%d\n,k); scanf(%d%d,i,j); s=(edgenode*)malloc(sizeof(edgenode)); s-adjvex=j; s-next=g-adjlist[i].firstedge; g-adjlist[i].firstedge=s; if(c==0) { s=(edgenode *)malloc(sizeof(edgenode)); s-adjvex=i; s-next=g-adjlist[j].firstedge; g-adjlist[j].firstedge=s; } } printf(成功！\n); } /**************************************/ /* 深度遍历 */ /**************************************/ void dfs(linkedgraph g,int i) { edgenode *p; printf(%c,g.adjlist[i].vertex); visited[i]=1; p=g.adjlist[i].firstedge; while(p) { if(!visited[p-adjvex]) dfs(g,p-adjvex); p=p-next; } } void dfsTra(linkedgraph g) { int i; for(i=0;ig.n;i++) visited[i]=0; for(i=0;ig.n;i++) if(!v