欧拉回路-数据结构与算法课程设计报告

合肥学院计算机科学与技术系课程设计报告2012～2013学年第2学期课程数据结构与算法设计课程设计课程设计名称欧拉回路学生姓名学号专业班级计算机科学与技术11级3班指导教师2013年3月题目：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？一．问题分析和任务定义：题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素云、张立昂主编的《离散数学》P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。二．数据结构的选择与概要设计：数据结构的选择：图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下：typedefstruct{ intn;//顶点个数 inte;//边的条数 intvexs[MAX_VERTEX_NUM];//一维数组储存顶点 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边}MGraph;//图2.概要设计首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行搜索得图中到每个顶点的度数，如果有奇度顶点，输出：不存在欧拉回路，即可结束程序。否则继续判断给定的图是否为连通图，如果是连通图输出：存在欧拉回路；否则输出：不存在欧拉回路。结束程序。三．详细设计和编码：1.将图转化为邻接矩阵存储：先输入图中顶点个个数和边的条数，对所有可能存在的边初始化为0，再依次输入边的信息，即如果顶点1,2存在相连的边，输入12（1,2为自动给顶点分配的编码）。将边1,2的信息改为1。用函数MGraph*creat_MGraph();完成，返回邻接矩阵的首地址即可。MGraph*creat_MGraph()//建立邻接矩阵{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("请输入顶点的个数："); scanf("%d",&n); printf("请输入边的条数："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//标记存在的边 } returnmg;//返回邻接矩阵的首地址}2.搜索有没有奇度顶点：对邻接矩阵的每一行进行搜索，用num记录顶点的度数（每次对新的顶点记录前都将num置为0）。为了排除顶点自身环对判断的影响，当遇到边的两顶点相同，忽略不计，这样不会对结果产生影响。如果搜索到奇度顶点则结束intEuleriancycle(MGraph*mg);函数，返回0，搜索完成且没有发现奇度顶点则返回1.intEuleriancycle(MGraph*mg)//判断是否存在欧拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return0; } return1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1}3.判断给定的图是否为连通图：本程序的深度优先遍历是一个递归的过程。其中visited[MAX_VERTEX_NUM]是一个辅助的全局变量，初始值均为0.表示该顶点没有被访问。访问后用1表示。在深度优先搜索时。我们需要调用dfs_trave()函数。在dfs_trave()中，针对每个没有被访问过的顶点调用dfs()函数，它是一个递归函数，完成从该顶点开始的深度优先搜索。如果图是一个连通图，那么完成对visited数组的初始化后，在dfs_trave()中只需调用dfs()函数一次即可完成对图的遍历。当图不是一个连通图时，则在dfs_trave()中需要针对每个连通分量分别调用dfs()函数。根据dfs()函数被调用的次数就可以判断给定的图是否为连通图。如果dfs()函数被调用一次则给定的图是连通图，否则不是连通图。intdfs_trave(MGraph*mg)//深度优先搜索遍历{ inti,m=0; for(i=1;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } returnm;//返回调用dfs函数的次数}voiddfs(MGraph*mg,inti)//深度优先搜索{ intj; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索}4.根据上述2,3可知，必须为连通图且没有奇度顶点才是欧拉图即存在欧拉回路。5.流程图如下（图：1）：开始开始顶点数、边数、边信息顶点数、边数、边信息将图转化为邻接矩阵将图转化为邻接矩阵搜索图中所有顶点的度数搜索图中所有顶点的度数判断是否存在奇度顶点判断是否存在奇度顶点 Y N对图进行深度优先搜索遍历对图进行深度优先搜索遍历对图进行深度优先搜索遍历对图进行深度优先搜索遍历判断图是否为连通图 判断图是否为连通图 N Y不存在欧拉回路存在欧拉回路不存在欧拉回路存在欧拉回路结束结束图：1流程图四．上机调试过程：本次实验中也遇到了一些小问题，通过在适当的位置加一些printf语句即可确定出现问题的语句大概的位置。加以分析、修改即可。在本次课程设计的第三组数据的测试时出现了不存在欧拉图的错误结果，仔细分析可知，在（2,2）邻接矩阵的对角线上，所以该点的度数在计算的时候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1的判断中增加了一个判断，当该点存在环，则在度数的计数时忽略不计，这样不会印象该点度数奇偶性的变化。这样就很好的解决了，存在环对判断结果的印象的问题。通过本次课程设计让我更加深刻的体会到调试程序需要平心静气，仔细分析、研究。要有一个严谨的态度，这样才能高效率的写出优质的代码。五．测试结果与分析：测试数据的选择：在测试中考虑到多种情况使用了多组数据，分别根据是否为连通图、是否没有奇度顶点设计了一下四组数据。第一组数据为连通图且没有奇度顶点，第二组数据为连通图且有奇度顶点，第三组数据为连通图、没有奇度顶点且有环，第四组数据为非连通图且有奇度顶点，第五组数据为非连通图且没有奇度顶点。每组数据进行多次测试。测试数据1：33121323测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，顶点两两相连。如下:2-1所示：113232 图：2-1测试1存在欧拉回路。测试结果正确。测试数据2：33321223测试结果： 结果分析：测试数据表示一个3个顶点，3条边的图，1,、2相连，2、3相连。如下图2-2所示：1 12323图：2-2测试2不存在欧拉回路。测试结果正确。测试数据:3：451213243422测试结果：结果分析：测试数据表示一个4个顶点，5条边的图，1、2相连，1、3相连,2、4相连,3、4相连，2、2相连。如下图2-3所示：21213434 图：2-3测试3存在欧拉回路。测试结果正确。测试数据4：5412344535测试结果：结果分析：测试数据表示一个5个顶点，4条边的图，1、2相连，3、4相连,4、5相连,3、5相连。如下:图2-4所示：3131542542不存在欧拉回路。测试结果正确。 图：2-4测试4测试数据5：66121323454656测试结果：结果分析：测试数据表示一个6个顶点，6条边的图，1、2相连，1、3相连,2、3相连,4、5相连，4、6相连，5、6相连。如下图2-5所示：541541632632 图：2-5不存在欧拉回路。测试结果正确。测试结果总结：通过对多种情况设计了多组数据多次测试如上，结果都得到了真确的结论。说明程序符合题目的要求，达到了实验的目的。六．用户使用说明：首先本程序中的所有顶点编号为1-N的整数。(0<N<1000)先输入图顶点的个数要求为一个正整数n，然后输入图所有边的条数要求为正整数e，再图边数行整形数，每行两个数（用空格相隔）表示一条边所连接的两个顶点编号。输出结果即为题目的解。七．参考文献：[1]王昆仑，李红.数据结构与算法.北京：高等教育出版社，2007年6月第1版[2]屈婉玲，耿素云，张立昂.离散数学.北京：高等教育出版社，2008年3月第1版八．附录：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAX_VERTEX_NUM1000//顶点的最大个数typedefstruct{ intn;//顶点个数 inte;//边的条数 intvexs[MAX_VERTEX_NUM];//一维数组储存顶点 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边}MGraph;//图intvisited[MAX_VERTEX_NUM];//全局变量。在对顶点进行深度优先搜索遍历时的辅助变量数组intEuleriancycle(MGraph*mg);//判断顶点的度数是否全为偶数，有奇数时输出0，全为偶数时输出1MGraph*creat_MGraph();//将图转化为邻接矩阵储存起来，返回邻接矩阵的首地址intdfs_trave(MGraph*mg);//深度优先搜索遍历voiddfs(MGraph*mg,inti);//深度优先搜索voidmain(){ intnum,m;//num用来接收顶点度数判断的结果，m用来接收图是否为连通图的结果 MGraph*mg; mg=creat_MGraph();//建立邻接矩阵 num=Euleriancycle(mg);//判断顶点的度数是否全为偶数。全为偶数时num=1；否则num=0 if(num!=1) { printf("不存在欧拉图！\n"); getchar(); exit(0); } m=dfs_trave(mg);//判断图是否为连通图 if(m!=1) printf("不存在欧拉图！\n"); else printf("存在欧拉图！\n"); getch();}MGraph*creat_MGraph()//建立邻接矩阵{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("请输入顶点的个数："); scanf("%d",&n); printf("请输入边的条数："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//标记存在的边 } returnmg;//返回邻接矩阵的首地址}intEuleriancycle(MGraph*mg)//判断是否存在欧拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { If((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return0; } return1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1}intdfs_trave(MGraph*mg)//深度优先搜索遍历{ inti,m=0; for(i=1;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } returnm;//返回调用dfs函数的次数}voiddfs(MGraph*mg,inti)//深度优先搜索{ intj; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索}

本科生学位论文论多媒体技术在教学中的应用姓名：指导教师：专业：教育管理专业年级：完成时间：

论多媒体技术在教学中的应用[摘要]多媒体不再是传统的辅助教学工具，而是为构造一种新的网络教学环境创造了条件，特别是对于教育社会化来说，多媒体网络是一种更理想的传播工具。多媒体本身具有：融合性、非线性化，无结构性、相互交涉性、可编辑性、实时性等特点；同时运用在教育教学上又有其特长：利于信息的存储利用、是培养发散性思维的工具、促使学习个别化的实现。多媒体在教学中的应用有着多种的形式，它在提高学生学习兴趣上有着积极的作用，同时它还能促进学生知识的获取与保持、对教学信息进行有效的组织与管理、建构理想的学习环境，促进学生自主学习等多方面的效果。立足未来发展，利用多媒体网络技术，开展教学试验。[关键词]多媒体网络教学系统资源共享多媒体技术主要指多媒体计算机技术，加工、控制、编辑、变换，还可以查询、检索。人们借助于多媒体技术可以自然贴切地表达、传播、处理各种视听信息，并具有更多的参与性和创造性。当今多媒体已成为广泛流传的名词，但人们对于它的认识，特别是对于它在教育教学方面如何更好应用，未知的因素还很多。

一、多媒体的教育特长任何一种媒体不管其怎样先进，它只能是作为一种工具被应用到教育领域，能不能促进教育的改革，。。。。。。应当吸取教训，加强理论研究，充分认识多媒体的特性及其教育特长，以便更好地在教育领域开发应用多媒体。

1、多媒体的特性

（1）融合性多种符号系统的融合是多媒体的特性之一，多媒体的这一特性区别于过去媒体符号系统的单一性或复合性。也就是说多媒体技术不是将符号系统叠加，而是具有整体性的融合。

（2）非线性化，无结构性因为多媒体是在超文本、，其组合结构是固定的、不变的。

（5）实时性多媒体信息中的声音、活动视濒、动画于时间有密切联系，对它们进行呈现、交互等集成处理是实时的。在显示某一主体内容时，其视听信息具有同步性。

2、多媒体的教育特长

（1）信息的存储利用便利多媒体特别是多媒体WWW网络信息的存储、提取、双向传输非常便利，它应用于教育，更利于教学信息传播机制的建立。

（2）发散性思维的工具在培养学习者发散性思维方面…………或创造性思维的基础。

（3）促使学习个别化的实现多媒体WWW网络有利于个别化的实现。因为学习者各人需求、学习经验、认知程度等不同，学习方法也有差异，由于多媒体教学信息的多角度多层次性，不具有固定的学习目标和既定学习路径，学习者可以自定学习路径选择自己需要的学习内容。

四、迎接信息时代，运用多媒体技术，实现网络教学传播

21世纪是一个信息高速发展的时代，…………，首先必须认清以下问题：

（一）多媒体不等于光盘化

。。。。。。由于人们认为这就是