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

数据结构图的遍历课程设计 课程名称:C语言 湖南涉外经济学院 学生课程设计(论文) 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目 图的遍历 姓 名 学 号 学 院 信息科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院 专业、年级 软件工程1101 指 导 教 师 刘 琼 年 月 日 1 摘 要 随着近些年来的发展计算机在我们日常说中非常重要、并且计算机带动这更大的人工智能的发展为我们人类的生活提供方便，然而电子设备的操作成为我们克服的一个问题，随之我国因人员数量不断增长和日益庞大的规模，所产生的数据量越来越大，对数据的管理带来的极大的挑战。 与此同时，无纸化办公的蓬勃发展和日趋成熟的计算机技术，使得现实问题计算机化，以其高效率、低成本的优势，日渐成为新兴模式和理念。 数据结构中图的遍历是一种算法，图在数据结构中应用十分广泛，对于图来说最重要的当然是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到，图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 本次课程设计通过用例图以及功能模块划分的方法描述。其次，在需求分析的基础上，对系统进行了总体设计及详细设计，使用C语言实现了并给出了效果图。最后对系统进行了测试并给出了测试结果。 关键词:计算机技术;图的遍历;C语言;算法;数据结构 2 图的遍历 目 录 摘 要 .......................................................................................................................2 目 录 .........................................................................................................................1 第一章 绪 论 ........................................................................................................................ 2 1.1课题背景及其现实意义......................................... 2 ............................................... 2 1.1.1 课题背景 1.1.2 课题意义............................................... 2 1.2 需求分析 .................................................... 2 1.3 设计目的 .................................................... 2 1.4 设计内容 .................................................... 3 第二章 系统功能分析 ............................................................................................................... 3 2.1 功能模块的实现 .............................................. 3 2.1.1 创建图模块............................................ 4 2.1.2 图以邻接矩阵的方式输出图.............................. 4 2.1.3 图的深度优先遍历...................................... 5 2.1.4 图的广度优先遍历...................................... 6 2.1.5 主函数................................................ 6 第三章 系统测试 ........................................................................................................................ 8 3.1程序流程图 .................................................................................................................... 8 第四章 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 与展望 .................................................................................................................... 9 参考文献 ...................................................................................................................................... 10 1 图的遍历 第一章 绪 论 1.1课题背景及其现实意义 1.1.1 课题背景 随着近些年来的发展计算机在我们日常说中非常重要、并且计算机带动这更大的人工智能的发展为我们人类的生活提供方便，然而电子设备的操作成为我们克服的一个问题，随之我国因人员数量不断增长和日益庞大的规模，所产生的数据量越来越大，对数据的管理带来的极大的挑战。 与此同时，无纸化办公的蓬勃发展和日趋成熟的计算机技术，使得现实问题计算机化，以其高效率、低成本的优势，日渐成为新兴模式和理念。 数据结构中图的遍历是一种算法，图在数据结构中应用十分广泛，对于图来说最重要的当然是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到，图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 本次课程设计通过用例图以及功能模块划分的方法描述。其次，在需求分析的基础上，对系统进行了总体设计及详细设计，使用C语言实现了并给出了效果图。最后对系统进行了测试并给出了测试结果。 1.1.2 课题意义 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。掌握有向图和无向图的概念掌握邻接矩阵和邻接链表建立图的存储结构掌握DFS及BFS对图的遍历操作了解图结构在人工智能、工程等领域的广泛应用。 1.2 需求分析 1、 用户可以根据自己的需求分别输入任意的一个有向图可以是非连通图也可以是连通图; 2、 通过用广度优先遍历和深度优先遍历已有的图并输出; 3、并且以邻接矩阵的形式输出该已有的图; 4、广度优先遍历图; 5、深度优先遍历图 1.3 设计目的 在大学期间数据结构是一个较为重要的饿课程，本课程设计为学生提供了一个既动手又动脑，自学，查资料，独立实践的机会。将本学期课本上的理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对数据结构课程有一个很明确的认识。 2 图的遍历 1.4设计内容 根据需求分析的结果，本系统至少要分为以下几个模块:mian 函数模块、创建图、以邻接矩阵的方式输出图、深度优先遍历图 、广度优先遍历图模块。其中，各模块的功能说明如下: 1、mian函数模块的主要功能为提供程序入口、前期环境设计、调用主要的执行函数和程序结束前的处理。 2、创建图模块的主要功能为提供简单友好的录入界面，用户可以根据自己的需求分别输入任意的一个有向图可以是非连通图也可以是连通图。 3、以邻接矩阵的方式输出图模块的主要功能邻接矩阵的形式输出该已有的图。 4、深度优先遍历图模块的主要功能为把图以深度优先方式遍历以后进行输出。 5、广度优先遍历图模块的主要功能为把图以广度优先方式遍历以后进行输出。 根据上述描述，给出该系统的总体设计图，如图所示 图的遍历 广深 创输度度退建出 优优出图图先 先模模模模模块 块块 块 块 4—1 设计内容 第二章 系统功能分析 2.1 功能模块的实现 下面将依次介绍mian 函数模块、创建图模块、以邻接矩阵的方式输出图、深度优先遍历图 、广度优先遍历图模块的现实。 3 图的遍历 2.1.1 创建图模块 本次图的储存结构选用的是邻接矩阵的方式储存各个顶点及其边之间的关系(用1表示 有关，0表示无关)，用两个数组分别储存顶点和数据之间的关系(边或弧)的信息，借助 于邻接矩阵容易判定任意两个顶点之间是否有边或者弧，容易求得各个顶点的度。 void CreateMGraph(MGraph *L) { int i,j; printf("请输入顶点数目:\n"); scanf("%d",&L->num); printf("请输入各顶点:\n"); for(i=0;inum;i++) { fflush(stdin); scanf("%c",&L->vexs[i]); } printf("请输入各顶点边的关系(1是有关0是无关):\n"); for(i=0;inum;i++) { for(j=0;jnum;j++) { scanf("%d",&L->arcs[i][j]); } } } 2.1.2 图以邻接矩阵的方式输出图 将图以邻接矩阵的方式输出图即就是讲数组中的数据用两个循环语句将其元素依次输出，这样就简单的表示了图上各个顶点之间的关 系。 void OutMGraph(MGraph L) { int i,j; printf("\n图的顶点数目v为:%d",L.num); printf("\n图的各顶点的信息为:\n"); for(i=0;i