室内布线数据结构课程设计.doc

1、数据结构课程设计报告书题目：室内布线姓名： 性别： 男 班级： 计091-2 学号：200925501213日期： 2010.7.7 课程设计内容：装修房子是一项颇为复杂的工程，现在需要写一个程序帮助房主设计室内电线的布局。 首先，墙壁上插座的位置是固定的。插座间需要有电线相连，而且要布置得整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。 房主想要知道，要将所有插座连通，自己需要买的电线最短长度是多少（取整数）提示：1、每个房间都有门，电线不可以穿门而过。图中给出一个有4个插座的房间的电线布局。2、输出时应注意，题目要求取整数，但不能四舍五入，必须向上取整，因为电

2、线短一点就不能保证连通。算法设计：#include #define MAX 20#define MAXSIZE 1000using namespace std;float H_LENGH,H_WIDTH,H_HIGH;int y;/定义房子的长宽高和插座的个数为全局变量typedef structfloat X,Y,Z;Point;typedef struct /用四个点定义门的位置Point DoorPlace4;int DP;/用来标记门在房间位置float D_HIGH;Door;typedef struct /定义插座的个数和位置Point SocketPlaceMAX;int Soc

3、ketNum,SD;HOutlet;typedef struct int row,col,mark;float e;Triple;typedef structTriple dataMAXSIZE;int m,n,len;TSMatrix;int P2W(Point p)/通过插座的位置求出插座在哪一面墙上int num;if (p.X=0&p.Y=0&p.Z=0)num=1;else if (p.X=H_LENGH&p.Y=0&p.Z=0)num=2;else if (p.X=0&p.Y=H_WIDTH&p.Z=0)num=3;else if (p.X=0&p.Y=0&p.Z=0)num=4;

4、return num;float max(float a,float b)/求两个数的最大值float tem;if (ab)tem=a;else tem=b;return tem;float max(float a,float b,float c)/求三个数的最小值float tem;tem=max(a,b);tem=max(tem,c);return tem;float max(float a,float b,float c,float d)/求四个数的最大值float tem;tem=max(a,b);tem=max(tem,c);tem=max(tem,d);return tem;fl

5、oat min(float a,float b)/求两个数的最小值float tem;if (ab)tem=a;else tem=b;return tem;float min(float a,float b,float c)/求三个数的最小值float tem;tem=min(a,b);tem=min(tem,c);return tem;float min(float a,float b,float c,float d)/求四个数的最小值float tem;tem=min(a,b);tem=min(tem,c);tem=min(tem,d);return tem;float JDZ(float

6、 X,float Y)/求两个数相减的绝对值float tem;tem=X-Y;if (tem0)tem=-tem;return tem;float CalDis(Point &p1,Point &p2,Door &D)/求两个插座之间的最短距离float distance=0,distance1=0,distance2=0,distance3=0,DL,DR,SL,SR;int Num1,Num2;DL=min(D.DoorPlace0.X,D.DoorPlace1.X,D.DoorPlace2.X,D.DoorPlace3.X);DR=max(D.DoorPlace0.X,D.DoorPl

7、ace1.X,D.DoorPlace2.X,D.DoorPlace3.X);SL=min(p1.X,p2.X);SR=max(p1.X,p2.X);Num1=P2W(p1);Num2=P2W(p2);if (JDZ(Num1,Num2)=0)/此情况为两个插座在同一面墙上if(Num2!=D.DP)/插座不在有门的那面墙上distance=JDZ(p1.X,p2.X)+JDZ(p1.Y,p2.Y)+JDZ(p1.Z,p2.Z);else if (DL=0&SL=DR)/插座在门那面墙上distance=JDZ(p1.X,p2.X)+JDZ(p1.Y,p2.Y)+JDZ(p1.Z,D.D_HIG

8、H)+JDZ(p1.Z,D.D_HIGH);else if (DR=H_LENGH&SLDL)distance=JDZ(p1.X,p2.X)+JDZ(p1.Y,p2.Y)+JDZ(p1.Z,D.D_HIGH)+JDZ(p1.Z,D.D_HIGH);else if (SLDR)distance=JDZ(p1.X,p2.X)+JDZ(p1.Y,p2.Y)+JDZ(p1.Z,D.D_HIGH)+JDZ(p1.Z,D.D_HIGH);elsedistance=JDZ(p1.X,p2.X)+JDZ(p1.Y,p2.Y)+JDZ(p1.Z,p2.Z);else if(JDZ(Num1,Num2)=1)/插

