管道铺设课程设计报告.docx
《管道铺设课程设计报告.docx》由会员分享，可在线阅读，更多相关《管道铺设课程设计报告.docx（6页珍藏版）》请在冰点文库上搜索。
管道铺设课程设计报告
编号：
江西理工大学
数据结构课程设计报告
班级：
学号：
姓名：
时间：
2015年6月22日
～2015年7月3日
指导教师：
2015年06月
一、摘要.....................................................................3
二、引言.......................................................................3
三、需求分析...............................................................3
四、概要设计...............................................................4
1.普利姆算法分析...............................................6
2.模块分析...........................................................6
3.抽象数据类型分析...........................................6
4.全部流程...........................................................6
五、详细设计...............................................................7
1.算法分析...........................................................7
（一）信息输入模块.........................................7
（二）建立最小生成树并输出结果.................8
2.源程序代码.......................................................9
六、测试结果...............................................................14
程序开始...............................................................14
信息输入...............................................................14
输出结果...............................................................14
七、设计体会...............................................................15
八、结束语...................................................................16
参考文献...............................................................16
一、摘要
N（N>10）个居民区之间需要铺设煤气管道。
假设任意两个居民区之间都可以铺设煤气管道，但代价不同。
问题的实质就是编写相应程序求解最小生成树问题。
程序要求：
事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。
设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。
二、引言
C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。
在各种流行编程语言中，都能看到C语言的影子。
学习掌握C语言是每一个计算机技术人员的基本功之一。
实际生活中最小生成树的问题具有很大的意义。
例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。
最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。
三需求分析
在N（N>10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。
在我们的课本中介绍了两种求解方法：
普利姆算法和克鲁斯卡尔算法。
普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。
而克鲁斯卡尔算法正好相反，
适宜求解边稀疏的最小生成树。
由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。
因此，我们选择了普利姆算法对问题进行求解。
四概要设计
1.普利姆算法分析
1普利姆算法思想
普利姆算法的思想是：
在图中人去一个定点k0作为开始点，令U={k0}，W=V-U，
其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短
的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。
2算法过程描述
1）在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U={k0}，集合T（E）为空。
2）从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1，并使k1加入U。
即U={k0，k1}，同时将该边加入集合T（E）中。
3）重复
（2），直到U=V为止。
4）这时T（E）中有n-1条边，T=（U，T（E））就是一一颗最小生成树。
2、模块分析
根据对模型的功能分析，该管道铺设设计可以具有以下功能：
1管道铺设信息的输入；
2最小生成树信息的输出；
功能模块图：
3.抽象数据类型分析
areanum居民区总数（顶点总数）；
edgenum边的总数；
date[][20]邻接矩阵存储图结构；
s边的权值；
short-way[i]居民区i到目前生成树中所有点集U中某个居民区的路程最小值
near-area[i]U中能使其最小的居民区
5.全部流程
五、详细设计
1.算法分析
1信息输入模块
djvex,u）;
closedge[j].lowcost=[k][j].adj;
}
}
closedge[k].lowcost=0;djvex,[k]）;owcost=0;dj{
djvex,[k]）;
closedge[j].lowcost=[k][j].adj;
}
}
system（"pause"）;
}
2.源程序代码
#include<>
#include<>
#include<>
#include<>
#include<>
#defineMAX_VERTEX_NUM20exnum,&（*G）.arcnum）;
printf（"请输入%d个顶点的值:
\n",（*G）.vexnum）;
for（i=0;i<（*G）.vexnum;++i）exs[i]）;
for（i=0;i<（*G）.vexnum;++i）exnum;++j）
{
（*G）.arcs[i][j].adj=INFINITY;rcs[i][j].info=NULL;
}
printf（"请输入%d条边的顶点1顶点2权值（以空格作为间隔）:
\n",（*G）.arcnum）;
for（k=0;k<（*G）.arcnum;++k）
{
scanf（"%s%s%d%*c",va,vb,&w）;rcs[i][j].adj=（*G）.arcs[j][i].adj=w;rcs[i][j].info=（*G）.arcs[j][i].info=info;exnum;++i）
for（j=0;j<（*G）.vexnum;++j）
{if（j%3==0）printf（"\n"）;
printf（"%d",（*G）.arcs[i][j].adj）;
}
return1;
system（"pause"）;
}
owcost）
i++;
min=SZ[i].lowcost;owcost>0）
if（min>SZ[j].lowcost）
{
min=SZ[j].lowcost;
k=j;
}
returnk;
}
djvex,u）;
closedge[j].lowcost=[k][j].adj;
}
}
closedge[k].lowcost=0;djvex,[k]）;owcost=0;dj{
djvex,[k]）;
closedge[j].lowcost=[k][j].adj;
}
}
system（"pause"）;
}
voidmain（）
{试结果
七.设计体会
通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了大家的动手能力。
同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更是存在很大的差距。
程序的运行结果与理论推导结果完全吻合，即该算法与程序设计满足课程设计要求。
该程序的主要优点是简单易懂，不存在理解上的障碍，也很自然地能想到这种解法。
主要缺点是程序的变动性比较差—初始化邻接矩阵后结果就固定了。
如果能加入图行和图的修改、插入、删除等操作，我想应该会好很多。
八、结束语
转眼，为期两周的《数据结构》课程设计即将结束了。
在这次课程设计中我的c语言知识和数据结构知识得到了很好学习。
编程能力也有了一定的提高。
同时也学回了解决问题的方法。
总结起来，自己主要有以下几点体会：
1.必须牢固掌握基础知识。
由于C语言是大一所学知识，没有好好的去体会掌握，同时也没有掌握好上学期学的《数据结构》这门课，所以在课程设计初期感到无从下手，但在后来的设计过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所了解和熟悉。
这时才逐渐有了思路。
所以，在这次课程设计以后，我下了决心：
以后一定要好好学习好专业知识。
2.必须培养严谨的科学态度。
我在编写程序时经常因为一些类似于少写了分号，大括号不匹配等造成的程序调试失败，不够认真仔细，给自己带来了许多麻烦。
3.这次课程设计也让我充分的认识到《数据结构》这门课的重要性。
它给我们的一个思想和大纲，让我们再编程时更容易找到思路，不至于无章可循。
同时它也有更广泛的实际应用价值。
总之，在这次课程设计中，我的C语言以及数据结构知识得到了长足的进步，对编程有了更深层次的了解。
参考文献
1.谭浩强《C语言设计》第2版
2.严蔚敏《数据结构C语言版》
升级会员 