图的遍历课程设计

文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.1格式已调整，word版本可编辑.数据结构课程设计报告题目：图的遍历学生姓名：刘再科学号：0213专业班级：计科10102班同组姓名:蔡双指导教师：孙叶枫设计时间：2011年下学期第18周指导老师意见:评定成绩:签名:日期:目录一．前言1.课程设计的目的…………………………………….32.课程设计的基本要求……………………………….4二．课程设计内容…………………………….…..5文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.2格式已调整，word版本可编辑.三．系统（项目）设计…………………...………6四．源程序………………………………………...8五．程序的调试及测试结果……………………..18六．小结…………………………………………..21七．参考文献…………………...............................21文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.3格式已调整，word版本可编辑.一．前言1、课程设计的目的《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.4格式已调整，word版本可编辑.2、课程设计的基本要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.5格式已调整，word版本可编辑.5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；二．课程设计内容题目：图的遍历功能：实现图的深度优先,广度优先遍历算法，并输出原图结构及遍历结果。分步实施：1)初步完成总体设计，搭好框架；2）完成最低要求：两种必须都要实现，写出画图的思路；3）进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.6格式已调整，word版本可编辑.三．系统（项目）设计图一、系统功能模块图用户登录录入图信息进入主菜单更改数据深度优先遍历广度优先遍历退出程序文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.7格式已调整，word版本可编辑.图二、主函数流程图登录开始CreatueMGraph(G)ch1='y'ch1='y'输入ch2CreatueMGraph(G)DFSTraverseM(G)BFSTraverseM(G)ch1='n'break结束程序ch2真1假230文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.8格式已调整，word版本可编辑.四．源程序#includestdio.h#includestdlib.h#defineMax10#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{charvexs[Max];intedges[Max][Max];intn,e;}MGraph;//以邻接矩阵作为图的存储结构intvisited[Max];//将visited[Max];//定义为全局变量并分配最大空间typedefstruct{intfront;intrear;intcount;intdata[QueueSize];文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.9格式已调整，word版本可编辑.}CirQueue;//定义队列的数据结构//初始化队列voidInitQueue(CirQueue*Q){Q-front=Q-rear=0;Q-count=0;}//队列空intQueueEmpty(CirQueue*Q){returnQ-count=QueueSize;//返回队列的最大长度}//队列满intQueueFull(CirQueue*Q){returnQ-count=QueueSize;//返回队列的最大长度}//进队voidEnQueue(CirQueue*Q,intx){if(QueueFull(Q))//队列满则出错{文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.10格式已调整，word版本可编辑.Error(Queueoverflow);}else{Q-count++;//否则count++,将x进队Q-data[Q-rear]=x;Q-rear=(Q-rear+1)%QueueSize;}}//出队intDeQueue(CirQueue*Q){inttemp;//定义整型的变量if(QueueEmpty(Q))//若为真则出错{Error(Queuueunderflow);return0;}else//为假泽count--,将队员出对{temp=Q-data[Q-front];Q-count--;文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.11格式已调整，word版本可编辑.Q-front=(Q-front+1)%QueueSize;returntemp;//返回出对元素值}}//建立一个图voidCreatueMGraph(MGraph*G){inti,j,k;//定义整形变量charch1,ch2;//定义字符型变量printf(\n请输入定点数,边数(格式:4,5));scanf(%d,%d,&(G-n),&(G-e));//输入图的顶点数华和边数for(i=0;iG-n;i++){getchar();printf(\n请输入第%d的顶点序号,i+1);scanf(%c,&(G-vexs[i]));//输入顶点的序号}for(i=0;iG-n;i++){for(j=0;jG-n;j++){G-edges[i][j]=0;//初始化矩阵文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.12格式已调整，word版本可编辑.}}for(k=0;kG-e;k++){getchar();printf(\n请输入第%d条边的顶点序号(格式:i,j):,k+1);scanf(%c,%c,&ch1,&ch2);//输入边的顶点序号for(i=0;ch1!=G-vexs[i];i++);for(j=0;ch2!=G-vexs[j];j++);G-edges[i][j]=1;//有边则赋值为1}}//深度优先遍历递归voidDFSM(MGraph*G,inti){intj;printf(%c,G-vexs[i]);visited[i]=TRUE;//标记visited[i]//依次优先搜索访问visited[i]的每个领结点for(j=0;jG-n;j++)//若visited[i]的一个有效邻接点visited[i]未被访问过,则//visited[i]出发进行递归调用文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.13格式已调整，word版本可编辑.if(G-edges[i][j]==1&&visited[j])DFSM(G,j);}//广度优先遍历递归voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;//定义一个队列Q,初始化队列为空InitQueue(&Q);printf(%c,G-vexs[k]);//访问初始点,并将其标记已访问visited[k]=TRUE;EnQueue(&Q,k);//将以访问过的初始点序号k入队while(!QueueEmpty(&Q))//队列非空进行循环{i=DeQueue(&Q);//队首元素出队for(j=0;jG-n;j++)//依次搜索vexs[k]的可能邻接点{if(G-edges[i][j]==1&&!visited[j]){visited[j]=TRUE;//标记vexs[j]已访问过EnQueue(&Q,j);//顶点序号j入队}文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.14格式已调整，word版本可编辑.}}}//深度优先遍历voidDFSTraverseM(MGraph*G){inti;printf(\n深度优先遍历序列:);for(i=0;iG-n;i++){visited[i]=FALSE;//访问标志数组初始化}for(i=0;iG-n;i++){if(!visited[i])//对尚未访问的的顶点调用DFSM{DFSM(G,i);}}}//广度优先遍历voidBFSTraverseM(MGraph*G)文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.15格式已调整，word版本可编辑.{inti;printf(\n广度优先遍历序列:);for(i=0;iG-n;i++){visited[i]=FALSE;//访问标志数组初始化}for(i=0;iG-n;i++){if(!visited[i])//对尚未访问的的顶点调用BFSM{BFSM(G,i);}}}voidmain(){MGraph*G,a;charch1;intch2;G=&a;printf(\n\t\t深度优先遍历和广度优先遍历\n);文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.16格式已调整，word版本可编辑.CreatueMGraph(G);//调用创建图矩阵函数getchar();ch1='y';//控制语句标志while(ch1=='y'||ch1=='Y'){printf(\n);printf(主菜单);printf(\n\