图的遍历数据结构课程设计

《图的遍历数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、徐俊《用C语言解决图的遍历的问题》第１４页共14页长沙理工大学《用C语言解决图的遍历》课程设计报告徐俊学院计算机与通信工程专业计算机科学与技术班级计算机08-03学号200850080307学生姓名徐俊指导教师湛新霞课程成绩完成日期2010年6月23日徐俊《用C语言解决图的遍历的问题》第１４页共14页课程设计成绩评定学院计算机与通信工程学院专业计算机科学与技术班级计算机08-03学号200850080307学生姓名徐俊指导教师湛新霞完成日期2010.6.23指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程

2、设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩指导教师签字2010年6月25日徐俊《用C语言解决图的遍历的问题》第１４页共14页用C语言解决图的遍历的问题学生姓名：徐俊指导老师：湛新霞摘要本课程设计主要目的在于更深一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图分别实现图的遍历，广度优先遍历和深度优先遍历的实现，用邻接矩阵和邻接表等多种结构存储存储图。在课程设计中，程序设计设计语言采用VisualC，程序运行平台为Windows98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多

3、种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。关键词程序设计；数据结构；有向图；无向图；存储结构；邻接矩阵；递归算法一引言数据结构是一门专业基础课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。图是一种较为复杂

4、且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。本设计采用目前最通用的程序设计语言之一—C语言作为数据结构和算法的描述语言。徐俊《用C语言解决图的遍历的问题》第１４页共14页二设计目的与任务2.1课程设计的目的进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能

5、。训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.2课程设计的任务问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）。图的DFS,BFS的递归和非递归算法的实现;用有向图实现图的遍历；用无向图实现图的遍历；用邻接矩阵存储图；用邻接表存储图。课题要求：首先输入图的结点数；依次输入图的各条边（数据之间用空格隔开）；输出的形式：按用

6、户选择的遍历方法给出遍历顺序，各字符间用->分隔；程序所能达到的功能：能够按要求输出所要的结果。徐俊《用C语言解决图的遍历的问题》第１４页共14页三设计方案和实施3.1总体设计采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：抽象数据类型的定义typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;基本操作CreateUDN(Graph&G)操作结果：用邻接矩阵创建带权无向网图。DFS(GraphG,intk)操作结果：对已存

7、在的图进行深度优先遍历。BFS(GraphG)操作结果：对已存在的图进行广度优先遍历。choose(GraphG)操作结果：对将要实现的操作步骤进行选择。程序包含两个模块主程序模块，其中主函数为intmain{输入信息；根据输入要求进行选择操作和输出；输出结果；}选择操作模块——实现具体选择的对应操作及输出操作。两模块之间的简单调用关系如图1所示。徐俊《用C语言解决图的遍历的问题》第１４页共14页主函数模块选择操作模块递归调用图1模块调用图3.2详细设计各个函数之间的调用关系如图2所示。主函数创建无向网