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

《算法与数据结构》课程设计报告书 ? 最小生成树：室内布线 专 业：计算机科学与技术 成 绩： 烟台大学计算机与控制工程学院 四、#includeiostream #includemath.h using namespace std; typedef struct //存放节点数据 { float x; float y; float h; }outlet; typedef struct { int no;//存放节点编号 int info;//存放节点所处墙面 }VertexType; typedef struct { float edges[20][20];//存放邻接矩阵数据 int n,e; VertexType vexs[20];//节点变量 }MGraph; int Dplace(outlet d[4])//根据门四角坐标求门的位置 { if(d[1].x==d[2].xd[1].x==d[3].xd[1].x==d[4].x)//若门四角的横坐标相同 { if(d[1].x==0)//横坐标为0，则门在1号墙壁上 return 1; else return 3;//否则在三号墙壁上 } if(d[1].y==d[2].yd[1].y==d[3].yd[1].y==d[4].y)//若门四角纵坐标相同 { if(d[1].y==0) return 2; else return 4; } } int Oplace(outlet Olet,float a,float b)//插座的位置 { if(Olet.x==0Olet.y=0Olet.h=0) return 1; if(Olet.y==0Olet.x 0Olet.h0) return 2; if(Olet.x==aOlet.y=0Olet.h=0) return 3; if(Olet.y==bOlet.x =0Olet.h=0) return 4; } int Xplace(int a,int b)//判断两插座的相对位置 { if(a==b)//如果两插座在同一面墙上，返回0 return 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))//如果两插座在相邻面墙上，返回1 return 1; else return 2; } float CC(outlet Olet1,outlet Olet2,outlet door[4],int a)//有门存在时两插座之间的距离 { float n; if(a==1||a==3)//当门在第1或3面墙上时 { if(Olet1.h=door[2].hOlet2.h=door[2].h(Olet1.y=door[2].ydoor[3].y=Olet2.y)||(Olet2.y=door[2].ydoor[3].y=Olet1.y)) //若果门处在两插座连线上 { n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+(door[2].h-Olet1.h)+(door[2].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=door[2].hOlet2.h=door[2].h(Olet1.x=door[2].xdoor[3].x=Olet2.x||Olet2.x=door[2].xdoor[3].x=Olet1.x)) //若果门处在两插座连线上 { n=fabs(Olet1.x-Olet2.x)+fabs(Olet1.y-Olet2.y)+(door[2].h-Olet1.h)+(door[2].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 struct