1、11问题描述:1.实验题目:需要在某个城市 n 个居民小区之间铺设煤气管道,则在这 n 个居民小区之间只需要铺设 n-1 条管道即可。假设任意两个小区之间都可以铺设管道,但由于地理环境不同,所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小,这个问题即为求无向网的最小生成树。2.基本要求:在可能假设的 m 条管道中,选取 n-1 条管道,使得既能连通 n 个小区,又能使总投资最小。每条管道的费用以网中该边的权值形式给出,网的存储采用邻接表的结构。3.测试数据:使用下图给出的无线网数据作为程序的输入,求出最佳铺设方案。右侧是给出的参考解。4.简述每一部分的对象、目的和要求:I.主函数部分:
2、对象:图 G;目的:为图 G 分配空间,以作为后续调用函数的参数;2要求:无。II. Create_ALGraph( )函数部分:对象:顶点,边及其权值;目的:将顶点,边存放在一起,构成图;要求:构造顶点表,各顶点的邻接表以构造图。III. Create_WLGraph( )函数部分:对象:图 G;目的:将图中的权值只存放一次,存放到 w 指向的结构体中;要求:权值只存放一次,再分别存放该边的左右顶点。IV. select_info( )函数部分:对象:w 指向的结构体;目的:将该结构体中的各权值以升序排列;要求:采用简单选择法进行排序。V. Create_TLGraph( )函数部分:对象:
3、排序后的 w 指向的结构体;目的:找到构成最小生成树的边;要求:依权值升序排列,判断各边是否构成回路来取舍各边。2需求分析1.程序所能达到的基本可能:在 n 个小区 m 条管道中,选取 n-1 条管道,实现连通这 n 个小区,同时权值之和为最小。2.输入输出形式及输入值范围:程序运行后,用户可根据提示信息:“Please input the vertices and the edges:“输入顶点数和边数,再根据提示信息: “Please input the information of the vertices:“输入顶点信息,然后进入循环,创建各个顶点的邻接表,即根据提示信息“Please
4、 input the information of edges:“和“Please input the information of weight:“依次输入各顶点与其他顶点本身以及两者之间的权值,创建图完毕。用户输入完毕后,程序自动输出运行结果。输入值必须为字母和浮点数,可以不必区分大小写。3.测试数据要求:3用户输入字母时,输入大写或小写,都可以被该程序识别,正常运行。但必须根据提示信息后面给出的参考形式,有针对性地输入逗号。3概要设计为了实现上述功能,该程序以邻接表来存储图,因此需要图这个抽象数据类型。1. 图抽象数据类型定义:ADT ALGraph数据对象:D= ii bAdjLst,
5、|,aicbintt,c,i=1,2,3.,n,n 0数据关系:R= ;基本操作:Create_ALGraph(G);/ 创建图Create_WLGraph(G); /将图 G 中各顶点以及权值存放到新图中,权值只存放一次select_info(W, G);/将新图 W 中的权值按升序排列Create_TLGraph(w, G); /将最小生成树以顶点对 (i, j)的形式输出ADT ALGraph2.本程序保护模块:主函数模块图模块调用关系:主函数模块 图模块3.主要算法流程图:4Create_ALGraph( )算法流程图: Create_WLGraph()算法流程图:5开 始读 入 顶
6、点数 和 边 数i=0i的 对 应 顶 点 及权 值将 新 边 表 结 点插 入 到 顶 点 Vi的 边 表 头 部k=k+1结 束TFFT开 始i=0inextTFTFTFCreate_TLGraph( )算法流程图:6开始初始化存储各顶点被访问情况及位置信息的结构体指针 v pi = 1调用j u d g e _ v e r t e x () 函数若两顶点都已被访问过若两顶点位置不同将该权值加入 T中 , 并把位置改相同若左顶点未被访问 , 右顶点已被访问若左顶点已被访问 , 右顶点未被访问若两顶点都未被访问将该权值加入 T中 , 并把左顶点的位置改为和右顶点相同将该权值加入 T中 , 并
7、把右顶点的位置改为和左顶点相同将该权值加入 T中 , 并把两顶点的位置改为相同i = i + 1i #include#define MaxVerNum 1002.元素类型、结点类型和结点指针类型:static void forcefloat(float *p)float f = *p;forcefloat(typedef struct node int adjvex;float info;struct node *next;EdgeNode;typedef struct vnode char vertex;EdgeNode *firstedge;VertexNode;typedef Verte
8、xNode AdjListMaxVerNum;struct bianint z,y;float info;typedef structchar vMaxVerNum;struct bian eMaxVerNum;WGraph;struct visit8visitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;3.邻接表类型:typedef structAdjList adjlist;int n,e;ALGraph;/部分基本操作的伪码实现Create_ALGraph(ALGraph *G)int i,j; char p,q;int k;
9、 /* int x=0; */EdgeNode *s;char a,b;printf(“Please input the vertices and the edges:n“);scanf(“%d,%d“,printf(“Please input the information of the vertices:n“);getchar();for(i=0;in);i+)scanf(“%c“,G-adjlisti.firstedge=NULL;/*if(G-adjlisti.vertex!= */for(k=0;ke);k+)printf(“Please input the information
10、of edges:n“);getchar();scanf(“%c,%c“,9s=(EdgeNode *)malloc(sizeof(EdgeNode);s-adjvex=q-64;i=p-64;getchar();printf(“Please input the information of weight:n“);scanf(“%f“,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(
11、“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+1return 0;void select_info(WGraph *W,ALGraph *G)int i,j,p
12、,k;10float 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=-1else if(vp-visitedw-ei.z-1=-1else if(vp-visitedw-ei.y-1=-1else if(vp-visitedw-ei.z-1=1&vp-visitedw-ei.y-1=1)