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

《算法与数据结构》课程设计报告书
 
最小生成树:室内布线
专业:计算机科学与技术
成绩:
烟台大学计算机与控制工程学院
四、程序正确性验证(指边界测试数据,即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果):
门不影响两插座路线的测试数据:
两插座在相邻墙面上,门处在两插座连线上,测试数据:
八、程序代码
#include<iostream>
#include<>
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].x&&d[1].x==d[3].x&&d[1].x==d[4].x)//若门四角的横坐标相同
{
if(d[1].x==0)//横坐标为0,则门在1号墙壁上
return 1;
else return 3;//否则在三号墙壁上
}
if(d[1].y==d[2].y&&d[1].y==d[3].y&&d[1].y==d[4].y)//若门四角纵坐标相同
{
if(d[1].y==0)
return 2;
else return 4;
}
}
int Oplace(outlet Olet,float a,float b)//插座的位置
{
if(==0&&>=0&&>=0)
return 1;
if(==0&& >0&&>0)
return 2;
if(==a&&>=0&&>=0)
return 3;
if(==b&& >=0&&>=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;

}
(outlet Olet1,outlet Olet2,outlet door[4],int a)//有门存在时两插座之间的距离
{
float n;
if(a==1||a==3)//当门在第1或3面墙上时
{
if(<=door[2].