《数据结构》课程设计报告(管道铺设最佳方案)

《《数据结构》课程设计报告(管道铺设最佳方案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计扌艮告设计题目：管道铺设施工的最佳方案选择年级2009班级计科***姓名***学»1£■rTwrr^指导教师*****起止时间2011年2学期一.实习目的通过本些实习，了解并初步掌握设计、实现较大系统的完整过程，包括需求分析、系统设计、模块划分、编码选择、系统集成、以及程序调试，熟练常握数据结构的选择、设计、实现以及操作方法，为进一步的应用程序开发打好坚实的基础。二•问题描述(具体任务)设计、实现一个城市的居民区之间管道铺设方案的咨询程序，为用户提供一种最佳的管道铺设方案。三.需求分析该程序所做的工作的是模拟城市管道铺设方案设计，为用户提供一种最

2、佳决策的铺设方案。此程序规定：(1)在程序屮输入居民区名称(节点名称)时，可以输入数字和个字母的字符串；输入连通两居民区名称时需输入一个字符型数据；输入两居民区名称Z间距离(两结点之I'可权值)吋需输入一个整型数据。(2)程序的输出信息主要是：管道铺设方案中最佳的铺设方案。(3)程序的功能包扌舌：提供对城市居民区(节点)信息的编辑，提供一种最佳决策:能到达所有居民区(节点),且代价最小。四.算法设计思想及流程图可以用连通网來表示n个居民区间可能铺设的管道，其中网的顶点表示居民区，边表示居民区之间的线路，赋于边的权值表示相应的代价，对于n个顶点的连通网可以建立许多

3、不同的生成树，每一颗生成树都可以是一个管道网，现在，我们要选择这样一个生成树，也就是使总的耗费最小。这个问题就是构造连通网的最小代价生成树(MinimumCostSpanningTree)(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。普里姆(Prim)算法是一个利用MST性质构造最小生成树的算法，其时间复杂度为O(n*n)o适合求稠密图。假设N=(V,{E})是连通网，TE是N是最小生成树屮边的集合，算法从U={uo)(uoeV),TE={}开始，重复执行一述操作：在所有ueu,veV-U的边(u,v)uE中找一条代价最小的迦u(),vo)

4、并入集合TE,同吋vo并入U,直至U二V为止，此吋TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。五.C语言源代码#include#include#include#include#defineMAX20〃结点最大数#defineMAX.VERS20〃弧最大数#defineINFINITY32767intHaveData=O;〃标志位，表示是否有数据typedefstruct}char*vexs[MAX];intvexnum,arcnum;intarcs[MAX][MAX]

5、;〃邻接矩阵JMGraph;typedefstruct}intadjvex;intlowcost;}Close[MAX_VERS];intLocate(MGraphG,char*a)//查找结点位置{for(inti=0;i

6、(sizeof(char)*5);ch2=(char*)malloc(sizeof(char)*5);printfC1请输入居民区(节点)个数，边数，逗号隔开，节点和弧数应大于1!“)；scanf("%d,%d'&G.vexnum,&G.arcnum);getchar();for(i=0;i

7、m;i++)for(intj=0;j

8、gh;G.arcs[v2