管道铺设问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“管道铺设方式”。
实验三：管道铺设施工的最佳方案
一．问题描述 1.实验题目：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：
在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3.测试数据：
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。
A38.244.618.28.7112.IB5.9CH52.541.1.379.256.4G10.585.667.3D参考解： 21E98.7F
AI.32B5.988.H7C41.1EGD二．需求分析
1.程序所能达到的基本可能： 2110.5F
在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。
2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。
3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:data.txt文件内容为：ABCDEFGHI 1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 6 9 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.2 3 5 41.1 三．概要设计
1.所用到得数据结构及其ADT typedef struct node //边表结点 { int NO;//邻接点域;vertexType adjvex;.379.2.112 EdgeType info;//权值
struct node *next;//指向下一个邻接点的指针域
}EdgeNode;
typedef struct vnode //顶点表节点 { vertexType vertex;//顶点域 EdgeNode *firstedge;//编表头指针
}VertexNode;
typedef struct //邻接表 { VertexNode adjlist[MaxVertexNum];int n,e;//顶点数和边数
}ALGraph;// ALGraph是以邻接表方式存储的图类型 基本操作：ALGraph * CreateALGraph()//建表 2.主程序流程及其模块调用关系 1)主程序模块
开始显示主界面建表生成最小树结束
建表模块ALGraph * CreateALGraph()开始打开文件fp=fopen(“C:data.txt”,“r”);fp==NULL读取G->n,G->e顶点数边数printf(“Cann't open the file!n”);打开文件失败i=1inYG->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;Nk=1keYfscanf(fp,“%d”,&i);fscanf(fp,“%d”,&j);fscanf(fp,“%f”,&m);输入边的信息N关闭文件结束i++;将边的信息存储到邻接表中k++最小生成树模块void tree(ALGraph *G,int m)开始sum=0;low[m]=0;visited[m]=0;i=1NinYlow[i]=1000;teed[i]=m;s=G->adjlist[m].firstedge;Ns!=NULLi=1结束Ylow[s->NO]=s->info;s=s->next;Nini=1Nini++Yi!=mYmin=1000;j=1YNjnsum+=min;visited[k]=0;s=G->adjlist[k].firstedge;Yi++visited[j]>0&&low[j]NO]>0&&s->infoNO]low[s->NO]=s->info;teed[s->NO]=k;i++s=s->next;
函数调用关系图
CreateALGraph();建表main()主函数tree(G,i);生成最小树
四、详细设计
1.实现每个操作的伪码，重点语句加注释 1）建表模块
ALGraph * CreateALGraph()//建表 {
int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen(“C:data.txt”,“r”);//打开文件 if(fp==NULL)//未找到文件 {
} printf(“Cann't open the file!n”);exit(1);G=(ALGraph *)malloc(sizeof(ALGraph));
printf(“请输入顶点数和边数（输入格式为：顶点数,边数）n”);scanf(“%d,%d”,&G->n,&G->e);for(i=1;in;i++)//建立顶点信息 { G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;
} for(k=1;ke;k++){ // printf(“请输入第%d条边的两个端点序号，输入格式为：i,jn”,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);
t->NO=i;t->adjvex=G->adjlist[i].vertex;
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->info=m;
t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;
} } fclose(fp);//关闭文件 return G;2）生成最小生成树模块 void tree(ALGraph *G,int m){
float low[100];int teed[100];int k,i,j;float min,sum=0;EdgeNode *s;low[m]=0;visited[m]=0;for(i=1;in;i++)
{
} s=G->adjlist[m].firstedge;while(s!=NULL)//数组初始化 {
} for(i=1;in;i++){
min=1000;for(j=1;jn;j++){ low[s->NO]=s->info;s=s->next;low[i]=1000;teed[i]=m;
}
} 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])//找到最小权值 {
} s=s->next;low[s->NO]=s->info;teed[s->NO]=k;printf(“最佳铺设方案n”);
} 3）主函数模块 void main(){ ALGraph *G;int i;for(i=1;in;i++)//输出最小生成树信息
if(i!=m)printf(“(%d,%d)%.2ft”,i,teed[i],low[i]);printf(“最小权值为:%.2fn”,sum);time_t rawtime;struct tm * timeinfo;time(&rawtime);timeinfo = localtime(&rawtime);printf(“ 实验名称：实验三：管道铺设施工的最佳方案n”);printf(“ 学号：031350102n”);printf(“ 姓名：王亚文n”);printf(“=============================================n”);
printf(“程序运行开始，”);printf(“Current local time and date:%s”,asctime(timeinfo));G=CreateALGraph();//建表 printf(“输入开始节点n”);scanf(“%d”,&i);tree(G,i);//生成最小树 //printfALGraph(G);printf(“n”);
}
五、调试分析
1.设计与调试过程中遇到的问题分析、体会
1）一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下： int i,j,k;
float m;EdgeNode *s,*t;ALGraph *G;printf(“Current local time and date:%s”,asctime(timeinfo));G=(ALGraph *)malloc(sizeof(ALGraph));
printf(“请输入顶点数和边数（输入格式为：顶点数,边数）n”);scanf(“%d,%d”,&G->n,&G->e);for(i=1;in;i++)//建立顶点信息 { G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;
} for(k=1;ke;k++){ printf(“请输入第%d条边的两个端点序号，输入格式为：i,jn”,k);
scanf(“%d,%d”,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode));t=(EdgeNode *)malloc(sizeof(EdgeNode));printf(“请输入第%d条边的对应权值n”,k);
} 对应截屏如下：发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输入，较为麻烦 t->NO=i;t->adjvex=G->adjlist[i].vertex;
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->info=m;
} return G;t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;
2）为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他顶点以及对应权值，输出函数为void printfALGraph(ALGraph *G)//输出表 {
int i;EdgeNode *s;printf(“输出信息n”);for(i=1;in;i++)
} 输出测试截屏如下证明从文件读写的与所需要建立的无向网相符 {
} printf(“%c的邻接点及权值:n”,G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){
} printf(“n”);printf(“%c %.2f ”,s->adjvex,s->info);s=s->next;
2.主要算法的时间复杂度分析
六、使用说明
程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。
七、测试结果
3）这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序： typedef struct node //边表结点 {
vertexType adjvex;
//邻接点域;EdgeType info;//权值
struct node *next;//指向下一个邻接点的指针域
}EdgeNode;修正后的程序为：
typedef struct node //边表结点 {
int NO;//邻接点域;vertexType adjvex;EdgeType info;//权值
struct node *next;//指向下一个邻接点的指针域
}EdgeNode;这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的，一开始我是考虑的将边输入两边，就是在循环时的终止条件设为ke；这样虽然能解决无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：
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句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中，原程序：
typedef VertexNode Adjlist[MaxVertexNum];
typedef struct //邻接表 {
Adjlist adjlist;//int n,e;//顶点数和边数 int n;int e;}ALGraph;// ALGraph是以邻接表方式存储的图类型 这个程序是抄的书上的，一开始不觉得书上的程序会是错的，结果一直没有看这个定义，在输入边的信息时循环次数总是不对，一直尝试着改动写的输入信息，弄了一下午也没有搞定这个问题，于是去求助研究生学长，下面是研究生学长发过来的邮件帮我指出错误所在，看了学长的这封邮件后，重新改了一下自己的程序，修正后的程序为 typedef struct //邻接表 { VertexNode adjlist[MaxVertexNum];int n,e;//顶点数和边数 }ALGraph;// ALGraph是以邻接表方式存储的图类型
程序修正后输入正常了，就开始进入下一个阶段生成最小树的程序。
3）在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开始是完全没有地方下手，网上百度了一下如何生成最小树，发现有两种方法，Kruskal和prim算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连通图求解最小生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如一开始我并没有在循环中写teed[i]=m;这句话，导致在最后输出边的信息时会有随机数产生，截图如下：
想到随机数产生可能是因为没有赋值，所以加上teed[i]=m;这句话果然最后就输出正确了，再次在输出时，产生的结果中有重复的一个节点，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 #define MaxVertexNum 100 typedef char vertexType;typedef float EdgeType;int visited[100];//访问变量，为一时表示未访问 typedef struct node //边表结点 {
int NO;//邻接点域;vertexType adjvex;EdgeType info;//权值
struct node *next;//指向下一个邻接点的指针域
}EdgeNode;
typedef struct vnode //顶点表节点 { vertexType vertex;//顶点域 EdgeNode *firstedge;//编表头指针
}VertexNode;
typedef struct //邻接表 { VertexNode adjlist[MaxVertexNum];int n,e;//顶点数和边数
}ALGraph;// ALGraph是以邻接表方式存储的图类型
ALGraph * CreateALGraph()//建表 {
int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen(“C:data.txt”,“r”);//打开文件 if(fp==NULL)//未找到文件 {
} printf(“Cann't open the file!n”);exit(1);G=(ALGraph *)malloc(sizeof(ALGraph));
printf(“请输入顶点数和边数（输入格式为：顶点数,边数）n”);scanf(“%d,%d”,&G->n,&G->e);for(i=1;in;i++)//建立顶点信息 { G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;
} for(k=1;ke;k++){ // printf(“请输入第%d条边的两个端点序号，输入格式为：i,jn”,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;
} fclose(fp);//关闭文件 return G;t->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=t;void tree(ALGraph *G,int m){
float low[100];int teed[100];int k,i,j;float min,sum=0;EdgeNode *s;low[m]=0;visited[m]=0;for(i=1;in;i++)
{ low[i]=1000;teed[i]=m;
} s=G->adjlist[m].firstedge;while(s!=NULL)//数组初始化 {
} for(i=1;in;i++){
min=1000;for(j=1;jn;j++){
} sum+=min;visited[k]=0;s=G->adjlist[k].firstedge;while(s!=NULL){
} if(visited[s->NO]>0&&s->infoNO])//找到最小权值 {
} s=s->next;low[s->NO]=s->info;teed[s->NO]=k;if(visited[j]>0&&low[j]
} min=low[j];k=j;//标记节点 low[s->NO]=s->info;s=s->next;} printf(“最佳铺设方案n”);
} /*void printfALGraph(ALGraph *G)//输出表 {
int i;EdgeNode *s;printf(“输出信息n”);for(i=1;in;i++)//输出最小生成树信息
if(i!=m)printf(“(%d,%d)%.2ft”,i,teed[i],low[i]);printf(“最小权值为:%.2fn”,sum);for(i=1;in;i++)
} */ void main(){
ALGraph *G;int i;time_t rawtime;{
} printf(“%c的邻接点及权值:n”,G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){
} printf(“n”);printf(“%c %.2f ”,s->adjvex,s->info);s=s->next;struct tm * timeinfo;time(&rawtime);timeinfo = localtime(&rawtime);printf(“ 实验名称：实验三：管道铺设施工的最佳方案n”);printf(“ 学号：031350102n”);printf(“ 姓名：王亚文n”);printf(“=============================================n”);
printf(“程序运行开始，”);printf(“Current local time and date:%s”,asctime(timeinfo));G=CreateALGraph();//建表 printf(“输入开始节点n”);scanf(“%d”,&i);tree(G,i);//生成最小树 //printfALGraph(G);printf(“n”);
}
九、实验收获和感想
在这个管道铺设问题的程序设计中，弄懂题意后发现其实这个题需要解决两个问题，一个是建立无向网的问题，另一个就是最小生成树的求解，所以这个程序设计还是需要模块化设计这个思路，首先需要解决的是如何建立无向网，在这个过程中我编写了一个输出函数以检验所建立的无向网是否是我们所需要的，建立无向网这个过程是我编写这个程序耗时最长的，因为开始一味的相信书上的程序是正确的所以吃了不少苦，最后还是多亏了研究生学长才得以解决这个问题，这个教训也告诫我不能一味的相信书本，最后能输出正确结果的才是正确的程序，在之后的程序编写时不要再因为是书本的原程序就原封不动的抄上在后续出错时也不检查是否是这个抄的程序的错误，再次是要善于用自己所学的知识简化问题而不是只用一种方法解决这个问题，在这个程序中建立边表信息时再多建立一个NO信息就可以大大简化问题，所以编写程序时还是要多想想其他办法，还有就是这个测试数据有9个顶点信息，15条边的信息，在测试时挨个输入显然会很麻烦，所以善于运用文件操作会很方便的，但printf(“Current local time and date:%s”,asctime(timeinfo));是最开始我是使用的键盘输入，并且将原语句保留在程序中，使用时可以使用键盘输入，或者在定义的文件C:data.txt中改变边和顶点信息，不管怎么说，使用文件操作后真的是方便很多，在经历了一次又一次要输入9个顶点信息15条边信息后第一次使用文件操作后感悟还是蛮大的，而且通过上面截图对比发现界面也简洁很多，所以还是要多学些东西这样才可以在某些时候简化问题，使问题解决的更加方便，还有就是要善于求助，例如在建立无向网时被一个问题坑了一下午，这个时候去求教学长，不仅可以解决问题，而且能更加清晰的记住这个问题，还有因为这个程序最开始编写时老师没有讲到prim算法，书上也没有相关知识，而自己又无从下手时，这个时候可以考虑上网查些资料，毕竟网上资源还是很丰富的。
总之，这个管道铺设问题程序语句最后写下来并没有很多行，但还是暴露了自己的很多问题，在解决问题的过程中慢慢完善自己，希望自己的编程能力能有所提高。
法律意见及依据综合你的问题分析，这其实是一个“管道地下通过权”的问题。管道企业铺设天然气管道，必然会涉及沿线土地使用问题，根据实际情况，可分为三类：第一类是必然的永久性用......
为了保障事情或工作顺利、圆满进行，就不得不需要事先制定方案，方案是在案前得出的方法计划。我们应该重视方案的制定和执行，不断提升方案制定的能力和水平，以更好地应对未来的挑......
自来水管道铺设协议书甲方：乙方： 签约地点：签订日期： 年 月 日 根据《中华人民共和国合同法》及国家其他有关法律、法规的规定，甲、乙双方在平等、自愿、等价有偿、公平、诚实信......
在人们越来越相信法律的社会中，合同起到的作用越来越大，它可以保护民事法律关系。相信很多朋友都对拟合同感到非常苦恼吧。下面是我给大家整理的合同范本，欢迎大家阅读分享借鉴......
非开挖铺设管道施工技术随着我国社会经济的快速发展，城市公用管道建设项目日益增多，常规的施工技术越来越不适应城市发展的需要。开槽铺设地下管线需要占用路面妨碍交通；开挖回......
