图的建立与遍历.docVIP

数据结构 课程设计(论文) 图的建立与遍历 院（系）名称 电子与信息工程学院 专业班级 计算机科学与技术 学号 学生姓名 指导教师 副教授 起 止 时 间： 2014.12.29—2015.1.9 课程设计（论文）任务及评语 院（系）：电子与信息工程学院 教研室：软件工程 学 号 学生姓名 专业班级 课程设计（论文）题目 图的建立与遍历 课程设计（论文）任务 任务要求： 图的建立与遍历实现以下几个功能：（1）创建图的存储结构并保存；（2）对图进行深度优先有哪些信誉好的足球投注网站（3）对图进行广度优先有哪些信誉好的足球投注网站。（4）输出遍历结果。 技术要求 1、数据的逻辑结构采用图状结构，物理结构采用链式存储结构（邻接表）。 2、软件能正常运行，界面清晰，操作要简单。 3、系统要有主界面设计，调用各个功能项。 4、采用Viscal C++编写代码，可读性强。 5、数据类型用typedef 定义。 指导教师评语及成绩 平时成绩： 答辩成绩： 论文成绩： 总成绩： 指导教师签字： 年 月 日 注：平时成绩占20%，答辩成绩占40%，论文成绩占40%。摘 要 本课程设计主要目的在于更深一步的了解图的建立与遍历的问题，图的深度遍历与图的广度遍历的实现，用有向图不带权图、有向带权图、无向不带权图和有向带权图分别实现图的遍历，深度优先遍历和广度优先遍历的实现，用邻接表来存储图。 在课程设计中，程序设计语言采用Visual C,程序运行平台为Windows 7。 在程序设计中我主要解决的是给出一个图如何用多中方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图。程序最终通过调试运行，初步实现了设计目标。 关键词：程序设计；数据结构；有向图；无向图；存储结构；邻接表 目 录 第1章 绪论 1 1.1系统的开发背景 1 1.2开发工具及语言 1 第2章 概要设计 2 2.1模块划分 2 2.2 数据结构的选择 2 第3章 系统详细设计与编码 3 3.1完整的源程序 3 3.2程序的输入和输出 9 3.3调试程序中遇到的问题及解决方案 10 第4章 思考题解析 11 4.1 思考题的选择 11 4.2类C算法 11 4.3程序分析 12 第5章 总结 13 参考文献 14 第1章 绪论 1.1系统的开发背景 图是一种较线性表和树更为复杂的数据结构，在图的结构中，结点之间的关系可以是任意的，图中任意连个元素之间都可能有关系。图的应用十分广泛，近年来已经渗入到其他的很多分支中。 1.2开发工具及语言 本系统使用V语言 题目应实现的具体功能： 按照自己的需要从有向向图不带权图、有向带权图、无向不带权图和有向带权图中选择建立一种图的结构，输入具体的顶点数目、顶点值、边的数目和权值，选择要开始遍历的顶点，并按照深度优先遍历和广度优先遍历输出该图。 2.2 数据结构的选择 系统数据的逻辑结构采用图状结构，物理结构采用链式存储结构（邻接表）。 存储结构定义如下： typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 ArctexType info; //该弧相关信息的指针 }ArcNode; typedef struct Vnode { VertexType data; //顶点信息 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }Vnode,Adjlist[MAC_VERTEX_NUM]; typedef struct { Adjlist vertices; int vexnum,arcnum; //图的当前顶点数和弧数 int kind; //图的种类标志 }Graph; 第3章 系统详细设计与编码 3.1完整的源程序 #include stdio.h #include stdlib.h #include string.h #define MAC_VERTEX_NUM 20 #define NULL 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #