欧拉回路的判定

软件设计文档

文档管理信息表项目名称欧拉回路判定版本内容编写代码关键字欧拉回路参考文档数据结构课本（C语言版）创建时间创建人最新发布日期文档变更纪录日期更改内容2012.07.06判断函数中是否存在欧拉回路的函数编写深度优先搜索、建栈、出栈代码的编写图的建立和邻接表存储结果的建立的代码的编写2012.07.09欧拉回路的判定函数的优化对已经编写的程序进行相应的注释和修改主要修改邻接表的创建工作！核心是数据部分2012.07.10对邻接表的建立函数做更近一步的修改，便于后面的操作重新修改文件，利于组内对代码的调试和使用修改深度优先搜索函数进行了文件的导入部分的函数的修改2012.07.11对欧拉回路的判断函数进行修改对深度优先搜索函数进行修改和完善对邻接表的建立函数做进一步的修改2012.07.12在建立图的函数中加入混合图的建立部分。对栈的相关程序做了修改，调整了栈的逆置和输出。更正了DFSTravers。函数并成功输出了欧拉回路的路径和权值。在建立图的函数中加入有向图的建立部分2012.07.13对欧拉回路的判定函数进行修改和完善对深度优先搜索的函数进行修改和完善对建立图的数据进行修改2012.07.14对有向图的欧拉回路进行修改对深度优先搜索函数和showstack函数做了适当调整。修改实习文档2012.07.16多有向图的欧拉回路进行改进校对并精简了我们的代码，确认了文件和函数修改了文档，对代码进行注释

文档主要评审意见产品组评审人员日期意见QA组评审人员日期意见TOC\o"1-5"\h\z\o"CurrentDocument"开发规划 1\o"CurrentDocument"编写目的与范围 1开发人员 1开发计划 1\o"CurrentDocument"开发环境和工具 1开发规范 错误！未定义书签。\o"CurrentDocument"总体设计 2\o"CurrentDocument"概念术语描述 2基本设计描述 2系统总体逻辑结构图 错误！未定义书签。系统部署结构图 错误！未定义书签。主要界面流程描述 错误！未定义书签。功能1界面流程 错误！未定义书签。功能2界面流程 错误！未定义书签。TOC\o"1-5"\h\z模块列表 2\o"CurrentDocument"数据结构及说明 3全局常量、变量及数据结构 9\o"CurrentDocument"重要局部变量及数据结构 9接口规范 错误!未定义书签。<模块1API> 15Interfacel 错误！ 未定义书签。Interface2 错误！ 未定义书签。\o"CurrentDocument"<模块2API> 15\o"CurrentDocument"<模块3API> 15模块设计 16\o"CurrentDocument"Module1设计 16Module2设计 错误！未定义书签。附录 32参考资料 32附加文档 错误！未定义书签。1开发规划计划在训练开始的十天内完成程序代码的编写及初步调试工作，后面的几天主要进行代码的进一步调试，准备答辩1.1编写目的与范围这个程序是由三个模块组成，每个模块都有各自的功能，三个模块功能紧密结合完成欧拉回路的判断工作。第一个模块的功能是根据输入的数据建立一个图，这个图可以是有向图、无向图也可以是混合图，并且用邻接表存储形式表示；第二个模块的功能是根据第一个模块中创建的图进行判断该图中是否存在欧拉回路;第三个模块的功能是根据第二个模块中的判断结果，如果图中存在欧拉回路，则对图进行深度优先搜索，并且输出一条有效的欧拉回路及路径长度，并将结果输出到文件中。1.2开发人员角色主要职责负责模块人员备注项目经理PM项目全面负责项目设计主要框架/模块编写项目进度控制■产品经理PT定义需求产品监督结果验证（测试）用户文档程序员DEV■编写代码■程序员DEV■编写代码■1.3开发计划日期内容1.4开发环境和工具开发工具工具作用CodeblockIDE

