《数据结构与算法课程设计报告--图遍历的演示.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计报告--图遍历的演示.docx（16页珍藏版）》请在课桌文档上搜索。
1、行等机科学与技术系课程设计报告20142015学年第二学期课程数据结构与算法课程设计名称图遍历的演示图遍历的演示一、 问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。任选国内城市，起点为合肥，暂时忽略里程。设图的结点20-30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,，n）。通过输入图的全部边（存于数据文件中，从文件读写）输入一个图，每个边为一个数对
2、，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。二、 数据结构的选择和概要设计城市与城市之间的关系无向图采用邻近多重表来实现,主要要表示无向图中的各个结点和边。我们要以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集，将该结果通过一定形式打印出来。1、数据结构的选择typedefstructENodeintivex,jvex;structENode*ilink;structENode*jlink;ENode;边的结点类型typedefstructVNodeintmark;chard
3、ata;intnumber;ENode*firstedge;VNode;顶点的结点类型typedefstructVNodeamiistMAX;intnumberOfVerts;intnumberOfEerts;Graph;图的信息typedefstructQENodeintdata;structQENode*next;QENode;队列结点该边依附的两个顶点在数组中的序号指向下一条依附于顶点ivex的边指向下一条依附于顶点jvex的边顶点信息顶点编号顶点数边数typedefstruct(QENode*rear;QENode*front;LinkQucue;队列的定义2、函数原型清单队列初始化函
4、数：voidInitQucue(LinkQueue*Q)入队列函数：voidQueueAppcnd(LinkQueue*Q,intv)出队列函数：voidQueueDclete(LinkQueue*Q,int*v)图初始化函数：voidInitilized(Graph*graph)图创建函数：voidCreateGraph(Graph*graph)访问标记设置函数：voidSetMark(Graph*graph)深度优先搜索遍历(DFS)函数：voidDFS(Graph*graph,intv)广度优先搜索遍历(BFS)函数：voidBFS(Graph*graph,intu)3、程序流程框架图选
5、择起始点一4J4JT4J广度优先遍历深度优先遍历退出程序。图-1.程序流程框架三、 详细设计和编码程序主体部分主要包括两大部分，一部分是对图的信息的处理，另一部分是关于遍历算法。这其中包含了邻接多重表构造的无向图的初始化深度优先搜索遍历和广度优先搜索遍历算法的应用。我们的题目是关于图遍历的演示，那么涉及到重点就是遍历算法，以下我们来围绕遍历算法进行探讨。1、深度遍历函数名称：voidDFS(Graph*graph,intv)函数参数：Graph*graph为创建的图intV指明当前开始结点。函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号参数。具体代码：voidDFS(Gr
6、aph*graph,intV)深度遍历(ENode*p;printf(,%c1”,v);graph-amlistv.mark=1;p=graph-amlistv.firstedge;whiIe(p!=NULL)(if(p-ivex=v)(if(graph-amlistp-jvex.mark=0)(printfCn*,p-ivex,p-jvex);DFS(graph,p-jvex);)p=p-ilink;)else(if(graphamlistp-ivex.mark=0)(printf(*n,p-jvex,p-ivex);DFS(graph,p-ivex);)p=p-jlink;)2、广度遍历函
7、数名称：voidBFS(Graph*graph,intu)函数参数：Graph*graph为创建的图intU为开始的结点。函数功能：实现一张无向图从一个指定的结点的广度优先搜索遍历，并将输出结点打印出来。具体代码：voidBFS(Graph*graph,intU)广度遍历(LinkQucueQ;ENode*p;InitQueue(&Q);printf(,%c1”,u);graph-amlistu.mark=1;QucueAppend(&Q,u);whiIe(Q.front!=Q.rear)(QucueDclete(&Q,&u);p=graph-amlistu.firstedge;whiIe(p
8、!=NULL)if(p-ivex=u)if(graphamlistp-jvex.mark=0)(QucueAppend(&Q,p-jvex);graph-amlistp-jvex.mark=1;printf(*n*,p-ivex,p-jvex);printf(,%c1”,p-jvex);)p=p-ilink;)else(if(graph-amlistp-ivex.mark=0)(QucueAppend(&Q,p-ivex);graph-amlistp-ivex.mark=1;printf(,11z,p-jvex,p-ivex);printf(,%c1p-ivex);)p=p-jlink;)以上
9、就是我们对深度优先搜索遍历算法和广度优先搜索遍历算法的数据算法的讨论,那么本题中核心算法介绍完后，就要讲讲最为基础但必不可少的算法程序了。3、图的初始化函数名称：voidInitilized(Graph*graph)函数参数：Graph*graph指向图指针。函数功能：分配空间给图，并将关于图的顶点和边的参数置为空。具体代码：voidInitilized(Graph*graph)图的初始化(graph=(Graph*)malloc(sizeof(Graph);graph-numberOfVerts=0;graph-numberOfEerts=0;)4、图的创建函数名称：voidCreateGr
10、aph(Graph*graph)函数参数：Graph*graph指向图指针。函数功能：由用户自定义输入数据，创建一张固定结点和边数的无向图。具体代码：voidCreateGraph(Graph*graph)图的创建图ENode*p,*q,*e;inti;Printf(“请输入连通无向图的顶点数和边数例如33：n*);scanf(%d%d”,fegraph-numbcrOfVerts,&graph-numberOfEerts);for(i=l;inumbcrOfVerts;i+)(Printf(请输入第%d个顶点的信息：n”,i);scanf(z,%szz,&graph-amlisti.data
11、);graph-amlisti.number=i;graph-amlisti.firstedge=NULL;graph-amlisti.mark=0;)for(i=l;inumbcrOfEerts;i+)(p=(ENode*)mal1oc(sizeof(ENode);Printf(请输入每条边的信息(编号小的在前例如13回车12回车23)n);scanf(*%d%d*,ftp-ivex,&p-jvex);p-ilink=p-jlink=NULL;if(graph-amlistp-ivex.firStedge=NULL)graph-amlistp-ivex.firstedge=p;else(q=
12、graph-amlistp-ivex.firstedge;whiIe(q!=NULL)(e=q;if(q-ivex=p-ivex)q=q-ilink;elseq=q-jlink;)if(e-ivex=p-ivex)e-ilink=p;elsee-jlink=p;)if(graph-amlistp-jvex.fIrstedge=NULL)graph-amlistp-jvex.firstedge=p;else(q=graph-amlistp-jvex.firstedge;whiIe(q!=NULL)e=q；if(q-ivex=p-ivex)q=q-ilink;elseq=q-jlink;)if(e
13、-ivex=p-ivex)e-ilink=p;elsee-jlink=p;)5、进入队列函数名称：voidQueucAppcnd(LinkQueue*Q,intv)函数参数：LinkQueue*Q链表，intV为新元素。函数功能：使新元素入队。具体代码：voidQueueAppend(LinkQueue*Q,intV)入队列(QENode*p;p=(QENode*)malloc(sizeof(QENode);p-data=V;p-next=NULL;Q-rear-next=p;Q-rear=p;)6、出队列函数名称：voidQueueDclete(LinkQueue*Q,int*v)函数参数：
14、LinkQueue*Q链表，int*v为替换指针。函数功能：实现元素离开队列。具体代码：voidQueueDelete(LinkQueue*Q,int*v)出队列QENode*p;if(Q-front=Q-rear)return;p=Q-front-next;*v=p-data;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);)四、 上机调试过程程序刚完成的时候，进行了多次调试，我们解决了不少的问题，那么其中就有链接多重表的存储错误，或者是广度优先搜索遍历出现溢出的现象，也存在为分配内存空间的情况导致程序运行失败，停止工作，其现象如
15、图-3所示。图-2.程序错误五、 测试结果及其分析请输入连通无向图的顶点数和边数例如33：微软拼音半：图-3.测试结果1请输入连通无向图的顶点数和边数例如33：56请输入第1个顶点的信息、；微软拼音半:图-4.测试结果2请输入连通无向图的顶点数和边数例如33：56i醴入第1个顶点的信息逮吊人第2个顶点的信息:矗入第3个顶点的信息:南尼谛输入第4个顶点的信息、：北厅、翰入第5个顶点的信息：3）3）3）3）E藉入每条边的信息（编号小的在前例如13回车i2回车212请输入每条边的信息（编号小的在前例如13回车i2回车213请输入每条边的信息（编号小的在前例如13回车工2回车2褊认每条边的信息（编号小
16、的在前例如13回车12回车223请输入每条边的信息（编号小的在前例如13回车12回车23）34请输入每条边的信息（编号小的在前例如13回车12回车23）楠渐音半：图-5.测试结果3输入深度广度遍历的起始点:2生成树:21345广度遢用序列其狗座生成树:顶点屋列：生成树边集：Processexitedwithreturnvalue0Pressanykeytocontinue.微软拼音半:图-6.测试结果4分析：利用深度优先（DFS）,广度优先（BFS）进行遍历的时候，我参考了许多资料才是功能得以实现。还有，在运行程序的时候，由于疏忽大意，申请空间不足，导致了出现内存问题，使得程序出现了小问题。当
17、然，程序虽然可以完成题目所要求的功能，但是并不够直观。如果时间充裕，我么仍然可以将程序进行改进，增加坐标演示等功能，让用户得到更好的体验。六、 用户使用说明书1、本程序的运行环境是WindoWS8.1操作系统（并向下兼容），Dev-c+2、进入演示程序后即显示“请输入无向连通图的定点数和边数”提示用户进行图的信息的录入。3、在图的初始化完成后会有“请输入第X的顶点的信息”和“请输入每条边的信息（编号小的在前例如13回车12回车23）”提示用户录入数据对图的顶点和边的信息进行录入。七、 参考文献1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2严蔚敏，吴伟明.数据结构.北京
18、：清华大学出版社，2007年5月。3编程中国：http:4 Easyx：http:Ww.easyx.Cn八、 附录程序源码：#includeitincludettdefineMAX30*该边依附的两个顶点在数组中的序号*/*指向下一条依附于顶点ivex的边*/*指向下一条依附于顶点jvex的边*/typedefstructENodeintivex,jvex;structENode*ilink;structENode*jlink;ENode;边或弧的信息typedefstructVNodC顶点类型intmark;chardata;顶点信息intnumber;顶点编号ENode*firstedge
19、;VNode;顶点信息typedefstructVNodeamiistMAX;intFiumbcrOfVerts;顶点的数目intFiumbcrOfEerts;边或弧的数目Graph;图的信息typedefstructQENodeintdata;数据structQENode*next;/指向下一结点)QENocle;队列结点typedefstructQENode*rear;队列尾指针QENode*front;队列头指针JLinkQueue;队列voidInitQueue(LinkQucue*Q)队列的初始化(Q-front=Q-rear=(QENode*)malloc(sizeof(QENod
20、e);Q-front-next=NULL;队列初始化就是头尾指针相等)voidQueueAppcnd(LinkQueuc*Q,intV)入队列(QENode*p;p=(QENode*)malIoc(sizeof(QENodc);分配空间p-data=v;将结点信息放入vp-next=NULL;/p-next指向空Q-rear-next=p;队尾next指向PQ-rcar=p;队尾指针指向p)voidQucueDelete(LinkQueuc*Q,int*v)出队列(QENode*p;if(Q-front=Q-rear)判队空return;p=Q-front-next;*v=p-data;Q-f
21、ront-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);)voidInitiIized(Graph*graph)图的初始化(graph=(Graph*)malloc(sizeof(Graph);graph-numberOfVerts=O;graph-numberOfEerts=O;)voidCreateGraph(Graph*graph)图的创建图ENode*p,*q,*e;inti;Printf(请输入连通无向图的顶点数和边数例如33：n);SCanf(%d%d”,fegraph-numbcrfVerts,&graph-numberOfEert
22、s);输入顶和边for(i=l;inumbcrOfVerts;i+)(Printf(请输入第%d个顶点的信息：n”,i);scanf(*%s*,graph-amlisti.data);读入顶点信息graph-amlisti.number=i;graph-amlisti.firstedge=NULL;点的边表头指针设为空graph-amlisti.mark=0;)for(i=l;inumbcrfEerts;i+)建立边表(p=(ENode*)malloc(sizeof(ENode);分配新结点PPrintf(请输入每条边的信息(编号小的在前例如13回车12回车23)n);SCanf(%d%dz,
23、fep-ivex,&p-jvex);读入边的顶点对应序号p-ilink=p-jlink=NULL;边表初始为空if(graph-amlistp-ivexLfirstedge=NULL)graph-amlistp-ivex.firstedge=p;else(q=graph-amlistp-ivex.firstedge;whiIe(q!=NULD(e=q;if(q-ivex=p-ivex)q=q-ilink;elseq=q-jlink;)if(e-ivex=p-ivex)e-ilink=p;elsee-jlink=p;)if(graph-amlistp-jvex.fIrstedge=NULL)gr
24、aph-amlistp-jvex.firstedge=p;else(q=graph-amlistp-jvex.firstedge;whiIe(q!=NULL)(e=q;if(q-ivex=p-ivex)q=q-ilink;elseq=q-jlink;)if(e-ivex=p-ivex)e-ilink=p;elsee-jlink=p;)voidSctMark(Graph*graph)设置访问标记(inti;for(i=l;inumbcrOfVerts;i+)graph-amlisti.mark=0;)voidDFS(Graph*graph,intV)深度遍历(ENode*p;printf(z,%
25、d,v);graph-amlistv.mark=1;p=graph-amlistv.firstedge;whiIe(p!=NULL)(if(p-ivex=v)(if(graphamlistp-jvex.mark=0)(printfCn*,p-ivex,p-jvex);DFS(graph,p-jvex);)p=p-ilink;)else(if(graph-amlistp-ivex.mark=0)(printf(z,nzz,p-jvex,p-ivex);DFS(graph,p-ivex);)p=p-jlink;voidBFS(Graph*graph,intU)广度遍历(LinkQucueQ;ENo
26、de*p;InitQucue(feQ);printf(,%c1”,u);graph-amlistu.mark=1;QucueAppend(&Q,u);while(Q.front!=Q.rear)(QucueDelete(&Q,&u);p=graph-amlistu.firstedge;whiIe(p!=NULL)(if(p-ivex=u)(if(graph-amlistp-jvex.mark=0)(QucueAppend(&Q,p-jvex);graph-amlistp-jvex.mark=1;printf(,11z,p-ivex,p-jvex);printf(,%c1”,p-jvex);)p
27、=p-ilink;)else(if(graph-amlistp-ivex.mark=0)(QucueAppend(&Q,p-ivex);graph-amlistp-ivex.mark=1;printf(*n*,p-jvex,p-ivex);printf(z,%cl”,p-ivex);)p=p-jlink;)intmain()intvl,v2;Graphgraph;charorder;Initilized(&,graph);CreateGraph(&graph);printf(*n输入深度广度遍历的起始点：n);scanf(%d”,&v2);vl=v2;Printf(n深度遍历序列及相应的生成树:n顶点序列：生成树边集：n);SetMark(&graph);DFS(&graph,v2);Printf(n广度遍历序列及相应生成树：n顶点序列：生成树边集：n);SetMark(&graph);BFS(&graph,vl);return0;)
