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

数据结构课程设计报告设计题目：管道铺设施工的最佳方案选择年 级 2009 班 级 计科* 姓 名 * 学 号 * 指导教师 * 起止时间 2011 年 2 学期一实习目的通过本些实习，了解并初步掌握设计、实现较大系统的完整过程，包括需求分析、系统设计、模块划分、编码选择、系统集成、以及程序调试，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用程序开发打好坚实的基础。二问题描述（具体任务）设计、实现一个城市的居民区之间管道铺设方案的咨询程序，为用户提供一种最佳的管道铺设方案。三需求分析 该程序所做的工作的是模拟城市管道铺设方案设计，为用户提供一种最佳决策的铺设方案。此程序规定：（1） 在程序中输入居民区名称(节点名称)时，可以输入数字和个字母的字符串；输入连通两居民区名称时需输入一个字符型数据；输入两居民区名称之间距离(两结点之间权值)时需输入一个整型数据。（2） 程序的输出信息主要是：管道铺设方案中最佳的铺设方案。（3） 程序的功能包括：提供对城市居民区(节点)信息的编辑，提供一种最佳决策：能到达所有居民区(节点),且代价最小。四算法设计思想及流程图 可以用连通网来表示n个居民区间可能铺设的管道，其中网的顶点表示居民区，边表示居民区之间的线路，赋于边的权值表示相应的代价，对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个管道网，现在，我们要选择这样一个生成树，也就是使总的耗费最小。这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree)(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。普里姆(Prim)算法是一个利用MST性质构造最小生成树的算法,其时间复杂度为O(n*n)。适合求稠密图。假设N=(V,E)是连通网，TE是N是最小生成树中边的集合，算法从U= u0( u0V),TE=开始，重复执行一述操作：在所有uU，vV-U的边(u,v) E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止，此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。五C语言源代码#include#include#include#include#define MAX 20 /结点最大数#define MAX_VERS 20 /弧最大数#define INFINITY 32767int HaveData=0; /标志位，表示是否有数据typedef structchar *vexsMAX; int vexnum,arcnum;int arcsMAXMAX; /邻接矩阵MGraph;typedef structint adjvex;int lowcost;CloseMAX_VERS;int Locate(MGraph G, char *a) /查找结点位置 for(int i=0;iG.vexnum;i+)if(strcmp(G.vexsi,a)=0)return i;return 0;void Create(MGraph &G) /按用户输入对图进行初始化 system(cls);printf(现在开始创建图n);int i,weigh,v1,v2;char *ch1,*ch2; ch1=(char *)malloc(sizeof(char)*5);ch2=(char *)malloc(sizeof(char)*5);printf(请输入居民区(节点)个数,边数,逗号隔开,节点和弧数应大于1!);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();for(i=0;iG.vexnum;i+)printf(nt请输入第%d个居民区(节点)!,i+1);G.vexsi=(char *)malloc(sizeof(char)*5);scanf(%s,G.vexsi);getchar();for(i=0;iG.vexnum;i+)for(int j=0;jG.vexnum;j+)G.arcsij=INFINITY; /初始化所有边长为无穷for(i=0;iG.arcnum;i+)printf(nt请输入第%d个弧的头:,i+1);scanf(%s,ch1);printf(t请输入第%d个弧的尾:,i+1);scanf(%s,ch2);printf(t请输入%s-%s的权值:,ch1,ch2);scanf(%d,&weigh);v1=Locate(G,ch1);v2=Locate(G,ch2);G.arcsv1v2=weigh;G.arcsv2v1=weigh;HaveData=1;system(cls);void Init(MGraph &G) /采用自定义数据进行测试FILE *fp; char *filename = size.txt; char buff110,buff210;int distance,i,v1,v2; if( (fp = fopen(filename,r) = NULL ) printf(文件打开出错!); return ; while(!feof(fp)fscanf(fp,%d,&v1);fscanf(fp,%d,&v2);G.vexnum=v1;G.arcnum=v2;fclose(fp);for(i=0;iG.vexnum;i+)for(int j=0;jG.vexnum;j+)G.arcsij=INFINITY; /初始化所有边长为无穷filename=vex.txt;if( (fp = fopen(filename,r) = NULL ) printf(文件打开出错!); return ; i=0;while(!feof(fp) fscanf(fp,%s,&buff1);G.vexsi=(char *)malloc(sizeof(char)*5);strcpy(G.vexsi+,buff1);fclose(fp); filename=arc.txt;if( (fp = fopen(filename,r) = NULL ) printf(文件打开出错!); return ; i=0;while(!feof(fp)fscanf(fp,%s,&buff1);fscanf(fp,%s,&buff2);fscanf(fp,%d,&distance);v1=Locate(G,buff1);v2=Locate(G,buff2);G.arcsv1v2=distance;G.arcsv2v1=distance;/whileprintf(ttt载入完成!);HaveData=1;int Mini(MGraph G,Close T) /求最小代价的弧int i,k=0,min=32767;for(i=0;iG.vexnum;i+)if(Ti.lowcost!=0) & (Ti.lowcost!=INFINITY) )min=Ti.lowcost;k=i;break;for(i=0;iG.vexnum;i+)if(Ti.lowcost!=0 & Ti.lowcostmin)min=Ti.lowcost;k=i;return k;/ 用普里姆算法输出最小生成树的边void Prim(MGraph G,Close closedge,char *start)int S,i,k; char start10;system(cls);printf(tt请输入起始点:3);scanf(%s,&start);printf(tt最佳方案为:n);S=Locate(G,start);for(i=0;iG.vexnum;i+)if(S!=i)closedgei.lowcost=G.arcsSi;closedgei.adjvex=S;closedgeS.lowcost=0;for(i=1;iG.vexnum;i+)k=Mini(G,closedge);printf(tt%s-%sn,G.vexsclosedgek.adjvex,G.vexsk); /输出closedgek.lowcost=0;for(int j=0;jG.vexnum;+j)if(G.arcskj. 当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明咨询系统可以从键盘正确输入信息.2. 我们事先建立了有关图的3 个文本文件(包括size.txt,vex.txt,arc.txt),在本系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息.3. 当从键盘或文本文件初始化城市居民区图后,测试增加或删除城市居民区结点,以上各功能都正确.2. 最佳铺设方案咨询功能。3.打印 打印结果正确。4.退出能正确退出。七总结（收获及体会）1、收获及体会通过这次课程设计练习，使我们更深刻地理解了程序的精髓-算法，完成整个程序设计使得对数据结构、算法的使用更加熟练。同时通过直接对图的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。经过这次课程设计，我们深刻认识到算法在程序设计中的重要性：程序=算法+数据结构。编程有时是一件枯燥乏味工作，只有坚持下去，才会有最终的胜利。 2感谢另外在这次程序设计的过程中，非常感谢老师对我们的耐心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有收获。同样也是老师的严格要求才使得小组成员能够顺利的完成任务。八参考文献数据结构(C语言版) 严蔚敏，吴伟民 清华大学出版社C程序设计(第三版) 谭浩强 清华大学出版社附录：测试数据城市居民区表 (共10个)居民区名称金色奥园状元府第紫竹小区世纪城理想城阳山公寓长江花园馨澳花园