9、座在相邻的两面墙上if (Num1=1)distance=H_LENGH-p1.X+p2.Y+JDZ(p1.Z,p2.Z);else if (Num1=2)distance=H_WIDTH-p1.Y+H_LENGH-p2.X+JDZ(p1.Z,p2.Z);elsedistance=H_WIDTH-p1.Y+p2.X+JDZ(p1.Z,p2.Z);else if(JDZ(Num1,Num2)=2)/插座在相对的面上if (Num1=1)distance1=p1.Z+p2.Z+H_WIDTH;distance2=p1.X+p2.X+H_WIDTH;distance3=(H_LENGH+H_WIDT

10、H)*2-distance2;distance=min(distance1,distance2,distance3);if (Num1=2)distance1=H_LENGH+p1.Z+p2.Z;distance2=H_LENGH+p1.Y+p2.Y;distance3=2*(H_LENGH+H_WIDTH)-distance2;distance=min(distance1,distance2,distance3);elsedistance=p1.X+p2.Y+JDZ(p1.Z,p2.Z);return distance;int Caledge(int n)/计算N个插座最多共有多少条线连接i

11、nt sum=0;for (int i=0;in;i+)sum=i+sum;return sum;Door InItDoorplace(Door &D)/初始化门的位置cout请输入门的四个顶点的坐标:;float x,y,z;for (int i=0;ixyz;if(x=0&x=0&z=0&y=0&z=0)D.DP=1;D.DoorPlacei.X=x;D.DoorPlacei.Y=y;D.DoorPlacei.Z=z;else if (x=H_LENGH&y!=0&z!=0)D.DP=2;D.DoorPlacei.X=x;D.DoorPlacei.Y=y;D.DoorPlacei.Z=z;

12、else if (x!=0&y=H_WIDTH&z!=0)D.DP=3;D.DoorPlacei.X=x;D.DoorPlacei.Y=y;D.DoorPlacei.Z=z;else if (x=0&y!=0&z!=0)D.DP=4;D.DoorPlacei.X=x;D.DoorPlacei.Y=y;D.DoorPlacei.Z=z;elsecout你输入的位置有误!;exit(0);else cout你输入的位置有误endl;exit(0);D.D_HIGH=max(D.DoorPlace0.Z,D.DoorPlace1.Z,D.DoorPlace2.Z,D.DoorPlace3.Z);re

13、turn D;HOutlet InitSocketPlace(HOutlet &House,int n=0)/对插座的位置进行初始化cout请对插座的位置进行初始化:;int i;float x,y,z;House.SocketNum=0;for (i=0;ixyz;if(x=0&x=0&y=0&z0&y=0&z0)House.SD=1;House.SocketPlacei.X=x;House.SocketPlacei.Y=y;House.SocketPlacei.Z=z;House.SocketNum+;else if (x=H_LENGH&y00&z0)House.SD=2;House.S

14、ocketPlacei.X=x;House.SocketPlacei.Y=y;House.SocketPlacei.Z=z;House.SocketNum+;else if (x0&y=H_WIDTH&z0)House.SD=3;House.SocketPlacei.X=x;House.SocketPlacei.Y=y;House.SocketPlacei.Z=z;House.SocketNum+;else if (x=0&y0&z0)House.SD=4;House.SocketPlacei.X=x;House.SocketPlacei.Y=y;House.SocketPlacei.Z=z;

15、House.SocketNum+;elsecout你输入的位置有误!;i-;elsecout你输入的位置有误!endl; i-;return House;TSMatrix CalTSM(TSMatrix &TSM,HOutlet &H,Door &D)int p=0,j,i;for (i=0;iH.SocketNum-1;i+)for (j=i+1;jH.SocketNum;j+)TSM.datap.row=i;TSM.datap.col=j;if (P2W(H.SocketPlacei)P2W(H.SocketPlacej)TSM.datap.e=CalDis(H.SocketPlacei,

16、H.SocketPlacej,D);elseTSM.datap.e=CalDis(H.SocketPlacej,H.SocketPlacei,D);p+;TSM.m=TSM.n=H.SocketNum;TSM.len=p+1;return TSM;TSMatrix TSMSORT(TSMatrix &TSM)/对三元组表按元素从小到大进行排序for (int i=0;iTSM.len-1;i+)for (int j=0;jTSM.dataj+1.e)TSM.dataMAXSIZE-1.e=TSM.dataj.e;TSM.dataMAXSIZE-1.col=TSM.dataj.col;TSM.d

17、ataMAXSIZE-1.row=TSM.dataj.row;TSM.dataj.e=TSM.dataj+1.e;TSM.dataj.col=TSM.dataj+1.col;TSM.dataj.row=TSM.dataj+1.row;TSM.dataj+1.e=TSM.dataMAXSIZE-1.e;TSM.dataj+1.col=TSM.dataMAXSIZE-1.col;TSM.dataj+1.row=TSM.dataMAXSIZE-1.row;TSM.data0.e=0;TSM.data0.col=0;TSM.data0.row=0;for (int t=0;tTSM.len;t+)co

18、utTSM.datat.row TSM.datat.col TSM.datat.eendl;return TSM;int CalLinMin(TSMatrix &TSM)/求出最少需要多长的电线int j=1,b,c,aMAX,d=0;float LineMIn;b=TSM.dataj.col;c=TSM.dataj.row;for (int i=0;i=TSM.m;i+)ai=0;ab=1;ac=1;LineMIn=TSM.data1.e;for (j=2;jTSM.m;j+)b=TSM.dataj.col;c=TSM.dataj.row;if (ab*ac=0)if (ab+ac!=0)a

19、b=1;ac=1;LineMIn=LineMIn+TSM.dataj.e;elseab=1;LineMIn=LineMIn+TSM.dataj.e;d+;TSM.dataj.mark=d;TSM.dataj.mark=d;return LineMIn;void main()float LineMin,Tem;HOutlet H;Door Dplace;TSMatrix ALGTSM;coutH_LENGHH_WIDTHH_HIGHy;/输入房子的长宽高和插座的个数InItDoorplace(Dplace);/输入门的四个角的位置InitSocketPlace(H,y);/按次序初始化插座的位置

20、CalTSM(ALGTSM,H,Dplace);/通过插座和门的相关信息计算出连接插座用的的线并存入三元组表for (int i=0;iALGTSM.len-1;i+)coutALGTSM.datai.row ALGTSM.datai.col ALGTSM.datai.eendl;TSMSORT(ALGTSM);/将三元组表按照元素从小到大进行排序LineMin=CalLinMin(ALGTSM);cout该房间至少需要LineMin米长的电线!endl;程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果）：1、如果输入插座的位置是在

21、空间（即不在墙面上）或者是在门上提示错误；2、输入的位置超过了房间的大小会提示错误；3、插座的位置如果是在墙角上会提示错误4、最多可在房间内放20个插座，按题目的要求，可以修改（#define MAX 20）主要问题、原因及解决方法：1、当计算每两个插座的之间需要的电线长度时太繁琐，所以我采用了分情况讨论把它分为插座在同一面墙上，在相邻的墙上，在相对立的墙上等等情况。2、判断门的位置时相对比较繁琐，所以我规定了插座只能在X-Z平面内，用户可按照自己门口的具体位置输入各点的坐标。3、最后在求最短距离是出了一点点问题，改进了图的最小生成树的算法后即可课程设计的主要收获：在本次课程设计中，我对前面所有学的算法进行了进一步的了解，加深巩固。同时也遇到了很多问题，我同查阅书籍、到网上搜集资料，与同学讨论研究，基本将所有问题得到了解决。 对今后课程设计的建议：感谢学校、老师给与我们这次本课程设计的机会，通过本次课程设计，加深巩固了本学科的在这学期学习的只是，同时提高了我们的动手动脑能力，培养了我们对本学科的兴趣，学校应该多举行类似的活动以提高我们的动手能力。13