Word撰写文档TortoiseSVN版本控制2总体设计2.1概念术语描述定义系统或产品中涉及的重要术语，为读者在阅读文档时提供必要的参考信息。序号术语或缩略语说明性定义1PMProjectManager,项目经理2PT产品经理DEV程序员2.2基本设计描述2.3模块列表模块名称（英文）功能输入数据输出数据备注CreateALGraph建立图包括边数，顶点数，顶点数据，权值，以邻接表的形式输出图自定义的地址GraphlSOuLa判断该图是否存在欧拉回路定点的入度和出度Ture\FALSEDFS对图进行深度优先搜索，记录每个顶点的入度和出度定点、地址一条欧拉回路和路径长度3数据结构及说明3.1全局常量、变量及数据结构常量名称所在目录功能Max_Vertex_Numtypedef structVNode限制了最大的顶点数TURE=1StatusGraphlSOuLa、DFS判断是否存在欧拉回路、深度优先搜索中标记该路径是否已被访问ERROR=0StatusGraphlSOuLa、DFS判断是否存在欧拉回路、深度优先搜索中标记该路径是否已被访问Digraph=2typedefstruct定义图的种类Undigraph=3typedefstruct定义图的种类Mixgraph=4typedefstruct定义图的种类变量全局变量：Max_Vertex_NumEdgeType定义新的类型名VertexType定义新的类型名数据结构包括图的邻接表结构存储、深度优先遍历、记录边的信息typedefstructArcNode//边表结点{intadjvex;//该弧所指向的位置structArcNode*Next_Arcs;//指向下一条弧的指针EdgeTypeweight;//^重}ArcNode;记录顶点信息typedefstructVNode//顶点表结点{VertexTypedata;//顶点信息ArcNode*First_Arcs;//指向第一条依附该顶点的弧的指针intvisited;intDegree;//度intOutDegree;//出度intInDegree;//入度}Vex_Node,Adjacent_list[Max_Vertex_Num];记录图的种类typedefstruct{Adjacent_listadjList;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;根据自定义的文件生成图ALGraphCreateALGraph(ALGraphp,char*path){FILE*fp=fopen(path,"rt");if(fp==NULL){printf("打开文件失败");exit(1);}fscanf(fp,"%d”,&p.kind);if(p.kind==Digraph)//如果是有向图则进行有向图的建立{printf("进行有向图的建立\n");inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d%d”,&p.adjList[i].data,&p.adjList[i].InDegree,&p.adjList[i].OutDegree);//读入顶点数据和出度入度p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}}elseif(p.kind==Undigraph)//进行无向图的建立{printf("进行无向图的建立\n");inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d”,&p.adjList[i].data,&p.adjList[i].Degree);//读入顶点数据和度数p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}}elseif(p.kind==mixgraph)//进行混合图的建立{fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数intcur,i,j,weight;for(i=0;i<p.vexnum;i++){fscanf(fp,"%d”,&p.adjList[i].data);//读入顶点数据p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}cur=0;while(cur<=p.arcnum){ArcNode*e;fscanf(fp,"%d”,&p.kind);if(p.kind==Undigraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}elseif(p.kind==Digraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}cur++;}}fclose(fp);returnp;}3.2重要局部变量及数据结构变量inti=0;intk,j,weight;ArcNode*e;数据结构创建图：ALGraphCreateALGraph(ALGraphp,char*path){FILE*fp=fopen(path,"rt");if(fp==NULL){printf("打开文件失败”)；exit(1);}fscanf(fp,”%d”,&p.kind);if(p.kind==Digraph)//如果是有向图则进行有向图的建立{printf("进行有向图的建立\n");inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d%d”,&p.adjList[i].data,&p.adjList[i].InDegree,&p.adjList[i].OutDegree);//读入顶点数据和出度入度p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}}elseif(p.kind==Undigraph)//进行无向图的建立{printf("进行无向图的建立\/);inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d”,&p.adjList[i].data,&p.adjList[i].Degree);//读入顶点数据和度数p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}}elseif(p.kind==mixgraph)//进行混合图的建立{fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数intcur,i,j,weight;for(i=0;i<p.vexnum;i++){fscanf(fp,”%d”,&p.adjList[i].data);//读入顶点数据p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}cur=0;while(cur<=p.arcnum){ArcNode*e;fscanf(fp,”%d”,&p.kind);if(p.kind==Undigraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}elseif(p.kind==Digraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}cur++;}}fclose(fp);returnp;}变量ArcNode*e,*m,*q,*t,*n;inti,j,m,count;数据结构判断图中是否存在欧拉回路：boolUnConGraph(ALGraphG)//无向图的连通判定及部分非欧拉回路判定{inti=0;intj=0;if(G.vexnumv=2)returnFALSE;while(ivG.vexnum){if(G.adjList[i].First_Arcs->Next_Arcs==NULL)j++;i++;}if(j==G.vexnum-1)returnTRUE;returnTRUE;}boolDiLGraphIsOuLa(ALGraphG)//有向连通图的判断{ArcNode*e,*m,*q,*t,*n;m=t=NULL;inti=0,j=0;while(ivG.vexnum){if(G.adjList[i].InDegree==0)i++；e=G.adjList[i].First_Arcs;if(G.adjList[e->adjvex].InDegree>=1&&GadjList[e->adjvex].OutDegree>=1){q=G.adjList[i].First_Arcs;}if(G.adjList[i].OutDegree>=1){m=GadjList[e->adjvex].First_Arcs;if(m!=NULL&&m->Next_Arcs!=NULL){m=m->Next_Arcs;}}if(G.adjList[e->adjvex].OutDegree!=0){e=G.adjList[e->adjvex].First_Arcs;while(e!=NULL){if(G.adjList[e->adjvex].InDegree>=2)n=e;if(e==q)returnTRUE;if(n==e){j++;if(j==2)returnTRUE;}if(G.adjList[e->adjvex].OutDegree>=2){t=G.adjList[e->adjvex].First_Arcs;if(t!=NULL&&t->Next_Arcs!=NULL)t=t->Next_Arcs;}if(t!=NULL&&G.adjList[e->adjvex].OutDegree==0){e=t;t=NULL;}if(G.adjList[e->adjvex].OutDegree==0){if(e->Next_Arcs==NULL)returnFALSE;}if(G.adjList[e->adjvex].OutDegree!=0){e=G.adjList[e->adjvex].First_Arcs;}}}if(m!=NULL&&GadjList[e->adjvex].OutDegree==0){e=m;m=NULL;}i++;}returnFALSE;}boolDiGraphIsOuLa(ALGraphG)//有向图的判定{inti=0;intj=0;if(G.vexnum==1){returnFALSE;}while(i<G.vexnum){if(G.adjList[i].OutDegree==GadjList[i].InDegree)j++;i++;}if(j==G.vexnum-1){returnTRUE;}else{if(!DiLGraphIsOuLa(G)){returnFALSE;}}returnTRUE;boolUnOGraphISOuLa(ALGraphG)//无向图的判定{if(!UnConGraph(G)){returnFALSE;}inti=0,m=0;while(i<G.vexnum){if((G.adjList[i].Degree)==1)m++;i++;}if(m>=G.vexnum-2){returnFALSE;}returnTRUE;}boolUnGraphISOuLa(ALGraphG)//无向图的进一步判定{intcount=0,i=0;if(UnOGraphISOuLa(G)){returnTRUE;}else{intj=0;while(i<Gvexnum){if(G.adjList[i].Degree==2*j+1){count++;}i++;}}for(i=0;i<G.vexnum;i++){if(count==2*i){returnTRUE;}returnFALSE;}boolGraphISOuLa(ALGraphG)//无向图及有向图的欧拉回路的判定条件{if(G.kind==2)//如果是有向图{if(DiGraphIsOuLa(G))returnTRUE;}elseif(G.kind==3){if(UnGraphISOuLa(G))returnTRUE;}returnFALSE;}变量inti,k;Nodes*top,*ntop;Vex_Node*p;ArcNode*q;数据结构对图进行深度优先搜索voidDFSTraverse(ALGraphG,char*path)//深度优先搜索{inti,k;Nodes*top,*ntop;Vex_Node*p;ArcNode*q;if(!GraphISOuLa(G)){printf("该图不能构成欧拉回路\n");exit(1);}elseprintf("该图能构成欧拉回路\/);for(i=0;i<G.vexnum;++i){ntop=top=InitStack(top);if(!G.adjList[i].visited){p=G.adjList+i;p->visited=TRUE;Push(top,p->data,0);}while(top->next!=NULL&&k!=-1){k=GetTop(top);p=G.adjList+k;q=p->First_Arcs;while(q&&k!=-1){if(!G.adjList[q->adjvex].visited){Push(top,q->adjvex,q->weight);p=GadjList+q->adjvex;p->visited=TRUE;q=p->First_Arcs;if(q==NULL){Pop(top);break;}}elseif(q->adjvex==i){k=-1;Push(top,q->adjvex,q->weight);while(ntop->next!=NULL){ntop=ntop->next;}Inverse(top,ntop,path);DestroyStack(top);}else{k=Judge(top,q,path);if(k==-1){p=G.adjList+q->adjvex;q=p->First_Arcs;p->visited=TRUE;}elseif(q->Next_Arcs){q=q->Next_Arcs;}else{q=NULL;Pop(top);break;}}}}}}4接口规范<模块1>ALGraphCreateALGraph(ALGraphp,char*path)Function图的建立：根据在文件中读取得数据建立符合文件要求的有向图、无向图、混合图。用邻接表结构存储。<模块2>boolUnConGraph(ALGraphG)//无向图的连通判定及部分非欧拉回路判定boolDiLGraphIsOuLa(ALGraphG)//有向连通图的判断boolDiGraphIsOuLa(ALGraphG)//有向图的判定boolUnOGraphISOuLa(ALGraphG)//无向图的判定boolUnGraphISOuLa(ALGraphG)//无向图的进一步判定boolGraphISOuLa(ALGraphG)//无向图及有向图的欧拉回路的判定条件Function欧拉回路的判定：根据模块一中建立的图分出是有向还是无向，判断该图中是否存在欧拉回路，若存在则返回TRUE，否则返回FASLE.<模块3>typedefstructNodes〃链栈的建立{VertexTypedata;EdgeTypeweight;structNodes*next;}Nodes,*LNodes;Nodes*top;Nodes*InitStack(Nodes*top)//初始化操作Nodes*Push(Nodes*top,intx,inty)//入栈voidPop(Nodes*top)〃出栈intGetTop(Nodes*top)voidDestroyStack(Nodes*top)voidShowStack(Nodes*top,Nodes*q,Nodes*ntop,char*path)〃栈的遍历voidInverse(Nodes*top,Nodes*ntop,char*path)//采用链表的逆置对栈实行逆置intJudge(Nodes*top,ArcNode*tmp,char*path)//*U断是否构成回路voidDFSTraverse(ALGraphG,char*path)//深度优先搜索Function根据模块二中的判定，若图中存在欧拉回路，则对图进行深度优先搜索，并输出一条欧拉回路及路径长度，将输出结果存入文件中；若不存在欧拉回路则程序结束。5模块设计5.1Modulel设计typedefstructArcNode//边表结点{intadjvex;//该弧所指向的位置structArcNode*Next_Arcs;//指向下一条弧的指针EdgeTypeweight;//权重}ArcNode;typedefstructVNode//顶点表结点{VertexTypedata;/顶点信息ArcNode*First_Arcs;//指向第一条依附该顶点的弧的指针intvisited;intDegree;//度intOutDegree;//出度intInDegree;//A度}Vex_Node,Adjacent_list[Max_Vertex_Num];typedefstruct{Adjacent_listadjList;intvexnum,arcnum;//图的当顶点数和弧数intkind;〃图的种类标志}ALGraph;名称所在目录功能前导文件typedefstructArcNodetypedefstructArcNode边表结点typedefstructVNode/ypedefstructVNode顶点表结点typedefstructtypedefstruct记录途中的顶点数和弧数ALGraphCreateALGraph(ALGraphp,char*path)ALGraphCreateALGraph(ALGraphp,char*path)建立图读取文件信息，用邻接表结构存储ALGraphCreateALGraph(ALGraphp,char*path){FILE*fp=fopen(path,"rt");if(fp==NULL){printf("打开文件失败”);exit(1);}fscanf(fp,”%d”,&p.kind);if(p.kind==Digraph)//如果是有向图则进行有向图的建立{printf("进行有向图的建立\n");inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d%d”,&p.adjList[i].data,&p.adjList[i].InDegree,&p.adjList[i].OutDegree);//读入顶点数据和出度入度p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}}elseif(p.kind==Undigraph)//进行无向图的建立{printf("进行无向图的建立\n");inti=0;intk,j,weight;ArcNode*e;fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数for(i=0;i<p.vexnum;i++){fscanf(fp,"%d%d”,&p.adjList[i].data,&p.adjList[i].Degree);//读入顶点数据和度数p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}for(k=0;k<p.arcnum;k++){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}}elseif(p.kind==mixgraph)//进行混合图的建立{fscanf(fp,"%d%d”,&p.vexnum,&p.arcnum);//读入顶点数，读入边数//printf("%d%d\n”,p.vexnum,p.arcnum);intcur,i,j,weight;for(i=0;i<p.vexnum;i++){fscanf(fp,”%d”,&p.adjList[i].data);//读入顶点数据//printf("%d\n”,p.adjList[i].data);p.adjList[i].First_Arcs=NULL;//边表置为空p.adjList[i].visited=FALSE;}cur=0;while(cur<=p.arcnum){ArcNode*e;fscanf(fp,”%d”,&p.kind);//printf("%d\n",p.kind);if(p.kind==Undigraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;//printf("%d",e->adjvex);e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;e=(ArcNode*)malloc(sizeof(ArcNode));e->weight=weight;e->adjvex=i;//printf("%d%d\n",e->adjvex,e->weight);e->Next_Arcs=(ArcNode*)p.adjList[j].First_Arcs;p.adjList[j].First_Arcs=e;}elseif(p.kind==Digraph){e=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d”,&i,&j,&weight);//读入边(vi,vj)上的顶点序号，权重e->weight=weight;e->adjvex=j;//printf("%d%d%d\n”,i,e->adjvex,e->weight);e->Next_Arcs=(ArcNode*)p.adjList[i].First_Arcs;p.adjList[i].First_Arcs=e;}cur++;}}fclose(fp);returnp;}

