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

1、 数据结构 课程设计报告题 目： 图的遍历 学生姓名： 学 号： 200817020103 专业班级： 信管08101班 同组姓名: 指导教师： 设计时间： 2010年上学期第 1 周 指导老师意见:评定成绩: 签名: 日期:目 录一、前言 1.1课程设计的目的与意义31.2对课程设计功能的需求分析3二、算法思想4三、数据结构4四、模块划分4.1、有关队列的一系列函数54.2、创建图的函数54.3、图的深度优先遍历递归54.4、图的广度优先遍历递归54.5、深度优先遍历54.6、广度优先遍历54.7、主函数5五、系统的概要设计1、系统功能模块图62、各模块流程图7六、源程序12七、程序的调试分

2、析以及测试结果1、程序的调试分析202、程序的测试结果20八、附录1、课程设计心得体会252、参考文献26一、前言1.1课程设计的目的与意义上学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求我们掌握数据结构中的各方面知识，还要求我们具备一定的c语言基础和编程能力。通过实践我们掌握数据结构中的知识。对于图的遍历这一课题来说，所要求我们掌握的数据结构知识主要有：图的存储结构、队列的基本运算实现、图的深度优先遍历算法实现、图的广度优先遍历算法实现。对于我们学生来讲，此次课程设计是

3、为了让我们训练自己的实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面的基本训练和工作经验。通过课程设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项目管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。1.2对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下： 1、用户可以随时建立一个有向图或无向图；2、用户可以根据自己的需要，对图进行深度遍历或广度遍历；3、用户可以

4、根据自己的需要对图进行修改；4、在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号;二、算法思想本课题本人所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。2.1.1图的邻接矩阵的建立 对任意给定的图（顶点数和边数自定），根据邻接矩阵的存储结构建立图的邻接矩阵。2.1.2 图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被

5、访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。三、数据结构#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 visitedmax;typedef struct int front; int rear; int count; int dataqueuesize;cirqu

6、eue;四、模块划分 4.1、队列的初始化、进队、出队、队列空、队列满的函数； void initqueue(cirqueue *q) /初始化队列int queueempty(cirqueue *q)/队列是否为空int queuefull(cirqueue *q)/队列满void enqueue(cirqueue *q,int x)/将队员进队int dequeue(cirqueue *q)/将队员出队4.2、创建图的函数 void createmgraph(mgraph *g)/根据用户需要创建一个图4.3、图的深度优先遍历递归void dfsm(mgraph *g,int i)/*含有

7、输出已访问的顶点的语句*/4.4、图的广度优先遍历递归 void bfsm(mgraph *g,int k) /*含有输出已访问的顶点的语句*/4.5、深度优先遍历 void dfstraversem(mgraph *g)/*调用dfsm函数*/4.6、广度优先遍历 void bfstraversem(mgraph *g) /*调用bfsm函数*/4.7、主函数 main() /*包含一些调用和控制语句*/ 五、系统的概要设计进入菜单选择用户登录图信息的录入修改图的信息广度优先遍历图深度优先遍历图 退出程序 图一、系统功能模块图输入ch2登陆开始createmgraph(g);ch1=ych1

8、=y 真 假 ch2 b r e a kch1=n 0createmgraph(g) 1dfstraversem(g) bfstraversem(g)bfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g)dfstraversem(g) 2 bfstraversem(g) 3结束程序图二、主函数流程图dfstraversem(mgraph *g)i=0invisitedi=falsei+i=0 in 真!visitedi i+ 非零 零dfsm(g,i)结束程序

9、图三、 深度优先遍历流程图dfsm(mgraph *g,int i) 输出g-vexsivisitedi=true j=0 jn 真 g-edgesij=1&!visitedjdfsm(g,i)j+结束程序图四、 深度优先遍历递归bfstraversem(mgraph *g)i=0invisitedi=falsei+i=0 in 真!visitedi i+ 非零 零bfs(g,i)结束程序图五、 深度优先遍历流程图i=dequeue(&q) j=0 !queueempty(&q)enqueue(&q,k)visitedi=true输出g-vexskinitqueue(&q)bfsm(mgrap

10、h *g,int k) jn 真!visitedi dfsm(g,i)i+结束程序图六、广度优先遍历递归流程图六、源程序#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 visitedmax;/*将visitedmax定义为全局变量并分配最大空间*/typedef struct int

11、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,i

