实验五图应用.doc

上海建桥学院本科数据结构实验报告（五） 课程名称：数据结构实验类型：综合实验室名称：机房开课学院：信息技术学院学生姓名：童宇奇专业：数字媒体艺术学号：10B01130141指导老师： 陈莲君实验五：图应用实验日期： 2011 年 11 月 23 日 评阅成绩： 实验目的及要求1. 熟练掌握图的邻接矩阵和邻接表的存储方式；2. 实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D.，而非键盘输入），分别用dfs（深度优先搜索）和bfs(广度优先搜索)遍历，输出图中顶点信息并验证。邻接矩阵图类型定义：#define MAX 40 typedef char vexType; /*顶点类型*/ typedef struct vexType vexMAX; int arcsMAXMAX; int vn,en; MGraph; 顺序存储的循环队列类型定义：typedef int datatype; /*队列元素为图的顶点下标,int型*/typedef struct node datatype dataMAX; int front, rear; SeqQueue; /*顺序存储的循环队列类型*/任务1自定义函数库文件Queue.h，完成队列的相关操作。2创建一个程序文件sy5.cpp，自定义相应函数完成以下操作：（1）void createGraph(MGraph *g) /*建邻接矩阵存储的无向图*/（2）void visit(MGraph *g,int v) /*访问v号顶点*/（3）void dfs(MGraph *g,int v) /*邻接矩阵存储的图的深度优先搜索*/（4）void bfs(MGraph *g,int v) /*邻接矩阵存储的图的广度优先搜索*/3 自定义函数库文件Queue.h 与sy5.cpp源程序清单（含必要的注释） sy5.cpp：#define MAX 40#include Queue.hint visitedMAX;typedef char vexType; /*顶点类型*/typedef structvexType vexMAX;int arcsMAXMAX;int vn,en; MGraph;void createGraph(MGraph *g); /*建邻接矩阵存储的无向图*/void visit(MGraph *g,int v); /*访问v号顶点*/void dfs(MGraph *g,int v); /*邻接矩阵存储的图的深度优先搜索*/void bfs(MGraph *g,int v); /*邻接矩阵存储的图的广度优先搜索*/void main()MGraph g;int i,v;createGraph(&g); /*建图*/for(i=0;ig.vn;i+) /*标记数组初始化*/visitedi=0;printf(开始顶点:); /*输入遍历开始顶点*/scanf(%d,&v);printf(输出(dfs):); /*DFS输出*/dfs(&g,v);printf(n);for(i=0;ivn);printf(输入边数:);scanf(%d,&g-en);for(i=0;ivn;i+) /*二维数组初始化*/for(j=0;jvn;j+)g-arcsij=0;for(v=0;vvn;v+) /*确定数据*/g-vexv=a;a+;printf(输入结构:n); /*确定边*/for(v=0;ven;v+)scanf(%d %d,&i,&j);g-arcsij=1;g-arcsji=1;void visit(MGraph *g,int v)printf(%c,g-vexv); void dfs(MGraph *g,int v)int j;visit(g,v); /*输出数据*/visitedv=1; /*标记已访问*/for(j=0;jvn;j+)if(g-arcsvj=1 & visitedj=0)dfs(g,j); /*递归*/ void bfs(MGraph *g,int v) int i,w; SeqQueue Q; InitQueue(&Q); /*队列初始化*/EnQueue(&Q,v); /*入队*/visitedv=1; /*标记已访问*/ while(!EmptyQueue(&Q)w=DeQueue(&Q); /*出队*/visit(g,w); /*输出数据*/for(i=0;ivn;i+)if(g-arcswi=1 & visitedi=0)EnQueue(&Q,i); /*入队*/visitedi=1; /*标记已访问*/Queue.h：#include typedef int datatype; /*队列元素为图的顶点下标,int型*/typedef struct nodedatatype dataMAX;int front, rear; SeqQueue; /*顺序存储的循环队列类型*/void InitQueue(SeqQueue *Q); /*初始化队列*/void EnQueue(SeqQueue *Q,int v); /*入队*/datatype DeQueue(SeqQueue *Q); /*出队*/int EmptyQueue(SeqQueue *Q); /*判队空*/int FullQueue(SeqQueue *Q); /*判队满*/void InitQueue(SeqQueue *Q)Q-front=Q-rear=0;void EnQueue(SeqQueue *Q,int v)if(FullQueue(Q)printf(队列已满); /*判队满*/return;Q-rear=(Q-rear+1)%MAX; /*入队*/Q-dataQ-rear=v;datatype DeQueue(SeqQueue *Q)if(EmptyQueue(Q)printf(队列为空); /*判队空*/return -1;Q-front=(Q-front+1)%MAX; /*出队*/return Q-dataQ-front;int EmptyQueue(SeqQueue *Q)return Q-front=Q-rear;int FullQueue(SeqQueue *Q)return (Q-rear+1)%MAX=Q-front;3 程序运行结果的屏幕拷贝内容 A图结构： B C D E实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等） 通过这次试验，我渐渐熟悉了关于图的算法