数据结构课程设计地铁建设问题_第1页
数据结构课程设计地铁建设问题_第2页
数据结构课程设计地铁建设问题_第3页
数据结构课程设计地铁建设问题_第4页
数据结构课程设计地铁建设问题_第5页
已阅读5页,还剩19页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、软件学院课程设计报告书课程名称数据结构设计题目地铁建设问题专业班级学号姓名指导教师2013年1月目录1设计时间22设计目的23设计任务24设计内容24.1需求分析24.1.1程序所能达到的功能24.1.2输入'输出的形式和输入值的范围24.1.3测试数据34.2总体设计34.2.1抽象数据类型定义34.2.2主程序的流程、模块之间的调用关系44.3详细设计54.3.1数据类型、函数的伪码算法54.3.2函数的调用关系图94.4测试与分析104.4.1测试104.4.2分析114.5附录115总结与展望16参考文献17成绩评定171设计时间2012年1月21日2012年1月25日2设计目

2、的1通过这次设计,在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解2 .训练程序设计方法以及上机操作等基本技能,积累编程经验3 .培养用计算机解决实际问题的能力3设计任务某城市要在各个辖区之间修建地铁,山于地铁建设费用昂贵,因此需要合理安排地铁建设线路,使市民可以沿地铁到达各个辖区,并使总费用最小。4设计内容4.1 需求分析4.1.1 程序所能达到的功能城市要在各个辖区之间修建地铁来加快经济发展,但山于建设地铁的费用昂贵,因此需要编写程序合理安排地铁的建设路线,使乘客可以沿地铁到达各个辖区,并使总的建设费用最小。(1)使用结构体数组,存储辖区

3、名称(2) 建立辖区间直接距离的无向图,用邻接矩阵存储辖区间直接距离信息(3) 根据读入的辖区距离信息,计算出应该建设哪些辖区的地铁路线(4) 输出应该建设的路线,以及所需建设的总里程信息4.1.2 输入、输出的形式和输入值的范围输出的形式和输入值的范圉输入数字和字母,字母为辖区名,数字为辖区间直接距离,名称个数。,0线路个数<o(0-1),直接距离m,0<m<10000输出的形式1:辖区名辖区名路程2:辖区名辖区名路程3:辖区名辖区名路程总费用为:路程的和4.1.3 测试数据正确输入:辖区个数:4名称abed线路起止辖区及直接距离:db3>dc5>ad4>

4、bc2>bd3>cd2>000开始辖区:a输出为:1:ab32:be23:cd2总费用:7错误输入:辖区个数:4名称abed线路及之间距离:asb3输出为:没有as这个辖区4.2总体设计4.2.1抽象数据类型定义1.抽象数据类型图的定义ADTGraph数据对象V:V是具有相同特性的数据元素的集合,成为顶点集。数据关系R:R二VRVR=<v,w>v,wWV且P(v,w),<v,w>表示从v至w的弧,谓词P(V,W)定义了弧v,w>的意义或信息、基本操作P:CreateGraph(&G,V,VR);初始条件:V是图的顶点集,VR是图中弧的集合

5、。操作结果:按V和VR的定义构造图G。ADTGraph422主程序的流程、模块之间的调用关系主程序的流程模块之间的调用关系(1)主函数main。调用intcreatgraph(Graph*g)建立无向图,用邻接矩阵存储;(2)voidMiniSpanTree_PRIM(Graphg,chara10)调用intminimun(structtree*a,Graphg)和intlocatevex(Graph*g,chara10)生成树,判断辖区名称输入是否正确;(3)主函数main()调用voidMiniSpanTree_PRIM(Graphg,chara10)计算最小生成树,输出最优线路和总里程。