12、nt x) if(queuefull(q)/*队列满则出错*/ error(queue overflow); else q-count+;/*否则count+，将x进队*/ q-dataq-rear=x; q-rear=(q-rear+1)%queuesize; /出队int dequeue(cirqueue *q) int temp;/*定义整型的变量*/ if(queueempty(q)/*若为真则出错*/ error(queue underflow); else/*为假则count-，将队员出队*/ temp=q-dataq-front;/*用temp返回其值*/ q-count-; q

13、-front=(q-front+1)%queuesize; return temp;/*返回出队元素值*/ /建立一个图void createmgraph(mgraph *g) int i,j,k;/*定义整型变量*/ char ch1,ch2;/*定义字符型变量*/ printf(n请输入顶点数，边数（格式：3，4）:); 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;in;

14、i+) for(j=0;jn;j+) g-edgesij=0;/*初始化矩阵*/ for(k=0;ke;k+) 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-vexsi); visitedi=true;/*标记v

15、isitedi*/ /*依次优先搜索访问visitedi的每个邻接点*/for(j=0;jn;j+) /*若visitedi的一个有效邻接点visitedj未被访问过，则从visitedj出发进行递归调用*/ 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

16、);/*将以访问过的初始点序号k入队*/ while(!queueempty(&q)/*队列非空进行循环处理*/ i=dequeue(&q);/*将队首元素出队*/ for(j=0;jn;j+)/*依次搜索vexsk的每一个可能的邻接点*/ 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;/*

17、访问标志数组初始化*/ for(i=0;in;i+) if(!visitedi)/*对尚未访问的顶点调用dfsm*/ dfsm(g,i); /广度优先遍历void bfstraversem(mgraph *g) int i; printf(n 广度优先遍历序列:);for(i=0;in;i+) visitedi=false;/*访问标志数组初始化*/ for(i=0;in;i+) if(!visitedi)/*对尚未访问的顶点调用bfsm*/ bfsm(g,i); main() mgraph *g,a; char ch1; int i,j,ch2; g=&a;printf(ntt 深度优先搜索

18、和广度优先搜索 n); createmgraph(g);/*调用创建图矩阵的函数*/ getchar(); ch1=y;/*设置控制语句标志*/ while(ch1=y|ch1=y) /*菜单栏*/ printf(n); printf( 选择菜单); printf(ntt*n); printf(tt* 更改数据请按:1 *n); printf(tt* 深度优先搜索请按:2 *n); printf(tt* 广度优先搜索请按:3 *n); printf(tt* 退出搜索请按:0 *n); printf(tt*n); printf(ntt请选择菜单号（0-3）：); scanf(%d,&ch2);

19、getchar(); switch(ch2) case 1: createmgraph(g);/*选1创建一个新的图矩阵*/ break; case 2: dfstraversem(g);/*选2进入深度优先搜索*/ break; case 3: bfstraversem(g);/*选3进入广度优先搜索*/ break; case 0:/*选0结束搜索，退出程序*/ ch1=n; break; default: system(cls); printf(ntt输入有误！n); break; if(ch2=1|ch2=2|ch2=3) printf(nntt );/*控制格式*/ 七、程序的调试分

20、析以及测试结果7.1程序的调试分析在调试过程中，程序中出现了许多的错误，有错误的调用、一些变量没有定义、等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：1、在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函数名、变量没有被定义等问题；2、在编写程序的过程中数组的大小写没有被确定；3、在编写程序的过程中一些变量没有被定义，导致程序出错；4、数组visitedmax应定义为全局变量，若不是则会出错；5、函数的返

21、回类型要确定，是void还是其他类型要十分注意；6、在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，这次的课程设计就有一些括号漏了或者多打了，导致括号不配套；7.2、程序的测试结果 7.2.1、初始进入程序时，程序提示按格式输入图的顶点个数和边数。7.2.2、输入顶点数和边数后，程序提示输入顶点的序号，为各顶点依次进行编号。7.2.3、将各顶点进行编号后，程序提示按格式输入边的顶点序号。 7.2.4、按格式依次输入边的顶点序号后，按enter键程序会出现“选择菜单”，用户根据需要进行选择。 7.2.5、用户选择2进入深度优先搜索，并输出深度优先遍历后的序列，再次输出菜单栏，进行选择。 7.2.7、用户再次选择3进入广度优先搜索，并输出广度优先遍历后的序列，再次输出菜单栏，进行选择。 7.2.8、用户选择1后进入更改数据，重新创建一个图。 6.2.9、用户选择0，则退出程序。八、附录5.1、课程设计心得体会 心得体会 通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的c语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。由于c语