5.2Module2设计分别判断有向图、无向图是否有回路boolUnConGraph(ALGraphG)//无向图的连通判定及部分非欧拉回路判定{inti=0;intj=0;if(G.vexnum<=2)returnFALSE;while(ivGvexnum){if(G.adjList[i].First_Arcs->Next_Arcs==NULL)j++；i++;}if(j==G.vexnum-1)returnTRUE;returnTRUE;}boolDiLGraphIsOuLa(ALGraphG)//有向连通图的判断{ArcNode*e,*m,*q,*t,*n;m=t=NULL;inti=0,j=0;while(i<Gvexnum){if(G.adjList[i].InDegree==0)i++;e=G.adjList[i].First_Arcs;if(G.adjList[e->adjvex].InDegree>=1&&GadjList[e->adjvex].OutDegree>=1)q=G.adjList[i].First_Arcs;if(G.adjList[i].OutDegree>=1){m=G.adjList[e->adjvex].First_Arcs;if(m!=NULL&&m->Next_Arcs!=NULL)m=m->Next_Arcs;}if(G.adjList[e->adjvex].OutDegree!=0){e=G.adjList[e->adjvex].First_Arcs;while(e!=NULL){if(G.adjList[e->adjvex].InDegree>=2)n=e;if(e==q)returnTRUE;if(n==e){j++;if(j=2)returnTRUE;}if(G.adjList[e->adjvex].OutDegree>=2){t=G.adjList[e->adjvex].First_Arcs;if(t!=NULL&&t->Next_Arcs!=NULL)t=t->Next_Arcs;}if(t!=NULL&&G.adjList[e->adjvex].OutDegree==0){e=t;t=NULL;}if(G.adjList[e->adjvex].OutDegree==0){if(e->Next_Arcs==NULL)returnFALSE;}if(G.adjList[e->adjvex].OutDegree!=0)e=GadjList[e->adjvex].First_Arcs;}}if(m!=NULL&&GadjList[e->adjvex].OutDegree==0){e=m;m=NULL;}i++;}returnFALSE;}boolDiGraphIsOuLa(ALGraphG)//有向图的判定{inti=0;intj=0;if(G.vexnum==1)returnFALSE;while(i<Gvexnum){if(G.adjList[i].OutDegree==GadjList[i].InDegree)j++;i++;}if(j==G.vexnum-1)returnTRUE;else{if(!DiLGraphIsOuLa(G))returnFALSE;}returnTRUE;}boolUnOGraphISOuLa(ALGraphG)//无向图的判定{if(!UnConGraph(G))returnFALSE;intm=0;if(m>=G.vexnum-2)returnFALSE;returnTRUE;}boolUnGraphISOuLa(ALGraphG)//无向图的进一步判定{intcount=0,i=0;if(UnOGraphISOuLa(G))returnTRUE;else{intj=0;while(ivGvexnum){if(G.adjList[i].Degree==2*j+1)count++;i++;}}for(i=0;ivGvexnum;i++){if(count==2*i)returnTRUE;}returnFALSE;}boolGraphISOuLa(ALGraphG)//无向图及有向图的欧拉回路的判定条件{if(G.vexnum>Garcnum)returnFALSE;if(G.kind==2)//如果是有向图{if(DiGraphIsOuLa(G))returnTRUE;}elseif(G.kind==3)if(UnGraphISOuLa(G))returnTRUE;}returnFALSE;}5.2.1函数调用关系boolGraphISOuLa(ALGraphG)//无向图及有向图的欧拉回路的判定条件中调用boolUnOGraphISOuLa(ALGraphG)//无向图的判定和boolboolDiGraphIsOuLa(ALGraphG)UnOGraphISOuLa(ALGraphG)//无向图的判定中调用boolUnOGraphISOuLa(ALGraphG)//无向图的判定和boolUnConGraph(ALGraphG)//无向图的连通判定boolDiGraphIsOuLa(ALGraphG)中调用boolDiLGraphIsOuLa(ALGraphG)//有向连通图的判断

5.3Module3设计创建链栈，深度优先搜索并用栈存储路径和权值typedefstructNodes〃链栈的建立{VertexTypedata;EdgeTypeweight;structNodes*next;}Nodes,*LNodes;Nodes*top;Nodes*InitStack(Nodes*top)//初始化操作{top=(LNodes)malloc(sizeof(Nodes));top->data=-1;top->next=NULL;returntop;}Nodes*Push(Nodes*top,intx,inty)//入栈{Nodes*nodes;nodes=(LNodes)malloc(sizeof(Nodes));if(!nodes)printf("createastack");nodes->data=x;nodes->weight=y;nodes->next=top->next;top->next=nodes;returntop;}voidPop(Nodes*top)〃出栈{Nodes*nodes;if(top->next==NULL)printf("Thestackisempty");nodes=top->next;top->next=nodes->next;free(nodes);}intGetTop(Nodes*top){returntop->next->data;}voidDestroyStack(Nodes*top){Nodes*p=top;while(p->next!=NULL){Pop(p);}}voidShowStack(Nodes*top,Nodes*q,Nodes*ntop,char*path)〃栈的遍历{intweight=0;FILE*fp=fopen(path,"at");if(fp==NU