6、4.3详细设计4.3.1数据类型、函数的伪码算法1 .结构体类型typedefstruct)charVM10;intvexnum;(Graph;2 .函数算法创建无向图intlocatevex(Graph*g,chara10)(inti;for(i=0;i<g->vexnum;i+)(if(strcnip(a,g->Vi)=O)returni;if(i=g,>vexnum)return-1;)intcreatgraph(Graph*g)(inti=0J,mkpoe;chara10,b10;printfC*设置辖区的个数:“);城市中辖区的个数scanfd&o);

7、for(i=0;i<o;i+)建立城市辖区名数组(printf(f%d个城市辖区名称为:“,i+1);scanf(H%su,g->Vi);g->vexnum=o;for(i=0;i<g->vexnum;i+)for(j=0;j<g->vexnum;j+)g->Rij=INFINITY;printf(“辖区之间的路程,以000为结束标志n“);scanf("s%s%d”,a,b,&m);while(strcmp(nOM,a)!=OIIstrcmp(nOu,b)!=OIIm!=0)k=locatevex(g,a);p=locatev

8、ex(g,b);if(k=-l)printf("没有$这个辖区n”,a);return0;printf(没有$这个辖区nb);return0;g->Rkp=g->Rpk=m;scanf("s%s%cT,a,b,&m);return1;structtreeintweizhi;intlowcost;intmininiun(structtreeGraphg)inti,k,m=O;for(i=0;i<g.vexnum;i+)(if(m=O&&ai.lowcost!=0)(m=1;k=i;)if(m=l&&ai.lowcost

9、!=0)(if(ai.Iowcost<ak.lowcost)k=i;1returnk;)普利姆算法求最小生成树,输出最优线路及费用voidMiniSpanTree_PRIM(Graphg.chara10J)(structtreeclosedgeM;intij5kjnoney=0;k=locatevex(&g,a);for(i=0;i<g.vexnum;i+)closedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgek.lowcost=0;for(i=l;i<g.vexnum;i+)k=minimun(closedge,g);

10、money+=closedgek.lowcost;printf(H%d:%s%s%dni,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost);ciosedgek.lowcost=0;for(j=0;j<g.vexnum;j+)if(g.Rkj<closedgej.Iowcost)(ck)sedgej.weizhi二k;closedgejlowcost二gRkj;>)printfC*总费用为:%dnH,money);432函数的调用关系图4. 4测试与分析4. 4. 1测试1.正确的输入城城城城不个个个-12 3 4年名名名名葭区区区区于 &

11、amp;一cd 0。为结品标志ah beB:3:总Pressanykeytocontinue2.错误的输入为为为为>0>»# 谴 1 2 3巨品C:WIKDO¥Ssysto»L32c«L<i.ex©cd00为结束标志Pi»eeant;keytocontxnue4.4.2分析调试过程中遇到的问题及其解决方法(1)问题:用for循环语句控制输入辖区名称及输出辖区名称时候的个数名不对应解决方法:数组下标时从零开始的,并且在for循环语句中,循环变量的执行次数总是比循环体的执行次数多一次,所以应该注意修改使其相对应(2)问题

12、:用循环控制各辖区及其之间的距离没有考虑清楚解决方法:用输入。00判定辖区及其直接距离数据输入完毕(3)问题:普利姆算法理解不透彻,用其计算最小生成树输出结果的时候出现问题解决方法:上网查阅资料及阅读课本询问同学,并在以前程序上加以修改,最终得以运行。4.5附录#indu(le<stclio.h>#defineINF32767typedefintInfoType;#defineMAXV100typedefstruct(intadj;InfoType*lnfo;ArcCell,AdjMatrixMAXVMAXVJ;typedefstruct(intedgesMAXVMAXV;intn

13、,e;intvexsMAXV;JMGraph;typedefstructANodeintadjvex;structANode*nextarc;InfoTypeinfo;JArcNode;typedefintVertex;typedefstructVnode(Vertexdata;ArcNode*flrstarqJVNode;typedefVNodeAdJListMAXV;typedefstruct(AdjListadjlist;intn,e;JALGraph;intsum=O;intLocatevex(MGraphg,intA)(inti;for(l=0;i<g,n;i+)(if(A=g

14、.vexsi)returni;)if(i=g.n)return1;intCreateMgraph(MGraph&g)int ij,k,w,vl,v2;printf("3s"畀oo”);elsepantfu%3d/gedges-11111deUsh-A)oljjprim(MGraph必34W)inI1omcos=MAXVhmm3二g-HinfclosesI1MAXVJfcKM-u.+4lowcossllgedges=sclosessnw;)M-O,=一+<mmHINF;fora=o;J:Il;j+一n-eoMuoss=o<<1。mmHoxvcostE

15、;中.)prms国M司ms区(堂dd)滩区=恭窿$:%dn.2.oses=khrmm)"-Slnn+HmimkHVCOS=kjHO;J。|WUII+in6P68SUJUJ=O会会6P68S【3MuOsm4alowcostJ=g.edgeskJ;closestJ=k;print”建设铁路线的最低费用为:%dii-sum);)voidmain()(intij;MGraphg;CreateMgraph(g);pHntf("辖区图的邻接矩阵:n");DispMat(g);prlntfC*普里姆算法结果:nH);Prim(g,O);printf(-ir);5总结与展望这次课

16、程设计任务是我在大学以来的遇到的第一次课程设计,刚开始看到题U的时候看起来不是很难,但是在实际编程操作中遇到了很多的问题,不过,在不断地遇到和解决问题的过程中,学到了很多的知识。通过这一周的课程设讣,加深了我对数据结构这门课程所学内容的进一步的理解与掌握。同时'通过设计程序解决地铁建设问题,让我明口学习知识不仅仅是要学习课本上的内容,还要从实际生活中学习课外的知识,把书本上的知识与现实生活好好的结合在一起。并且在查阅资料和完成设计的同时丁我初步的了解了我们所学的课本知识在实际中的应用。同时.,这次课程设计进一步锻炼了我的编写程序的能力,和同学的合作交流也让自己学到了更多,发现自己在实际问题分析中的不足。在编写程序的过程中,我更深切的认识到了认真、仔细、耐心的重要性,比如,就不能忽略循环时的控制变量。在本次课程设计中,主要运用了图的知识解决实际问题。同过这次的应用实践,让我体会到了图之所以能够在计算机中存在,首先要捕捉他有哪些具体化、数字化的信息,比如说权值、顶点个数等,也就是想要把生活中的信息用计算机表达出来,首先就得把他们数字化,具体化成

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论