图的广度周游数据结构程序设计.doc

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 图的广度周游 专业 软件工程 班级 学号 姓名 联系方式 指导教师 20 年 月 日目 录1、数据结构课程设计任务书2、总体设计3、算法的设计思想4、调试与测试：5、源程序清单和执行结果6、C程序设计总结7、致谢8、参考文献1、数据结构课程设计任务书1.1、题目图的广度周游1.2、要求1.掌握图的邻接表存储结构 ，2.掌握队列的基本运算实现 ，3.掌握图的邻接表的算法实现， 4.掌握图的广度优先搜索周游算法实现 。2、总体设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi=Vexnums结束NNYY3、算法的设计思想1)定义图的邻接表存储结构2）实现图的邻接表存储，即建立图的存储结构3）实现图的深度优先遍历4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。伪代码：1、定义邻接矩阵和队列的存取结构；2、创建图L： 1.置空图L-num=0； 2.输入顶点数目num； 3.i+,输入结点L-vexsi直到L-num;3、输出图L的各顶点；4、深度优先遍历图g中能访问的各个顶点 1.输入起点的下标qidian； 2.标志数组初始化markv=0; 3.for(v=qidian;vg.num+qidian;v+) / v1=v%g.num;if(markv1=0)DFS(g,v1,mark); /从第v1个点出发深度优先遍历图g中能访问的各个顶点 （算法描述里的流程图很详细）5、广度优先周游图g中能访问的各个顶点。 1.构造空队列； 2.入队a0； 3.a0出队，a0的邻接点入队，遍历a0； 4.队首出队，重复3直到队列为空； 5.判断是否全遍历完了； 6.输出广度优先遍历序列。4、 调试与测试：5、源程序清单和执行结果#include #include #include #define MAX_VERTEX_NUM 20 /图的最大顶点数#define MAXQSIZE 30 /队列的最大容量 enum BOOL False,True;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; /弧结点typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一条依附该顶点的弧的指针 int vexnum,arcnum; /图的当前顶点和弧数 int GraphKind; /图的种类，0-无向图，1-有向图Graph; typedef struct /队列结构int elemMAXQSIZE; /数据域 int front; /队头指针 int rear; /队尾指针SqQueue; BOOL visitedMAX_VERTEX_NUM; /全局变量访问标志数组void CreateGraph(Graph &); /生成图的邻接表void DFSTraverse(Graph); /深度优先搜索遍历图void DFS(Graph,int); void BFSTraverse(Graph); /广度优先搜索遍历图void Initial(SqQueue &); /初始化一个队列BOOL QueueEmpty(SqQueue); /判断队列是否空BOOL EnQueue(SqQueue &,int); /将一个元素入队列BOOL DeQueue(SqQueue &,int &); /将一个元素出队列int FirstAdjVex(Graph,int); /求图中某一顶点的第一个邻接顶点int NextAdjVex(Graph,int,int); /求某一顶点的下一个邻接顶点void main()Graph G; /采用邻接表结构的图 char j=y; /-程序解说- printf(本程序将演示生成一个图，并对它进行遍历.n); printf(首先输入要生成的图的种类.n); printf(0-无向图, 1-有向图n); printf(之后输入图的顶点数和弧数。n格式：顶点数，弧数；例如:4,3n); printf(接着输入各边(弧尾，弧头).n例如:n1,2n1,3n2,4n); printf(程序会生成一个图，并对它进行深度和广度遍历.n); printf(深度遍历:1-2-4-3n广度遍历:1-2-3-4n); /- while(j!=N&j!=n) printf(请输入要生成的图的种类(0/1):); scanf(%d,&G.GraphKind); /输入图的种类 printf(请输入顶点数和弧数：); scanf(%d,%d,&G.vexnum,&G.arcnum); /输入图的顶点数和弧数 CreateGraph(G); /生成邻接表结构的图 DFSTraverse(G); /深度优先搜索遍历图 BFSTraverse(G); /广度优先搜索遍历图 printf(图遍历完毕，继续进行吗?(Y/N); scanf( %c,&j); void CreateGraph(Graph &G)/构造邻接表结构的图G int i; int start,end; ArcNode *s; for(i=1;i=G.vexnum;i+) G.AdjListi=NULL; /初始化指针数组 for(i=1;inextarc=G.AdjListstart; /插入到邻接表中 s-adjvex=end; G.AdjListstart=s; if(G.GraphKind=0) /若是无向图，再插入到终点的弧链中 s=(ArcNode *)malloc(sizeof(ArcNode); s-nextarc=G.AdjListend; s-adjvex=start; G.AdjListend=s; void DFSTraverse(Graph G)/深度优先遍历图G int i; printf(DFSTraverse:); for(i=1;i=G.vexnum;i+) visitedi=False; /访问标志数组初始化 for(i=1;i,i); for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w) if(!visitedw) DFS(G,w); /对尚未访问的邻接顶点w调用DFS void BFSTraverse(Graph G)/按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited int i,u,w; SqQueue Q; printf(BFSTreverse:); for(i=1;i= G.vexnum;i+) visitedi=False; /访问标志数组初始化 Initial(Q); /初始化队列 for(i=1;i,i); EnQueue(Q,i); /将序号i入队列 while(!QueueEmpty(Q) /若队列不空，继续 DeQueue(Q,u); /将队头元素出队列并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) /对u的尚未访问的邻接顶点w进行访问并入队列 visitedw=True; printf(%d-,w); EnQueue(Q,w); printf(bb n); int FirstAdjVex(Graph G,int v)/在图G中寻找第v个顶点的第一个邻接顶点 if(!G.AdjListv) return 0; else return(G.AdjListv-adjvex);int NextAdjVex(Graph G,int v,int u)/在图G中寻找第v个顶点的相对于u的下一个邻接顶点 ArcNode *p; p=G.AdjListv; while(p-adjvex!=u) p=p-nextarc; /在顶点v的弧链中找到顶点u if(p-nextarc=NULL) return 0; /若已是最后一个顶点，返回0 else return(p-nextarc-adjvex); /返回下一个邻接顶点的序号 void Initial(SqQueue &Q) /队列初始化 Q.front=Q.rear=0; BOOL QueueEmpty(SqQueue Q)/判断队列是否已空，若空返回True,否则返回False if(Q.front=Q.rear) return True; else return False; BOOL EnQueue(SqQueue &Q,int ch)/入队列，成功返回True，失败返回False if(Q.rear+1)%MAXQSIZE=Q.front) return False; Q.elemQ.rear=ch; Q.rear=(Q.rear+1)%MAXQSIZE; return True; BOOL DeQueue(SqQueue &Q,int &ch)/出队列,成功返回True，并用ch返回该元素值，失败返回False if(Q.front=Q.rear) return False; ch=Q.elemQ.front; Q.front=(Q.front+1)%MAXQSIZE; return True; /成功出队列，返回True6、 C程序设计总结本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不出结果等问题，经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。 在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除