管道铺设问题.docx
《管道铺设问题.docx》由会员分享,可在线阅读,更多相关《管道铺设问题.docx(26页珍藏版)》请在冰点文库上搜索。
管道铺设问题
实验三:
管道铺设施工的最佳方案
一.问题描述
1.实验题目:
需要在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。
假设任意两个小区之间则可以铺设管道,但由于地理环境不同,所需要的费用也不尽相同。
选择最优的方案能使总投资尽可能小,这个问题即为求无向网的最小生成树。
2.基本要求:
在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。
每条管道的费用以网中该边的权值形式给出,网的存储采用邻接表的结构。
3.测试数据:
使用下图给出的无线网数据作为程序的输入,求出最佳铺设方案。
参考解:
二.需求分析
1.程序所能达到的基本可能:
在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。
选择最优的方案能使总投资尽可能小,在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。
2.输入输出形式及输入值范围:
程序运行后,显示提示信息:
请输入顶点数和边数(输入格式为:
顶点数,边数)之后程序从文件名为”C:
\\data.txt读入顶点信息和边的信息,之后显示提示信息输入开始节点,执行生成最小树程序,输出生成的最小树信息。
3.测试数据要求:
顶点数边数为整数,顶点信息为大写字母,边的权值为浮点型,C:
\\data.txt文件内容为:
ABCDEFGHI
1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.27852.51812.1898.71918.23541.1
三.概要设计
1.所用到得数据结构及其ADT
typedefstructnode//边表结点
{
intNO;//邻接点域;
vertexTypeadjvex;
EdgeTypeinfo;//权值
structnode*next;//指向下一个邻接点的指针域
}EdgeNode;
typedefstructvnode//顶点表节点
vertexTypevertex;//顶点域
EdgeNode*firstedge;//编表头指针
}VertexNode;
typedefstruct//邻接表
VertexNodeadjlist[MaxVertexNum];
intn,e;//顶点数和边数
}ALGraph;//ALGraph是以邻接表方式存储的图类型
基本操作:
ALGraph*CreateALGraph()//建表
2.主程序流程及其模块调用关系
1)主程序模块
建表模块ALGraph*CreateALGraph()
最小生成树模块voidtree(ALGraph*G,intm)
函数调用关系图
四、详细设计
1.实现每个操作的伪码,重点语句加注释
1)建表模块
inti,j,k;
floatm;
FILE*fp;
EdgeNode*s,*t;
ALGraph*G;
fp=fopen("C:
\\data.txt","r");//打开文件
if(fp==NULL)//未找到文件
printf("Cann'topenthefile!
\n");
exit
(1);
}
G=(ALGraph*)malloc(sizeof(ALGraph));
printf("请输入顶点数和边数(输入格式为:
顶点数,边数)\n");
scanf("%d,%d",&G->n,&G->e);
for(i=1;i<=G->n;i++)//建立顶点信息
G->adjlist[i].vertex=fgetc(fp);
G->adjlist[i].firstedge=NULL;
visited[i]=i;
for(k=1;k<=G->e;k++)
//printf("请输入第%d条边的两个端点序号,输入格式为:
i,j\n",k);
//scanf("%d,%d",&i,&j);
fscanf(fp,"%d",&i);
fscanf(fp,"%d",&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
t=(EdgeNode*)malloc(sizeof(EdgeNode));
//printf("请输入第%d条边的对应权值\n",k);
fscanf(fp,"%f",&m);//保存边信息,以无向网方式
s->NO=j;
s->adjvex=G->adjlist[j].vertex;
s->info=m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
t->NO=i;
t->adjvex=G->adjlist[i].vertex;
t->info=m;
t->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=t;
fclose(fp);//关闭文件
returnG;
2)生成最小生成树模块
voidtree(ALGraph*G,intm)
floatlow[100];intteed[100];
intk,i,j;
floatmin,sum=0;
EdgeNode*s;
low[m]=0;
visited[m]=0;
for(i=1;i<=G->n;i++)
low[i]=1000;
teed[i]=m;
s=G->adjlist[m].firstedge;
while(s!
=NULL)//数组初始化
low[s->NO]=s->info;
s=s->next;
for(i=1;in;i++)
min=1000;
for(j=1;j<=G->n;j++)
if(visited[j]>0&&low[j]{min=low[j];k=j;//标记节点}}sum+=min;visited[k]=0;s=G->adjlist[k].firstedge;while(s!=NULL){if(visited[s->NO]>0&&s->infoNO])//找到最小权值{low[s->NO]=s->info;teed[s->NO]=k;}s=s->next;}}printf("最佳铺设方案\n");for(i=1;i<=G->n;i++)//输出最小生成树信息if(i!=m)printf("(%d,%d)%.2f\t",i,teed[i],low[i]);printf("最小权值为:%.2f\n",sum);}3)主函数模块voidmain(){ALGraph*G;inti;time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);printf("实验名称:实验三:管道铺设施工的最佳方案\n");printf("学号:031350102\n");printf("姓名:王亚文\n");printf("=============================================\n");printf("程序运行开始,");printf("Currentlocaltimeanddate:%s",asctime(timeinfo));G=CreateALGraph();//建表printf("输入开始节点\n");scanf("%d",&i);tree(G,i);//生成最小树//printfALGraph(G);printf("\n");printf("Currentlocaltimeanddate:%s",asctime(timeinfo));}五、调试分析1.设计与调试过程中遇到的问题分析、体会1)一开始对文件读写操作不熟,采用从键盘输出的方式验证正确与否,对应程序如下:inti,j,k;floatm;EdgeNode*s,*t;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));printf("请输入顶点数和边数(输入格式为:顶点数,边数)\n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i++)//建立顶点信息{G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;}for(k=1;k<=G->e;k++){printf("请输入第%d条边的两个端点序号,输入格式为:i,j\n",k);scanf("%d,%d",&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode));t=(EdgeNode*)malloc(sizeof(EdgeNode));printf("请输入第%d条边的对应权值\n",k);scanf("%f",&m);//保存边信息,以无向网方式s->NO=j;s->adjvex=G->adjlist[j].vertex;s->info=m;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;t->NO=i;t->adjvex=G->adjlist[i].vertex;t->info=m;t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;}returnG;}对应截屏如下:发现这种方式输入耗时长,而且在生成树程序不正确时修改程序需要重复输入,较为麻烦2)为检验所建立的无向网,编写了一个输出函数,输出各个顶点以及与该顶点相邻的其他顶点以及对应权值,输出函数为voidprintfALGraph(ALGraph*G)//输出表{inti;EdgeNode*s;printf("输出信息\n");for(i=1;i<=G->n;i++){printf("%c的邻接点及权值:\n",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("%c%.2f",s->adjvex,s->info);s=s->next;}printf("\n");}}输出测试截屏如下证明从文件读写的与所需要建立的无向网相符2.主要算法的时间复杂度分析六、使用说明程序运行后,显示提示信息:请输入顶点数和边数(输入格式为:顶点数,边数)之后程序从文件名为”C:\\data.txt读入顶点信息和边的信息,之后显示提示信息输入开始节点,执行生成最小树程序,输出生成的最小树信息。七、测试结果3)这个程序遇到的第一个主要问题是在建表过程,因为边的顶点信息是大写英文字母,一开始我是用的ASCLL码值,使用不方便,后来采用在定义时考虑多定义一个量,原程序:typedefstructnode//边表结点{vertexTypeadjvex;//邻接点域;EdgeTypeinfo;//权值structnode*next;//指向下一个邻接点的指针域}EdgeNode;修正后的程序为:typedefstructnode//边表结点{intNO;//邻接点域;vertexTypeadjvex;EdgeTypeinfo;//权值structnode*next;//指向下一个邻接点的指针域}EdgeNode;这样多定义了一个量在后面的过程中会简单许多,其次书上给的程序是生成有向网的,一开始我是考虑的将边输入两边,就是在循环时的终止条件设为k<=2*G->e;这样虽然能解决无向网问题,但是一条边重复输入两边,较为麻烦,后期修正为:s->NO=j;s->adjvex=G->adjlist[j].vertex;s->info=m;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;t->NO=i;t->adjvex=G->adjlist[i].vertex;t->info=m;t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中,原程序:typedefVertexNodeAdjlist[MaxVertexNum];typedefstruct//邻接表{Adjlistadjlist;//intn,e;//顶点数和边数intn;inte;}ALGraph;//ALGraph是以邻接表方式存储的图类型这个程序是抄的书上的,一开始不觉得书上的程序会是错的,结果一直没有看这个定义,在输入边的信息时循环次数总是不对,一直尝试着改动写的输入信息,弄了一下午也没有搞定这个问题,于是去求助研究生学长,下面是研究生学长发过来的邮件帮我指出错误所在,看了学长的这封邮件后,重新改了一下自己的程序,修正后的程序为typedefstruct//邻接表{VertexNodeadjlist[MaxVertexNum];intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型程序修正后输入正常了,就开始进入下一个阶段生成最小树的程序。3)在生成最小树这个程序的编写中,开始因为编程序是在老师讲解生成树之前,所以一开始是完全没有地方下手,网上XX了一下如何生成最小树,发现有两种方法,Kruskal和prim算法,但研究生学长这个适合用prim算法,Kruskal算法适合与边稀疏的连通图求解最小生成树,所以在编写时主要研究的是用prim算法,在编写prim算法时除了很多问题,例如一开始我并没有在循环中写teed[i]=m;这句话,导致在最后输出边的信息时会有随机数产生,截图如下:想到随机数产生可能是因为没有赋值,所以加上teed[i]=m;这句话果然最后就输出正确了,再次在输出时,产生的结果中有重复的一个节点,<1,1>1000.00这个不应该被输出,所以考虑在输出时加一个限制条件if(i!=m)再次输出就没有了,中间编写时问题不大,之前有看过prim算法的详细介绍,所以在主思路上没有太大的错误,相对写起来也比较顺利。2)建立邻接表的复杂度为O(n+e);Prim算法的时间复杂度为O(elogn);八、附录#include#include#include#include//输入序号与字母对应关系A-1,,B-2,C-3,D-4,E-5,F-6,G-7,H-8,I-9#defineMaxVertexNum100typedefcharvertexType;typedeffloatEdgeType;intvisited[100];//访问变量,为一时表示未访问typedefstructnode//边表结点{intNO;//邻接点域;vertexTypeadjvex;EdgeTypeinfo;//权值structnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表节点{vertexTypevertex;//顶点域EdgeNode*firstedge;//编表头指针}VertexNode;typedefstruct//邻接表{VertexNodeadjlist[MaxVertexNum];intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型ALGraph*CreateALGraph()//建表{inti,j,k;floatm;FILE*fp;EdgeNode*s,*t;ALGraph*G;fp=fopen("C:\\data.txt","r");//打开文件if(fp==NULL)//未找到文件{printf("Cann'topenthefile!\n");exit(1);}G=(ALGraph*)malloc(sizeof(ALGraph));printf("请输入顶点数和边数(输入格式为:顶点数,边数)\n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i++)//建立顶点信息{G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;}for(k=1;k<=G->e;k++){//printf("请输入第%d条边的两个端点序号,输入格式为:i,j\n",k);//scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode*)malloc(sizeof(EdgeNode));t=(EdgeNode*)malloc(sizeof(EdgeNode));//printf("请输入第%d条边的对应权值\n",k);fscanf(fp,"%f",&m);//保存边信息,以无向网方式s->NO=j;s->adjvex=G->adjlist[j].vertex;s->info=m;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;t->NO=i;t->adjvex=G->adjlist[i].vertex;t->info=m;t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;}fclose(fp);//关闭文件returnG;}voidtree(ALGraph*G,intm){floatlow[100];intteed[100];intk,i,j;floatmin,sum=0;EdgeNode*s;low[m]=0;visited[m]=0;for(i=1;i<=G->n;i++){low[i]=1000;teed[i]=m;}s=G->adjlist[m].firstedge;while(s!=NULL)//数组初始化{low[s->NO]=s->info;s=s->next;}for(i=1;in;i++){min=1000;for(j=1;j<=G->n;j++){if(visited[j]>0&&low[j]{min=low[j];k=j;//标记节点}}sum+=min;visited[k]=0;s=G->adjlist[k].firstedge;while(s!=NULL){if(visited[s->NO]>0&&s->infoNO])//找到最小权值{low[s->NO]=s->info;teed[s->NO]=k;}s=s->next;}}printf("最佳铺设方案\n");for(i=1;i<=G->n;i++)//输出最小生成树信息if(i!=m)printf("(%d,%d)%.2f\t",i,teed[i],low[i]);printf("最小权值为:%.2f\n",sum);}/*voidprintfALGraph(ALGraph*G)//输出表{inti;EdgeNode*s;printf("输出信息\n");for(i=1;i<=G->n;i++){printf("%c的邻接点及权值:\n",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("%c%.2f",s->adjvex,s->info);s=s->next;}printf("\n");}}*/voidmain(){ALGraph*G;inti;time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);printf("实验名称:实验三:管道铺设施工的最佳方案\n");prin
min=low[j];
k=j;//标记节点
sum+=min;
visited[k]=0;
s=G->adjlist[k].firstedge;
=NULL)
if(visited[s->NO]>0&&s->infoNO])//找到最小权值
teed[s->NO]=k;
printf("最佳铺设方案\n");
for(i=1;i<=G->n;i++)//输出最小生成树信息
if(i!
=m)
printf("(%d,%d)%.2f\t",i,teed[i],low[i]);
printf("最小权值为:
%.2f\n",sum);
3)主函数模块
voidmain()
inti;
time_trawtime;
structtm*timeinfo;
time(&rawtime);
timeinfo=localtime(&rawtime);
printf("实验名称:
管道铺设施工的最佳方案\n");
printf("学号:
031350102\n");
printf("姓名:
王亚文\n");
printf("=============================================\n");
printf("程序运行开始,");
printf("Currentlocaltimeanddate:
%s",asctime(timeinfo));
G=CreateALGraph();//建表
printf("输入开始节点\n");
scanf("%d",&i);
tree(G,i);//生成最小树
//printfALGraph(G);
printf("\n");
五、调试分析
1.设计与调试过程中遇到的问题分析、体会
1)一开始对文件读写操作不熟,采用从键盘输出的方式验证正确与否,对应程序如下:
printf("请输入第%d条边的两个端点序号,输入格式为:
scanf("%d,%d",&i,&j);
printf("请输入第%d条边的对应权值\n",k);
scanf("%f",&m);//保存边信息,以无向网方式
对应截屏如下:
发现这种方式输入耗时长,而且在生成树程序不正确时修改程序需要重复输入,较为麻烦
2)为检验所建立的无向网,编写了一个输出函数,输出各个顶点以及与该顶点相邻的其他顶点以及对应权值,输出函数为voidprintfALGraph(ALGraph*G)//输出表
printf("输出信息\n");
printf("%c的邻接点及权值:
\n",G->adjlist[i].vertex);
s=G->adjlist[i].firstedge;
printf("%c%.2f",s->adjvex,s->info);
输出测试截屏如下证明从文件读写的与所需要建立的无向网相符
2.主要算法的时间复杂度分析
六、使用说明
七、测试结果
3)这个程序遇到的第一个主要问题是在建表过程,因为边的顶点信息是大写英文字母,一开始我是用的ASCLL码值,使用不方便,后来采用在定义时考虑多定义一个量,原程序:
vertexTypeadjvex;//邻接点域;
修正后的程序为:
这样多定义了一个量在后面的过程中会简单许多,其次书上给的程序是生成有向网的,一开始我是考虑的将边输入两边,就是在循环时的终止条件设为k<=2*G->e;这样虽然能解决无向网问题,但是一条边重复输入两边,较为麻烦,后期修正为:
修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。
其次解决耗时最长的一个错误是在建表中,原程序:
typedefVertexNodeAdjlist[MaxVertexNum];
Adjlistadjlist;
//intn,e;//顶点数和边数
intn;
inte;
这个程序是抄的书上的,一开始不觉得书上的程序会是错的,结果一直没有看这个定义,在输入边的信息时循环次数总是不对,一直尝试着改动写的输入信息,弄了一下午也没有搞定这个问题,于是去求助研究生学长,下面是研究生学长发过来的邮件帮我指出错误所在,看了学长的这封邮件后,重新改了一下自己的程序,修正后的程序为
程序修正后输入正常了,就开始进入下一个阶段生成最小树的程序。
3)在生成最小树这个程序的编写中,开始因为编程序是在老师讲解生成树之前,所以一开始是完全没有地方下手,网上XX了一下如何生成最小树,发现有两种方法,Kruskal和prim算法,但研究生学长这个适合用prim算法,Kruskal算法适合与边稀疏的连通图求解最小生成树,所以在编写时主要研究的是用prim算法,在编写prim算法时除了很多问题,例如一开始我并没有在循环中写teed[i]=m;这句话,导致在最后输出边的信息时会有随机数产生,截图如下:
想到随机数产生可能是因为没有赋值,所以加上teed[i]=m;这句话果然最后就输出正确了,再次在输出时,产生的结果中有重复的一个节点,<1,1>1000.00这个不应该被输出,所以考虑在输出时加一个限制条件if(i!
=m)再次输出就没有了,
中间编写时问题不大,之前有看过prim算法的详细介绍,所以在主思路上没有太大的错误,相对写起来也比较顺利。
2)建立邻接表的复杂度为O(n+e);
Prim算法的时间复杂度为O(elogn);
八、附录
#include
//输入序号与字母对应关系A-1,,B-2,C-3,D-4,E-5,F-6,G-7,H-8,I-9
#defineMaxVertexNum100
typedefcharvertexType;
typedeffloatEdgeType;
intvisited[100];//访问变量,为一时表示未访问
if(visited[j]>0&&low[j]{min=low[j];k=j;//标记节点}}sum+=min;visited[k]=0;s=G->adjlist[k].firstedge;while(s!=NULL){if(visited[s->NO]>0&&s->infoNO])//找到最小权值{low[s->NO]=s->info;teed[s->NO]=k;}s=s->next;}}printf("最佳铺设方案\n");for(i=1;i<=G->n;i++)//输出最小生成树信息if(i!=m)printf("(%d,%d)%.2f\t",i,teed[i],low[i]);printf("最小权值为:%.2f\n",sum);}/*voidprintfALGraph(ALGraph*G)//输出表{inti;EdgeNode*s;printf("输出信息\n");for(i=1;i<=G->n;i++){printf("%c的邻接点及权值:\n",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("%c%.2f",s->adjvex,s->info);s=s->next;}printf("\n");}}*/voidmain(){ALGraph*G;inti;time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);printf("实验名称:实验三:管道铺设施工的最佳方案\n");prin
/*voidprintfALGraph(ALGraph*G)//输出表
*/
prin
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2