管道铺设问题.docx
- 文档编号:1212231
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:26
- 大小:474.35KB
管道铺设问题.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)建表模块
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;
}
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;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->info { 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 #defineMaxVertexNum100 typedefcharvertexType; 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;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->info { 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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管道 铺设 问题