在邻接表存储结构上实现图的遍历

《在邻接表存储结构上实现图的遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大连科技学院数据结构课程设计题目在邻接表存储结构上实现图的遍历学生姓名李楠专业班级网络工程13-1指导教师郭文书职称　　副教授所在单位信息科学系教学部主任王立娟完成日期2015年1月11日课程设计报告单学号23姓名李楠专业班级网络工程13-1考核项目评分备注1平时工作态度及遵守纪律情况　　　（10分）2掌握基本理论、关键知识、基本技能的程度和阅读参考资料的水平　　（10分）3独立工作能力、综合运用所学知识分析和解决问题能力及实际工作能力提高的程度　　（20分）4完成课程设计说明书及软件的情况与水平（小

2、组分工情况、规范性、整洁清楚、叙述完整性、思路清晰程度、工作量及实际运行情况和创新性）　　（60分）总评成绩综合评定：　　　（优、良、中、及格、不及格）指导教师签字：　　　2015年1月11日数据结构课程设计任务书一、任务及要求：1.设计（研究）任务和要求研究内容：在邻接表存储结构上实现图的遍历任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。（2）对指导教师下达的题目进行系统分析。（3）根据分析结果完成系统设计。（4）编程：在计算机上实现题目的代码实现。（5）完成对该系统的测试和

3、调试。（6）提交课程设计报告。要求完成课程设计报告3000字以上(约二十页)。完成若干综合性程序设计题目，综合设计题目的语句行数的和在100行语句以上。2.原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3.参考题目：二、工作量2周（10个工作日）时间三、计划安排第1个工作日：查找相关资料、书

4、籍，阅读示例文档，选择题目。第2个工作日－第3个工作日：设计程序结构、模块图。第4个工作日－第9个工作日：完成程序的编码，并且自己调试、测试。穿插进行课程设计报告的撰写。第10个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。指导教师签字：　　　　　　　　　　　　　　　　　　　2014年12月28日目录1需求分析11.1系统概述11.2系统运行环境11.3功能需求描述12总体设计22.1开发与设计的总体思想22.2系统模块结构22.3系统总体流程33详细设计43.1数

5、据类型43.2邻接表创建模块53.3邻接表输出模块63.4输出DFS遍历模块83.5输出BFS遍历模块94系统测试11总结13参考文献14附录15大连科技学院2013级数据结构课程设计报告1需求分析1.1系统概述邻接表是图的一种存储结构。邻接表中的每个顶点表结点应包含两个区域：一个是顶点域，用来存放顶点的信息；另一个是指针域，用来存放与顶点相关联的所有边链接成的边表头指针。图的遍历是从图的某一顶点出发，沿着某条搜索路径对图的每个顶点都访问一次且仅访问一次。根据搜索路径方向的不同，有两种常用的图的遍历方

6、法：深度优先搜索和广度优先搜索。1.2系统运行环境1.硬件环境处理器：InterPentium166MX或更高内存：32M硬盘空间：1GB显卡：SVGA显示适配器2.软件环境操作系统：Windows98/ME/2000/XP/WIN7开发语言：VisualC++1.3功能需求描述图是一种较线性表和树更为复杂的数据结构.图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.因此,在研究有关图的问题时,要考虑图中每个顶点的信息,访问图中的各顶点,而访问图中各顶点的操作过程就是图的遍历

7、.当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。20大连科技学院2013级数据结构课程设计报告2总体设计2.1开发与设计的总体思想由于图形结构比树形结构逻辑特征更复杂，所以图的遍历比树的遍历也要复杂得多。因为图中人一个顶点都可能与其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条搜索路径有回到了该顶点上。为了避免某一顶点被重复访问，在图的遍历过程中，必须采取某种方法来记录每个顶点是否被访问过。为此，可以设一个辅助数组，数组的初始值均设为“假”，一旦某个顶点被访

8、问过，则将辅助数组中相应的值置为“真”。所以要根据搜索路径方向的不同，则有两种常用的图的遍历方法：深度优先搜索遍历和广度优先搜索遍历。2.2系统模块结构在邻接表存储结构上实现图的遍历邻接表创建模块输出DFS遍历模块输出BFS遍历模块邻接表输出模块退出结束程序图2-1系统模块结构图20大连科技学院2013级数据结构课程设计报告2.3系统总体流程在邻接表存储结构上实现图的遍历输入顶点个数建立邻接表输入边的信息输入边的个数输入顶点信息邻接表建立成功输入2输入3