数据结构与算法课程设计报告..doc

合肥学院 计算机科学与技术系 课程设计报告 2012 ～2013 学年第 2 学期 课程 数据结构与算法设计课程设计 课程设计名称 欧拉回路 学生姓名 陶飞 学号 1104012039 专业班级 计算机科学与技术11级3班 指导教师 李红，何立新，华珊珊，陈艳平 2013 年 3月 题目： 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ 一．问题分析和任务定义： 题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素云、张立昂主编的《离散数学》P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。 首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先有哪些信誉好的足球投注网站遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。 然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。 当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。 二．数据结构的选择与概要设计： 数据结构的选择： 图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下： typedef struct { int n;//顶点个数 int e;//边的条数 int vexs[MAX_VERTEX_NUM];//一维数组储存顶点 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边 }MGraph;//图 2.概要设计 首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行有哪些信誉好的足球投注网站得图中到每个顶点的度数，如果有奇度顶点，输出：不存在欧拉回路，即可结束程序。否则继续判断给定的图是否为连通图，如果是连通图输出：存在欧拉回路；否则输出：不存在欧拉回路。结束程序。 三．详细设计和编码： 1.将图转化为邻接矩阵存储： 先输入图中顶点个个数和边的条数，对所有可能存在的边初始化为0，再依次输入边的信息，即如果顶点1,2存在相连的边，输入1 2 （1,2为自动给顶点分配的编码）。将边1,2的信息改为1。用函数MGraph *creat_MGraph();完成，返回邻接矩阵的首地址即可。 MGraph *creat_MGraph()//建立邻接矩阵 { int i,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;//标记存在的边 } return mg;//返回邻接矩阵的首地址 } 2.有哪些信誉好的足球投注网站有没有奇度顶点： 对邻接矩阵的每一行进行有哪些信誉好的足球投注网站，用num记录顶点的度数（每次对新的顶点记录前都将num置