最小生成树的方法完成室内布线问题.doc

算法与数据结构课程设计报告书最小生成树：室内布线专 业：计算机科学与技术 成 绩： 烟台大学计算机与控制工程学院四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果）：门不影响两插座路线的测试数据：两插座在相邻墙面上，门处在两插座连线上，测试数据：八、程序代码#include#includeusing namespace std;typedef struct /存放节点数据float x;float y;float h;outlet;typedef struct int no;/存放节点编号int info;/存放节点所处墙面VertexType;typedef struct float edges2020;/存放邻接矩阵数据int n,e;VertexType vexs20;/节点变量MGraph;int Dplace(outlet d4)/根据门四角坐标求门的位置if(d1.x=d2.x&d1.x=d3.x&d1.x=d4.x)/若门四角的横坐标相同if(d1.x=0)/横坐标为0，则门在1号墙壁上return 1;else return 3;/否则在三号墙壁上if(d1.y=d2.y&d1.y=d3.y&d1.y=d4.y)/若门四角纵坐标相同if(d1.y=0)return 2;else return 4;int Oplace(outlet Olet,float a,float b)/插座的位置if(Olet.x=0&Olet.y=0&Olet.h=0)return 1;if(Olet.y=0&Olet.x 0&Olet.h0)return 2; if(Olet.x=a&Olet.y=0&Olet.h=0)return 3;if(Olet.y=b&Olet.x =0&Olet.h=0)return 4;int Xplace(int a,int b)/判断两插座的相对位置if(a=b)/如果两插座在同一面墙上，返回0return 0;if(a=1&(b=2|b=4)|a=2&(b=1|b=3)|a=3&(b=2|b=4)|a=4&(b=3|b=1)/如果两插座在相邻面墙上，返回1return 1;else return 2;float CC(outlet Olet1,outlet Olet2,outlet door4,int a)/有门存在时两插座之间的距离float n;if(a=1|a=3)/当门在第1或3面墙上时if(Olet1.h=door2.h&Olet2.h=door2.h&(Olet1.y=door2.y&door3.y=Olet2.y)|(Olet2.y=door2.y&door3.y=Olet1.y)/若果门处在两插座连线上n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+(door2.h-Olet1.h)+(door2.h-Olet2.h);return n;else/如果门不影响两插座的链接n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+fabs(Olet1.h-Olet2.h);return n;if(a=2|a=4)/如果门在第2 4 面墙上if(Olet1.h=door2.h&Olet2.h=door2.h&(Olet1.x=door2.x&door3.x=Olet2.x|Olet2.x=door2.x&door3.x=Olet1.x)/若果门处在两插座连线上n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+(door2.h-Olet1.h)+(door2.h-Olet2.h);return n;else/如果门在第2 4 面墙上n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+fabs(Olet1.h-Olet2.h);return n;typedef structint u;int v;float w;Edge;void InsertSort(Edge R,int n)/直接插入函数int i,j,h;Edge tmp;for(i=1;i=0&tmp.wRj.w)Rj+1=Rj;j-;Rj+1=tmp;void Kruskal(MGraph g)/克鲁斯卡尔函数int i,j,u1,v1,sn1,sn2,k;int vset400;float m=0;Edge E400;k=0;for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(g.edgesij!=0)Ek.u=i;Ek.v=j;Ek.w=g.edgesij;k+;InsertSort(E,k);for(i=0;ig.n;i+)vseti=i;k=1;j=0;while(kg.n)u1=Ej.u;v1=Ej.v;sn1=vsetu1;sn2=vsetv1;if(sn1!=sn2)m=m+Ej.w;k+;for(i=0;ig.n;i+)if(vseti=sn2)vseti=sn1;j+;cout所需要的电线最短为：endl;cout ceil(m)endl;/输出最短总路线coutendl;int main()MGraph pp;/定义图 float HX,HY,HH;/定义房屋大小int N,i,j,x;int k,l;/暂存节点信息变量float m;cout请输入房屋大小和插座数目：HXHYHHN;if(N20)cout插座超过20，请重新输入：HXHYHHN;while(HX!=0&HY!=0&HH!=0&N!=0)/循环输入设置outlet Olet20;/插座数组outlet c,d;/插座的临时存放cout请输入个插座的坐标：endl;for(i=0;iOleti.xOleti.yOleti.h;outlet door4;/定义门的四个角的坐标 cout请输入门的四个角的坐标endl;for(i=1;idoori.xdoori.ydoori.h;x=Dplace(door);/门所在墙的编号for(i=0;iN;i+)/输入各节点的信息pp.vexsi.no=i;/节点编号=Oplace(Oleti,HX,HY);/节点信息的存入(插座编号从1开始的)pp.n=N;pp.e=N*N;for(i=0;iN;i+)/存入各插座两两间的长度（两两相比较）c=Oleti;/暂存插座ik=;/暂存此节点信息（即对应插座所处墙壁）for(j=i+1;jN;j+)d=Oletj;/暂存插座jl=;if(pp.vexsi.no=pp.vexsj.no)/若是同一节点，间距为0pp.edgesij=0;else/如果是不同节点分为以下三种情况if(Xplace(k,l)=0)/如果两插座在同一个墙壁上if(x!=k)/如果门不在这个墙壁上m=fabs(Oleti.x-Oletj.x)+fabs(Oleti.y-Oletj.y)+fabs(Oleti.h-Oletj.h);pp.edgesij=m;pp.edgesji=m;else/若门在这个墙壁上m=CC(c,d,door,x);pp.edgesij=m;pp.edgesji=m;if(Xplace(k,l)=1)/如果两插座在相邻的两个墙壁上if(x!=k&x!=l)/如果门不在两插座所在的墙壁上m=fabs(Oleti.x-Oletj.x)+fabs(Oleti.y-Oletj.y)+fabs(Oleti.h-Oletj.h);pp.edgesij=m;pp.edgesji=m;elsem=CC(c,d,door,x);pp.edgesij=m;pp.edgesji=m;if(Xplace(k,l)=2)/若两插座在对立的墙面上m=fabs(Olet