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

《数据结构课程设计：图的遍历的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计设计说明书图的遍历的实现学生姓名周朝学号1118064029班级网络1101班成绩指导教师申静数学与计算机科学学院2014年1月4日课程设计任务书2013—2014学年第一学期课程设计名称：数据结构课程设计课程设计题目：图的遍历实现完成期限：自2013年12月23日至2014年1月4日共2周设计内容：1.任务说明(1)采用邻接表存储结构创建一个图；(2)编程实现图的深度优先搜索（或广度优先搜索）遍历算法；(3)输出遍历结果；(4)给定具体数据调试程序。2.要求1）问题分析和任务定义：根据设计题目的要求，充分

2、地分析和理解问题，明确问题要求做什么？2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告。3.参考资料指导教师：申静教研室负责人：余冬梅课程设计评阅评语：指导教师签名：年月日摘要本课

3、程设计主要目的在于更深一步的了解图的遍历的问题，以无向图为例分别实现了广度优先遍历和深度优先遍历，在课程设计中，程序设计设计语言采用VisualC，程序运行平台为Windows98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题。程序最终通过调试运行，实现了设计目标。关键词:程序设计；数据结构；无向图目录一课题描述1二设计目的与任务22.1课程设计的目的22.2课程设计的任务2三设计方案和实施33.1总体设计33.2基本操作33.3详细设计4四运行调试结果6五结论与致谢9六附录10一

4、课题描述图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好

5、的工作作风。本设计采用目前最通用的程序设计语言之一—C语言作为数据结构和算法的描述语言。14二设计目的与任务2.1课程设计的目的进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，

6、并在此过程中培养严谨的科学态度和良好的工作作风。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.2课程设计的任务1）任务说明用C/C++编写一个程序实现图的遍历的算法。从键盘上输入一个图的基本信息（图用邻矩阵表示）。图的DFS,BFS的递归和非递归算法的实现；用有向图实现图的遍历；用无向图实现图的遍历；用邻接矩阵存储图；用邻接表存储图。2）要求1>首先输入图的结点数；2>依次输入图的各条边（数据之间用空格隔开）；3>输出的形式：按用户选择的遍历方法给出遍历顺序，各字符间用->分隔；4>程序所能达到的功能：能够

7、按要求输出所要的结果。14三设计方案和实施3.1总体设计采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：抽象数据类型的定义typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;3.2基本操作CreateUDN(Graph&G)操作结果：用邻接矩阵创建带权无向网图。DFS(GraphG,intk)操作结果：对已存在的图进行深度优先遍历。BFS(GraphG)操作结果：对已

8、存在的图进行广度优先遍历。choose(GraphG)操作结果：对将要实现的操作步骤进行选择。程序包含两个模块主程序模块，其中主函数为intmain{输入信息；根据输入要求进行选择操作和输出；输出结果；}选择操作模块—实现具体选择的对应操作及输出操作。两模块之间关系如下图3.114图3.1模块关系图3.