搜索
数据结构课程设计报告设计题目：管道铺设施工的最佳方案选择年级2009班级计科***姓名***学号*********指导教师*****起止时间2011年2学期一．实习目的通过本些实习，了解并初步掌握设计、实现较大系统的完整过程，包括需求分析、系统设计、模块划分、编码选择、系统集成、以及程序调试，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用程序开发打好坚实的基础。二．问题描述（具体任务）设计、实现一个城市的居民区之间管道铺设方案的咨询程序，为用户提供一种最佳的管道铺设方案。三．需求分析该程序所做的工作的是模拟城市管道铺设方案设计，为用户提供一种最佳决策的铺设方案。此程序规定：（1）在程序中输入居民区名称(节点名称)时，可以输入数字和个字母的字符串；输入连通两居民区名称时需输入一个字符型数据；输入两居民区名称之间距离(两结点之间权值)时需输入一个整型数据。（2）程序的输出信息主要是：管道铺设方案中最佳的铺设方案。（3）程序的功能包括：提供对城市居民区(节点)信息的编辑，提供一种最佳决策：能到达所有居民区(节点),且代价最小。四．算法设计思想及流程图可以用连通网来表示n个居民区间可能铺设的管道，其中网的顶点表示居民区，边表示居民区之间的线路，赋于边的权值表示相应的代价，对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个管道网，现在，我们要选择这样一个生成树，也就是使总的耗费最小。这个问题就是构造连通网的最小代价生成树(MinimumCostSpanningTree)(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。普里姆(Prim)算法是一个利用MST性质构造最小生成树的算法,其时间复杂度为O(n*n)。适合求稠密图。假设N=(V,{E})是连通网，TE是N是最小生成树中边的集合，算法从U={u0}(u0∈V),TE={}开始，重复执行一述操作：在所有u∈U，v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止，此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。五．C语言源代码#includestdio.h#includestring.h#includestdlib.h#includemalloc.h#defineMAX20//结点最大数#defineMAX_VERS20//弧最大数#defineINFINITY32767intHaveData=0;//标志位，表示是否有数据typedefstruct{char*vexs[MAX];intvexnum,arcnum;intarcs[MAX][MAX];//邻接矩阵}MGraph;typedefstruct{intadjvex;intlowcost;}Close[MAX_VERS];intLocate(MGraphG,char*a)//查找结点位置{for(inti=0;iG.vexnum;i++)if(strcmp(G.vexs[i],a)==0)returni;return0;}voidCreate(MGraph&G)//按用户输入对图进行初始化{system(cls);printf(现在开始创建图\n);inti,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(\n\t请输入第%d个居民区(节点)!,i+1);G.vexs[i]=(char*)malloc(sizeof(char)*5);scanf(%s,G.vexs[i]);getchar();}for(i=0;iG.vexnum;i++)for(intj=0;jG.vexnum;j++)G.arcs[i][j]=INFINITY;//初始化所有边长为无穷for(i=0;iG.arcnum;i++){printf(\n\t请输入第%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.arcs[v1][v2]=weigh;G.arcs[v2][v1]=weigh;}HaveData=1;system(cls);}voidInit(MGraph&G)//采用自定义数据进行测试{FILE*fp;char*filename=size.txt;charbuff1[10],buff2[10];intdistance,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(intj=0;jG.vexnum;j++)G.arcs[i][j]=INFINITY;//初始化所有边长为无穷filename=vex.txt;if((fp=fopen(filename,r))==NULL){printf(文件打开出错!);return;}i=0;while(!feof(fp)){fscanf(fp,%s,&buff1);G.vexs[i]=(char*)malloc(sizeof(char)*5);strcpy(G.vexs[i++],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.arcs[v1][v2]=distance;G.arcs[v2][v1]=distance;}//whileprintf(\t\t\t载入完成!);HaveData=1;}intMini(MGraphG,CloseT)//求最小代价的弧{inti,k=0,min=32767;for(i=0;iG.vexnum;i++)if((T[i].lowcost!=0)&&(T[i].lowcost!=INFINITY)){min=T[i].lowcost;k=i;break;}for(i=0;iG.vexnum;i++)if(T[i].lowcost!=0&&T[i].lowcostmin){min=T[i].lowcost;k=i;}returnk;}//用普里姆算法输出最小生成树的边voidPrim(MGraphG,Closeclosedge,char*start){intS,i,k;charstart[10];system(cls);printf(\t\t请输入起始点:3);scanf(%s,&start);printf(\t\t最佳方案为:\n);S=Locate(G,start);for(i=0;iG.vexnum;i++)if(S!=i){closedge[i].lowcost=G.arcs[S][i];closedge[i].adjvex=S;}closedge[S].lowcost=0;for(i=1;iG.vexnum;i++){k=Mini(G,closedge);printf(\t\t%s----%s\n,G.vexs[closedge[k].adjvex],G.vexs[k]);//输出closedge[k].lowcost=0;for(intj=0;jG.vexnum;++j)if(G.arcs[k][j]closedge[j].lowcost)//更新{closedge[j].lowcost=G.arcs[k][j];closedge[j].adjvex=k;}//if}//for}intmain(){MGraphM;intselect;Closeclosedge;while(1){printf(\t\t欢迎使用管道最佳铺设方案咨询系统\n);printf(\t\t*********************************\n);printf(\t\t\t1.输入数据\t2.载入数据\n);printf(\t\t\t3.最佳方案\t4.退出\n);printf(\t\t*********************************\n);printf(\n\t\t请选择:);scanf(%d,&select);switch(select){case1:Create(M);break;case2:Init(M);break;case3:if(!HaveData)printf(\t\t没有数据，无法输出!\n);elsePrim(M,closedge,p);break;default:exit(0);}}//whilereturn0;}六．测试分析（运行结果）按照附录中的测试数据，得出如下测试、分析结果：1.操作员管理功能1.当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明咨询系统可以从键盘正确输入信息.2.我们事先建立了有关图的3个文本文件(包括size.txt,vex.txt,arc.txt),在本系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息.3.当从键盘或文本文件初始化城市居民区图后,测试增加或删除城市居民区结点,以上各功能都正确.2.最佳铺设方案咨询功能。3.打印打印结果正确。4.退出能正确退出。七．总结（收获及体会）1、收获及体会通过这次课程设计练习，使我们更深刻地理解了程序的精髓-----算法，完成整个程序设计使得对数据结构、算法的使用更加熟练。同时通过直接对图的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。经过这次课程设计，我们深刻认识到算法在程序设计中的重要性：程序=算法+数据结构。编程有时是一件枯燥乏味工作，只有坚持下去，才会有最终的胜利。2．感谢另外在这次程序设计的过程中，非常感谢老师对我们的耐心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有收获。同样也是老师的严格要求才使得小组成员能够顺利的完成任务。八．参考文献数据结构(C语言版)严蔚敏，吴伟民清华大学出版社C程序设计(第三版)谭浩强清华大学出版社附录：测试数据城市居民区表(共10个)居民区名称金色奥园状元府第紫竹小区世纪城理想城阳山公寓长江花园馨澳花园城南庄兴和城各小区距离(单位：米共18条)金色奥园状元府第1100金色奥园紫竹小区1050金色奥园世纪城950金色奥园理想城1200状元府第世纪城800状元府第长江花园900紫竹小区世纪城950紫竹小区阳山公寓970阳山公寓世纪城960阳山公寓馨澳花园1500长江花园世纪城990长江花园馨澳花园980长江花园城南庄1150长江花园兴和城960长江花园理想城1250城南庄馨澳花园1400城南庄兴和城900理想城兴