数据结构课程设计-地铁建设问题.doc

the principle of simplified EIA of construction projects in the region. In terms of land, linked to the implementation of urban and rural construction land increase and decrease, replacement indicators for priority areas project. Charges, into the projects of water, electricity, administrative charges and preferential policies. In the area of taxation, and settled in areas of industry and its production company, within 5 years after the completion of fiscal incentives to enterprises. In terms of financing, integration of land, tax, financial and other resources, and construct Government credit + business credit credit system, establishment of marketization, commercialization and modernization of the investment and financing platform; effective Bank-enterprise docking, encourages private capital into the Park, to raise industry development fund. 5, optimize the environment and service industries. To create policy lowlands, Highlands, integrity of service land, development land as the goal, to optimize the area under development environment. All administrative law enforcement departments to appoint a full-time personnel stationed in areas dedicated to coordinating and solving problems associated with businesses in this sector. When there are substantial issues, sector leaders arranged to personally intervene, in-person, in-person push tangible area building a green light, easy line. To further reduce and standardize administrative examination and approval items, simplify examination and approval links, improve efficiency; according to the .Since the educational practice of the mass line of the party, himself seriously in the education, practical control central eight rules and opposing the four winds and practicing three Suns, and check the spirit of Jiao Yulu, ideology, solicit opinions based on outstanding problems checked swing, careful analysis and reflection. Will now check report is as follows: first, adherence to the partys political discipline, eight in the central provision, change the style of the basic situation of 1, in compliance with the partys political disciplines. Conscientiously abide by the partys political discipline, abide by the Constitution and the rules and regulations of the party, in the political, ideological and maintain highly consistent with the CPC Central Committee on the action, there is no violation of the partys political discipline problems. 2, in the implementation of the central authorities of the eight provisions. Improving research, improving research methods, but there are less grass-roots units, primary first-hand an inadequate grasp of the problem, which is to be strengthened in the future. Second, construction, strictly in accordance with the provisions to streamline and improve the quality of meetings of the Conference. Third, streamlining file briefs, culture involves all aspects of propaganda and ideology, sometimes due to the practical needs of invention notifications, this area needs further软 件 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2013 年 1 月发包人指定专人负责协调施工中的有关事宜，并监督施工进度、安全与文明施工。发包人对承包人施工中违规操作有权做好处理决定或经济处罚。streamlining. Four are standard visits, except as required to participate in training, no other activity. Five is to improve news reporting, for propaganda work strictly according to the regulations. Six is strictly your presentation published strictly according to the regulations. Seven is strictly thrift, required the use of vehicles and office space and corporate hospitality. 3, change the style. Propaganda and ideological work of the new situation and new requirements of the new tasks, had done a lot of fruitful work, has made many achievements, but further closer to the grass roots, close to reality, close to the masses and also inadequate innovation must continue to improve. Second, the four winds some outstanding issues 1, oppose formalism. One theory is that he didnt, with less close contact. Theoretical study of consciousness is not high enough, system performance is not strong enough; more passive learning, active learning few generalities and learn more, delving into less. Especially based on rational thinking on major issues, applying theory to guide the work done is not good enough, not really understand and grasp the spirit and essence of the scientific Outlook on development, did not truly achieve mastery, to apply, to a certain extent, affect the development and implementation of ideas and initiatives. Second, work arrangements, and less supervision. Propaganda and ideological work is the objective, which needs to keep the continuity efforts deployed, but stressed in the work time, less supervision. For example, color weekends in the summer theatrical activities, city square performances, urging townships, communities and rural areas shows the implementation is inadequate, insufficient cultural an educational role to play. Third base enough, master grass-less real. Propaganda and ideological work in the new situation of characteristics and regularity of enough, deep enough for grass-roots public opinion Dynamics survey, for grass-roots typically drive less. For example, rural culture team active, . Im not actively take the initiative to take up, the lack of spirit of daring to, resulting in some job had a lot of power, but no tangible results. Third, innovation, lack of motivation. Emancipation did not end, innovation does not exist. In practical work, not your head, previous work experience, lack of innovation initiatives, study on the characteristics of propaganda and ideological work under the new situation through, grip on grassroots ideological trends and changes are not deep, to promote new initiatives and explore new methods of ideological and cultural work is not much, and some lack of relevance and timeliness. 4, discipline, lowering, and hard work are lacking. While working and enterprising spirit down. No real solution to treat yourself right, correctly treat past honors, their complacency, and work to see their scores more, less checking his own shortcomings, like to listen to the praise, satisfied face, online promotion, there are typical, and lack of high standards and strict requirements, the effect is real. Second hard drive less. On hard and 目 录1 设计时间12 设计目的13设计任务14 设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析114.4.1测试114.4.2分析134.5 附录145 总结与展望20参考文献22成绩评定2221 1 设计时间2013年1月16日至2013年1月21日2 设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。1. 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）；2. 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路；3. 输出应该建设的地铁线路及所需建设总里程。4 设计内容 4.1需求分析1、程序所能达到的功能：(1)根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。(2)根据普利姆算法计算最小生成树。(3)输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比）。(4)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(5)输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见4.4.1测试部分。3、输出的形式及内容： 包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见4.4.1测试部分。4、测试数据： 四个城市abcd及其之间的距离权值，详见4.4.1测试部分。4.2总体设计4.2.1数据类型的定义1.图的邻接矩阵存储数据类型定义：typedef struct char VM10; int RMM;int vexnum;Graph;）2.辅助数组数据类型定义：typedef structint adjvex;int lowcost;closedgeMAX;4.2.2基本操作：CreateCity(&G)操作结果：构造一个无向图G；LocateDistri(Graph g,int u)操作结果：找出目标城市的位置；Min(Graph g,closedge closedge)操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam1)操作结果：用普里姆算法找到连接各辖区的最短路；4.2.3主程序的流程主程序的流程如图1所示： 图14.2.4各程序模块之间的层次（调用）关系各程序模块之间的层次（调用）关系如图2所示：图24.3详细设计4.3.1预处理#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /创建图的结构体 char VM10; /顶点数组，用来存储辖区的值即辖区的名称 int RMM; /邻接矩阵，邻接矩阵的元素值为辖区之间的距离 int vexnum; /辖区的个数Graph; struct tree int weizhi; int lowcost;4.3.2创建辖区无向图的算法int creatgraph(Graph *g) /创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵 int i=0,j,m,k,p; char a10,b10; printf(*欢迎使用本程序解决地铁建设问题*n); printf(*请按照提示依次输入相关信息*n); printf(*请输入所有的辖区，以0作为结束标志*n); scanf(%s,g-Vi);/输入结点值 while(strcmp(0,g-Vi)!=0) i+; scanf(%s,g-Vi); g-vexnum=i; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY;/初始化 printf(*请输入辖区之间的路程，以0 0 0为结束标志*n); scanf(%s%s%d,a,b,&m); /输入辖区结点及辖区之间的距离 while(strcmp(0,a)!=0 | strcmp(0,b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);/查找a,b在图中的位置 if(k=-1) printf(*对不起，输入错误，没有%s这个辖区*n,a);return 0; if(p=-1) printf(*对不起，输入错误，没有%s这个辖区*n,b);return 0;g-Rkp=g-Rpk=m;/k到p和p到k之间的距离相同 scanf(%s%s%d,a,b,&m); /输入辖区结点及辖区之间的距离 return 1;struct tree int weizhi; int lowcost;int minimun(struct tree *a,Graph g) /求出第k辖区，此时i辖区与k辖区之间的距离最短int i,k,m=0; for(i=0;ig.vexnum;i+) if(m=0 & ai.lowcost!=0) m=1; k=i; if(m=1 & ai.lowcost!=0)if(ai.lowcostak.lowcost)k=i; return k;4.3.3定位函数int locatevex(Graph *g,char a10) /查找辖区u在辖区图中的位置int i;for(i=0;ivexnum;i+)/循环执行条件是当u=Vi时停止，求i值if(strcmp(a,g-Vi)=0)return i; if(i=g-vexnum)return -1; 4.3.4求最小生成树的结点算法int minimun(struct tree *a,Graph g) /求出第k辖区，此时i辖区与k辖区之间的距离最短int i,k,m=0;for(i=0;ig.vexnum;i+)if(m=0 & ai.lowcost!=0)m=1; k=i;if(m=1 & ai.lowcost!=0)if(ai.lowcostak.lowcost)k=i;return k;4.3.5 PRIM算法及输出void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a);for(i=0;ig.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; /两辖区k，i之间的距离closedgei.weizhi=k; /与辖区i相邻的最近的辖区设为辖区k closedgek.lowcost=0;/初始化，U=uprintf(*根据您的输入建立邻接表为:*n); for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) printf(|%d| ,g.Rij); printf(nn); printf(*得到应建设地铁的辖区及之间权值为:*n); for(i=1;ig.vexnum;i+) k=minimun(closedge,g); /求出最小生成树T的下一个结点，第k结点 money+=closedgek.lowcost; printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); /输出生成树的边 closedgek.lowcost=0; /第k顶点并入U集 for(j=0;jg.vexnum;j+) if(g.Rkjclosedgej.lowcost) /新顶点并入集后，选择新的边，将小的边放到辅助数组中 closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf(*据统计地铁的总建设路程为：%d *n,money);4,3,6主函数模块void main()int i; Graph g; char a10; i=creatgraph(&g); if(i)printf(*请输入起始地点为：*n); scanf(%s,a); MiniSpanTree_PRIM(g,a);printf(*感谢使用本程序，谢谢！*n);4.4测试与分析4.4.1测试测试数据：1.以图3为例图 32.输入城市区域名称，如图4所示：图 43.根据需要，依次输入各个区域代号和边的权值，如图5所示：图 54.根据提示，输入地铁站的起始地点如图6所示：图 65.输出最终结果，如图7所示：图 74.4.2分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。最首要的任务就是选择合适的计算思路，并加以实现。经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。经过编写，调试，最终完成了程序的设计。2.算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为O(n3)，空间复杂度为O(2n) 表达是求值，主要是运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3.针对可能出现的输入错误，作出相应的应对措施：如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图8所示：图84.5 附录源程序：#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /创建图的结构体 char VM10; /顶点数组，用来存储辖区的值即辖区的名称 int RMM; /邻接矩阵，邻接矩阵的元素值为辖区之间的距离 int vexnum; /辖区的个数Graph; int locatevex(Graph *g,char a10) /查找辖区u在辖区图中的位置int i; for(i=0;ivexnum;i+)/循环执行条件是当u=Vi时停止，求i值 if(strcmp(a,g-Vi)=0) return i; if(i=g-vexnum) return -1; int creatgraph(Graph *g) /创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵 int i=0,j,m,k,p; char a10,b10; printf(*欢迎使用本程序解决地铁建设问题*n); printf(*请按照提示依次输入相关信息*n); printf(*请输入所有的辖区，以0作为结束标志*n); scanf(%s,g-Vi);/输入结点值 while(strcmp(0,g-Vi)!=0) i+; scanf(%s,g-Vi); g-vexnum=i; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY;/初始化 printf(*请输入辖区之间的路程，以0 0 0为结束标志*n); scanf(%s%s%d,a,b,&m); /输入辖区结点及辖区之间的距离 while(strcmp(0,a)!=0 | strcmp(0,b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);/查找a,b在图中的位置 if(k=-1) printf(*对不起，输入错误，没有%s这个辖区*n,a);return 0; if(p=-1) printf(*对不起，输入错误，没有%s这个辖区*n,b);return 0;g-Rkp=g-Rpk=m;/k到p和p到k之间的距离相同 scanf(%s%s%d,a,b,&m); /输入辖区结点及辖区之间的距离 return 1;struct tree int weizhi; int lowcost;int minimun(struct tree *a,Graph g) /求出第k辖区，此时i辖区与k辖区之间的距离最短int i,k,m=0; for(i=0;ig.vexnum;i+) if(m=0 & ai.lowcost!=0) m=1; k=i; if(m=1 & ai.lowcost!=0)if(ai.lowcostak.lowcost)k=i; return k;void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a);for(i=0;ig.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; /两辖区k，i之间的距离closedgei.weizhi=k; /与辖区i相邻的最近的辖区设为辖区k closedgek.lowcost=0;/初始化，U=uprintf(*根据您的输入建立邻接表为:*n); for(i=0;ig.vexnum;i+