管道铺设综合项目施工的最佳专项方案问题.doc

一． 问题描述：
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<n,e>:"输入顶点数和边数，再依照提示信息："Please input the information of the vertices<v>:"输入顶点信息，然后进入循环，创立各个顶点邻接表，即依照提示信息"Please input the information of edges<p,q>:"和"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 ALGraph
2.本程序保护模块：
主函数模块
图模块
调用关系：

3.重要算法流程图：

Create_ALGraph( )算法流程图： Create_WLGraph()算法流程图：

Create_TLGraph( )算法流程图：

四． 详细设计
1. 有关头文献调用阐明：
#include<stdio.h>
#include<stdlib.h>
#define MaxVerNum 100
2.元素类型、结点类型和结点指针类型：
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 AdjList[MaxVerNum];
struct bian
{int z,y;
float info;
};
typedef struct
{char v[MaxVerNum];
struct bian e[MaxVerNum];
}WGraph;
struct visit
{visited[MaxVerNum];
position[MaxVerNum];
vvpp[MaxVerNum][MaxVerNum];
}
3.邻接表类型：
typedef struct
{AdjList 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,e>:\n");
scanf("%d,%d",&(G->n),&(G->e));
printf("Please input the information of the vertices<v>:\n");
getchar();
for(i=0;i<(G->n);i++)
{scanf("%c",&(G->adjlist[i].vertex));
G->adjlist[i].firstedge=NULL;
/*if(G->adjlist[i].vertex!=' '&&G->adjlist[i].vertex!='\n'&&G->adjlist[i].vertex!=' ')
x++;*/
}
for(k=0;k<2*(G->e);k++)
{printf("Please input the information of edges<p,q>:\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->adjlist[i-1].firstedge;
G->adjlist[i-1].firstedge=s;
}/*
printf("Please output the information:\n");
printf("%d,%d\n",G->n,G->e);
printf("x=%d\n",x);
for(i=0;i<G->n;i++)
{printf("%c\n",G->adjlist[i].vertex);
s=G->adjlist[i].firstedge;
while(s!=NULL)
{printf("the linbian is %d,the info is %.1f\n",s->adjvex,s->info);
s=s->next;
}
}*/
}
int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s)
{int t;
for(t=0;t<k;t++)
if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex)
return 1;
return 0;
}
void select_info(WGraph *W,ALGraph *G)
{int i,j,p,k;
float t;
for(i=0;i<(G->e);i++)
{p=i;
for(j=i+1;j<(G->e);j++)
if(W->e[j].info<W->e[p].info) p=j;
if(p!=i)
{t=W->e[p].info;
W->e[p].info=W->e[i].info;
W->e[i].info=t;
k=W->e[p].z;
W->e[p].z=W->e[i].z;
W->e[i].z=k;
k=W->e[p].y;
W->e[p].y=W->e[i].y;
W->e[i].y=k;
}
}/*
for (i=0;i<(G->e);i++)
printf("%.1f ",W->e[i].info);
printf("\n");*/
}
int judge_vertex(WGraph *w,int i,struct visit *vp)
{
if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)
return 1;
else if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)
return 2;
else if(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)
return 3;
else if(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].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;i<(G->n);i++)
{vp->visited[i]=-1;
vp->position[i]=-1;
vp->vvpp[i][0]=i+1;
for(j=1;j<G->n;j++)
vp->vvpp[i][j]=0;
}
T.v[0]=w->v[w->e[0].z-1];
T.v[1]=w->v[w->e[0].y-1];
vp->visited[w->e[0].z-1]=1;
vp->position[w->e[0].z-1]=w->e[0].z;
for(j=0;j<(G->n);j++)
if(vp->vvpp[w->e[0].z-1][j]==0)
{vp->vvpp[w->e[0].z-1][j]=w->e[0].y;
break;}
vp->visited[w->e[0].y-1]=1;
vp->position[w->e[0].y-1]=w->e[0].z;
T.e[0].info=w->e[0].info;
T.e[0].z=w->e[0].z;
T.e[0].y=w->e[0].y;
for(i=1;i<(G->e);i++)
{t=judge_vertex(w,i,vp);
if(t==4)
{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1])
continue;
else{ abc=0；bcd=0;
for(j=0;j<G->n;j++)
if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0)
abc++;
for(j=0;j<G->n;j++)
if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0)
bcd++;
for(j=bcd,h=0;j<G->n&&h<abc;j++,h++)
{vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];
vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;
}
for(h=bcd;h<abc+bcd;h++)
vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
}
else if(t==1)
{ vp->visited[w->e[i].z-1]=1;
vp->visited[w->e[i].y-1]=1;
T.v[k++]=w->v[w->e[i].z-1];
T.v[k++]=w->v[w->e[i].y-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
vp->position[w->e[i].z-1]=w->e[i].z;
vp->position[w->e[i].y-1]=w->e[i].z;
vp->vvpp[w->e[i].z-1][1]=w->e[i].y;
vp->vvpp[w->e[i].y-1][0]=0;
}
else if(t==2)
{vp->visited[w->e[i].z-1]=1;
vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];
for(j=0;j<(G->n);j++)
if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0)
{vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z;
break;
}
vp->vvpp[w->e[i].z-1][0]=0;
T.v[k++]=w->v[w->e[i].z-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
else if(t==3)
{vp->visited[w->e[i].y-1]=1;
vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1];
for(j=0;j<(G->n);j++)
if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0)
{vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y;
break;
}
vp->vvpp[w->e[i].y-1][0]=0;
T.v[k++]=w->v[w->e[i].y-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
}
printf("Please output the information:\n");
for(i=0;i<(G->n)-1;i++)
printf("(%c,%c)\n",T.e[i].z+64,T.e[i].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->v[0]=G->adjlist[0].vertex;
s=G->adjlist[0].firstedge;
while(s!=NULL)
{W->e[k].z=1;
W->e[k].y=s->adjvex;
W->e[k].info=s->info;
k++;
s=s->next;
}
for(i=1;i<(G->n);i++)
{W->v[i]=G->adjlist[i].vertex;
s=G->adjlist[i].firstedge;
while(s!=NULL)
{m=Panduan_Vertex(k,i,W,s);
if(m==1)
{s=s->next;
continue;}
else
{ W->e[k].z=i+1;
W->e[k].y=s->adjvex;
W->e[k].info=s->info;
k++;
s=s->next;
}
}
}/*
printf("Please output the information:\n");
for(i=0;i<G->n;i++)
printf("%c\n",W->v[i]);
for(i=0;i<G->e;i++)
printf("%d,%d,%.1f\n",W->e[i].z,W->e[i].y,W->e[i].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.浮现问题及解决办法：
在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路算法中遇到很大困难，日后采用如下办法解决了这个问题：
将每个顶点分别放在一种构造体中，构造体中数组visited[i]记录顶点Vi与否被访问过状况，position[i]记录顶点Vi详细位置，二维数组vvpp[i][j]记录已经将以该顶点为左顶点或右顶点权值存入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<stdio.h> /*调用头文献库阐明*/
#include<stdlib.h>
#define MaxVerNum 100
static 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 AdjList[MaxVerNum];
typedef struct /*构造图构造体*/
{AdjList adjlist； /*邻接表*/
int n,e； /*顶点数和边数*/
}ALGraph;
struct bian /*存储权值及其左右顶点构造体*/
{int z,y；
float info;
};
typedef struct /*用该构造体来只存储一次权值及其相应顶点*/
{char v[MaxVerNum];
struct bian e[MaxVerNum];
}WGraph;
struct visit /*用该构造体来存储各结点被访问状况，
{visited[MaxVerNum]； 位置，和其她结点关系*/
position[MaxVerNum];
vvpp[MaxVerNum][MaxVerNum];
}
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,e>:\n")； /*输入顶点数和边数*/
scanf("%d,%d",&(G->n),&(G->e));
printf("Please input the information of the vertices<v>:\n");
getchar();
for(i=0;i<(G->n);i++) /*建立有n各顶点顶点表*/
{scanf("%c",&(G->adjlist[i].vertex))； /*读入顶点信息*/
G->adjlist[i].firstedge=NULL;
}
for(k=0;k<2*(G->e);k++) /*建立边表*/
{printf("Please input the information of edges<p,q>:\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->adjlist[i-1].firstedge； /*将新边表结点s插入到顶点Vi边表头部*/
G->adjlist[i-1].firstedge=s;
}
}
int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s) /*判断该边是不是已经读入到w指
{int t； 向构造体中*/
for(t=0;t<k;t++)
if((w->e[t]).y==i+1&&(w->e[t]).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;i<(G->e);i++) /*简朴选取排序*/
{p=i;
for(j=i+1;j<(G->e);j++)
if(W->e[j].info<W->e[p].info) p=j;
if(p!=i)
{t=W->e[p].info； /*将两条边权值左右顶点都进行互换*/
W->e[p].info=W->e[i].info;
W->e[i].info=t;
k=W->e[p].z;
W->e[p].z=W->e[i].z;
W->e[i].z=k;
k=W->e[p].y;
W->e[p].y=W->e[i].y;
W->e[i].y=k;
}
}/*
for (i=0;i<(G->e);i++)
printf("%.1f ",W->e[i].info);
printf("\n");*/
}
int judge_vertex(WGraph *w,int i,struct visit *vp) /*判断顶点访问状况*/
{
if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)
return 1;
else if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)
return 2;
else if(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)
return 3;
else if(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].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;i<(G->n);i++) /*将各顶点被访问状况，位置，与其她顶点
{vp->visited[i]=-1； 互有关系进行初始化*/
vp->position[i]=-1;
vp->vvpp[i][0]=i+1;
for(j=1;j<G->n;j++)
vp->vvpp[i][j]=0;
}
T.v[0]=w->v[w->e[0].z-1];
T.v[1]=w->v[w->e[0].y-1];
vp->visited[w->e[0].z-1]=1;
vp->position[w->e[0].z-1]=w->e[0].z;
for(j=0;j<(G->n);j++)
if(vp->vvpp[w->e[0].z-1][j]==0)
{vp->vvpp[w->e[0].z-1][j]=w->e[0].y;
break;}
vp->visited[w->e[0].y-1]=1;
vp->position[w->e[0].y-1]=w->e[0].z;
T.e[0].info=w->e[0].info;
T.e[0].z=w->e[0].z;
T.e[0].y=w->e[0].y;
for(i=1;i<(G->e);i++)
{t=judge_vertex(w,i,vp)； /*依照不同顶点访问状况选用相应操作*/
if(t==4) /*两顶点均已被访问过状况*/
{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]) /*两顶点位置相似*/
continue； /*舍去这条边，否则会构成回路*/
else{ abc=0；bcd=0； /*倘若两顶点位置不同*/
for(j=0;j<G->n;j++)
if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0)
abc++;
for(j=0;j<G->n;j++)
if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0)
bcd++;
for(j=bcd,h=0;j<G->n&&h<abc;j++,h++) 将两顶点放在同一种数组中*/
{vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];
vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0；/*将原数组置零*/
}
for(h=bcd;h<abc+bcd;h++)
vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1];
T.e[m].info=w->e[i].info； /*将该边存入T中*/
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
}
else if(t==1) /*两顶点都未被访问状况*/
{ vp->visited[w->e[i].z-1]=1;
vp->visited[w->e[i].y-1]=1;
T.v[k++]=w->v[w->e[i].z-1];
T.v[k++]=w->v[w->e[i].y-1];
T.e[m].info=w->e[i].info； /*将该边存入T中*/
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
vp->position[w->e[i].z-1]=w->e[i].z； /*将两顶点位置改为相似*/
vp->position[w->e[i].y-1]=w->e[i].z;
vp->vvpp[w->e[i].z-1][1]=w->e[i].y； /*将两顶点存储到一种数组中*/
vp->vvpp[w->e[i].y-1][0]=0;
}