图的遍历课程设计

《图的遍历课程设计》由会员分享，可在线阅读，更多相关《图的遍历课程设计（22页珍藏版）》请在装配图网上搜索。

1、 数据结构 课程设计报告题 目： 图的遍历 学生姓名： 刘再科 学 号： 201017010213 专业班级： 计科10102班 同组姓名: 蔡双 指导教师： 孙叶枫 设计时间： 2011年下学期第18周 指导老师意见: 评定成绩: 签名: 日期: 目 录一前言1. 课程设计的目的.32. 课程设计的基本要求.4二课程设计内容.5三系统（项目）设计.6四源程序.8五程序的调试及测试结果.18六小结.21七参考文献.21一前言1、课程设计的目的数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简

2、单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；n

3、 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2、课程设计的基本要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使

4、得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；二课程设计内容题目：图的遍历功能：实现图的深度优先, 广

5、度优先遍历算法，并输出原图结构及遍历结果。分步实施：1) 初步完成总体设计，搭好框架；2） 完成最低要求：两种必须都要实现，写出画图的思路；3）进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。三 系统（项目）设计用户登录录入图信息进入主菜单更改数据深度优先遍历广度优先遍历退出程序 图一、系统功能模块图登录开始CreatueMGraph(G)ch1=ych1=y输入ch2CreatueMGrap

6、h(G)DFSTraverseM(G)BFSTraverseM(G)ch1=nbreak结束程序ch2真1假230图二、主函数流程图四源程序#include#include#define Max 10#define FALSE 0#define TRUE 1#define Error printf #define QueueSize 30typedef struct char vexsMax; int edgesMaxMax;int n,e;MGraph;/以邻接矩阵作为图的存储结构int visited Max;/将visitedMax;/定义为全局变量并分配最大空间typedef stru

7、ct int front ;int rear;int count;int dataQueueSize;CirQueue;/定义队列的数据结构/初始化队列void InitQueue(CirQueue *Q )Q-front=Q-rear=0;Q-count=0;/队列空int QueueEmpty(CirQueue *Q) return Q-count=QueueSize;/返回队列 的最大长度/队列满int QueueFull(CirQueue *Q) return Q-count=QueueSize;/返回队列 的最大长度/进队void EnQueue(CirQueue *Q,int x)

8、if(QueueFull(Q)/队列满则出错Error(Queue overflow);elseQ-count+;/否则count+,将x进队Q-dataQ-rear=x;Q- rear=(Q-rear+1)%QueueSize;/出队int DeQueue (CirQueue *Q)int temp;/定义整型的变量if (QueueEmpty(Q)/若为真则出错Error(Queuue underflow); return 0;else/为假泽count-,将队员出对temp=Q-dataQ- front;Q- count-;Q- front=(Q- front+1)%QueueSize;

9、return temp;/返回出对元素值/建立一个图void CreatueMGraph(MGraph *G) int i,j,k;/定义整形变量char ch1,ch2;/定义字符型变量printf(n请输入定点数,边数(格式:4,5);scanf(%d,%d,&(G-n),&(G-e);/输入图的顶点数华和边数for(i=0;in ;i+)getchar();printf(n请输入第%d的顶点序号,i+1);scanf(%c,&(G-vexsi);/输入顶点的序号 for(i=0;i n;i+)for(j=0;j n;j+)G-edgesij=0;/初始化矩阵for(k=0;ke ;k+)

10、getchar();printf(n请输入第%d条边的顶点序号(格式:i,j):,k+1);scanf(%c,%c,&ch1,&ch2);/输入边的顶点序号for(i=0;ch1!=G-vexsi;i+);for(j=0;ch2!=G- vexsj;j+);G- edgesij=1;/有边则赋值为1/深度优先遍历递归void DFSM(MGraph *G,int i) int j;printf(%c,G-vexs i);visitedi=TRUE;/标记visitedi/依次优先搜索访问visitedi的每个领结点for(j=0;j n;j+)/若visitedi的一个有效邻接点visited

11、i未被访问过,则/visitedi出发进行递归调用if(G-edgesij=1&visitedj)DFSM(G,j);/广度优先遍历递归void BFSM(MGraph *G,int k)int i,j;CirQueue Q;/定义一个队列Q,初始化队列为空InitQueue(&Q);printf(%c ,G-vexsk);/访问初始点,并将其标记已访问visitedk=TRUE;EnQueue(&Q,k);/将以访问过的初始点序号k入队while(!QueueEmpty(&Q)/队列非空进行循环i=DeQueue(&Q);/队首元素出队for(j=0;jn;j+)/依次搜索vexsk的可能邻

12、接点if(G-edgesij=1&!visitedj)visitedj=TRUE;/标记vexsj已访问过EnQueue(&Q,j);/顶点序号j入队/深度优先遍历void DFSTraverseM(MGraph *G)int i;printf(n 深度优先遍历序列: );for(i=0;in;i+)visitedi=FALSE;/访问标志数组初始化for(i=0;in;i+)if(!visitedi)/对尚未访问的的顶点调用DFSMDFSM(G,i);/广度优先遍历void BFSTraverseM(MGraph *G)int i;printf(n 广度优先遍历序列: );for(i=0;i

13、n;i+)visitedi=FALSE;/访问标志数组初始化for(i=0;in;i+)if(!visitedi)/对尚未访问的的顶点调用BFSMBFSM(G,i);void main()MGraph *G,a;char ch1;int ch2;G=&a;printf(ntt 深度优先遍历和广度优先遍历 n);CreatueMGraph(G);/调用创建图矩阵函数getchar();ch1=y;/控制语句标志while(ch1=y|ch1=Y) printf(n);printf( 主菜单 );printf(ntt=n);printf(tt = 更改数据请按:1 =n);printf(tt =

14、深度优先遍历请按:2 =n);printf(tt = 广度优先遍历请按:3 =n);printf(tt = 退出程序请按:0 =n);printf(ntt=n);printf(ntt请选择: );scanf(%d,&ch2);getchar();switch(ch2)case 1:CreatueMGraph(G);/选择1创建一个新的图矩阵break;case 2:DFSTraverseM(G);/选择深度优先遍历break;case 3: BFSTraverseM(G);/选择广度优先遍历 break;case 0: /选择0退出程序 ch1=n; break;default:system(

15、cls);printf(ntt输入错误!n);break;if(ch2=1|ch2=2|ch2=3)printf(nntt );/控制格式五程序的调试及测试结果 5.1、开始进入程序。5.2、输入顶点和边数后，进入顶点的序号编号。 5.3、将顶点编号后，输入边的顶点序号。5.4、输入边的顶点序号后，进入主菜单进行选择。5.5、选择2进行深度优先遍历，再次进入主菜单进行选择。 5.6、选择1更改数据，重新创建一个图。 5.7、选择0退出程序。六小结通过为期一周的课程设计使我对图的遍历有了更深的认识和理解，也使我更加明白图的遍历在数据结构中的重要性和地位。但是我的图的遍历程序还有一些缺陷，如，各个函数联合还是做得不够细致，程序的精简度还是不够，比较冗长，以后要多加学习， 巩固基础，多多学习，接受以及应用新编程知识，懂得掌握更加精辟的思维方式来缩短程序的代码长度，简洁程序，使程序可读性怎强以及运行速度变得更加快。七参考文献数据结构：C语言版/严蔚敏，吴伟民编著。清华大学出版社，2007。C语言程序设计（第二版）：谭浩强 编著。清华大学出版社，2008。数据结构（C语言）实践教程：胡元义，邓亚玲，罗作民，胡明星 编著。西安电子科技大学出版社，2001.12。22