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

课程名称：C语言 湖南涉外经济学院 学生课程设计（论文）题 目 图的遍历 姓 名 学 号 学 院 信息科学与工程学院 专业、年级 软件工程1101 指 导 教 师 刘 琼 年 月 日1摘 要随着近些年来的发展计算机在我们日常说中非常重要、并且计算机带动这更大的人工智能的发展为我们人类的生活提供方便，然而电子设备的操作成为我们克服的一个问题，随之我国因人员数量不断增长和日益庞大的规模，所产生的数据量越来越大，对数据的管理带来的极大的挑战。与此同时，无纸化办公的蓬勃发展和日趋成熟的计算机技术，使得现实问题计算机化，以其高效率、低成本的优势，日渐成为新兴模式和理念。数据结构中图的遍历是一种算法，图在数据结构中应用十分广泛，对于图来说最重要的当然是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到，图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 本次课程设计通过用例图以及功能模块划分的方法描述。其次，在需求分析的基础上，对系统进行了总体设计及详细设计，使用C语言实现了并给出了效果图。最后对系统进行了测试并给出了测试结果。关键词：计算机技术；图的遍历；C语言；算法；数据结构2图的遍历目 录摘 要2目 录1第一章 绪 论21.1课题背景及其现实意义21.1.1 课题背景21.1.2 课题意义21.2 需求分析21.3 设计目的31.4 设计内容3第二章 系统功能分析42.1 功能模块的实现42.1.1 创建图模块42.1.2 图以邻接矩阵的方式输出图52.1.3 图的深度优先遍历52.1.4 图的广度优先遍历72.1.5 主函数8第三章 系统测试93.1程序流程图9第四章 总结与展望10参考文献110第一章 绪 论1.1课题背景及其现实意义1.1.1 课题背景随着近些年来的发展计算机在我们日常说中非常重要、并且计算机带动这更大的人工智能的发展为我们人类的生活提供方便，然而电子设备的操作成为我们克服的一个问题，随之我国因人员数量不断增长和日益庞大的规模，所产生的数据量越来越大，对数据的管理带来的极大的挑战。与此同时，无纸化办公的蓬勃发展和日趋成熟的计算机技术，使得现实问题计算机化，以其高效率、低成本的优势，日渐成为新兴模式和理念。数据结构中图的遍历是一种算法，图在数据结构中应用十分广泛，对于图来说最重要的当然是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到，图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 本次课程设计通过用例图以及功能模块划分的方法描述。其次，在需求分析的基础上，对系统进行了总体设计及详细设计，使用C语言实现了并给出了效果图。最后对系统进行了测试并给出了测试结果。1.1.2 课题意义图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。掌握有向图和无向图的概念掌握邻接矩阵和邻接链表建立图的存储结构掌握DFS及BFS对图的遍历操作了解图结构在人工智能、工程等领域的广泛应用。1.2 需求分析1、 用户可以根据自己的需求分别输入任意的一个有向图可以是非连通图也可以是连通图； 2、 通过用广度优先遍历和深度优先遍历已有的图并输出；3、 并且以邻接矩阵的形式输出该已有的图； 4、 广度优先遍历图；5、 深度优先遍历图 1.3 设计目的在大学期间数据结构是一个较为重要的饿课程，本课程设计为学生提供了一个既动手又动脑，自学，查资料，独立实践的机会。将本学期课本上的理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对数据结构课程有一个很明确的认识。1.4设计内容根据需求分析的结果，本系统至少要分为以下几个模块：mian 函数模块、创建图、以邻接矩阵的方式输出图、深度优先遍历图 、广度优先遍历图模块。其中，各模块的功能说明如下：1、mian函数模块的主要功能为提供程序入口、前期环境设计、调用主要的执行函数和程序结束前的处理。2、创建图模块的主要功能为提供简单友好的录入界面，用户可以根据自己的需求分别输入任意的一个有向图可以是非连通图也可以是连通图。3、以邻接矩阵的方式输出图模块的主要功能邻接矩阵的形式输出该已有的图。4、深度优先遍历图模块的主要功能为把图以深度优先方式遍历以后进行输出。5、广度优先遍历图模块的主要功能为把图以广度优先方式遍历以后进行输出。根据上述描述，给出该系统的总体设计图，如图所示图的遍历退出模块输出图模块深度优先模块广度优先模块创建图模块41 设计内容第2章 系统功能分析2.1 功能模块的实现下面将依次介绍mian 函数模块、创建图模块、以邻接矩阵的方式输出图、深度优先遍历图 、广度优先遍历图模块的现实。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-vexsi); printf(请输入各顶点边的关系（1是有关0是无关）：n); for(i=0;inum;i+) for(j=0;jnum;j+)scanf(%d,&L-arcsij);2.1.2 图以邻接矩阵的方式输出图将图以邻接矩阵的方式输出图即就是讲数组中的数据用两个循环语句将其元素依次输出，这样就简单的表示了图上各个顶点之间的关系。void OutMGraph(MGraph L)int i,j;printf(n图的顶点数目v为：%d,L.num);printf(n图的各顶点的信息为：n);for(i=0;iL.num;i+)printf(%7c,L.vexsi);printf(n);for(i=0;iL.num;i+) for(j=0;jL.num;j+) printf(%7d ,L.arcsij); printf(n); 2.1.3 图的深度优先遍历图的深度优先遍历的定义：假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点（源点），则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 其实现思路如下代码：void DFS(MGraph g,int point,int mark) /深度优先遍历int v1;markpoint=1;printf(%c ,g.vexspoint);for(v1=0;v1g.num;v1+)if(g.arcspointv1!=0&markv1=0)DFS(g,v1,mark); /对尚未访问的顶点调用DFSvoid DFSTraverse(MGraph g)int point,v,v1,markmaxsize; printf(n深度遍历：);printf(n请输入起点的下标：);scanf(%d,&point);getchar(); for(v=0;vg.num;v+) markv=0; for(v=point;vg.num+point;v+)v1=v%g.num;if(markv1=0)DFS(g,v1,mark);/对未访问的顶点调用DFS2.1.4图的广度优先遍历图的深度优先遍历的定基本思路：1、 从图中某个顶点V0出发，并访问此顶点；2、 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，Wk；然后，依次从W1,W2，Wk出发访问各自未被访问的邻接点；3、 重复步骤2，直到全部顶点都被访问为止。 其算法思路如下代码：void BFS()/按广度优先遍历图G，使用辅助队列Q和访问标志数组mark QueueInit(&q); QueueIn(&q,v); printf(%c ,g.vexsv); while(QueueIsEmpty(q)=0) QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2g.num;v2+) if(g.arcsv1v2!=0&markv2=0) QueueIn(&q,v2); /入队操作markv2=1;printf(%c ,g.vexsv2); 2.1.5主函数其主函数实现了界面友好及其函数功能要划分，进一步增加人机交互操作界面。void main() switch(i) case 1:CreateMGraph(&tu);break; / 创建图case 2:OutMGraph(tu);break;/输出图case 3:DFSTraverse(tu);break; / 深度遍历图 case 4:GBFS(tu);/ 广度遍历图 break; case 8:exit(0); /退出程序/8第3章 系统测试开始3.1程序流程图输入cin结束否否否否是是是是是输入错误退出广度优先深度优先输出图创建图Cin=5Cin=4Cin=3Cin=2Cin=1第四章 总结与展望在为期一个月的课程设计制作中，我们深深的体会到了编程的重要性，虽然在编程的过程中我们遇到了很多的困难，但在问与答中一一克服，在解决问题的同时我们学到了很多老师上课所没有传述的知识，也让我们更加熟悉了编程的操作和word文档的编写。 在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，让我意识到数据结构作为我们的主要专业课程之一，开始觉得那些程序枯燥无味，但在这次课程设计后我发现在自己一点一滴的努力中对数据结构算法程序的兴趣也在增加。 可是在制作的过程中，编程总是运行错误成为了我们非常大的困难之一，常常在悉心时久的编程后，运行出现错误，往往是越改越错，导致此段代码需要重新编写，但在前面代码的不断出错与修改的同时，我们也学到了更多，领悟到了上课所没有领会的知识点，所以在后面的编程中就越编越顺。 一个月前我们还为如何下手感到措手不及。最后还是在老师的耐心分析和指导下完成了课程的思路和工作的分配。比如在调试时发现，程序运行后一直无法返回至主菜单，且VC也无法识别出程序的错误，使我们一直困扰多时，后来经过了讨论和分析后解决了此问题。