管道铺设施工的最佳方案问题Word格式.docx

1、Please input the information of the vertices输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息Please input the information of edges和Please input the information of weight:依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。3.测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。三概要设计为

2、了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。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（ ）

3、算法流程图： Create_WLGraph（）算法流程图： Create_TLGraph（ ）算法流程图：四详细设计1.相关头文件的调用说明：#includestdlib.h#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

4、 *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;struct bianint z,y;typedef structchar vMaxVerNum; struct bian eMaxVerNum;WGraph;struct visitvisitedMaxVerNum; positionMaxVerNum; vvppMaxVerNumMaxVerNum;3.邻接表类型： AdjList adjlist; int n,e; ALGraph;/部分基本操作的伪码实现Create_ALGraph（ALGraph *G）int i,j;

5、 char p,q; int k; /* int x=0; */ EdgeNode *s; char a,b; printf（n）; scanf（%d,%d,&（G-n）,&e）; getchar（）; for（i=0;iadjlisti.firstedge=NULL; /*if（G-adjlisti.vertex!= &G-n） x+;*/ for（k=0;ke）;k+） printf（%c,%cp,&q）; s=（EdgeNode *）malloc（sizeof（EdgeNode）; s-adjvex=q-64; i=p-64;%f（s-info）;next=G-adjlisti-1.fi

6、rstedge;adjlisti-1.firstedge=s; /*Please output the information:%d,%dn,G-n,G-x=%dn,x）;n;%cnadjlisti.vertex）; s=G-adjlisti.firstedge; while（s!=NULL）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

7、=s-adjvex） return 1; return 0;void select_info（WGraph *W,ALGraph *G） int i,j,p,k; float t; p=i; for（j=i+1;jej.infoep.info） p=j; if（p!=i） t=W-ep.info; W-ep.info=W-ei.info;ei.info=t; k=W-ep.z;ep.z=W-ei.z;ei.z=k;ep.y;ep.y=W-ei.y;ei.y=k; for （i=0;%.1f ,W-ei.info）;int judge_vertex（WGraph *w,int i,struct

8、visit *vp） if（vp-visitedw-ei.z-1=-1&vp-ei.y-1=-1）return 1;else if（vp-ei.y-1=1）return 2;ei.y-1=-1&ei.z-1=1）return 3;ei.z-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）; vp-visitedi

9、=-1; vp-positioni=-1;vvppi0=i+1; for（j=1;vvppij=0; T.v0=w-vw-e0.z-1; T.v1=w-e0.y-1;e0.z-1=1;positionw-e0.z-1=w-e0.z; for（j=0; if（vp-vvppw-e0.z-1j=0）e0.z-1j=w-e0.y; break;e0.y-1=1;e0.y-1=w- T.e0.info=w-e0.info; T.e0.z=w- T.e0.y=w- for（i=1; t=judge_vertex（w,i,vp）; if（t=4） if（vp-ei.z-1=vp-ei.y-1） conti

10、nue; else abc=0; bcd=0; for（j=0; if（vp-vvppvp-ei.y-1-1j!=0） abc+; for（j=0; if（vp-ei.z-1-1j! bcd+; for（j=bcd,h=0;n&hvvpp（vp-ei.z-1）-1j=vp-ei.y-1）-1h;ei.y-1-1h=0; for（h=bcd;abc+bcd;h+） vp-position（vp-ei.z-1-1h）-1=vp-ei.z-1; T.em.info=w- T.em.z=w- T.em.y=w- m+; else if（t=1） vp-ei.z-1=1;ei.y-1=1; T.vk+=

11、w-ei.y-1; T.em.info=w-ei.z-1=w-ei.y-1=w-ei.z-11=w-ei.y-10=0; else if（t=2）ei.z-1=vp-ei.y-1-1j=0）ei.y-1-1j=w-ei.z-10=0; else if（t=3）ei.y-1=vp-ei.z-1-1j=0）ei.z-1-1j=w-printf（for（i=0;n）-1;（%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 *

12、）malloc（sizeof（WGraph）;v0=G-adjlist0.vertex;adjlist0.firstedge; W-ek.z=1;ek.y=s-adjvex;ek.info=s-info; k+;vi=G-adjlisti.vertex; m=Panduan_Vertex（k,i,W,s）; if（m=1） s=s- else W-ek.z=i+1;vi）;e;%d,%d,%.1fnei.z,W-ei.y,W- select_info（W,G）; Create_TLGraph（W,G）;4.主函数的伪码：main（）ALGraph *G; G=（ALGraph *）malloc

13、（sizeof（ALGraph）; Create_ALGraph（G）; Create_WLGraph（G）;5.函数调用关系：五调试分析1.出现问题及解决方法：在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路的算法中遇到很大困难，后来采用以下方法解决了这个问题：将每个顶点分别放在一个结构体中，结构体中的数组visitedi记录顶点Vi是否被访问过的情况，positioni记录顶点Vi的具体位置，二维数组vvppij记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。其具体思想是：只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个

14、权值加入T中，先检验该权值的两顶点是否在同一个二维数组中。若不在，则将该权值存入T中；若在，将该权值舍去（因为再将该权值加入T中，就会出现回路）。2.方法优缺点分析：优点：思想比较简单，容易令人理解；在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。缺点：由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系理清需要足够的耐心和细心。3主要算法的时间和空间复杂度分析：（1）由于Create_ALGraph（ ）算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故

15、其时间复杂度为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”，“ABCDEFGH

16、I”，“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”，

17、“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） 运行结果截屏：八附录源程序清单： /*调用的头文件库说明*/ /*由于我的TC中不支持浮点数，故添加了这个程序段*/typedef struct node /*构造邻接表的结构体*/ /*存放权值*/ /*指向下一个邻接点的指针域*/typedef struct vnode /*构造顶点表的结构体*/ /*顶点域*/ /*边表头指针*/typedef struct /*构造图的结构体*/ /*邻接表*/ /*顶点数和边数*/struct bian /*存放权值及其左右顶点的结构体*/typedef struct /*用该结构体来只存放一次权值及其相应的顶点*/char vMaxVerNu