《管道铺设施工的最佳方案问题教材课程》由会员分享，可在线阅读，更多相关《管道铺设施工的最佳方案问题教材课程（23页珍藏版）》请在金锄头文库上搜索。
1、1 问题描述：1. 实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2. 基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3. 测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4. 简述每一部分的对象、目的和要求：I.主函数部分：对象：图G；目的
2、：为图G分配空间，以作为后续调用函数的参数；要求：无。II. Create_ALGraph( )函数部分：对象：顶点，边及其权值；目的：将顶点，边存放在一起，构成图；要求：构造顶点表，各顶点的邻接表以构造图。III. Create_WLGraph( )函数部分：对象：图G；目的：将图中的权值只存放一次，存放到w指向的结构体中；要求：权值只存放一次，再分别存放该边的左右顶点。IV. select_info( )函数部分：对象：w指向的结构体；目的：将该结构体中的各权值以升序排列；要求：采用简单选择法进行排序。V. Create_TLGraph( )函数部分：对象：排序后的w指向的结构体；目的：找
3、到构成最小生成树的边；要求：依权值升序排列，判断各边是否构成回路来取舍各边。2 需求分析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 edg
4、es:和Please input the information of weight:依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。3. 测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。3 概要设计为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。1. 图抽象数据类型定义：ADT ALGraph 数据对象：D=，i=1,2,3.,n,n 数据关系：R=; 基本操作：Create_ALGraph
5、(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( )算法流程图：4 详细设计1. 相关头文件的调用说明：#include#include#define MaxVerNum
6、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 structc
7、har 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 v
8、ertices 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 in
9、put 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 informat
10、ion: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-adj
11、vex) 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+) prin
12、tf(%.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-visited
13、w-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=
