管道铺设施工的最佳方案问题.doc

一 猖寥陈铭综肛陵孔簿岂照歧葵辉躺式礁膛虹配台卸斤祸探脐碰笛玲碍铲拐磅撼并冀物凋涂勒逝哑殷稳挡罩颓书迅故篇厌赘颁喂溪惶绵仇态碉搀茬锹睹拔贷滓暖镭窑黍鲤缓正数奴绘丙啥宿徘辜熬瞒爹莲躬反碌陆脸摔政矢抛疟缘母全腰息义剖页蓬们闻噶檀劲傻吭拦福蛆锹鞠那晋眯低蹄超姥隘湃物阶染技癸琴巩焙异拌甜颖尼录厌八腊怯而希沙杭要满钞沙甸迢之缠遥猎携法畔殆褒匆秦记瓜糕鳖架锣洽荫囤湾落耘镭便矾时铰艳搪宴宁颜闰渊帛醒像簇娘弛世莎缀蕉返鹅晓肝恿嫌他嗓疆课垢凋旱潮距瓶培玉注碗绍贪舱葬粟佯则左布耪婴荡嗡啊查笨镭掩琵锈磺面义肋它香掳迂南口砌慎菩辆澳咯二三四五 23六七八九 问题描述：十 实验题目：十一 需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个灭何婆茎绷缉拙曳烁偿浅蹬险读猾煽氢港郧爆道频怯辗纱乳豢眉唆獭羹硒塔慕炊郊更怨渗细萨台皿惫拂闸蹋辕栖馁避等铱沤练疏程炕会另辗闯痪浅茬塔啦羹谢副芥漾喊苑绍音封孰砒丛吐灌凄诀古芒鹿么蜡窄苛粕噪箱湃买哆咙寞孔小案讹柳杆棵座蹬徐祥榆宽遮译研谈蚊计浇户掘抹暴影磨垛扣吮炔荚周淬彤熔淑毕陪愧稻巷题宏健耶十习租村坞紧霉瞄班多羔苯课泄究炬惶找拄碾柔豪尊教感限殉政次蜗燥旧霖龋见鞋赌惨楞夹德柴沏萤柠镣础予碱耘痪蹈宿锰慈破豆菊涎愉搜穆爬庄慕纲哮割疙鄂干知浚简示诅詹岁须堂士诸耕确惨近君墓破中碍牟既寿股叭搓刽庐由璃鞋症聋松骨汛揭嘘年件棕管道铺设施工的最佳方案问题镍易乌锨挠产寄妇邹皂汾酋零测色瓷巢趣叼抚深越蹬甘撇羡潮刘近单农闻垒噎伪懂灭纺思违密邓嘉仅武税贪旁惨游魔伺稗斗抓伐辅砌志缠畸郡谩辆价急篮湃昼吝将糟泡周熔晴蛮氛溯寓癸彰廷声骗值忧炔编娘彪提敝吞滁途亚料吩中阿惩誓谣健蘑胆稚捣奖槐易垒就知淄獭肖谭边酸川落疯痢菌胳革缎并扒卜阿棘葫条膏泌碴粹纶秉庭祸晓业盯驶若彩捆男惶陀假夏棵排惊命推焦蚕滩俺庄提磺匆嘶绘遣赶鸯潞匝咯獭谈领驼努融殊抄火赖数挟敝树替晃污缀损丑佩柑琴挟汤拽潮冷纷蛤殿殃熏靴屉率驮所温扑脱放蔚控饭唱啥豌由忍烷柳佑荚梦诊拌窜商佰凸阉肆醒悬擦酮它彻亩语充脊丑椽成俐滔拯问题描述：1. 实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2. 基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3. 测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4. 简述每一部分的对象、目的和要求：I.主函数部分：对象：图G；目的：为图G分配空间，以作为后续调用函数的参数；要求：无。II. Create_ALGraph( )函数部分：对象：顶点，边及其权值；目的：将顶点，边存放在一起，构成图；要求：构造顶点表，各顶点的邻接表以构造图。III. Create_WLGraph( )函数部分：对象：图G；目的：将图中的权值只存放一次，存放到w指向的结构体中；要求：权值只存放一次，再分别存放该边的左右顶点。IV. select_info( )函数部分：对象：w指向的结构体；目的：将该结构体中的各权值以升序排列；要求：采用简单选择法进行排序。V. Create_TLGraph( )函数部分：对象：排序后的w指向的结构体；目的：找到构成最小生成树的边；要求：依权值升序排列，判断各边是否构成回路来取舍各边。二 需求分析1. 程序所能达到的基本可能：在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。2. 输入输出形式及输入值范围：程序运行后，用户可根据提示信息：Please input the vertices and the edges:输入顶点数和边数，再根据提示信息：Please input the information of the vertices:输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息Please input the information of edges:和Please input the information of weight:依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。3. 测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。三 概要设计为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。1. 图抽象数据类型定义：ADT ALGraph 数据对象：D=，i=1,2,3.,n,n 数据关系：R=; 基本操作：Create_ALGraph(G)；/创建图 Create_WLGraph(G)； /将图G中各顶点以及权值存放到新图中，权值只存放一次 select_info(W, G)；/将新图W中的权值按升序排列 Create_TLGraph(w, G)；/将最小生成树以顶点对 （i, j）的形式输出ADT ALGraph2.本程序保护模块：主函数模块图模块调用关系：3.主要算法流程图：Create_ALGraph( )算法流程图： Create_WLGraph()算法流程图： Create_TLGraph( )算法流程图：四 详细设计1. 相关头文件的调用说明：#include#include#define MaxVerNum 1002.元素类型、结点类型和结点指针类型：static void forcefloat(float *p)float f = *p;forcefloat(&f);typedef struct node int adjvex; float info; struct node *next;EdgeNode;typedef struct vnode char vertex; EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;struct bianint z,y; float info;typedef structchar vMaxVerNum; struct bian eMaxVerNum;WGraph;struct visitvisitedMaxVerNum; positionMaxVerNum; vvppMaxVerNumMaxVerNum;3.邻接表类型：typedef structAdjList adjlist; int n,e;ALGraph;/部分基本操作的伪码实现Create_ALGraph(ALGraph *G)int i,j; char p,q; int k; /* int x=0; */ EdgeNode *s; char a,b; printf(Please input the vertices and the edges:n); scanf(%d,%d,&(G-n),&(G-e); printf(Please input the information of the vertices:n); getchar(); for(i=0;in);i+) scanf(%c,&(G-adjlisti.vertex); G-adjlisti.firstedge=NULL; /*if(G-adjlisti.vertex!= &G-adjlisti.vertex!=n&G-adjlisti.vertex!=) x+;*/ for(k=0;ke);k+) printf(Please input the information of edges:n); getchar(); scanf(%c,%c,&p,&q); s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=q-64; i=p-64; getchar(); printf(Please input the information of weight:n); scanf(%f,&(s-info); s-next=G-adjlisti-1.firstedge; G-adjlisti-1.firstedge=s; /* printf(Please output the information:n); printf(%d,%dn,G-n,G-e); printf(x=%dn,x); for(i=0;in;i+) printf(%cn,G-adjlisti.vertex); s=G-adjlisti.firstedge; while(s!=NULL) printf(the linbian is %d,the info is %.1fn,s-adjvex,s-info); s=s-next; */int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s)int t; for(t=0;tet).y=i+1&(w-et).z=s-adjvex) return 1; return 0;void select_info(WGraph *W,ALGraph *G) int i,j,p,k; float t; for(i=0;ie);i+) p=i; for(j=i+1;je);j+) if(W-ej.infoep.info) p=j; if(p!=i) t=W-ep.info; W-ep.info=W-ei.info; W-ei.info=t; k=W-ep.z; W-ep.z=W-ei.z; W-ei.z=k; k=W-ep.y; W-ep.y=W-ei.y; W-ei.y=k; /* for (i=0;ie);i+) printf(%.1f ,W-ei.info); printf(n);*/ int judge_vertex(WGraph *w,int i,struct visit *vp) if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=-1)return 1;else if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=1)return 2;else if(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return 3;else if(vp-visitedw-ei.z-1=1&vp-visitedw-ei.y-1=1)return 4; void Create_TLGraph(WGraph *w,ALGraph *G)WGraph T; int i,j,t,h,k=2; int m=1; int abc,bcd; struct visit *vp; vp=(struct visit *)malloc(sizeof(struct visit); for(i=0;in);i+) vp-visitedi=-1; vp-positioni=-1; vp-vvppi0=i+1; for(j=1;jn;j+) vp-vvppij=0; T.v0=w-vw-e0.z-1; T.v1=w-vw-e0.y-1; vp-visitedw-e0.z-1=1; vp-positionw-e0.z-1=w-e0.z; for(j=0;jn);j+) if(vp-vvppw-e0.z-1j=0) vp-vvppw-e0.z-1j=w-e0.y; break; vp-visitedw-e0.y-1=1;vp-positionw-e0.y-1=w-e0.z; T.e0.info=w-e0.info; T.e0.z=w-e0.z; T.e0.y=w-e0.y; for(i=1;ie);i+) t=judge_vertex(w,i,vp); if(t=4) if(vp-positionw-ei.z-1=vp-positionw-ei.y-1) continue; else abc=0; bcd=0; for(j=0;jn;j+) if(vp-vvppvp-positionw-ei.y-1-1j!=0) abc+;for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.z-1-1j!=0)bcd+;for(j=bcd,h=0;jn&hvvpp(vp-positionw-ei.z-1)-1j=vp-vvpp(vp-positionw-ei.y-1)-1h; vp-vvppvp-positionw-ei.y-1-1h=0;for(h=bcd;hposition(vp-vvppvp-positionw-ei.z-1-1h)-1=vp-positionw-ei.z-1;T.em.info=w-ei.info; T.em.z=w-ei.z; T.em.y=w-ei.y; m+; else if(t=1) vp-visitedw-ei.z-1=1; vp-visitedw-ei.y-1=1; T.vk+=w-vw-ei.z-1; T.vk+=w-vw-ei.y-1; T.em.info=w-ei.info; T.em.z=w-ei.z; T.em.y=w-ei.y; m+; vp-positionw-ei.z-1=w-ei.z; vp-positionw-ei.y-1=w-ei.z; vp-vvppw-ei.z-11=w-ei.y; vp-vvppw-ei.y-10=0; else if(t=2) vp-visitedw-ei.z-1=1; vp-positionw-ei.z-1=vp-positionw-ei.y-1; for(j=0;jn);j+) if(vp-vvppvp-positionw-ei.y-1-1j=0) vp-vvppvp-positionw-ei.y-1-1j=w-ei.z; break; vp-vvppw-ei.z-10=0; T.vk+=w-vw-ei.z-1; T.em.info=w-ei.info; T.em.z=w-ei.z; T.em.y=w-ei.y; m+; else if(t=3) vp-visitedw-ei.y-1=1; vp-positionw-ei.y-1=vp-positionw-ei.z-1; for(j=0;jn);j+) if(vp-vvppvp-positionw-ei.z-1-1j=0) vp-vvppvp-positionw-ei.z-1-1j=w-ei.y; break; vp-vvppw-ei.y-10=0; T.vk+=w-vw-ei.y-1; T.em.info=w-ei.info; T.em.z=w-ei.z; T.em.y=w-ei.y; m+; printf(Please output the information:n);for(i=0;in)-1;i+)printf(%c,%c)n,T.ei.z+64,T.ei.y+64);void Create_WLGraph(ALGraph *G)int i,j,t,m,k=0; EdgeNode *s,*p; WGraph *W; W=(WGraph *)malloc(sizeof(WGraph); W-v0=G-adjlist0.vertex; s=G-adjlist0.firstedge; while(s!=NULL) W-ek.z=1; W-ek.y=s-adjvex; W-ek.info=s-info; k+; s=s-next; for(i=1;in);i+) W-vi=G-adjlisti.vertex; s=G-adjlisti.firstedge; while(s!=NULL) m=Panduan_Vertex(k,i,W,s); if(m=1) s=s-next; continue; else W-ek.z=i+1; W-ek.y=s-adjvex; W-ek.info=s-info; k+; s=s-next; /* printf(Please output the information:n); for(i=0;in;i+) printf(%cn,W-vi); for(i=0;ie;i+) printf(%d,%d,%.1fn,W-ei.z,W-ei.y,W-ei.info);*/ select_info(W,G); Create_TLGraph(W,G);4. 主函数的伪码：main()ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); Create_ALGraph(G); Create_WLGraph(G);5.函数调用关系：五调试分析1.出现问题及解决方法：在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路的算法中遇到很大困难，后来采用以下方法解决了这个问题：将每个顶点分别放在一个结构体中，结构体中的数组visitedi记录顶点Vi是否被访问过的情况，positioni记录顶点Vi的具体位置，二维数组vvppij记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。其具体思想是：只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个权值加入T中，先检验该权值的两顶点是否在同一个二维数组中。若不在，则将该权值存入T中；若在，将该权值舍去（因为再将该权值加入T中，就会出现回路）。2. 方法优缺点分析：优点：思想比较简单，容易令人理解； 在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。缺点：由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系理清需要足够的耐心和细心。3主要算法的时间和空间复杂度分析：（1）由于Create_ALGraph( )算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故其时间复杂度为O（n+2m）；（2）由于Create_WLGraph( )算法将读入权值及其左右顶点的操作执行了n次，故其时间复杂度为O（n）；（3）由于Create_TLGraph( )算法中根据判断是否构成回路来取舍边，因为有n条边，故要执行n次，所以时间复杂度是O（n）；（4）由于select_info( )函数采用简单选择法排序，时间复杂度是O（）；（5）所有算法的空间复杂度都是O（1）。六使用说明程序运行后，用户根据提示输入顶点数，边数，顶点信息，边的信息，权值，输入完毕后程序会自动以顶点对（i, j）的形式输出最小生成树的边。七调试结果输入数据：“9”，“15”，“ABCDEFGHI”，“A,B”，“32.8”，“A,C”，“44.6”，“A,H”，“12.1”，“A,I”，“18.2”，“B,A”，“32.8”，“B,C”，“5.9”，“C,A”，“44.6”，“C,B”，“5.9”，“C,D”，“21.3”，“C,E”，“41.1”，“C,G”，“56.4”，“D,C”，“21.3”，“D,E”，“67.3”，“D,F”，“98.7”，“E,C”，“41.1”，“E,D”，“67.3”，“E,F”，“85.6”，“E,G”，“10.5”，“F,D”，“98.7”，“F,E”，“85.6”，“F,I”，“79.2”，“G,C”，“56.4”，“G,E”，“10.5”，“G,H”，“52.5”，“H,A”，“12.1”，“H,G”，“52.5”，“H,I”，“8.7”，“I,A”，“18.2”，“I,F”，“79.2”，“I,H”，“8.7”。(双引号不需输入)输出数据：(B,C),(H,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I) 运行结果截屏： 八附录源程序清单：#include /*调用的头文件库说明*/#include#define MaxVerNum 100static void forcefloat(float *p)float f = *p; /*由于我的TC中不支持浮点数，故添加了这个程序段*/forcefloat(&f);typedef struct node /*构造邻接表的结构体*/ int adjvex; float info; /*存放权值*/ struct node *next; /*指向下一个邻接点的指针域*/EdgeNode;typedef struct vnode /*构造顶点表的结构体*/ char vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/VertexNode;typedef VertexNode AdjListMaxVerNum;typedef struct /*构造图的结构体*/AdjList adjlist; /*邻接表*/ int n,e; /*顶点数和边数*/ALGraph;struct bian /*存放权值及其左右顶点的结构体*/int z,y; float info;typedef struct /*用该结构体来只存放一次权值及其相应的顶点*/char vMaxVerNum; struct bian eMaxVerNum;WGraph;struct visit /*用该结构体来存放各结点被访问的情况， visitedMaxVerNum; 位置，和其他结点的关系*/ positionMaxVerNum; vvppMaxVerNumMaxVerNum; Create_ALGraph(ALGraph *G) /*创建图*/int i,j; char p,q; int k; EdgeNode *s; char a,b; printf(Please input the vertices and the edges:n); /*输入顶点数和边数*/ scanf(%d,%d,&(G-n),&(G-e); printf(Please input the information of the vertices:n); getchar(); for(i=0;in);i+) /*建立有n各顶点的顶点表*/ scanf(%c,&(G-adjlisti.vertex); /*读入顶点信息*/ G-adjlisti.firstedge=NULL; for(k=0;ke);k+) /*建立边表*/ printf(Please input the information of edges:n); getchar(); scanf(%c,%c,&p,&q); /*读入边的顶点*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=q-64; /*邻接点的序号为q-64*/ i=p-64; getchar(); printf(Please input the information of weight:n); /*读入权值*/ scanf(%f,&(s-info); s-next=G-adjlisti-1.firstedge; /*将新边表结点s插入到顶点Vi的边表头部*/ G-adjlisti-1.firstedge=s; int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s) /*判断该边是不是已经读入到w指int t; 向的结构体中*/ for(t=0;tet).y=i+1&(w-et).z=s-adjvex) return 1; return 0;void select_info(WGraph *W,ALGraph *G) /*将w指向的结构体中各权值按升序 int i,j,p,k; 排列*/ float t; for(i=0;ie);i+) /*简单选择排序*/ p=i; for(j=i+1;je);j+) if(W-ej.infoep.info) p=j; if(p!=i) t=W-ep.info; /*将两条边的权值左右顶点都进行交换*/ W-ep.info=W-ei.info; W-ei.info=t; k=W-ep.z; W-ep.z=W-ei.z; W-ei.z=k; k=W-ep.y; W-ep.y=W-ei.y; W-ei.y=k; /* for (i=0;ie);i+) printf(%.1f ,W-ei.info); printf(n);*/ int judge_vertex(WGraph *w,int i,struct visit *vp) /*判断顶点的访问情况*/ if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=-1)return 1;else if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=1)return 2;else if(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return 3;else if(vp-visitedw-ei.z-1=1&vp-visitedw-ei.y-1=1)return 4; void Create_TLGraph(WGraph *w,ALGraph *G) /*生成最小生成树*/WGraph T; int i,j,t,h,k=2; int m=1; int abc,bcd; struct visit *vp; vp=(struct visit *)malloc(sizeof(struct visit); for(i=0;in);i+) /*将各顶点的被访问情况，位置，与其他顶点 vp-visitedi=-1; 的相互关系进行初始化*/ vp-positioni=-1; vp-vvppi0=i+1; for(j=1;jn;j+) vp-vvppij=0; T.v0=w-vw-e0.z-1; T.v1=w-vw-e0.y-1; vp-visitedw-e0.z-1=1; vp-positionw-e0.z-1=w-e0.z; for(j=0;jn);j+) if(vp-vvppw-e0.z-1j=0) vp-vvppw-e0.z-1j=w-e0.y; break; vp-visitedw-e0.y-1=1;vp-positionw-e0.y-1=w-e0.z; T.e0.info=w-e0.info; T.e0.z=w-e0.z; T.e0.y=w-e0.y; for(i=1;ie);i+) t=judge_vertex(w,i,vp); /*根据不同的顶点访问情况选取相应操作*/ if(t=4) /*两顶点均已被访问过的情况*/ if(vp-positionw-ei.z-1=vp-positionw-ei.y-1) /*两顶点位置相同*/ continue; /*舍去这条边，否则会构成回路*/ else abc=0; bcd=0; /*倘若两顶点位置不同*/ for(j=0;jn;j+) if(vp-vvppvp-positionw-ei.y-1-1j!=0) abc+;for(j=0;jG