图的建立与遍历

《图的建立与遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计(论文)图的建立与遍历院（系）名称电子与信息工程学院专业班级计算机科学与技术学号学生姓名指导教师副教授起止时间：2014.12.29—2015.1.9课程设计（论文）任务及评语院（系）：电子与信息工程学院教研室：软件工程学号学生姓名专业班级课程设计（论文）题目图的建立与遍历课程设计（论文）任务任务要求：图的建立与遍历实现以下几个功能：（1）创建图的存储结构并保存；（2）对图进行深度优先搜索（3）对图进行广度优先搜索。（4）输出遍历结果。技术要求1、数据的逻辑结构采用图状结构，物理结构采用链式存储结构（邻接表）。2、软件

2、能正常运行，界面清晰，操作要简单。3、系统要有主界面设计，调用各个功能项。4、采用ViscalC++编写代码，可读性强。5、数据类型用typedef定义。指导教师评语及成绩平时成绩：答辩成绩：论文成绩：总成绩：指导教师签字：年月日注：平时成绩占20%，答辩成绩占40%，论文成绩占40%。本科生课程设计（论文）摘要本课程设计主要目的在于更深一步的了解图的建立与遍历的问题，图的深度遍历与图的广度遍历的实现，用有向图不带权图、有向带权图、无向不带权图和有向带权图分别实现图的遍历，深度优先遍历和广度优先遍历的实现，用邻接表来存储图。在课程设计

3、中，程序设计语言采用VisualC,程序运行平台为Windows7。在程序设计中我主要解决的是给出一个图如何用多中方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图。程序最终通过调试运行，初步实现了设计目标。关键词：程序设计；数据结构；有向图；无向图；存储结构；邻接表II本科生课程设计（论文）目录第1章绪论11.1系统的开发背景11.2开发工具及语言1第2章概要设计22.1模块划分22.2数据结构的选择2第3章系统详细设计与编码33.1完整的源程序33.2程序的输入和输出93.3调试程序中遇到的问题及解决方

4、案10第4章思考题解析114.1思考题的选择114.2类C算法114.3程序分析12第5章总结13参考文献14II本科生课程设计（论文）第1章绪论1.1系统的开发背景图是一种较线性表和树更为复杂的数据结构，在图的结构中，结点之间的关系可以是任意的，图中任意连个元素之间都可能有关系。图的应用十分广泛，近年来已经渗入到其他的很多分支中。1.2开发工具及语言本系统使用ViscalC++语言开发，主界面清晰显示所有功能项，使用简单。各个功能项均定义一个函数来实现，在主函数中调用各个子函数实现不同的功能。14本科生课程设计（论文）第2章概要设计

5、2.1模块划分题目应实现的具体功能：按照自己的需要从有向向图不带权图、有向带权图、无向不带权图和有向带权图中选择建立一种图的结构，输入具体的顶点数目、顶点值、边的数目和权值，选择要开始遍历的顶点，并按照深度优先遍历和广度优先遍历输出该图。2.2数据结构的选择系统数据的逻辑结构采用图状结构，物理结构采用链式存储结构（邻接表）。存储结构定义如下：typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针ArctexTypeinfo;//该弧相关

6、信息的指针}ArcNode;typedefstructVnode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}Vnode,Adjlist[MAC_VERTEX_NUM];typedefstruct{Adjlistvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}Graph;14本科生课程设计（论文）第3章系统详细设计与编码3.1完整的源程序#include#include

7、#include#defineMAC_VERTEX_NUM20#defineNULL0#defineTRUE1#defineFALSE0#defineOVERFLOW-2#defineOK1#defineERROR0#defineArctexTypeinttypedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针ArctexTypeinfo;//该弧相关信息的指针}ArcNode;typedefcharVertexTyp

8、e[5];typedefstructVnode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}Vnode,Adjlist[MAC_VERTEX_NUM];