地铁建设问题.doc

1、软件学院课程设计报告书课程名称数据结构设计题目地铁建设问题专业班级学号姓名指导教师2013年1月1目录1设计时间22设计目的23设计任务24设计内容241需求分析2411程序所能达到的功能2412输入、输出的形式和输入值的范围2413测试数据342总体设计3421抽象数据类型定义3422主程序的流程、模块之间的调用关系443详细设计5431数据类型、函数的伪码算法5432函数的调用关系图944测试与分析10441测试10442分析1145附录115总结与展望16参考文献17成绩评定1721设计时间2012年1月21日2012年1月25日2设计目的1通过这次设计，在数据结构的逻辑结构和存储结构、

2、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解2训练程序设计方法以及上机操作等基本技能，积累编程经验3培养用计算机解决实际问题的能力3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容41需求分析411程序所能达到的功能城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要编写程序合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（1）使用结构体数组，存储辖区名称（2）建立辖区间直接距离的无向图，用邻接矩阵存储辖区间直接距离信

3、息（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线（3）输出应该建设的路线，以及所需建设的总里程信息412输入、输出的形式和输入值的范围输出的形式和输入值的范围输入数字和字母，字母为辖区名，数字为辖区间直接距离，名称个数O，0|V,WV且P（V，W），表示从V到W的弧，4谓词P（V,W）定义了弧的意义或信息基本操作PCREATEGRAPH（INTRMMINTVEXNUMGRAPH2函数算法创建无向图INTLOCATEVEXGRAPHG,CHARA10INTIFORI0IVEXNUMIIFSTRCMPA,GVI0RETURNIIFIGVEXNUMRETURN1INTCREATGRA

4、PHGRAPHGINTI0,J,M,K,P,O,ECHARA10,B106PRINTF“设置辖区的个数“/城市中辖区的个数SCANF“D“,FORI0IVIGVEXNUMOFORI0IVEXNUMIFORJ0JVEXNUMJGRIJINFINITYPRINTF“辖区之间的路程，以000为结束标志N“SCANF“SSD“,A,B,WHILESTRCMP“0“,A0|STRCMP“0“,B0|M0KLOCATEVEXG,APLOCATEVEXG,BIFK1PRINTF“没有S这个辖区N“,ARETURN0IFP1PRINTF“没有S这个辖区N“,BRETURN0GRKPGRPKMSCANF“SSD

5、“,A,B,7RETURN1STRUCTTREEINTWEIZHIINTLOWCOSTINTMINIMUNSTRUCTTREEA,GRAPHGINTI,K,M0FORI0IINCLUDEINCLUDEINCLUDEDEFINEINFINITY10000DEFINEM20TYPEDEFSTRUCTCHARVM10INTRMMINTVEXNUMGRAPHINTLOCATEVEXGRAPHG,CHARA10INTIFORI0IVEXNUMIIFSTRCMPA,GVI012RETURNIIFIGVEXNUMRETURN1INTCREATGRAPHGRAPHGINTI0,J,M,K,P,O,ECHARA

6、10,B10PRINTF“设置辖区的个数“/城市中辖区的个数SCANF“D“,FORI0IVIGVEXNUMOFORI0IVEXNUMIFORJ0JVEXNUMJGRIJINFINITYPRINTF“辖区之间的路程，以000为结束标志N“SCANF“SSD“,A,B,WHILESTRCMP“0“,A0|STRCMP“0“,B0|M0KLOCATEVEXG,APLOCATEVEXG,B13IFK1PRINTF“没有S这个辖区N“,ARETURN0IFP1PRINTF“没有S这个辖区N“,BRETURN0GRKPGRPKMSCANF“SSD“,A,B,RETURN1STRUCTTREEINTWEI

7、ZHIINTLOWCOSTINTMINIMUNSTRUCTTREEA,GRAPHGINTI,K,M0FORI0IGVEXNUMIIFM0KIIFM1RETURNKVOIDMINISPANTREE_PRIMGRAPHG,CHARA10STRUCTTREECLOSEDGEMINTI,J,K,MONEY0KLOCATEVEXFORI0IGVEXNUMIIFIKCLOSEDGEILOWCOSTGRKICLOSEDGEIWEIZHIKCLOSEDGEKLOWCOST0FORI1IGVEXNUMI15KMINIMUNCLOSEDGE,GMONEYCLOSEDGEKLOWCOSTPRINTF“DSSDN“,

8、I,GVCLOSEDGEKWEIZHI,GVK,CLOSEDGEKLOWCOSTCLOSEDGEKLOWCOST0FORJ0JGVEXNUMJIFGRKJCLOSEDGEJLOWCOSTCLOSEDGEJWEIZHIKCLOSEDGEJLOWCOSTGRKJPRINTF“总费用为DN“,MONEYVOIDMAININTIGRAPHGCHARA10ICREATGRAPHIFIPRINTF“从哪里开始“SCANF“S“,AMINISPANTREE_PRIMG,A165总结与展望这次课程设计任务是我在大学以来的遇到的第一次课程设计，刚开始看到题目的时候看起来不是很难，但是在实际编程操作中遇到了很多的

9、问题，不过，在不断地遇到和解决问题的过程中，学到了很多的知识。通过这一周的课程设计，加深了我对数据结构这门课程所学内容的进一步的理解与掌握。同时，通过设计程序解决地铁建设问题，让我明白学习知识不仅仅是要学习课本上的内容，还要从实际生活中学习课外的知识，把书本上的知识与现实生活好好的结合在一起。并且在查阅资料和完成设计的同时，我初步的了解了我们所学的课本知识在实际中的应用。同时，这次课程设计进一步锻炼了我的编写程序的能力，和同学的合作交流也让自己学到了更多，发现自己在实际问题分析中的不足。在编写程序的过程中，我更深切的认识到了认真、仔细、耐心的重要性，比如，就不能忽略循环时的控制变量。在本次课程

10、设计中，主要运用了图的知识解决实际问题。同过这次的应用实践，让我体会到了图之所以能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，也就是想要把生活中的信息用计算机表达出来，首先就得把他们数字化，具体化成计算机能够识别的信息。所以，我需要学习更多的专业知识以便用计算机更好的解决现实生活中遇到的问题。这次课程设计时虽然遇到了好多的问题，但是还会有意外的收获。这次就不仅练习了动手能力、综合能力，还巩固了专业知识，收获了很多。17参考文献1谭浩强C程序设计教程北京清华大学出版社2007072严蔚敏数据结构（C语言）清华大学出版社201033高维春主编C语言程序设计项目教程北京人民邮电出版社2010054谭浩强C程序设计题解与上机指导（第三版）M北京清华大学出版社2007成绩评定成绩教师签字